Processus de décision markovien

Bien des problèmes exigent une suite de décisions dont les conséquences se déploient dans le temps et ne sont pas entièrement prévisibles. Le processus de décision markovien en est la formalisation standard. Il spécifie les situations où l’agent peut se trouver, les actions disponibles, la probabilité de passer d’une situation à une autre étant donné une action, et la récompense immédiate reçue.

La propriété de Markov est l’hypothèse simplificatrice qui rend le cadre traitable : la distribution de l’état suivant ne dépend que de l’état courant et de l’action choisie, non de la manière dont l’agent y est parvenu. C’est moins restrictif qu’il n’y paraît d’abord, car tout ce qui, dans l’historique, compte véritablement peut être replié dans la définition de l’état, au prix d’un espace d’états plus grand.

Ce que l’on cherche est une politique, une application des états vers les actions. La valeur d’une politique en un état est la récompense totale espérée si on la suit à partir de là. Comme une bonne décision présente dépend de la valeur des états auxquels elle mène, et que ces valeurs dépendent des décisions ultérieures, le problème est intrinsèquement récursif ; l’équation de Bellman exprime exactement cette cohérence interne et fonde les algorithmes qui résolvent les PDM.

Les récompenses futures sont actualisées par un facteur compris entre zéro et un appliqué à chaque pas. Cela sert deux fins : garder le total fini sur un horizon non borné, et encoder une véritable préférence pour les récompenses plus proches. Un facteur proche de zéro produit un comportement myope, tandis qu’un facteur proche de un produit un comportement prévoyant, au prix d’un apprentissage plus lent et moins stable.

Considérez un robot sur une grille où chaque case est un état et où les actions sont les quatre déplacements cardinaux. Le déplacement est peu fiable : la direction voulue réussit la plupart du temps et dévie occasionnellement de côté. Atteindre la case but rapporte une grande récompense positive, tomber dans un danger une grande récompense négative, et chaque pas ordinaire une petite récompense négative pour décourager la flânerie.

La politique optimale n’est pas simplement le plus court chemin. Comme le déplacement peut déraper, un itinéraire passant juste à côté d’un danger comporte un risque réel d’y tomber, et la politique peut préférer un trajet plus long qui garde ses distances. La fonction de valeur encode cela en attribuant une valeur plus faible aux états voisins des dangers.

Le petit coût par pas compte plus qu’il n’y paraît. Sans lui, une politique qui errerait indéfiniment sans jamais atteindre le danger ne perdrait rien, et l’agent n’aurait aucune incitation à terminer. La conception des récompenses de ce genre est là où réside en réalité l’essentiel de la difficulté pratique de l’apprentissage par renforcement.