Mansori

Reinforcement Learning: An Agent Learns a Maze

About this lesson, for parents and teachers

Nobody tells this robot where the goal is. It only gets points for reaching it and loses points for falling in the pit. Watch it learn the maze from experience alone.

Ages 15–18 · about 10 minutes · builds on Shortest Path on a Map

Try this

  1. Press Watch 1 episode. With no experience, the agent wanders randomly until it bumps into the goal or the pit.
  2. Press Train 10 episodes a few times. Green spreads backwards from the goal and arrows point the way.
  3. When the dotted path turns green it is a shortest route. Tap a square on it to build a wall, then train again.
  4. Set explore ε to 0 on a fresh start, or discount γ low, and see how learning changes.

How it works

In reinforcement learning an agent takes actions in an environment and receives rewards. Here the agent is in a square (its state) and can move up, down, left or right. Reaching the goal gives +10, the pit gives -10, and every step costs -0.1 so that shorter routes are better. Nobody shows it the answer; it must discover it by trial and error.

The agent keeps a table of Q-values: Q(s, a) estimates the total future reward of taking action a in state s. After every move it updates one entry: Q ← Q + α [r + γ · max Q(s') - Q]. The part in brackets is the surprise: what it got plus the best it expects next, minus what it guessed. The learning rate α sets how far to move toward that new estimate.

At first only the move into the goal earns a big reward. On later episodes, the square before it learns "from here I can reach a high-value square", then the square before that, and so on. That is why you see value spread backwards from the goal. The discount γ makes rewards further away count a little less, so the agent prefers shorter paths.

An agent that always takes its current best move may never discover a better route. So during training it uses ε-greedy exploration: with probability ε it moves randomly. This is the explore versus exploit trade-off. The arrows show the greedy policy, the action with the highest Q-value in each square, which is what the agent would do if it stopped exploring.

Where engineers use this

Deep reinforcement learning replaces the table with a neural network: DeepMind's DQN learned Atari games from pixels, and AlphaGo combined it with search. Reinforcement learning from human feedback (RLHF) is used to fine-tune chatbots, and RL also tunes robot controllers and data-centre cooling.

Words to know

Agent
The learner that observes a state, chooses an action and receives a reward.
Reward
A number the environment gives after each action, saying how good it was.
Q-value
An estimate of total future reward for taking an action in a state, then acting well afterwards.
Policy
The agent's rule for choosing an action in each state.
Exploration
Trying actions that are not currently the best, to learn something new.

Talk about it

Goal: Reward an agent for reaching the goal and watch Q-values spread until it finds the best path.

  • Why does the agent need a small penalty for every step? What would happen without it?
  • How is learning to ride a bike like reinforcement learning? What is the reward?
  • If the reward is badly chosen, an agent might find a sneaky shortcut its designers did not intend. Can you think of an example?

Without a screen: Draw a 5x5 maze on paper with a goal square. One person is the agent and moves a coin while the other secretly knows where the goal is and only says "+10" when the coin lands on it. Write a number in each square as you learn which squares lead to the goal fastest.

Curriculum links: CSTA K-12 3B-AP-09 (implement an artificial intelligence algorithm to play a game or solve a problem); AI4K12 Big Idea 3 (Learning); AP CSP Algorithms and Programming

Questions

What is reinforcement learning in simple terms?
Reinforcement learning is learning by trial and error with rewards. An agent tries actions, gets points for good outcomes and penalties for bad ones, and gradually learns which actions lead to the most reward.

What is Q-learning?
Q-learning is a reinforcement learning algorithm that keeps an estimate, called a Q-value, of how much future reward each action will bring in each state. After every step it nudges that estimate toward the reward it got plus the best value of the next state.

What is the difference between reinforcement learning and supervised learning?
In supervised learning every example comes with the correct answer. In reinforcement learning nobody gives the right action; the agent only gets a reward signal, often delayed, and must work out which earlier actions earned it.