Reinforcement learning: learning from rewards

Every model so far learned from examples with the right answer attached: this point is class A, this house sold for that much. Nobody can label every move of a game or every turn of a robot's wheel, though. What there is instead is a score that arrives later: a win, a crash, a reward.

Reinforcement learning learns from that score alone. The agent acts, sees what happens, and slowly works out which moves lead to reward, even when the reward comes many moves after the decision that earned it. This lesson builds the classic method, Q-learning, on a few small grids.

state and action

Where the agent is (a cell of the grid) and what it can do there (move up, right, down or left).

reward

A number the world hands back after each move: +10 for the goal, −1 per step, −100 for the cliff.

discount γ

A reward $k$ moves away counts $\gamma^k$ times as much as one now. With $\gamma = 0.9$, ten points four moves away are worth $0.9^4 \cdot 10 \approx 6.6$ today.

Q-value

$Q(s, a)$: the total discounted reward the agent expects if it makes move $a$ in state $s$ and plays as well as it can afterwards.

policy

How the agent chooses moves. The greedy policy picks the move with the largest $Q(s, a)$; the arrows on the grid show it.

ε-greedy

Mostly greedy, but with chance $\varepsilon$ a random move instead, so the agent keeps trying things it doesn't yet rate.

The agent starts with every Q-value at 0 and wanders. After every move it nudges one entry of its table towards a target: the reward it just got, plus the discounted value of the best move from where it landed.

Only the move that entered the goal learns anything in the first episode. On the next visit to the cell before it, the target includes that cell's new value, so the reward spreads one step further back each time, shrinking by $\gamma$ per step. The wash fades with distance from the goal because of that discount.

Here every move costs 1 and the cliff costs 100. The fastest route runs right along the edge.

The target uses $\max_{a'} Q(s', a')$, the value of acting greedily next, whatever the agent actually does next. So Q-learning learns how good the edge is for an agent that never slips, even while its own ε-greedy wandering keeps slipping. That is called learning off-policy. A method that learns the value of the policy it really follows (SARSA) would pay for the slips and prefer a row further from the edge.

Before each update, decide whether that Q-value will rise, fall or stay put. Compare the target, $r + \gamma \max Q(s', \cdot)$, with the value it has now. When the agent exploits, predict which move it makes from the Q-values listed.

From the start, a +1 is two moves away and a +10 is four. Which is better depends entirely on $\gamma$: the +1 is worth $\gamma \cdot 1$ and the +10 is worth $\gamma^3 \cdot 10$. Work out both for $\gamma = 0.9$ and for $\gamma = 0.25$, then run each and see which way the arrows from S end up pointing.

Then use the input box to try:

• The crossover: at which $\gamma$ does the preference flip? (Solve $\gamma = 10\gamma^3$.)
• No exploring: set epsilon = 0 on the near-or-far world. The first goal the agent stumbles onto is the one it keeps going back to, so the other one may never be found.
• Too few episodes: with episodes = 10, the arrows from S may still loop.

• The agent learns $Q(s, a)$, the discounted reward to expect from a move, and acts greedily on it, with chance $\varepsilon$ of exploring.
• Each update moves $Q(s, a)$ a fraction $\alpha$ towards $r + \gamma \max_{a'} Q(s', a')$; rewards spread backwards one step per visit.
• The fixed point is the Bellman equation, the same one dynamic programming solves when the rules are known.
• $\gamma$ trades near rewards against far ones; ε trades using what is known against finding out more.
• Next: replace the table with a neural network and the same update learns Atari games (DQN).