# Optimal Best-Arm Identification in Bandits with Access to Offline Data

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 54 references that are in the map.
- First posted on arXiv 15 Jun 2023.

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

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [Towards Instance Optimal Bounds for Best Arm Identification](https://mlsanity.com/paper/1608.06031/) (2016)
- [Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection](https://mlsanity.com/paper/1702.03605/) (2017)
- [On the Optimality of Batch Policy Optimization Algorithms](https://mlsanity.com/paper/2104.02293/) (2021)
- [Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2102.03734/) (2021)
- [Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization](https://mlsanity.com/paper/2111.13807/) (2021)
- [Optimal Exploitation of Clustering and History Information in Multi-Armed Bandit](https://mlsanity.com/paper/1906.03979/) (2019)
- [Online Pricing with Offline Data: Phase Transition and Inverse Square Law](https://mlsanity.com/paper/1910.08693/) (2019)
- [Artificial Replay: A Meta-Algorithm for Harnessing Historical Data in Bandits](https://mlsanity.com/paper/2210.00025/) (2022)
- [On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits](https://mlsanity.com/paper/2210.00895/) (2022)
- [Combining Offline Causal Inference and Online Bandit Learning for Data Driven Decision](https://mlsanity.com/paper/2001.05699/) (2020)
- [Unimodal Bandits without Smoothness](https://mlsanity.com/paper/1406.7447/) (2014)

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

- [Online Bandit Learning with Offline Preference Data for Improved RLHF](https://mlsanity.com/paper/2406.09574/) (2024)
- [Best Arm Identification with Possibly Biased Offline Data](https://mlsanity.com/paper/2505.23165/) (2025)
- [Optimal Best Arm Identification with Fixed Confidence in Restless Bandits](https://mlsanity.com/paper/2310.13393/) (2023)
- [Augmenting Online RL with Offline Data is All You Need: A Unified Hybrid RL Algorithm Design and Analysis](https://mlsanity.com/paper/2505.13768/) (2025)
- [Bayesian Decision Making around Experts](https://mlsanity.com/paper/2510.08113/) (2025)
- [Multi-Objective Reward and Preference Optimization: Theory and Algorithms](https://mlsanity.com/paper/2512.10601/) (2025)
- [Offline-Online Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2604.11994/) (2026)
- [DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedback](https://mlsanity.com/paper/2610.12960/) (2026)

## Abstract (arXiv)

Learning paradigms based purely on offline data as well as those based solely on sequential online learning have been well-studied in the literature. In this paper, we consider combining offline data with online learning, an area less studied but of obvious practical importance. We consider the stochastic K-armed bandit problem, where our goal is to identify the arm with the highest mean in the presence of relevant offline data, with confidence 1-δ. We conduct a lower bound analysis on policies that provide such 1-δ probabilistic correctness guarantees. We develop algorithms that match the lower bound on sample complexity when δ is small. Our algorithms are computationally efficient with an average per-sample acquisition cost of tildeO(K), and rely on a careful characterization of the optimality conditions of the lower bound problem.