PDM et équation de Bellman

La recherche supposait que vos actions font ce que vous voulez. Abandonnez cette hypothèse - laissez une action réussir la plupart du temps et déraper de temps en temps - et une suite fixe de coups cesse d’être une réponse utile. Ce qu’il vous faut à la place est une règle qui vous dit quoi faire depuis là où vous finissez réellement.

Les cinq parties

Un processus de décision markovien est un problème de décision séquentielle dans un environnement pleinement observable et stochastique. Il est spécifié par :

Deux d’entre elles pèsent plus lourd qu’il n’y paraît.

Le modèle de transition est là où vit l’incertitude. $P(s' \mid s, a)$ est une distribution, non une issue. Tenter d’aller à droite peut vous y mener avec probabilité $0.8$ et vous laisser sur place avec probabilité $0.2$. L’agent ne choisit pas $s'$ ; il ne choisit que $a$.

La propriété de Markov est l’hypothèse qui rend cela traitable. L’état suivant dépend de l’état et de l’action courants seuls - non de la manière dont vous êtes arrivé. C’est une vraie restriction, et c’est elle qui permet d’attacher un nombre à chaque état plutôt qu’à chaque historique possible.

La récompense sur l’état. Ce cours suit Russell et Norvig, où la récompense s’attache à l’état où vous êtes, notée $R(s)$. Une grande partie de la littérature l’attache plutôt à la transition, $R(s,a,s')$. La théorie est la même dans les deux cas, mais les équations diffèrent : attendez-vous à cet écart en comparant les sources.

Pourquoi la réponse est une politique

Comme les issues sont stochastiques, un plan comme « droite, droite, haut » ne vaut rien : le premier dérapage vous met quelque part que la suite du plan ne traite plus.

La réponse est une politique $\pi(s)$ - une action recommandée pour chaque état. Elle ne cesse jamais d’être applicable, car quoi qu’il arrive, vous êtes dans un état et la politique a une réponse pour lui. Une politique optimale $\pi^*$ est une politique qui maximise l’utilité espérée.

Ce dont dépend la meilleure politique. La figure ci-dessous est le monde 4x3 de Russell et Norvig : quatre cases sur trois dont une bloquée par un mur, et deux sorties valant $+1$ et $-1$. Son modèle de transition est un peu plus riche que celui décrit plus haut : chaque mouvement va dans la direction voulue avec probabilité $0.8$ et de chaque côté avec $0.1$, et il n’y a pas d’actualisation. La seule chose que vous déplacez est la récompense de survie R, le $R(s)$ que paie chaque case non terminale, et la politique optimale en est une fonction en escalier : à huit seuils, la flèche d’une case bascule. Le bouton le -0.04 des manuels la ramène à la valeur qu’utilisent Russell et Norvig.

L’équation de Bellman

Supposez que vous connaissiez déjà $U(s)$, l’utilité de chaque état. Alors la valeur d’être en $s$ se décompose en ce que vous encaissez maintenant et ce que vous pouvez espérer ensuite :

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

Lisez-la lentement, car chaque morceau travaille :

• $R(s)$ - encaissée pour être en $s$, quoi que vous fassiez ensuite.
• $\max_a$ - vous choisissez l’action, vous prenez donc la meilleure disponible.
• $\sum_{s'} P(s' \mid s,a) U(s')$ - vous ne choisissez pas l’issue, l’avenir est donc une moyenne pondérée par le modèle de transition.
• $\gamma$ - actualise cet avenir par rapport au présent.

L’ordre compte : maximiser sur ce que vous contrôlez, moyenner sur ce que vous ne contrôlez pas.

C’est une condition, non une recette. Elle ne dit rien sur la manière de trouver $U$ ; elle dit seulement que le vrai $U$ doit la satisfaire en chaque état simultanément. Avec $n$ états vous obtenez $n$ équations à $n$ inconnues - mais elles sont non linéaires, car $\max$ n’est pas un opérateur linéaire : vous ne pouvez pas simplement les résoudre par l’algèbre linéaire. Passer de cette condition à des nombres effectifs est l’objet de la leçon suivante.

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.

Pourquoi actualiser

Avec $\gamma < 1$, une récompense située à $k$ pas vaut $\gamma^k$ fois sa valeur faciale. Deux raisons à cela :

1. Cela borne le total. Une suite infinie de récompenses bornées sommerait sinon à l’infini, et les infinis ne se comparent pas.
2. Cela exprime une préférence réelle. Plus tôt vaut généralement mieux.

À $\gamma = 0$ l’agent est myope, ne se souciant que de $R(s)$. Quand $\gamma \to 1$ il devient prévoyant, prêt à accepter une longue traversée sans récompense pour un gros gain à la fin.

Essayez-le en direct. Regardez les probabilités d’occupation évoluer à partir des seuls taux de transition, sans politique en jeu. Celle-ci est une chaîne à temps continu dotée d’un état de panne absorbant : elle ne se stabilise donc jamais, et sur l’horizon affiché la masse s’écoule régulièrement vers failed.

Avant le quiz

Sachez lister les cinq parties, énoncer ce que la propriété de Markov interdit, expliquer pourquoi une politique bat un plan sous incertitude, et désigner quel terme de l’équation de Bellman est une maximisation et lequel est une espérance - et pourquoi ils ne sont pas interchangeables. L’article compagnon Les processus de décision markoviens dérive la même matière plus longuement.