Markov Decision Processes

For any policy $\pi$, the value function $V^\pi$ satisfies:

$V^\pi(s) = \sum_{a} \pi(a|s) \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) \, V^\pi(s') \right]$

In matrix form, writing $R^\pi$ for the expected reward vector under $\pi$ and $P^\pi$ for the transition matrix under $\pi$:

$V^\pi = R^\pi + \gamma P^\pi V^\pi$

The value of a state is the expected immediate reward plus the discounted expected value of the next state. This recursion expresses the idea that the future looks the same from any point in a Markov process. SO we can break the infinite-horizon problem into one step plus the rest.

The Bellman expectation equation is a system of $|\mathcal{S}|$ linear equations in $|\mathcal{S}|$ unknowns. For a fixed policy, the value function can be computed exactly by solving $V^\pi = (I - \gamma P^\pi)^{-1} R^\pi$. This is the basis of policy evaluation.

The optimal value function $V^*$ satisfies:

$V^*(s) = \max_{a \in \mathcal{A}} \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) \, V^*(s') \right]$

Equivalently, the optimal action-value function satisfies:

$Q^*(s,a) = R(s,a) + \gamma \sum_{s'} P(s'|s,a) \max_{a'} Q^*(s', a')$

The optimal value of a state is obtained by choosing the action that maximizes the immediate reward plus discounted future value. The max replaces the expectation over the policy because the optimal agent always picks the best action.

Unlike the Bellman expectation equation, the Bellman optimality equation is nonlinear (because of the max). It cannot be solved by matrix inversion. Instead, we solve it iteratively via value iteration or policy iteration.

Define the Bellman optimality operator $\mathcal{T}: \mathbb{R}^{|\mathcal{S}|} \to \mathbb{R}^{|\mathcal{S}|}$ by:

$(\mathcal{T}V)(s) = \max_{a} \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) \, V(s') \right]$

Then $\mathcal{T}$ is a $\gamma$-contraction in the $\ell^\infty$ norm:

$\|\mathcal{T}V - \mathcal{T}U\|_\infty \leq \gamma \|V - U\|_\infty$

By the Banach fixed point theorem, $\mathcal{T}$ has a unique fixed point $V^*$, and value iteration $V_{k+1} = \mathcal{T}V_k$ converges to $V^*$ at rate $\gamma^k$.

Applying the Bellman update brings any value estimate closer to the true optimal value. The discount factor $\gamma < 1$ is doing the heavy lifting: each application of $\mathcal{T}$ shrinks errors by a factor of $\gamma$.

This theorem guarantees that value iteration converges, and tells us the rate. After $k$ iterations, $\|V_k - V^*\|_\infty \leq \gamma^k \|V_0 - V^*\|_\infty$. The contraction property is the reason dynamic programming works.

If $\gamma = 1$ (undiscounted), the operator is not a contraction and value iteration may not converge. The undiscounted case requires additional structure (e.g., all policies reach a terminal state).

Let $\pi$ be a policy and define the greedy policy $\pi'$ by:

$\pi'(s) = \arg\max_{a} Q^\pi(s, a)$

Then $V^{\pi'}(s) \geq V^\pi(s)$ for all $s \in \mathcal{S}$, with equality for all $s$ if and only if $\pi$ is already optimal.

If you evaluate a policy, then act greedily with respect to the resulting value function, you can only do better. This is the engine behind policy iteration: evaluate, improve, repeat.

Combined with policy evaluation, this gives the policy iteration algorithm: evaluate $\pi$ exactly, improve to $\pi'$, and repeat. Since there are finitely many deterministic policies and each step improves the value, policy iteration terminates at the optimal policy in finite steps.