Technische Zusammenfassung: Modellbasiertes Bootstrap für gesteuerte Markov-Ketten

Problemstellung

Die Arbeit adressiert die Herausforderung der statistischen Inferenz für endliche gesteuerte Markov-Ketten (CMCs) in Szenarien, in denen die das Daten generierende Verhaltenspolitik $\pi_b$ nichtstationär oder historienabhängig sein kann. Dieses Szenario ist im Offline-Reinforcement-Learning (RL) weit verbreitet, wo Daten von einer unbekannten Politik $\pi_b$ gesammelt werden, die nicht notwendigerweise die Annahmen der Stationarität oder Markov-Eigenschaft erfüllt.

Bestehende Bootstrap-Verfahren für Markov-Ketten stützen sich häufig auf Stationarität oder spezifische Mischungsbedingungen, die für allgemeine CMCs mit historienabhängigen Steuerungen nicht gelten. Darüber hinaus erfordern Standard-Plug-in-Konfidenzintervalle (CIs), die auf zentralen Grenzwertsätzen (CLTs) basieren, eine Kovarianzschätzung, was die Leistung bei endlichen Stichproben verschlechtern kann. Die Autoren identifizieren zwei offene Probleme:

1. Kann ein modellbasiertes Bootstrap für endliche CMCs entwickelt werden, ohne Stationarität oder Markov-Eigenschaft der Steuerpolitik zu verlangen?
2. Kann die Verteilungskonsistenz eines solchen Bootstrap-Schätzers nachgewiesen und auf nachgelagerte RL-Aufgaben wie Off-Policy-Evaluation (OPE) und Optimal Policy Recovery (OPR) erweitert werden?

Methodik

Modell- und Datenaufbau

Die Autoren betrachten eine endliche CMC $\{(X_i, A_i)\}_{i \ge 0}$ mit Zustandsraum $\mathcal{S}$ und Aktionsraum $\mathcal{A}$. Der Übergangskernel ist $M(a)_{s,t} = P(X_{i+1}=t | X_i=s, A_i=a)$. Der beobachtete Offline-Datensatz $\mathcal{D}_n$ besteht aus $K$ Episoden fester Länge $T$ (wobei $n=KT$), die von einer unbekannten Verhaltenspolitik $\pi_b$ generiert wurden. Die Politik $\pi_b$ darf nichtstationär und historienabhängig sein.

Aus $\mathcal{D}_n$ berechnen die Autoren:

• Einen zählbasierten empirischen Übergangsschätzer: $\hat{M}(a)_{s,t} = N(a)_{s,t} / N(a)_s$.
• Eine empirische Verhaltenspolitik: $\hat{\pi}_b(a|s) = N(a)_s / N_s$.

Modellbasiertes Bootstrap-Verfahren

Das vorgeschlagene Verfahren konstruiert eine Bootstrap-CMC $\{(X^*_i, A^*_i)\}_{i \ge 0}$ unter Verwendung des empirischen Übergangskernels $\hat{M}$ und der empirischen Verhaltenspolitik $\hat{\pi}_b$.

1. Initialisierung: Für jede Bootstrap-Replikation $j$ startet der Prozess im beobachteten Anfangszustand der ursprünglichen Episode, $X^{*(k,j)}_0 = X^{(k)}_0$.
2. Simulation: Übergänge werden sequentiell generiert, indem Aktionen $A^{*(k,j)}_i \sim \hat{\pi}_b(\cdot | X^{*(k,j)}_i)$ und nächste Zustände $X^{*(k,j)}_{i+1} \sim \hat{M}(A^{*(k,j)}_i)_{X^{*(k,j)}_i, \cdot}$ gesampelt werden.
3. Schätzung: Aus dem simulierten Datensatz $\mathcal{D}^*_n$ wird ein Bootstrap-Übergangsschätzer $\hat{M}^*$ berechnet.
4. Replikation: Dieser Prozess wird $B$-mal wiederholt, um Bootstrap-Replikate $\hat{M}^{*(1)}, \dots, \hat{M}^{*(B)}$ zu erhalten.

Nachgelagerte Anwendungen

Das Bootstrap wird auf zwei nachgelagerte Ziele angewendet:

• Off-Policy-Evaluation (OPE): Schätzung von Wertfunktionen $V_\pi$ und Q-Funktionen $Q_\pi$ für eine feste Zielpolitik $\pi$ durch Lösen der Bellman-Gleichungen mit $\hat{M}$ und $\hat{M}^*$.
• Optimal Policy Recovery (OPR): Schätzung optimaler Wertfunktionen $V_\star$ und $Q_\star$ durch Lösen optimaler Bellman-Gleichungen mit $\hat{M}$ und $\hat{M}^*$.

Konfidenzintervalle werden unter Verwendung der empirischen Quantile der Bootstrap-Replikate (Percentile-CI) oder über Pivot-Methoden konstruiert.

Wichtige theoretische Beiträge

1. Verteilungskonsistenz des Bootstraps

Die Arbeit stellt die ersten Ergebnisse zur Verteilungskonsistenz für modellbasierte Bootstraps in endlichen CMCs mit potenziell nichtstationären oder historienabhängigen Politiken bereit.

• Einzelketten-Regime ($K=1, T \to \infty$): Satz 1 beweist, dass bedingt auf die Daten $\mathcal{D}_n$, $\sqrt{n} \text{vec}(\hat{M}^* - \hat{M})$ in Verteilung gegen einen Gaußschen Grenzwert $N(0, \bar{\Lambda})$ konvergiert, der der asymptotischen Verteilung des ursprünglichen Schätzers $\sqrt{n} \text{vec}(\hat{M} - M)$ entspricht.
• Episoden-Regime ($T$ fest, $K \to \infty$): Proposition 1 erweitert dieses Ergebnis auf das episodenbasierte Setting, indem die Episoden über Pseudo-Übergänge in eine einzige Kette eingebettet werden. Es bestätigt, dass das Bootstrap auch dann konsistent bleibt, wenn Episoden durch Resets getrennt sind.

Technische Werkzeuge:

• Ein neuartiges Bootstrap-Gesetz der großen Zahlen (LLN) für Besuchszahlen ($N^*_s/n \to p_s$ fast sicher).
• Eine neuartige Anwendung des Martingal-Zentralen Grenzwertsatzes (CLT) für Bootstrap-Übergangsincremente unter Verwendung schwacher Mischungsbedingungen (Annahmen 1–3), um die Abhängigkeitsstruktur zu behandeln.

2. Gültigkeit für OPE und OPR

Proposition 2 erweitert die Verteilungskonsistenz auf die Schätzer für Wert- und Q-Funktionen unter Verwendung der Delta-Methode.

• Die Autoren verifizieren die Hadamard-Differenzierbarkeit der Bellman-Operatoren bezüglich der Übergangsblockmatrix.
• Für OPE konvergieren die Bootstrap-Replikate von $V_\pi$ und $Q_\pi$ gegen dieselben Gaußschen Grenzwerte wie die ursprünglichen Schätzer.
• Für OPR erreichen die Bootstrap-Replikate von $V_\star$ und $Q_\star$ unter einer Nicht-Entartungsbedingung (streng positiver Abstand zwischen optimalen und suboptimalen Aktionen) ebenfalls Verteilungskonsistenz.

Experimentelle Ergebnisse

Die Autoren bewerten die Leistung bei endlichen Stichproben am RiverSwim-Problem ($S=6, A=2$), einem Benchmark, der für schwierige Exploration bekannt ist aufgrund unausgewogener Besuchshäufigkeiten und nahezu entarteter optimaler Politiken.

• Setup: Vergleiche wurden gegenüber dem episodenbasierten Bootstrap (Hao et al., 2021) und Plug-in-CLT-CIs (Zhu et al., 2024; Su et al., 2026) über verschiedene Stichprobengrößen ($n$) und Episodenlängen ($T$) durchgeführt.
• Ergebnisse:
  • Die vorgeschlagenen modellbasierten Bootstrap-Percentile-CIs übertreffen die Baselines erheblich und erreichen eine nahezu nominale Abdeckung (z. B. 0,48–0,54 für 50 %, 0,87–0,94 für 90 %, 0,92–0,97 für 95 %) in gut beprobten Regimen ($n \ge 500$).
  • Baselines (episodenbasierter Bootstrap und Plug-in-CLT) zeigen systematische Unterabdeckung, insbesondere bei kleinen Stichprobengrößen und kurzen Episodenlängen.
  • Der episodenbasierte Bootstrap versagt bei $n=50$ vollständig, wenn $T \ge 50$ (Kollaps auf Null-Abdeckung), da eine einzelne Episode die Bootstrap-Variation eliminiert.
  • Die Leistung ist am schwächsten für selten besuchte Zustands-Aktions-Paare (nahe Zustand 6) und kurze Horizonte ($T=10$), was mit den theoretischen Einschränkungen der asymptotischen Normalität und Nicht-Entartung übereinstimmt.

Bedeutung und Einschränkungen

Bedeutung:
Die Arbeit liefert eine rigorose theoretische Grundlage für die Verwendung modellbasierter Bootstraps im Offline-RL und adressiert spezifisch die Lücke, in der Verhaltenspolitiken nichtstationär oder historienabhängig sind. Sie zeigt, dass solche Bootstraps asymptotisch gültige Konfidenzintervalle sowohl für Übergangskernel als auch für nachgelagerte RL-Ziele liefern, ohne eine explizite Kovarianzschätzung zu erfordern.

Einschränkungen und zukünftige Richtungen (wie von den Autoren angegeben):

• Belohnungsfunktion: Die Analyse geht von einer bekannten Belohnungsfunktion aus. Obwohl die Autoren anmerken, dass die Gültigkeit wahrscheinlich auch dann gilt, wenn die Belohnungsschätzung konvergiert, werden die Effekte von Schätzfehlern der Belohnung bei endlichen Stichproben nicht analysiert.
• Zustands-Aktions-Raum: Die aktuellen Ergebnisse beschränken sich auf endliche Zustands-Aktions-Räume. Die Erweiterung auf Funktionsapproximation oder kontinuierliche Räume bleibt zukünftiger Arbeit vorbehalten.
• Asymptotische Regime: Die episodenbasierte Analyse geht davon aus, dass $T$ fest ist und $K \to \infty$. Die Konsistenz des Bootstraps im Regime, in dem $K$ fest ist ($K>1$) und $T \to \infty$, bleibt eine offene Frage.
• Nicht-stationäre Politiken: Obwohl die Theorie nicht-stationäre Politiken zulässt, wurden in den numerischen Experimenten vorwiegend stationäre Verhaltenspolitiken verwendet; weitere Experimente mit nicht-stationären Politiken werden vorgeschlagen.