Thompson Sampling for Linearly Constrained Bandits
  We address multi-armed bandits (MAB) where the objective is to maximize the
cumulative reward under a probabilistic linear constraint. For a few real-world
instances of this problem, constrained extensions of the well-known Thompson
Sampling (TS) heuristic have recently been proposed. However, finite-time
analysis of constrained TS is challenging; as a result, only O(\sqrt{T}) bounds
on the cumulative reward loss (i.e., the regret) are available. In this paper,
we describe LinConTS, a TS-based algorithm for bandits that place a linear
constraint on the probability of earning a reward in every round. We show that
for LinConTS, the regret as well as the cumulative constraint violations are
upper bounded by O(\log T) for the suboptimal arms. We develop a proof
technique that relies on careful analysis of the dual problem and combine it
with recent theoretical work on unconstrained TS. Through numerical experiments
on two real-world datasets, we demonstrate that LinConTS outperforms an
asymptotically optimal upper confidence bound (UCB) scheme in terms of
simultaneously minimizing the regret and the violation.
