States, actions, and rewards

Picture a small robot on a grid. One square holds a charging dock worth +1. Next to it is a staircase worth −1: fall down it and the run is over. The floor is slippery, so when the robot tries to move, it sometimes slides sideways instead. Which way should it go from each square?

No single move earns the +1. The reward comes only at the end, after a whole chain of moves, and each move changes where the robot is. That is what makes this harder than the slot machines of the last lesson.

Markov decision processes

Problems like this are described as a Markov decision processMarkov decision processThe standard model of a sequential decision problem: states, actions, transition probabilities for where each action leads, and rewards. What happens next depends only on the current state and action.Open in glossary, or MDP. It has four parts:

• States: the situations the agent can be in. Here, the squares.
• Actions: what it can do in each state. Here, up, right, down, and left.
• Transitions: where each action leads, with probabilities. Here, a move goes as intended 80% of the time and slips to each side 10% of the time. Walls and edges block movement.
• Rewards: the number received after each move. Here, a small cost for every move (−0.04), plus the exit’s reward when the robot reaches +1 or −1, which ends the episode.

“Markov” means the next state depends only on the current state and action, not on how the agent got there. A chess position nearly works this way: apart from a few rules, such as whether castling is still allowed and draws by repetition, the history of moves does not matter once you know the board.

What the agent learns is a policyPolicyAn agent's rule for choosing actions: for each state, which action to take, or the probability of taking each one.Open in glossary: a rule that says which action to take in each state.

Return and discounting

The agent wants to collect as much reward as possible in total, not just on the next move. The total from some point on is called the returnReturnThe total reward an agent collects from some point on, usually with later rewards discounted: G = r1 + γ r2 + γ² r3 + ...Open in glossary. Usually later rewards count for less:

The discount factorDiscount factorA number gamma between 0 and 1 that shrinks rewards the further in the future they arrive. Low gamma makes an agent short-sighted; gamma near 1 makes it patient.Open in glossary $\gamma$ (gamma) is between 0 and 1. With $\gamma = 0.9$, a reward three steps away counts for $0.9^2 = 0.81$ of its size, and one twenty steps away for about 0.14. A low discount makes the agent impatient; $\gamma = 1$ counts every reward fully, which only works when episodes are sure to end.

What a state is worth

The valueValue functionThe return an agent can expect from a state (or from a state and an action) when it follows a given policy from then on. Values let an agent compare choices whose payoff comes later.Open in glossary of a state is the return the agent can expect from there if it acts as well as possible from then on. A square next to the +1 is worth nearly 1; a square far away is worth less, because getting there costs moves and risks slips.

Values connect to each other. A state is worth the best action’s expected reward plus the discounted value of wherever that action lands you. This is the Bellman equationBellman equationThe rule linking a state's value to its neighbors': a state is worth the expected reward of the next step plus the discounted value of where you land. For the best policy, take the best action.Open in glossary, after Richard Bellman, who developed dynamic programming in the 1950s:

The sum averages over where the action might land, weighted by the probability of each outcome.

Value iteration

The Bellman equation suggests a way to find the values. Start with every value at zero. Then sweep through every state and replace its value with the right-hand side, using the current values of its neighbors. Repeat until nothing changes. This is value iterationValue iterationA planning method that starts with all values at zero and repeatedly updates every state with the Bellman equation until the values stop changing. Needs a known model of the world.Open in glossary. Once the values settle, the best policy is simply: in each state, take the action that achieves the maximum.

import numpy as np

# The 4 by 3 world: "." empty, "#" wall, numbers are exits. Start bottom left.
rows = [". . . +1",
        ". # . -1",
        ". . . ."]
grid = [r.split() for r in rows]
H, W = len(grid), len(grid[0])
moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]  # up, right, down, left
gamma, living, slip = 1.0, -0.04, 0.2

def land(r, c, a):
    """Where moving in direction a from (r, c) lands; walls and edges block."""
    nr, nc = r + moves[a][0], c + moves[a][1]
    if 0 <= nr < H and 0 <= nc < W and grid[nr][nc] != "#":
        return nr, nc
    return r, c

def q_value(V, r, c, a):
    """Expected reward plus discounted value: 80% as intended, 10% to each side."""
    total = 0.0
    for d, p in [(a, 1 - slip), ((a + 1) % 4, slip / 2), ((a + 3) % 4, slip / 2)]:
        nr, nc = land(r, c, d)
        cell = grid[nr][nc]
        if cell in (".", "#"):
            total += p * (living + gamma * V[nr, nc])
        else:  # an exit: its reward, and the episode ends
            total += p * (living + float(cell))
    return total

V = np.zeros((H, W))
for sweep in range(1, 1000):
    new = V.copy()
    for r in range(H):
        for c in range(W):
            if grid[r][c] == ".":
                new[r, c] = max(q_value(V, r, c, a) for a in range(4))
    change = np.abs(new - V).max()
    V = new
    if change < 1e-6:
        break

print(f"settled after {sweep} sweeps")
print(np.round(V, 3))
arrows = "^>v<"
for r in range(H):
    print(" ".join(arrows[int(np.argmax([q_value(V, r, c, a) for a in range(4)]))]
                   if grid[r][c] == "." else grid[r][c] for c in range(W)))

settled after 28 sweeps
[[0.812 0.868 0.918 0.   ]
 [0.762 0.    0.66  0.   ]
 [0.705 0.655 0.611 0.388]]
> > > +1
^ # ^ -1
^ < < <

What the values tell you

The textbook answer. The classic world comes from Russell and Norvig’s Artificial Intelligence: A Modern Approach, and with its settings (no discount, −0.04 per move, 20% slip) value iteration reproduces the book’s values: 0.705 at the start, 0.918 beside the +1. From the start the best route goes up and around the top, away from the −1. The bottom right cell even goes left, the long way round, rather than risk slipping into the −1 on the short way.

The cost of moving sets the attitude to risk. When moves are nearly free (a cost below about 0.027), the cell beside the −1 walks straight into the wall. That looks broken, but it is the safest move available: a sideways slip from it goes up or down, never into the −1, and waiting costs almost nothing. When moves cost more than about 1.65 each, the same cell jumps into the −1 on purpose, because ending now is cheaper than walking to the +1. Nothing about the agent changed between these cases. Only the rewards did, and the behavior follows from them.

Discount and slip are separate dials. In the cliff edge world, a low discount makes the distant +10 look small, so the agent settles for the +1. Slip decides whether the short path along the cliff is worth the risk. With no slip and a low discount, the agent hurries to the +1 along the edge; with no slip and a high discount it runs along the edge to the +10; with the default 20% slip it climbs away from the edge either way.

Values need not settle. With no discount and a reward for every move, wandering forever is worth an unlimited amount, so value iteration never converges. With $\gamma < 1$, each sweep shrinks the remaining error by at least a factor of $\gamma$, so the values always settle.

Planning needs a model

Value iteration looked up every transition probability and reward in every sweep. It is planning, not learning: it needs a complete model of the world before it starts. Real agents rarely have one. A robot does not know the exact physics of its floor, and in Go, with roughly $10^{170}$ legal positions, you could not list the states even if you knew the rules perfectly.

Two ideas fix this, and the rest of the track builds on them. The next lesson learns values from experience, by trying actions and watching what happens, with no model at all. And when there are too many states to list, a neural network can estimate values instead of a table. DeepMind’s AlphaGo and AlphaZero did both, training networks that estimate how good a position is from games of self-play.