Adversarial Sleeping Bandit Problems with Multiple Plays: Algorithm and Ranking Application
This addresses the challenge of selecting multiple items per time step in recommendation systems with uncertain availability, but it is incremental as it extends existing single-arm methods.
The paper tackles the sleeping bandit problem with multiple plays in online recommendation systems, where arms have adversarial losses and unknown availability distributions, and proposes an algorithm that achieves a regret upper bound of O(kN^2√(T log T)).
This paper presents an efficient algorithm to solve the sleeping bandit with multiple plays problem in the context of an online recommendation system. The problem involves bounded, adversarial loss and unknown i.i.d. distributions for arm availability. The proposed algorithm extends the sleeping bandit algorithm for single arm selection and is guaranteed to achieve theoretical performance with regret upper bounded by $\bigO(kN^2\sqrt{T\log T})$, where $k$ is the number of arms selected per time step, $N$ is the total number of arms, and $T$ is the time horizon.