# Bridging the gap between regret minimization and best arm identification, with application to A/B tests

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2018.

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

- [Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits](https://mlsanity.com/paper/2110.08627/) (2021)
- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms](https://mlsanity.com/paper/2309.00591/) (2023)
- [Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits](https://mlsanity.com/paper/2306.02208/) (2023)
- [Adaptive Experimentation in the Presence of Exogenous Nonstationary Variation](https://mlsanity.com/paper/2202.09036/) (2022)
- [Adaptive Experimental Design and Counterfactual Inference](https://mlsanity.com/paper/2210.14369/) (2022)
- [Learning the Pareto Front Using Bootstrapped Observation Samples](https://mlsanity.com/paper/2306.00096/) (2023)
- [Best Arm Identification with Minimal Regret](https://mlsanity.com/paper/2409.18909/) (2024)
- [Reward Maximization for Pure Exploration: Minimax Optimal Good Arm Identification for Nonparametric Multi-Armed Bandits](https://mlsanity.com/paper/2410.15564/) (2024)
- [Best of Three Worlds: Adaptive Experimentation for Digital Marketing in Practice](https://mlsanity.com/paper/2402.10870/) (2024)
- [Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysis](https://mlsanity.com/paper/2406.07455/) (2024)
- [Balancing Performance and Costs in Best Arm Identification](https://mlsanity.com/paper/2505.20583/) (2025)
- [Learning Peer Influence Probabilities with Linear Contextual Bandits](https://mlsanity.com/paper/2510.19119/) (2025)
- [Beyond the Lower Bound: Bridging Regret Minimization and Best Arm Identification in Lexicographic Bandits](https://mlsanity.com/paper/2511.05802/) (2025)
- [UCB for Large-Scale Pure Exploration: Beyond Sub-Gaussianity](https://mlsanity.com/paper/2511.22273/) (2025)
- [Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits](https://mlsanity.com/paper/2606.01799/) (2026)
- [MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits](https://mlsanity.com/paper/2607.14706/) (2026)
- [Experimentation and Commitment under Reward Shifts](https://mlsanity.com/paper/2607.23432/) (2026)

## Abstract (arXiv)

State of the art online learning procedures focus either on selecting the best alternative ("best arm identification") or on minimizing the cost (the "regret"). We merge these two objectives by providing the theoretical analysis of cost minimizing algorithms that are also delta-PAC (with a proven guaranteed bound on the decision time), hence fulfilling at the same time regret minimization and best arm identification. This analysis sheds light on the common observation that ill-callibrated UCB-algorithms minimize regret while still identifying quickly the best arm. We also extend these results to the non-iid case faced by many practitioners. This provides a technique to make cost versus decision time compromise when doing adaptive tests with applications ranging from website A/B testing to clinical trials.