Markov Decision Processes

Most decision problems in a textbook are one-shot: here are the odds, here are the payoffs, pick the option with the best expected value. Trading is not like that. Buying today leaves you holding inventory tomorrow, which changes what you should do tomorrow. Selling into a thin book moves the price you will get on your next order. The action and the situation are entangled, and a sequence of individually sensible choices can add up to a disaster. A Markov decision process, or MDP, is the language for writing such problems down precisely enough to solve them.

The analogy: a market maker with a warehouse

Picture a market maker as a shopkeeper with a warehouse. At any moment their situation is what sits in the warehouse plus what the market looks like — inventory, mid price, spread, time left in the day. Their choice is where to post bids and offers. Whatever they choose, two things happen: money changes hands, and the warehouse ends up in a new condition, partly because of their choice and partly because of who happened to trade with them.

That is the whole structure. A situation you can observe, a choice you control, an immediate payoff, and a new situation that follows partly from you and partly from chance. Everything below is just careful notation for those four things.

The five ingredients

An MDP is the tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$:

• $\mathcal{S}$, the set of states — every situation the agent might find itself in.
• $\mathcal{A}$, the set of actions — everything it may choose to do.
• $P(s' \mid s, a)$, the transition probabilities — given that you are in state $s$ and take action $a$, the chance of landing in state $s'$ next.
• $R(s, a)$, the reward — the immediate payoff for that choice.
• $\gamma$, the discount factor, a number between 0 and 1 saying how much less a reward is worth for arriving one step later.

The defining assumption is the Markov property: $P$ depends on the current state and action only, not on how you got there. In words, the state is a sufficient summary of the past. If you know where you are now, the history adds nothing.

A policy $\pi(a \mid s)$ is a rule for choosing actions — for each state, which action, or which distribution over actions. Solving an MDP means finding the policy that earns the most over time.

Return: adding up the future

You do not maximise the next reward, you maximise the whole stream. The return from time $t$ is

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1}.$$

In words: add up every future reward, shrinking each one by an extra factor of $\gamma$ for every step you have to wait. The value of a state under a policy is the average return you expect starting there:

$$v_\pi(s) = \mathbb{E}_\pi \left[ G_t \mid S_t = s \right].$$

In words: if I were dropped into state $s$ and followed policy $\pi$ forever, what would my discounted total come to on average?

Worked example: computing one return

An agent holds a position over five steps and collects rewards $+2, +2, -3, +1, +2$, with $\gamma = 0.9$. The discount weights are $1,\ 0.9,\ 0.81,\ 0.729,\ 0.6561$, so

$$G = 2 + 0.9(2) + 0.81(-3) + 0.729(1) + 0.6561(2)$$ $$G = 2 + 1.80 - 2.43 + 0.729 + 1.312 = 3.41 .$$

Undiscounted, those rewards sum to $4.00$. Discounting cost $0.59$, and it did so unevenly: the early gain of $+2$ counted in full, while the later gain of $+2$ counted for only $1.31$. Notice also that the loss at step 3 was softened to $-2.43$. Discounting does not just shrink the total — it changes which parts of the future the agent cares about.

Worked example: choosing the discount factor

A constant reward of 1 per step, forever, is worth the geometric sum

$$G = 1 + \gamma + \gamma^2 + \dots = \frac{1}{1 - \gamma}.$$

So $\gamma = 0.9$ gives $10$, $\gamma = 0.99$ gives $100$, $\gamma = 0.5$ gives just $2$. That number $1/(1-\gamma)$ is the effective horizon: roughly how many steps the agent can see. Equivalently, rewards halve in importance every $\ln(0.5)/\ln(\gamma)$ steps — about 6.6 steps at $\gamma = 0.9$, but 69 steps at $\gamma = 0.99$.

Now use it. Suppose an execution agent acts once a minute and must care about the whole 390-minute trading day. You need $1/(1-\gamma) \approx 390$, so

$$\gamma \approx 1 - \frac{1}{390} = 0.9974 .$$

The default $\gamma = 0.99$ gives a horizon of 100 minutes — the agent would happily dump inventory at 2pm because the closing auction is beyond its sight. The default $\gamma = 0.9$ makes it blind past ten minutes, so it learns to scalp and never learns to work an order. The discount factor is not a tuning knob, it is a statement about what the agent is trying to achieve.

What this means in practice

Framing a trading problem as an MDP is most of the work, and it is where most attempts fail:

• State design. Include everything that changes what you should do: inventory, time remaining, recent fills, a volatility estimate. Leave out anything you could not observe live.
• Action design. Prefer a small set of meaningful choices — post at the touch, post one tick behind, cross the spread, do nothing — over a continuous size in shares. Coarse actions learn far faster from limited data.
• Reward design. Raw profit and loss is a noisy, fat-tailed signal, and an agent trained on it learns to take enormous risk for a fractionally better mean. Subtract a risk penalty and the transaction costs, and do it inside the reward rather than as a filter afterwards.

Once a problem is written as an MDP, the question becomes how to compute the value of each state and the best action in each. That is what the Bellman equations answer.