Abstract
In many real-world decision-making scenarios, such as viral marketing or online pricing, choosing an action provides information not only about its own reward but also about the rewards of related actions. This is modeled as a "graphical bandit" problem. While most existing literature assumes the underlying feedback graph is known, this paper demonstrates that Thompson Sampling (TS) can achieve optimal performance even when the graph structure is hidden. We analyze two variants, TS-N and TS-U, proving regret bounds that scale with the graph's independence number. Empirical evaluations show that these TS variants significantly outperform traditional UCB and elimination-based algorithms.
Introduction
The Multi-Armed Bandit (MAB) framework is a cornerstone of reinforcement learning, balancing the exploration of unknown actions with the exploitation of known high-reward actions. Graphical bandits extend this by incorporating side observations: pulling one lever reveals rewards for its neighbors in a feedback graph. However, a significant gap exists between theory and practice, as real-world graphs (e.g., social networks) are often private or latent. This work addresses the challenge of achieving optimal regret without prior or posterior knowledge of the graph structure.
Methodology
We investigate two versions of the Thompson Sampling algorithm:
- TS-N (Vanilla Thompson Sampling): A standard Bayesian approach that samples actions based on their posterior probability of being optimal. The authors provide a new, tighter analysis of its "Information Ratio" to bound regret.
- TS-U (Thompson Sampling with Exploration): Designed for directed graphs where information flow may be restricted. TS-U incorporates a small uniform exploration component ($\epsilon$) to ensure the algorithm eventually observes enough of the latent graph to make informed decisions.
A key theoretical contribution is the use of the independence number ($\beta_0$) to bound regret. Unlike the clique-cover number used in previous work, the independence number provides a sharper, more efficient theoretical guarantee, as it is always smaller than or equal to the clique cover number.
Empirical Evaluation
The algorithms were tested using Beta-Bernoulli bandits across various graph dynamics, including time-invariant and time-variant (Erdős-Rényi) models.
As shown in the figure above, both TS-N and TS-U consistently achieve lower cumulative regret than UCB-N and Cohen’s elimination-based algorithm. TS-N typically performs best in practice, effectively exploiting side observations even without explicit graph knowledge. In directed settings, TS-U ensures robust performance by maintaining sufficient exploration, preventing the algorithm from getting stuck in sub-optimal nodes.
Conclusion
This research confirms that Thompson Sampling is a powerful, "graph-agnostic" tool for graphical bandits. By naturally balancing exploration and exploitation through posterior sampling, it exploits hidden information structures more effectively than frequentist alternatives. Future work includes extending these proofs to non-Bayesian settings and more complex reward structures like contextual bandits.
Summary updated