🤖 machine learning

Adaptive Exploration for Latent-State Bandits

Cet article propose des algorithmes d'exploration adaptatifs pour les bandits à états latents qui améliorent LinUCB en incorporant des paires action-récompense décalées et des empreintes de sondage dynamiques afin de suivre efficacement les états de Markov non observés, réduisant ainsi le regret dynamique par rapport aux références standards lorsque les résumés d'état sont suffisamment distincts et mis à jour fréquemment.

Auteurs originaux : Jikai Jin, Kenneth Hung, Sanath Kumar Krishnamurthy, Baoyi Shi, Congshan Zhang

Publié 2026-06-02

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jikai Jin, Kenneth Hung, Sanath Kumar Krishnamurthy, Baoyi Shi, Congshan Zhang

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes un chef essayant de cuisiner le repas parfait pour un client, mais que vous ne pouvez pas voir le client. Vous voyez seulement l'assiette qu'il vous rend après avoir mangé.

Dans un scénario de cuisine normal, si le client dit : « Cette soupe est trop salée », vous savez exactement ce qu'il faut corriger. Mais dans le scénario de ce document, le goût du client change en fonction d'un facteur caché que vous ne voyez pas — peut-être vient-il de manger un snack très épicé, ou peut-être se sent-il malade, ou peut-être que la météo extérieure a fait naître une envie différente.

C'est le problème des Bandits à État Latent. Le « Bandit » est le chef (l'algorithme) qui choisit un plat (une action). L'« État Latent » est la condition cachée (l'humeur ou la santé du client) qui modifie le goût de la nourriture. Le chef ne peut pas voir l'état, il ne voit que le retour (la récompense).

Voici comment le document résout ce casse-tête, décomposé en concepts simples :

1. Le Problème : Le « Fantôme » dans la machine

Les algorithmes de cuisine standards (comme les algorithmes de Bandit de base) supposent que le goût du client est constant. Ils pensent : « Si j'ai servi de la soupe et qu'il l'a aimée, je servirai de la soupe à nouveau ».
Mais si le goût du client change secrètement (par exemple, s'il passe de « envie de soupe » à « envie de pizza » sans vous le dire), le chef continue de faire le mauvais choix. Le chef se trompe de recette parce qu'il lui manque le contexte caché. Le document appelle cela la confusion (confounding). Le chef devine la mauvaise recette car il lui manque le contexte caché.

2. Le Premier Indice : Regarder la dernière bouchée (Contexte décalé)

La première idée des auteurs est simple : Regardez ce qui s'est passé juste un instant auparavant.
Si le client vient de manger un taco épicé et vous rend une assiette disant « Trop chaud », cela vous indique quelque chose sur son état actuel. Même si vous ne pouvez pas le voir, le fait qu'il vienne de manger un taco et qu'il ressente de la chaleur suggère qu'il est actuellement dans un état de « sensibilité à la chaleur ».

Le document appelle cela le LC-UCB (Upper Confidence Bound à Contexte Décalé). Il traite la dernière action et la dernière récompense comme un « indice » sur l'état caché actuel. C'est comme dire : « Puisqu'il vient de se plaindre de l'épice, je devrais probablement éviter la nourriture épicée pour le moment ».

La faille : Parfois, l'indice n'est pas suffisant. Imaginez deux états cachés différents (par exemple, « Faim » et « Ennui ») qui font tous deux dire au client « La soupe est correcte ». Si vous regardez seulement la dernière bouchée, vous ne pouvez pas savoir dans quel état il se trouve, et vous pourriez donc choisir le plat suivant de travers.

3. Le Deuxième Indice : L'empreinte digitale de l'état (Sondage)

Pour résoudre la confusion, le document suggère une approche de « menu de dégustation » appelée Sondage (Probing).
Au lieu de simplement servir un plat, le chef sert un minuscule échantillon de deux plats différents en même temps (ou de façon consécutive) pour obtenir une « empreinte digitale » de l'état actuel du client.

Scénario A (Sondage randomisé) : Si vous avez deux clients assis l'un à côté de l'autre, vous pouvez donner un taco à l'un et une salade à l'autre exactement au même moment. Leurs réactions combinées vous donnent une « empreinte digitale » unique qui vous indique exactement dans quel état ils se trouvent.
Scénario B (Sondage séquentiel) : Si vous n'avez qu'un seul client, vous lui donnez un taco, vous attendez une seconde, puis vous lui donnez une salade. Si le goût du client ne change pas trop vite, la combinaison de ces deux réactions agit toujours comme une emprent digitale.

Cette « empreinte digitale » aide le chef à distinguer des états qui semblaient identiques auparavant.

4. Le Chef Intelligent : Exploration Adaptative

Les auteurs réalisent qu'explorer constamment tout le menu est une perte de temps. Vous n'avez pas besoin de goûter un nouveau menu chaque seconde. Vous n'avez besoin de sonder que lorsque vous êtes confus ou qu'un certain temps s'est écoulé depuis votre dernier contrôle.

Ils ont créé des Algorithmes Adaptatifs (AdaRP-UCB et AdaSP-UCB) qui utilisent trois « portes » pour décider quand sonder :

La Porte de la « Surprise » (Résiduel) : Si la réaction du client est totalement différente de ce que le chef avait prédit (ex : « Je pensais que vous aimeriez la soupe, mais vous l'avez détestée ! »), il est temps de procéder à un nouveau sondage pour comprendre ce qui a changé.
La Porte du « Cas de l'équilibre » (Incertitude) : Si le chef hésite de manière égale entre deux plats (les scores sont à égalité), il doit sonder pour obtenir un signal plus clair avant de s'engager.
La Porte de l'« Obsolescence » (Danger/Hazard) : Si le chef n'a pas sondé depuis longtemps, l'« empreinte digitale » est peut-être vieille et inutile. L'algorithme force un rafraîchissement au cas où l'état du client aurait dérivé.

5. Les Résultats : Quand cela fonctionne-t-il ?

Les auteurs ont testé cela dans une « cuisine numérique » avec des milliers de simulations.

Cela fonctionne mieux quand : Les états cachés sont assez distincts pour être identifiés par les empreintes digitales, et que les états ne changent pas trop brutalement entre le moment où vous prenez un échantillon et le moment où vous l'utilisez.
Cela échoue quand : Le bruit est trop fort (le client est trop imprévisible), ou si les états changent si vite qu'au moment où vous terminez votre « menu de dégustation », le client a déjà changé d'avis.

Résumé

Le document nous enseigne comment prendre de meilleures décisions lorsque le monde change de manières que nous ne pouvons pas voir directement. Au lieu de deviner aveuglément ou de tester constamment tout, nous utilisons des indices passés et des tests intelligents et sur demande pour construire une « empreinte digitale » de la situation cachée. Cela nous permet de garder une longueur d'avance sur les changements, même lorsque ces changements sont invisibles.

Résumé technique : Exploration adaptative pour les bandits à états latents

1. Formulation du problème

L'article traite d'un problème de bandit multi-bras non stationnaire où les distributions de récompenses dépendent d'un état de Markov non observé (latent) qui évolue de manière autonome au fil du temps. Contrairement aux bandits contextuels standards, l'apprenant ne peut pas observer directement l'état $s_t$ ; il n'observe que l'action sélectionnée $a_t$ et la récompense stochastique résultante $r_t$ .

Le défi central est que le bras optimal change à mesure que les transitions d'état se produisent, mais l'apprenant doit inférer l'état actuel uniquement à partir de l'historique des actions et des récompenses. Cette configuration introduit trois difficultés techniques spécifiques :

Estimation confondue des récompenses : Les algorithmes standards moyennent les récompenses sur la distribution des états, ce qui conduit à un biais systématique lorsque le bras optimal varie selon les états.
Attribution temporelle des récompenses : Il est difficile de distinguer si un changement de performance de la récompense est dû à une progression de l'apprentissage ou à une transition dans l'état caché.
Information d'état limitée : L'algorithme ne peut pas se conditionner directement sur les caractéristiques de l'état et doit s'appuyer sur des signaux indirects, une tâche qui devient plus difficile à mesure que l'espace d'états croît.

L'objectif est de minimiser le regret dynamique par rapport à un oracle conscient de l'état, défini comme la différence cumulée entre la récompense du bras optimal pour l'état caché actuel et le bras réellement sélectionné.

2. Méthodologie

Les auteurs proposent une famille d'algorithmes qui intègrent un Contexte Décalé (Lagged Context) et des Stratégies de Sondage (Probing Strategies) dans le cadre de LinUCB. L'approche évite l'estimation explicite du modèle de transition de Markov latent, en s'appuyant plutôt sur des statistiques de faible dimension pour séparer les états.

2.1 Contexte Décalé (LC-UCB)

Le premier composant, Lagged-Context UCB (LC-UCB), traite la paire action-récompense précédente $(a_{t-1}, r_{t-1})$ comme un vecteur de caractéristiques contextuelles $\phi_t$ .

Intuition : Sous des dynamiques d'état Markoviennes lentes, la récompense précédente fournit des informations sur l'état précédent $s_{t-1}$ , qui est fortement corrélé avec l'état actuel $s_t$ .
Mécanisme : L'algorithme apprend une application de $(a_{t-1}, r_{t-1})$ vers la récompense actuelle $r_t$ . Cela permet à l'apprenant de suivre implicitement l'état et de sélectionner le bras optimal pour l'état récent inféré, plutôt que de viser la moyenne sur tous les états.
Limitation : LC-UCB peut échouer si plusieurs états produisent des récompenses similaires pour la même action (non-identifiabilité), entraînant une ambiguïté dans l'inférence de l'état.

2.2 Sondage pour l'empreinte digitale de l'état (State Fingerprints)

Pour résoudre l'ambiguïté, les auteurs introduisent des stratégies de sondage qui génèrent des « empreintes digitales de l'état » — des observations conjointes de récompenses provenant de plusieurs bras qui identifient de manière unique l'état caché. Deux paradigmes sont proposés :

Randomized Probing UCB (RP-UCB) : Applicable lorsque plusieurs unités expérimentales (par exemple, des utilisateurs) peuvent se voir assigner différents bras simultanément. Il collecte de véritables observations conjointes $(r_0, r_1)$ à partir du même instant $t$ .
Sequential Probing UCB (SP-UCB) : Applicable pour les contextes à unité unique. Il échantillonne les bras de manière consécutive (par exemple, le bras 0 à $t$ , le bras 1 à $t+1$ ) et traite la paire $(r_t, r_{t+1})$ comme une empreinte digitale synthétique. Cela repose sur l'hypothèse que l'état est « collant » (haute probabilité d'auto-transition) afin que l'état ne change pas entre les deux sondages.

2.3 Exploration Adaptative (AdaRP-UCB / AdaSP-UCB)

Un calendrier de sondage fixe incurre du regret même lorsque le modèle est confiant. Les auteurs proposent des variantes de Sondage Adaptatif qui rafraîchissent les empreintes digitales uniquement lorsque cela est nécessaire, en utilisant trois mécanismes de déclenchement (gating) :

Porte de Résidu (Residual Gate) : Déclenche un sondage si l'erreur de prédiction (résidu studentisé) dépasse un seument, indiquant une dérive du modèle ou une transition d'état.
Porte d'Incertitude (Uncertainty Gate) : Déclenche un sondage si la marge entre les deux meilleurs scores UCB est faible, indiquant une haute incertitude dans la sélection des bras.
Porte de Vieillissement/Danger (Staleness/Hazard Gate) : Déclenche un sondage si l'empreinte digitale n'a pas été mise à jour pendant une durée définie par une fonction de risque exponentielle, empêissant l'utilisation d'informations obsolètes.

Ces portes sont soumises à un intervalle minimal entre sondages ( $\tau_{min}$ ) pour éviter les comportements oscillatoires.

3. Contributions Clés

Cadre Algorithmique : Le développement de LC-UCB, RP-UCB, SP-UCB et de leurs variantes adaptatives (AdaRP-UCB, AdaSP-UCB) qui combinent le contexte décalé et le sondage coordonné pour gérer les bandits à état latent sans estimation explicite du modèle Markovien.
Analyse Théorique : Une décomposition du regret dynamique en trois composantes : l'ambiguïté de représentation (erreur d'approximation), le coût du sondage, et la dérive après qu'une empreinte soit devenue obsolète. L'article fournit des bornes montrant que le sondage adaptatif minimise le regret en équilibrant ces facteurs.
Validation Empirique : Évaluation systématique à travers différents nombres d'états cachés ( $S$ ), taux de transition (probabilité de maintien $p_{stay}$ ), bruit de récompense ( $\sigma$ ) et horizons temporels ( $T$ ).

4. Résultats Expérimentaux

Les algorithmes ont été évalués par rapport aux bases classiques (UCB1, Thompson Sampling), aux méthodes adverses (EXP3) et aux méthodes non stationnaires (Sliding Window UCB, Discounted UCB).

Performance : Les méthodes de sondage adaptatif (spécifiquement AdaRP-UCB et AdaSP-UCB) ont systématiquement surpassé toutes les bases dans les environnements où les résumés (empreintes) pouvaient distinguer les états et étaient mis à jour suffisamment fréquemment.
- AdaRP-UCB a obtenu le regret le plus bas dans 12 configurations sur 13, montrant des gains significatifs dans les environnements volatils.
- AdaSP-UCB a été le plus performant dans les contextes à unité unique avec un faible bruit, un mélange lent ou de grands espaces d'états.
Modes de Défaillance : L'article identifie les conditions spécifiques où les méthodes se dégradent :
- Bruit Élevé : Lorsque le bruit ( $\sigma$ ) est élevé par rapport à l'écart entre les bras, les empreintes deviennent faibles, et les méthodes non stationnaires (comme D-UCB) peuvent être plus performantes.
- Faible Séparation des Empreintes : Si différents états produisent des distributions de récompense conjointe similaires, la stratégie de sondage ne peut pas les lever l'ambiguïté.
- Changement Rapide : Le sondage séquentiel (SP-UCB) échoue lorsque l'état change fréquemment durant la fenêtre de sondage (faible $p_{stay}$ ), rendant l'empreinte digitale synthétique invalide.
Études d'Ablation : La suppression de la caractéristique d'empreinte ( $\phi_{fp}$ ) a considérablement augmenté le regret dans les environnements à états collants, confirmant la valeur des observations conjointes. La suppression du contexte décalé ( $\phi_{lag}$ ) a eu un impact moindre dans certains contextes randomisés, suggant que le timing adaptatif était le principal moteur d'amélioration dans ces cas.

5. Signification et Revendications

L'article affirme que sa contribution principale est une approche pratique de la non-stationnarité structurée où l'environnement évolue via un processus de Markov autonome. Contrairement aux bandits non stationnaires standards qui traitent les changements comme une dérive arbitraire, ou aux POMDP qui nécessitent une observabilité complète ou un décodage complexe, cette approche utilise des résumés d'historique légers et des sondages pour maintenir une estimation actuelle du bras optimal.

Les auteurs soulignent que leurs méthodes sont plus efficaces dans les régimes où :

L'état latent est prévisible sur de courts horizons (mélange lent).
La stratégie de sondage peut générer des statistiques suffisantes (empreintes) qui séparent les états pertinents.
Les mécanismes de déclenchement adaptatifs peuvent maintenir ces résumés à jour sans incurir un excès de regret de sondage.

Ce travail comble le fossé entre les bandits contextuels et l'apprentissage par renforcement à état latent en offrant une solution efficace sur le plan computationnel (basée sur LinUCB) qui ne nécessite pas d'apprendre l'intégralité de la dynamique de transition de l'état caché.