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.

本文考虑了具有随机动作集和对抗回报的睡眠强盗问题，提出了一种新的受到 EXP3 启发的高效算法，并在每轮可用集合从一些未知的任意分布中产生的最普遍版本中提出了一个具有保证的高效算法。

具备随机行动集和对抗性奖励的改进型睡眠赌博机

Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial  Rewards

In many practical uses of reinforcement learning (RL) the set of actions
available at a given state is a random variable, with realizations governed by
an exogenous stochastic process. Somewhat surprisingly, the foundations for
such sequential decision processes have been unaddressed. In this work, we
formalize and investigate MDPs with stochastic action sets (SAS-MDPs) to
provide these foundations. We show that optimal policies and value functions in
this model have a structure that admits a compact representation. From an RL
perspective, we show that Q-learning with sampled action sets is sound. In
model-based settings, we consider two important special cases: when individual
actions are available with independent probabilities; and a sampling-based
model for unknown distributions. We develop poly-time value and policy
iteration methods for both cases; and in the first, we offer a poly-time linear
programming solution.

研究了具有随机动作集的马尔可夫决策过程及其最优策略和值函数的性质，并针对不同情况提出了多项式时间的策略迭代和价值迭代方法。