Skip to content

Tail-Influence Sampling for CVaR Policy Evaluation

Sep 2026 · 1 citation · 41 references
Computer Science

TL;DR

A tail influence for each queryable conditional law that aggregates how its uncertainty affects CVaR across every Bellman reuse is derived, and an exact-grid regime in which tail- and mean-optimal allocations coincide is characterized.

Abstract

Policies with similar mean returns can differ sharply in rare failures, yet estimating lower-tail conditional value-at-risk (CVaR) accurately can require many costly rollouts. When different conditional components of a stochastic workflow can be queried separately, we ask how to allocate a fixed evaluation budget to estimate a fixed policy's CVaR most accurately. We derive a tail influence for each queryable conditional law that aggregates how its uncertainty affects CVaR across every Bellman reuse. Its variance yields the fixed-design efficiency bound and the oracle Neyman allocation. Tail-Influence Sampling (TIS) estimates these influence scales from a pilot model and reallocates fresh queries toward kernels that matter most for the tail; a visitation-anchored variant protects against pilot underallocation. Under fixed dimension and a positive quantile margin, TIS attains oracle asymptotic variance and first-order MSE including pilot cost, while the anchored variant is within a factor two of the oracle. We also characterize an exact-grid regime in which tail- and mean-optimal allocations coincide. On CliffWalking, TIS reduces MSE by 41% versus learned occupancy and 76% versus complete rollouts at the same charged transition budget. In frozen language-model review workflows, anchored TIS beats an equally regularized mean-influence blend in 23 of 24 MMLU-Pro settings and reaches 2.4-3.4$\times$ lower MSE than rollouts on six-call FinQA reviews.

View source

Similar papers

#artificial intelligence Preprint Sep 2026

Speculative Evaluation of Stochastic LLMs

Real-generation experiments that account for the pilot synchronization barrier show that HBN-async mitigates its overhead, helping translate statistical efficiency into practical evaluation benefits, and outperforming hindsight-tuned empirical and independent Bayesian baselines.

Qian-Li Shen, Xiang Li, Ruo-Meng Ding et al. · 0 citations
#machine learning Preprint Oct 2026

Variance-Optimal Off-Policy Evaluation with Conjunct Effect Modeling

Off-policy evaluation (OPE) for contextual bandit policies becomes challenging when action-level importance weighting incurs excessive variance. Doubly robust (DR) estimation remains unbiased under common support but retains these high-variance action-level weights. A prior estimator, Off-policy evaluation with Conjunc...

Nicolò Felicioni, Michael Benigni, Maurizio Ferrari Dacrema et al. · 0 citations
#machine learning Preprint Oct 2026

Metropolis-Hastings Dominates Importance Resampling for Policy Composition

Post-training a large language model (LLM) often requires exploring trade-offs between multiple rewards, but retraining for each trade-off is expensive. Decoding-time policy composition allows these trade-offs to be adjusted by combining reward-specific policies at inference time. This composition targets a weighted pr...

Alexey Kurennoy, R. Yarullin, Fergal Reid · 0 citations
Book Open access Sep 2026

Generalized Position-Based Model: Rethinking Position Weights in Ranking Off-Policy Evaluation

Generalized PBM is introduced, an estimator that learns position-specific weights by minimizing an approximate upper bound on the estimation error, which retains the unbiasedness guarantees of INTERPOL while significantly simplifying its hyperparameter selection.

Norman Knyazev, Vito Bellini, H. Yurtseven et al. · 0 citations
Sep 2026

Contextual Conditional Value-at-Risk: Estimation and Optimization

This work exploits the Rockafellar–Uryasev representation to formulate both contextual CVaR estimation and optimization as optimization problems involving conditional expectations, and develops a unified data-driven predict-then-optimize framework.

Heng Luo, Ni-Fei Lin, L. J. Hong · 0 citations
#artificial intelligence Preprint Sep 2026

Risk-Aware Adaptive Evaluation: Finding High-Impact Failures Under Limited Budgets

Evaluating interactive agents is expensive. Agent behavior is stochastic, so reliability must be measured over repeated trials, but failures are rare and differ widely in how much they matter. Standard benchmarks spend this budget uniformly: a read-only lookup is sampled as often as an irreversible payment action. We i...

Priyanath Maji, S. Chowdhury · 0 citations

Related blog posts

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.