Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

Technische Samenvatting: Robuuste Gemiddelde-Beloning Markov Beslissingsprocessen

Probleemformulering
Dit werk onderzoekt de statistische complexiteit van het leren van een $\epsilon$-optimale policy voor distributioneel robuuste gemiddelde-belonings Markov Beslissingsprocessen (AMDP's) onder een generatief model-setting. De agent opereert binnen een nominale omgeving gedefinieerd door een transitiekernel $P^0$ en een beloningsfunctie $r$. Echter, de werkelijke dynamiek van de omgeving is onzeker en kan liggen binnen een voorgeschreven onzekerheidsverzameling $\mathcal{P}$ gecentreerd rond $P^0$. Specifiek beschouwt het artikel $(s, a)$-rechthoekige totale variatie (TV) onzekerheidsverzamelingen met een straal van maximaal $\sigma$.

Het doel is het maximaliseren van de robuuste gemiddelde beloning, gedefinieerd als de slechtste gemiddelde beloning op de lange termijn over alle transitiekernels in $\mathcal{P}$:
$$\rho^{\pi, \sigma} := \inf_{P \in \mathcal{P}} \lim_{T \to \infty} \mathbb{E}^\pi_P \left[ \frac{1}{T} \sum_{t=0}^{T-1} r(s_t, a_t) \right]$$
Het leerdoel is het berekenen van een policy $\hat{\pi}$ met behulp van $N$ monsters per staat-actie paar, zodanig dat $\rho^{\star, \sigma} - \rho^{\hat{\pi}, \sigma} \leq \epsilon$, waarbij $\rho^{\star, \sigma}$ de optimale robuuste gemiddelde beloning is.

Kernparameters en Structurele Aannames
De analyse steunt op twee cruciale structurele parameters:

1. Nominale Optimale Bias Span ($H_0$): De span van de biasfunctie die voldoet aan de nominale Bellman-optimaliteitsvergelijking.
2. Robuuste Optimale Bias Span ($H_\sigma$): De span van de biasfunctie die voldoet aan de robuuste Bellman-optimaliteitsvergelijking.

Het artikel stelt vast dat $H_0$ en $H_\sigma$ over het algemeen onafhankelijk zijn; noch controleert de één de ander. Een cruciale perturbatieschaal wordt geïdentificeerd als $\sigma H_0$, die het leerprobleem opsplitst in twee afzonderlijke regimes:

• High-Tolerance Regime ($\epsilon \gtrsim \sigma H_0$): De perturbatie veroorzaakt door onzekerheid is klein in verhouding tot de gewenste nauwkeurigheid.
• Low-Tolerance Regime ($\epsilon \lesssim \sigma H_0$): De perturbatie is significant, en louter nominale optimalisatie is onvoldoende om robuuste optimaliteit te garanderen.

Methodologie: Reductie-gebaseerde Plug-in Procedures
De kern van de methodologische bijdrage is een reductiekader dat het moeilijke robuuste gemiddelde-beloningsprobleem transformeert naar een meer hanteerbaar robuust gedisconteerd MDP (DMDP) probleem. De auteurs stellen twee algoritmen voor op basis van deze reductie:

1. Span-geïnformeerde Procedure (Algoritme 1): Veronderstelt dat $H_0$ en $H_\sigma$ bekend zijn. Het kiest adaptief tussen een nominale reductie (het oplossen van een standaard DMDP met de empirische kernel) en een robuuste reductie (het oplossen van een DMDP over de onzekerheidsverzameling). De keuze hangt af van de ordening van $H_0$ en $H_\sigma$ en het tolerantieregime. De discontfactor $\gamma$ wordt gekalibreerd op basis van de relevante span-parameter (bijv. $\gamma = 1 - \epsilon/(3H_\sigma)$).
2. Span-agnostische Procedure (Algoritme 2): Werkt zonder kennis van $H_0$ of $H_\sigma$. Het construeert een verzameling kandidaat-policies uit zowel nominale als robuuste reducties over een dyadisch rooster van discontfactoren. Vervolgens selecteert het de beste policy met behulp van een lower-confidence bound (LCB) op de robuste gemiddelde beloning, afgeleid van een "anker-certificaat" berekend uit een aparte data-batch. Dit stelt het algoritme in staat om adaptief de juiste reductie en de juiste discontfactor te kiezen op basis van de data.

De analyse maakt gebruik van drie belangrijke technische verfijningen om strakke grenzen te bereiken:

• Het vergelijken van het robuuste gedisconteerde probleem met een nominale referentie-oplossing (anker) om variantietermen te verfijnen.
• Het controleren van gedisconteerde waardefuncties via hun spans ($H_\sigma$) in plaats van de effectieve horizon.
• Het gebruik van gelokaliseerde concentratiegrenzen gestuurd door deze spans.

Hoofdresultaten: Minimax Sample Complexiteit
Het artikel biedt passende upper en lower bounds voor de minimax sample complexiteit $N_{SA}$ (monsters per staat-actie paar), tot aan logaritmische factoren. De complexiteit wordt gekarakteriseerd door een samenvatting van vier regimes gebaseerd op de ordening van $H_0$ en $H_\sigma$ en het tolerantieregime:

$$N_{SA} \asymp \frac{SA}{\epsilon^2} \times \begin{cases} \min\{H_0, H_\sigma\} & \text{indien } \epsilon \gtrsim \sigma H_0 \quad (\text{High Tolerance}) \\ \min\{H_0, H_\sigma\} + \sigma H_\sigma^2 & \text{indien } \epsilon \lesssim \sigma H_0 \quad (\text{Low Tolerance}) \end{cases}$$

• High-Tolerance Regime: De complexiteit wordt gedomineerd door de lineaire span-term $\min\{H_0, H_\sigma\}$. Als $H_\sigma \leq H_0$, levert de robuuste reductie een strakkere grens op dan de nominale.
• Low-Tolerance Regime: Een extra "robuustheid-specifieke" term $\sigma H_\sigma^2$ verschijnt, wat de kosten vertegenwoordigt van het afhandelen van distributionele onzekerheid wanneer een hoge precisie vereist is.
• Lower Bound: De auteurs bewijzen een minimax lower bound die overeenkomt met de upper bound, waarmee wordt vastgesteld dat de term $\sigma H_\sigma^2$ fundamenteel is en niet vermeden kan worden in het low-tolerance regime. Dit is de eerste lower bound die de statistische limieten van distributioneel robuuste AMDP's karakteriseert.

Betekenis en Claims
Het artikel beweert de eerste minimax-optimale karakterisering van de sample complexiteit voor distributioneel robuuste AMDP's te bieden. De belangrijkste bijdragen zijn:

• Resolutie van de Sample Complexiteit Kloof: Eerdere robuuste upper bounds (bijv. Roch et al., 2025, 2026) waren kwadratisch afhankelijk van robuuste span-parameters ($H_{Roch}^2$ of $H_{RHI}^2$) zonder onderscheid te maken tussen hoge en lage tolerantie. Dit werk verfijnt de afhankelijkheid naar $\min\{H_0, H_\sigma\}$ in het high-tolerance regime en identificeert de precieze $\sigma H_\sigma^2$ kosten in het low-tolerance regime.
• Adaptieve Algoritmen: De voorgestelde span-agnostische procedure (Algoritme 2) bereikt deze optimale snelheden zonder voorafgaande kennis van de span-parameters, waarbij het automatisch adapteert aan het regime en de relatieve grootte van $H_0$ en $H_\sigma$.
• Generaliteit: De resultaten blijven geldig zelfs als alleen de robuuste span $H_\sigma$ als begrensd wordt aangenomen, wat een complexiteit oplevert van $\tilde{\Theta}(SA(H_\sigma + \sigma H_\sigma^2)\epsilon^{-2})$.

Experimentele resultaten op gecontroleerde simulaties verifiëren de voorspelde lineaire afhankelijkheid van $\min\{H_0, H_\sigma\}$ en de kwadratische afhankelijkheid van $\sigma H_\sigma^2$ in het low-tolerance regime, evenals de adaptiviteit van het span-agnostische algoritme. De auteurs merken op dat toekomstig werk gekoppelde onzekerheidsstructuren en online (regret-gebaseerde) settings zou kunnen verkennen, maar het huidige werk richt zich strikt op de generatieve model-setting.