Reinforcement Learning I: MDPs, Bellman Equations, DP and Monte Carlo

Every model we have trained so far was shown the right answer. A label, a target, a next word. But nobody hands a robot the correct motor command, and nobody tells a chess program the best move in advance. It only finds out much later whether it won. How do you learn from that? This lesson is the foundation of the answer.

• Supervised: answers given
• Here: only delayed feedback

In lesson 58 we studied inference, latency and the limits of large language models. Lesson 30 gave you a quick tour of reinforcement learning. Today we slow down and do it properly. We define the problem as a Markov decision process, derive the Bellman equations step by step, solve a small world with dynamic programming, and then learn from raw experience with Monte Carlo methods.

• MDPs and returns
• Bellman equations
• Dynamic programming
• Monte Carlo

Reinforcement learning is a loop. An agent observes a state, chooses an action, and the environment answers with a reward and a new state. Then it repeats. The agent is whatever makes decisions. The environment is everything else, including the rules of the world. The agent's whole goal is to collect as much total reward as possible over time.

• State, action, reward, next state
• Goal: maximize total reward

This differs from supervised learning in three ways. First, feedback is evaluative, not instructive: a reward says how good you did, not what you should have done. Second, rewards are delayed, so credit must be assigned across many steps. Third, the agent's own actions change the data it sees, so it must explore, not just exploit what it already knows.

• Evaluative feedback
• Delayed reward
• Actions shape the data

We formalise the loop as a Markov decision process, written as a tuple of five things: a set of states S, a set of actions A, transition probabilities P, a reward function R, and a discount factor gamma. P of s prime given s and a is the probability of landing in s prime after taking action a in state s. Together they define the entire world.

• S: states, A: actions
• P: transition probabilities
• R: reward, gamma: discount

The word Markov carries one key assumption: the future depends only on the current state and action, not on the full history. Chess is a good example, because the board position contains everything you need. If your state leaves out important information, such as the velocity of a ball, the process stops being Markov, and you must enrich the state.

• Future depends on present only
• Missing info breaks it

A policy is the agent's behaviour. Written pi of a given s, it is the probability of choosing action a in state s. A deterministic policy is just a lookup table from states to actions. A uniform random policy in a world with four actions gives each action probability one quarter. Learning means finding a good policy.

• Maps states to action probabilities
• Random or deterministic

The agent cares about the return, the discounted sum of future rewards: G equals r1 plus gamma times r2 plus gamma squared times r3, and so on. Take rewards 2, 3 and 5 with gamma equal to 0.5. The return is 2 plus 1.5 plus 1.25, which is 4.75. Rewards that arrive later are worth less.

• G = r1 + gamma r2 + gamma^2 r3 ...
• 2 + 1.5 + 1.25 = 4.75

There is a shortcut that powers everything ahead. The return from now equals the next reward plus gamma times the return from the next step. Check it. The last return is 5. One step earlier, 3 plus 0.5 times 5 is 5.5. At the start, 2 plus 0.5 times 5.5 is 4.75. Same answer, computed backward one step at a time.

• Backward: 5, then 5.5, then 4.75
• Recursion is the key

Gamma sits between zero and one. With gamma equal to zero the agent is completely short sighted and only cares about the next reward. As gamma approaches one it becomes far sighted. It also keeps infinite sums finite: a reward of 1 forever with gamma 0.9 is worth 1 divided by 0.1, which is 10. A common mistake is forgetting that gamma changes what the best policy is.

• gamma 0: only next reward
• Infinite sum 1/(1-0.9) = 10

The return depends on luck, so we take its average. The state-value function V pi of s is the expected return when starting in state s and then following policy pi. It answers a simple question: how good is it to be here, if I behave like this? Value is a prediction, and it is always tied to a specific policy.

• Expected return from state s
• Depends on the policy

The action-value function Q pi of s and a is the expected return if you take action a right now, and only afterwards follow pi. It lets us compare actions directly. The two are linked: V pi of s is the average of Q pi of s and a, weighted by the probability that the policy picks each action.

• Value of a first action
• V = policy-weighted average of Q

Let us build a world small enough to solve by hand. A two by two grid. Call the cells A and B on top, C and D below. D is the terminal goal. Every step costs a reward of minus 1, gamma is 1, and moves are deterministic. Bumping into a wall leaves you in place. The agent wants to reach D quickly.

• D is terminal
• Reward -1 per step
• Walls: stay in place

Start from the definition: V pi of s is the expected value of G. Now use our recursion, G equals the next reward plus gamma times the next return. Expectation splits over the sum, so V pi of s becomes the expected next reward plus gamma times the expected value of the next state. Averaging over actions and transitions gives the Bellman expectation equation.

• Use G = r + gamma G_next
• Average over actions and outcomes

Use the uniform random policy. From B, two actions, up and right, bump walls and stay at B. Down reaches D, worth zero. Left goes to A. So V of B equals minus 1 plus a quarter of V B twice, plus zero, plus a quarter of V A. By symmetry, C behaves the same as B. From A, two actions stay, one goes to B, one to C.

• V(B) = -1 + 0.5 V(B) + 0.25 V(A)
• V(C) matches V(B)

Let a be the value of A and b the value of B, which equals C. For B: b equals minus 1 plus 0.5 b plus 0.25 a, so b is minus 2 plus 0.5 a. For A: a equals minus 1 plus 0.5 a plus 0.5 b, so a is minus 2 plus b. Substitute: a equals minus 4 plus 0.5 a, giving a equals minus 8, and b equals minus 6.

• b = -2 + 0.5a
• a = -2 + b
• a = -8, b = -6

Now ask for the best possible behaviour. The optimal value V star takes the best action instead of averaging: V star of s equals the maximum over actions of the expected reward plus gamma times V star of the next state. In our grid, V star of B is minus 1, because going down reaches D. V star of A is minus 2: right, then down.

• Max replaces the average
• V*(B) = -1, V*(A) = -2

The same idea works for actions. Q star of A and right is minus 1 plus V star of B, which is minus 2. Q star of A and up is minus 1 plus V star of A, which is minus 3. The best policy is greedy with respect to Q star. Two common mistakes: forgetting that the expectation equation needs a fixed policy, and forgetting that terminal states have value zero.

• Q*(A,right) = -1 + V*(B) = -2
• Terminals have value 0

Solving linear equations by hand does not scale to millions of states. Dynamic programming turns the Bellman equations into update rules, applied again and again until the numbers stop changing. It assumes we know the model, meaning the transition probabilities and rewards. It exploits the recursion by reusing the values of neighbouring states instead of recomputing whole futures.

• Needs the model P and R
• Reuse neighbour values

Policy evaluation finds V pi for a given policy. Start with every value at zero. After sweep one, every non terminal cell becomes minus 1. After sweep two, B and C become minus 1.75, and A becomes minus 2. After sweep three, B is minus 2.375 and A is minus 2.875. The table keeps sliding toward minus 6 and minus 8.

• Sweep 1: all -1
• Sweep 3: A -2.875, B -2.375
• Converges to -8 and -6

In NumPy this is a short loop. Keep a value array of four numbers. For each sweep, compute new values from the old ones using the policy, then measure the largest change. Stop when that change drops below a small threshold such as one in a million. A subtle choice: updating in place or from a copy. Both converge, but the sweep numbers differ.

• Loop sweeps over all states
• Stop when max change is tiny

Once we know V pi, we can improve the policy by acting greedily. In each state, choose the action with the highest one step lookahead value. Under the random policy, A has values minus 8 for staying, and minus 6 for moving to B or C. So the greedy policy moves A toward B or C. B moves down to D. The new policy is already better.

• Pick best one-step lookahead
• New policy is at least as good

Policy iteration alternates two steps: evaluate the current policy, then improve it greedily. Repeat until the policy stops changing. In our grid, the improved policy is evaluated: A is minus 2, B and C are minus 1. Improving again changes nothing, so we have the optimal policy. In general this converges in a surprisingly small number of rounds.

• Alternate until policy is stable
• Ends at the optimal policy

Value iteration skips the full evaluation. It applies the optimality equation directly, taking a max at every update. Starting from zeros, sweep one gives minus 1 everywhere. Sweep two gives B and C still at minus 1, but A drops to minus 2, since moving right costs one step plus V of B. Sweep three changes nothing. We have converged to V star.

• Update with max directly
• Sweep 2: A becomes -2
• Sweep 3: no change

The code looks like policy evaluation with one change. For each state, compute the lookahead value of every action as a vector, then take the maximum instead of the weighted average. After convergence, extract the policy with an argmax over the same lookahead. Common mistake: forgetting to zero out the terminal state, which lets value leak out of the goal.

• Lookahead vector, then max
• Policy = argmax of lookahead
• Keep terminal at zero

Dynamic programming is exact and elegant, but it has two limits. It needs the model: you must know every transition probability. And each sweep touches every state, which explodes for large problems. Backgammon has an enormous number of positions, and a robot has continuous states. We need methods that learn from experience instead, and that brings us to Monte Carlo.

• Requires a known model
• Sweeps every state

Monte Carlo methods need no model. The agent simply plays complete episodes, from start to terminal, and records what happened. The value of a state is estimated as the average of the returns observed after visiting it. This is the law of large numbers at work, and it only works for episodic tasks, since we need an episode to end before computing returns.

• No model needed
• Complete episodes only

Suppose one episode under the random policy goes A, B, A, C, D with reward minus 1 each step and gamma 1. That is four steps. The first visit to A is at time zero, with return minus 4. B, visited at time one, has return minus 3. C, at time three, has return minus 1. First visit Monte Carlo counts only the first time A appears.

• Episode: A, B, A, C, D
• G(A) = -4, G(B) = -3, G(C) = -1
• Second visit to A ignored

Every-visit Monte Carlo would also count the second visit to A, with return minus 2, averaging minus 4 and minus 2 to get minus 3. Both converge to the true value. To avoid storing all returns, update incrementally: new V equals old V plus one over N times the difference between the return and old V. If A's first return is minus 4 and the next is minus 10, the mean becomes minus 7.

• Every-visit also converges
• V += (G - V) / N
• -4 and -10 give -7

Prediction estimates values. Control finds a good policy. Without a model, state values are not enough, because to pick an action we would need to know where it leads. So we estimate Q of s and a instead, averaging returns for each state action pair. Then we improve the policy greedily with respect to Q, and repeat, just like policy iteration.

• Estimate Q(s, a) from returns
• Improve policy greedily
• Repeat with new episodes

There is a trap. If the policy is purely greedy, it only tries actions it already believes are best, so other actions never get sampled, and their estimates never improve. The agent can lock into a mediocre habit forever. Exploration is not optional. One fix, exploring starts, begins each episode at a random state and action. It is often impractical in real settings.

• Greedy never tries alternatives
• Exploration is required

A practical fix is the epsilon greedy policy. With probability epsilon, pick a random action. Otherwise take the best known one. With epsilon 0.1 and four actions, the greedy action gets probability 0.9 plus 0.1 divided by 4, which is 0.925. Each other action gets 0.025. These add to one. Every action keeps a chance, so every estimate keeps improving.

• Greedy action: 0.925
• Others: 0.025 each
• Epsilon = 0.1, four actions

When the agent learns about the same policy it is following, that is on-policy learning. Our epsilon greedy control is on-policy. Off-policy learning separates two policies: a behaviour policy that generates data, and a target policy that we want to evaluate. This lets an agent explore randomly while learning about the greedy policy, or learn from another agent's experience.

• On: learn the policy you follow
• Off: behaviour b, target pi

Data from the behaviour policy is distributed differently from what the target policy would produce, so we reweight it. At each step, multiply by the probability under the target, divided by the probability under the behaviour. If the behaviour picks uniformly at one quarter, and the greedy target picks that action with probability one, each step has ratio four. Over two steps the weight is sixteen. Long episodes make weights huge, so variance is a real problem.

• Ratio = pi(a|s) / b(a|s)
• Two steps: 4 x 4 = 16
• Long episodes: high variance

Let us compare. Dynamic programming bootstraps: it updates a value using the current estimates of neighbouring states, and it needs the model. Monte Carlo does not bootstrap: it waits for the true observed return, which makes it unbiased but noisy, and it works without a model. Each sweeps or samples differently, and the next lesson blends both ideas.

• DP: model, bootstraps
• MC: samples, full returns

Let us recap. An MDP packages states, actions, transitions, rewards and a discount. A policy picks actions, and the return adds up discounted rewards. V and Q measure expected return. The Bellman equations express value recursively; on our grid they gave minus 8 and minus 6, and the optimum of minus 2 and minus 1. Dynamic programming sweeps with a known model, while Monte Carlo averages episode returns.

• MDP, policy, return, gamma
• Bellman: recursive values
• DP uses a model, MC uses episodes

Monte Carlo waits until an episode ends, and dynamic programming needs a model. In lesson 60 we get the best of both with temporal difference learning, then Q-learning, policy gradients and deep reinforcement learning.

• Lesson 60: TD, Q-learning
• Subscribe for the series