An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints
Jiahui Zhu, Kihyun Yu, Dabeen Lee, Xin Liu, Honghao Wei · 2025
Read An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints by Jiahui Zhu, Kihyun Yu, Dabeen Lee, Xin Liu, Honghao Wei (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-21841.txt.
Introduction
Jiahui Zhu, Kihyun Yu, Dabeen Lee, Xin Liu, and Honghao Wei design a learning algorithm that stays safe even when the rules keep changing against it. In online safe reinforcement learning, an agent must gain rewards while obeying safety limits modeled as a constrained decision process. Older methods assume the limits behave statistically, and they break when limits are unknown, shifting, or set by an adversary.
Their algorithm, OMDPD, mixes optimism with a mirror descent primal-dual scheme. It provably keeps both regret and safety violations growing only with the square root of the number of rounds, a best-known rate. It needs no slack condition and no known safe policy to start from. Sharper estimates of rewards and transitions improve the bounds further. The authors aim at settings like driving, robotics, and security.
Catalog record
| CREATOR | Jiahui Zhu, Kihyun Yu, Dabeen Lee, Xin Liu, Honghao Wei |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 97 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-21841
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints Jiahui Zhu, Kihyun Yu, Dabeen Lee, Xin Liu, Honghao Wei Abstract Online safe reinforcement learning (RL) plays a key role in dynamic environments, with applications in autonomous driving, robotics, and cybersecurity. The objective is to learn optimal policies that maximize rewards while satisfying safety constraints modeled by constrained Markov decision processes (CMDPs). Existing methods achieve sublinear regret under stochastic constraints but often fail in adversarial settings, where constraints are unknown, time-varying, and potentially adversarially designed. In this paper, we propose the O ptimistic M irror D escent P rimal- D ual (OMDPD) algorithm, the first to address online CMDPs with anytime adversarial constraints. OMDPD achieves optimal regret 𝒪 ~ ( K ) \tilde{\mathcal{O}}(\sqrt{K}) and strong constraint violation 𝒪 ~ ( K ) \tilde{\mathcal{O}}(\sqrt{K}) without relying on Slater’s condition or the existence of a strictly known safe policy. We further show that access to accurate estimates of rewards and transitions can further improve these bounds. Our results offer practical guarantees for safe decision-making in adversarial environments. 1 Introduction Online safe reinforcement learning (RL) has been applied successfully across various domains, including autonomous driving ( Isele et al. 2018 ) , recommender systems ( Chow et al. 2017 ) , and robotics ( Achiam et al. 2017 ) . It enables the efficient development of policies that adhere to essential safety requirements, such as collision avoidance, budget compliance, and reliability. In safe RL, the objective is to learn an optimal policy that maximizes cumulative rewards while satisfying expected cumulative safety constraints when interacting with an unknown environment. These safety-critical sequential decision-making problems are formally modeled as constrained Markov decision processes (CMDPs) ( Altman 1999 ) . We study the problem of learning such policies in episodic CMDPs where the agent must balance exploration and exploitation to minimize strong regret (regret and hard constraint violation), a metric quantifying the cumulative performance loss relative to the optimal safe policy—while avoiding excessive constraint violations. In many practical scenarios, especially in safety-critical applications, the environment is often dynamic, with conditions that can change unpredictably or even adversarially. Relying solely on stationary models can lead to suboptimal or unsafe outcomes, as these models fail to capture the time-varying nature of constraints and system dynamics. For instance, in autonomous driving ( Kirschner et al. 2021 ) , it is crucial to avoid collisions in variable environments influenced by changing traffic flows and weather conditions. Similarly, in cybersecurity ( Yinka-Banjo & Ugot 2020 ) , adversarial CMDPs can model interactions between system defenders and attackers, requiring defenders to make decisions under uncertainty and strict system constraints while accounting for potential adversarial actions. This necessitates the consideration of adversarial settings, where constraints may be unknown, time-dependent, and potentially adversarially designed to challenge the learning process. Existing methods ( Efroni et al. 2020 ; Müller et al. 2023 ; Germano et al. 2023 ; Müller et al. 2024 ; Kitamura et al. 2024 ) provide sublinear regret guarantees for stochastic constraints but struggle to generalize to such adversarial cases. The adversarial setting is inherently more challenging due to the dynamic and unpredictable nature of constraints, compounded by the assumption that error cancellation in constraint violations is not allowed. Adversarial CMDPs are thus crucial for handling dynamic environments, ensuring robust and safe decision-making in situations where conventional stochastic models fall short. Constraint violation is usually used to theoretically evaluate the performance of the safety of a safe RL algorithm. One commonly used constraint violation evaluates the policies in the beverage sense such that it allows error cancellation, as defined by ( Efroni et al. 2020 ) , involves summing positive (unsafe) and negative (safe) constraint violations, ensuring a sublinear total constraint violation during learning. In this paper we consider a stronger notion of constraint violation, focusing exclusively on the sum of positive errors. To illustrate, consider a cost function d(\pi_{k}) , which equals -1 when the policy \pi_{k} used in episode k is safe, and 1 when it is unsafe. If half of the policies over K episodes are safe and the other half are unsafe, the weak constraint violation—permitting cancellation—results in [\sum_{k=1}^{K}d(\pi_{k})]^{+}=0, where [\cdot]^{+}=\max\{\cdot,0\}. However, under strong constraint violation, which disallows cancellation, the total violation becomes \sum_{k=1}^{K}\left[d(\pi_{k})\right]^{+}=K/2. Clearly, weaker sublinear constraint violations do not ensure relatively safe policies during learning. In this work, we aim to address two fundamental research questions: RQ1: Can we design a unified algorithm that achieves the optimal order of regret and hard constraint violation in unknown CMDPs with both stochastic and adversarial costs under minimum assumption? RQ2: What are the bottlenecks for further improving the bound? CMDPs with cumulative constraints that allow cancellation have been extensively studied under both model-free ( Wei et al. 2022a ; Wei et al. 2022b ; Wei et al. 2023 ; Ghosh et al. 2022 ; Bai et al. 2022 ) and model-based approaches ( Ding et al. 2021 ; Liu et al. 2021a ; Bura et al. 2021 ; Singh et al. 2020 ; Ding et al. 2021 ; Chen et al. 2022 ; Efroni et al. 2020 ) . The study by ( Qiu et al. 2020 ; Stradi et al. 2024a ) focuses on CMDPs with only an adversarial reward function. Recent work ( Germano et al. 2023 ; Stradi et al. 2024c ) considers online learning CMDPs under strong constraint violation for the long-term average cost and sublinear regret and violation results are well established. However, we note that in our scenario, the constraints are sufficiently strict—particularly in adversarial settings—that an average safe policy fails to guarantee safety for each individual episode . Consequently, focusing on the long-term average constraint alone is less meaningful under these conditions. Other works such as ( Ding & Lavaei 2022 ; Wei et al. 2023 ) consider scenarios where rewards, costs, and transition kernels are non-stationary, assuming bounded total variation. However, all of the above works we mentioned are not applicable to settings with adversarial costs, and they only address weak constraint violations. Algorithm Regret Adversarial Violation Stochastic Violation Slater’s Condition Known Safe Policy ( Efroni et al. 2020 ) \mathcal{O}(\sqrt{K}) N/A \mathcal{O}(\sqrt{K}) ✓ No ( Müller et al. 2023 ) † \mathcal{O}(\sqrt{K}) N/A \mathcal{O}(\sqrt{K}) ✓ Yes ( Stradi et al. 2024c ) † \tilde{\mathcal{O}}(\sqrt{K}) N/A \tilde{\mathcal{O}}(\sqrt{K}) ✓ No ( Müller et al. 2024 ) † \tilde{\mathcal{O}}(K^{0.93}) N/A \tilde{\mathcal{O}}(K^{0.93}) ✓ No ( Kitamura et al. 2024 ) † \tilde{\mathcal{O}}(K^{\frac{6}{7}}) N/A \tilde{\mathcal{O}}(K^{\frac{6}{7}}) ✓ No OMDPD † \tilde{\mathcal{O}}(\sqrt{K}) \tilde{\mathcal{O}}(\sqrt{K}) \tilde{\mathcal{O}}(\sqrt{K}) ✗ No Table 1: Comparison between OMDPD and existing related work. We omit the dependence on the dimension of the action, state space, and the number of steps in CMDPs here. \dagger: Consider the stronger notion of constraint violation, which disallows cancellation. ( Efroni et al. 2020 ) only consider a weaker version. ( Müller et al. 2024 ) need to access a strictly feasible policy. More discussions can be found in Section 2 . To address the aforementioned challenges, we propose the O ptimistic M irror D escent P rimal- D ual (OMDPD) algorithm that ensures optimal regret and strong constraint violation bounds with respect to the number of episodes K , regardless of whether the reward and cost functions