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.
Introduction
In the standard Multi-Armed Bandit (MAB) problem, an agent selects an action and observes only the reward associated with that specific action. "Graphical Bandits" extend this model by introducing side observations: selecting an action reveals the rewards of its neighbors in a feedback graph. This model is highly relevant to applications like viral marketing or social network analysis, where an intervention on one node provides information about connected nodes.
Existing literature often assumes the feedback graph is either known beforehand or revealed locally after an action is taken. However, in many real-world scenarios—such as privacy-restricted networks—the graph structure remains hidden. This paper investigates the "without the graphs" setting, asking whether optimal regret can be achieved without explicit knowledge of the underlying network.
Methodology
The study evaluates two Thompson Sampling (TS) variants:
- Vanilla Thompson Sampling (TS-N): A standard Bayesian approach that maintains posterior distributions for each arm's reward. At each step, it samples from these distributions and selects the arm with the highest sample. Crucially, it updates the posteriors for all arms whose rewards are observed via the feedback graph, regardless of whether they were the primary selection.
- Thompson Sampling with Exploration (TS-U): Designed specifically for directed graphs, this variant incorporates a small amount of uniform random exploration (probability $\epsilon$). This prevents the algorithm from ignoring "informative" arms that might have low individual rewards but provide significant data about other arms.
Theoretical analysis is conducted using the Information Ratio framework, which quantifies the regret incurred per unit of information gained about the optimal action.
Experimental Setup
The algorithms were tested using Beta-Bernoulli bandits, where rewards are binary and beliefs are modeled via Beta distributions. The feedback structures included:
- Time-invariant graphs: Fixed cliques (undirected) and specific directed structures.
- Time-variant graphs: Dynamic networks generated using the Erdős-Rényi model, where connections change at each time step.
Key Insights
- Graph-Agnosticism: Thompson Sampling implicitly leverages the graph structure by updating its internal model with all available data, requiring no prior knowledge of the network.
- Undirected Optimality: In undirected settings, TS-N is shown to be optimal, with regret scaling with the average independence number ($\beta_0$) of the graph.
- Directed Graph Challenges: In directed graphs, certain nodes may be highly informative but yield low rewards. TS-N might stop selecting these nodes, leading to suboptimal information gain. TS-U addresses this through forced exploration.
- Tighter Theoretical Bounds: The authors demonstrate that TS regret depends on the independence number, providing a tighter bound than the clique cover number used in previous research.
Results and Discussion
Empirical results demonstrate that both TS-N and TS-U significantly outperform existing benchmarks, such as UCB-N and Cohen’s elimination algorithm.
As shown in Figure 3, TS-N consistently achieves the lowest regret across both static and dynamic graph environments. While TS-U provides better theoretical guarantees for directed graphs, TS-N often performs superiorly in practice, maintaining lower regret even in complex time-variant scenarios.
Conclusion
This work establishes that Thompson Sampling is a robust and optimal choice for graphical bandits, even when the feedback graph is unknown and time-varying. Future research may explore extensions to linear bandits or address the theoretical gap for vanilla TS in directed graph settings.
Summary updated