Les processus de décision markoviens

La recherche adversariale et le minimax planifiait contre un adversaire, mais supposait le monde lui-même fiable : jouez un coup et l’échiquier change exactement comme prévu. Les environnements réels ne sont pas si obligeants. Un robot à qui l’on ordonne d’avancer peut dériver ; une recommandation peut être suivie ou non. Les actions ont des distributions de probabilité sur les issues, non des issues uniques.

Un processus de décision markovien est le formalisme standard de cette situation, et c’est le socle sur lequel tout l’apprentissage par renforcement est bâti.

A. Les ingrédients

Un PDM est spécifié par quatre choses :

• un ensemble d’états $s$ ;
• un ensemble d’actions $A(s)$ disponibles dans chaque état ;
• un modèle de transition $P(s' \mid s, a)$, la probabilité d’atterrir en $s'$ quand l’action $a$ est prise en $s$ ;
• une fonction de récompense $R(s)$.

Le nom vient de la propriété de Markov : la probabilité de l’état suivant ne dépend que de l’état et de l’action courants, non de l’historique du chemin parcouru. C’est ce qui rend le problème traitable - l’état courant est un résumé suffisant du passé.

Une note sur l’emplacement de la récompense. D’après Russell et Norvig, la récompense $R(s)$ est ici attachée à l’état où se trouve l’agent, et apparaît en dehors de la maximisation comme de l’espérance. Une grande partie de la littérature d’apprentissage par renforcement écrit plutôt $R(s, a, s')$, une récompense sur la transition, ce qui la déplace à l’intérieur de la somme. Les deux formulations sont équivalentes pour notre propos, mais les équations diffèrent : il vaut donc la peine de savoir quelle convention vous lisez.

Une politique $\pi$ est une fonction recommandant une action pour chaque état - non un plan pour une éventualité, mais une règle complète de comportement. Résoudre un PDM, c’est trouver une bonne politique.

B. Pourquoi actualiser

L’utilité d’exécuter une politique $\pi$ depuis l’état $s$ est la somme espérée des récompenses le long du chemin :

$$U^{\pi}(s) = E\left[\sum_{t=0}^{\infty} \gamma^{t} R(S_t)\right],$$

où $S_t$ est l’état atteint au temps $t$ et $\gamma \in [0, 1]$ est le facteur d’actualisation. L’actualisation n’est pas une technicité ajoutée par commodité. Si l’agent peut ne jamais atteindre un état terminal, les histoires sont infiniment longues et les sommes non actualisées divergent en général - et comparer deux politiques valant toutes deux $+\infty$ n’est pas une question bien posée.

Avec $\gamma < 1$ et des récompenses bornées par $R_{\max}$, la série géométrique règle l’affaire :

$$U([s_0, s_1, s_2, \dots]) = \sum_{t=0}^{\infty} \gamma^{t} R(s_t) \;\le\; \sum_{t=0}^{\infty} \gamma^{t} R_{\max} = \frac{R_{\max}}{1 - \gamma}.$$

Toute utilité est finie, donc toute paire de politiques est comparable. Un $\gamma$ proche de $0$ rend l’agent myope ; $\gamma = 1$ retrouve des récompenses simplement additives, ce qui n’est sûr que si l’agent atteindra à coup sûr un état terminal - une politique offrant cette garantie est dite propre.

Une politique optimale est alors $\pi^{*} = \arg\max_{\pi} U^{\pi}(s)$. Une conséquence agréable des récompenses actualisées à horizon infini est que $\pi^{*}$ ne dépend pas de l’état de départ : on peut donc parler de la politique optimale et écrire $U(s)$ pour l’utilité sous celle-ci.

$U(s)$ et $R(s)$ sont des quantités différentes. $R(s)$ est la récompense à court terme d’être en $s$ ; $U(s)$ est le total à long terme depuis $s$. Les confondre est la source de confusion la plus fréquente dans cette matière.

C. L’équation de Bellman

Voici l’idée centrale. L’utilité d’un état est sa récompense immédiate plus l’utilité espérée actualisée de là où la meilleure action vous mène :

$$U(s) = R(s) + \gamma \max_{a \in A(s)} \sum_{s'} P(s' \mid s, a)\, U(s').$$

C’est l’équation de Bellman, d’après Richard Bellman (1957). Lisez-la lentement : le $\max$ choisit la meilleure action, la $\sum$ moyenne sur les endroits où cette action peut réellement vous mener, et $\gamma$ actualise le futur par rapport au présent.

S’il y a $n$ états, il y a $n$ telles équations à $n$ inconnues. Elles ne sont pas linéaires, car $\max$ n’est pas un opérateur linéaire - on ne peut donc pas simplement inverser une matrice et en finir.

L'ordre des opérations est ce qu'une formule ne montre pas, alors la figure ci-dessous le démonte. Chaque action a sa propre ligne, avec sa propre moyenne sur les issues qu'elle ne contrôle pas, et le maximum se prend visiblement entre les lignes plutôt qu'à l'intérieur d'un symbole. Faites glisser le facteur d'actualisation pour voir le terme futur naître de rien : à zéro l'agent ne voit que le coût de la vie, près de un il est dominé par une récompense située plusieurs pas plus loin.

D. L’itération sur les valeurs, menée jusqu’à convergence

Le remède est d’itérer. Partez d’utilités arbitraires, évaluez le membre de droite, et utilisez le résultat comme nouveau membre de gauche. Répétez.

Prenons un monde à quatre états. Deux états non terminaux, $s_1$ et $s_2$, chacun avec $R(s) = -0.04$ - une petite pénalité par pas, qui encourage à finir. Deux terminaux : GOAL d’utilité $+1$ et PIT de $-1$. Posons $\gamma = 0.9$.

Initialisons $U(s_1) = U(s_2) = 0$.

Balayage 1. Pour $s_2$, Right donne $0.8(1) + 0.2(-1) = 0.6$, tandis que Left donne $0.8(0) + 0.2(0) = 0$. Donc

$$U(s_2) = -0.04 + 0.9 \times 0.6 = -0.04 + 0.54 = 0.50 .$$

Pour $s_1$, les deux actions ne voient encore que des zéros, donc $U(s_1) = -0.04 + 0.9 \times 0 = -0.04$.

Balayage 2. Désormais $s_1$ voit la valeur apparue en $s_2$. Right donne $0.8(0.50) + 0.2(-0.04) = 0.400 - 0.008 = 0.392$, battant le $-0.04$ de Stay :

$$U(s_1) = -0.04 + 0.9 \times 0.392 = -0.04 + 0.3528 = 0.3128 .$$

$U(s_2)$ ne bouge pas, ses deux issues étant terminales.

En poursuivant :

Les valeurs cessent de bouger à $U(s_1) = 0.3902$, $U(s_2) = 0.5000$.

Nous pouvons confirmer ce point fixe exactement plutôt que de faire confiance à l’itération. Une fois Right connue comme la meilleure action en $s_1$, l’équation de Bellman y devient

$$U(s_1) = -0.04 + 0.9\big(0.8 \times 0.5 + 0.2\,U(s_1)\big) = 0.32 + 0.18\,U(s_1),$$

donc $U(s_1) = 0.32 / 0.82 = 0.390243\ldots$, conforme au tableau à quatre décimales.

Lire la politique sur les utilités convergées donne Right dans les deux états, avec des utilités espérées du successeur $\sum_{s'} P(s' \mid s, a)\,U(s')$ de $0.478$ contre $0.390$ en $s_1$, et $0.600$ contre $0.412$ en $s_2$. Ajouter $R(s)$ et actualiser les transforme en valeurs d’action $Q(s, a)$ de l’article suivant : $0.3902$ contre $0.3112$ en $s_1$, et $0.5000$ contre $0.3310$ en $s_2$, avec le même classement.

Son exécution reproduit le tableau ci-dessus et affiche Right pour les deux états.

E. L’itération sur les politiques

L’itération sur les valeurs calcule des utilités à haute précision et lit la politique à la fin. Mais la politique cesse souvent de changer bien avant que les nombres se stabilisent - dans notre monde, Right était optimale en $s_1$ dès le balayage 2, alors que la quatrième décimale a continué de bouger plusieurs balayages de plus. L’itération sur les politiques exploite cela en alternant :

1. Évaluation de la politique - étant donné une politique fixée $\pi_i$, calculer les utilités qu’elle produit.
2. Amélioration de la politique - recalculer la meilleure action dans chaque état à l’aide de ces utilités, donnant $\pi_{i+1}$.

Répétez jusqu’à ce que la politique cesse de changer. Le gain est à l’étape 1 : avec l’action de chaque état fixée par la politique, il ne reste plus de $\max$, et l’équation de Bellman devient

$$U_i(s) = R(s) + \gamma \sum_{s'} P(s' \mid s, \pi_i(s))\, U_i(s') .$$

Ce sont des équations linéaires - $n$ équations, $n$ inconnues, résolubles exactement par l’algèbre linéaire standard en $O(n^3)$. Pour de petits espaces d’états, l’évaluation exacte est souvent l’approche la plus rapide ; pour de grands espaces, le coût cubique mord, et l’on emploie plutôt une évaluation approchée (quelques balayages plutôt qu’une résolution exacte).

F. Ce que cela achète, et ce que cela suppose

Les deux algorithmes livrent une politique optimale pour un PDM connu. Cette hypothèse est celle qui compte : itération sur les valeurs comme sur les politiques exigent d’emblée le modèle de transition $P(s' \mid s, a)$ et la fonction de récompense $R(s)$. Ce sont des algorithmes de planification, non d’apprentissage.

Un agent lâché dans un environnement inconnu n’a ni l’un ni l’autre. Il doit agir, observer ce qui arrive, et s’améliorer - ce qui est le sujet de L’apprentissage par renforcement et le Q-learning.

À retenir

• Un PDM, ce sont des états, des actions, un modèle de transition et des récompenses, la propriété de Markov faisant de l’état courant un résumé suffisant du passé.
• Une politique prescrit une action pour chaque état ; résoudre un PDM, c’est en trouver une optimale.
• L’actualisation garde finies les utilités à horizon infini, bornées par $R_{\max}/(1-\gamma)$, de sorte que les politiques restent comparables.
• L’équation de Bellman $U(s) = R(s) + \gamma \max_a \sum_{s'} P(s' \mid s,a)U(s')$ est non linéaire à cause du $\max$.
• L’itération sur les valeurs l’applique comme mise à jour jusqu’à convergence ; notre monde s’est stabilisé à $U(s_1) = 0.3902$, confirmé exactement par $0.32/0.82$.
• L’itération sur les politiques alterne évaluation et amélioration ; fixer la politique supprime le $\max$ et laisse des équations linéaires.
• Les deux exigent un modèle connu - elles planifient, elles n’apprennent pas.

La suite

L’apprentissage par renforcement et le Q-learning abandonne l’hypothèse d’un modèle connu et apprend un bon comportement à partir de la seule expérience.