Skip to Main content Skip to Navigation
Conference papers

Improved sleeping bandits with stochastic action sets and adversarial rewards

Aadirupa Saha 1 Pierre Gaillard 2 Michal Valko 3
2 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
Abstract : 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(T 2/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 ∈ A$ 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(√ 2 K T)$ regret guarantee. Our theoretical results are corroborated with experimental evaluations.
Document type :
Conference papers
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/hal-02950106
Contributor : Michal Valko <>
Submitted on : Sunday, September 27, 2020 - 11:24:26 AM
Last modification on : Wednesday, September 30, 2020 - 3:34:08 AM

File

saha2020improved.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02950106, version 1

Collections

Citation

Aadirupa Saha, Pierre Gaillard, Michal Valko. Improved sleeping bandits with stochastic action sets and adversarial rewards. ICML 2020 - 37th International Conference on Machine Learning, Jul 2020, Vienna / Virtual, Austria. ⟨hal-02950106⟩

Share

Metrics

Record views

1258

Files downloads

109