Certifying reliable upper tail estimates from bandit data under policy reuse
Coverage Cliffs in Off-Policy Quantile Certification
Machine Learning
Summary
Sometimes when computers pick policies based on past decisions, it's hard to say how good the worst outcomes might be. The authors study how to safely estimate upper bounds on bad outcomes (tails) when using logged data from past decision-making. They show a new method called TailCert that gives confidence guarantees even when picking policies from the same data. Their math explains how much data is needed depending on the policy search and uncertainty, and they demonstrate issues with naive reuse and how to manage them.
What this means in practice
- •For online advertising teams: Estimate safe worst-case performance of ad-targeting policies selected from logged interaction data.
- •For automated trading teams: Certify upper quantile risk of trading strategies chosen from historical market feedback data.
Authors
Pauline Bourigault, Emmanuelle Bourigault
Abstract
We study when logged contextual-bandit data can certify an upper tail quantile for a policy selected from the same sample. We construct a PAC-Bayes Bernstein lower-confidence envelope for the target cumulative distribution function (CDF), simultaneous over a predeclared threshold grid and all data-dependent posteriors. The resulting procedure, TailCert, uses the envelope's first crossing of level p to return an atom-safe upper confidence bound on the selected posterior's pooled p-quantile (or inconclusive). It can also be used to select a policy under a certified tail constraint. The concentration ingredients are standard; the main theoretical contribution is a matched finite-class certification boundary comparing full logs with their joint weighted CDF indicators at a fixed threshold. On an explicit rare-action class, the required sample size grows linearly with the overlap factor W, logarithmically with policy-search and confidence complexity, and quadratically with the inverse CDF safety margin; the upper and lower bounds agree up to constants in the stated regime. On this class, the CDF reduction hides which actions exceeded the budget; retaining action counts restores the full-log rate. Simulations verify the predicted search-complexity shift, winner's-curse failure of naive reuse, and the power cost of splitting.