Markov Decision Processes and the Bellman Equation

Question

Reinforcement learning is usually the framework of choice for problems like optimal execution, where an agent takes a sequence of actions and only sees the consequences later.

Write down the formal definition of a Markov Decision Process. State the Markov property precisely. Define a policy $\pi$, the state-value function $V^{\pi}$ and the action-value function $Q^{\pi}$. Derive the Bellman expectation equation and the Bellman optimality equation, and explain how value iteration and Q-learning flow directly from them. Use an optimal-execution / inventory problem as your running example.

Accepted Answer

A Markov Decision Process (MDP) is the mathematical object that formalises sequential decision-making under uncertainty. It is the tuple \begin{equation} (S, A, P, R, \gamma) \end{equation} where $S$ is the set of states, $A$ the set of actions, $P(s_{t+1} \mid s_t, a_t)$ the transition probability of landing in state $s_{t+1}$ after taking action $a_t$ in state $s_t$, $R(s_t, a_t)$ the (expected) reward, and $\gamma \in [0, 1)$ a discount factor that makes future rewards worth less than immediate ones and keeps infinite sums finite.

Running exampleImagine optimal execution: you must liquidate a large inventory of $X$ shares before the close. The state is your remaining inventory and time left (plus market features such as spread and volatility); the action is how many shares to send this interval; the reward is the (negative) execution cost incurred, i.e. price impact plus the slippage against arrival price. The MDP captures the central tension: trade fast and you pay impact, trade slow and you carry price risk.

The Markov propertyThe defining assumption is that the future depends on the past only through the present state: \begin{equation} P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots) = P(s_{t+1} \mid s_t, a_t) \end{equation} The state must therefore be a sufficient statistic. If execution cost depends on recent traded volume, that volume has to be packed into the state, or the Markov property fails.

Policy and value functionsA policy $\pi(a \mid s)$ maps states to a distribution over actions. The agent's objective is the expected discounted return \begin{equation} G_t = \sum_{k=0}^{\infty} \gamma^{k} R_{t+k} \end{equation} We define the state-value and action-value functions as the expected return from following $\pi$: \begin{equation} V^{\pi}(s) = E_{\pi}[G_t \mid s_t = s], \qquad Q^{\pi}(s, a) = E_{\pi}[G_t \mid s_t = s, a_t = a] \end{equation} $V$ tells you how good a state is; $Q$ tells you how good a particular action is in that state.

Deriving the Bellman expectation equationThe trick is to peel the first reward off the return: \begin{equation} G_t = R_t + \gamma (R_{t+1} + \gamma R_{t+2} + \dots) = R_t + \gamma G_{t+1} \end{equation} Taking the conditional expectation under $\pi$ and using the Markov property (the tail $G_{t+1}$ depends only on $s_{t+1}$) gives the recursion \begin{equation} V^{\pi}(s) = \sum_{a} \pi(a \mid s) \left[ R(s, a) + \gamma \sum_{s_{t+1}} P(s_{t+1} \mid s, a) \, V^{\pi}(s_{t+1}) \right] \end{equation} The value of a state equals the immediate reward plus the discounted value of wherever you land next. The analogous equation for $Q^{\pi}$ is \begin{equation} Q^{\pi}(s, a) = R(s, a) + \gamma \sum_{s_{t+1}} P(s_{t+1} \mid s, a) \sum_{a_{t+1}} \pi(a_{t+1} \mid s_{t+1}) \, Q^{\pi}(s_{t+1}, a_{t+1}) \end{equation}

The Bellman optimality equationWe do not want to evaluate a fixed policy, we want the best one. The optimal value satisfies the same recursion but with a $\max$ over actions instead of an average under $\pi$: \begin{equation} V^{*}(s) = \max_{a} \left[ R(s, a) + \gamma \sum_{s_{t+1}} P(s_{t+1} \mid s, a) \, V^{*}(s_{t+1}) \right] \end{equation} \begin{equation} Q^{*}(s, a) = R(s, a) + \gamma \sum_{s_{t+1}} P(s_{t+1} \mid s, a) \max_{a_{t+1}} Q^{*}(s_{t+1}, a_{t+1}) \end{equation} The optimal policy is then simply greedy with respect to $Q^{*}$: $\pi^{*}(s) = \arg\max_a Q^{*}(s, a)$. In the execution example this says: the best action now is the one whose immediate cost plus expected best future cost is smallest.

How the algorithms flow from thisThe optimality equation is a fixed point, and the Bellman operator is a $\gamma$-contraction, so iterating it converges.

 	Value iterationwhen $P$ and $R$ are known, simply turn the optimality equation into an update and sweep until convergence: \begin{equation} V_{k+1}(s) \leftarrow \max_a \left[ R(s,a) + \gamma \sum_{s_{t+1}} P(s_{t+1} \mid s, a) V_k(s_{t+1}) \right] \end{equation}
 	Q-learningwhen $P$ and $R$ are unknown, we cannot take the expectation analytically, so we sample transitions and nudge $Q$ towards the Bellman target. After observing $(s, a, r, s_{t+1})$: \begin{equation} Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma \max_{a_{t+1}} Q(s_{t+1}, a_{t+1}) - Q(s,a) \right] \end{equation} The bracket is the temporal-difference error: the gap between the current estimate and a one-step sample of the optimality equation.

Both algorithms are nothing more than the Bellman equation made operational. For execution with a continuous state, the table is replaced by a function approximator (deep Q-networks, policy gradients), but the underlying Bellman recursion is unchanged.

Title	Category	Subcategory	Difficulty	Status
Exploration versus Exploitation	Machine Learning	Reinforcement Learning	Medium	Unlock
Q-Learning for Market Making	Machine Learning	Reinforcement Learning	Hard	Unlock

The Interview Guide for Quants and Traders

Markov Decision Processes and the Bellman Equation

What do you think of this page?