Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.21841 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912405208956928 |
|---|---|
| author | Zhu, Jiahui Yu, Kihyun Lee, Dabeen Liu, Xin Wei, Honghao |
| author_facet | Zhu, Jiahui Yu, Kihyun Lee, Dabeen Liu, Xin Wei, Honghao |
| contents | 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 Optimistic Mirror Descent Primal-Dual (OMDPD) algorithm, the first to address online CMDPs with anytime adversarial constraints. OMDPD achieves optimal regret O(sqrt(K)) and strong constraint violation 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_21841 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints Zhu, Jiahui Yu, Kihyun Lee, Dabeen Liu, Xin Wei, Honghao Machine Learning Artificial Intelligence 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 Optimistic Mirror Descent Primal-Dual (OMDPD) algorithm, the first to address online CMDPs with anytime adversarial constraints. OMDPD achieves optimal regret O(sqrt(K)) and strong constraint violation 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. |
| title | An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2505.21841 |