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

Sintesi Tecnica: Processi Decisionali di Markov con Ricompensa Media Robusta

Formulazione del Problema
Questo lavoro investiga la complessità statistica dell'apprendimento di una politica $\epsilon$-ottimale per i Processi Decisionali di Markov con Ricompensa Media (AMDP) Distribuzionalmente Robusti in un setting di modello generativo. L'agente opera all'interno di un ambiente nominale definito da un kernel di transizione $P^0$ e una funzione di ricompensa $r$. Tuttavia, la dinamica del vero ambiente è incerta e può trovarsi all'interno di un insieme di incertezza prescritto $\mathcal{P}$ centrato in $P^0$. Nello specifico, il documento considera insiemi di incertezza a variazione totale (TV) $(s, a)$-rettangolari con un raggio al massimo $\sigma$.

L'obiettivo è massimizzare la ricompensa media robusta, definita come la peggiore ricompensa media a lungo termine su tutti i kernel di transizione 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]$$
L'obiettivo dell'apprendimento è calcolare una politica $\hat{\pi}$ utilizzando $N$ campioni per coppia stato-azione tale che $\rho^{\star, \sigma} - \rho^{\hat{\pi}, \sigma} \leq \epsilon$, dove $\rho^{\star, \sigma}$ è la ricompensa media robusta ottimale.

Parametri Chiave e Assunzioni Strutturali
L'analisi si basa su due parametri strutturali critici:

1. Span del Bias Ottimale Nominale ($H_0$): Lo span della funzione di bias che soddisfa l'equazione di Bellman ottimalità nominale.
2. Span del Bias Ottimale Robusto ($H_\sigma$): Lo span della funzione di bias che soddisfa l'equazione di Bellman ottimalità robusta.

Il documento stabilisce che $H_0$ e $H_\sigma$ sono generalmente indipendenti; nessuno dei due controlla l'altro. Viene identificata una scala di perturbazione cruciale, $\sigma H_0$, che separa il problema di apprendimento in due distinti regimi:

• Regime ad Alta Tolleranza ($\epsilon \gtrsim \sigma H_0$): La perturbazione causata dall'incertezza è piccola rispetto alla precisione target.
• Regime a Bassa Tolleranza ($\epsilon \lesssim \sigma H_0$): La perturbazione è significativa e l'ottimizzazione nominale da sola è insufficiente per garantire l'ottimalità robusta.

Metodologia: Procedure Plug-in basate su Riduzione
Il nucleo del contributo metodologico è un framework di riduzione che trasforma il difficile problema della ricompensa media robusta in un problema di MDP scontato (DMDP) robusto più trattabile. Gli autori propongono due algoritmi basati su questa riduzione:

1. Procedura Informata dallo Span (Algoritmo 1): Assume che $H_0$ e $H_\sigma$ siano noti. Seleziona adattivamente tra una riduzione nominale (risoluzione di un DMDP standard con il kernel empirico) e una riduzione robusta (risoluzione di un DMDP sull'insieme di incertezza). La scelta dipende dall'ordinamento di $H_0$ e $H_\sigma$ e dal regime di tolleranza. Il fattore di sconto $\gamma$ è calibrato in base allo span rilevante (ad esempio, $\gamma = 1 - \epsilon/(3H_\sigma)$).
2. Procedura Agnostica rispetto allo Span (Algoritmo 2): Opera senza la conoscenza di $H_0$ o $H_\sigma$. Costruisce un insieme di politiche candidate da sia riduzioni nominali che robuste attraverso una griglia dicotomica di fattori di sconto. Successivamente, seleziona la migliore politica utilizzando un limite inferiore di confidenza (LCB) sulla ricompensa media robusta, derivato da un "certificato ancora" (anchor certificate) calcolato da un batch di dati separato. Ciò consente all'algoritmo di scegliere adattivamente la riduzione e il fattore di sconto corretti in base ai dati.

L'analisi sfrutta tre raffinamenti tecnici chiave per ottenere limiti stretti:

• Confrontare il problema scontato robusto con una soluzione di riferimento nominale (ancora) per restringere i termini di varianza.
• Controllare le funzioni di valore scontate tramite i loro span ($H_\sigma$) piuttosto che l'orizzonte temporale effettivo.
• Utilizzare limiti di concentrazione localizzati governati da questi span.

Risultati Principali: Complessità Campionaria Minimax
Il documento fornisce limiti superiore e inferiore (upper e lower bounds) corrispondenti per la complessità campionaria minimax $N_{SA}$ (campioni per coppia stato-azione), a meno di fattori logaritmici. La complessità è caratterizzata da un riepilogo in quattro regimi basato sull'ordinamento di $H_0$ e $H_\sigma$ e sul regime di tolleranza:

$$N_{SA} \asymp \frac{SA}{\epsilon^2} \times \begin{cases} \min\{H_0, H_\sigma\} & \text{se } \epsilon \gtrsim \sigma H_0 \quad (\text{Alta Tolleranza}) \\ \min\{H_0, H_\sigma\} + \sigma H_\sigma^2 & \text{se } \epsilon \lesssim \sigma H_0 \quad (\text{Bassa Tolleranza}) \end{cases}$$

• Regime ad Alta Tolleranza: La complessità è dominata dal termine lineare dello span $\min\{H_0, H_\sigma\}$. Se $H_\sigma \leq H_0$, la riduzione robusta fornisce un limite più stretto di quella nominale.
• Regime a Bassa Tollerza: Appare un termine aggiuntivo "specifico della robustezza" $\sigma H_\sigma^2$, che rappresenta il costo di gestire l'incertezza distributiva quando è richiesta un'alta precisione.
• Limite Inferiore (Lower Bound): Gli autori dimostrano un limite inferiore minimax che corrisponde al limite superiore, stabilendo che il termine $\sigma H_\sigma^2$ è fondamentale e non può essere evitato nel regime a bassa tolleranza. Questo è il primo limite inferiore che caratterizza i limiti statistici degli AMDP distribuzionalmente robusti.

Significatività e Rivendicazioni
Il documento sostiene di fornire la prima caratterizzazione minimax-ottimale della complessità campionaria per gli AMDP con ricompensa media distribuzionalmente robusti. I contributi chiave includono:

• Risoluzione del Gap della Complessità Campionaria: I precedenti limiti superiori robusti (ad esempio, Roch et al., 2025, 2026) dipendevano quadraticamente dai parametri di span robusti ($H_{Roch}^2$ o $H_{RHI}^2$) senza distinguere tra alta e bassa tolleranza. Questo lavoro affina la dipendenza a $\min\{H_0, H_\sigma\}$ nel regime ad alta tolleranza e identifica il costo preciso di $\sigma H_\sigma^2$ nel regime a bassa tolleranza.
• Algoritmi Adattivi: La procedura agnostica rispetto allo span (Algoritmo 2) raggiunge questi tassi ottimali senza la conoscenza preventiva dei parametri di span, adattandosi automaticamente al regime e alle grandezze relative di $H_0$ e $H_\sigma$.
• Generalità: I risultati valgono anche se viene assunto solo che lo span robusto $H_\sigma$ sia limitato, producendo una complessità di $\tilde{\Theta}(SA(H_\sigma + \sigma H_\sigma^2)\epsilon^{-2})$.

I risultati sperimentali su simulazioni controllate verificano la dipendenza lineare predetta da $\min\{H_0, H_\sigma\}$ e la dipendenza quadratica da $\sigma H_\sigma^2$ nel regime a bassa tolleranza, nonché l'adattività dell'algoritmo agnostico rispetto allo span. Gli autori osservano che lavori futuri potrebbero esplorare strutture di incertezza accoppiate e setting online (basati sul regret), ma il presente lavoro si concentra strettamente sul setting del modello generativo.