Résumé Technique : Exploration Pure pour une Bonne Politique en Apprentissage par Renforcement avec Feedback de Bandit

1. Formulation du Problème

Cet article aborde le problème de l'Identification d'une Bonne Politique (GPI) dans le cadre de l'Exploration Pure en Apprentissage par Renforcement (RL). Contrairement à l'objectif traditionnel de l'Identification de la Meilleure Politique (BPI), qui vise à identifier une politique (quasi-)optimale avec une haute confiance, la GPI se concentre sur la recherche d'une politique satisfaisant un seuil de performance spécifique.

Formellement, étant donné un Processus de Décision de Markov (MDP) épisodique avec des dynamiques de transition $P$ et une distribution initiale $p$ inconnues, un espace d'états fini $S$, un espace d'actions $A$ et un horizon $H$, l'agent se voit fournir un seuil de récompense $\mu_0$. L'objectif est de concevoir un algorithme $\delta$-Probablement Approximativement Correct ($\delta$-PAC) qui :

• Cas Positif : S'il existe une politique $\pi$ telle que sa récompense totale attendue $V^\pi_0(s_0) \ge \mu_0$, l'algorithme doit sortir une telle politique avec une probabilité d'au moins $1-\delta$.
• Cas Négatif : Si la valeur de la politique optimale $V^*_0(s_0) < \mu_0$, l'algorithme doit sortir "Aucune" avec une probabilité d'au moins $1-\delta$.

La métrique de performance est la complexité d'échantillonnage attendue (le nombre attendu d'épisodes explorés, noté $\tau$) nécessaire pour prendre une décision correcte. L'article exclut explicitement le cas où $V^*_0(s_0) = \mu_0$, car des travaux antérieurs (Degenne et Koolen [2019]) ont établi que tout algorithme $\delta$-PAC nécessiterait un nombre infini d'échantillons dans ce cas limite.

2. Méthodologie : BEE-GPI

Les auteurs proposent un nouvel algorithme nommé BEE-GPI (Exploration-Exploitation Équilibrée pour l'Identification d'une Bonne Politique). L'algorithme fonctionne par phases $k=1, 2, \dots$, où chaque phase comprend une étape d'exploration adaptative suivie d'un mécanisme de bifurcation décisionnelle.

Composants Clés :

1. Étape d'Exploration (ES-BPI-UCRL) :

   • Cette étape utilise un oracle BPI-UCRL à Arrêt Anticipé. Il emploie une stratégie d'échantillonnage optimiste (similaire à BPI-UCRL) pour estimer les noyaux de transition et les fonctions de valeur.
   • Crucialement, il introduit un nouveau mécanisme d'arrêt anticipé. L'oracle vérifie deux conditions à chaque étape :
     • Condition (3) : Une borne inférieure de confiance sur la valeur de la politique optimiste courante dépasse $\mu_0$ (ajustée par un facteur $C$). Si elle est remplie, une politique candidate est identifiée.
     • Condition (4) : Une borne supérieure de confiance sur la fonction de valeur optimale est inférieure à $\mu_0$. Si elle est remplie, l'instance est déclarée négative.
   • Si aucune des deux conditions n'est remplie et que le budget d'exploration $T^{ee}_k$ n'est pas dépassé, l'algorithme continue l'échantillonnage.

2. Bifurcation Décisionnelle :

   • Si l'oracle renvoie "Non Terminé", l'algorithme passe à la phase suivante avec une tolérance d'erreur plus stricte $\delta_k$ et un budget accru.
   • Si l'oracle renvoie "Aucune" mais que la confiance est insuffisante ($\delta_k \ge \delta/10$), l'algorithme continue vers la phase suivante pour garantir la garantie $\delta$-PAC.
   • Si l'oracle renvoie une politique candidate $\hat{\pi}_k$, l'algorithme entre dans l'Étape d'Exploitation.

3. Exploitation et Vérification :

   • Dans cette étape, la politique candidate $\hat{\pi}_k$ est exécutée de manière répétée pour estimer sa vraie valeur.
   • L'algorithme construit un intervalle de confiance pour la récompense moyenne empirique. Si la borne inférieure de confiance dépasse $\mu_0$ dans un budget d'échantillonnage spécifique, la politique est sortie comme solution.
   • Si le budget est épuisé sans vérification, l'algorithme retourne à l'étape d'exploration de l'itération suivante.

3. Contributions Clés

L'article apporte trois contributions théoriques principales :

1. Formalisation de la GPI : Les auteurs définissent formellement le problème de l'Identification d'une Bonne Politique dans le cadre de confiance fixe, le distinguant du $\epsilon$-BPI. Ils soulignent que les réductions standards du $\epsilon$-BPI sont sous-optimales pour la GPI car l'écart $V^*_0(s_0) - \mu_0$ est inconnu a priori, rendant le choix de $\epsilon$ difficile.
2. Conception d'Algorithme et Bornes Supérieures : Ils proposent BEE-GPI et dérivent des bornes supérieures théoriquement fondées sur sa complexité d'échantillonnage pour les cas positifs et négatifs.
   • Cas Positifs : La complexité d'échantillonnage est bornée par $O\left(\frac{H^2 \log(1/\delta)}{(V^*_0(s_0) - \mu_0)^2}\right) + O\left(\frac{\text{poly}(S, A, H)}{(V^*_0(s_0) - \mu_0)^2}\right)$.
   • Cas Négatifs : La borne implique des termes couplés aux tailles des espaces d'états et d'actions, spécifiquement $O\left(\frac{(H+1)^4 SA \log(1/\delta)}{(V^*_0(s_0) - \mu_0)^2}\right)$.
3. Bornes Inférieures et Near-Optimalité : Les auteurs établissent des bornes inférieures pour le problème GPI en utilisant des "Instances Uniformes" construites (pour les cas positifs) et des "Instances Arborescentes" (pour les cas négatifs).
   • Ils prouvent que pour les cas positifs, tout algorithme $\delta$-PAC doit encourir une complexité d'échantillonnage de $\Omega\left(\frac{H \log(1/\delta)}{(V^*_0 - \mu_0)^2} + \frac{H^2 SA}{(V^*_0 - \mu_0)^2}\right)$.
   • Pour les cas négatifs, la borne inférieure est $\Omega\left(\frac{HSA \log(1/\delta)}{(\mu_0 - V^*_0)^2}\right)$.
   • Ces résultats démontrent que BEE-GPI est presque optimal, l'écart entre les bornes supérieures et inférieures étant limité à des facteurs polynomiaux de $S, A, H$.

4. Résultats et Analyse

Insights Théoriques

• Découplage des Termes Logarithmiques : Une découverte significative est que pour les cas positifs, le coefficient du terme $\log(1/\delta)$ dans la complexité d'échantillonnage est $O(H^2)$ et est indépendant de la taille de l'espace d'états $S$ et de la taille de l'espace d'actions $A$. Cela contraste fortement avec les réductions BPI standards, où le coefficient évolue typiquement de manière polynomiale avec $S$ et $A$.
• Asymétrie : Il existe une asymétrie inhérente entre les cas positifs et négatifs. Alors que les cas positifs permettent une identification efficace d'une bonne politique sans explorer l'ensemble de l'espace d'états-actions, les cas négatifs nécessitent une exploration globale pour certifier qu'aucune politique ne satisfait le seuil, d'où la dépendance à $S$ et $A$ dans le terme $\log(1/\delta)$.

Expériences Numériques

Les auteurs valident leur approche en utilisant deux environnements classiques : les MDP Chaîne Simple et Double Chaîne.

• Configuration : Ils comparent BEE-GPI à l'algorithme BPI-UCRL de l'état de l'art (Kaufmann et al. [2021]). Pour assurer une comparaison équitable, BPI-UCRL se voit fournir le paramètre oracle $\epsilon = V^*_0 - \mu_0$, lui donnant une connaissance préalable significative.
• Résultats : À travers divers seuils $\mu_0$, BEE-GPI nécessite systématiquement beaucoup moins d'épisodes pour identifier une politique qualifiée par rapport à BPI-UCRL. Les résultats empiriques confirment l'avantage théorique du découplage du terme $\log(1/\delta)$ des tailles des espaces d'états et d'actions.

5. Signification et Revendications

L'article revendique que BEE-GPI offre une solution plus efficace pour les scénarios RL pratiques où trouver la politique absolument optimale est inutile ou computationnellement prohibitif, mais où trouver une politique "suffisamment bonne" (dépassant un référentiel) est critique.

• Pertinence Pratique : Les auteurs citent des applications en informatique médicale (identification de traitements dépassant un standard de soins), en informatique en nuage (respect des Accords de Niveau de Service) et en finance (respect des objectifs de retour sur investissement) où l'objectif est la satisfaction d'un seuil plutôt que l'optimalité.
• Avancement Théorique : En formalisant la GPI et en fournissant des bornes presque optimales, ce travail comble le fossé entre l'exploration pure théorique et les exigences pratiques basées sur des seuils. Il démontre que la complexité d'échantillonnage peut être considérablement réduite lorsque l'objectif est relâché de l'optimalité à la satisfaction d'un seuil, en particulier dans le cas d'instances positives.
• Perspectives Futures : Les auteurs suggèrent modestement que les travaux futurs pourraient consister à dériver des bornes dépendantes de l'instance plus serrées et à étendre ce cadre aux MDP à grande échelle en utilisant l'approximation de fonction.

En résumé, l'article établit que l'identification d'une politique satisfaisant un seuil de récompense est fondamentalement différente de l'identification de la meilleure politique, et propose un algorithme qui exploite cette distinction pour atteindre une efficacité d'échantillonnage supérieure, en particulier lorsque l'écart entre la valeur optimale et le seuil est le principal moteur de la difficulté.