mlsanityData to 14 Oct 2026

Graph Feedback Bandits on Similar Arms: With and Without Graph Structures

arXiv 2501.14314 ↗First posted 24 Jan 2025cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the stochastic multi-armed bandit problem with graph feedback. Motivated by applications in clinical trials and recommendation systems, we assume that two arms are connected if and only if they are similar (i.e., their means are close to each other). We establish a regret lower bound for this problem under the novel feedback structure and introduce two upper confidence bound (UCB)-based algorithms: Double-UCB, which has problem-independent regret upper bounds, and Conservative-UCB, which has problem-dependent upper bounds. Leveraging the similarity structure, we also explore a scenario where the number of arms increases over time (referred to as the ballooning setting). Practical applications of this scenario include Q&A platforms (e.g., Reddit, Stack Overflow, Quora) and product reviews on platforms like Amazon and Flipkart, where answers (or reviews) continuously appear, and the goal is to display the best ones at the top. We extend these two UCB-based algorithms to the ballooning setting. Under mild assumptions, we provide regret upper bounds for both algorithms and discuss their sub-linearity. Furthermore, we propose a new version of the corresponding algorithms that do not rely on prior knowledge of the graph's structural information and provide regret upper bounds. Finally, we conduct experiments to validate the theoretical results.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 12 of its 28 references that are in the map. First posted on arXiv 24 Jan 2025.

Builds on

12 of 28 references.

References · 12

  1. 2015Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challengescited by 114
  2. 2014Online Clustering of Banditscited by 102
  3. 2014Nonstochastic Multi-Armed Bandits with Graph-Structured Feedbackcited by 61
  4. 2019Multi-Armed Bandits with Correlated Armscited by 34
  5. 2016Online Learning with Feedback Graphs Without the Graphscited by 27
  6. 2019Feedback graph regret bounds for Thompson Sampling and UCBcited by 17
  7. 2022Optimal Clustering with Bandit Feedbackcited by 15
  8. 2022Learning on the Edge: Online Learning with Stochastic Feedback Graphscited by 12
  9. 2017Reward Maximization Under Uncertainty: Leveraging Side-Observations on Networkscited by 8
  10. 2020Ballooning Multi-Armed Banditscited by 7
  11. 2022Best Arm Identification in Restless Markov Multi-Armed Banditscited by 3
  12. 2023Optimal Best Arm Identification with Fixed Confidence in Restless Banditscited by 3

Built on by

Cited by year (2026 to 14 Oct)

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

3 papers.

  1. 2025KABB: Knowledge-Aware Bayesian Bandits for Dynamic Expert Coordination in Multi-Agent Systemscited by 37
  2. 2026Multi-Armed Bandits with Arriving Arms: Sequential Screening, Dynamic Regret, and Sublinear Guaranteescited by 0
  3. 2026Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspacescited by 0