Markov Decision Processes.
An MDP is a 5-tuple: $$ \mathcal{M} = (\mathcal{S}, \mathcal{A}, P, R, \gamma) $$- \(\mathcal{S}\): state space
- \(\mathcal{A}\): action space
- \(P(s' \mid s,a)\): transition model (probability of next state \(s'\))
- \(R(s,a)\): expected immediate reward
- \(\gamma \in [0,1)\): discount factor
A state must contain enough information
The Markov assumption concerns the information available for predicting the next transition. A pendulum angle alone is usually insufficient: two pendulums at the same angle can be moving in opposite directions. Including angular velocity makes the state more informative. If remaining time affects the task's rewards or termination, it also belongs in a finite-horizon state. An observation vector is not automatically a Markov state merely because a simulator returns it.
We can describe rewards and next states jointly with \(p(s',r\mid s,a)\). The notation above is its marginal form: $$P(s'\mid s,a)=\sum_r p(s',r\mid s,a),\qquad R(s,a)=\sum_{s',r}r\,p(s',r\mid s,a).$$ The sums become integrals for continuous quantities. Keeping the joint model in mind helps with terminal rewards: a reward may depend on which destination was reached, even though \(R(s,a)\) averages over those destinations.
Trajectories and return.
Under a policy \(\pi\), the interaction produces a trajectory \((s_0,a_0,r_0,s_1,a_1,r_1,\dots)\). The discounted return from time \(t\) is: $$ G_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k}. $$ Reinforcement learning is typically framed as finding a policy that maximizes expected return.Reward timing, boundaries, and the planning horizon
This post writes \(r_t\) for the reward generated by action \(a_t\). Later posts often call that same reward \(R_{t+1}\). In both conventions it belongs to the transition from \(S_t\) to \(S_{t+1}\). A return is a random outcome along one trajectory; a value function is its conditional expectation over possible trajectories.
For an episode ending at \(T\), set \(G_T=0\) and sum only through the final action. A terminal state has zero continuation value even if the transition into it pays a reward. For an infinite horizon with \(|r_t|\le R_{\max}\), $$|G_t|\le\frac{R_{\max}}{1-\gamma},\qquad \left|\sum_{k=H}^{\infty}\gamma^k r_{t+k}\right|\le\frac{\gamma^H R_{\max}}{1-\gamma}.$$ Discounting therefore bounds both values and the error from cutting off distant rewards. The bound needs bounded rewards; \(\gamma<1\) alone is not enough for every conceivable reward process.
Given an initial-state distribution \(\rho_0\), the performance objective is $$J(\pi)=\sum_s\rho_0(s)V^\pi(s).$$ Changing \(\rho_0\) changes which starting situations count toward reported performance. In a genuinely finite-horizon problem we may use \(\gamma=1\), but the discounted contraction argument later in this post then needs to be replaced by backward induction or other appropriate episodic assumptions.
Policies.
A (stochastic) policy is a conditional distribution over actions given a state: $$ \pi(a\mid s) = P(a_t=a \mid s_t=s). $$ A deterministic policy is a special case where \(\pi(a\mid s)\) puts all probability mass on one action, often written as \(\pi(s)\in\mathcal{A}\).Value functions
The state-value function under policy \(\pi\) is: $$ V^\pi(s) = \mathbb{E}_\pi \left[G_0 \mid s_0=s\right] = \mathbb{E}_\pi\left[\sum_{t=0}^{\infty}\gamma^t r_t \,\middle|\, s_0=s\right]. $$ The action-value function (often more directly useful in control) is: $$ Q^\pi(s,a) = \mathbb{E}_\pi\left[\sum_{t=0}^{\infty}\gamma^t r_t \,\middle|\, s_0=s, a_0=a\right]. $$ The optimal value functions are: $$ V^*(s)=\max_\pi V^\pi(s), \qquad Q^*(s,a)=\max_\pi Q^\pi(s,a). $$ And an optimal policy can be recovered by acting greedily with respect to \(Q^*\): $$ \pi^*(s)\in \arg\max_a Q^*(s,a). $$Bellman expectation equations.
The key idea is that value functions satisfy a one-step recursion. For a fixed policy \(\pi\), we can “peel off” the first reward and then the rest is the value of the next state: $$ V^\pi(s) = \sum_a \pi(a\mid s)\Bigg[ R(s,a) + \gamma \sum_{s'} P(s'\mid s,a)V^\pi(s') \Bigg]. $$ Similarly: $$ Q^\pi(s,a) = R(s,a) + \gamma \sum_{s'} P(s'\mid s,a)\sum_{a'}\pi(a'\mid s')Q^\pi(s',a'). $$ It is often useful to note the relationship between \(V^\pi\) and \(Q^\pi\): $$ V^\pi(s)=\sum_a \pi(a\mid s)Q^\pi(s,a). $$Deriving the recursion with conditional expectations
Start with the identity \(G_t=r_t+\gamma G_{t+1}\). Condition on the current state, and then condition again on the action and next outcome: $$\begin{aligned}V^\pi(s)&=\mathbb E_\pi[r_t+\gamma G_{t+1}\mid S_t=s]\\&=\sum_a\pi(a\mid s)\sum_{s',r}p(s',r\mid s,a)\big[r+\gamma\mathbb E_\pi[G_{t+1}\mid S_{t+1}=s']\big].\end{aligned}$$ The Markov property and a stationary policy let us identify the inner expectation as \(V^\pi(s')\). This is the step that turns a statement about whole trajectories into a reusable one-step equation.
The equation averages over outcomes; it does not claim every observed return equals its expectation. If an action succeeds half the time with reward 10 and otherwise returns zero, its expected immediate reward is 5, although no individual trial pays 5. Similarly, a Bellman equation constrains expected continuation values without making the environment deterministic.
Bellman optimality equations.
If we want the best possible policy, we can replace the policy expectation with a max: $$ V^*(s)=\max_a \left[ R(s,a) + \gamma \sum_{s'}P(s'\mid s,a)V^*(s') \right]. $$ And: $$ Q^*(s,a)=R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)\max_{a'}Q^*(s',a'). $$ These equations define the optimal solution as a fixed point. The rest of RL is about computing or approximating that fixed point.Bellman operators and convergence (why iteration works).
Define the policy evaluation operator \(T^\pi\): $$ (T^\pi V)(s) = \sum_a \pi(a\mid s)\left[R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s')\right]. $$ And the optimality operator \(T^*\): $$ (T^* V)(s)=\max_a\left[R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s')\right]. $$ A crucial fact: for \(\gamma\in[0,1)\), both operators are \(\gamma\)-contractions under the sup norm: $$ \|T V - T W\|_\infty \le \gamma \|V-W\|_\infty. $$ This implies:- Each operator has a unique fixed point: \(V^\pi\) for \(T^\pi\), and \(V^*\) for \(T^*\).
- Repeated application converges: \(V_{k+1}=T^\pi V_k\) converges to \(V^\pi\), and \(V_{k+1}=T^* V_k\) converges to \(V^*\).
Why approximation errors shrink under a backup
For policy evaluation, subtract the two backups. Their reward terms cancel. Taking absolute values gives $$|(T^\pi V)(s)-(T^\pi W)(s)|\le\gamma\sum_{a,s'}\pi(a\mid s)P(s'\mid s,a)|V(s')-W(s')|\le\gamma\|V-W\|_\infty.$$ The final inequality follows because probabilities sum to one. For optimality, use \(|\max_a x_a-\max_a y_a|\le\max_a|x_a-y_a|\) before applying the same bound.
Consequently, after \(k\) exact sweeps, \(\|V_k-V^*\|_\infty\le\gamma^k\|V_0-V^*\|_\infty\). We can also measure the Bellman residual \(e=\|T^*V-V\|_\infty\) without knowing \(V^*\). The triangle inequality gives \(\|V-V^*\|_\infty\le e+\gamma\|V-V^*\|_\infty\), hence $$\|V-V^*\|_\infty\le\frac{e}{1-\gamma}.$$ A residual of 0.01 at \(\gamma=0.99\) only certifies a value error no larger than 1. This explains why a seemingly small update can still be insufficient when the horizon is long.
Dynamic programming teaser.
If the transition model \(P\) and reward function \(R\) are known, we can solve the MDP with dynamic programming:- Policy evaluation: compute \(V^\pi\) (a prediction problem).
- Policy improvement: make the policy greedy with respect to \(V^\pi\) (a control step).
- Alternating these yields policy iteration.
- Applying \(T^*\) repeatedly yields value iteration.
Worked MDP example: small stochastic grid.
We will use a 3-state MDP:- State 0: terminal “bad” (reward 0)
- State 1: decision state
- State 2: terminal “good” (reward +1)
left or right. The outcome is slightly stochastic: with probability 0.9 you go the intended direction, and with probability 0.1 you slip to the opposite terminal. This makes the Bellman expectations non-trivial.
import numpy as np
states = [0, 1, 2]
actions = ["left", "right"]
gamma = 0.95
# Transition model P[s, a] -> list of (prob, s_next, reward)
# Terminal states self-loop with zero reward.
P = {
0: {"left": [(1.0, 0, 0.0)], "right": [(1.0, 0, 0.0)]},
2: {"left": [(1.0, 2, 0.0)], "right": [(1.0, 2, 0.0)]},
1: {
"left": [(0.9, 0, 0.0), (0.1, 2, 1.0)],
"right": [(0.9, 2, 1.0), (0.1, 0, 0.0)]
}
}
def bellman_backup(V, s, a):
# Computes: R(s,a) + gamma * sum_{s'} P(s'|s,a) V(s')
return sum(prob * (r + gamma * V[s_next]) for (prob, s_next, r) in P[s][a])
1) Value iteration.
Value iteration applies the Bellman optimality operator \(T^*\) repeatedly: $$ V_{k+1}(s) \leftarrow \max_a \left[ R(s,a) + \gamma \sum_{s'}P(s'\mid s,a)V_k(s') \right]. $$
V = np.zeros(len(states))
for k in range(50):
V_new = V.copy()
# Only state 1 is non-terminal in this toy MDP
s = 1
V_new[s] = max(bellman_backup(V, s, a) for a in actions)
# Check convergence (optional)
if np.max(np.abs(V_new - V)) < 1e-10:
V = V_new
break
V = V_new
# Extract greedy policy from V
q_left = bellman_backup(V, 1, "left")
q_right = bellman_backup(V, 1, "right")
pi_star = "right" if q_right > q_left else "left"
print("V*:", V)
print("Greedy policy at state 1:", pi_star)
print("Q*(1,left), Q*(1,right):", q_left, q_right)
Checking the numbers before running the iteration
Both destination states have zero continuation value. Therefore $$Q^*(1,\mathrm{left})=0.1,\qquad Q^*(1,\mathrm{right})=0.9.$$ A policy choosing right with probability \(p\) has \(V^\pi(1)=0.1+0.8p\). The uniform policy is worth 0.5, always-left is worth 0.1, and always-right is worth 0.9. Starting from zero, value iteration reaches the answer in one nontrivial sweep.
The discount factor has no effect in this particular example because the only nonzero reward is immediate. If instead a successful move led to an intermediate state that paid 1 on the following transition, the right action would be worth \(0.9\gamma\). This distinction is useful when debugging: shifting a reward by one transition changes its discount, even when the diagram looks almost identical.
2) Policy iteration (in depth).
Policy iteration alternates:- Policy evaluation: solve \(V^\pi = T^\pi V^\pi\).
- Policy improvement: update $$\pi(s)\in\arg\max_a \left[R(s,a)+\gamma\sum_{s'}P(s'|s,a)V^\pi(s')\right].$$
# Initialize a deterministic policy at state 1
policy = {1: "left"}
V = np.zeros(len(states))
def policy_evaluation(policy, V, iters=50):
# Iterative evaluation: V <- T^pi V
for _ in range(iters):
V_new = V.copy()
s = 1
a = policy[s]
V_new[s] = bellman_backup(V, s, a)
V = V_new
return V
def policy_improvement(V):
# Greedy improvement at state 1
q = {a: bellman_backup(V, 1, a) for a in actions}
return "right" if q["right"] > q["left"] else "left"
for _ in range(10):
V = policy_evaluation(policy, V, iters=50)
new_action = policy_improvement(V)
if new_action == policy[1]:
break
policy[1] = new_action
print("Policy-iteration policy:", policy)
print("Value under policy:", V)
Value iteration vs policy iteration.
- Value iteration performs “partial policy evaluation” implicitly by applying \(T^*\) directly. It is simple and guaranteed to converge, but can require many iterations for tight tolerance.
- Policy iteration evaluates the current policy more fully, then improves it. It often converges in fewer outer loops, but each evaluation step can be more expensive.