Markov Decision Processes | ML-101

From a Loop to a Model

Lesson 14.1 described the interaction: state, action, reward, next state, repeat. That description is enough to talk about the problem and nowhere near enough to solve it. To compute anything you need to say precisely what the environment is, and the standard answer is the Markov decision process — the MDP. It is the formalism the whole field is built on, and Sutton and Barto (2018) devote their Chapter 3 to it.

The pay-off for the formalism is a single recursive equation, due to Bellman (1957), that relates the value of where you are to the value of where you could go next. Once you have that equation you can solve small problems exactly, and every method in Lessons 14.3 and 14.4 is a way of approximating its solution when the problem is not small.

The Markov Property, and What It Assumes Away

A state has the Markov property if it summarises the past well enough that the past adds nothing. Formally, the probability of the next state and reward depends on the current state and action alone — not on how you arrived there.

The Markov Property

p(s',r \mid s,a) = \Pr\{ S_{t+1} = s',\; R_{t+1} = r \mid S_t = s,\; A_t = a \}

The four-argument function p is the environment’s dynamics: given that you were in state s and took action a, it gives the probability of landing in s′ and collecting reward r. Nothing about S_t-1, A_t-1 or any earlier step appears on the right-hand side. That absence is the entire assumption.

It is worth being blunt about what this assumes away. A chess position is Markov: the board, whose move it is, and the castling and en-passant rights determine everything that can follow, and the sequence of moves that produced the position is irrelevant. A single video frame of a moving ball is not Markov: it does not contain the ball’s velocity, so it cannot predict the next frame. A doctor’s one-off blood test is not Markov either, because the trend over the past year is missing.

The fix is nearly always to redefine the state rather than to abandon the framework: stack the last few frames, add velocity, add the running summary. This is engineering, and it has a cost — every quantity you add multiplies the size of the state space. Bellman called that growth the curse of dimensionality, and it is the reason tabular methods run out of room and Lesson 14.3 ends up replacing the table with a neural network.

When the State Is Genuinely Hidden

Sometimes no amount of engineering makes the observation Markov, because the information is not available at all — a robot with a limited camera cannot see behind itself. That case has its own name, the partially observable MDP, and it is genuinely harder: the agent has to maintain a belief over states rather than a state. Everything in this module assumes the fully observable case, which is the standard place to start and where the Bellman equations hold as written.

The Five Pieces

An MDP is a tuple of five things, and naming them is most of the work of framing a problem.

S, A, p, r, γ

States S. The set of situations the agent can be in. Some may be terminal, which ends the episode.

Actions A. What the agent may do. Often this depends on the state, written A(s).

Transition probabilities p(s′, r | s, a). The dynamics above. Deterministic environments are the special case where all the probability sits on one outcome.

Reward function r. The expected reward for a transition, obtained from p by averaging over r. It is a property of the environment, not of the agent, and Lesson 14.1’s warning about reward hacking is a warning about how you write this piece.

Discount factor γ. A number with 0 ≤ γ ≤ 1 that says how much a reward one step later is worth relative to one now.

Return, and Why the Future Is Discounted

The agent is not maximising the next reward. It is maximising everything that comes after, and that total needs a name and a definition. The return G_t is the discounted sum of all future reward from time t onward.

Discounted Return

G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}

The reward arriving one step from now is R_t+1 and it is undiscounted, since k = 0 gives γ⁰ = 1; the one after is weighted by γ, then γ², and so on. Note the index convention from Lesson 14.1 is doing real work here: acting at time t earns R_t+1, so the sum starts at t+1.

There are three reasons for the discount, and only the first is mathematical. If the interaction never terminates, the undiscounted sum of rewards can be infinite, and infinities cannot be compared — two policies both scoring infinity are indistinguishable. With γ < 1 and bounded rewards the geometric series converges, so every policy has a finite score and the comparison is meaningful.

Second, sooner is genuinely better in most real problems: money now beats money later, a robot that reaches the goal in ten steps beats one that takes a thousand. Third, γ encodes uncertainty about the far future — a claim on a reward a hundred steps away is worth less because so much can intervene.

The two extremes are instructive. At γ = 0 the return is just R_t+1 and the agent is perfectly myopic: it optimises the next step and will happily walk off a cliff on the step after. As γ approaches 1 the agent becomes far-sighted and the returns from different policies become harder to tell apart, which makes learning slower. Typical values in practice sit between 0.9 and 0.99. γ = 1 is legitimate only for episodic tasks that are guaranteed to terminate, where the sum is finite because it has an end.

Policy, State Value, Action Value

A policy π(a | s) is the agent’s rule of behaviour: the probability of choosing action a in state s. Everything the agent can be judged on follows from its policy, because the policy plus the dynamics p determine the distribution over trajectories, and therefore the distribution over returns.

Two functions turn that distribution into numbers you can act on. The state-value function answers: starting here and following π, what return should I expect?

State-Value Function

V^{\pi}(s) = \mathbb{E}_{\pi}\left[ G_t \mid S_t = s \right]

The expected return from state s under policy π. It is an expectation for two separate reasons: the policy may pick actions at random, and the environment may respond at random. The superscript π is not decoration — a state has no value in the abstract, only a value under some way of behaving.

The action-value function asks a slightly different and much more useful question: what if I take a specific action here first, and only then follow π?

Action-Value Function

Q^{\pi}(s,a) = \mathbb{E}_{\pi}\left[ G_t \mid S_t = s, A_t = a \right]

Q is what you need in order to choose. Given V alone you must look one step ahead through the model p to compare actions; given Q you simply compare numbers already indexed by action and take the largest. That is exactly why Lesson 14.3 learns Q rather than V — it is the form that does not require a model.

The Bellman Expectation Equation

Here is the idea the whole module rests on. The return from a state splits into the very next reward plus the discounted return from wherever you land. Take the expectation of both sides and the value function becomes recursive: V appears on both sides of its own definition.

Bellman Expectation Equation

V^{\pi}(s) = \sum_a \pi(a \mid s) \sum_{s',r} p(s',r \mid s,a) \left[ r + \gamma V^{\pi}(s') \right]

Read it outward-in. The outer sum averages over the actions the policy might take. The inner sum averages over the outcomes the environment might produce. The bracket is the immediate reward plus the discounted value of the state you land in. For a finite MDP this is one linear equation per state, so the value of a fixed policy can in principle be found by solving a linear system.

The value of a policy is therefore not something you have to simulate for a thousand episodes to discover. It is the solution of a system of equations you can write down from the model. That is a remarkable amount of leverage to get from one assumption about states.

Optimality: Replace the Average with a Maximum

Evaluating a given policy is not the goal; finding the best one is. An optimal policy π^* is one whose value is at least as high as every other policy’s in every state. Every finite MDP has at least one, and all optimal policies share the same value function V^*.

The Bellman optimality equation differs from the expectation equation in exactly one place. An optimal agent does not average over what its policy might do — it takes the best action available. So the outer sum over π becomes a maximum over a.

Bellman Optimality Equation

V^{*}(s) = \max_a \sum_{s',r} p(s',r \mid s,a) \left[ r + \gamma V^{*}(s') \right]

The inner expectation over the environment’s randomness stays — you cannot maximise over what the world does. The maximum is only over what you do. Note the equation is no longer linear, which is why the optimal value function is found by iteration rather than by solving a linear system.

One consequence is worth stating on its own, because it is what makes the whole approach practical: once you have V^*, acting optimally requires no search at all. Look one step ahead, take the action maximising the bracket above, and you are behaving optimally over an infinite horizon. All the long-term planning has been compressed into the value function.

Solving It When the Model Is Known

If p is known, the Bellman optimality equation can be solved by dynamic programming — Bellman’s (1957) method, and the subject of Sutton and Barto’s Chapter 4. The trick is to stop treating it as an equation to be solved and to treat it as an assignment to be repeated.

Value Iteration Update

V_{k+1}(s) \leftarrow \max_a \sum_{s',r} p(s',r \mid s,a) \left[ r + \gamma V_k(s') \right]

The optimality equation with an arrow instead of an equals sign, swept over every state. Start from any V₀ — all zeros is normal — and repeat. For γ < 1 the sweep is a contraction, so the estimates converge to V^* from any starting point. In practice you stop when the largest change across a sweep falls below a tolerance.

Work it by hand on a four-cell corridor. The states are 1, 2, 3 and a terminal goal G, in a line. The two actions are left and right, both deterministic; bumping the left wall from state 1 leaves you in state 1. Moving right from state 3 reaches G, pays reward 1 and ends the episode. Every other transition pays 0. Set γ = 0.9 and V₀ = 0 everywhere.

Value Iteration, Three Sweeps

Sweep 1. State 3: right gives 1 + 0.9 × 0 = 1, left gives 0 + 0.9 × 0 = 0, so V₁(3) = 1. States 1 and 2 see zeros in every direction, so they stay at 0.

Sweep 2. State 2: right gives 0 + 0.9 × V₁(3) = 0.9, so V₂(2) = 0.9. State 3 stays at 1. State 1 is still 0.

Sweep 3. State 1: right gives 0 + 0.9 × 0.9 = 0.81, so V₃(1) = 0.81. Nothing changes on the next sweep, so this is V^*: 0.81, 0.9, 1.

Read the answer. Value decreases with distance from the goal by a factor of γ per step, which is exactly what γ means. Acting greedily with respect to these numbers gives “always go right” — the optimal policy, extracted without any search.

The alternative is policy iteration, which alternates two steps instead of fusing them. Policy evaluation solves the Bellman expectation equation for the current policy, giving V^π exactly. Policy improvement then makes the policy greedy with respect to that V^π. Repeat until the improvement step changes nothing, at which point the policy satisfies the optimality equation and is optimal.

Policy Iteration on the Same Corridor

Start from the deliberately bad policy “always go left”. Evaluation gives V = 0 in every state, because the goal is never reached. Improvement finds that at state 3 going right is worth 1 against 0, so it flips state 3 to right.

Evaluate again: V(3) = 1, V(2) = 0, V(1) = 0. Improvement now finds state 2 is worth 0.9 going right against 0 going left, and flips it. Evaluate: V(3) = 1, V(2) = 0.9, V(1) = 0. Improvement flips state 1, since 0.9 × 0.9 = 0.81 beats 0. Evaluate: 0.81, 0.9, 1 — and the next improvement changes nothing, so the policy is optimal.

Note what happened: the policy was optimal after three improvements even though the values were still being refined. That is the usual pattern, and it is why policy iteration often needs remarkably few rounds. Value iteration is cheaper per sweep because it never waits for evaluation to finish, while each policy-iteration round does more work but acts on an exact value function. On a corridor this small the two finish in the same number of rounds — three each, as above; the difference only tells on larger problems. Both are dynamic programming, and both require p.

Which brings the lesson to its own boundary. Everything above needs the transition probabilities to be known, and for most real problems they are not: nobody hands you the dynamics of a warehouse, a market or a user. That single missing ingredient is what Lesson 14.3 is about — learning Q from experience alone, with no model of the environment at all.

Key Takeaways

An MDP is the formal statement of the RL problem: states, actions, transition probabilities p(s′, r | s, a), a reward function, and a discount factor γ with 0 ≤ γ ≤ 1.
The Markov property says the current state and action determine the distribution of what comes next, with no dependence on history. Velocity, trends and stacked frames exist to make it true.
The return is the discounted sum of future rewards. Discounting keeps continuing tasks finite, prefers sooner reward, and hedges the far future. γ = 1 is only safe when episodes terminate.
V^π(s) is the expected return from s under π; Q^π(s, a) is the expected return after committing to a first. Q is the form you can act on without a model.
The Bellman expectation equation makes V recursive: the immediate reward plus the discounted value of the next state, averaged over the policy and over the environment.
The Bellman optimality equation replaces the average over actions with a maximum. It is non-linear, and its solution V^* makes optimal behaviour a one-step lookahead.
Value iteration sweeps the optimality update to convergence; policy iteration alternates exact evaluation with greedy improvement. Both are Bellman’s (1957) dynamic programming, and both need p.
Bellman’s curse of dimensionality is why enlarging the state to restore the Markov property has a real cost, and why tabular methods eventually give way to function approximation.