Technische Samenvatting: Minimax PAC-grenzen voor leren in Exogene Contextuele MDP's

1. Probleemstelling

Dit artikel onderzoekt de steekproefcomplexiteit van leren in tabulaire gedisconteerde Markov Beslissingsprocessen (MDP's) met exogene i.i.d. contexten. Het model wordt gedefinieerd door een tupel $\mathcal{M} = (\mathcal{X}, \mathcal{Z}, \mathcal{A}, P, r, \mu, \gamma)$, waarbij:

• $\mathcal{X}$ een eindige gecontroleerde toestandsruimte is.
• $\mathcal{A}$ een eindige actieruimte is.
• $\mathcal{Z}$ een eindige contextruimte is.
• $\gamma \in [0, 1)$ de disconteringsfactor is.
• $P: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to \Delta(\mathcal{X})$ de transitiekernel is.
• $r: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to [0, 1]$ de beloningsfunctie is.
• $\mu$ de onbekende distributie over contexten is.

Op elk tijdstip $t$ wordt een context $Z_t$ onafhankelijk getrokken uit $\mu$ en onthuld aan de agent vóór de selectie van een actie. De agent kiest $A_t$, ontvangt een beloning $r(X_t, A_t, Z_t)$, en gaat over naar de volgende toestand $X_{t+1} \sim P(\cdot | X_t, A_t, Z_t)$. Cruciaal is dat de volgende context $Z_{t+1}$ onafhankelijk is van de acties van de agent en de huidige toestand, en enkel afhangt van $\mu$.

De leerdoelen zijn Beleidsevaluatie (Policy Evaluation, PE), Best-Value Schatting (Best-Value Estimation, BVE), en Best-Beleid Extractie (Best-Policy Extraction, BPE). De steekproefcomplexiteit wordt gemeten door een paar $(n_{\text{learn}}, m_{\text{query}})$, wat het aantal oracle-oproepen vertegenwoordigt die worden gedaan tijdens een offline leerfase en het aantal oproepen tijdens de beslissingstijd (query) fase, respectievelijk. Het artikel beschouwt twee regimes:

1. Bekende Dynamiek: $P$ en $r$ zijn bekend; enkel $\mu$ is onbekend.
2. Volledig Onbekend: Zowel $\mu$ als $P$ zijn onbekend.

2. Methodologie

2.1 Kerninzicht: Gemiddelde Waardefuncties

De centrale methodologische bijdrage is de reductie van het probleem van de uitgebreide ruimte $\mathcal{X} \times \mathcal{Z}$ naar de gecontroleerde toestandsruimte $\mathcal{X}$. De auteurs definiëren de gemiddelde waardefunctie $\bar{V}(x) := \mathbb{E}_{Z \sim \mu}[V(x, Z)]$.
Omdat de volgende context onafhankelijk van $\mu$ wordt getrokken, hangt de Bellman-optimaliteitsvergelijking voor de gemiddelde waarde $\bar{V}^\star$ enkel af van de transitiekernel die over $\mu$ is gemiddeld:
$$\bar{V}^\star(x) = \mathbb{E}_{Z \sim \mu} \left[ \max_{a \in \mathcal{A}} \left( r(x, a, Z) + \gamma \sum_{x'} P(x' | x, a, Z) \bar{V}^\star(x') \right) \right]$$
Deze formulering stelt de leerling in staat om een vector in $\mathbb{R}^{|\mathcal{X}|}$ te schatten in plaats van in $\mathbb{R}^{|\mathcal{X}||\mathcal{Z}|}$, waardoor de complexiteit effectief wordt ontkoppeld van de grootte van de contextruimte $|\mathcal{Z}|$.

2.2 Algoritmisch Kader: Variance-Gereduceerde Halvering

Het artikel maakt gebruik van een variance-gereduceerd waarde-iteratieschema (geadapteerd van Sidford et al., 2019) om de gemiddelde waardefuncties te schatten. Het algoritme werkt in twee fasen:

1. Offline Fase (Anker Schatting): Het algoritme berekent een hoog-waarschijnlijkheid ondergrens (anker) voor de Bellman-operator toegepast op een initiële waardeschatting. Dit vereist een grote batch monsters om de variantie van het empirische gemiddelde te beheersen.
2. Online/Iteratieve Fase (Variance-Gereduceerde Updates): Opvolgende iteraties schatten enkel het verschil tussen de huidige Bellman-backup en het anker. Door dezelfde monsters te hergebruiken voor de verschilterm, wordt de variantie aanzienlijk verminderd, wat kleinere steekproeven per iteratie mogelijk maakt.

Het algoritme gebruikt een "halveringsstrategie", waarbij herhaaldelijk een subroutine (HALFERR) wordt aangeroepen die de foutenmarge $u$ halveert totdat de doelaccuratesse $\epsilon$ is bereikt.

2.3 Omgaan met Onbekende Dynamiek

In het volledig onbekende regime kan het algoritme de Bellman-backup niet exact berekenen, zelfs niet met een gesamplede context. In plaats daarvan trekt het algoritme voor elke gesamplede context $Z$ een transitie-monster $X' \sim P(\cdot | x, \pi(x, Z), Z)$ om een onbevooroordeelde schatting van de backup te vormen. Dit introduceert een extra variantieterm gerelateerd aan de transitiekernel, die rigoureus wordt begrensd met behulp van een martingaal-decompositie die zowel de context- als de transitiewillekeurheid meeneemt.

3. Belangrijkste Resultaten

3.1 Bekende Dynamiek, Onbekende Contextdistributie ($P, r$ bekend, $\mu$ onbekend)

Wanneer de transitiekernel en beloningen bekend zijn, stelt het artikel vast dat de steekproefcomplexiteit onafhankelijk is van de grootte van de contextruimte $|\mathcal{Z}|$.

• Complexiteit: Het algoritme bereikt de doelstellingen met $(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(\beta^3/\epsilon^2), 0)$, waarbij $\beta = (1-\gamma)^{-1}$.
• Optimaliteit: Een minimax ondergrens van $\Omega(\beta^3/\epsilon^2)$ is bewezen, wat aantoont dat de bovengrens exact is tot aan de logaritmische factoren.
• Implicatie: De leerling hoeft niet de waarden voor elk $(x, z)$ paar te schatten; het schatten van de gemiddelde waarde $\bar{V}$ volstaat. De query-fase vereist geen extra monsters ($m_{\text{query}}=0$) omdat de lift van $\bar{V}$ naar $V(x, z)$ een deterministische Bellman-backup is met de bekende $P$ en $r$.

3.2 Toepassing op Perfecte Eén-Staps Lookahead

Het kader wordt toegepast op de perfecte één-staps transitie lookahead (waarbij de agent alle mogelijke volgende toestanden voor alle acties observeert voordat hij handelt).

• Deze setting wordt getoond als een speciaal geval van de exogene contextuele MDP waarbij de contextruimte de verzameling van alle mogelijke transitie-tensoren is.
• Het resultaat levert een steekproefcomplexiteit van $\tilde{O}(\beta^3/\epsilon^2)$ lookahead-monsters op.
• In termen van individuele tabulaire transities komt dit overeen met $\tilde{O}(\beta^3 |\mathcal{X}||\mathcal{A}|/\epsilon^2)$, wat de eerdere grens van Lu et al. (2025) met een factor $\beta$ verbetert.

3.3 Volledig Onbekend Regime ($P$ en $\mu$ onbekend)

Wanneer zowel de dynamiek als de contextdistributie onbekend zijn, richt het artikel zich op Beleidsevaluatie (PE).

• Complexiteit: Het algoritme bereikt $(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2), \tilde{O}(\beta^2/\epsilon^2))$.
• Afweging: De offline fase leert de gemiddelde waarde $\bar{V}^\pi$ (wat $|\mathcal{X}|$ transities per contextmonster kost). De query-fase schat de uiteindelijke één-staps transitieverwachting bij de gerealiseerde $(x, z)$ met behulp van verse monsters.
• Ondergrenzen: Het artikel bewijst bijpassende ondergrenzen, waarmee wordt aangetoond dat:
  • $m_{\text{query}} = \Omega(\beta^2/\epsilon^2)$ noodzakelijk is voor accuratesse op beslistijd.
  • $n_{\text{learn}} + |\mathcal{X}| m_{\text{query}} = \Omega(|\mathcal{X}|\beta^3/\epsilon^2)$ noodzakelijk is voor offline leren.
• Betekenis: Zelfs in het volledig onbekende regime blijft de complexiteit onafhankelijk van $|\mathcal{Z}|$. De onbekende dynamiek dwingt niet tot schatting op de uitgebreide ruimte; het introduceert enkel stochasticiteit in de beslistijd "lift" van $\bar{V}$ naar $V(x, z)$.

4. Betekenis en Claims

Het artikel claimt de eerste minimax-optimale PAC-grenzen te bieden voor leren in exogene contextuele MDP's. De primaire bijdragen zijn:

1. Ontkoppeling van Contextgrootte: Het toont aan dat de statistische prijs van grote contextruimtes vermijdbaar is. De steekproefcomplexiteit hangt af van de gecontroleerde toestandsruimte $|\mathcal{X}|$ maar niet van de contextruimte $|\mathcal{Z}|$.
2. Optimale Snelheden: De afgeleide snelheden ($\tilde{O}(\beta^3/\epsilon^2)$ voor bekende dynamiek en $\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2)$ voor volledig onbekende dynamiek) zijn tot aan de logaritmische factoren aangetoond minimax-optimaal te zijn.
3. Verenigd Kader: Het kader omvat en verbetert bestaande resultaten voor perfecte één-staps lookahead en biedt een rigoureuze analyse van de offline/online steekproefafweging.

De auteurs merken op dat hoewel de ondergrens strak is bij het zuiver online punt ($n_{\text{learn}}=0$) en het herbruikbare-oracle punt (hun voorgestelde algoritme), de strakheid van de grens voor tussenliggende afwegingen een open vraag blijft. Daarnaast wordt het uitbreiden van deze resultaten naar Best-Policy Extraction (BPE) in het volledig onbekende regime overgelaten aan toekomstig werk, vanwege de moeilijkheid van het omgaan met selectiebias bij het schatten van het maximum over acties vanuit transitie-monsters.