  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(\sqrt{T})$. In this paper, we provide a new computationally
efficient algorithm inspired by EXP3 satisfying a regret of order $O(\sqrt{T})$
when the availabilities of each action $i \in \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(\sqrt {2^K
T})$ regret guarantee. Our theoretical results are corroborated with
experimental evaluations.
