Q-Learning (Reinforcement Learning)

Learning from rewards

Most machine learning needs labelled examples: “this photo is a cat”. In reinforcement learning there are no labels. An agent acts in an environment, receives rewards or penalties, and must work out by itself which actions lead to good outcomes. This is how game-playing programs such as AlphaGo learned, and how robots learn to walk in simulation.

The grid world in the 3D model is the classic small example:

• States: the cells of the grid.
• Actions: up, right, down, left. Walking into a wall leaves you where you are.
• Rewards: −1 per step (hurry up!), +10 at the goal, −10 in a pit. Both end the episode.

The Q-table

Q(s, a) is the agent’s estimate of the total future reward if it takes action a in state s and then behaves as well as it can. If you know all the Q-values, acting well is easy: in every state, pick the action with the highest Q. In the model, a tile’s height shows its best Q-value and the arrow shows the best action.

The update rule

After every step (state s, action a, reward r, new state s′), Q-learning nudges its estimate towards a better one:

Q(s, a) ← Q(s, a) + α · [ r + γ · max over a′ of Q(s′, a′) − Q(s, a) ]

• r + γ · max Q(s′, ·) is the target: the reward we just got plus the discounted value of the best thing we can do next.
• α (learning rate, 0.5 here) controls how far we move towards the target.
• γ (discount, 0.9 here) makes future rewards worth a bit less than immediate ones.

At first everything is 0, so the steps only learn “walking costs −1”. When the agent finally stumbles into the goal, the last move gets a big positive value. On later episodes the move before it sees that value through max Q(s′), and so on. The reward spreads backwards one step at a time, which is why the tiles near the goal rise first.

Explore or exploit?

If the agent always takes its current best action, it might never discover a better route. ε-greedy fixes this: with probability ε take a random action (explore), otherwise take the best one (exploit). With too little exploration the agent can get stuck; with too much, it wanders around and learns slowly.

Code

import random

def q_learning(step, start, n_states, episodes=150, alpha=0.5, gamma=0.9, eps=0.2):
    Q = {(s, a): 0.0 for s in range(n_states) for a in range(4)}
    for _ in range(episodes):
        s, done = start, False
        while not done:
            if random.random() < eps:
                a = random.randrange(4)                      # explore
            else:
                a = max(range(4), key=lambda x: Q[(s, x)])   # exploit
            s2, r, done = step(s, a)                         # environment answers
            best_next = 0 if done else max(Q[(s2, x)] for x in range(4))
            Q[(s, a)] += alpha * (r + gamma * best_next - Q[(s, a)])
            s = s2
    return Q

The step function is the environment: given a state and an action, it returns the new state, the reward and whether the episode ended. For real problems the Q-table is replaced by a neural network that predicts Q-values. That is Deep Q-Learning (DQN), which learned to play Atari games from the screen pixels.

Q-learning vs other methods

Common mistakes

• Using the action actually taken next in the target. That is SARSA. Q-learning uses the max over next actions.
• Forgetting that terminal states have no future: their max Q is 0.
• Setting ε = 0 from the start. The agent may never find the goal.
• Expecting convergence after a few episodes. Values need many visits before they stop changing.