Markov Decision Processes

Why we need a formalism

In reinforcement learning, you interact with an environment over time. The key difficulty is credit assignment across time: an action now may cause a good or bad outcome many steps later. To reason about this cleanly, we want a model that:

1. 1)Separates what the agent controls (actions, policy) from what the environment does (stochastic transitions).
2. 2)Encodes time and uncertainty.
3. 3)Is simple enough to yield recursive equations (so dynamic programming applies).

An MDP is the standard model that accomplishes this.

Definition

A (finite) Markov Decision Process is a tuple:

• •S: set of states
• •A: set of actions (sometimes A(s) depends on the state)
• •P: transition dynamics, where

P(s′ | s, a) = Pr(Sₜ₊₁ = s′ | Sₜ = s, Aₜ = a)

• •R: reward function. Common choices:
• •R(s, a): expected immediate reward after taking action a in state s
• •R(s, a, s′): expected reward for the transition (s, a, s′)
• •γ (gamma): discount factor, 0 ≤ γ ≤ 1

The Markov decision epoch (Markov property)

The “atomic step” of an MDP is a decision epoch:

• •You are in state s
• •You choose an action a (possibly stochastically)
• •The environment samples the next state s′ from P(·|s,a)
• •You receive a reward r governed by R

The Markov property means the future depends on the past only through the current state (and chosen action):

Pr(Sₜ₊₁ = s′ | S₀, A₀, …, Sₜ = s, Aₜ = a) = Pr(Sₜ₊₁ = s′ | Sₜ = s, Aₜ = a)

This assumption is what lets us write Bellman equations: it provides the “optimal substructure” for sequential decisions.

Trajectories and return

A trajectory is a sequence (S₀, A₀, R₁, S₁, A₁, R₂, …). The (discounted) return from time t is:

Gₜ = ∑ₖ₌₀^∞ γᵏ Rₜ₊ₖ₊₁

• •If γ is near 0, you care mostly about immediate reward.
• •If γ is near 1, you care strongly about long-term reward (but need conditions to keep the sum finite).

What γ really does (motivation before math)

Discounting is not just a mathematical trick. It does three practical jobs:

1. 1)Preference for sooner rewards (time preference).
2. 2)Convergence: if rewards are bounded, discounting ensures ∑ γᵏ R converges.
3. 3)Effective horizon: roughly, rewards more than ~1/(1−γ) steps away contribute little.

Relationship to Markov chains and dynamic programming

An MDP generalizes a Markov chain:

• •A Markov chain has P(s′|s).
• •An MDP has P(s′|s,a), because the agent’s action influences transitions.

An MDP also sets up dynamic programming:

• •The value of a state can be written in terms of the value of successor states.
• •That recursion is exactly what DP exploits.

A quick taxonomy (to orient you)

The rest of this lesson builds the two central ingredients: policies and value functions, and then shows how Bellman equations connect them.

Why policies come first

An MDP by itself is just a world model. To talk about “expected return,” we must specify how actions are selected. That’s the role of a policy.

Policies (deterministic and stochastic)

A policy π is a decision rule mapping states to actions.

• •Deterministic: a = π(s)
• •Stochastic: π(a|s) = Pr(Aₜ = a | Sₜ = s)

Stochastic policies matter even when the environment is fully known:

• •They can represent uncertainty or exploration.
• •In some settings (e.g., partial observability), randomization can be essential.

From an MDP + policy to a Markov reward process

Once you fix π, the agent is no longer “choosing” actions freely; actions are sampled from π. The resulting state process becomes a Markov chain with transition matrix:

P^π(s′|s) = ∑ₐ π(a|s) P(s′|s,a)

If rewards depend on (s,a) (or (s,a,s′)), you also get an induced reward model, e.g.:

R^π(s) = ∑ₐ π(a|s) R(s,a)

This reduction is conceptually important: policy evaluation is “just” analyzing the Markov reward process induced by π.

Value function: expected discounted return

Now we define the central predictive quantities.

State-value function:

V^π(s) = 𝔼_π[ Gₜ | Sₜ = s ] = 𝔼_π[ ∑ₖ₌₀^∞ γᵏ Rₜ₊ₖ₊₁ | Sₜ = s ]

Action-value function:

Q^π(s,a) = 𝔼_π[ Gₜ | Sₜ = s, Aₜ = a ]

Intuition:

• •V^π(s) tells you how good it is to be in s, if you commit to following π.
• •Q^π(s,a) tells you how good it is to take action a in s, and then follow π.

Advantage function (useful later)

A closely related quantity is the advantage:

A^π(s,a) = Q^π(s,a) − V^π(s)

It measures how much better/worse an action is compared to the policy’s average behavior at s.

Bellman expectation equations (the key recursion)

Why a recursion exists

Because of the Markov property, the future after the next step depends only on the next state (and the policy). So the return decomposes into:

Gₜ = Rₜ₊₁ + γ Gₜ₊₁

Take conditional expectation under π.

Deriving the Bellman expectation equation for V^π

Start from the definition:

V^π(s) = 𝔼_π[ Gₜ | Sₜ = s ]

Substitute Gₜ = Rₜ₊₁ + γ Gₜ₊₁:

V^π(s)

= 𝔼_π[ Rₜ₊₁ + γ Gₜ₊₁ | Sₜ = s ]

= 𝔼_π[ Rₜ₊₁ | Sₜ = s ] + γ 𝔼_π[ Gₜ₊₁ | Sₜ = s ]

Now expand the next-step expectation by conditioning on Aₜ and Sₜ₊₁:

𝔼_π[ Rₜ₊₁ + γ V^π(Sₜ₊₁) | Sₜ = s ]

= ∑ₐ π(a|s) ∑_{s′} P(s′|s,a) \big( R(s,a,s′) + γ V^π(s′) \big)

So:

V^π(s) = ∑ₐ π(a|s) ∑_{s′} P(s′|s,a) ( R(s,a,s′) + γ V^π(s′) )

This is the Bellman expectation equation for V^π.

Bellman expectation equation for Q^π

Similarly:

Q^π(s,a) = ∑_{s′} P(s′|s,a) ( R(s,a,s′) + γ 𝔼_{a′∼π(·|s′)}[ Q^π(s′,a′) ] )

Or equivalently:

Q^π(s,a) = ∑_{s′} P(s′|s,a) ( R(s,a,s′) + γ ∑_{a′} π(a′|s′) Q^π(s′,a′) )

Vector/matrix form (finite state MRP view)

When π is fixed, you can write the state-value Bellman equation in linear algebra form.

Let V^π ∈ ℝ^{|S|} be a vector with entries V^π(s). Define:

• •P^π ∈ ℝ^{|S|×|S|}, with entries P^π(s′|s)
• •r^π ∈ ℝ^{|S|}, with entries r^π(s) = 𝔼_π[Rₜ₊₁|Sₜ=s]

Then:

V^π = r^π + γ P^π V^π

Rearrange:

( I − γ P^π ) V^π = r^π

If ( I − γ P^π ) is invertible (it is under standard discounted assumptions), then:

V^π = ( I − γ P^π )⁻¹ r^π

This “closed form” is conceptually useful: policy evaluation becomes solving a linear system. Practically, DP and iterative methods are often preferred.

A note on terminal states and episodic tasks

Many tasks end (episode termination). A common modeling choice:

• •Add terminal absorbing state s_T with P(s_T|s_T,a)=1 and reward 0 thereafter.
• •Or define V(s_T)=0 by convention.

Either way, Bellman equations remain valid with appropriate boundary conditions.

Why “optimality” is subtle

Once you define V^π and Q^π, it’s tempting to say “pick the action with highest value.” But value depends on the policy itself: if you change actions now, future actions may also change.

So we define optimality in a fixed point sense: an optimal policy is one whose value dominates all others.

Optimal value functions

Define the optimal state-value function:

V*(s) = max_π V^π(s)

and optimal action-value function:

Q*(s,a) = max_π Q^π(s,a)

These exist for finite discounted MDPs.

Bellman optimality equation for V*

Start from: if you are in s, and you act optimally, you choose the best action a, then the environment transitions, and you continue optimally from s′.

That gives:

V(s) = maxₐ ∑_{s′} P(s′|s,a) ( R(s,a,s′) + γ V(s′) )

This is the Bellman optimality equation.

Bellman optimality equation for Q*

Similarly, for Q* you commit to the first action a, then behave optimally afterward:

Q(s,a) = ∑_{s′} P(s′|s,a) ( R(s,a,s′) + γ max_{a′} Q(s′,a′) )

Greedy policies and extracting an optimal policy

Once you have Q*(s,a), you can define a greedy policy:

π(s) ∈ argmaxₐ Q(s,a)

This π* is optimal (ties may yield multiple optimal policies).

Policy improvement theorem (why greedy helps)

A key piece of theory is that being greedy with respect to a value function improves (or at least does not worsen) the policy.

Let π be any policy, and define a new policy π′ such that for all s:

π′(s) ∈ argmaxₐ Q^π(s,a)

Then:

V^{π′}(s) ≥ V^π(s) for all s

This theorem justifies policy iteration: evaluate π to get V^π (or Q^π), improve greedily to get π′, repeat.

Contraction view (why the Bellman operator converges)

Define the Bellman optimality operator T acting on a value function V:

(TV)(s) = maxₐ ∑_{s′} P(s′|s,a) ( R(s,a,s′) + γ V(s′) )

Then V* is the unique fixed point:

V = T V

Under the max norm ‖·‖∞, T is a γ-contraction:

‖T V − T W‖∞ ≤ γ ‖V − W‖∞

This matters because:

• •Repeatedly applying T (value iteration) converges to V*.
• •The rate depends on γ: as γ → 1, convergence slows.

Even if you don’t prove the contraction fully, the intuition is strong: discounting shrinks the influence of future differences by γ each step.

Comparing the “three Bellman equations”

Where the reward function fits

A common confusion: “Is reward tied to states or transitions?” In general, reward can depend on (s,a,s′). For many derivations, we use its expectation:

R̄(s,a) = 𝔼[ Rₜ₊₁ | Sₜ=s, Aₜ=a ] = ∑_{s′} P(s′|s,a) R(s,a,s′)

Then Bellman optimality for V* can be written:

V(s) = maxₐ \big( R̄(s,a) + γ ∑_{s′} P(s′|s,a) V(s′) \big)

It’s the same idea—just less notation.

Deterministic vs stochastic optimal policies

In finite discounted MDPs, there always exists an optimal deterministic stationary policy (depends only on s, not time). That’s a powerful simplification:

• •You don’t need to search over time-dependent policies.
• •You don’t need randomness to be optimal (though it may still be useful for learning).

This fact is part of why MDPs are such a clean framework.

Why dynamic programming applies

Dynamic programming works when:

• •The problem has optimal substructure: optimal decisions from state s depend on optimal solutions of successor states.
• •Subproblems overlap: many trajectories revisit the same state.

The Bellman optimality equation is precisely the DP recursion.

Value iteration

Value iteration applies the optimality operator repeatedly.

Initialize V₀(s) arbitrarily (often 0). Then iterate:

V_{k+1}(s) = maxₐ ∑_{s′} P(s′|s,a) ( R(s,a,s′) + γ V_k(s′) )

After convergence to V*, extract:

π(s) ∈ argmaxₐ ∑_{s′} P(s′|s,a) ( R(s,a,s′) + γ V(s′) )

What’s happening conceptually:

• •Early iterations propagate reward information one step outward.
• •Each iteration increases the “planning horizon” by roughly one step.

Policy iteration

Policy iteration alternates between evaluation and improvement.

1) Policy evaluation: solve for V^π via:

V^π(s) = ∑ₐ π(a|s) ∑_{s′} P(s′|s,a) ( R(s,a,s′) + γ V^π(s′) )

In matrix form:

( I − γ P^π ) V^π = r^π

2) Policy improvement:

π_new(s) ∈ argmaxₐ ∑_{s′} P(s′|s,a) ( R(s,a,s′) + γ V^π(s′) )

Repeat until the policy stops changing.

Value iteration vs policy iteration

Where “learning” begins (model-free RL)

DP assumes you know P and R. In many RL problems you don’t; you only observe samples.

But the MDP framing still matters because:

• •TD learning methods approximate Bellman expectation equations using samples.
• •Q-learning approximates the Bellman optimality equation using samples.
• •Actor-critic methods tie policy optimization to value estimation (advantage functions).

This is the bridge from MDP theory to modern RL.

Connection to policy gradients (unlock)

Policy gradient methods optimize π_θ directly. The objective is typically:

J(θ) = 𝔼_{τ∼π_θ}[ ∑ₜ γᵗ Rₜ₊₁ ]

Even though policy gradients do not require an explicit model P, they still rely on the MDP structure:

• •Trajectories τ are generated by the MDP transitions.
• •The return Gₜ is defined by the same discounted sum.
• •Baselines often use V^π(s) to reduce variance, introducing the advantage A^π(s,a).

So understanding Bellman equations makes actor-critic updates feel motivated rather than magical.

Connection to task discretization (unlock)

When you discretize a continuous or ill-defined task (common in LLM agent systems), you often create:

• •A discrete state representation S (milestones, tool states, memory summaries)
• •A discrete action set A (tool calls, subtask choices)
• •A reward signal R (success metrics, latency penalties, correctness scores)

If the resulting system approximately satisfies a Markov property (state summarizes relevant history), you can treat it as an MDP and apply planning/evaluation ideas:

• •Estimate values of subtasks (states)
• •Compare strategies (policies)
• •Reason about long-horizon tradeoffs via γ

Even if the environment is only approximately Markov, the MDP lens provides a disciplined way to debug and improve the design.

Beyond the basics (what to keep in mind at difficulty 5)

MDPs are clean, but real RL systems introduce complications:

• •Large/continuous state spaces: V and Q must be approximated.
• •Partial observability: the Markov property fails for raw observations (POMDPs).
• •Average-reward vs discounted: some continuing tasks use average reward instead of γ.
• •Off-policy learning: evaluating/improving a target policy while behaving with another.

Still, the MDP + Bellman equations remain the conceptual backbone.