Exploration-free reinforcement learning with linear function approximation

In the context of Markov Decision Processes (MDPs) with linear Bellman completeness, a generalization of linear MDPs, the learning capabilities of a \emph{greedy} algorithm are reconsidered. The motivation is that, when exploration is costly or dangerous, an exploration-free approach may be preferable to optimistic or randomized solutions. In this thesis is shown that, under a condition of sufficient diversity in the feature distribution, Least-Squares Value Iteration (LSVI) can achieve sublinear regret. Specifically, the expected cumulative regret is at most \( \mathcal{\tilde{O}}(H^3\sqrt{dK/\lambda_0}) \), where \( K \) is the number of episodes, $H$ is the task horizon, $d$ is the dimension of the feature map and $\lambda_0$ is a measure of feature diversity. The theoretical findings are empirically validated on synthetic linear MDPs. This analysis is a first step towards exploration-free reinforcement learning in MDPs with large state spaces.

Nel contesto dei Markov Decision Processes (MDPs) con linear Bellman completeness, una generalizzazione dei linear MDPs, le capacità di apprendimento di un algoritmo \emph{greedy} vengono riconsiderate. La motivazione è che, quando l’esplorazione è costosa o rischiosa, un approccio privo di esplorazione può essere preferibile rispetto a soluzioni ottimistiche o casuali. In questa tesi si dimostra che, sotto una condizione di sufficiente diversità nella distribuzione delle features, Least-Squares Value Iteration (LSVI) può raggiungere un regret sublineare. In particolare, il regret cumulativo atteso è al massimo \( \mathcal{\tilde{O}}(H^3\sqrt{dK/\lambda_0}) \), dove \( K \) è il numero di episodi, \( H \) è l'orizzonte, \( d \) è la dimensione delle features e \( \lambda_0 \) è una misura della diversità delle features. I risultati teorici sono validati empiricamente su linear MDPs sintetici. Questa analisi rappresenta un primo passo verso il reinforcement learning senza esplorazione in MDPs con spazi degli stati ampi.