Understanding Bandits with Graph Feedback

Abstract

The bandit problem with graph feedback, proposed in [Mannor and Shamir, NeurIPS 2011], is modeled by a directed graph $G=(V,E)$ where $V$ is the collection of bandit arms, and once an arm is triggered, all its incident arms are observed. A fundamental question is how the structure of the graph affects the min-max regret. We propose the notions of the fractional weak domination number ${\delta }^{\ast }$ and the $k$-packing independence number capturing upper bound and lower bound for the regret respectively. We show that the two notions are inherently connected via aligning them with the linear program of the weakly dominating set and its dual -- the fractional vertex packing set respectively. Based on this connection, we utilize the strong duality theorem to prove a general regret upper bound $O\left({\left({\delta }^{\ast }\log |V|\right)}^{\frac{1}{3}}{T}^{\frac{2}{3}}\right)$ and a lower bound $\Omega \left({\left({\delta }^{\ast }/\alpha \right)}^{\frac{1}{3}}{T}^{\frac{2}{3}}\right)$ where $\alpha$ is the integrality gap of the dual linear program. Therefore, our bounds are tight up to a ${\left(\log |V|\right)}^{\frac{1}{3}}$ factor on graphs with bounded integrality gap for the vertex packing problem including trees and graphs with bounded degree. Moreover, we show that for several special families of graphs, we can get rid of the ${\left(\log |V|\right)}^{\frac{1}{3}}$ factor and establish optimal regret.

arXiv commentTo be published in NeurIPS'21

References in corpus (7)

• Efficient learning by implicit exploration in bandit problems with side observations
• Online Learning: A Modern Introduction Using Convex Optimization
• From Bandits to Experts: A Tale of Domination and Independence
• Online Learning with Feedback Graphs Without the Graphs
• Information Directed Sampling for Stochastic Bandits with Graph Feedback
• Connections Between Mirror Descent, Thompson Sampling and the Information Ratio
• Learning the Experts for Online Sequence Prediction