Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints

Bandit problems with long-term constraints are challenging due to the need for algorithms performing optimally under both stochastic and adversarial conditions. Prior works using primal-dual methods often impose strong assumptions, such as the Slater’s condition and knowledge of a lower bound on the Slater’s parameter, leading to suboptimal performance. These methods also typically exhibit non-optimal dependencies on the number of constraints.

This research introduces a new algorithm based on optimistic estimations of constraints using a UCB-like approach. Surprisingly, this simple method provides optimal performance in both stochastic and adversarial settings. The key innovation lies in designing adaptive weights that effectively handle different constraint types. The algorithm offers a significantly cleaner analysis than previous primal-dual methods and achieves logarithmic dependence on the number of constraints. Furthermore, it provides Õ(VT) regret without requiring Slater’s condition in the stochastic setting.