No-Regret Reinforcement Learning in Smooth MDPs
This work addresses a major open problem in RL theory for researchers and practitioners dealing with continuous control, though it is incremental in building upon existing structural assumptions.
The paper tackles the open challenge of achieving no-regret guarantees in reinforcement learning for continuous state/action spaces by introducing a novel structural assumption called ν-smoothness, which generalizes previous settings like linear and Lipschitz MDPs, and proposes two algorithms that achieve the best theoretical guarantees compared to state-of-the-art methods.
Obtaining no-regret guarantees for reinforcement learning (RL) in the case of problems with continuous state and/or action spaces is still one of the major open challenges in the field. Recently, a variety of solutions have been proposed, but besides very specific settings, the general problem remains unsolved. In this paper, we introduce a novel structural assumption on the Markov decision processes (MDPs), namely $ν-$smoothness, that generalizes most of the settings proposed so far (e.g., linear MDPs and Lipschitz MDPs). To face this challenging scenario, we propose two algorithms for regret minimization in $ν-$smooth MDPs. Both algorithms build upon the idea of constructing an MDP representation through an orthogonal feature map based on Legendre polynomials. The first algorithm, \textsc{Legendre-Eleanor}, archives the no-regret property under weaker assumptions but is computationally inefficient, whereas the second one, \textsc{Legendre-LSVI}, runs in polynomial time, although for a smaller class of problems. After analyzing their regret properties, we compare our results with state-of-the-art ones from RL theory, showing that our algorithms achieve the best guarantees.