Technische Samenvatting: Leren in Markoviaanse Bandieten met Niet-observeerbare Toestanden en Beperkte Beslissingsepochen

1. Probleemdefinitie

Dit artikel behandelt het probleem van regret-minimalisatie in markoviaanse bandieten onder twee specifieke beperkingen:

1. Niet-observeerbare Toestanden: De controller observeert de interne toestand van de armen (Markovketens) niet. De enige beschikbare feedback is de beloning die door de geactiveerde arm wordt gegenereerd. Dit komt overeen met een "full bandit feedback" setting waarbij de toestandsruimte verborgen is.
2. Beperkte Beslissingsepochen: De controller kan niet willekeurig bij elke tijdstap van arm wisselen. In plaats daarvan is wisselen alleen toegestaan op specifieke beslissingsepochen ($\tau_i$), wat stoptijden zijn die worden bepaald door de stroom van beloningen. Specifiek moet de controller zich aan een arm blijven houden totdat een specifiek signaal (bijv. een niet-nul beloning) wordt ontvangen.

De armen worden gemodelleerd als Markov Decision Processes (MDP's) waarbij de transitiedynamiek afhangt van de vraag of de arm actief of passief is. Het systeem evolueert zodanig dat niet-geactiveerde armen verder evolueren volgens hun passieve kernels ($p^0_a$), terwijl geactiveerde armen evolueren volgens actieve kernels ($p^1_a$).

2. Leerkader en Benchmark

De auteurs beperken hun analyse tot een "pure regret" benchmark.

• Pure Policies: Een beleid wordt gedefinieerd als "puur" als het vanaf het begin tot het einde van de leerk horizon één enkele arm selecteert zonder ooit te wisselen.
• Regret Definitie: De regret is het verschil tussen de cumulatieve beloning van het leeralgoritme en de cumulatieve beloning van het beste pure beleid (de arm met de hoogste asymptotische winst).

Motivatie voor Pure Policies:
Hoewel pure policies over het algemeen suboptimaal zijn voor "restless" bandieten (waar inactieve armen evolueren), introduceren de auteurs een klasse bandieten genaamd self-degrading restless bandits. In deze gevallen, als een arm inactief wordt gelaten, heeft de verwachte bias (een maat voor de afwijking van het gemiddelde rendement) de neiging om af te nemen of constant te blijven ten opzichte van de observaties van de controller. Het artikel bewijst dat voor self-degrading bandieten, pure policies asymptotisch optimaal zijn. Deze klasse generaliseert "rested" bandieten (waar inactieve armen bevriezen) en omvat niet-triviale restless voorbeelden zoals non-preemptieve Gilbert-Elliott kanalen en Nerlove-Arrow modellen.

3. Methodologie: UCB-NOM

Het artikel stelt UCB-NOM voor (Upper Confidence Bound for Non-Observable Markovian bandits), een optimistisch algoritme geïnspireerd door het UCB-principe.

Belangrijkste componenten van UCB-NOM:

1. Empirische Winstschatter: Het algoritme schat de winst ($g_a$) van een arm $a$ door de beloningen te middelen die werden verzameld wanneer die arm actief was.
2. Optimistische Index Constructie: Om de niet-observeerbaarheid van toestanden en de beperkingen af te handelen, construeert het algoritme een optimistische bovengrens $\tilde{g}_a(t)$ voor de werkelijke winst. Deze index bevat:
   • De empirische gemiddelde beloning.
   • Een exploratiebonus (betrouwbaarheidsinterval) die rekening houdt met:
     • Het aantal pulls ($N_a(t)$).
     • Het aantal keren dat het algoritme naar arm $a$ is gewisseld (wisselkosten).
     • De bias span ($sp(b_a)$) van de Markovketen van de arm, die de maximale afwijking van de biasfunctie kwantificeert.
3. Doubling Trick: Om te voldoen aan de eigenschap van "zelden wisselen" die vereist is voor theoretische garanties, gebruikt het algoritme een doubling trick. Zodra een arm is geselecteerd, wordt deze gespeeld totdat het aantal bezoeken aan de arm verdubbeld is. Dit zorgt ervoor dat het aantal wisselingen logaritmisch groeit met het aantal pulls.

Geadresseerde Theoretische Uitdagingen:

• Niet-observeerbaarheid: In tegenstelling tot eerdere werken (bijv. RCA door Tekin & Liu) die vertrouwen op het observeren van toestanden om regeneratiecycli te triggeren, kan UCB-NOM geen regeneratie gebruiken. In plaats daarvan begrenst het de fout met behulp van de bias span en het aantal wisselingen.
• Beperkte Epochen: Het algoritme moet rekening houden met de vertraging tussen beslissingsepochen. De analyse gaat uit van een bovengrens ($C_\tau$) op de verwachte tijd tot de volgende beslissingsepoche.

4. Belangrijkste Resultaten en Theoretische Garanties

A. Ondergrenzen (Onmogelijkheid van Logaritmische Regret)

Het artikel stelt vast dat zonder voorkennis van de structuur van de bandiet, logaritmische regret ($O(\log T)$) onbereikbaar is voor consistente, zelden-wisselende algoritmen.

• Theorem 4: Voor elk consistent, zelden-wisselend algoritme schaalt de verwachte regret als $\omega(\log T)$ (super-logaritmisch). Dit wordt bewezen door alternatieve modellen te construeren die via beloningen alleen ononderscheidbaar zijn van het ware model maar verschillende optimale armen hebben, waardoor het algoritme gedwongen wordt om suboptimale armen excessief te trekken om ze te onderscheiden.

B. UCB-NOM Prestaties (Algemeen Geval)

• Theorem 6: UCB-NOM bereikt een regret-bound van $O(f(T)^2 \log T)$, waarbij $f(T)$ een "span proxy" functie is die naar oneindig divergeert.
• Betekenis: Door $f(T)$ te kiezen die arbitrair langzaam divergeert, kan UCB-NOM het idealistische logaritmische regime arbitrair dicht benaderen, waardoor het de super-logaritmische ondergrens effectief evenaart.

C. Prestaties met Voorkennis (Begrensde Bias Span)

Als het algoritme wordt voorzien van een bekende bovengrens $D$ op de bias span van alle armen (en de vertraging van de beslissingsepoche), verbeteren de prestaties aanzienlijk.

• Theorem 8 (Instance-Dependent): Met een vaste span proxy $f \equiv D$, bereikt UCB-NOM een $O(\log T)$ instance-afhankelijke regret.
• Theorem 9 (Worst-Case): Onder dezelfde aanname van een begrensde span bereikt het algoritme een worst-case regret van $O(\sqrt{T \log T})$.

D. Afstemming en Betrouwbaarheidsparameters

Het artikel analyseert de keuze van de betrouwbaarheidsparameter $\delta(t)$. Het suggereert dat het "onder-optimistisch" zijn (het kiezen van een kleinere $\delta(t)$ om de betrouwbaarheidsintervallen te verbreden) de voorkeur heeft boven de standaard stochastic bandits. Dit komt omdat de ruis in Markoviaanse estimators groter kan zijn dan de beloningsvariantie suggereert vanwege de bias span, wat grotere exploratiebonussen vereist om de optimistische eigenschap te behouden.

5. Betekenis en Bijdragen

Het artikel claimt de volgende bijdragen:

1. Probleemformulering: Het formaliseert een leersetting die niet-observeerbare toestanden en endogene beperkte beslissingsepochen combineert, gemotiveerd door communicatienetwerken (bijv. non-preemptieve kanaalschema's).
2. Self-Degrading Bandits: Het identificeert en definieert een klasse van restless bandieten waarbij pure policies optimaal zijn, wat het gebruik van pure regret als benchmark rechtvaardigt.
3. Fundamentele Limieten: Het bewijst dat de niet-observeerbaarheid van toestanden in combinatie met beperkte epochen inherent een logaritmische regret verhindert in het algemene geval, waarmee een super-logaritmische ondergrens wordt vastgesteld.
4. Algoritme Ontwerp: Het introduceert UCB-NOM, een algoritme dat bijna optimale regret bereikt zonder staatsobservatie. Cruciaal is dat de regret bounds niet afhankelijk zijn van het aantal toestanden ($|S_a|$) van de onderliggende Markovketens, maar van de bias span.
5. Structurele Inzichten: Het demonstreert dat met een eenvoudige voorkennis (een bovengrens op de bias span), de klassieke logaritmische regret garanties van stochastic bandits kunnen worden teruggewonnen, wat suggereert dat staat-niet-observeerbaarheid een "milde ongemakkelijkheid" is in self-degrading settings, mits structurele grenzen bekend zijn.

De auteurs concluderen dat hoewel de setting complexer is dan standaard stochastic bandits, het voorgestelde framework en algoritme robuuste theoretische garanties bieden zonder de complexe technieken te vereisen die gewoonlijk geassocieerd worden met Partially Observable Markov Decision Processes (POMDP's), mits men zich houdt aan de pure regret benchmark.