Comprendre Équation de Bellman
Dans un processus de décision markovien, un agent choisit des actions aux issues incertaines et veut la politique de plus grande récompense actualisée espérée. L’équation de Bellman énonce la relation que les utilités optimales doivent satisfaire : l’utilité d’un état est sa récompense immédiate plus l’utilité espérée actualisée de la meilleure action depuis cet état.
Chaque morceau de cette phrase porte du poids. Le maximum parcourt les actions, que l’agent choisit. La somme à l’intérieur parcourt les états successeurs, que l’agent ne choisit pas : le futur arrive donc comme une moyenne pondérée par le modèle de transition. Intervertir les deux décrirait un agent qui choisit sa propre chance.
C’est une condition et non une recette. Avec n états elle donne n équations à n inconnues, mais le maximum les rend non linéaires, si bien qu’on ne les résout pas directement. L’itération sur les valeurs applique le membre de droite comme une mise à jour et converge parce que cette mise à jour est contractante ; l’itération sur les politiques alterne entre l’évaluation d’une politique fixée, qui EST linéaire, et son amélioration.
Le facteur d’actualisation fait deux choses. Il garde finie, et donc comparable, une suite infinie de récompenses bornées, et il dit que le plus tôt vaut mieux. Sa taille fixe l’horizon effectif : bas, l’agent est myope et ne voit que la récompense immédiate ; proche de 1, il accepte une longue traversée sans récompense pour un gain lointain.
Comment calculer
U(s) = R(s) + \gamma \max_{a \in A(s)} \sum_{s'} P(s' \mid s, a)\, U(s')
où
- U(s)
- l’utilité de l’état s sous une politique optimale
- R(s)
- la récompense immédiate d’être en s
- \gamma
- le facteur d’actualisation, entre 0 et 1
- P(s' \mid s, a)
- la probabilité que l’action a depuis s aboutisse en s'
Exemple : Équation de Bellman
Prenez une actualisation de 0,9. Une récompense à un pas vaut 0,9 de sa valeur faciale, à cinq pas 0,5905, à dix pas 0,3487 et à cinquante pas 0,0052. Le premier pas où une récompense vaut moins d’un pour cent de sa valeur faciale est le pas 44, ce qui est une définition utilisable de l’horizon qu’implique cette actualisation.
Ce nombre bouge fortement avec l’actualisation, et c’est pourquoi celle-ci est un choix de modélisation et non un bouton de réglage. À 0,99 le même seuil d’un pour cent se situe au-delà du pas 450 ; à 0,5 il arrive au pas 7.
La structure compte autant que l’arithmétique. Dans un monde en grille avec un petit coût de séjour, une action qui laisse l’agent sur place ne peut jamais battre une action qui le rapproche d’un meilleur état, si myope que soit l’actualisation : rester vaut R + gamma U(s) et bouger vaut R + gamma U(s'), donc la comparaison se réduit à U(s') contre U(s) et l’actualisation se simplifie entièrement.
Questions fréquentes
Pourquoi ne peut-on pas simplement résoudre les équations ?
À cause du maximum. Pour une politique FIXÉE le max disparaît et il reste un système linéaire, soluble directement, ce que fait exactement l’étape d’évaluation de l’itération sur les politiques.
Que se passe-t-il à une actualisation exactement égale à 1 ?
La somme peut ne pas converger, et deux politiques de récompense totale infinie ne se comparent pas. Cela ne s’utilise que si toute exécution atteint sûrement un état terminal, ou si l’on emploie la récompense moyenne par pas au lieu de la récompense totale.
En résumé
L’équation de Bellman dit ce que les utilités optimales doivent satisfaire : la récompense maintenant, plus une moyenne actualisée sur les issues que vous ne contrôlez pas, de la meilleure action que vous contrôlez. C’est une condition plutôt qu’une méthode, et le max est ce qui la rend intéressante et ce qui l’empêche d’être de l’algèbre linéaire.