Stochastic Bandits with Linear Constraints
This work addresses optimization under constraints in sequential decision-making for applications like resource allocation, but it is incremental as it builds on existing bandit frameworks with specific cost constraints.
The paper tackles the problem of constrained contextual linear bandits, where an agent aims to maximize cumulative reward while keeping expected costs below a threshold, by proposing an upper-confidence bound algorithm called OPLB and proving a regret bound of ̃O(d√T/(τ-c₀)). It also extends this to multi-armed bandits with a more efficient algorithm achieving ̃O(√KT/(τ-c₀)) regret, showing a √K improvement over a naive approach.
We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies, whose expected cumulative reward over the course of $T$ rounds is maximum, and each has an expected cost below a certain threshold $τ$. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB), and prove an $\widetilde{\mathcal{O}}(\frac{d\sqrt{T}}{τ-c_0})$ bound on its $T$-round regret, where the denominator is the difference between the constraint threshold and the cost of a known feasible action. We further specialize our results to multi-armed bandits and propose a computationally efficient algorithm for this setting. We prove a regret bound of $\widetilde{\mathcal{O}}(\frac{\sqrt{KT}}{τ- c_0})$ for this algorithm in $K$-armed bandits, which is a $\sqrt{K}$ improvement over the regret bound we obtain by simply casting multi-armed bandits as an instance of contextual linear bandits and using the regret bound of OPLB. We also prove a lower-bound for the problem studied in the paper and provide simulations to validate our theoretical results.