Thompson Sampling for Linearly Constrained Bandits
This work addresses constrained decision-making in bandit problems, which is incremental as it builds on existing Thompson Sampling methods with new theoretical guarantees.
The paper tackles the problem of multi-armed bandits with a probabilistic linear constraint on rewards, proposing LinConTS, a Thompson Sampling-based algorithm that achieves O(log T) bounds on both regret and constraint violations, outperforming an asymptotically optimal UCB scheme in experiments.
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.