Abstract
This paper addresses the stochastic multi-armed bandit problem with an undirected feedback graph. We devise a UCB-based algorithm, UCB-NE, to provide a problem-dependent regret bound that depends on the graph's structural complexity rather than the total number of arms.
Introduction
In a standard Multi-Armed Bandit (MAB) problem, a learner tries to find the best option by trying them out sequentially, aiming to minimize regret—the difference between the optimal reward and the actual reward received. In many real-world scenarios, such as social networks, pulling one "arm" (e.g., showing an ad to a user) provides "side observations" about its neighbors in a feedback graph.
While existing algorithms could exploit these graphs to improve the time-dependent part of regret, their initial overhead (the constant term) often scaled linearly with the total number of arms $K$. This paper introduces UCB-NE, an algorithm designed to break this "linear barrier," ensuring that performance scales with the graph's clique covering number rather than the raw number of arms.
Methodology
The authors propose two primary algorithmic contributions to leverage feedback graphs efficiently.
UCB-NE: Strategic Over-Exploration
UCB-NE (Upper Confidence Bound with extra Exploration) is a modification of the classic UCB algorithm. As detailed in Algorithm 1, it adds an extra exploration bonus based on the degree of the node in the feedback graph ($|N_i|^{1/4}$). This intentional "over-exploration" allows the mathematical analysis to "wash out" the linear dependence on the number of arms in the constant term of the regret bound.
Thompson Sampling (TS-N)
The paper also provides the first problem-dependent regret analysis for Thompson Sampling in the feedback graph setting. Thompson Sampling (TS-N), shown in Algorithm 2, is a Bayesian approach that samples from a posterior distribution (Beta distribution) to make decisions. Interestingly, TS-N does not require knowledge of the graph structure to run, yet it still benefits from the graph's properties in its performance bounds.
Key Insights and Results
- Breaking the Linear Barrier: The authors successfully moved the constant term of the regret from $O(K)$ to $O(\ln(\text{clique size}))$. This means that as a network grows, the algorithm's overhead grows much more slowly.
- The Power of Extra Exploration: Counter-intuitively, forcing the algorithm to explore slightly more than usual ensures that sub-optimal arms are observed enough times early on to reduce the long-term cost associated with the total number of arms.
- Empirical Validation: Using synthetic setups with varying clique sizes (up to 2056 arms), the authors confirmed that regret for UCB-NE and TS-N grows logarithmically with clique size. In practice, a variant called TS-MaxN performed the best, though it currently lacks a formal problem-dependent regret bound.
Conclusion and Future Work
This work demonstrates that with strategic exploration, it is possible to achieve regret bounds that depend on the structural complexity of the feedback graph rather than the number of arms. Future research directions include tightening the leading term for UCB-NE and extending these results to directed or time-varying feedback graphs.
Summary updated