Online Episodic Convex Reinforcement Learning
This work solves a generalization of RL to convex losses, which is a foundational problem for AI/ML theory, though it appears incremental as it builds on existing MDP and convex optimization frameworks.
The paper tackles online learning in episodic Markov decision processes with convex objective functions, known as concave utility reinforcement learning (CURL), by introducing the first algorithm achieving near-optimal regret bounds without prior knowledge of transitions, and also addresses a bandit version with sub-linear regret.
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.