← Back to all news
arXiv Machine Learning

Coverage Cliffs in Off-Policy Quantile Certification

The paper introduces TailCert, a method for certifying an upper tail quantile of a policy’s performance using logged contextual‑bandit data. It builds a PAC‑Bayes Bernstein lower‑confidence envelope over a threshold grid and all data‑dependent posteriors, returning an atom‑safe upper confidence bound on the selected posterior’s pooled p‑quantile. The authors provide finite‑sample guarantees, analyze sample complexity on a rare‑action class, and demonstrate the method’s effectiveness through simulations.

Related stories

arXiv AI
Sep 2

Bandits in Prod: Hyperparameter Optimization at Inference Time

The paper introduces Online Hyperparameter Optimization (OHPO), framing it as an infinitely many‑armed bandit problem over mixed and conditional search spaces. It proposes the IMABO framework, which couples any bandit policy with any oracle for proposing new configurations, and presents IMOSS—a restart‑free anytime policy with provable regret bounds. Experiments show that IMABO, combined with practical oracles such as TPE, an incumbent‑mutation oracle, and a pretrained tabular foundation model, outperforms random search across a range of settings from classical ML models to LLM‑based agents.

By Louis Abraham, Tuan-Anh Nguyen, Nicolas Devatine
llmsagentsreinforcement-learning
More like this →
arXiv Computation and Language
Sep 25

StepCOPS: Closed-Testing Lower-Tail Certificates for Language-Model Policy Selection

StepCOPS is a new method for selecting a language‑model policy from many checkpoints, prompts, and decoding rules by providing closed‑testing lower‑tail certificates. It uses an independent proposal split to nominate a lower‑tail floor for each candidate, applies exact binomial tests on a fresh certification split, and employs Holm’s step‑down procedure to certify a set of floors. In experiments across 24 configurations and 11 benchmarks, StepCOPS achieves 96.4% selected‑policy coverage, raises the certified floor by 1.5 points over prior methods, stays 0.6 points below a large‑reference jury oracle, and abstains in 2.4% of trials.

By Ibne Farabi Shihab, Sanjeda Akter, Anuj Sharma
benchmarkssafety
More like this →
arXiv Machine Learning
Oct 12

Accelerating Linear Bandits with Persistent Candidate Sets

The paper introduces Persistent Candidate LinUCB (PC‑LinUCB), a variant of the LinUCB algorithm for linear bandits that reduces per‑round score evaluations from ≥×K to ≥×(k+q) by maintaining a small set of active actions and sampling challengers from the remaining actions. It provides high‑probability regret bounds that include a standard learning term and an additive discovery cost of order ≥×((K-k)×log(K-k))/q, which does not grow with the horizon. Experiments demonstrate that PC‑LinUCB accelerates LinUCB while keeping regret comparable, and the persistent candidate approach can be applied beyond LinUCB.

By Bingkui Tong, Daria Korovaitceva, Marina Sheshukova, Sergey Samsonov, Junpei Komiyama
reinforcement-learning
More like this →
arXiv Machine Learning
Jun 2

Bandit Simulation for Average Reward Inference

arXiv:2606. 00913v1 Announce Type: cross Abstract: Multi-arm bandit algorithms are increasingly used in online platforms, clinical trials, and social science experiments, but valid statistical inference on their performance remains an open challenge.

By Samya Praharaj, Chih-Yu Chang, Koulik Khamaru, Kelly W. Zhang
reinforcement-learning
More like this →