Stochastic Graphical Bandits with Adversarial Corruptions

Shiyin Lu, Guanghui Wang, Lijun Zhang

1. Introduction

The Multi-Armed Bandit (MAB) framework is a cornerstone of online learning, balancing exploration and exploitation. Graphical Bandits (GB) enhance this by introducing a feedback graph where selecting an arm reveals rewards for its neighbors. While traditional models assume purely stochastic or purely adversarial rewards, real-world applications—such as online advertising subject to click fraud—often present a "stochastic with adversarial corruptions" landscape. This paper introduces Elise (Exploring on Independent Sets), a robust algorithm designed to navigate these corrupted environments efficiently.

2. The Elise Algorithm

Elise addresses the limitations of prior robust algorithms by leveraging the graph structure to minimize exploration costs. Its design is centered on three primary innovations:

2.1 Independent Set Exploration

Rather than exploring all $K$ arms, Elise identifies an independent set—a subset of arms where no two are neighbors. By observing rewards from an independent set, the learner can infer information about the entire graph. Elise employs a greedy sub-routine to find these sets, reducing the exploration complexity from the total number of arms $K$ to the graph's independence number $\alpha$.

2.2 Soft Arm Elimination

To remain resilient against adversaries, Elise avoids permanent arm elimination. Traditional "hard" elimination can be exploited by an adversary who corrupts an optimal arm early to force its removal. Elise utilizes an epoch-based "soft" approach, reducing the selection probability of underperforming arms without ever reaching zero. This allows the algorithm to recover if an arm's initial poor performance was due to temporary corruption.

2.3 Refined Statistical Estimators

The authors replace standard Chernoff-Hoeffding bounds with Bernstein’s inequality. By incorporating variance into the reward estimates, Elise achieves significantly tighter confidence intervals. This refinement reduces the leading constant factors in the regret bound by approximately 500x compared to previous state-of-the-art methods like BARBAR.

3. Theoretical Contributions

The primary theoretical achievement is a regret bound of $O(\alpha \ln K \ln T + \alpha C)$, where $C$ is the total corruption budget. This bound is the first to scale linearly with the independence number $\alpha$ in a corrupted setting, ensuring that the "penalty" for adversarial interference is proportional to the graph's inherent complexity rather than the total number of choices.

4. Experimental Evaluation

The authors evaluated Elise using synthetic simulations across two primary settings:

  • Multi-Armed Bandit (MAB): Tested with $K=5$ and $K=10$ arms using truncated normal reward distributions.
  • Graphical Bandits: Utilized Erdos–Renyi random graphs with varying edge probabilities ($p=0.2, 0.5$) to simulate different levels of side information.
  • Adversary Model: An adversary was simulated to "zero out" optimal rewards until a budget $C$ was exhausted.

5. Results and Discussion

Experimental results confirm that Elise significantly outperforms both standard stochastic algorithms and previous robust methods.

Comparison of Elise vs. BARBAR and UCB in a standard Multi-Armed Bandit setting ($K=5, 10$). Elise demonstrates superior robustness and lower cumulative regret.

In the MAB setting, the standard UCB algorithm fails under corruption, exhibiting linear regret. While BARBAR remains robust, Elise achieves much lower regret due to its tighter theoretical constants.

Performance of Elise in the Graphical Bandit setting across different graph densities ($p=0.2, 0.5$). Higher density (larger $p$) leads to lower regret as side information increases.

In graphical settings, Elise effectively utilizes side information. As the graph density increases (higher $p$), the independence number $\alpha$ decreases, leading to lower cumulative regret. Elise consistently outperforms Exp3-Set and AAE-AlphaSample across these configurations.

6. Conclusion and Future Work

Elise represents a significant step forward in making graphical bandit algorithms practical for real-world, noisy environments. By focusing exploration on independent sets and employing soft elimination, it achieves theoretical optimality with practical efficiency. Future research may explore extending these results to directed graphs, time-varying feedback structures, or heavy-tailed reward distributions.

Summary updated

Abstract

We study bandits with graph-structured feedback, where a learner repeatedly selects an arm and then observes rewards of the chosen arm as well as its neighbors in the feedback graph. Existing work on graphical bandits assumes either stochastic rewards or adversarial rewards, both of which are extremes and appear rarely in real-world scenarios. In this paper, we study graphical bandits with a reward model that interpolates between the two extremes, where the rewards are overall stochastically generated but a small fraction of them can be adversarially corrupted. For this problem, we propose an online algorithm that can utilize the stochastic pattern and also tolerate the adversarial corruptions. The main idea is to restrict exploration to carefully-designed independent sets of the feedback graph and perform exploitation by adopting a soft version of arm elimination. Theoretical analysis shows that our algorithm attains an $O(\alpha \ln{K} \ln{T} + \alpha C)$ regret, where $\alpha$ is the independence number of the feedback graph, $K$ is the number of arms, $T$ is the time horizon, and $C$ quantifies the total corruptions introduced by the adversary. The effectiveness of our algorithm is demonstrated by numerical experiments.
BibTeX
@inproceedings{lu2021stochastic,
  author = {Shiyin Lu and Guanghui Wang and Lijun Zhang},
  title = {{Stochastic Graphical Bandits with Adversarial Corruptions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i10.17060},
}
Figure