7.7.2 The MDP Framing

Basic Prerequisites: 01 · From Zero and Probability & Measure Theory.

---

1. Intuition & Practical Objective

Before any algorithm, the modelling decision that determines everything: what is the state, what are the actions, and what exactly is the reward? This page is the formal spine of the folder. It writes trading as a Markov Decision Process $(\mathcal{S},\mathcal{A},P,R,\gamma )$, shows how the Bellman equations turn that into a solvable fixed point, and - most importantly - shows how to look at a trading problem and choose a state representation that actually satisfies the Markov property.

The practical objective: a reader should be able to take any trading decision (“rebalance this book”, “liquidate this order”, “quote this market”) and write down a defensible MDP, then justify why the Bellman equation applies. If the state is wrong, every algorithm downstream is wrong in the same way.

The three design questions, in order of importance:

1. Reward. What am I maximizing? In execution: realized proceeds minus impact minus a risk penalty. In portfolio: log growth, or mean-variance, or a drawdown-adjusted return. The reward is the specification of the strategy.
2. State. What must I remember so that the future is conditionally independent of the deeper past? Inventory, time-to-deadline, price/vol features, outstanding order size. “Enough state” is a modelling claim, not a wish.
3. Action. What can I actually do, and on what grid? Shares-per-interval, limit-price offsets, target-position fractions. The action space’s shape (discrete vs continuous) determines which algorithm (Q-learning vs policy gradient) is even applicable.

---

2. Mathematical Ground Truth & Derivations

2.1 The MDP and the two Bellman equations

An MDP is the tuple $(\mathcal{S},\mathcal{A},P,R,\gamma )$ with transition kernel $P(s^{\prime }\mid s,a)$ and expected reward $R(s,a)=\mathbb{E}[R_{t+1}\mid S_t=s,A_t=a]$. The state-value and action-value functions under policy $\pi$ are

$$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].$$

Expanding $G_t=R_{t+1}+\gamma G_{t+1}$ gives the Bellman expectation equation

$$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 })],$$

and, taking the max over actions, the Bellman optimality equation

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

The optimal action-value satisfies $Q^{\ast }(s,a)=R(s,a)+\gamma {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a){\max }_{a^{\prime }}{Q}^{\ast }(s^{\prime },a^{\prime })$ and the optimal policy is greedy, ${\pi }^{\ast }(s)=\arg {\max }_a{Q}^{\ast }(s,a)$.

2.2 Contraction and existence

Define the Bellman optimality operator $(\mathcal{T}V)(s)={\max }_a[R(s,a)+\gamma {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)V(s^{\prime })]$. For $\gamma <1$ it is a $\gamma$-contraction in the sup-norm: $\Vert \mathcal{T}V-\mathcal{T}U{\Vert }_{\infty }\le \gamma \Vert V-U{\Vert }_{\infty }$. By Banach’s fixed-point theorem it has a unique fixed point $V^{\ast }$, and value iteration $V_{k+1}=\mathcal{T}{V}_k$ converges geometrically at rate $\gamma$. This is why discounted RL works at all - and why an undiscounted ($\gamma =1$) infinite-horizon trading problem needs care (it may not contract).

2.3 The trading MDP, concretely

For optimal execution of $X_0$ shares over $T$ steps:

• State $S_t=(t,x_t)$ - time step and shares remaining (optionally a price/volatility feature).
• Action $A_t=v_t$ - shares to sell this interval, $0\le v_t\le x_t$ (discrete grid or continuous).
• Reward $R_{t+1}=v_t(S_t-\eta v_t)-h{x}_t$ - proceeds net of temporary impact $\eta v_t$ (linear or convex) and a holding/risk penalty $h{x}_t$ for the inventory you still carry.
• Dynamics $x_{t+1}=x_t-v_t$; price is typically a martingale under the reference measure, so the only control-relevant cost is impact plus the risk of holding.

This is the canonical RL-execution formulation (Nevmyvaka–Kearns; and the DP twin of Almgren–Chriss). The holding penalty subsumes risk aversion: larger $h$ (or smaller $\gamma$) makes the agent sell faster.

2.4 The Markov property is engineered, not assumed

The chain $S_t$ must be such that $\mathbb{E}[R_{t+1}\mid S_t,A_t]=\mathbb{E}[R_{t+1}\mid \text{history}]$. Financial state is deliberately constructed to satisfy this: you include the unfilled inventory (not just total traded), time-to-deadline, and enough price statistics that the conditional expectation is stable. The regime-switching analogue - where the hidden state must be inferred - is HMM & GMM; here we assume the state is observed.

---

3. Computational Implementation - build a stochastic MDP and verify the Bellman fixed point

Here the price is a genuine 2-state Markov chain (sticky: stays with prob $0.7$), so the MDP is stochastic and the transition kernel is explicit. We solve it by value iteration and then verify the Bellman optimality equation holds to machine precision. Stdlib only.

Two things are worth reading off. First, the Bellman residual is exactly zero - value iteration has found the true fixed point $V^{\ast }=\mathcal{T}{V}^{\ast }$, the object every learning method in 03 and 04 is trying to reach. Second, the value is state-dependent: $Q^{\ast }(11,\cdot )>Q^{\ast }(9,\cdot )$ because holding the same inventory in a high-price state is worth more, and the greedy action can differ across price states purely because the future price distribution differs. A state-blind policy could not express this.

---

4. Failure Modes & First-Principles Breakdowns

1. State aliasing (Markov violation). If two genuinely different situations are mapped to the same state $s$, the Bellman backup averages over them and $Q^{\ast }(s,\cdot )$ is a blur of two problems. Classic in execution: forgetting the remaining order size, or the realized volatility that determines risk-aversion. The residual test (does $V\approx \mathcal{T}V$ on held-out paths?) is your detector.
2. Reward–risk confusion. Encoding risk as a big holding penalty $h$ and also discounting aggressively $\gamma$ double-counts impatience. Be explicit about which knob carries the risk aversion - for the continuous-time version, see Almgren–Chriss where a single $\lambda$ does it cleanly.
3. Diagnosing the wrong component. When a trained agent underperforms, first recompute $V^{\ast }$ by value iteration on your simulator and check the agent reaches it. If it does and you still lose money, the simulator (P, R) is wrong, not the algorithm - the single most common misdiagnosis in trading-RL.
4. Undiscounted infinite-horizon traps. With $\gamma =1$ and a non-absorbing chain the contraction argument fails; value iteration can diverge and Q-learning has no fixed point guarantee. Discount, or impose a hard terminal liquidation.
5. Action-space / grid mismatch. Discretizing shares too coarsely can make the intended schedule unreachable; too finely and tabular methods explode. This is a modelling cost, not a bug to be tuned away (motivating function approximation in 03).

---

5. References

• Sutton & Barto, Reinforcement Learning: An Introduction (2nd ed., 2018)
• Bertsekas, Dynamic Programming and Optimal Control, Vol I
• Bertsimas, Dimitris & Lo, Andrew W.: “Optimal Control of Execution Costs” (J. Financial Markets 1(1), 1998)
• Nevmyvaka, Feng & Kearns (ICML 2006)
• Puterman, Martin L.: Markov Decision Processes (1994)

---

6. Connected Graph Bridges

• Back: 01 · From Zero
• Forward: 03 · Value-Based RL · 04 · Policy-Gradient & Actor-Critic · Index Hub
• Theory base: Probability & Measure Theory · Calculus & Optimization
• State inference (when the state is hidden): Regime Classification: HMM & GMM
• Continuous-time cousin: Optimal Execution & Almgren–Chriss