Résumé Technique : Apprentissage par Renforcement avec Observations Déclenchées par l'Action

1. Définition du Problème

L'article traite d'une classe spécifique de Processus de Décision Markoviens Partiellement Observables (POMDP) où la disponibilité des observations de l'état n'est pas exogène ou fixe, mais plutôt déclenchée par l'action. Dans l'apprentissage par renforcement (RL) standard, un agent observe le nouvel état après chaque action. Dans de nombreux scénarios pratiques (ex. : diagnostics cliniques, trading financier), l'obtention d'une observation de l'état est coûteuse, peu fiable ou nécessite une action spécifique pour être déclenchée.

Les auteurs formalisent ce cadre comme des Processus de Décision Markoviens à Traçabilité Sporadique Déclenchée par l'Action (ATST-MDPs).

• Mécanisme : Lorsqu'un agent dans un état $s$ exécute une action $a$, il reçoit une récompense et l'environnement transite vers $s'$. Crucialement, $s'$ n'est pas toujours observé. Avec une probabilité $\beta(a)$, un « événement d'observation » (rafale de données) se produit, révélant $s'$ ainsi que la récompense cumulée depuis la dernière rafale. Avec une probabilité $1-\beta(a)$, aucun retour d'état n'est fourni.
• Défi : L'agent doit simultanément optimiser la politique de contrôle et décider quand déclencher les observations (en choisissant des actions ayant un $\beta(a)$ plus élevé) pour réduire l'incertitude, équilibrant ainsi le coût de l'acquisition d'informations et la performance du contrôle.
• Distinction : Contrairement aux POMDP standards où les observations sont bruitées mais fréquentes, ou au RL avec des délais exogènes où le retour est simplement tardif, les ATST-MDP présentent des délais endogènes où les choix d'actions de l'agent déterminent directement la fréquence de la révélation de l'état.

2. Méthodologie

2.1 Espace d'États Augmenté et Équations de Bellman

Pour gérer la partialité de l'observation, les auteurs définissent un espace d'états augmenté $\mathcal{X} = \mathcal{S} \times \mathcal{A}^{<\infty}$. Un état augmenté $x = (s_1, a_1, \dots, a_n)$ consiste en le dernier état observé $s_1$ et la séquence d'actions entreprises depuis cette observation.

• Suffisance : L'état augmenté sert de statistique suffisante pour l'historique, permettant de traiter le problème comme un MDP entièrement observé sur $\mathcal{X}$.
• Dynamique : La transition sur $\mathcal{X}$ est un mélange : avec une probabilité $\beta(a)$, l'état est réinitialisé vers le nouvel état observé $s'$; avec une probabilité $1-\beta(a)$, la séquence d'actions est complétée ($x \leftarrow x \cdot a$).
• Équations de Bellman : Les auteurs dérivent les équations d'optimalité de Bellman pour les fonctions de valeur $V^\pi$ et $Q^\pi$ sur cet espace augmenté, prouvant l'existence d'une politique augmentée optimale $\pi^*$.

2.2 Reformulation par Séquence d'Actions

Reconnaissant que l'espace d'états augmenté bifurque à l'infini, les auteurs proposent une reformulation basée sur la structure de renouvellement des rafales de données. Au lieu de décider action par action, l'agent s'engage dans une séquence d'actions $a \in \mathcal{A}^\mathbb{N}$ à chaque rafale de données, l'exécutant jusqu'à la prochaine observation.

• Cela transforme le problème en un processus de décision sur $(\mathcal{S}, \mathcal{A}^\mathbb{N})$.
• La fonction de valeur $K^\pi(s, a)$ représente la récompense escomptée accumulée à partir de l'état $s$ en exécutant la séquence $a$ jusqu'à la prochaine rafale de données, plus la valeur de continuation de l'état révélé.

2.3 Représentation Linéaire sous l'Hypothèse de MDP Linéaire

Pour rendre traitable l'espace infini des séquences d'actions, l'article suppose une structure de MDP Linéaire (Hypothèse 4.1), où les noyaux de transition et les récompenses sont linéaires par rapport à une application de caractéristiques (feature map) $\phi(s, a)$.

• Idée clé : Sous cette hypothèse, la fonction de valeur de la séquence d'actions $K^\pi$ admet une représentation linéaire dans une application de caractéristiques de dimension finie $\psi: \mathcal{S} \times \mathcal{A}^\mathbb{N} \to \mathbb{R}^{2d}$.
• Construction : La fonction de caractéristiques $\psi$ est construite en utilisant des matrices d'action $M_a$ (dérivées des dynamiques de transition) et les probabilités d'observation $\beta_a$. Plus précisément, $\psi$ encode l'évolution des caractéristiques au cours de la séquence d'actions et la probabilité que des rafales de données surviennent à chaque étape.
• Résultat : $K^\pi(s, a) = \langle \psi(s, a), v^\pi_{1,2} \rangle$, où $v^\pi_{1,2}$ est un vecteur dépendant de la politique. Cela permet l'utilisation de méthodes de régression standard malgré l'espace d'actions infini.

2.4 Estimation et Algorithme d'Apprentissage

L'article propose l'algorithme ATST-LSVI-UCB (Least-Squares Value Iteration avec Bornes Supérieures de Confiance pour les ATST-MDP).

• Estimation des Caractéristiques : Puisque la véritable fonction de caractéristiques $\psi$ est inconnue, l'algorithme estime les matrices d'action $M_a$ sous-jacentes et les probabilités d'observation $\beta_a$ à partir de données exploratoires en utilisant la régression de Ridge et les moyennes empiriques. Le Théorème 4.6 et le Corollaire 4.9 fournissent des bornes de complexité d'échantillonnage non asymptotiques pour construire une approximation $\epsilon$-admissible de $\psi$.
• Algorithme : L'algorithme opère en épisodes avec des horizons géométriques. Il effectue une itération de valeur vers l'arrière sur la fonction de caractéristiques estimée pour calculer des estimations de valeur optimistes (en utilisant des bonus UCB) et exécute des séquences d'actions gourmandes (greedy).
• Optimisation : Bien que l'espace d'actions soit infini, l'optimisation $\max_a K(s, a)$ est effectuée sur l'image compacte de la fonction de caractéristiques. En pratique, cela peut être approximé en se restreignant à des séquences de profondeur finie ou éventuellement périodiques.

3. Contributions Clés

1. Formalisation des ATST-MDPs : Un nouveau cadre pour le RL où la disponibilité des observations est une fonction de l'action choisie, faisant le pont entre les MDP standards et les POMDP généraux.
2. Fondements Théoriques : Dérivation des équations de Bellman sur l'espace d'états augmenté et preuve de l'existence d'une politique optimale.
3. Représentation Linéaire : Démonstration que, sous l'hypothèse de MDP linéaire, la fonction de valeur sur les séquences d'actions est linéaire dans une fonction de caractéristiques de dimension finie, permettant un apprentissage efficace.
4. Algorithme et Bornes de Regret : Proposition de l'ATST-LSVI-UCB, un algorithme d'itération de valeur optimiste. Les auteurs prouvent une borne de regret de $\tilde{O}(\sqrt{d^3 K (1-\gamma)^{-3}})$ pour l'apprentissage épisodique, correspondant au taux optimal connu pour les MDP linéaires entièrement observables.
5. Complexité d'Échantillonnage : Établissement de garanties de complexité d'échantillonnage pour l'estimation de la fonction de caractéristiques des séquences d'actions à partir de données, montrant qu'elle est polynomiale par rapport à la dimension $d$ et indépendante de la taille de l'espace d'états $|\mathcal{S}|$.

4. Résultats

• Théoriques : La borne de regret correspond à l'état de l'art pour les MDP linéaires avec pleine observabilité, malgré la complexité ajoutée de la partialité de l'observation et des délais déclenchés par l'action. La borne évolue avec la dimension des caractéristiques $d$, le nombre d'épisodes $K$, et l'inverse du facteur de remise $(1-\gamma)$.
• Empiriques : Des expériences sur deux environnements tabulaires, RiverSwim (centré sur l'exploration) et RiverBalance (centré sur la stabilisation), démontrent la viabilité de l'algorithme.
  • Dans RiverSwim, les observations éparses (faible $\beta$) accélèrent étonnamment la convergence en encourageant des engagements en boucle ouverte plus longs (exploration).
  • Dans RiverBalance, des observations fréquentes (haut $\beta$) produisent des récompenses plus élevées, car la tâche nécessite des corrections dépendant de l'état pour maintenir la stabilité.
  • Les résultats soulignent que la fréquence d'observation optimale dépend de la tâche.

5. Signification et Revendications

L'article affirme fournir une base théorique pour l'apprentissage par renforcement dans des environnements avec des observations d'état déclenchées par l'action. Sa signification réside dans :

• Réduction des Écarts : Il traite une classe de POMDP très pertinente en pratique (perception active, capteurs coûteux) que les méthodes de POMDP générales peinent à gérer en raison de l'intraitabilité computationnelle.
• Tractabilité : En exploitant la structure de renouvellement induite par les rafales de données et l'hypothèse de MDP linéaire, il transforme un problème de partialité d'observation complexe en un problème de régression linéaire traitable.
• Optimalité : Il atteint des taux de regret comparables aux contextes de pleine observabilité, suggérant que le « coût » de l'observabilité sporadique peut être atténué si le mécanisme d'observation est compris et exploité.
• Estimation sans Récompense : L'estimation de la fonction de caractéristiques est sans récompense (reward-free), ce qui signifie que l'apprentissage structurel de l'environnement (dynamiques et probabilités d'observation) peut être découplé de la fonction de récompense spécifique, permettant une adaptation flexible de la politique.

Les auteurs notent que les travaux futurs devraient se concentrer sur la conception de schémas d'approximation efficaces pour l'optimisation des séquences d'actions infinies et sur le développement d'algorithmes entièrement en ligne capables d'affiner les estimations de caractéristiques de manière adaptative sans données exploratoires pré-collectées.