Résumé

Cet article analyse les algorithmes d'apprentissage par renforcement (RL) pour les processus de décision de Markov (MDP) sous le critère de la récompense moyenne. Nous nous concentrons sur les algorithmes d'apprentissage Q basés sur l'itération de la valeur relative (RVI), qui sont des analogues stochastiques sans modèle de la méthode RVI classique pour les PDM à récompense moyenne. Ces algorithmes ont une faible complexité par itération, ce qui les rend bien adaptés aux grands problèmes d'espace d'état. Nous étendons l'analyse de convergence presque sûre des algorithmes d'apprentissage RVI Q développée par Abounadi, Bertsekas et Borkar (2001) de l'unichain aux MDP faiblement communicants. Cette extension est importante à la fois sur le plan pratique et sur le plan théorique : les PDM faiblement communicants couvrent un éventail d'applications beaucoup plus large que les PDM unichaîne, et leurs équations d'optimalité ont une structure de solution plus riche (avec de multiples degrés de liberté), ce qui introduit une complexité supplémentaire dans la démonstration de la convergence algorithmique. Nous caractérisons également les ensembles vers lesquels convergent les algorithmes d'apprentissage RVI Q, en montrant qu'ils sont compacts, connectés, potentiellement non convexes et constitués de solutions à l'équation d'optimalité moyenne-récompense, avec exactement un degré de liberté de moins que l'ensemble de solutions général de cette équation. En outre, nous étendons notre analyse à deux algorithmes RL hiérarchiques à récompense moyenne basés sur le RVI en utilisant le cadre des options, en prouvant leur convergence presque sûre et en caractérisant leurs ensembles de convergence sous l'hypothèse que le processus de décision semi-Markov sous-jacent est faiblement communicant.