TL;DR
This paper introduces the first framework for "sleeping" dueling bandits, where a learner must identify the best option through pairwise comparisons even as the available choices change unpredictably over time. The authors prove this problem is inherently harder than standard bandit problems and provide two new algorithms—S1DB-UCB and S1DB-ED—that achieve near-optimal performance in these volatile environments.
What Problem Does This Paper Address?
In the classic Multi-Armed Bandit (MAB) problem, a learner tries to find the best "arm" (option) to maximize rewards. Dueling Bandits are a popular variation where, instead of seeing a numerical reward, the learner picks two items and only sees which one is preferred (e.g., "Do users prefer Search Result A or B?").
However, most research assumes the set of items is fixed. In the real world, options "sleep": a retail store runs out of stock, a restaurant removes a dish from the menu, or a web server goes down. This is known as the Sleeping Bandit problem.
Until this paper, no one had combined these two realistic constraints: preference-based feedback and adversarial availability (where an "adversary" can choose which items are unavailable at any time). The authors call this new setting DB-SPAA (Dueling Bandits with Stochastic Preferences and Adversarial Availabilities).
The challenge is that the "best" item isn't a single fixed target; the learner must compete against the best available item in every round, incurring regret based on the preference gap between their choices and the optimal available choice.
Methods
The authors tackle the problem from both a theoretical and algorithmic perspective:
- Lower Bound Analysis: They first prove that this problem is fundamentally more difficult than standard sleeping bandits. While standard MAB problems scale linearly with the number of items ($K$), they show that sleeping dueling bandits scale with $K^2$. This is because an adversary can force the learner to compare almost every possible pair of items by strategically making certain items unavailable.
- S1DB-UCB: A "fixed-confidence" algorithm based on Upper Confidence Bounds. It maintains a record of every pairwise "duel" and uses a confidence interval to estimate which items are potential winners.
- S1DB-ED: A more computationally efficient "expected regret" algorithm. It uses Empirical Divergence (ED)—a measure of how likely an item is to be the best based on its win-loss record—to filter out "good" arms. This algorithm is designed to be "near-optimal," meaning its performance closely matches the theoretical limits they derived.
Datasets and Experimental Setup
The paper evaluates the algorithms using synthetic preference models rather than static datasets, which is standard for online learning research. They constructed three types of preference matrices based on the Plackett-Luce model:
- Easy: Preferences are well-separated, making the best item easy to spot.
- Medium: Moderate diversity in preferences.
- Hard: Items are very similar, requiring many comparisons to distinguish the winner.
To simulate "sleeping," they used different availability sequences, ranging from items going offline randomly (Independent) to items going offline in groups (Low/High Correlation).
Key Insights and Ideas
- The $K$-factor Penalty: In standard dueling bandits, you can often find the best arm by comparing everything to a single "champion." In the sleeping version, the adversary can "hide" your champion, forcing you to learn the relationships between all the "sub-optimal" arms. This makes the problem $K$ times harder than the non-sleeping version.
- Total Ordering: The authors assume a "total ordering" (if A > B and B > C, then A > C). This ensures a clear "Condorcet winner" exists for any subset of available items.
- Adaptivity: A major novelty of the S1DB-ED algorithm is its ability to adapt to the "hardness" of the availability sequence. If the environment is kind and keeps the best items available, the algorithm incurs less regret; if the environment is malicious, the algorithm still maintains its theoretical guarantees.
Key Results
- Theoretical Bound: The authors established a lower bound of $\Omega(K^2 \log T / \Delta)$, confirming the quadratic dependence on the number of items.
- Near-Optimality: The S1DB-ED algorithm achieves a regret bound of $O(K \log T / \Delta)$, which matches the lower bound in terms of time ($T$) and is near-optimal regarding the number of items.
- Empirical Performance:
As shown above, both algorithms successfully converged to the optimal policy across Easy, Medium, and Hard scenarios. Interestingly, S1DB-UCB actually tended to slightly outperform S1DB-ED in practice, despite S1DB-ED's strong theoretical guarantees.
- Robustness: The algorithms proved robust even when item availabilities were highly correlated, showing they can handle complex, non-random "sleeping" patterns.
Limitations and Future Work
- Total Ordering Assumption: The current model assumes a perfect hierarchy of items. In reality, preferences can be cyclic (A beats B, B beats C, but C beats A). Extending this to "Borda" or "Copeland" winners would be a significant next step.
- Pairwise vs. Subset: The model only considers duels between two items. Many modern systems (like Amazon or Netflix) show a list of items. Extending this to subset-wise feedback would increase its practical utility.
- Contextual Information: The paper doesn't account for "context" (e.g., user profiles). Combining sleeping dueling bandits with contextual features is a promising direction for personalized recommendation systems.
Summary updated