Tail-Influence Sampling for CVaR Policy Evaluation

Tail-Influence Sampling for CVaR Policy Evaluation. By Pauline Bourigault and four others, from Imperial College London, Huawei Noah's Ark Lab, and one other institution. Published on the twenty-ninth of September. Its code repository is worked out: about one hundred source files, with a readme and a licence.

Two policies can have similar average returns and still differ sharply in how often they fail badly. The measure that captures this is the lower-tail conditional value-at-risk, CVaR, and estimating it accurately can take many costly rollouts. The setting here is a stochastic workflow whose conditional components can be queried separately. Given a fixed evaluation budget and a fixed policy, the question is how to spend those queries so the policy's CVaR is estimated as accurately as possible.

The central object is a tail influence, derived for each conditional law that can be queried. It aggregates how uncertainty in that component affects CVaR across every Bellman reuse. The variance of this influence gives two things at once: the efficiency bound for a fixed design, and the oracle Neyman allocation, meaning the ideal split of the budget.

The oracle needs quantities nobody knows in advance, so Tail-Influence Sampling, TIS, estimates the influence scales from a pilot model, then sends fresh queries toward the kernels that matter most for the tail. A pilot can underallocate, so there is also a visitation-anchored variant that guards against that.

The guarantees follow. TIS attains the oracle asymptotic variance and the first-order mean squared error, with the pilot's own cost counted. The anchored variant comes within a factor of two of the oracle. The authors also characterize an exact-grid regime in which the allocation that is optimal for the tail and the one optimal for the mean turn out to be the same.

Those guarantees hold under two conditions: fixed dimension, and a positive quantile margin. The anchored variant's factor of two is the price of protection when the pilot model misjudges where queries are needed.

Empirically, on CliffWalking, TIS cuts mean squared error by forty-one percent against learned occupancy, and by seventy-six percent against complete rollouts, at the same charged transition budget. In frozen language-model review workflows, anchored TIS beats an equally regularized mean-influence blend in twenty-three of twenty-four MMLU-Pro settings. On six-call FinQA reviews it reaches between two point four and three point four times lower mean squared error than rollouts.

The shape of the idea is simple to carry away. When you care about rare failures, the budget should go where uncertainty moves the tail, not where it moves the average, and the tail influence is the quantity that says where that is.