mlsanityData to 14 Oct 2026

Scale-free Adversarial Reinforcement Learning

arXiv 2403.00930 ↗First posted 1 Mar 2024cs.LG cs.AIcited by 2

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

This paper initiates the study of scale-free learning in Markov Decision Processes (MDPs), where the scale of rewards/losses is unknown to the learner. We design a generic algorithmic framework, underlineScale underlineClipping underlineBound (textttSCB), and instantiate this framework in both the adversarial Multi-armed Bandit (MAB) setting and the adversarial MDP setting. Through this framework, we achieve the first minimax optimal expected regret bound and the first high-probability regret bound in scale-free adversarial MABs, resolving an open problem raised in citehadiji2023adaptation. On adversarial MDPs, our framework also give birth to the first scale-free RL algorithm with a tildeO(√T) high-probability regret guarantee.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 20 of its 32 references that are in the map. First posted on arXiv 1 Mar 2024.

Builds on

20 of 32 references.

References · 20

  1. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  2. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  3. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  4. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  5. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  6. 2016Scale-Free Online Learningcited by 85
  7. 2013Follow the Leader If You Can, Hedge If You Mustcited by 70
  8. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  9. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 51
  10. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  11. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 43
  12. 2023Unconstrained Online Learning with Unbounded Lossescited by 25
8 more
  1. 2017Sparsity, variance and curvature in multi-armed banditscited by 24
  2. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  3. 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 17
  4. 2020Adaptation to the Range in K-Armed Banditscited by 13
  5. 2022Scale-free Unconstrained Online Learning for Curved Lossescited by 13
  6. 2021Scale Free Adversarial Multi Armed Banditscited by 12
  7. 2023Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learningcited by 7
  8. 2023Improved Algorithms for Adversarial Bandits with Unbounded Lossescited by 3

Built on by

Cited by year

Citing papers per year: 2024: 2.

2 papers.

  1. 2024uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABscited by 8
  2. 2024State-free Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Learning Adversarial MDPs with Stochastic Hard Constraints
  2. 2026Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints
  3. 2025Provably Invincible Adversarial Attacks on Reinforcement Learning Systems: A Rate-Distortion Information-Theoretic Approach
  4. 2025Towards Optimal Adversarial Robust Reinforcement Learning with Infinity Measurement Error
  5. 2024Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints
  6. 2024No-Regret Reinforcement Learning in Smooth MDPs
  7. 2025Regret Bounds for Robust Online Decision Making
  8. 2024Horizon-Free Regret for Linear Markov Decision Processes