Comprendre les pathologies de l'évaluation approximative des politiques lorsqu'elle est combinée à la cupidité dans l'apprentissage par renforcement.

Résumé

Malgré le succès empirique, la théorie de l'apprentissage par renforcement (RL) avec approximation de la fonction de valeur reste fondamentalement incomplète. Des travaux antérieurs ont identifié une variété de comportements pathologiques qui apparaissent dans les algorithmes d'apprentissage par renforcement qui combinent l'évaluation approximative de la politique et l'avidité. L'oscillation des politiques en est un exemple frappant : un algorithme peut passer indéfiniment d'une politique à l'autre, au lieu de converger vers un point fixe. Cependant, la qualité des politiques dans la région d'oscillation n'est pas bien comprise. Dans cet article, nous présentons des exemples simples illustrant qu'en plus de l'oscillation des politiques et des points fixes multiples, le même problème de base peut conduire à la convergence vers la pire politique possible pour une approximation donnée. De tels comportements peuvent survenir lorsque les algorithmes optimisent la précision de l'évaluation pondérée par la distribution des états qui se produisent dans le cadre de la politique actuelle, mais qu'ils se montrent avides en se basant sur la valeur des états qui sont rares ou inexistants dans le cadre de cette distribution. Cela signifie que les valeurs utilisées pour l'avidité ne sont pas fiables et peuvent orienter la politique dans des directions non souhaitées. Notre observation que cela peut conduire à la pire politique possible montre que, dans un sens général, ces algorithmes ne sont pas fiables. L'existence de tels exemples permet de circonscrire le type de garanties théoriques possibles et le type d'idées algorithmiques susceptibles d'être utiles. Nous démontrons analytiquement et expérimentalement que de tels comportements pathologiques peuvent avoir un impact sur un large éventail d'algorithmes de RL et de programmation dynamique ; de tels comportements peuvent apparaître avec et sans bootstrapping, et avec une approximation de fonction linéaire ainsi qu'avec des fonctions paramétrées plus complexes comme les réseaux neuronaux.