Letting the Machine Learn to Trade: Nevmyvaka, Feng and Kearns on Reinforcement Learning for Execution

The classical approach to optimal execution goes like this. Write down a model of the market. Assume prices are a random walk. Assume impact is linear, or a square root. Assume liquidity refills at some rate. Then solve the resulting equations and out pops an optimal trading schedule.

The trouble is obvious. Your answer is only as good as your assumptions, and the assumptions are, frankly, made up. Real order books do not behave like a tidy set of differential equations.

Yuriy Nevmyvaka, Yi Feng and Michael Kearns asked a different question: what if we do not write down a model at all, and instead let an algorithm learn to trade by trial and error against the real historical order book?

The problem: your model of the market is wrong

Every assumption in the classical execution literature is a simplification that somebody knows to be false.

• Prices are not a random walk at short horizons, they have structure.
• Impact is not linear, and probably not exactly a square root either.
• The order book does not refill at a constant exponential rate.
• Liquidity depends on the time of day, on volatility, on what just happened.

You could try to patch each of these, but every patch makes the model less tractable, and eventually you cannot solve it anyway. There is a ceiling on how realistic a model can be while still being solvable.

Reinforcement learning offers a way around the ceiling. You do not need a solvable model. You need an environment you can practise in, and a way to measure whether you did well.

The key idea via analogy: learning to drive by driving

There are two ways to learn to drive.

The first is to derive the physics. Model the friction of the tyres, the torque of the engine, the mass of the car, and compute the optimal steering input. It works beautifully if your model of the car is right, and it fails badly if it is not.

The second is to get in the car and drive, badly at first, and pay attention to what happens. Turn the wheel too hard, feel it skid, do less next time. You never write down a single equation. You learn a policy: given what I see right now, what should I do? After enough practice, you drive well, and you drive well precisely because you learned against the real car rather than a model of it.

The second way is reinforcement learning, and that is what the authors do. The setup:

• The goal. You must buy a fixed number of shares within a fixed time. That is non-negotiable, exactly as in the classical problem.
• The state. What the algorithm can see when it makes a decision: how many shares remain, how much time is left, and features of the current order book such as the spread, the depth, and recent price movement.
• The action. How aggressively to price the order right now. Post passively and wait, or price it aggressively to get filled.
• The reward. How good the execution price was. Simple, and it is the thing you actually care about.

They then train the algorithm against a year and a half of millisecond-resolution NASDAQ limit order book data, which for 2006 was a genuinely serious undertaking. The algorithm plays the execution game over and over against real historical books, and learns a policy: a mapping from what it sees to what it should do.

The clever engineering contribution is a factorisation of the state space. The naive way of doing this blows up: the number of possible combinations of remaining shares, remaining time, spread, depth and price history is astronomically large, and you would never have enough data to learn anything. The authors exploit the structure of the problem, in particular the fact that a small order's own impact is limited, to break the state space into manageable pieces that can actually be learned from data.

And it works. The learned policies substantially outperform the standard simple benchmarks that execution desks use, the fixed and naive submission strategies that ignore market conditions. The algorithm learns, without being told, to trade differently depending on what the book looks like.

Why it mattered

• It was the first serious, large-scale application of reinforcement learning to execution. Nearly every machine-learning-for-execution paper written since cites this one. It established the problem framing, the state and action design, and the benchmarks.
• The framing is genuinely apt. Execution is a sequential decision problem with a clear objective, a well-defined state, and abundant data. That is exactly the shape of problem reinforcement learning is good at, and this paper was early to see it.
• It sidesteps model risk entirely. By learning from data rather than from assumptions, the approach avoids the entire question of whether impact is linear or square-root. It does not care. It just learns what happened.
• It exploits information the classical models throw away. Almgren-Chriss style models schedule your trading using little more than a clock. This one can look at the current spread, the current depth, and the recent price action and react to them. That is a strictly richer information set, and the improvement over the naive benchmarks shows it is worth something.
• The state-space factorisation was a real contribution. Making the learning problem tractable is the difference between an idea and a result.

The honest limitations

• Backtesting execution is fundamentally treacherous. The historical order book you are training against did not contain you. In reality, your orders would have consumed liquidity, moved prices, and changed the behaviour of everyone else. Replaying history while pretending you had no effect on it systematically flatters any execution strategy. The authors work with small orders partly to limit this, but the problem never fully goes away.
• It learns yesterday's market. A policy trained on 2004 order books is optimised for 2004 market structure and 2004 participants. Markets change, sometimes abruptly. A learned policy has no way of knowing when the world it learned has stopped existing.
• The policy is opaque. Almgren-Chriss gives you a formula you can reason about and defend to a risk committee. A learned policy gives you a lookup table. When it does something surprising, you have no principled way to say whether it is being clever or broken.
• It handles small orders, not the ones that matter most. The approach works best where your own impact is limited. The genuinely hard execution problems, the ones involving large fractions of daily volume, are exactly the ones where the no-impact backtesting assumption breaks down worst.
• Reward design is subtle. Optimising for average execution price is not the same as optimising risk-adjusted execution, and a policy trained on the former may take risks a trader would not accept.

The one-line takeaway

Nevmyvaka, Feng and Kearns showed that instead of assuming a model of the market and solving it, you can let an algorithm learn to execute by trial and error against real historical order book data, and that the resulting policies, which react to the live state of the book rather than just to the clock, beat the naive strategies that desks were actually using.