Riepilogo Tecnico: Limiti Minimax PAC per l'Apprendimento in MDP Contestuali Esogeni

1. Definizione del Problema

Questo articolo investiga la complessità campionaria dell'apprendimento in MDP tabulari scontati con contesti i.i.d. esogeni. Il modello è definito da una tupla $\mathcal{M} = (\mathcal{X}, \mathcal{Z}, \mathcal{A}, P, r, \mu, \gamma)$, dove:

• $\mathcal{X}$ è uno spazio di stati controllati finito.
• $\mathcal{A}$ è uno spazio di azioni finito.
• $\mathcal{Z}$ è uno spazio di contesti finito.
• $\gamma \in [0, 1)$ è il fattore di sconto.
• $P: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to \Delta(\mathcal{X})$ è il kernel di transizione.
• $r: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to [0, 1]$ è la funzione di ricompensa.
• $\mu$ è la distribuzione sconosciuta sui contesti.

Ad ogni passo temporale $t$, un contesto $Z_t$ viene estratto indipendentemente da $\mu$ e rivelato all'agente prima della selezione dell'azione. L'agente sceglie $A_t$, riceve la ricompensa $r(X_t, A_t, Z_t)$ e transita verso $X_{t+1} \sim P(\cdot | X_t, A_t, Z_t)$. Fondamentalmente, il contesto successivo $Z_{t+1}$ è indipendente dalle azioni dell'agente e dallo stato corrente, dipendendo solo da $\mu$.

Gli obiettivi di apprendimento sono la Valutazione della Policy (PE), la Stima del Valore Ottimo (BVE) e l'Estrazione della Miglior Policy (BPE). La complessità campionaria è misurata da una coppia $(n_{\text{learn}}, m_{\text{query}})$, che rappresenta il numero di chiamate all'oracolo effettuate durante una fase di apprendimento offline e il numero di chiamate effettuate durante la fase decisionale (query), rispettivamente. L'articolo considera due regimi:

1. Dinamiche Note: $P$ e $r$ sono note; solo $\mu$ è sconosciuta.
2. Completamente Sconosciute: Sia $\mu$ che $P$ sono sconosciute.

2. Metodologia

2.1 Intuizione Centrale: Funzioni di Valore Medie

Il contributo metodologico centrale è la riduzione del problema dallo spazio aumentato $\mathcal{X} \times \mathcal{Z}$ allo spazio degli stati controllati $\mathcal{X}$. Gli autori definiscono la funzione di valore media $\bar{V}(x) := \mathbb{E}_{Z \sim \mu}[V(x, Z)]$.
Poiché il contesto successivo viene estratto indipendentemente da $\mu$, l'equazione di Bellman ottimalità per il valore medio $\bar{V}^\star$ dipende solo dal kernel di transizione mediato su $\mu$:
$$\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]$$
Questa formulazione permette al learner di stimare un vettore in $\mathbb{R}^{|\mathcal{X}|}$ piuttosto che in $\mathbb{R}^{|\mathcal{X}||\mathcal{Z}|}$, disaccoppiando efficacemente la complessità dalla dimensione dello spazio dei contesti $|\mathcal{Z}|$.

2.2 Framework Algoritmico: Halving con Riduzione della Varianza

L'articolo impiega uno schema di iterazione di valore con riduzione della varianza (adattato da Sidford et al., 2019) per stimare le funzioni di valore medie. L'algoritmo opera in due fasi:

1. Fase Offline (Stima dell'Ancora): L'algoritmo calcola un limite inferiore ad alta probabilità (ancora) per l'operatore di Bellman applicato a una stima iniziale del valore. Ciò richiede un grande batch di campioni per controllare la varianza della media empirica.
2. Fase Online/Iterativa (Aggiornamenti con Riduzione della Varianza): Le iterazioni successive stimano solo la differenza tra l'attuale backup di Bellman e l'ancora. Riutilizzando gli stessi campioni per il termine di differenza, la varianza è significativamente ridotta, permettendo dimensioni campionarie minori per iterazione.

L'algoritmo utilizza una strategia di "halving" ( dimezzamento), chiamando ripetutamente una subroutine (HALFERR) che dimezza il limite di errore $u$ finché non viene raggiunta l'accuratezza target $\epsilon$.

2.3 Gestione delle Dinamiche Sconosciute

Nel regime completamente sconosciuto, l'algoritmo non può calcolare esattamente il backup di Bellman anche con un contesto campionato. Invece, per ogni contesto campionato $Z$, l'algoritmo estrae un campione di transizione $X' \sim P(\cdot | x, \pi(x, Z), Z)$ per formare una stima non viesata del backup. Ciò introduce un termine di varianza aggiuntivo relativo al kernel di transizione, che viene rigorosamente limitato tramite una decomposizione martingala che tiene conto sia della casualità del contesto che di quella della transizione.

3. Risultati Chiave

3.1 Dinamiche Note, Distribuzione del Contesto Sconosciuta ($P, r$ note, $\mu$ sconosciuta)

Quando il kernel di transizione e le ricompense sono noti, l'articolo stabilisce che la complessità campionaria è indipendente dalla dimensione dello spazio dei contesti $|\mathcal{Z}|$.

• Complessità: L'algoritmo raggiunge gli obiettivi con $(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(\beta^3/\epsilon^2), 0)$, dove $\beta = (1-\gamma)^{-1}$.
• Ottimalità: Un limite inferiore minimax di $\Omega(\beta^3/\epsilon^2)$ è dimostrato, mostrando che il limite superiore è stretto (tight) fino a fattori logaritmici.
• Implicazione: Il learner non ha bisogno di stimare i valori per ogni coppia $(x, z$; stimare il valore medio $\bar{V}$ è sufficiente. La fase di query non richiede campioni aggiuntivi ($m_{\text{query}}=0$) perché il "lift" da $\bar{V}$ a $V(x, z)$ è un backup di Bellman deterministico utilizzando $P$ e $r$ noti.

3.2 Applicazione al Lookahead Perfetto a Un Passo

Il framework viene applicato all'impostazione di lookahead della transizione perfetta a un passo (dove l'agente osserva tutti i possibili stati successivi per tutte le azioni prima di agire).

• Questa impostazione è mostrata essere un caso speciale dell'MDP contestuale esogeno dove lo spazio dei contesti è l'insieme di tutti i possibili tensori di transizione.
• Il risultato produce una complessità campionaria di $\tilde{O}(\beta^3/\epsilon^2)$ campioni di lookahead.
• In termini di singole transizioni tabulari, ciò corrisponde a $\tilde{O}(\beta^3 |\mathcal{X}||\mathcal{A}|/\epsilon^2)$, migliorando il precedente limite di Lu et al. (2025) di un fattore $\beta$.

3.3 Regime Completamente Sconosciuto ($P$ e $\mu$ sconosciuti)

Quando sia le dinamiche che la distribuzione del contesto sono sconosciute, l'articolo si concentra sulla Valutazione della Policy (PE).

• Complessità: L'algoritmo raggiunge $(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2), \tilde{O}(\beta^2/\epsilon^2))$.
• Trade-off: La fase offline apprende il valore medio $\bar{V}^\pi$ (costando $|\mathcal{X}|$ transizioni per campione di contesto). La fase di query stima l'aspettativa di transizione a un passo finale al realizzato $(x, z)$ utilizzando nuovi campioni.
• Limiti Inferiori: L'articolo dimostra limiti inferiori corrispondenti, dimostrando che:
  • $m_{\text{query}} = \Omega(\beta^2/\epsilon^2)$ è necessario per l'accuratezza al tempo decisionale.
  • $n_{\text{learn}} + |\mathcal{X}| m_{\text{query}} = \Omega(|\mathcal{X}|\beta^3/\epsilon^2)$ è necessario per l'apprendimento offline.
• Significato: Anche nel regime completamente sconosciuto, la complessità rimane indipendente da $|\mathcal{Z}|$. Le dinamiche sconosciute non costringono la stima sullo spazio aumentato; introducono solo la stocasticità nel "lift" decisionale da $\bar{V}$ a $V(x, z)$.

4. Significato e Rivendicazioni

L'articolo sostiene di fornire i primi limiti PAC minimax-ottimali per l'apprendimento in MDP contestuali esogeni. I suoi contributi primari sono:

1. Disaccoppiamento dalla Dimensione del Contesto: Dimostra che il prezzo statistico di grandi spazi di contesti è evitabile. La complessità campionaria dipende dallo spazio degli stati controllati $|\mathcal{X}|$ ma non dallo spazio dei contesti $|\mathcal{Z}|$.
2. Rate Ottimali: I rate derivati ($\tilde{O}(\beta^3/\epsilon^2)$ per dinamiche note e $\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2)$ per dinamiche completamente sconosciute) sono mostrati essere minimax-ottimali fino a fattori logaritmici.
3. Framework Unificato: Il framework assorbe e migliora i risultati esistenti per il lookahead perfetto a un passo e fornisce un'analisi rigorosa del trade-off tra campioni offline/online.

Gli autori osservano che, sebbene il limite inferiore sia stretto al punto puramente online ($n_{\text{learn}}=0$) e al punto dell'oracolo riutilizzabile (il loro algoritmo proposto), la compattezza del limite per i trade-off intermedi rimane una questione aperta. Inoltre, l'estensione di questi risultati alla Best-Policy Extraction (BPE) nel regime completamente sconosciuto è lasciata come lavoro futuro a causa della difficoltà di gestire il bias di selezione quando si stima il massimo sulle azioni partendo da campioni di transizione.