Résumé Technique : Apprentissage Bayésien pour le Problème du Plus Court Chemin Stochastique

1. Formulation du Problème

L'article traite du problème du Plus Court Chemin Stochastique (SSP), défini comme un processus de décision de Markov (MDP) à horizon infini et non actualisé, possédant un état terminal absorbant. Contrairement aux MDP standard avec facteur d'actualisation ( $\gamma < 1$), la formulation SSP ($\gamma = 1$) nécessite l'existence d'un état cible unique ($s_g$) de récompense nulle et l'existence d'au moins une politique « propre » (une politique qui atteint $s_g$ avec une probabilité de 1 depuis n'importe quel état).

L'objectif principal est d'apprendre la fonction de valeur d'action optimale, $Q^*$, qui satisfait les Équations de Bellman d'Optimalité (BOE). Le défi réside dans le fait que $Q^*$ n'est pas directement observée ; seuls des triplets état-action-récompense $(s, a, r)$ sont observés via l'interaction. Les auteurs visent à construire un cadre bayésien pour quantifier l'incertitude sur $Q^*$ et faciliter les compromis exploration-exploitation via l'échantillonnage de Thompson (échantillonnage de la distribution postérieure) sans dépendre des hypothèses irréalistes ou des approximations ad hoc courantes dans la littérature existante de l'apprentissage par renforcement (RL) bayésien.

2. Méthodologie

2.1. Construction de la Vraisemblance via les Équations de Bellman

La principale contribution méthodologique est la construction directe de la fonction de vraisemblance basée sur les BOE plutôt que sur des algorithmes d'approximation stochastique (comme le Q-learning) ou des erreurs de différence temporelle (TD).

• Paramétrage : La fonction de valeur optimale est approximée par une fonction paramétrique $Q_\theta$.
• Contrainte : Pour une paire état-action $(s, a)$, la récompense attendue $\bar{r}_{s,a}$ doit satisfaire la BOE : $\bar{r}_{s,a} = Q_\theta(s, a) - \mathbb{E}[\max_{a'} Q_\theta(S', a')]$.
• Vraisemblance : Les auteurs définissent une fonction de vraisemblance $p(r_t | \theta, \psi, s_t, a_t)$ où la récompense observée $r_t$ est modélisée comme la récompense attendue déterministe plus un bruit. Cela contraint les paramètres $\theta$ à être cohérents avec les BOE observées.

2.2. Gestion des Récompenses Déterministes et des Postérieurs sur Variétés

Un défi théorique important surgit lorsque les récompenses sont déterministes (sans bruit). Dans ce cas, les BOE imposent des contraintes d'égalité strictes sur $\theta$.

• Densité de Variété : La distribution postérieure de $\theta$ s'effondre de l'espace de paramètres complet vers une variété de faible dimension définie par l'intersection des contraintes des BOE.
• Mesure de Hausdorff : Les auteurs caractérisent cette distribution postérieure à l'aide d'une densité par rapport à la mesure de Hausdorff (Théorème 2), plutôt qu'une densité de Lebesgue standard. Cela fournit une description mathématique rigoureuse de la distribution postérieure pour les récompenses sans bruit.

2.3. Relaxation et Approximation de la Vraisemblance

L'échantillonnage direct à partir d'une densité de variété est computationnellement intraitable pour les méthodes de Monte Carlo standard. Pour faciliter l'inférence, les auteurs proposent de relaxer la vraisemblance :

• Convolution : La vraisemblance exacte est convoluée avec un noyau (par exemple, Gaussien ou uniforme) avec une tolérance $\epsilon$.
• Densité de Lebesgue : Cette relaxation « épaissit » la variété, résultant en une distribution postérieure dotée d'une densité de Lebesgue standard adaptée à l'échantillonnage MCMC.
• Compromis : L'article analyse rigoureusement les conséquences de cette relaxation. Bien qu'elle permette un échantillonnage tractable, elle introduit des problèmes d'indéterminabilité. Plus précisément, pour les paramétrages tabulaires, la vraisemblance relaxée peut assigner une masse infinie à des ensembles de paramètres correspondant à des politiques impropres (politiques qui n'atteignent jamais l'objectif), alors que la distribution postérieure exacte ne le fait pas.

2.4. Échantillonnage de la Postérieure pour l'Exploration

Le cadre utilise l'échantillonnage de Thompson (échantillonnage de la distribution postérieure) pour l'exploration. À chaque épisode, une politique est échantillonnée à partir de la distribution postérieure de $Q_\theta$ (soit en échantillonnant $\theta$ directement, soit en calculant la masse de probabilité sur les politiques) et déployée jusqu'à ce que l'objectif soit atteint ou qu'une boucle impropre soit détectée.

3. Principales Contributions

1. Formulation Bayésienne Rigoureuse : L'article fournit une formulation bayésienne de premier principe pour les SSP qui dérive la vraisemblance directement des équations de Bellman d'optimalité, évitant les vraisemblances heuristiques souvent utilisées dans le RL bayésien basé sur la TD.
2. Caractérisation de la Variété : Il établit que pour les récompenses déterministes, la distribution postérieure réside sur une variété de faible dimension et fournit la formule de densité explicite par rapport à la mesure de Hausdorff (Théorème 2).
3. Analyse de la Relaxation et de l'Indéterminabilité : Les auteurs prouvent mathématiquement que relaxer la vraisemblance par un noyau Gaussien (pour permettre une densité de Lebesgue) crée un problème d'indéterminabilité spécifique : la distribution postérieure peut être dominée par des politiques impropres si la variance du prior est élevée (Théorème 4). Cela contraste avec la distribution postérieure exacte, qui exclut correctement les politiques impropres.
4. Dérivation de la Postérieure Tabulaire : Pour les paramétrages tabulaires avec des priors gausiens et des vraisemblances relaxées, la distribution postérieure est montrée comme étant un mélange de gaussiennes tronquées (Proposition 1).
5. Évaluation et Validation Empirique : L'article introduit un protocole de benchmarking utilisant les variantes de l'environnement "Deep Sea" pour comparer leur méthode aux approches bayésiennes basées sur la TD (Bayes-TD, Bayes-TD-En, Bayes-TD-Max).

4. Résultats

4.1. Résultats Théoriques

• Convergence : Lorsque la tolérance de relaxation $\epsilon \to 0$, la distribution postérieure approximative converge vers la distribution postérieure exacte de la variété.
• Dominance des Politiques Impropres : En présence de politiques impropres, un prior gaussien combiné à une vraisemblance relaxée peut conduire à une distribution postérieure où la masse est « étirée » le long de directions correspondant à des politiques impropres, pouvant biaiser la sélection des actions optimales. Cet effet est atténué par des $\epsilon$ plus petits ou par l'utilisation de priors qui pénalisent explicitement les politiques impropres.

4.2. Expériences Numériques

Des expériences ont été menées sur des variantes du benchmark Deep Sea (environnements standard, pyramid et swirl) :

• Efficacité des Données : Le cadre proposé (Bayes-BR) a démontré une efficacité de données supérieure par rapport aux méthodes bayésiennes basées sur la TD, particulièrement lorsque la tolérance de relaxation $\epsilon$ était faible (ex: 0,01).
• Convergence : La probabilité a posteriori de la politique optimale a convergé rapidement vers 1 dans l'environnement Deep Sea standard (8 épisodes pour une profondeur de 3).
• Optima Multiples : Dans la variante "Deep Sea Pyramid" présentant plusieurs politiques optimales, la distribution postérieure a correctement réparti la masse de manière égale entre toutes les politiques optimales.
• Politiques Impropres : Dans la variante "Deep Sea Swirl" (contenant des politiques impropres), le cadre a réussi à récupérer la classe de politique optimale malgré le risque théorique de dominance des politiques impropres, à condition que $\epsilon$ soit suffisamment petit.
• Défis d'Échantillonnage : L'étude a noté que l'algorithme HMC (Hamiltonian Monte Carlo) standard peinait à échantillonner efficacement la distribution postérieure relaxée lorsque $\epsilon$ était très petit (0,01), soulignant la difficulté d'échantillonner près de la variété même avec la relaxation.

5. Signification et Revendications

L'article affirme que son cadre quantifie fidèlement l'incertitude dans le contexte du SSP sans dépendre des « hypothèses de modélisation irréalistes » ou des « approximations ad hoc » trouvées dans de nombreux travaux de RL bayésien existants (qui découlent souvent des mises à jour de Q-learning).

• Fidélité : En dérivant la vraisemblance des BOE, la distribution postérieure résultante est théoriquement ancrée dans les conditions d'optimalité du MDP.
• Aperçu des Approximations : Ce travail fournit une analyse mathématique critique de l'étape de « relaxation » souvent utilisée en pratique. Il révèle que si la relaxation permet une inférence tractable, elle modifie fondamentalement la géométrie de la distribution postérieure, pouvant mener à la sélection de politiques impropres si elle n'est pas gérée avec soin.
• Benchmarking : Les auteurs fournient un nouveau benchmark pour comparer les méthodes de RL bayésien, montrant que leur approche est plus efficace en termes de données que les méthodologies concurrentes basées sur la TD dans le cadre du SSP.

L'article conclut avec modestie, reconnaissant que bien que le cadre soit robuste, des travaux futurs sont nécessaires pour concevoir des priors qui excluent explicitement les politiques impropres et pour développer des méthodes d'échantillonnage plus sophistiquées pour gérer les défis liés aux valeurs de $\epsilon$ très faibles.