![[2602.07418] Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Losses](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.07418] Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Losses
Summary
This paper presents an algorithm that achieves optimal static and dynamic regret simultaneously in adversarial multi-armed bandits with deterministic losses, addressing a significant gap in existing literature.
Why It Matters
Understanding how to achieve optimal regret in multi-armed bandit scenarios is crucial for developing more efficient algorithms in machine learning. This research provides insights into the performance of algorithms against different adversarial models, which can enhance decision-making processes in various applications.
Key Takeaways
- The paper extends the impossibility results for static and dynamic regret to deterministic losses.
- An algorithm is introduced that achieves optimal regret against an oblivious adversary.
- The findings highlight the differences in performance between adaptive and oblivious adversaries.
- The research offers a new model selection procedure that may have broader implications in bandit problems.
- This work contributes to the ongoing discussion about regret benchmarks in machine learning.
Computer Science > Machine Learning arXiv:2602.07418 (cs) [Submitted on 7 Feb 2026 (v1), last revised 17 Feb 2026 (this version, v2)] Title:Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Losses Authors:Jian Qian, Chen-Yu Wei View a PDF of the paper titled Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Losses, by Jian Qian and Chen-Yu Wei View PDF HTML (experimental) Abstract:In adversarial multi-armed bandits, two performance measures are commonly used: static regret, which compares the learner to the best fixed arm, and dynamic regret, which compares it to the best sequence of arms. While optimal algorithms are known for each measure individually, there is no known algorithm achieving optimal bounds for both simultaneously. Marinov and Zimmert [2021] first showed that such simultaneous optimality is impossible against an adaptive adversary. Our work takes a first step to demonstrate its possibility against an oblivious adversary when losses are deterministic. First, we extend the impossibility result of Marinov and Zimmert [2021] to the case of deterministic losses. Then, we present an algorithm achieving optimal static and dynamic regret simultaneously against an oblivious adversary. Together, they reveal a fundamental separation between adaptive and oblivious adversaries when multiple regret benchmarks are considered simultaneously. It also provides new insight into the long open problem...
