mlsanityData to 14 Oct 2026

Pure Exploration with Feedback Graphs

arXiv 2503.07824 ↗First posted 10 Mar 2025stat.ML cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

We study the sample complexity of pure exploration in an online learning problem with a feedback graph. This graph dictates the feedback available to the learner, covering scenarios between full-information, pure bandit feedback, and settings with no feedback on the chosen action. While variants of this problem have been investigated for regret minimization, no prior work has addressed the pure exploration setting, which is the focus of our study. We derive an instance-specific lower bound on the sample complexity of learning the best action with fixed confidence, even when the feedback graph is unknown and stochastic, and present unidentifiability results for Bernoulli rewards. Additionally, our findings reveal how the sample complexity scales with key graph-dependent quantities. Lastly, we introduce TaS-FG (Track and Stop for Feedback Graphs), an asymptotically optimal algorithm, and demonstrate its efficiency across different graph configurations.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 26 of its 64 references that are in the map. First posted on arXiv 10 Mar 2025.

Builds on

26 of 64 references.

References · 26

  1. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 641
  2. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  3. 2016Optimal Best Arm Identification with Fixed Confidencecited by 239
  4. 2015Online Learning with Feedback Graphs: Beyond Banditscited by 80
  5. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 79
  6. 2018Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervalscited by 76
  7. 2020Optimal Best-arm Identification in Linear Banditscited by 71
  8. 2019Pure Exploration with Multiple Correct Answerscited by 64
  9. 2019Non-Asymptotic Pure Exploration by Solving Gamescited by 63
  10. 2014Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithmscited by 60
  11. 2014Unimodal Bandits: Regret Lower Bounds and Optimal Algorithmscited by 37
  12. 2021Navigating to the Best Policy in Markov Decision Processescited by 29
14 more
  1. 2016Online Learning with Feedback Graphs Without the Graphscited by 27
  2. 2019Feedback graph regret bounds for Thompson Sampling and UCBcited by 17
  3. 2019Bandits with Feedback Graphs and Switching Costscited by 17
  4. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  5. 2021Understanding Bandits with Graph Feedbackcited by 14
  6. 2022Learning on the Edge: Online Learning with Stochastic Feedback Graphscited by 12
  7. 2023Practical Contextual Bandits with Feedback Graphscited by 11
  8. 2023On the Minimax Regret for Online Learning with Feedback Graphscited by 8
  9. 2022Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedbackcited by 6
  10. 2024Efficient Contextual Bandits with Uninformed Feedback Graphscited by 6
  11. 2022On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structurecited by 5
  12. 2023Online Learning with Feedback Graphs: The True Shape of Regretcited by 5
  13. 2024Can Probabilistic Feedback Drive User Impacts in Online Platforms?cited by 5
  14. 2022Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimalitycited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 2.

4 papers.

  1. 2025Pure Exploration with Infinite Answerscited by 1
  2. 2025Non-Asymptotic Analysis of (Sticky) Track-and-Stopcited by 1
  3. 2026Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learningcited by 1
  4. 2026ICMAPE: In-Context Multiagent Pure Explorationcited by 0