Résumé technique : Émergence de l'exploration dans l'apprentissage par renforcement par gradient de politique via le réessai (Retrying)

1. Énoncé du problème

Dans l'apprentissage par renforcement (RL), l'exploration est généralement pilotée par l'ajout de bonus explicites (par exemple, l'entropie, la curiosité ou des bonus basés sur le comptage) au signal de récompense, ou par l'emploi de méthodes d'échantillonnage de la distribution postérieure. Les auteurs avancent un mécanisme distinct : l'exploration doit émerger naturellement du besoin de l'agent à maximiser les récompenses sous incertitude par le biais du réessai (retrying).

L'intuition centrale est que dans les environnements où un agent peut réessayer des actions ou rencontrer des états similaires, une politique gourmande (greedy) est sous-optimale si elle ignore le potentiel de rendements plus élevés lors des tentatives ultérieures. Sans la possibilité de réessayer, le choix rationnel est l'action actuellement supposée produire la récompense la plus élevée. Cependant, sous incertitude, une politique qui se couvre contre l'incertitude en explorant des actions alternatives peut obtenir un maximum attendu de rendement plus élevé sur plusieurs essais. Les méthodes existantes nécessitent souvent des modèles auxiliaires complexes pour estimer l'incertitude ou construire des bonus ; cet article demande si l'exploration peut être induite purement par l'optimisation d'un objectif basé sur la récompense qui formalise la valeur du réessai.

2. Méthodologie

2.1 L'objectif ReMax

Les auteurs proposent ReMax (Retry Maximum), un objectif qui évalue une politique $\pi$ par le maximum attendu de $M$ échantillons indépendants (essais), plutôt que par le rendement attendu d'un seul essai.

Dans un contexte de bandit avec des valeurs d'action $\mu$ et une distribution sur ces valeurs $\Pi$ (représentant l'incertitude épistémique), l'objectif ReMax est défini par :
$$J^M_{\text{ReMax}}(\pi) := \mathbb{E}_{\mu \sim \Pi} \left[ \mathbb{E}_{A^{[M]} \sim \pi} \left[ \max_{m \in [M]} \mu_{A_m} \mid \mu \right] \right]$$
où $A^{[M]}$ représente $M$ tirages indépendants de la politique $\pi$.

• Mécanisme : En maximisant le maximum attendu de $M$ tirages, l'objectif incite la politique à assigner une masse de probabilité aux actions qui pourraient produire des récompenses élevées, même si elles ne sont pas actuellement la moyenne maximale estimée. Cela induit une stochasticité (exploration) comme une propriété émergente pour se prémunir contre l'incertitude.
• Cas déterministe : Même avec des récompenses fixes, ReMax remodèle la géométrie de l'objectif. Augmenter le paramètre de réessai $M$ aplatit le gradient près de l'optimum, ralentissant la convergence et maintenant l'exploration, tandis qu'un $M$ plus petit accélère les mises à jour.

2.2 Extension au RL (MDP)

L'extension de ReMax aux processus de décision markoviens (MDP) présente des défis :

1. Unité d'incertitude : L'incertitude en RL englobe l'ensemble de l'environnement (récompenses et transitions).
2. Faisabilité des réessais : Réinitialiser physiquement l'environnement pour réessayer plusieurs actions à partir du même état est souvent irréalisable.

Pour y remédier, les auteurs définissent l'objectif ReMax à l'aide d'une fonction Q $Q^\pi(s, a)$ qui représente le rendement épisodique attendu. L'objectif est formulé comme le maximum attendu sur $M$ tirages des valeurs Q à un état $s$ :
$$J^M_{\text{ReMax}}(\pi, s, Q) := \mathbb{E}_{Q \sim \mathcal{Q}} \left[ \mathbb{E}_{A^{[M]} \sim \pi} \left[ \max_{m \in [M]} Q(s, A_m) \right] \right]$$
Ici, la distribution $\mathcal{Q}$ capture l'incertitude sur les valeurs Q (soit via une modélisation explicite comme des ensembles, soit implicitement via la non-stationnarité des critiques profonds).

2.3 Formulation du gradient de politique

Pour optimiser ReMax efficacement, les auteurs dérivent un nouvel estimateur de gradient de politique (PG) qui est calculable à partir de rendements de trajectoire unique.

• Échec de l'approche naïve : Une application directe du théorème du gradient de politique nécessite d'observer les rendements pour tous les $M$ actions échantillonnées simultanément, ce qui est irréalisable en RL épisodique.
• Reformulation par l'amélioration attendue (EI) : Les auteurs introduisent une base (baseline) basée sur l'« amélioration attendue » (empruntée à l'optimisation bayésienne). Ils décomposent l'opérateur max en un terme spécifique à l'action et une base représentant le maximum des $M-1$ autres tirages ($W_{-m}$).
• Solution en forme close : En triant les valeurs Q, ils dérivent une expression en forme close pour le terme d'amélioration attendue. Cela permet d'estimer le gradient en utilisant un rendement de trajectoire unique $R(s, a)$ et les estimations actuelles de Q.
• Paramètre continu $m$ : Le compte de réessai entier $M$ est généralisé à un paramètre réel continu $m > 0$. Cela permet un contrôle fin de l'arbitrage exploration-exploitation. Le terme $(1 - C_j)^{M-1}$ dans la solution en forme close est remplacé par $(1 - C_j)^{m-1}$.

2.4 Algorithme RePPO

Les auteurs instaurent ReMax au sein du cadre de l'optimisation de politique proximale (PPO), créant ainsi ReMax PPO (RePPO).

• Architecture : Une méthode acteur-critique on-policy utilisant un critique Q.
• Objectif de substitution : RePPO modifie le substitut standard de PPO en remplaçant l'avantage standard par un avantage basé sur l'EI.
  $$A^+(t) = R^+(t) - b^+(s_t)$$
  où $R^+(t) = \text{EIm}(R^\lambda_t, \pi_\theta, Q_\phi(s_t, \cdot))$ et $b^+$ est la valeur attendue des valeurs Q transformées par l'EI.
• Stratégie de remplacement de Q : Pour empêcher le critique de surestimer l'amélioration de l'action échantillonnée (en raison de la sous-estimation de la valeur Q), les auteurs remplacent la valeur Q de l'action échantillonnée par le rendement réel de la trajectoire lors du calcul du terme d'EI. Cela garantit que l'« amélioration » est mesurée par rapport au véritable rendement, et non par rapport à une estimation potentiellement biaisée.

3. Contributions clés

1. Objectif ReMax : Un nouvel objectif de RL qui induit l'exploration via la maximisation gourmande du rendement sous incertitude (réessai) sans bonus d'exploration explicite.
2. Dérivation théorique : Une nouvelle formulation de gradient de politique pour ReMax qui est estimable à partir de rendements de trajectoire unique, utilisant une expression en forme close pour le maximum attendu sur $M$ tirages.
3. Contrôle continu : La généralisation du compte de réessai discret $M$ à un paramètre continu $m$, permettant un ajustement précis du taux d'exploration.
4. Algorithme RePPO : Un algorithme de RL profond pratique (RePPO) qui implémente ReMax dans un cadre PPO, démontrant que l'exploration peut émerger de la fonction objectif elle-même.

4. Résultats expérimentaux

4.1 Expériences de bandits

• Stochasticité : Dans un bandit à deux bras, ReMax induit des politiques stochastiques pour $M \ge 2$, alors que le RL standard ($M=1$) produit des politiques déterministes.
• Adaptativité : ReMax adapte l'exploration à la magnitude de l'incertitude de la récompense. À mesure que la variance augmente, la politique ReMax optimale augmente l'exploration pour capturer les résultats rares à haut rendement, contrairement à la softmax régularisée par l'entropie qui reste fixe en fonction de la moyenne.
• Regret : Dans les contextes de bandits postérieurs (Beta-Bernoulli et Gaussian-Gaussian), ReMax présente un regret cumulé empiriquement sous-linéaire, comparable au Thompson Sampling et à l'UCB, et supérieur à la base Softmax.

4.2 Benchmarks MinAtar

Évalué sur quatre jeux (Breakout, Asterix, Freeway, Space Invaders) :

• Performance : RePPO (avec $m \in [1.2, 1.4]$) a surpassé les variantes standard de PPO (PPO-V, PPO-Q) et PPO avec des bonus d'entropie ou de Random Network Distillation (RND) de bonus.
• Exploration : RePPO a maintenu une entropie de politique plus élevée tout au long de l'entraînement par rapport à PPO avec un bonus d'entropie explicite, malgré l'absence de tel bonus.
• Sensibilité aux paramètres : La performance a culminé autour de $m=1.2$ à $1.4$. Un $m$ plus grand ralentissait la décroissance de l'entropie (maintenant l'exploration), tandis qu'un $m$ plus petit entraînait une convergence plus rapide mais une performance moindre.
• Ablation : Supprimer la base indépendante de l'action ou la stratégie de remplacement de Q dégradait significativement la performance, confirmant leur nécessité.

4.3 Benchmark Craftax

Évalué sur Craftax, un environnement de RL à grande échelle et ouvert :

• Performance : RePPO ($m=1.2$) a obtenu une performance compétitive (11,87 % du rendement maximum) par rapport aux variantes de PPO avec des bonus d'entropie et de RND (11,66 % et 11,68 %), et a surpassé PPO sans bonus.
• Scalabilité : RePPO a maintenu une entropie plus élevée sans bonus explicite, démontrant que le mécanisme passe à l'échelle sur des tâches complexes à long horizon.

5. Signification et affirmations

L'article affirme que ReMax offre une alternative prometteuse aux méthodes d'exploration traditionnelles en :

• Éliminant le besoin de bonus explicites : L'exploration émerge naturellement de l'objectif de maximiser le rendement maximum attendu sur les réessais.
• Simplifiant la conception d'algorithmes : Il évite la surcharge computationnelle et la complexité de la conception de bonus de curiosité ou du maintien de modèles de la distribution postérieure explicites (bien qu'il puisse utiliser ces derniers pour l'estimation de l'incertitude).
• Fournissant un contrôle précis : Le paramètre continu $m$ permet un ajustement précis de l'arbitrage exploration-exploitation.

Les auteurs notent que bien que leurs expériences de RL profond aient principalement démontré une exploration stochastique (augmentation de l'entropie de la politique), le cadre théorique soutient l'exploration profonde (collecte d'informations temporellement cohérente) si combiné à une modélisation explicite de l'incertitude (par exemple, des ensembles). Ils positionnent ReMax comme un principe général applicable aux domaines où le réessai est précieux, y compris les tâches de raisonnement avec les grands modèles de langage (LLM), en établissant des parallèles avec les objectifs pass@K dans ce domaine.

Le travail est modeste dans ses affirmations théoriques, notant que les bornes de regret formelles pour le cadre du RL profond sont laissées pour de futurs travaux, et que les résultats actuels sont des démonstrations empiriques d'efficacité.