Amélioration de la limite de regret et de la répétition de l'expérience dans l'itération de politique régularisée

Résumé :

Dans ce travail, nous étudions les algorithmes d'apprentissage dans les processus de décision de Markov (PDM) non actualisés à horizon infini avec approximation de fonction. Nous montrons d'abord que l'analyse du regret de l'algorithme Politex (une version de l'itération de politique régularisée) peut être affinée de O(T^3/4) à O(√T^3/4) sous des hypothèses presque identiques, et nous instancions la borne avec une approximation de fonction linéaire. Notre résultat fournit la première limite de regret O(√T) à haute probabilité pour un algorithme efficace en termes de calcul dans ce contexte. L'implémentation exacte de Politex avec une approximation de fonction de réseau neuronal est inefficace en termes de mémoire et de calcul. Puisque notre analyse suggère que nous devons bien approximer la moyenne des fonctions action-valeur des politiques passées, nous proposons une implémentation simple et efficace où nous entraînons une seule fonction Q sur un tampon de relecture avec les données passées. Nous montrons que cela conduit souvent à des performances supérieures à d'autres choix de mise en œuvre, notamment en termes de temps d'horloge. Notre travail fournit également une nouvelle justification théorique pour l'utilisation du rejeu d'expérience dans les algorithmes d'itération de politique.