Dueling Bandits with Adversarial Sleeping

Aadirupa Saha, Pierre Gaillard

Abstract

We introduce the problem of sleeping dueling bandits with stochastic preferences and adversarial availabilities (DB-SPAA). In almost all dueling bandit applications, the decision space often changes over time; eg, retail store management, online shopping, restaurant recommendation, search engine optimization, etc. Surprisingly, this 'sleeping aspect' of dueling bandits has never been studied in the literature. Like dueling bandits, the goal is to compete with the best arm by sequentially querying the preference feedback of item pairs. The non-triviality however results due to the non-stationary item spaces that allow any arbitrary subsets items to go unavailable every round. The goal is to find an optimal 'no-regret' policy that can identify the best available item at each round, as opposed to the standard 'fixed best-arm regret objective' of dueling bandits. We first derive an instance-specific lower bound for DB-SPAA $\Omega( \sum_{i =1}^{K-1}\sum_{j=i+1}^K \frac{\log T}{\Delta(i,j)})$, where $K$ is the number of items and $\Delta(i,j)$ is the gap between items $i$ and $j$. This indicates that the sleeping problem with preference feedback is inherently more difficult than that for classical multi-armed bandits (MAB). We then propose two algorithms, with near optimal regret guarantees. Our results are corroborated empirically.

Introduction

In the classic Dueling Bandits framework, a learner repeatedly chooses a pair of items and observes which one a user prefers, with the goal of identifying the best item with minimal regret. However, real-world scenarios are rarely static. In retail, products go out of stock; in search engines, pages might be down; in restaurant recommendations, venues close. This is the "sleeping" aspect: items can become unavailable at any time. While this has been studied for standard Multi-Armed Bandits (MAB), it had never been addressed for Dueling Bandits until now.

This paper introduces the DB-SPAA (Dueling Bandits with Stochastic Preferences and Adversarial Availabilities) problem. Here, underlying preferences are stable, but the set of available items is chosen by an adversary who can hide the best items to force the learner into difficult trade-offs.

The DB-SPAA Framework

The DB-SPAA problem is fundamentally harder than standard sleeping MAB. Because the learner only receives relative feedback, an adversary can hide the top items, forcing the learner to understand the relationship between every single pair of suboptimal items to prepare for scenarios where they are the only ones available. The authors establish a fundamental lower bound of $\Omega( \sum_{i =1}^{K-1}\sum_{j=i+1}^K \frac{\log T}{\Delta(i,j)})$, confirming that the problem's difficulty scales quadratically with the number of items $K$.

Algorithms for Dynamic Environments

The researchers propose two primary algorithms to address the DB-SPAA challenge:

1. SlDB-UCB (Upper Confidence Bound)

SlDB-UCB is a fixed-confidence algorithm that maintains pairwise estimates for every possible duel. It uses optimistic confidence intervals to select the most promising items from the currently available set $S_t$. It is designed to provide strong guarantees that regret will not exceed a specific threshold with high probability.

Algorithm 1: SlDB-UCB, a fixed-confidence algorithm for sleeping dueling bandits.

2. SlDB-ED (Empirical Divergence)

SlDB-ED is an expected regret algorithm inspired by the Relative Minimum Empirical Divergence (RMED) approach. Instead of simple confidence intervals, it uses KL-divergence to measure how likely an item is to be the "best" among the currently available set. This algorithm is sequence-adaptive: if an item is rarely available, the algorithm focuses its exploration on items that appear more frequently.

Empirical Evaluation

The algorithms were evaluated using synthetic datasets based on the Plackett-Luce model. Scenarios ranged from "Easy" (clear preference separation) to "Hard" (very close preferences). They also simulated various availability sequences, from random to highly correlated.

Key results include:

  • Near-Optimality: Both algorithms achieve regret bounds that are near-optimal. SlDB-ED, in particular, matches the lower bound's dependence on time ($T$).
  • Performance: In simulations, SlDB-UCB generally outperformed SlDB-ED in terms of raw regret, while SlDB-ED showed consistent distribution-free scaling of $O(T^{2/3})$ in worst-case scenarios.

Conclusion and Future Work

This work provides the first formal treatment of the sleeping aspect in dueling bandits. Future research directions include relaxing the "total ordering" constraint to accommodate cyclical preferences (e.g., Borda or Copeland rankings), incorporating contextual information (item features), and extending the framework from pairwise duels to multi-item "battles."

Summary updated

Abstract

We introduce the problem of sleeping dueling bandits with stochastic preferences and adversarial availabilities (DB-SPAA). In almost all dueling bandit applications, the decision space often changes over time; eg, retail store management, online shopping, restaurant recommendation, search engine optimization, etc. Surprisingly, this `sleeping aspect' of dueling bandits has never been studied in the literature. Like dueling bandits, the goal is to compete with the best arm by sequentially querying the preference feedback of item pairs. The non-triviality however results due to the non-stationary item spaces that allow any arbitrary subsets items to go unavailable every round. The goal is to find an optimal `no-regret' policy that can identify the best available item at each round, as opposed to the standard `fixed best-arm regret objective' of dueling bandits. We first derive an instance-specific lower bound for DB-SPAA $\Omega( \sum_{i =1}^{K-1}\sum_{j=i+1}^K \frac{\log T}{\Delta(i,j)})$, where $K$ is the number of items and $\Delta(i,j)$ is the gap between items $i$ and $j$. This indicates that the sleeping problem with preference feedback is inherently more difficult than that for classical multi-armed bandits (MAB). We then propose two algorithms, with near optimal regret guarantees. Our results are corroborated empirically.
BibTeX
@inproceedings{saha2021dueling,
  author = {Aadirupa Saha and Pierre Gaillard},
  title = {{Dueling Bandits with Adversarial Sleeping}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=QWXFOs7WAs},
}
Figure