Grading a Policy That Was Never Run
Credit: Tesfu Assefa

Grading a Policy That Was Never Run

You cannot test-drive a new policy on patients or customers just to see what happens, so reinforcement learning tries to grade it from the records of a policy already running. The two standard methods each fail, one by hiding its errors and the other by drowning in noise. Nan Jiang and Lihong Li built an estimator that escapes both failures, then proved that part of the error left over cannot be removed at all.
Nov 20, 2026
7 min read
0.00 MPXR

A hospital cannot try out a new treatment schedule on patients just to see what happens. A marketing team cannot fire off a million emails under an untested strategy and check the damage afterwards. Yet somebody has to attach a number to each of these decisions before anyone commits. Reinforcement learning calls this off-policy value evaluation: estimating how well a new policy would perform using only the records of what a different policy already did. The two standard approaches each fail in a specific way, one by hiding its errors and the other by drowning in noise. Nan Jiang of the University of Michigan and Lihong Li of Microsoft Research built an estimator that escapes both failures, then proved that some of the error left over cannot be removed at all.

Two ways to be wrong

Your data came from a behavior policy, the system already running. You want to score a target policy, the candidate you cannot afford to deploy. The difficulty is mismatch: the new policy would have acted differently and visited different situations, and the further into a sequence you look, the more the two histories diverge.

One approach fits a model of the world from the data, then evaluates the new policy inside that model. Real problems have huge state spaces, so the model must generalize, and generalization introduces error whenever the true dynamics fall outside the function class you chose. The researchers make a sharp point about this: you generally cannot measure that error from the data. An estimate that might be badly wrong in an unmeasurable direction is a poor basis for changing a treatment protocol.

The alternative, importance sampling, reweights the logged sequences. For each action you compute the ratio of the probability the new policy would have chosen it to the probability the old one did, then multiply those ratios along the sequence. The result is unbiased and needs no model of the world at all. The catch is arithmetic: multiplying ratios step after step produces numbers that swing wildly, and the variance grows exponentially with the length of the sequence. Over a hundred steps, individual estimates land nowhere near the truth.

One method is quiet and possibly wrong; the other is honest and too noisy to act on.

Credit: Tesfu Assefa
Credit: Tesfu Assefa

A one-step trick, applied a hundred times

The doubly robust estimator already existed for contextual bandits, the stripped-down version of the problem where an agent sees one situation, acts once, and collects one reward with no future to consider. Dudík, Langford, and Li introduced it in 2011. Start from a model's prediction, then correct it using the importance ratio applied to the gap between the observed reward and the predicted one. Good model, small correction, low variance. Bad model, and the correction absorbs the gap while the estimate stays unbiased. The name refers to that pair of chances.

Extending this to sequential problems needed one observation, and I find it the most satisfying moment in the paper. Step-wise importance sampling can be rewritten as a recursion, each step's estimate depending on the next. Written that way, every time step looks like a bandit problem: the situation is the context, the action is the action, and the reward is the immediate reward plus whatever the recursion returns from the future. That quantity has a known expected value, the Q-function, which measures how good an action is in a given situation under the policy being evaluated.

So the researchers apply the bandit correction at every step. Nothing in the derivation is complicated, and the consequence is striking. Importance sampling turns out to be their estimator's special case, the one where you supply an estimated Q-function of zero. Anyone using plain importance sampling is already running the doubly robust estimator with the worst model available.

Where the variance goes

The theoretical analysis splits the total variance into pieces, and the quality of the estimated Q-function enters only one of them, as the gap between estimate and truth. Better model, smaller gap, less variance, with unbiasedness holding throughout.

The honest part comes next. Three kinds of randomness feed the total: which action the old policy happened to take, how noisy the rewards are, and how the world transitions between states. The correction touches only the first.

Rather than bury this, the researchers went after it. Using the Cramér-Rao bound, a classical result that sets a floor on the variance of any unbiased estimator, they show that for a broad class of problems the floor equals exactly what their method achieves with a perfect Q-function. The leftover variance belongs to the problem, not to the method. Removing it demands extra assumptions about the world, and every assumption made during evaluation costs some of the credibility you were trying to buy. This part of the work is pure theoretical analysis, with no experiment behind it.

Three problems, thousands of runs

The experiments cover two benchmarks and one real dataset: mountain car, a sailing task on a ten-by-ten grid with shifting wind, and roughly 3,700 recorded email exchanges with potential donors drawn from the KDD Cup 1998 data.

Across thousands of repeated runs, the new estimator beat both importance sampling and the weighted variant most practitioners prefer. On the donation data, a low-bias version of it won in every configuration tested, beating the importance sampling family when the two policies differ sharply and beating the model-based estimator when they resemble each other. That is what the theory predicts, and seeing the pattern hold on real records rather than a benchmark is what makes the paper convincing.

[INSERT FIGURE 3 HERE — the donation dataset bar chart comparing all five estimators]

Image credit: Jiang, Nan, and Lihong Li. "Doubly Robust Off-policy Value Evaluation for Reinforcement Learning." arXiv.org, May 26, 2016. https://arxiv.org/abs/1511.03722

A final experiment used the estimator to choose policies rather than merely score them. Substituting it for importance sampling, a cautious agent accepted good candidates far more readily, because importance sampling is too noisy to endorse anything that departs much from logged behavior. The researchers then generated deliberately bad candidates to test whether this readiness amounted to recklessness. At matched confidence levels, it rejected them just as reliably.

Conclusion

Reinforcement learning increasingly reaches domains where experiments are expensive, dangerous, or forbidden, and there the ability to evaluate a policy from historical records decides whether the technology can be used responsibly. The problem has long forced a choice between estimates that are precise but quietly biased and estimates that are honest but too noisy to act on. Neither serves a clinician weighing a treatment schedule against the one already in use.

This study presents an estimator that dissolves the trade-off by pairing a learned model with a statistical correction, so that a good model buys precision while a bad one costs precision and never accuracy. The recommendation follows directly: teams relying on importance sampling should treat this as a drop-in replacement, since what they run today is the same estimator with the least informative model possible.

The lower-bound result deserves the last word. By proving that part of the remaining uncertainty belongs to the problem itself, the researchers marked the limit of what any honest estimator can reach, which tells the field where to stop optimizing and where to look instead. What remains is whether these methods survive contact with the messy records that hospitals and public agencies actually keep.

About the Writer

More from Mindplex

Keep reading

Three more ideas worth your time.

Browse Community

Discussion

Join the discussion

Sign in to share a response with the community.

Type @ to mention someone Type / or use + to add a block Highlight text, then choose Link
Loading editor

Comments cannot be edited after posting because they become part of the reputation record. Give yours a quick review first.