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