MDP Formulation for Stock Trading

Optimization · Medium · Free problem

You want to trade a single stock over a finite horizon of $T$ time steps to maximize your expected total profit. At each step you observe the current stock price $S_t$ and whether you currently hold the stock or not.

At each time step, you can take one of three actions: buy one share (if you have no position), sell your share (if you are holding), or hold (do nothing). Buying costs you $S_t$ and selling earns you $S_t$. Assume you can only hold at most one share at a time and there are no transaction costs beyond the price itself.

The stock price follows a discrete-time Markov process -- that is, $S_{t+1}$ depends only on $S_t$, not on the full history.

  1. Formulate this problem as a Markov Decision Process: define the state space, action space, transition probabilities, and reward function.
  1. Write down the Bellman equation for the value function $V(t, s, h)$ where $t$ is time, $s$ is the stock price, and $h \in \{0, 1\}$ indicates whether you hold the stock.
  1. How would you solve this MDP in practice? Discuss the approach and any complications that arise when the price space is large or continuous.

Hints

  1. Think about what information you need at each time step to decide whether to act. That gives you the state space.
  2. The state should include both the stock price and your current position. The action space depends on which of those two position states you are in.
  3. Write the Bellman equation by comparing the expected value of acting (buying or selling) versus holding, using the Markov transition probabilities to compute the expectation over future prices.

Worked Solution

How to Think About It: This is a classic setup question that every quant should be able to rattle off. The key tension is simple: you want to buy low and sell high, but you do not know the future. The MDP framework lets you think about this rigorously -- at every point in time, given what you know right now (price and position), what is the optimal action? The entire problem reduces to defining four things cleanly: states, actions, transitions, and rewards. Once you have those, the Bellman equation writes itself.

Key Insight: The state must capture everything you need to make an optimal decision. Here that means the current time $t$, the current price $S_t$, and whether you are holding the stock $h \in \{0, 1\}$. If you forget to include the holding indicator, you cannot distinguish "should I buy?" from "should I sell?" -- the action space depends on the state.

The Method:

Part 1 -- MDP Formulation:

  • State space: $\mathcal{S} = \{(t, s, h) : t \in \{0, 1, \ldots, T\},\; s \in \mathcal{P},\; h \in \{0, 1\}\}$, where $\mathcal{P}$ is the set of possible prices and $h = 1$ means you hold the stock.
  • Action space: At state $(t, s, 0)$ (no position): $\mathcal{A} = \{\text{buy}, \text{hold}\}$. At state $(t, s, 1)$ (holding): $\mathcal{A} = \{\text{sell}, \text{hold}\}$. This enforces the constraint that you cannot sell what you do not own or buy a second share.
  • Transition probabilities: Since the price is Markov, $P(S_{t+1} = s' \mid S_t = s) = p(s' \mid s)$, independent of the action taken (actions affect your portfolio, not the stock price). The holding state transitions deterministically: buy flips $h$ from 0 to 1, sell flips $h$ from 1 to 0, hold keeps $h$ unchanged.
  • Reward function: $R(t, s, h, a)$ captures the immediate cash flow:
  • Buy: $R = -s$ (you pay the price)
  • Sell: $R = +s$ (you receive the price)
  • Hold: $R = 0$
  • At terminal time $T$, if $h = 1$, you can either force a liquidation at $S_T$ or assign $R = S_T$ as a terminal reward to close out the position.

Part 2 -- Bellman Equation:

For $t < T$:

$$V(t, s, 0) = \max\left\{-s + \sum_{s'} p(s' \mid s)\, V(t+1, s', 1),\;\; \sum_{s'} p(s' \mid s)\, V(t+1, s', 0)\right\}$$

$$V(t, s, 1) = \max\left\{+s + \sum_{s'} p(s' \mid s)\, V(t+1, s', 0),\;\; \sum_{s'} p(s' \mid s)\, V(t+1, s', 1)\right\}$$

The first term in each max corresponds to acting (buy or sell), the second to holding. Terminal conditions: $V(T, s, 0) = 0$ and $V(T, s, 1) = s$ (forced liquidation at horizon).

Part 3 -- Practical Solution:

  1. Discretize the price space. If $S_t$ takes on $M$ possible values, the state space has size $2 \times M \times T$. For a coarse grid ($M \sim 50$-$100$, $T \sim 250$ trading days), this is easily solvable by backward induction in $O(T \cdot M^{2})$ time.
  1. Backward induction. Start at $t = T$ with the terminal values. At each step $t = T-1, T-2, \ldots, 0$, compute $V(t, s, h)$ for all $(s, h)$ by evaluating both actions and taking the max. Store the optimal action as the policy.

3. Complications with large/continuous price spaces: - The curse of dimensionality hits when you add features to the state (e.g., volume, volatility regime, multiple assets). The state space grows exponentially. - For continuous prices, you need function approximation -- fit $V(t, s, h)$ with regression (Longstaff-Schwartz style) or a neural network. - Model risk is the elephant in the room: your transition probabilities $p(s' \mid s)$ are estimated, not known. The optimal policy is only as good as the model. In practice, traders add constraints (position limits, maximum holding periods) to make the policy more robust to model misspecification.

Practical Considerations:

  • Adding transaction costs is straightforward: replace $R(\text{buy}) = -s - c$ and $R(\text{sell}) = s - c$ for some cost $c$. This creates a no-trade region around the current position, which is economically sensible.
  • A discount factor $\gamma < 1$ can be included if you want to penalize delayed profits, though for short-horizon trading this is often set to 1.
  • If the Markov assumption is too restrictive, you can expand the state to include lagged prices or technical indicators, but this increases the state space.

Answer: The MDP has states $(t, s, h)$, actions $\{\text{buy}, \text{sell}, \text{hold}\}$ with feasibility constraints based on $h$, Markov transition probabilities for the price, and immediate rewards equal to the cash flow from each trade. The value function satisfies the Bellman equations above and is solved by backward induction over the finite horizon. For large or continuous state spaces, use function approximation methods like fitted value iteration or Longstaff-Schwartz regression.

Intuition

The MDP formulation is the bread and butter of how quants think about sequential decision-making under uncertainty. The core idea is deceptively simple: if you can define what you know (state), what you can do (actions), how the world evolves (transitions), and what you care about (rewards), then dynamic programming gives you the optimal strategy for free via the Bellman equation. This framework shows up everywhere -- from optimal execution and market making to inventory management and options hedging.

The subtle point that separates a good answer from a textbook recitation is understanding the limitations. In practice, the transition probabilities are never known exactly, and the state space for real trading problems is enormous (multiple assets, order book state, regime indicators). The MDP framework tells you what the optimal policy looks like in theory, but implementing it requires approximations -- and the choice of approximation (discretization, function approximation, constraints on the policy) is where the real skill lies. Interviewers ask this question to see if you can set up the framework cleanly and then immediately identify why the textbook version does not work out of the box.

Related problems

Open the full interactive solver →