Technische Samenvatting: Modelgebaseerde Bootstrap van Gecontroleerde Markovketens

Probleemstelling

Het artikel behandelt de uitdaging van statistische inferentie voor eindige Gecontroleerde Markovketens (CMC's) in situaties waarbij het gedragsbeleid dat de data genereert, mogelijk niet-stationair is of afhankelijk van de geschiedenis. Dit scenario komt veel voor in offline versterkende leer (RL), waarbij data wordt verzameld door een onbekend beleid $\pi_b$ dat niet noodzakelijk voldoet aan aannames van stationariteit of Markov-eigenschappen.

Bestaande bootstrap-methoden voor Markovketens vertrouwen vaak op stationariteit of specifieke mengcondities die niet gelden voor algemene CMC's met op geschiedenis gebaseerde controles. Bovendien vereisen standaard plug-in betrouwbaarheidsintervallen (BI's) gebaseerd op Central Limit Theorems (CLT's) schatting van de covariantie, wat de prestaties bij eindige steekproeven kan verslechteren. De auteurs identificeren twee open problemen:

1. Kan een modelgebaseerde bootstrap worden ontwikkeld voor eindige CMC's zonder stationariteit of Markov-eigenschappen van het controlebeleid te vereisen?
2. Kan de distributieve consistentie van een dergelijke bootstrap-schatting worden vastgesteld en worden uitgebreid naar downstream RL-taken zoals Off-Policy Evaluation (OPE) en Optimal Policy Recovery (OPR)?

Methodologie

Model en Data-Opzet

De auteurs beschouwen een eindige CMC $\{(X_i, A_i)\}_{i \ge 0}$ met toestandsruimte $\mathcal{S}$ en actieruimte $\mathcal{A}$. De overgangskern is $M(a)_{s,t} = P(X_{i+1}=t | X_i=s, A_i=a)$. De waargenomen offline dataset $\mathcal{D}_n$ bestaat uit $K$ episodes van vaste lengte $T$ (waarbij $n=KT$), gegenereerd door een onbekend gedragsbeleid $\pi_b$. Het beleid $\pi_b$ mag niet-stationair zijn en afhankelijk van de geschiedenis.

Uit $\mathcal{D}_n$ berekenen de auteurs:

• Een op tellingen gebaseerde empirische overgangsschatting: $\hat{M}(a)_{s,t} = N(a)_{s,t} / N(a)_s$.
• Een empirisch gedragsbeleid: $\hat{\pi}_b(a|s) = N(a)_s / N_s$.

Modelgebaseerde Bootstrapprocedure

De voorgestelde methode construeert een bootstrap-CMC $\{(X^*_i, A^*_i)\}_{i \ge 0}$ met behulp van de empirische overgangskern $\hat{M}$ en het empirische gedragsbeleid $\hat{\pi}_b$.

1. Initialisatie: Voor elke bootstrap-repliek $j$ begint het proces bij de waargenomen beginstaat van de oorspronkelijke episode, $X^{*(k,j)}_0 = X^{(k)}_0$.
2. Simulatie: Overgangen worden sequentieel gegenereerd door acties te stalen $A^{*(k,j)}_i \sim \hat{\pi}_b(\cdot | X^{*(k,j)}_i)$ en volgende toestanden $X^{*(k,j)}_{i+1} \sim \hat{M}(A^{*(k,j)}_i)_{X^{*(k,j)}_i, \cdot}$.
3. Schatting: Uit de gesimuleerde dataset $\mathcal{D}^*_n$ wordt een bootstrap-overgangsschatting $\hat{M}^*$ berekend.
4. Replicatie: Dit proces wordt $B$ keer herhaald om bootstrap-replieken $\hat{M}^{*(1)}, \dots, \hat{M}^{*(B)}$ te verkrijgen.

Downstream Toepassingen

De bootstrap wordt toegepast op twee downstream doelen:

• Off-Policy Evaluation (OPE): Schatten van waardenfuncties $V_\pi$ en Q-functies $Q_\pi$ voor een vast doelpolitiek $\pi$ door Bellman-vergelijkingen op te lossen met $\hat{M}$ en $\hat{M}^*$.
• Optimal Policy Recovery (OPR): Schatten van optimale waardenfuncties $V_\star$ en $Q_\star$ door optimale Bellman-vergelijkingen op te lossen met $\hat{M}$ en $\hat{M}^*$.

Betrouwbaarheidsintervallen worden geconstrueerd met behulp van de empirische kwantielen van de bootstrap-replieken (percentiel-BI) of via pivot-methoden.

Belangrijkste Theoretische Bijdragen

1. Distributieve Consistentie van de Bootstrap

Het artikel stelt de eerste resultaten vast voor distributieve consistentie van modelgebaseerde bootstraps in eindige CMC's met mogelijk niet-stationaire of op geschiedenis gebaseerde beleidsplannen.

• Regime van Eén Keten ($K=1, T \to \infty$): Stelling 1 bewijst dat, conditioneel op de data $\mathcal{D}_n$, $\sqrt{n} \text{vec}(\hat{M}^* - \hat{M})$ in verdeling convergeert naar een Gaussische limiet $N(0, \bar{\Lambda})$, wat overeenkomt met de asymptotische verdeling van de oorspronkelijke schatter $\sqrt{n} \text{vec}(\hat{M} - M)$.
• Episodisch Regime ($T$ vast, $K \to \infty$): Proposition 1 breidt dit resultaat uit naar de episodische setting door de episodes te embedden in één enkele keten via pseudo-overgangen. Het bevestigt dat de bootstrap consistent blijft, zelfs wanneer episodes gescheiden zijn door resets.

Technische Hulpmiddelen:

• Een nieuw Bootstrap Wet van de Grote Getallen (WGG) voor bezoektellingen ($N^*_s/n \to p_s$ bijna zeker).
• Een nieuwe toepassing van de Martingale Central Limit Theorem (CLT) voor bootstrap-overgangsincrementen, waarbij gebruik wordt gemaakt van zwakke mengcondities (Aannames 1–3) om de afhankelijkheidsstructuur te hanteren.

2. Validiteit voor OPE en OPR

Proposition 2 breidt de distributieve consistentie uit naar de schatters voor waarden- en Q-functies met behulp van de Delta-methode.

• De auteurs verifiëren de Hadamard-differentieerbaarheid van de Bellman-operatoren met betrekking tot de overgangs-blokmatrix.
• Voor OPE convergeren de bootstrap-replieken van $V_\pi$ en $Q_\pi$ naar dezelfde Gaussische limieten als de oorspronkelijke schatters.
• Voor OPR bereiken de bootstrap-replieken van $V_\star$ en $Q_\star$, onder een niet-degeneratievoorwaarde (een strikt positief gat tussen optimale en suboptimale acties), ook distributieve consistentie.

Experimentele Resultaten

De auteurs evalueren de prestaties bij eindige steekproeven op het RiverSwim-probleem ($S=6, A=2$), een benchmark die bekend staat om moeilijke exploratie vanwege onbalans in bezoekfrequenties en bijna-degenererende optimale beleidsplannen.

• Opzet: Vergelijkingen werden gemaakt met de episodische bootstrap (Hao et al., 2021) en plug-in CLT BI's (Zhu et al., 2024; Su et al., 2026) over verschillende steekproefgroottes ($n$) en episode-lengtes ($T$).
• Vondsten:
  • De voorgestelde modelgebaseerde bootstrap percentiel-BI's presteren aanzienlijk beter dan de baselines, met een dekking die dicht bij de nominale waarde ligt (bijv. 0,48–0,54 voor 50%, 0,87–0,94 voor 90%, 0,92–0,97 voor 95%) in goed-gestalde regimes ($n \ge 500$).
  • Baselines (episodische bootstrap en plug-in CLT) vertonen systematische onderdekking, met name bij kleine steekproefgroottes en korte episode-lengtes.
  • De episodische bootstrap faalt volledig bij $n=50$ wanneer $T \ge 50$ (instortend tot nul dekking) omdat een enkele episode de bootstrap-variatie elimineert.
  • De prestaties zijn het zwakst voor zelden bezochte staat-actieparen (nabij staat 6) en korte horizonnen ($T=10$), wat consistent is met de theoretische beperkingen van asymptotische normaliteit en niet-degeneratie.

Betekenis en Beperkingen

Betekenis:
Het artikel biedt een rigoureuze theoretische onderbouwing voor het gebruik van modelgebaseerde bootstraps in offline RL, specifiek gericht op het gat waar gedragsbeleid niet-stationair is of afhankelijk van de geschiedenis. Het toont aan dat dergelijke bootstraps asymptotisch geldige betrouwbaarheidsintervallen opleveren voor zowel overgangskernen als downstream RL-doelen zonder expliciete schatting van de covariantie te vereisen.

Beperkingen en Toekomstige Richtingen (zoals gesteld door de auteurs):

• Beloningsfunctie: De analyse gaat uit van een bekende beloningsfunctie. Hoewel de auteurs opmerken dat de validiteit waarschijnlijk geldt als de beloningsschatting convergeert, worden de effecten bij eindige steekproeven van fouten in de beloningsschatting niet geanalyseerd.
• Staat-Actieruimte: De huidige resultaten zijn beperkt tot eindige staat-actieruimten. Uitbreiding naar functiebenadering of continue ruimten wordt overgelaten aan toekomstig werk.
• Asymptotische Regimes: De episodische analyse gaat uit van een vaste $T$ en $K \to \infty$. De consistentie van de bootstrap in het regime waarbij $K$ vast is ($K>1$) en $T \to \infty$ blijft een open vraag.
• Niet-Stationaire Beleidsplannen: Hoewel de theorie niet-stationaire beleidsplannen aankunt, werden in de numerieke experimenten voornamelijk stationaire gedragsbeleid gebruikt; verdere experimenten met niet-stationaire beleidsplannen worden voorgesteld.