mlsanityData to 14 Oct 2026

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

arXiv 2306.09048 ↗First posted 15 Jun 2023cs.LG stat.MLcited by 8

Not on the map. Why?

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.

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

24 of 54 references.

References · 24

  1. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,920
  2. 2014Convex Optimization: Algorithms and Complexitycited by 575
  3. 2019Introduction to Multi-Armed Banditscited by 481
  4. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  5. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  6. 2016Optimal Best Arm Identification with Fixed Confidencecited by 239
  7. 2013lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Banditscited by 149
  8. 2016Simple Bayesian Algorithms for Best Arm Identificationcited by 117
  9. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 79
  10. 2018Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervalscited by 76
  11. 2019Non-Asymptotic Pure Exploration by Solving Gamescited by 63
  12. 2013Thompson Sampling for 1-Dimensional Exponential Family Banditscited by 42
12 more
  1. 2022Top Two Algorithms Revisitedcited by 34
  2. 2016Towards Instance Optimal Bounds for Best Arm Identificationcited by 30
  3. 2017Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selectioncited by 28
  4. 2021On the Optimality of Batch Policy Optimization Algorithmscited by 28
  5. 2021Regret Minimization in Heavy-Tailed Banditscited by 25
  6. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalizationcited by 25
  7. 2019Optimal Exploitation of Clustering and History Information in Multi-Armed Banditcited by 14
  8. 2019Online Pricing with Offline Data: Phase Transition and Inverse Square Lawcited by 13
  9. 2022Artificial Replay: A Meta-Algorithm for Harnessing Historical Data in Banditscited by 13
  10. 2022On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Banditscited by 8
  11. 2020Combining Offline Causal Inference and Online Bandit Learning for Data Driven Decisioncited by 5
  12. 2014Unimodal Bandits without Smoothnesscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 1; 2025: 4; 2026: 2.

8 papers.

  1. 2024Online Bandit Learning with Offline Preference Data for Improved RLHFcited by 6
  2. 2025Best Arm Identification with Possibly Biased Offline Datacited by 5
  3. 2023Optimal Best Arm Identification with Fixed Confidence in Restless Banditscited by 3
  4. 2025Augmenting Online RL with Offline Data is All You Need: A Unified Hybrid RL Algorithm Design and Analysiscited by 3
  5. 2025Bayesian Decision Making around Expertscited by 0
  6. 2025Multi-Objective Reward and Preference Optimization: Theory and Algorithmscited by 0
  7. 2026Offline-Online Reinforcement Learning for Linear Mixture MDPscited by 0
  8. 2026DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedbackcited by 0