Résumé technique : Bornes améliorées pour l'exploration sans récompense et agnostique à la récompense

Formulation du problème

Ce papier aborde le défi de l'exploration dans des processus de décision markoviens (MDP) tabulaires, à horizon fini et épisodiques, où l'agent opère sans observer de signaux de récompense externes durant la phase de collecte de données. Les auteurs étudient deux cadres spécifiques :

1. Exploration sans récompense (RFE) : L'agent explore un environnement inconnu sans aucun signal de récompense. L'objectif est de produire une politique qui est $\epsilon$-optimale pour n'importe quelle fonction de récompense arbitraire révélée après la phase d'exploration.
2. Exploration agnostique à la récompense (RAE) : Similaire à la RFE, mais la fonction de récompense est tirée d'une petite classe finie prédéfinie (de taille polynomiale en $|S|, |A|, H$). L'objectif est de trouver une politique $\epsilon$-optimale pour la récompense spécifique tirée de cette classe.

La difficulté centrale réside dans la collecte de données suffisantes pour estimer avec précision la dynamique de transition état-action sans l'orientation d'un signal de récompense, garantissant ainsi que le modèle résultant permet le calcul de politiques quasi-optimales pour des tâches ultérieures.

Méthodologie

L'approche proposée remplace la dépendance à l'égard de multiples sous-routines indépendantes sans regret trouvées dans les travaux antérieurs par une procédure d'apprentissage en ligne unifiée. L'algorithme (Algorithme 1) opère en trois étapes :

1. Création de la politique d'exploration

Au lieu d'exécuter plusieurs algorithmes stochastiques sans regret (comme le font Jin et al., 2020b ; Li et al., 2024b), les auteurs emploient une seule exécution d'un algorithme de Descente de Miroir en Ligne (OMD) sur une séquence de fonctions de récompense auxiliaires soigneusement construites.

• Mécanisme : L'algorithme génère une séquence de récompenses $\{\lambda_t\}$ conçue pour orienter l'agent vers des paires état-action moins visitées. La récompense à l'étape $t$ est inversement proportionnelle au nombre de visites de la paire état-action (plus une constante $c$ pour gérer les visites à faible probabilité).
• Perspective d'optimisation : Ce processus est encadré comme la résolution approximative d'un problème d'optimisation convexe sur l'espace des mesures d'occupation valides. Plus précisément, il vise à minimiser l'objectif de barrière logarithmique négative $f(\mu) = -\sum \log \mu_h(s,a)$.
• Signification : En utilisant un seul algorithme de MDP en ligne (adapté de Rosenberg & Mansour, 2019) plutôt que des itérations de style Frank-Wolfe, la méthode réduit considérablement les termes de complexité d'échantillonnage d'ordre inférieur. Elle réutilise les échantillons tout au long du processus d'apprentissage pour construire une « couverture de politiques » assurant une exploration quasi-uniforme des triplets état-action significatifs.

2. Estimation de la dynamique

En utilisant la politique d'exploration générée à l'étape 1, l'agent collecte $N$ trajectoires. Pour gérer les corrélations temporelles inhérentes aux données de trajectoire, les auteurs utilisent un cadre de sous-échantillonnage à deux volets (Li et al., 2024a). Cette technique divise l'ensemble de données en un ensemble principal et un ensemble auxiliaire pour induire une indépendance statistique, permettant la construction d'un noyau de transition empirique $\hat{P}$ avec des garanties de concentration rigoureuses.

3. Estimation de la politique

Une fois la fonction de récompense réelle révélée, l'algorithme calcule une politique $\epsilon$-optimale en utilisant le pessimisme face à l'incertitude.

• L'algorithme construit un MDP empirique utilisant $\hat{P}$ et la récompense révélée.
• Il applique un terme de pénalité $b_h(s,a)$ dérivé d'inégalités de concentration de type Bernstein aux estimations de la valeur Q. Cette pénalité évolue avec la variance empirique et les comptes de visites, décourageant la politique de visiter des paires état-action mal couvertes.
• La politique finale $\hat{\pi}$ est la politique optimale pour ce MDP empirique pessimiste.

Contributions et résultats clés

1. Complexité d'échantillonnage améliorée pour l'exploration agnostique à la récompense (RAE)

Le papier présente un nouvel algorithme qui atteint la complexité d'échantillonnage d'ordre élevé optimale pour la RAE, correspondant à la borne inférieure pour l'identification de la meilleure politique (BPI).

• Résultat : La complexité d'échantillonnage est $O\left(\frac{|S||A|H^3 \ell_0^3}{\epsilon^2} + \frac{|S|^2|A|H^4 \ell_0^3}{\epsilon}\right)$.
• Amélioration : Alors que les travaux antérieurs (Li et al., 2024b) atteignaient le terme d'ordre élevé optimal $O(|S||A|H^3/\epsilon^2)$, leur borne souffrait d'un terme d'ordre inférieur à haute complexité qui rendait la borne optimale uniquement pour des $\epsilon$ extrêmement petits. La méthode proposée réduit considérablement ce terme d'ordre inférieur, rendant l'algorithme applicable à une plus large gamme de paramètres de précision.

2. Borne inférieure serrée pour l'exploration sans récompense (RFE)

Les auteurs prouvent une borne inférieure serrée pour la complexité d'échantillonnage de la RFE dans les MDP non homogènes en temps.

• Résultat : Tout algorithme RFE nécessite $\Omega\left(\frac{|S|^2|A|H^3}{\epsilon^2}\right)$ trajectoires en espérance.
• Signification : Cela résout une conjecture de Li et al. (2024b) selon laquelle la borne inférieure minimax pour la RFE non homogène en temps est un facteur $H$ plus grande que le cas homogène en temps. Cela établit que les bornes supérieures existantes (par exemple, M´enard et al., 2021) sont optimales à des facteurs logarithmiques près.

3. Cadre théorique

Le papier offre une perspective technique novatrice en reliant la création de la politique d'exploration à la minimisation d'un objectif de barrière logarithmique sur les mesures d'occupation. Il démontre qu'une approche de descente de miroir en ligne peut approximer cette solution plus efficacement que les méthodes précédentes basées sur Frank-Wolfe, réduisant ainsi la dépendance aux dimensions du problème dans les termes d'ordre inférieur.

Signification et affirmations

Le papier affirme faire progresser la compréhension théorique de l'exploration sans récompense en :

1. Désenchevêtrant l'exploration et l'exploitation : Il clarifie la complexité d'échantillonnage intrinsèque de l'exploration dans les MDP à horizon fini.
2. Praticabilité de la RAE : En assouplissant les exigences restrictives sur le paramètre de précision $\epsilon$ trouvées dans les bornes optimales antérieures, la méthode proposée rend l'exploration agnostique à la récompense pratique même dans des régimes de précision modérée.
3. Exhaustivité de la caractérisation : La combinaison de la nouvelle borne supérieure pour la RAE et de la borne inférieure serrée pour la RFE fournit une caractérisation minimax complète de la complexité d'échantillonnage pour ces problèmes (à des facteurs logarithmiques près).

Les auteurs déclarent explicitement que leur objectif est l'analyse théorique des MDP tabulaires à horizon fini, laissant les MDP non tabulaires et les résultats empiriques comme pistes pour des travaux futurs. Ils ne revendiquent pas d'application immédiate à des domaines réels spécifiques comme la robotique ou la médecine, mais mettent plutôt l'accent sur les améliorations théoriques fondamentales qui permettent de telles applications.