Graph Feedback Bandits on Similar Arms: With and Without Graph Structures
Preprint
Abstract
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 \emph{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.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Optimal Best Arm Identification With Fixed Confidence in Restless BanditsIEEE Transactions on Information Theory, 2024
- Best Arm Identification in Restless Markov Multi-Armed BanditsIEEE Transactions on Information Theory, 2022
- Ballooning multi-armed banditsArtificial Intelligence, 2021
- AdaptiveBandit: A Multi-armed Bandit Framework for Adaptive Sampling in Molecular SimulationsJournal of Chemical Theory and Computation, 2020
- Nonstochastic Multi-Armed Bandits with Graph-Structured FeedbackSIAM Journal on Computing, 2017
- Online Learning of Rested and Restless BanditsIEEE Transactions on Information Theory, 2012
- UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problemPeriodica Mathematica Hungarica, 2010
- The Nonstochastic Multiarmed Bandit ProblemSIAM Journal on Computing, 2002
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985
- On domination and independent domination numbers of a graphDiscrete Mathematics, 1978