Lenient Regret for Multi-Armed Bandits
  We consider the Multi-Armed Bandit (MAB) problem, where an agent sequentially
chooses actions and observes rewards for the actions it took. While the
majority of algorithms try to minimize the regret, i.e., the cumulative
difference between the reward of the best action and the agent's action, this
criterion might lead to undesirable results. For example, in large problems, or
when the interaction with the environment is brief, finding an optimal arm is
infeasible, and regret-minimizing algorithms tend to over-explore. To overcome
this issue, algorithms for such settings should instead focus on playing
near-optimal arms. To this end, we suggest a new, more lenient, regret
criterion that ignores suboptimality gaps smaller than some $\epsilon$. We then
present a variant of the Thompson Sampling (TS) algorithm, called
$\epsilon$-TS, and prove its asymptotic optimality in terms of the lenient
regret. Importantly, we show that when the mean of the optimal arm is high
enough, the lenient regret of $\epsilon$-TS is bounded by a constant. Finally,
we show that $\epsilon$-TS can be applied to improve the performance when the
agent knows a lower bound of the suboptimality gaps.
