Résumé technique : Bornes PAC Minimax pour l'apprentissage dans les MDP contextuels exogènes

1. Configuration du problème

Cet article étudie la complexité d'échantillonnage de l'apprentissage dans les processus de décision de Markov (MDP) tabulaires à rabais avec des contextes i.i.d. exogènes. Le modèle est défini par un tuple $\mathcal{M} = (\mathcal{X}, \mathcal{Z}, \mathcal{A}, P, r, \mu, \gamma)$, où :

• $\mathcal{X}$ est un espace d'états contrôlés fini.
• $\mathcal{A}$ est un espace d'actions fini.
• $\mathcal{Z}$ est un espace de contextes fini.
• $\gamma \in [0, 1)$ est le facteur de rabais.
• $P: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to \Delta(\mathcal{X})$ est le noyau de transition.
• $r: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to [0, 1]$ est la fonction de récompense.
• $\mu$ est la distribution inconnue sur les contextes.

À chaque étape de temps $t$, un contexte $Z_t$ est tiré indépendamment de $\mu$ et révélé à l'agent avant la sélection de l'action. L'agent choisit $A_t$, reçoit une récompense $r(X_t, A_t, Z_t)$, et transite vers $X_{t+1} \sim P(\cdot | X_t, A_t, Z_t)$. Crucialement, le contexte $Z_{t+1}$ est indépendant des actions de l'agent et de l'état actuel, dépendant uniquement de $\mu$.

Les objectifs d'apprentissage sont l'Évaluation de Politique (PE - Policy Evaluation), l'Estimation de la Meilleure Valeur (BVE - Best-Value Estimation) et l'Extraction de la Meilleure Politique (BPE - Best-Policy Extraction). La complexité d'échantillonnage est mesurée par une paire $(n_{\text{learn}}, m_{\text{query}})$, représentant respectivement le nombre d'appels à l'oracle effectués pendant une phase d'apprentissage hors ligne et le nombre d'appels effectués pendant la phase de décision (requête). L'article considère deux régimes :

1. Dynamique connue : $P$ et $r$ sont connus ; seul $\mu$ est inconnu.
2. Entièrement inconnu : $\mu$ et $P$ sont tous deux inconnus.

2. Méthodologie

2.1 Intuition centrale : Fonctions de valeur moyennées

La contribution méthodologique centrale est la réduction du problème de l'espace augmenté $\mathcal{X} \times \mathcal{Z}$ vers l'espace d'états contrôlés $\mathcal{X}$. Les auteurs définissent la fonction de valeur moyennée $\bar{V}(x) := \mathbb{E}_{Z \sim \mu}[V(x, Z)]$.
Parce que le prochain contexte est tiré indépendamment de $\mu$, l'équation de Bellman d'optimalité pour la valeur moyennée $\bar{V}^\star$ dépend uniquement du noyau de transition moyenné sur $\mu$ :
$$\bar{V}^\star(x) = \mathbb{E}_{Z \sim \mu} \left[ \max_{a \in \mathcal{A}} \left( r(x, a, Z) + \gamma \sum_{x'} P(x' | x, a, Z) \bar{V}^\star(x') \right) \right]$$
Cette formulation permet à l'apprenant d'estimer un vecteur dans $\mathbb{R}^{|\mathcal{X}|}$ plutôt que dans $\mathbb{R}^{|\mathcal{X}||\mathcal{Z}|}$, découplant ainsi la complexité de la taille de l'espace de contexte $|\mathcal{Z}|$.

2.2 Cadre algorithmique : Réduction de la variance par division (Halving)

L'article emploie un schéma d'itération de valeur à réduction de variance (adapté de Sidford et al., 2019) pour estimer les fonctions de valeur moyennées. L'algorithme opère en deux phases :

1. Phase hors ligne (Estimation de l'ancre) : L'algorithme calcule une borne inférieure de haute probabilité (ancre) pour l'opérateur de Bellman appliqué à une estimation de valeur initiale. Cela nécessite un grand lot d'échantillons pour contrôler la variance de la moyenne empirique.
2. Phase en ligne/itérative (Mises à jour par réduction de variance) : Les itérations suivantes estiment uniquement la différence entre le backup de Bellman actuel et l'ancre. En réutilisant les mêmes échantillons pour le terme de différence, la variance est considérablement réduite, permettant des tailles d'échantillons plus petites par itération.

L'algorithme utilise une stratégie de "division" (halving), appelant de manière répétée une sous-routine (HALFERR) qui divise par deux la borne d'erreur $u$ jusqu'à ce que la précision cible $\epsilon$ soit atteinte.

2.3 Gestion de la dynamique inconnue

Dans le régime entièrement inconnu, l'algorithme ne peut pas calculer exactement le backup de Bellman même avec un contexte échantillonné. Au lieu de cela, pour chaque contexte échantillonné $Z$, l'algorithme tire un échantillon de transition $X' \sim P(\cdot | x, \pi(x, Z), Z)$ pour former une estimation non biaisée du backup. Cela introduit un terme de variance supplémentaire lié au noyau de transition, qui est rigoureusement borné à l'aide d'une décomposition de martingales prenant en compte à la fois l'aléa du contexte et de la transition.

3. Résultats clés

3.1 Dynamique connue, distribution de contexte inconnue ($P, r$ connus, $\mu$ inconnu)

Lorsque le noyau de transition et les récompenses sont connus, l'article établit que la complexité d'échantillonnage est indépendante de la taille de l'espace de contexte $|\mathcal{Z}|$.

• Complexité : L'algorithme atteint les objectifs avec $(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(\beta^3/\epsilon^2), 0)$, où $\beta = (1-\gamma)^{-1}$.
• Optimalité : Une borne inférieure minimax de $\Omega(\beta^3/\epsilon^2)$ est prouvée, montrant que la borne supérieure est serrée à des facteurs logarithmiques près.
• Implication : L'apprenant n'a pas besoin d'estimer les valeurs pour chaque paire $(x, z)$ ; l'estimation de la valeur moyennée $\bar{V}$ suffit. La phase de requête ne nécessite aucun échantillon supplémentaire ($m_{\text{query}}=0$) car le passage de $\bar{V}$ à $V(x, z)$ est un backup de Bellman déterministe utilisant $P$ et $r$ connus.

3.2 Application à l'anticipation parfaite à une étape (Perfect One-Step Lookahead)

Le cadre est appliqué au réglage de l'anticipation de transition parfaite à une étape (où l'agent observe tous les états suivants possibles pour toutes les actions avant d'agir).

• Ce réglage est montré comme étant un cas particulier du MDP contextuel exogène où l'espace de contexte est l'ensemble de tous les tenseurs de transition possibles.
• Le résultat produit une complexité d'échantillonnage de $\tilde{O}(\beta^3/\epsilon^2)$ échantillons d'anticipation.
• En termes de transitions tabulaires individuelles, cela correspond à $\tilde{O}(\beta^3 |\mathcal{X}||\mathcal{A}|/\epsilon^2)$, améliorant la borne précédente de Lu et al. (2025) d'un facteur $\beta$.

3.3 Régime entièrement inconnu ($P$ et $\mu$ inconnus)

Lorsque la dynamique et la distribution de contexte sont toutes deux inconnues, l'article se concentre sur l'Évaluation de Politique (PE).

• Complexité : L'algorithme atteint $(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2), \tilde{O}(\beta^2/\epsilon^2))$.
• Compromis : La phase hors ligne apprend la valeur moyennée $\bar{V}^\pi$ (coûtant $|\mathcal{X}|$ transitions par échantillon de contexte). La phase de requête estime l'espérance de transition d'une étape finale au $(x, z)$ réalisé en utilisant des échantillons frais.
• Bornes inférieures : L'article prouve des bornes inférieures correspondantes, démontrant que :
  • $m_{\text{query}} = \Omega(\beta^2/\epsilon^2)$ est nécessaire pour la précision au moment de la décision.
  • $n_{\text{learn}} + |\mathcal{X}| m_{\text{query}} = \Omega(|\mathcal{X}|\beta^3/\epsilon^2)$ est nécessaire pour l'apprentissage hors ligne.
• Signification : Même dans le régime entièrement inconnu, la complexité reste indépendante de $|\mathcal{Z}|$. La dynamique inconnue ne force pas l'estimation sur l'espace augmenté ; elle introduit seulement de la stochasticité dans le "lift" au moment de la décision de $\bar{V}$ vers $V(x, z)$.

4. Signification et affirmations

L'article affirme fournir les premières bornes PAC minimax-optimales pour l'apprentissage dans les MDP contextuels exogènes. Ses principales contributions sont :

1. Découplage de la taille du contexte : Il démontre que le prix statistique des grands espaces de contextes est évitable. La complexité d'échantillonnage dépend de l'espace d'états contrôlés $|\mathcal{X}|$ mais pas de l'espace de contexte $|\mathcal{Z}|$.
2. Taux optimaux : Les taux dérivés ($\tilde{O}(\beta^3/\epsilon^2)$ pour la dynamique connue et $\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2)$ pour le cas entièrement inconnu) sont montrés comme étant minimax-optimaux à des facteurs logarithmiques près.
3. Cadre unifié : Le cadre englobe et améliore les résultats existants pour l'anticipation parfaite à une étape et fournit une analyse rigoureuse du compromis entre échantillonnage hors ligne et en ligne.

Les auteurs notent que bien que la borne inférieure soit serrée au point purement en ligne ($n_{\text{learn}}=0$) et au point de l'oracle réutilisable (leur algorithme proposé), la serrage de la borne pour les compromis intermédiaires reste une question ouverte. De plus, l'extension de ces résultats à l'Extraction de la Meilleure Politique (BPE) dans le régime entièrement inconnu est laissée comme travail futur en raison de la difficulté de gérer le biais de sélection lors de l'estimation du maximum sur les actions à partir d'échantillons de transition.