Apprentissage par renforcement spartiate en ligne

Résumé

Nous étudions la dureté de l'apprentissage par renforcement en ligne dans un processus de décision de Markov (PDM) linéaire clairsemé à horizon fixe, avec un accent particulier sur le régime de haute dimension où la dimension ambiante est plus grande que le nombre d'épisodes. Notre contribution est double. Premièrement, nous fournissons une borne inférieure montrant que le regret linéaire est généralement inévitable dans ce cas, même s'il existe une politique qui collecte des données bien conditionnées. La construction de la borne inférieure utilise un MDP avec un nombre fixe d'états tandis que le nombre d'actions s'échelonne avec la dimension ambiante. Notez que lorsque l'horizon est fixé à un, le cas des bandits stochastiques linéaires, le regret linéaire peut être évité. Deuxièmement, nous montrons que si l'apprenant a accès à l'oracle d'une politique qui recueille des données bien conditionnées, une variante du Lasso équipée de l'itération Q a un regret presque sans dimension de Õ (s2/3N2/3) où N est le nombre d'épisodes et s est le niveau de sparsité. Cela montre que dans le cadre d'une action de grande envergure, la difficulté de l'apprentissage peut être attribuée à la difficulté de trouver une bonne politique exploratoire.