Bandits in Flux: Adversarial Constraints in Dynamic Environments
This addresses a challenging problem in online decision-making under constraints, with applications in real-world dynamic environments, though it appears incremental as an extension of existing methods.
The paper tackles adversarial multi-armed bandits with time-varying constraints by proposing a primal-dual algorithm, achieving sublinear dynamic regret and constraint violation with state-of-the-art performance.
We investigate the challenging problem of adversarial multi-armed bandits operating under time-varying constraints, a scenario motivated by numerous real-world applications. To address this complex setting, we propose a novel primal-dual algorithm that extends online mirror descent through the incorporation of suitable gradient estimators and effective constraint handling. We provide theoretical guarantees establishing sublinear dynamic regret and sublinear constraint violation for our proposed policy. Our algorithm achieves state-of-the-art performance in terms of both regret and constraint violation. Empirical evaluations demonstrate the superiority of our approach.