Topic 7a – Reinforcement Learning

When you cannot check every possibility, you climb toward the best answer you can find — or let evolution find it for you.

Learning Objectives

By the end of this topic, you should be able to:

This topic is not assessed on a Competency Demo. The material here — reinforcement learning, hill climbing, and genetic algorithms — is important for building a complete picture of how AI systems learn, but it will not appear on CD #6. Instead, you will return to this material at the end of the week when you complete the AI Post-Reflection on Blackboard. That reflection asks you to connect what you encountered across both AI weeks to your thinking about teaching and AI. The ideas in this topic are worth your genuine attention — they will make your reflection richer.

Learning Activities

To help you meet the learning objectives, we have prepared a combination of readings, activities, and videos.

Course Readings

These reading were designed to introduce the course topics to an audience of educators. They should be considered "required" and read in order.

Supplemental Readings

Some participants find it helpful to read about a topic from a source written for a slightly more technical audience. These supplemental readings cover similar material as the course readings but may not fully align with the course learning objectives. Use them as an optional complement to your study, not a substitute for the course readings.

Lesson Videos

These videos support the readings above and may present the material with some deeper connections and worked examples.

Checking for Understanding, Questions

Optimization and Fitness Landscapes

  1. A school district wants to assign 40 teachers to 40 classrooms to minimize travel time between rooms for team-teaching pairs. There are more than 8 × 1047 possible assignments. Why is exhaustive search impossible here? What does this tell us about the kind of algorithm needed?
  2. Describe a fitness landscape for the classroom assignment problem. What does a "peak" represent? What does a "valley" represent? What would it mean for two solutions to be "neighbors"?

Hill Climbing

  1. Trace hill climbing on the following simplified scenario: a teacher is trying to find the best order for five topics in a unit, scored by student engagement ratings from a pilot. She starts with order [A, B, C, D, E] which scores 62. Swapping B and C produces a score of 71. Swapping A and B from the new arrangement produces 68. Swapping D and E produces 74. Swapping C and D produces 73. What does hill climbing do at each step? Where does it stop?
  2. A hill climbing agent searching for a good weekly staff meeting schedule keeps trying small changes but every change it considers makes the score worse. It stops and reports the current schedule as optimal. A staff member points out that a completely different schedule structure — moving the meeting to a different day entirely — would be dramatically better. Which hill climbing pathology does this illustrate? Why couldn't the agent find the better solution?

Genetic Algorithms

  1. A genetic algorithm is being used to optimize a school bus route. The population consists of ten candidate routes. After evaluating fitness, the two best-performing routes are selected as parents. Their routes are split at the midpoint and recombined to create two offspring routes. One offspring has a randomly swapped stop order.
    • Which step is selection? Which is crossover? Which is mutation?
    • Why might the offspring routes be better than either parent?
    • Why might they be worse? What happens in the next generation if they are?
  2. Explain in your own words why genetic algorithms are better than hill climbing at escaping local optima. What specific mechanism allows a genetic algorithm to explore parts of the solution space that hill climbing would never reach?
  3. Both hill climbing and genetic algorithms improve solutions through a reward signal rather than labeled training data. In one or two sentences, explain how this connects them to the reinforcement learning category from Topic 6c.

Checking for Understanding, Answers

You can compare your answers to the following answer key.

Show Answer Key

Optimization and Fitness Landscapes

  1. 8 × 1047 is a number so enormous that even checking one assignment per nanosecond for the entire age of the universe would not come close to evaluating them all. Exhaustive search is computationally impossible. This tells us the problem requires a heuristic or approximation approach — an algorithm that finds a good solution without guaranteeing the globally optimal one, by intelligently navigating the solution space rather than checking everything.
  2. In the fitness landscape for classroom assignment: a peak represents a particular assignment of teachers to classrooms that scores better than all its immediate neighbors — the lowest total travel time reachable by swapping any single teacher-room pair from that configuration. A valley represents an assignment that scores worse than most of its neighbors — high travel time. Two solutions are neighbors if one can be reached from the other by a single small change, such as swapping two teachers between their currently assigned classrooms.

Hill Climbing

  1. Hill climbing always moves to a neighbor with a higher score, stopping when no improvement is available. Step by step: start at [A,B,C,D,E], score 62. Try swapping B and C → score 71 (improvement) → accept, now at [A,C,B,D,E], score 71. Try swapping A and B → score 68 (worse) → reject. Try swapping D and E → score 74 (improvement) → accept, now at [A,C,B,E,D], score 74. Try swapping C and D → score 73 (worse) → reject. If no remaining swaps improve the score, hill climbing stops at [A,C,B,E,D] with score 74. This may or may not be the globally best ordering.
  2. This illustrates a local optimum: the agent is at a configuration where every small change (every neighboring solution) is worse, so it stops — even though a much better solution exists elsewhere in the space. Hill climbing only moves to neighboring solutions; it has no mechanism to jump to a distant, very different part of the solution space. The dramatically better schedule (a different day entirely) is not reachable by a sequence of small incremental changes from the current position without first passing through many worse solutions, so the agent can never get there.

Genetic Algorithms

    • Selection = choosing the two best-performing routes as parents. Crossover = splitting each route at the midpoint and recombining them to create two new routes. Mutation = randomly swapping a stop order in one offspring.
    • The offspring might be better because each parent contains a different combination of good route segments. Crossover combines the best features of each parent into a single route that neither parent had — a new arrangement that inherits the strengths of both.
    • They might be worse because crossover can produce combinations that conflict — a sequence of stops that seemed efficient in one parent may not work well when spliced with the other half of a different parent. If offspring are worse, they simply score poorly in the next fitness evaluation and are unlikely to be selected as parents for the next generation — they are naturally "weeded out."
  2. Genetic algorithms maintain a population of many diverse solutions simultaneously, rather than a single current position. When selection, crossover, and mutation are applied, offspring can appear anywhere in the solution space — including regions far from any parent. This diversity means the algorithm is effectively exploring many different parts of the landscape at once. A local optimum for one individual in the population does not trap the entire search; other individuals in different parts of the space continue to evolve, and crossover can combine distant solutions in ways that escape any single local peak.
  3. Both techniques use a fitness score (a reward signal) to evaluate how good each solution is and to guide improvement over time, without requiring any labeled training examples. This is the defining feature of reinforcement learning: learning is driven by feedback about outcomes rather than by being shown correct answers.

Extend Your Learning

The following resources go a little deeper on topics we touched on but did not fully explore in the readings. These are entirely optional — none of this material appears on the Competency Demo — but each one is a natural "next question" from something covered this week.

  • Neuroevolution: evolving neural networks
    Using genetic algorithms to evolve the structure and weights of neural networks, rather than training them by gradient descent. This active research area combines Topics 7a (this topic) and 6e in interesting ways. This overview from Uber AI Labs introduces the concept and explains why it is sometimes competitive with gradient-based training.
    Evolution Strategies as a Scalable Alternative to Reinforcement Learning — arXiv