# No-Regret Online Reinforcement Learning with Adversarial Losses and Transitions

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 32 references that are in the map.
- First posted on arXiv 27 May 2023.

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

- [Corruption-robust exploration in episodic reinforcement learning](https://mlsanity.com/paper/1911.08689/) (2019)
- [A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitions](https://mlsanity.com/paper/1805.10066/) (2018)
- [Best of Both Worlds Policy Optimization](https://mlsanity.com/paper/2302.09408/) (2023)

## Built on by (most cited first, 13 of 13)

- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2502.17625/) (2025)
- [Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification](https://mlsanity.com/paper/2410.07533/) (2024)
- [Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints](https://mlsanity.com/paper/2405.14372/) (2024)
- [MetaCURL: Non-stationary Concave Utility Reinforcement Learning](https://mlsanity.com/paper/2405.19807/) (2024)
- [Adaptive Online Non-stochastic Control](https://mlsanity.com/paper/2310.02261/) (2023)
- [Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback](https://mlsanity.com/paper/2510.17103/) (2025)
- [Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback](https://mlsanity.com/paper/2405.00950/) (2024)
- [Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2509.20114/) (2025)
- [Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processes](https://mlsanity.com/paper/2602.01295/) (2026)
- [Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptation](https://mlsanity.com/paper/2602.07205/) (2026)
- [Enhancing Online Reinforcement Learning with Meta-Learned Objective from Offline Data](https://mlsanity.com/paper/2501.07346/) (2025)
- [Truly Adapting to Adversarial Constraints in Constrained MABs](https://mlsanity.com/paper/2602.14543/) (2026)

## Abstract (arXiv)

Existing online learning algorithms for adversarial Markov Decision Processes achieve O(√T) regret after T rounds of interactions even if the loss functions are chosen arbitrarily by an adversary, with the caveat that the transition function has to be fixed. This is because it has been shown that adversarial transition functions make no-regret learning impossible. Despite such impossibility results, in this work, we develop algorithms that can handle both adversarial losses and adversarial transitions, with regret increasing smoothly in the degree of maliciousness of the adversary. More concretely, we first propose an algorithm that enjoys widetildeO(√T + C^textsfP) regret where C^textsfP measures how adversarial the transition functions are and can be at most O(T). While this algorithm itself requires knowledge of C^textsfP, we further develop a black-box reduction approach that removes this requirement. Moreover, we also show that further refinements of the algorithm not only maintains the same regret bound, but also simultaneously adapts to easier environments (where losses are generated in a certain stochastically constrained manner as in Jin et al. [2021]) and achieves widetildeO(U + √UC^textsfL + C^textsfP) regret, where U is some standard gap-dependent coefficient and C^textsfL is the amount of corruption on losses.