Technische Samenvatting: Adaptieve Exploratie voor Latente Toestands-Bandits

1. Probleemformulering

Het artikel behandelt een niet-stationair multi-armed bandit probleem waarbij de beloningsverdelingen afhangen van een onwaargenomen (latente) Markov-toestand die autonoom over de tijd evolueert. In tegenstelling tot standaard contextuele bandits kan de leerling de toestand $s_t$ niet direct observeren; zij observeren enkel de gekozen actie $a_t$ en de resulterende stochastische beloning $r_t$.

De kernuitdaging is dat de optimale arm verandert naarmate de verborgen toestand overgaat, maar de leerling de huidige toestand uitsluitend moet afleiden uit de geschiedenis van acties en beloningen. Deze setting introduceert drie specifieke technische moeilijkheden:

1. Verwarrende Beloningsschatting: Standaardalgoritmen middelen beloningen over de toestandsverdeling, wat leidt tot een systematische bias wanneer de optimale arm varieert tussen toestanden.
2. Temporele Beloningsattributie: Het is moeilijk te onderscheiden of een verandering in beloningsprestaties het gevolg is van leerprogressie of van een transitie in de verborgen toestand.
3. Beperkte Toestandsinformatie: Het algoritme kan niet direct conditioneren op toestandsfeatures en moet vertrouwen op indirecte signalen, een taak die moeilijker wordt naarmate de toestandsruimte groeit.

Het doel is om de dynamische regret te minimaliseren ten opzichte van een toestand-bewuste oracle, gedefinieerd als het cumulatieve verschil tussen de beloning van de optimale arm voor de huidige verborgen toestand en de daadwerkelijk gekozen arm.

2. Methodologie

De auteurs stellen een familie van algoritmen voor die Lagged Context en Probing Strategieën integreren in het LinUCB-framework. De aanpak vermijdt expliciete schatting van het latente Markov-transitiemodel, maar vertrouwt in plaats daarvan op laag-dimensionale statistieken om toestanden te scheiden.

2.1 Lagged Context (LC-UCB)

De eerste component, Lagged-Context UCB (LC-UCB), behandelt het vorige actie-beloningspaar $(a_{t-1}, r_{t-1})$ als een contextuele feature-vector $\phi_t$.

• Intuïtie: Onder trage Markoviaanse toestandsdynamiek biedt de vorige beloning informatie over de vorige toestand $s_{t-1}$, die sterk gecorreleerd is met de huidige toestand $s_t$.
• Mechanisme: Het algoritme leert een mapping van $(a_{t-1}, r_{t-1})$ naar de huidige beloning $r_t$. Dit stelt de leerling in staat om de toestand impliciet te volgen en de arm te selecteren die optimaal is voor de geïnferred recente toestand, in plaats van de gemiddelde waarde over alle toestanden.
• Beperking: LC-UCB kan falen als meerdere toestanden vergelijkbare beloningen produceren voor dezelfde actie (niet-identificeerbaarheid), wat leidt tot ambiguïteit in de toestand-inferentie.

2.2 Probing voor Toestandsvingerafdrukken

Om ambiguïteit op te lossen, introduceren de auteurs probing strategieën die "toestandsvingerafdrukken" genereren—gezamenlijke observaties van beloningen van meerdere armen die de verborgen toestand uniek identificeren. Twee paradigma's worden voorgesteld:

1. Randomized Probing UCB (RP-UCB): Toepasbaar wanneer meerdere experimentele eenheden (bijv. gebruikers) tegelijkertijd verschillende armen toegewezen kunnen krijgen. Het verzamelt echte gezamenlijke observaties $(r_0, r_1)$ van hetzelfde tijdstip.
2. Sequential Probing UCB (SP-UCB): Toepasbaar voor single-unit settings. Het bemonstert armen opeenvolgend (bijv. arm 0 op $t$, arm 1 op $t+1$) en behandelt het paar $(r_t, r_{t+1})$ als een synthetische vingerafdruk. Dit berust op de aanname dat de toestand "plakkerig" is (hoge zelf-transitie waarschijnlijkheid), zodat de toestand niet verandert tussen de twee probes.

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

Vaste probing-schema's veroorzaken regret zelfs wanneer het model confident is. De auteurs stellen Adaptive Probing varianten voor die vingerafdrukken alleen verversen wanneer dat nodig is, gebruikmakend van drie gating mechanismen:

• Residual Gate: Activeert een probe als de voorspellingsfout (Studentized residual) een drempelwaarde overschrijdt, wat wijst op modeldrift of een toestandstransitie.
• Uncertainty Gate: Activeert een probe als de marge tussen de top twee UCB-scores klein is, wat wijst op hoge onzekerheid in de armselectie.
• Staleness (Hazard) Gate: Activeert een probe als de vingerafdruk gedurende een bepaalde duur niet is bijgewerkt, gedefinieerd door een exponentiële hazard functie, om het gebruik van verouderde informatie te voorkomen.

Deze gates zijn onderworpen aan een minimale inter-probe gap ($\tau_{min}$) om oscillerend gedrag te voorkomen.

3. Belangrijkste Bijdragen

1. Algoritmisch Framework: De ontwikkeling van LC-UCB, RP-UCB, SP-UCB en hun adaptieve varianten (AdaRP-UCB, AdaSP-UCB) die lagged context combineren met gecoördineerde probing om latente-toestands-bandits te behandelen zonder expliciete schatting van de Markov-transitiemodellen.
2. Theoretische Analyse: Een decompositie van dynamische regret in drie componenten: representatie-ambiguïteit (benaderingsfout), probe-kosten, en drift nadat een vingerafdruk verouderd is geraakt. Het artikel biedt bounds die aantonen dat adaptieve probing de regret minimaliseert door deze factoren in balans te houden.
3. Empirische Validatie: Systematische evaluatie over variërende aantallen verborgen toestanden ($S$), transitieratent (zelf-transitie waarschijnlijkheid $p_{stay}$), beloningsruis ($\sigma$) en tijdshorizons ($T$).

4. Experimentele Resultaten

De algoritmen werden geëvalueerd tegen klassieke baselines (UCB1, Thompson Sampling), adversariële methoden (EXP3) en niet-stationaire methoden (Sliding Window UCB, Discounted UCB).

• Prestaties: De adaptieve probing methoden (met name AdaRP-UCB en AdaSP-UCB) presteerden consistent beter dan alle baselines in omgevingen waar de samenvattingen (vingerafdrukken) de toestanden konden onderscheiden en frequent genoeg werden bijgewerkt.
  • AdaRP-UCB behaalde de laagste regret in 12 van de 13 gerandomiseerde configuraties, wat significante winst laat zien in volatiele omgevingen.
  • AdaSP-UCB presteerde het best in single-unit settings met lage ruis, trage mixing of grote toestandsruimtes.
• Foutmodi: Het artikel identificeert specifieke condities waarin de methoden degraderen:
  • Hoge Ruis: Wanneer ruis ($\sigma$) hoog is ten opzichte van de arm-gap, worden vingerafdrukken zwak en kunnen niet-stationaire baselines (zoals D-UCB) beter presteren.
  • Zwakke Vingerafdruk-scheiding: Als verschillende toestanden vergelijkbare gezamenlijke beloningsverdelingen opleveren, kan de probing strategie hen niet onderscheiden.
  • Snelle Wisseling: Sequential probing (SP-UCB) faalt wanneer de toestand frequent verandert binnen het probe-venster (lage $p_{stay}$), waardoor de synthetische vingerafdruk ongeldig wordt.
• Ablatie Studies: Het verwijderen van de fingerprint feature ($\phi_{fp}$) verhoogde de regret aanzienlijk in sticky-state omgevingen, wat de waarde van gezamenlijke observaties bevestigt. Het verwijderen van de lagged context ($\phi_{lag}$) had in sommige gerandomiseerde settings een kleinere impact, wat suggereert dat adaptieve timing daar de primaire drijfveer was.

5. Betekenis en Claims

Het artikel claimt dat de primaire bijdrage een praktische aanpak is voor gestructureerde niet-stationariteit waarbij de omgeving evolueert via een autonoom Markov-proces. In tegenstelling tot standaard niet-stationaire bandits die veranderingen als willekeurige drift behandelen, of POMDP's die volledige observeerbaarheid of complexe decodering vereisen, gebruikt deze aanpak lichtgewicht geschiedenis-samenvattingen en probes om een actuele schatting van de optimale arm te behouden.

De auteurs benadrukken dat hun methoden het meest effectief zijn in regimes waar:

1. De latente toestand voorspelbaar is over korte horizonten (trage mixing).
2. De probing strategie voldoende statistieken (vingerafdrukken) kan genereren die de relevante toestanden scheiden.
3. De adaptieve gating mechanismen deze samenvattingen actueel kunnen houden zonder excessieve probe-regret te veroorzaken.

Het werk overbrugt de kloof tussen contextuele bandits en latent-state reinforcement learning door een computationeel efficiënte oplossing (gebaseerd op LinUCB) te bieden die geen volledige transitiedynamiek van de verborgen toestand vereist om te leren.