MDPs & Bellman Equations

The Markov Decision Process is the formal language of reinforcement learning. Almost every algorithm — value iteration, Q-learning, policy gradients, modern actor-critic methods — is a way of approximately solving the Bellman equations of an MDP. This page sets up the formalism and derives the equations that every later chapter rests on.

The MDP

A (discounted, infinite-horizon) Markov Decision Process is a tuple $(\mathcal{S},\mathcal{A},P,r,\gamma ,{\rho }_0)$:

• $\mathcal{S}$ — state space.
• $\mathcal{A}$ — action space.
• $P(s^{\prime }\mid s,a)$ — transition probability.
• $r(s,a)\in \mathbb{R}$ — reward function.
• $\gamma \in [0,1)$ — discount factor.
• ${\rho }_0(s)$ — initial-state distribution.

A trajectory $\tau =(s_0,a_0,s_1,a_1,\dots )$ is generated by sampling $s_0\sim {\rho }_0$, then iterating $a_t\sim \pi (\cdot \mid s_t)$ and $s_{t+1}\sim P(\cdot \mid s_t,a_t)$. The return is the discounted sum of rewards $G_t=\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{r}_{t+k}$.

The Markov property — the future depends on history only through the current state — is what makes the framework tractable. Many real-world problems are not Markov in their raw observation, motivating Partially-Observable MDPs (POMDPs) and frame-stacking / RNN-based state aggregation.

Value functions

Define two functions that measure long-run reward under a policy $\pi$:

$$V^{\pi }(s)={\mathbb{E}}_{\pi }[G_t\mid s_t=s],Q^{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t\mid s_t=s,a_t=a].$$

$V^{\pi }$ is the state-value function (expected return from $s$); $Q^{\pi }$ is the action-value function. They relate as

$$V^{\pi }(s)=\sum _a\pi (a\mid s)Q^{\pi }(s,a).$$

A policy ${\pi }^{\ast }$ is optimal if $V^{{\pi }^{\ast }}(s)\ge V^{\pi }(s)$ for every $s$ and every $\pi$. Such a policy always exists (Puterman, 1994) and one of them is deterministic.

Bellman expectation equations

By conditioning on the first action and the next state:

$$V^{\pi }(s)=\sum _a\pi (a\mid s)[r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }\mid s,a)V^{\pi }(s^{\prime })],$$$$Q^{\pi }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }\mid s,a)\sum _{a^{\prime }}\pi (a^{\prime }\mid s^{\prime })Q^{\pi }(s^{\prime },a^{\prime }).$$

Both are linear in the unknowns ($V^{\pi }$, $Q^{\pi }$) given the dynamics — finite MDPs can be solved in closed form by matrix inversion. For large or unknown MDPs, iterative methods replace the inversion.

Bellman optimality equations

For the optimal policy ${\pi }^{\ast }$, the value function satisfies a non-linear fixed-point equation:

$$V^{\ast }(s)=\underset{a}{max}[r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }\mid s,a)V^{\ast }(s^{\prime })],$$$$Q^{\ast }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }\mid s,a)\underset{a^{\prime }}{max}{Q}^{\ast }(s^{\prime },a^{\prime }).$$

Once $Q^{\ast }$ is known, the optimal policy is greedy: ${\pi }^{\ast }(s)=\arg \underset{a}{max}{Q}^{\ast }(s,a)$. Knowing $Q^{\ast }$ is therefore equivalent to knowing ${\pi }^{\ast }$.

Bellman operators and contraction

Define the Bellman optimality operator ${\mathcal{T}}^{\ast }$ on the space of bounded functions $V:\mathcal{S}\to \mathbb{R}$:

$$({\mathcal{T}}^{\ast }V)(s)=\underset{a}{max}[r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }\mid s,a)V(s^{\prime })].$$

Two crucial properties:

1. ${\mathcal{T}}^{\ast }$ is a $\gamma$-contraction in the ${\ell }_{\mathrm{\infty }}$ norm: $\parallel {\mathcal{T}}^{\ast }{V}_1-{\mathcal{T}}^{\ast }{V}_2{\parallel }_{\mathrm{\infty }}\le \gamma \parallel V_1-V_2{\parallel }_{\mathrm{\infty }}$.
2. Its unique fixed point is $V^{\ast }$.

By Banach's fixed-point theorem, the iteration $V_{k+1}={\mathcal{T}}^{\ast }{V}_k$ converges to $V^{\ast }$ from any initialisation, geometrically with rate $\gamma$. This is the value iteration algorithm, and it is the prototype every later RL algorithm approximates.

Policy iteration

Alternative dynamic-programming algorithm: alternate between policy evaluation (solve $V^{\pi }$ given $\pi$) and policy improvement (set ${\pi }^{\prime }(s)=\arg \underset{a}{max}{Q}^{\pi }(s,a)$). Each step strictly improves the policy unless it is already optimal, and convergence happens in finitely many iterations on finite MDPs (Howard, 1960). Modern actor-critic algorithms are stochastic, sample-based generalisations of policy iteration.

What to read next

• Q-Learning — the model-free, sample-based version of value iteration.
• Policy Gradient — the alternative, policy-iteration-style approach.
• DQN — Q-learning with a deep network.