# Online Episodic Convex Reinforcement Learning

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

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 32)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [A Divergence Minimization Perspective on Imitation Learning Methods](https://mlsanity.com/paper/1911.02256/) (2019)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Online Convex Optimization in Adversarial Markov Decision Processes](https://mlsanity.com/paper/1905.07773/) (2019)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Risk Averse Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1904.00511/) (2019)
- [Concave Utility Reinforcement Learning: the Mean-Field Game Viewpoint](https://mlsanity.com/paper/2106.03787/) (2021)
- [Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses](https://mlsanity.com/paper/2107.08346/) (2021)
- [Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs](https://mlsanity.com/paper/2006.08040/) (2020)
- [Efficient Risk-Averse Reinforcement Learning](https://mlsanity.com/paper/2205.05138/) (2022)
- [The Importance of Non-Markovianity in Maximum State Entropy Exploration](https://mlsanity.com/paper/2202.03060/) (2022)
- [Challenging Common Assumptions in Convex Reinforcement Learning](https://mlsanity.com/paper/2202.01511/) (2022)
- [An improper estimator with optimal excess risk in misspecified density estimation and logistic regression](https://mlsanity.com/paper/1912.10784/) (2019)
- [An optimal algorithm for bandit convex optimization](https://mlsanity.com/paper/1603.04350/) (2016)
- [Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space](https://mlsanity.com/paper/2306.01854/) (2023)
- [A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs](https://mlsanity.com/paper/2305.08629/) (2023)
- [Apprenticeship Learning via Frank-Wolfe](https://mlsanity.com/paper/1911.01679/) (2019)
- [(Bandit) Convex Optimization with Biased Noisy Gradient Oracles](https://mlsanity.com/paper/1609.07087/) (2016)
- [Online Newton Method for Bandit Convex Optimisation](https://mlsanity.com/paper/2406.06506/) (2024)
- [Online Markov Decision Processes with Aggregate Bandit Feedback](https://mlsanity.com/paper/2102.00490/) (2021)
- [Concentration Bounds for Discrete Distribution Estimation in KL Divergence](https://mlsanity.com/paper/2302.06869/) (2023)
- [Improved Policy Optimization for Online Imitation Learning](https://mlsanity.com/paper/2208.00088/) (2022)

## 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.