Online Episodic Convex Reinforcement Learning

2025/05/12 by Bianca Marin Moreno, Khaled Eldowa, Moreno, Bianca Marin +7
Computer Science · #Adaptive Dynamic Programming Control #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2505.07303

openalex publication_date 2025/05/12 · openalex created_date 2025/10/17 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Online Newton Method for Bandit Convex Optimisation
• Efficient Model-Based Concave Utility Reinforcement Learning through Greedy Mirror Descent
• A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs
• Concentration Bounds for Discrete Distribution Estimation in KL Divergence
• Improved Policy Optimization for Online Imitation Learning
• Efficient Risk-Averse Reinforcement Learning
• The Importance of Non-Markovianity in Maximum State Entropy Exploration
• Challenging Common Assumptions in Convex Reinforcement Learning
• Generalized conditional gradient and learning in potential mean field games
• Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses
• Concave Utility Reinforcement Learning: the Mean-Field Game Viewpoint
• Reward is enough for convex MDPs
• On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
• Online Markov Decision Processes with Aggregate Bandit Feedback
• Variational Policy Gradient Method for Reinforcement Learning with General Utilities
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
• Kullback-Leibler-Quadratic Optimal Control
• Online Learning: A Modern Introduction Using Convex Optimization
• An improper estimator with optimal excess risk in misspecified density estimation and logistic regression
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• A Divergence Minimization Perspective on Imitation Learning Methods
• Apprenticeship Learning via Frank-Wolfe
• Online Convex Optimization in Adversarial Markov Decision Processes
• Risk Averse Robust Adversarial Reinforcement Learning
• Provably Efficient Maximum Entropy Exploration
• More Adaptive Algorithms for Adversarial Bandits
• Minimax Regret Bounds for Reinforcement Learning
• Kernel-based methods for bandit convex optimization
• An optimal algorithm for bandit convex optimization
• (Bandit) Convex Optimization with Biased Noisy Gradient Oracles
• Explore no more: Improved high-probability regret bounds for non-stochastic bandits
• Empirical Bernstein Bounds and Sample Variance Penalization
• Online convex optimization in the bandit setting: gradient descent without a gradient
• Reinforcement Learning: An Introduction

Related

• Efficient Model-Based Concave Utility Reinforcement Learning through Greedy Mirror Descent
• MetaCURL: Non-stationary Concave Utility Reinforcement Learning
• Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewards
• Online Convex Optimization in Adversarial Markov Decision Processes
• Online Convex Optimization Perspective for Learning from Dynamically Revealed Preferences