# Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards

arXiv: https://arxiv.org/abs/2004.06248 · HTML: https://mlsanity.com/paper/2004.06248/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Apr 2020.

## Built on by (most cited first, 12 of 12)

- [Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data](https://mlsanity.com/paper/2206.00737/) (2022)
- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Optimal cross-learning for contextual bandits with unknown context distributions](https://mlsanity.com/paper/2401.01857/) (2024)
- [Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret](https://mlsanity.com/paper/2205.14790/) (2022)
- [Low-Regret Active learning](https://mlsanity.com/paper/2104.02822/) (2021)
- [One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Bandits](https://mlsanity.com/paper/2210.14998/) (2022)
- [Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling](https://mlsanity.com/paper/2303.09033/) (2023)
- [Near-optimal Per-Action Regret Bounds for Sleeping Bandits](https://mlsanity.com/paper/2403.01315/) (2024)
- [Adversarial Sleeping Bandit Problems with Multiple Plays: Algorithm and Ranking Application](https://mlsanity.com/paper/2307.14549/) (2023)
- [DP-Dueling: Learning from Preference Feedback without Compromising User Privacy](https://mlsanity.com/paper/2403.15045/) (2024)
- [Improving Sequential Query Recommendation with Immediate User Feedback](https://mlsanity.com/paper/2205.06297/) (2022)
- [Counterfactual Regret for Reflective Agents with Lean-Verified Guarantees](https://mlsanity.com/paper/2610.14790/) (2026)

## Abstract (arXiv)

In this paper, we consider the problem of sleeping bandits with stochastic action sets and adversarial rewards. In this setting, in contrast to most work in bandits, the actions may not be available at all times. For instance, some products might be out of stock in item recommendation. The best existing efficient (i.e., polynomial-time) algorithms for this problem only guarantee an O(T2/3) upper-bound on the regret. Yet, inefficient algorithms based on EXP4 can achieve O(√T). In this paper, we provide a new computationally efficient algorithm inspired by EXP3 satisfying a regret of order O(√T) when the availabilities of each action i ∈ cA are independent. We then study the most general version of the problem where at each round available sets are generated from some unknown arbitrary distribution (i.e., without the independence assumption) and propose an efficient algorithm with O(√ 2K T) regret guarantee. Our theoretical results are corroborated with experimental evaluations.