Apprentissage par renforcement quasi minimal optimal pour les processus de décision de Markov à mélange linéaire

Résumé

Nous étudions l'apprentissage par renforcement (RL) avec approximation de fonction linéaire où le noyau de probabilité de transition sous-jacent du processus de décision de Markov (MDP) est un modèle de mélange linéaire (Jia et al., 2020 ; Ayoub et al., 2020 ; Zhou et al., 2020) et l'agent d'apprentissage a accès à un oracle d'intégration ou d'échantillonnage des noyaux de base individuels. Nous proposons une nouvelle inégalité de concentration de type Bernstein pour les martingales auto-normalisées pour les problèmes de bandits linéaires avec un bruit limité. Sur la base de cette nouvelle inégalité, nous proposons un nouvel algorithme efficace en termes de calcul avec approximation de fonction linéaire, appelé UCRL-VTR+, pour les MDP de mélange linéaire susmentionnés dans le cadre épisodique non actualisé. Nous montrons que UCRL-VTR+ atteint un regret Õ (dHT‾‾√) où d est la dimension de la cartographie des caractéristiques, H est la longueur de l'épisode et T est le nombre d'interactions avec le MDP. Nous prouvons également une borne inférieure d'appariement Ω(dHT‾‾√) pour ce paramètre, ce qui montre que UCRL-VTR+ est optimal minimax jusqu'à des facteurs logarithmiques. De plus, nous proposons l'algorithme UCLK+ pour la même famille de MDPs sous actualisation et montrons qu'il atteint un Õ (dT‾‾√/(1-γ)1,5) regret, où γ∈[0,1) est le facteur d'actualisation. Notre borne supérieure correspond à la borne inférieure Ω(dT‾‾√/(1-γ)1,5) prouvée par Zhou et al. (2020) jusqu'à des facteurs logarithmiques, ce qui suggère que UCLK+ est presque optimal minimax. À notre connaissance, il s'agit des premiers algorithmes efficaces en termes de calcul et presque minimax optimaux pour RL avec approximation linéaire des fonctions.