# Bandits in Flux: Adversarial Constraints in Dynamic Environments

arXiv: https://arxiv.org/abs/2601.19867 · HTML: https://mlsanity.com/paper/2601.19867/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 57 references that are in the map.
- First posted on arXiv 27 Jan 2026.

## Builds on (most cited first, 24 of 24)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [Stochastic Bandits for Multi-platform Budget Optimization in Online Advertising](https://mlsanity.com/paper/2103.10246/) (2021)
- [Bandit Convex Optimization for Scalable and Dynamic IoT Management](https://mlsanity.com/paper/1707.09060/) (2017)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [No-Regret Algorithms for Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2102.06296/) (2021)
- [Censored Semi-Bandits: A Framework for Resource Allocation with Censored Feedback](https://mlsanity.com/paper/1909.01504/) (2019)
- [Online Convex Optimization with Perturbed Constraints](https://mlsanity.com/paper/1906.00049/) (2019)
- [Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints](https://mlsanity.com/paper/2312.10303/) (2023)
- [Interference Constrained Beam Alignment for Time-Varying Channels via Kernelized Bandits](https://mlsanity.com/paper/2207.00908/) (2022)
- [Solving Combinatorial Games using Products, Projections and Lexicographically Optimal Bases](https://mlsanity.com/paper/1603.00522/) (2016)
- [Diversity-Preserving K-Armed Bandits, Revisited](https://mlsanity.com/paper/2010.01874/) (2020)
- [Queue Scheduling with Adversarial Bandit Learning](https://mlsanity.com/paper/2303.01745/) (2023)
- [A Restless Bandit Model for Resource Allocation, Competition and Reservation](https://mlsanity.com/paper/1804.02100/) (2018)
- [Bridging Adversarial and Nonstationary Multi-armed Bandit](https://mlsanity.com/paper/2201.01628/) (2022)
- [Adversarial Bandits against Arbitrary Strategies](https://mlsanity.com/paper/2205.14839/) (2022)
- [Learning to Schedule Online Tasks with Bandit Feedback](https://mlsanity.com/paper/2402.16463/) (2024)

## Abstract (arXiv)

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.