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.
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
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
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
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.· Proceedings of the 20th ACM...· 0 citations
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· Asia-Pacific Journal of Oper...· 0 citations
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· microsoft.comNov 16, 2026
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.
MIT News · Artificial Intelligence· news.mit.eduNov 13, 2026