Regret Bounds for Sleeping Experts and Bandits

Robert D. Kleinberg, Alexandru Niculescu-Mizil, Yogeshwer Sharma

In the traditional framework of online learning, such as the Multi-Armed Bandit (MAB) problem, a learner chooses from a fixed set of $n$ actions in each round, aiming to minimize regret against the best single action in hindsight. However, real-world scenarios often violate the assumption of constant availability. Whether it is a stock that is temporarily untradable, a network route that is down, or a product that is out of stock, actions frequently "sleep." This paper provides a foundational analysis of the "sleeping experts" and "sleeping bandits" problems, establishing near-optimal regret bounds and defining a robust benchmark for performance in dynamic environments.

The Problem: Defining Success in a Shifting Menu

The primary challenge in the sleeping experts setting is defining a fair benchmark. If the historically "best" action is only available for a small fraction of the total time $T$, comparing a learner's total performance against that action's potential performance is mathematically problematic and often unintuitive.

To address this, the authors introduce the "Best Ordering" benchmark. Instead of comparing the learner to a single action, they compare it to a fixed permutation (ranking) of all actions. In any given round, the benchmark policy simply selects the highest-ranked action among those currently available (the "awake" set). This mimics natural decision-making—such as a consumer who has a clear preference list and chooses their favorite available item.

Algorithmic Frameworks

The paper explores two distinct reward models: the Stochastic model, where rewards are drawn from fixed but unknown distributions, and the Adversarial model, where rewards are chosen by an opponent to maximize the learner's difficulty.

1. The Stochastic Setting

In the stochastic environment, the authors adapt classic algorithms to handle availability constraints:

  • Follow The Awake Leader (FTAL): Designed for the full-information (expert) setting, this algorithm selects the awake expert with the highest average historical payoff, calculated only from the rounds where that expert was actually awake.
  • Awake Upper Estimated Reward (AUER): An adaptation of the UCB1 algorithm for the bandit (partial-information) setting. It utilizes confidence intervals to balance the exploration of rarely seen "sleeping" arms with the exploitation of known high-performing ones.

2. The Adversarial Setting

In the adversarial setting, the problem becomes significantly more complex. The authors treat each of the $n!$ possible orderings as a "meta-expert." By applying standard regret-minimization tools like Hedge or Exp4 over these permutations, they can derive regret bounds, though at a high computational cost.

Key Results and Regret Bounds

The authors prove that their derived regret bounds are "tight," matching the mathematical lower bounds of the problem within small logarithmic factors.

Setting Regret Bound Note
Stochastic Experts $O(1)$ Regret is independent of $T$; the algorithm stops making mistakes quickly.
Stochastic Bandits $O(\log T)$ Matches the optimal rate for standard bandits, scaled by action gaps.
Adversarial Experts $\Omega(\sqrt{Tn \log n})$ Regret grows with the square root of time and number of actions.
Adversarial Bandits $\Omega(n\sqrt{T})$ A higher regret floor due to limited information.

Computational Complexity and NP-Hardness

While the paper establishes that optimal regret bounds exist for the adversarial setting, it also identifies a significant hurdle: computational efficiency. The authors demonstrate that finding the best ordering in the adversarial case is related to the "Feedback Arc Set" problem, which is NP-hard.

This implies that any algorithm attempting to explicitly learn the best ordering in a fully adversarial environment cannot be computationally efficient (polynomial time) unless P = NP. While the "brute force" approach using $n!$ permutations works theoretically, it is impractical for large action sets.

Conclusion

This work bridges the gap between theoretical online learning and practical scenarios where action availability is fluid. By introducing the Best Ordering benchmark, the authors provide a natural and mathematically rigorous way to evaluate performance in sleeping environments. While the stochastic case is effectively solved with efficient algorithms like FTAL and AUER, the adversarial case remains a fertile ground for future research, specifically regarding the development of polynomial-time algorithms that can approach the theoretical regret lower bounds.

Summary updated

BibTeX
@inproceedings{kleinberg2008regret,
  author = {Robert D. Kleinberg and Alexandru Niculescu-Mizil and Yogeshwer Sharma},
  title = {{Regret Bounds for Sleeping Experts and Bandits}},
  booktitle = {Conference on Learning Theory},
  year = {2008},
}
Figure