# Anytime-valid Optimal Policy Identification

arXiv: https://arxiv.org/abs/2606.17515 · HTML: https://mlsanity.com/paper/2606.17515/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 31 references that are in the map.
- First posted on arXiv 16 Jun 2026.

## Builds on (most cited first, 21 of 21)

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Optimal and Adaptive Off-policy Evaluation in Contextual Bandits](https://mlsanity.com/paper/1612.01205/) (2016)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Confidence Intervals for Policy Evaluation in Adaptive Experiments](https://mlsanity.com/paper/1911.02768/) (2019)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Statistical Inference with M-Estimators on Adaptively Collected Data](https://mlsanity.com/paper/2104.14074/) (2021)
- [Confident Off-Policy Evaluation and Selection through Self-Normalized Importance Weighting](https://mlsanity.com/paper/2006.10460/) (2020)
- [Anytime-valid off-policy inference for contextual bandits](https://mlsanity.com/paper/2210.10768/) (2022)
- [Post-Contextual-Bandit Inference](https://mlsanity.com/paper/2106.00418/) (2021)
- [Design of Experiments for Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2107.09912/) (2021)
- [Instance-optimal PAC Algorithms for Contextual Bandits](https://mlsanity.com/paper/2207.02357/) (2022)
- [Off-policy Confidence Sequences](https://mlsanity.com/paper/2102.09540/) (2021)
- [On Elimination Strategies for Bandit Fixed-Confidence Identification](https://mlsanity.com/paper/2205.10936/) (2022)
- [Anytime-Valid Linear Models and Regression Adjusted Causal Inference in Randomized Experiments](https://mlsanity.com/paper/2210.08589/) (2022)
- [Adaptive Off-Policy Inference for M-Estimators Under Model Misspecification](https://mlsanity.com/paper/2509.14218/) (2025)
- [Off-policy estimation with adaptively collected data: the power of online learning](https://mlsanity.com/paper/2411.12786/) (2024)
- [Anytime-Valid Inference in Adaptive Experiments: Covariate Adjustment and Balanced Power](https://mlsanity.com/paper/2506.20523/) (2025)

## Built on by (most cited first, 1 of 1)

- [You Don't Need To Stay in The Loop: An Agentic Robotics Loop for Robot-Policy Improvement](https://mlsanity.com/paper/2608.07555/) (2026)

## Abstract (arXiv)

We develop an anytime-valid framework for optimal policy identification from logged contextual bandit data. In many applied settings, the analyst wants to select the optimal policy from a candidate policy class Pi, but data are generated by an externally determined logging policy that they do not control. The analyst may also wish to monitor evidence continuously, stopping once the optimal policy is clear rather than committing to a fixed sample size in advance. This paper addresses these challenges by constructing a time-indexed set St that retains the true optimal policy set uniformly over time with high probability. The resulting procedure allows the analyst to monitor policy values, eliminate clearly suboptimal policies, and stop at data-dependent times without invalidating inference. When the optimal policy is unique, we define a stopping time for its identification and derive a sample-complexity bound scaling as O!left(fraclog |Pi|+loglog(1/Deltamin)Deltamin2right), where Deltamin is the gap between the best and second-best policy values. Simulations demonstrate that the anytime-valid approach can yield substantial sample savings relative to fixed-N designs. An application to a large adaptive experiment on reducing misinformation online illustrates how the method provides a dynamic view as evidence on the optimal policy accumulates.