Analysis of Thompson Sampling for Graphical Bandits Without the Graphs

Fang Liu, Zizhan Zheng, Ness B. Shroff

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:

  1. 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.
  2. 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.

Cumulative regret of TS variants compared to UCB-N and Cohen's algorithm in time-invariant (a) and time-variant (b) graph settings.

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

Abstract

We study multi-armed bandit problems with graph feedback, in which the decision maker is allowed to observe the neighboring actions of the chosen action, in a setting where the graph may vary over time and is never fully revealed to the decision maker. We show that when the feedback graphs are undirected, the original Thompson Sampling achieves the optimal (within logarithmic factors) regret $\tilde{O}\left(\sqrt{\beta_0(G)T}\right)$ over time horizon $T$, where $\beta_0(G)$ is the average independence number of the latent graphs. To the best of our knowledge, this is the first result showing that the original Thompson Sampling is optimal for graphical bandits in the undirected setting. A slightly weaker regret bound of Thompson Sampling in the directed setting is also presented. To fill this gap, we propose a variant of Thompson Sampling, that attains the optimal regret in the directed setting within a logarithmic factor. Both algorithms can be implemented efficiently and do not require the knowledge of the feedback graphs at any time.
BibTeX
@inproceedings{liu2018analysis,
  author = {Fang Liu and Zizhan Zheng and Ness B. Shroff},
  title = {{Analysis of Thompson Sampling for Graphical Bandits Without the Graphs}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=hR9OUlbwSil},
}
Figure