Theoretical guarantees for reinforcement learning in continuous state and action spaces

Adapting reinforcement learning to Markov decision processes with continuous state and action spaces is crucial for many real-world applications, particularly in robotics and control. From a theoretical perspective, however, this regime remains poorly understood: while tight guarantees exist for tabular MDPs, a general theory with provably efficient algorithms for the continuous case is still lacking. In this thesis, we introduce a new class of problems, Smooth MDPs, which provides a unifying framework for reinforcement learning in continuous environments. Smooth MDPs are defined through functional regularity assumptions on the Bellman operator and on reward and transition dynamics. This framework rigorously generalizes several models studied in the literature, including continuous bandits, LQRs and their extensions, Lipschitz and kernelized MDPs. Although Sobolev-Hölder-type assumptions are central to nonparametric regression and have recently been explored in bandit problems, prior to this work, a systematic treatment in the context of reinforcement learning was still missing. From a statistical perspective, we characterize the complexity of Smooth MDPs and demonstrate that, in the presence of a simulator, an algorithm with minimax-optimal sample complexity (with near-log factors) exists. In the online interaction scenario, we propose three algorithms for Smooth MDPs, each associated with a different learning objective, and analyze their performance by obtaining regret bounds that explicitly depend on the degree of process regularity. These results generalize classical bounds for simpler classes and improve the state of the art for kernelized MDPs with Matérn kernels.

Adattare l’apprendimento per rinforzo a processi decisionali di Markov con spazi di stato e azione continui è cruciale per molte applicazioni reali, in particolare in robotica e controllo. Dal punto di vista teorico, tuttavia, questo regime rimane poco compreso: mentre per gli MDP tabulari esistono garanzie nette, nel caso continuo manca ancora una teoria generale con algoritmi dimostrabilmente efficienti. In questa tesi introduciamo una nuova classe di problemi, gli MDP Lisci, che fornisce un quadro unificante per l’apprendimento per rinforzo in ambienti continui. Gli MDP Lisci sono definiti tramite ipotesi di regolarità funzionale sull’operatore di Bellman e sulle dinamiche di ricompensa e transizione. Questo framework generalizza in modo rigoroso diversi modelli studiati in letteratura, tra cui banditi continui, LQR e loro estensioni, MDP lipschitziani e kernelizzati. Nonostante ipotesi di tipo Sobolev-Hölder siano centrali nella regressione non parametrica e recentemente esplorate nei problemi bandit, prima di questo lavoro mancava una trattazione sistematica nel contesto dell’apprendimento per rinforzo. Dal punto di vista statistico, caratterizziamo la complessità degli MDP Lisci e dimostriamo che, in presenza di un simulatore, esiste un algoritmo con complessità campionaria minimax-ottimale (a fattori logaritmici). Nel regime di interazione online, proponiamo tre algoritmi per gli MDP Lisci, ciascuno associato a un diverso obiettivo di apprendimento, e ne analizziamo le prestazioni ottenendo limiti di regret che dipendono esplicitamente dal grado di regolarità del processo. Questi risultati generalizzano limiti classici per classi più semplici e migliorano lo stato dell’arte per MDP kernelizzati con kernel Matérn.