Abstract
We address the problem of Internal Regret in adversarial Sleeping Bandits and the relationship between different notions of sleeping regrets in multi-armed bandits. We propose a new concept called Internal Regret for sleeping multi-armed bandits (MAB) and present an algorithm that achieves sublinear Internal Regret, even when losses and availabilities are both adversarial. We demonstrate that a low internal regret leads to both low external regret and low policy regret for i.i.d. losses. Our contribution is unifying existing notions of regret in sleeping bandits and exploring their implications for each other. In addition, we extend our results to Dueling Bandits (DB), a preference feedback version of multi-armed bandits, and design a low-regret algorithm for sleeping dueling bandits with stochastic preferences and adversarial availabilities. We validate the effectiveness of our algorithms through empirical evaluations.
Introduction
In online machine learning, the Multi-Armed Bandit (MAB) framework is a cornerstone for decision-making under uncertainty. Traditionally, a learner selects an arm from a fixed set to minimize "regret"—the difference between the accumulated loss and the loss of the best single action in hindsight. However, real-world scenarios often involve "sleeping" bandits, where the set of available actions $S_t$ changes at each time step. This occurs in various domains, such as retail inventory management or dynamic content recommendation.
The Challenge of Sleeping Bandits
Historically, success in sleeping bandits has been measured through disparate metrics:
- External Sleeping Regret: Comparing performance to the best single arm during its periods of availability.
- Ordering Regret: Comparing performance to a fixed ranking of arms (e.g., always picking the highest-ranked available arm).
- Policy Regret: Comparing performance to the best mapping from available sets to actions.
The difficulty lies in the environment's nature. While some metrics are manageable in stochastic settings, minimizing ordering regret becomes NP-hard when both losses and arm availabilities are adversarial. This paper introduces a unified approach to bridge these gaps.
A Unified Framework: Internal Sleeping Regret
The authors propose Internal Sleeping Regret as a master metric. In game theory, internal regret asks: "If I played arm $i$, would I have been better off playing arm $j$ instead every time $j$ was available?"
As illustrated in the figure above, Internal Sleeping Regret serves as a unifying force. The authors prove that achieving low Internal Sleeping Regret automatically guarantees low External Regret in adversarial settings and low Ordering/Policy Regret in stochastic settings. This "One Arrow, Two Kills" property allows a single algorithmic approach to satisfy multiple performance criteria simultaneously.
The SI-EXP3 Algorithm
To minimize this new regret notion, the authors developed SI-EXP3 (Sleeping Internal EXP3). The algorithm operates by maintaining $K(K-1)$ "fictitious experts," where each expert manages a specific pair of arms $(i \to j)$.
As shown in the algorithm listing, SI-EXP3 finds a probability distribution $p_t$ over available arms by solving a linear system (finding a "fixed point"). This ensures that the overall internal regret remains bounded even under adversarial conditions. Theoretically, SI-EXP3 achieves an optimal regret bound of $O(\sqrt{TK \log K})$.
Extensions to Dueling Bandits
The framework is further extended to Dueling Bandits, where learners only observe the winner of a "duel" between two arms rather than absolute rewards. By employing a "Sparring" technique—running two instances of SI-EXP3 against each other—the authors achieve the first $O(\sqrt{T})$ regret bound for sleeping dueling bandits with stochastic preferences and adversarial availabilities, a significant improvement over the previous $O(T^{2/3})$ state-of-the-art.
Empirical Results and Insights
Empirical evaluations across stochastic and dependent environments (where losses depend on which arms are awake) demonstrate SI-EXP3's robustness. In scenarios where standard baselines like S-UCB and S-EXP3 suffered linear regret, SI-EXP3 maintained sublinear growth, effectively learning the optimal strategy despite adversarial shifts.
Key insights from the study include:
- Adversarial Robustness: SI-EXP3 is one of the few algorithms capable of handling the "hardest" case where both losses and availability are adversarial.
- Computational Trade-offs: While theoretically powerful, the $O(K^3)$ per-round complexity for solving the linear system may pose challenges for systems with a very large number of arms.
Conclusion
By introducing Internal Sleeping Regret, this work provides a cohesive theoretical foundation for the sleeping bandit problem. The SI-EXP3 algorithm and its extension to dueling bandits represent a significant step forward in creating robust, general-purpose decision-making agents for dynamic environments.
Summary updated