Policy Learning and Off-Policy Evaluation

A commercial risk-prediction algorithm decided which patients got extra care. Strip away the machinery and what was deployed was a policy in the strict sense. Take the context a patient record can show, return an action: enrol this person in the additional help, or do not.

The objective it was trained on was health-care costs rather than illness. That single choice is the whole of the failure. Cost is recorded automatically, arrives without a study behind it, and looks enough like need to pass unchallenged. The audit that caught it ran in Science in 2019. Ziad Obermeyer and three colleagues put the size of the gap on the record: remedying the disparity would raise the share of Black patients receiving additional help from 17.7% to 46.5%.

Their abstract closes with a claim about objectives rather than about model quality: “We suggest that the choice of convenient, seemingly effective proxies for ground truth can be an important source of algorithmic bias in many contexts.”

Read the deployed output alone and you would conclude the rule had found the patients who needed help. It had found the patients whose need had already been converted into spending. Something else shipped alongside the model: an eligibility policy. A standing answer to who is worth trying something on, written by an optimiser, never defined by the product, invisible in the one metric that approved it.

Everything else in this lesson is an attempt to catch that failure earlier. First by naming the pieces. Then by putting the missing constraints into the objective. Finally by refusing to trust an estimate the logs cannot support.

Most of the muddle here comes from letting four words slide into each other. A rule and the number it earns are different objects. So are that number and your estimate of it. That last distinction is the one the opening case never had to confront.

The Open Bandit Dataset is the rare place where all four can be pointed at separately. ZOZOTOWN ran a seven-day experiment in late November 2019. Every user impression was randomly served by one of two policies: a uniform Random policy, or Bernoulli Thompson Sampling. In the ALL campaign the Random policy logged 1,374,327 impressions at a 0.35% ± 0.010 CTR. Bernoulli Thompson Sampling logged 12,168,084 impressions at 0.50% ± 0.004. Four researchers released the logs publicly in 2021.

There are two rules. There are their two values, measured rather than argued for. The Random policy's propensities are known by construction, so its log is exactly the material an off-policy estimate of Bernoulli Thompson Sampling would have to work from. And 0.50% sits there as the answer to check against. As the authors put it: “Our dataset is unique in that it contains a set of multiple logged bandit datasets collected by running different policies on the same platform.”

All four objects were present in the Science story too. There was a rule. There was a value it appeared to improve. There was a regret nobody could quote, because no reference policy had ever been named. And the whole judgement rested on data generated by the system already running.

A policy takes the context it can see and chooses a treatment. Its value depends on far more than the effects. It depends on who actually turns up, since the covariate distribution decides which parts of the rule ever fire. It depends on what treating a person costs, on how many people you are able to treat, and on what the outcome is worth to you once you have it. Effects are one ingredient among several. They are the only ingredient a CATE model supplies.

Two CATE models can disagree about the size of the effect almost everywhere and still hand you the same rule.

That is not a curiosity. A decision consumes an ordering and a cut-off, and nothing else. The precision the model spends on magnitudes is spent somewhere the rule never looks. It is also why a better effect model can leave the shipped behaviour untouched, and why a slightly worse one can change it completely.

Off-policy evaluation is what lets you put a number on a rule before running it. You take the logging propensities — known if the old system randomised, estimated if it did not — and an outcome model. You combine them to ask what the new rule would have earned on the cases you already saw. Estimators that use both together, the doubly robust family, give you two chances to be right rather than one.

That property was proved and measured in 2011 by three researchers at Yahoo! Research. Their abstract states the guarantee in its exact shape: “We prove that this approach yields accurate value estimates when we have either a good (but not necessarily consistent) model of rewards or a good (but not necessarily consistent) model of past policy.” Read the two qualifications slowly. Either. Not necessarily consistent.

They tested the estimator on nine UCI benchmark datasets converted to bandit feedback, from glass with 214 rows and 6 classes up to letter with 20,000 rows and 26 classes. They also ran it on about 4 million user identifiers — “bcookies” — randomly selected during March 2010 at a “popular Internet portal” they declined to name. Variance came in lower than inverse propensity scoring, bias far lower than the direct method. Two chances is not an exemption. The causal assumptions behind the logs still have to hold.

Support is the hard limit. An action the logging policy almost never took cannot be evaluated reliably, however good the estimator is. There are no cases in which anyone tried it. The referral rule in the opening case never ran into this wall. It only ever proposed actions the records were full of, which is exactly why its estimated performance looked so clean.

Three things are worth checking separately, and they fail in different ways. The CATE model predicts conditional average effects; you check it against held-out outcomes. The policy rule maps context to treatment; you check it by reading it. Policy value is the expected utility under that rule; you check it against evidence. The rest of this lesson is about how thin that evidence usually is.

Maximise a single outcome with nothing else written down and you will usually get a rule you cannot use. It will score well while doing it, because the score contains only what you asked for. This is the general form of the opening failure.

The difference a written-down constraint makes has been measured. Empirical Welfare Maximization was applied to 9,223 adult observations from the National JTPA Study, where the assignment probability was a known two-thirds. Optimise the outcome alone and the EWM linear rule treats 96% of the population, for an estimated gain of $1,364 per population member. Put the programme's $774 average cost per treatment assignment into the same objective and the rule itself moves: 69% treated, $792 per population member. Kitagawa and Tetenov published that in Econometrica in 2018.

The quadrant rule moves too, and it does not move uniformly. In their words: “The EWM treatment rule that takes into account $774 treatment assignment cost has the same earnings threshold, but lowers the education threshold to 12.” The threshold that held is $19,670 of prior earnings. The education threshold fell from 15 years to 12. One constraint, entered into the objective rather than applied afterwards, redrew who was eligible along one axis and left the other alone. A post-hoc filter cannot do that.

The four below are not filters to apply after the optimiser finishes. Each one changes the answer, in the way the $774 did.

The work runs in a cycle, and the order matters more than any single stage.

You begin by defining the actions available and the utility you are trading in: what counts as a win, what a treatment costs, what abstaining is worth. Only then do you estimate the causal ingredients — effects, propensities, outcome models. With those in hand you optimise the policy, subject to the constraints, inside a class of rules you are willing to defend. You evaluate that rule off-policy against the logs, noting where the logs can support the answer and where they cannot. And you validate online, because a value computed on old data is a claim about behaviour that has not happened yet.

The last two stages have been closed end to end in public. A 2011 paper out of Yahoo! took about 40 million Front Page Today Module events, logged from a random bucket between 1 and 10 November 2009, with about 20 articles in the pool at any moment. It compared replay-based off-policy estimates against what the online serving bucket actually did. The offline estimates matched the online bucket's per-article and per-day CTRs.

The same authors measured how much the estimate wobbles between runs. On over 4,000,000 user visits from a random bucket on 1 May 2009, the ratio of run-to-run standard deviation to mean CTR was about 2.4% for ε-greedy and below 1.5% for UCB and LinUCB. Their claim for the method is deliberately narrow: “Therefore, our evaluation method provides a solution that is accurate (like bucket tests) without the cost and risk of running the policy in the real system.” Note the precondition that made it hold. The logs came from a random bucket, so the propensities were known rather than reconstructed.

Every arrow in the cycle carries an assumption worth writing down, and each stage has a point where you can stop and refuse to continue.

The team behind the referral algorithm ran the middle of this loop competently. They estimated, optimised, and reported. What they skipped was both ends. The utility was never defined beyond the costs the system already recorded, and the rule was never validated as a rule.

The exercise is to walk a set of effect estimates all the way to a decision rule that a colleague could read, question and switch off.

Write the actions and the utility down first, before any fitting. Then the objective is a decision the team made rather than a side effect of what was easy to measure. Health-care costs were easy to measure. Then fit the causal ingredients.

Choose a policy class simple enough to explain out loud. Depth-1 and depth-2 trees, or a linear rule with a threshold you can name, are policy classes you can read aloud in a meeting. Then add capacity, cost, safety and access as constraints on the optimisation itself, not as a screen applied to its output. Expect the rule to move when you do, the way the education threshold moved from 15 years to 12.

Score the result off-policy, and record two things rather than one: the value, and the contexts where the logs were too thin to support the value you just reported. Bottou and his co-authors built exactly that separation into their reporting, and the next section is about why.

What you should end up holding is not a model file. It is a rule stated in words, a list of the constraints it obeys, and an honest map of where its evidence stops.

Deploy when three things hold together. The policy improves held-out or randomised value against a strong baseline, not against a straw one. It respects the constraints and stays inside the support you established. And it stays interpretable enough that the people running the operation can steer it, override it, and explain afterwards what it did.

How much of an estimate is borrowed can be measured, and once has been. Depth-1 and depth-2 tree policies were learned on 19,170 registrants from four California counties in the GAIN welfare-to-work randomized evaluation. There were 28 covariates, and the outcome was average quarterly income in $1,000s over 9 years. Then Athey and Wager did what most evaluations cannot. They replaced the fitted propensities with the true county randomization probabilities and recomputed.

Every method's estimated improvement over random assignment falls. The AIPW depth-2 tree goes from 0.091 ± 0.026 to 0.080 ± 0.028. The IPW depth-2 tree from 0.043 ± 0.026 to 0.029 ± 0.028. The unconstrained plug-in rule from 0.077 ± 0.026 to 0.063 ± 0.028. What survived the swap was the ranking, not the level. Their 2021 Econometrica paper says so: “As seen in the second rightmost column of Table 2, our feasible evaluation discussed above gave the correct ordering for the methods, but was somewhat optimistic in terms of the quality of the learned policies.”

That is a deployment rule in one sentence. An off-policy comparison is generally good enough to choose between candidate rules, and not good enough to promise the number to anyone.

A simpler rule with slightly lower estimated value is often the better deployment. Less of its value is borrowed from extrapolation, and when it goes wrong it goes wrong somewhere visible.

If the off-policy evidence is weak, the answer is not a longer argument about estimators. Run the policy as an experiment. A randomised comparison between rules is the strongest evidence a deployment decision can have, and it is also the only thing that fills in the support the logs are missing.

That is what would have caught the referral algorithm at the start of this lesson. Not a better cost model — the cost model was predicting costs. A defined utility, a written constraint on access, and a live comparison that would have made the patients at 17.7% visible as a decision rather than as an absence.