Information-Theoretic Regret Bounds for Bandits with Fixed Expert Advice

Khaled Eldowa, Nicolò Cesa-Bianchi, Alberto Maria Metelli, Marcello Restelli

This paper, titled "Information-Theoretic Regret Bounds for Bandits with Fixed Expert Advice," provides a significant theoretical update to how we understand the performance of bandit algorithms when guided by experts.

TL;DR

The authors introduce new regret bounds for bandits with expert advice that scale based on the similarity between experts. By using information-theoretic measures, they show that if experts provide similar recommendations, the learner's regret can approach zero—a major improvement over traditional bounds that remained large even for nearly identical experts.

What Problem Does This Paper Address?

In the classic multi-armed bandit problem, a learner tries to minimize "regret"—the difference between their total loss and the loss they would have incurred by always picking the best single action. A common extension is "bandits with expert advice," where $N$ experts suggest probability distributions over $K$ possible actions at every turn.

Historically, the best-known regret bound for the standard EXP4 algorithm was roughly $\sqrt{2TK \log N}$. While powerful, this bound has a major blind spot: it doesn't account for the content of the experts' advice. Even if all $N$ experts are 99% identical, the bound stays large. The authors tackle this gap, asking: Can we prove regret bounds that naturally shrink as experts become more similar?

Methods

The authors analyze two distinct algorithmic approaches to leverage expert similarity:

  1. EXP4 with a Modified Estimator (Algorithm 1): They re-examine the classic EXP4 algorithm but introduce a modified loss estimator. By subtracting a "baseline" probability (the minimum probability any expert assigns to an arm), they can better isolate the differences between experts and reduce the variance of their estimates. Algorithm 1: EXP4 with Fixed Expert Advice
Algorithm 1: EXP4 with Fixed Expert Advice
  1. Online Stochastic Mirror Descent (OSMD) (Algorithm 2): Instead of just picking experts, this approach treats the problem as a bandit task over the convex hull of the experts' policies. It uses a negative entropy regularizer and projects the learner's strategy onto this hull at each step, effectively treating the set of experts as a single structured decision space. Algorithm 2: OSMD on the Convex Hull of Policies
Algorithm 2: OSMD on the Convex Hull of Policies

Datasets

Not discussed in the paper. This work is purely theoretical and focuses on proving mathematical upper and lower bounds on regret.

Key Insights and Ideas

  • The $S^*(\Theta)$ Index: The authors define a new similarity measure, $S^*(\Theta)$, which is the sum of the "ranges" of probabilities assigned to each action across all experts. Crucially, $S^*(\Theta)$ is always smaller than or equal to previous similarity measures and can drop to zero if experts are identical.
  • Vanishing Regret: For the first time, they provide a bound for EXP4 that can get arbitrarily close to zero as experts become more similar. This matches our intuition: if everyone gives the same advice, it's easy to do as well as the best expert.
  • Information Radius: For the OSMD approach, the regret is controlled by $D^*(\Theta)$, which acts like the "width" or "radius" of the expert set in terms of KL-divergence. This bound is particularly effective when the number of actions $K$ is small relative to the number of experts $N$.
  • The Bias-Variance Tradeoff: The paper highlights a neat contrast: EXP4 (Alg 1) uses expert similarity to reduce the variance of loss estimates, while OSMD (Alg 2) uses the limited size of the expert set's convex hull to reduce the bias (the log term in the bound).

Key Results

  • EXP4 Regret: The new bound is $R_T \le \sqrt{2T S^*(\Theta) \log N}$. This is strictly better than the previous state-of-the-art $\sqrt{2T S(\Theta) \log N}$.
  • OSMD Regret: The alternative algorithm achieves $R_T \le \sqrt{2T D^*(\Theta) K}$. The authors show that for certain "$\epsilon$-uniform" policy sets, this bound is superior to the EXP4 bound.
  • Near-Optimality: By constructing specific adversarial environments (like "Radially Symmetric Uniform Policies"), the authors prove lower bounds that match their upper bounds up to logarithmic factors, suggesting their analysis is very close to the fundamental limits of the problem.

Limitations and Future Work

  • The $S^*(\Theta)$ Bottleneck: While $S^*(\Theta)$ is an improvement, the authors admit it can still be "stuck" at $\ge 1$ in some cases where the experts are actually quite similar in terms of total variation distance (see Example 3 in the paper).
  • Fixed vs. Unknown Experts: The current analysis assumes the learner knows the experts' distributions beforehand. A natural next step is extending these information-theoretic bounds to settings where the experts' advice must be learned on the fly.
  • Adaptivity: The authors suggest investigating whether algorithms can automatically adapt to the underlying structure of the policy set without needing to know similarity parameters in advance.

Summary updated

Abstract

We investigate the problem of bandits with expert advice when the experts are fixed and known distributions over the actions. Improving on previous analyses, we show that the regret in this setting is controlled by information-theoretic quantities that measure the similarity between experts. In some natural special cases, this allows us to obtain the first regret bound for EXP4 that can get arbitrarily close to zero if the experts are similar enough. While for a different algorithm, we provide another bound that describes the similarity between the experts in terms of the KL-divergence, and we show that this bound can be smaller than the one of EXP4 in some cases. Additionally, we provide lower bounds for certain classes of experts showing that the algorithms we analyzed are nearly optimal in some cases.
BibTeX
@inproceedings{eldowa2023information,
  author = {Khaled Eldowa and Nicolò Cesa-Bianchi and Alberto Maria Metelli and Marcello Restelli},
  title = {{Information-Theoretic Regret Bounds for Bandits with Fixed Expert Advice}},
  booktitle = {ITW},
  year = {2023},
  doi = {10.1109/itw55543.2023.10161661},
}
Figure