Abstract
In the classic multi-armed bandit problem with expert advice, standard regret bounds typically depend on the number of experts rather than the similarity of their recommendations. This paper introduces new, tighter regret bounds for scenarios where experts are fixed probability distributions over actions. By employing information-theoretic measures of expert similarity, we demonstrate that regret can be significantly reduced—and even become vanishingly small—when experts recommend similar actions. We analyze two primary algorithmic approaches: a modified EXP4 algorithm and Online Stochastic Mirror Descent (OSMD) on the convex hull of policies, showing that similarity acts as a critical resource for reducing variance and bias in loss estimation.
Introduction
The "bandits with expert advice" problem involves a learner choosing actions to minimize regret—the difference between their cumulative loss and that of the best expert. Standard algorithms like EXP4 yield regret bounds of $\sqrt{2TK \log N}$, where $T$ is time, $K$ is the number of actions, and $N$ is the number of experts. However, these bounds fail to account for the content of the experts' advice. Intuitively, if 1,000 experts provide nearly identical recommendations, the learning task should be easier than if they were diverse. This paper addresses this gap by quantifying how expert similarity reduces learning difficulty.
Methods
The authors propose and analyze two distinct algorithmic strategies to exploit expert similarity:
1. Modified EXP4
The first approach adapts the classic EXP4 algorithm by utilizing a modified loss estimate. Instead of raw loss estimation, it uses a "centered" loss that subtracts the minimum probability assigned to an arm across all experts. This technique allows the estimator's variance to scale directly with the similarity of the experts.
2. Online Stochastic Mirror Descent (OSMD)
The second approach treats the problem as a bandit task over the convex hull of the experts' policies. By projecting the learner's distribution onto this space and employing a negative entropy regularizer, the authors derive a bound based on the "width" of the policy set in terms of KL-divergence.
To validate these methods, the authors also derived minimax lower bounds using synthetic policy structures such as radially symmetric uniform policies and $\epsilon$-uniform policies.
Key Insights and Results
The core contribution of this work is the identification of similarity as an information-theoretic resource that controls the variance of loss estimates.
- The $S^*(\Theta)$ Index: A new similarity index, $S^*(\Theta)$, is introduced to measure the sum of the ranges of probabilities assigned to each arm. Unlike previous metrics, this index can approach zero, allowing for the first EXP4 bound that vanishes as experts become identical.
- Regret Bounds: Theorem 1 proves that the modified EXP4 achieves $R_T \leq \sqrt{2T S^*(\Theta) \log N}$. Theorem 2 shows that the OSMD approach achieves $R_T \leq \sqrt{2T K D^*(\Theta)}$, where $D^*(\Theta)$ is the KL-divergence "width" of the policy set.
- Information Radius: The OSMD bound is linked to the "information radius" (Jensen-Shannon divergence), connecting bandit regret to classical information theory.
- Optimality: Lower bounds demonstrate that the $S^*(\Theta)$ bound is optimal (up to logarithmic factors) for specific uniform policy classes.
Conclusion and Future Work
This research provides a more nuanced understanding of regret in bandit problems with expert advice. While the current analysis assumes known expert distributions, future work will explore whether these bounds hold when distributions must be learned online. Additionally, the authors noted cases where $S^*(\Theta)$ may not fully capture expert similarity, suggesting that further refinement of information-theoretic quantities is possible.
Summary updated