mlsanityData to 14 Oct 2026

Online Episodic Convex Reinforcement Learning

arXiv 2505.07303 ↗First posted 12 May 2025cs.LG stat.MLcited by 0

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

Abstract (arXiv)

We study online learning in episodic finite-horizon Markov decision processes (MDPs) with convex objective functions, known as the concave utility reinforcement learning (CURL) problem. This setting generalizes RL from linear to convex losses on the state-action distribution induced by the agent's policy. The non-linearity of CURL invalidates classical Bellman equations and requires new algorithmic approaches. We introduce the first algorithm achieving near-optimal regret bounds for online CURL without any prior knowledge on the transition function. To achieve this, we use an online mirror descent algorithm with varying constraint sets and a carefully designed exploration bonus. We then address for the first time a bandit version of CURL, where the only feedback is the value of the objective function on the state-action distribution induced by the agent's policy. We achieve a sub-linear regret bound for this more challenging problem by adapting techniques from bandit convex optimization to the MDP setting.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 32 of its 56 references that are in the map. First posted on arXiv 12 May 2025.

Builds on

32 of 56 references.

References · 32

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  3. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  4. 2018Provably Efficient Maximum Entropy Explorationcited by 242
  5. 2019A Divergence Minimization Perspective on Imitation Learning Methodscited by 190
  6. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  7. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  8. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
  9. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  10. 2021Reward is enough for convex MDPscited by 84
  11. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  12. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
20 more
  1. 2016Kernel-based methods for bandit convex optimizationcited by 63
  2. 2019Risk Averse Robust Adversarial Reinforcement Learningcited by 57
  3. 2021Concave Utility Reinforcement Learning: the Mean-Field Game Viewpointcited by 56
  4. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  5. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 51
  6. 2022Efficient Risk-Averse Reinforcement Learningcited by 43
  7. 2022The Importance of Non-Markovianity in Maximum State Entropy Explorationcited by 35
  8. 2022Challenging Common Assumptions in Convex Reinforcement Learningcited by 30
  9. 2019An improper estimator with optimal excess risk in misspecified density estimation and logistic regressioncited by 25
  10. 2016An optimal algorithm for bandit convex optimizationcited by 20
  11. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  12. 2023A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPscited by 15
  13. 2019Apprenticeship Learning via Frank-Wolfecited by 13
  14. 2016(Bandit) Convex Optimization with Biased Noisy Gradient Oraclescited by 12
  15. 2024Online Newton Method for Bandit Convex Optimisationcited by 12
  16. 2021Online Markov Decision Processes with Aggregate Bandit Feedbackcited by 10
  17. 2023Concentration Bounds for Discrete Distribution Estimation in KL Divergencecited by 7
  18. 2022Improved Policy Optimization for Online Imitation Learningcited by 6
  19. 2023Efficient Model-Based Concave Utility Reinforcement Learning through Greedy Mirror Descentcited by 6
  20. 2020Kullback-Leibler-Quadratic Optimal Controlcited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learning
  2. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  3. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
  4. 2026Learning Markov Decision Processes under Fully Bandit Feedback
  5. 2021Fast Rates for the Regret of Offline Reinforcement Learning
  6. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
  7. 2026Mathematical methods of reinforcement learning
  8. 2024Inverse Concave-Utility Reinforcement Learning is Inverse Game Theory