🤖 Navigateur Robot — Itération de la Valeur MDP en Direct

L'itération de la valeur est un algorithme de programmation dynamique basé sur un modèle, permettant de résoudre un processus de décision markovien (MDP) : un espace d'états S, un espace d'actions A, un modèle de transition connu P(s'|s,a), une fonction de récompense R(s,a,s') et un facteur d'actualisation γ. Partant d'une fonction de valeur arbitraire V(s), il applique de manière répétée la mise à jour de Bellman-optimalité V(s) ← max_a Σ_s' P(s'|s,a)[R(s,a,s') + γV(s')] à tous les états simultanément (un balayage synchrone). Comme cette mise à jour est une application contractante sous γ<1, des balayages répétés convergent de manière prouvée vers l'unique fonction de valeur optimale V*, à partir de laquelle la politique optimale π*(s) = argmax_a Σ_s' P(s'|s,a)[R(s,a,s') + γV*(s')] peut être lue directement.

L'itération de la valeur est basée sur un modèle : elle nécessite que les probabilités de transition P(s'|s,a) et la fonction de récompense R(s,a,s') soient connues à l'avance, et elle calcule une espérance exacte sur chaque résultat possible de chaque action dans chaque état à chaque balayage — aucune simulation ni exploration de l'environnement n'est nécessaire. Le Q-learning (traité dans la simulation d'apprentissage par renforcement distincte de ce site) est sans modèle : l'agent ne connaît pas P ni R à l'avance, il doit donc réellement agir dans l'environnement, observer des transitions échantillonnées (s, a, r, s'), et mettre à jour progressivement Q(s,a) avec une règle de différence temporelle Q(s,a) ← Q(s,a) + α[r + γ·max_a' Q(s',a') − Q(s,a)]. L'itération de la valeur converge vers le V* exact en un nombre borné de balayages étant donné le modèle ; le Q-learning ne converge qu'asymptotiquement, par exploration par essais et erreurs, et ne nécessite aucun modèle de transition explicite. Cette simulation implémente délibérément le cas basé sur un modèle afin que les deux familles d'algorithmes puissent être clairement distinguées.

Les robots réels et les agents physiques exécutent rarement une action parfaitement — les roues glissent, les capteurs dérivent et les sols sont irréguliers. Cette simulation modélise cela avec un modèle de transition stochastique classique : choisir de se déplacer dans une direction donnée réussit avec une probabilité P(intentionnelle) (réglable, par défaut 0,80), tandis que la probabilité restante est répartie également entre une déviation de 90° à gauche et une déviation de 90° à droite du cap prévu. La mise à jour de Bellman fait la somme des trois résultats possibles pondérés par leurs probabilités, ce qui est précisément ce qui fait de ceci un véritable MDP plutôt qu'une recherche déterministe du plus court chemin — la politique optimale doit se prémunir contre le risque d'une glissade indésirable vers un mur ou un obstacle.

Trois termes de récompense se combinent pour définir R(s,a,s') : un petit coût de pas négatif (par défaut −0,04) appliqué à chaque mouvement non terminal, ce qui pousse la politique optimale vers des chemins plus courts ; une pénalité de collision avec un obstacle ou un mur (par défaut −0,75) appliquée chaque fois qu'une transition est bloquée par un mur, un obstacle ou la limite de la grille, ce qui pousse la politique à conserver une marge de sécurité autour des obstacles, surtout lorsque les transitions sont bruitées ; et une récompense terminale de but (+1) reçue en entrant dans la cellule de but, ce qui rend l'atteinte du but intéressante. L'itération de la valeur propage les trois à travers la mise à jour de Bellman, de sorte que les cellules proches du but acquièrent des valeurs élevées en premier, et ce signal de haute valeur se propage vers l'arrière, balayage après balayage, jusqu'à ce que chaque état atteignable dispose d'une estimation précise de son gain espéré à long terme.

Chaque balayage synchrone enregistre le changement absolu maximal de la valeur de n'importe quel état, max_s |V_new(s) − V_old(s)|, et la simulation trace cette quantité sur une échelle logarithmique en fonction du numéro de balayage. Comme l'opérateur d'optimalité de Bellman est une γ-contraction, cette séquence de delta maximal est garantie de décroître de manière monotone vers zéro ; la simulation déclare la convergence une fois qu'elle passe sous 1e-4. À ce stade, V(s) est à une erreur faible et bornée de la véritable V*(s), et la politique gloutonne qui en est extraite, π(s) = argmax_a Q(s,a), est la politique optimale pour le MDP tel que configuré.

Oui. γ contrôle à quel point la valeur d'un état est influencée par des récompenses situées à de nombreux pas dans le futur : avec un γ proche de 1, les récompenses de but lointaines se propagent presque sans atténuation à travers toute la grille, de sorte que la politique optimale planifie loin à l'avance et est prête à faire des détours plus longs mais plus sûrs autour des obstacles. Avec un γ plus proche de 0,5, les récompenses futures sont fortement actualisées, ce qui rend la politique myope — elle peut accepter un chemin plus court mais plus risqué au-delà d'un obstacle, car la valeur actualisée d'atteindre le but quelques pas plus tard ne vaut pas beaucoup plus que de l'atteindre un pas plus tôt. γ contrôle également la vitesse de convergence : un γ plus petit fait contracter l'opérateur de Bellman plus rapidement, de sorte que des facteurs d'actualisation plus faibles convergent généralement en moins de balayages.