Bandits in Flux: Adversarial Constraints in Dynamic Environments

Tareq Si Salem
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:4969-4977, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-salem26a, title = { Bandits in Flux: Adversarial Constraints in Dynamic Environments }, author = {Salem, Tareq Si}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {4969--4977}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/salem26a/salem26a.pdf}, url = {https://proceedings.mlr.press/v300/salem26a.html}, abstract = { 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. } }
Endnote
%0 Conference Paper %T Bandits in Flux: Adversarial Constraints in Dynamic Environments %A Tareq Si Salem %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-salem26a %I PMLR %P 4969--4977 %U https://proceedings.mlr.press/v300/salem26a.html %V 300 %X 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.
APA
Salem, T.S.. (2026). Bandits in Flux: Adversarial Constraints in Dynamic Environments . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:4969-4977 Available from https://proceedings.mlr.press/v300/salem26a.html.

Related Material