Sintesi Tecnica: Auto-esplorazione per l'Apprendimento per Rinforzo Online

Definizione del Problema

Il documento affronta il fondamentale dilemma esplorazione-sfruttamento nell'apprendimento per rinforzo (RL) online per processi decisionali di Markov (MDP) a orizzonte infinito e scontati, con spazi di stato e di azione finiti. Nello specifico, si concentra sul setting on-policy, dove i dati vengono generati da una singola traiettoria da una catena di Markov, piuttosto che da un modello generativo o da un batch offline.

Gli algoritmi allo stato dell'arte attuali spesso si affidano a due assunzioni problematiche per garantire la convergenza:

1. Esplorazione Sufficiente: Assumono che ogni azione possa essere selezionata con una probabilità maggiore di zero per ogni stato (spesso imposta tramite un'esplicita esplorazione $\epsilon$-greedy). Tuttavia, in contesti on-policy non regolarizzati, le politiche ottimali possono essere deterministiche, causando il fallimento di questa assunzione.
2. Parametri Dipendenti dall'Algoritmo: I limiti della complessità campionaria esistenti dipendono spesso da parametri come il tempo di miscelazione (mixing time) e la distribuzione stazionaria delle catene di Markov indotte dalle politiche intermedie. Questi parametri sono ignoti nella pratica e possono essere arbitrariamente grandi, portando ad algoritmi sub-ottimali o non implementabili.

Il documento mira a sviluppare metodi privi di parametri (parameter-free) che raggiungano una complessità campionaria $O(\epsilon^{-2})$ indipendente dall'algoritmo, senza richiedere la conoscenza preventiva dei tassi di miscelazione o delle distribuzioni stazionarie, evitando al contempo la sub-ottimalità degli schemi di esplorazione espliciti.

Metodologia

Gli autori introducono una nuova classe di metodi chiamata Auto-esplorazione, integrata nello Stochastic Policy Mirror Descent (SPMD). L'idea centrale è quella di esplorare automaticamente sia gli spazi di stato che quelli di azione attraverso meccanismi basati sui dati anziché su iperparametri fissi.

1. Fondamento Teorico: Nuove Garanzie di Convergenza

Gli autori stabiliscono innanzitutto nuove garanzie di convergenza dell'ultimo iterato (last-iterate convergence) ad alta probabilità per lo SPMD. A differenza dei lavori precedenti che si concentrano sulla convergenza dell'iterato medio o del miglior iterato, questa analisi assicura che la politica finale sia vicina all'ottima.

• Assunzioni: L'analisi richiede solo che la funzione Q sia limitata e che l'estimatore stocastico abbia un piccolo bias pesato e momenti secondi limitati.
• Tecnica: La dimostrazione utilizza un nuovo raggruppamento degli iterati e una nuova analisi della divergenza di Bregman adattata al fattore di sconto $\gamma$, migliorando i limiti precedenti di un fattore di $O((1-\gamma)^{-2})$.

2. Setting Tabulare: Tempo di Esplorazione Dinamico

Per il caso tabulare, gli autori propongono un tempo di esplorazione dinamico per sostituire l'ignoto tempo di miscelazione.

• Truncated On-Policy Monte Carlo (TOMC): Utilizzano un estimatore troncato per la funzione Q. Se una coppia stato-azione non viene visitata entro un certo tempo, le viene assegnato un valore elevato per scorzarne la selezione.
• Stopping Dinamico: Inve al posto di un orizzonte di esplorazione fisso, l'algoritmo viene eseguito per una durata determinata dal tempo di primo contatto (first hitting time) delle coppie stato-azione. Questo tempo è casuale e guidato dai dati.
• Esplorazione Implicita: Il metodo si basa sull'esistenza di una politica deterministica ottimale che induce una catena di Markov irriducibile. Sotto questa assunzione, gli autori dimostrano che la politica esplora naturalmente stati "difficili da raggiungere" (esplorazione implicita dello stato) senza necessità di una randomizzazione esplicita.

3. Approssimazione Lineare di Funzione: Nuova Distribuzione di Campionamento

Per il setting di approssimazione lineare di funzione, gli autori affrontano la difficoltà di campionare dalla distribuzione stazionaria ignota.

• Distribuzione di Visitatio Scontata: Propongono una nuova distribuzione di campionamento basata sulla distribuzione di visita scontata ($\kappa^\pi_{s_{or}}$) partendo da uno stato di origine arbitrario, anziché dalla distribuzione stazionaria. Questa distribuzione è sempre ben definita e non richiede la stima dei tempi di miscelazione.
• Conditional Temporal Differencing (CTD): L'algoritmo costruisce un operatore stocastico utilizzando una strategia di campionamento a due fasi:
  1. Esplorazione dello Stato: Utilizzare una politica perturbata $\tilde{\pi}^{(S)}$ per raggiungere un stato di origine fisso $s_{or}$.
  2. Esplorazione dell'Azione: Una volta raggiunto $s_{or}$, passare alla politica corrente $\pi$ (con eventuale esplorazione dell'azione $\tilde{\pi}^{(A)}$) per un numero di passi distribuito geometricamente.
• Gestione del Bias: Il metodo distingue tra casi in cui l'errore di approssimazione della funzione è noto (esplorazione implicita sufficiente) rispetto a casi in cui è ignoto (richiede esplorazione esplicita per proteggersi dal bias).

Contributi Chiave

1. Complessità Campionaria $O(\epsilon^{-2})$ Indipendente dall'Algoritmo: Il documento presenta il primo algoritmo basato su SPMD per l'RL on-policy online che raggiunge una complessità campionaria $O(\epsilon^{-2})$ sia nel setting tabulare che in quello di approssimazione lineare di funzione. Fondamentalmente, il limite di complessità dipende da costanti specifiche del problema (come il tasso di miscelazione della politica ottimale) ma è indipendente dai parametri dipendenti dall'algoritmo (come i tassi di miscelazione delle politiche intermedie).
2. Implementazione Priva di Parametri: I metodi proposti non richiedono la conoscenza preventiva di tempi di miscelazione, distribuzioni stazionarie o altre costanti dipendenti dal problema. Utilizzano tempi di esplorazione dinamici derivati da osservazioni in tempo reale (tempi di contatto).
3. Convergenza dell'Ultimo Iterato ad Alta Probabilità: Gli autori forniscono garanzie rigorose di convergenza ad alta probabilità per l'ultimo iterato di SPMD, una garanzia più forte rispetto ai limiti di regret o di iterato medio comuni nella letteratura precedente.
4. Nuova Distribuzione di Campionamento: Nel setting di approssimazione di funzione, l'introduzione di una distribuzione di campionamento basata sulla distribuzione di visita scontata copre una classe più generale di catene di Markov rispetto a quelle che si affidano alle distribuzioni stazionarie.

Risultati

• Setting Tabulare: L'algoritmo raggiunge una precisione $\epsilon$ con probabilità $1-\delta$ utilizzando al massimo $\tilde{O}(D_{expl}(\delta) \cdot |A|^{2-\frac{1}{2}+\log_2(1/[1-\gamma])} (1-\gamma)^{-5} \epsilon^{-2})$ campioni. Qui, $D_{expl}(\delta)$ è una costante indipendente dall'algoritmo relativa alle proprietà di miscelazione della politica ottimale.
• Approssimazione di Funzione: Un limite di complessità campionaria simile è stabilito per il setting lineare. L'analisi rivela un compromesso: se l'errore di approssimazione della funzione è ignoto, l'esplorazione esplicita è necessaria per garantire la convergenza; se noto, l'esplorazione implicita è sufficiente.
• Miglioramento rispetto allo Stato dell'Arte: La complessità campionaria migliora rispetto ai precedenti limiti di esplorazione implicita (es. [37]) di un fattore di $O(|A|^{1/2}/(1-\gamma))$ e rimuove la dipendenza dai tassi di miscelazione specifici dell'algoritmo.

Significato e Rivendicazioni

Il documento sostiene di aver risolto un problema aperto di lunga data: raggiungere una complessità campionaria $O(\epsilon^{-2})$ on-policy e indipendente dall'algoritmo per l'RL scontato con stati e azioni finite senza schemi di esplorazione espliciti.

• Praticità: Eliminando la necessità di regolare gli iperparametri basati su incognite come i tempi di miscelazione o le distribuzioni stazionarie, i metodi sono "semplici da implementare" e robusti.
• Rigore Teorico: Il lavoro colma il divario tra garanzie teoriche e implementazione pratica fornendo limiti non asintotici che valgono per l'ultimo iterato, che è l'effettivo output dell'algoritmo.
• Novità: Il concetto di "auto-esplorazione" tramite tempi di arresto dinamici e l'uso di distribuzioni di visita scontata per il campionamento sono presentati come contributi innovativi che fanno avanzare la comprensione dell'esplorazione nell'RL online.

Gli autori posizionano questo lavoro come un passo verso la creazione di algoritmi di RL efficienti e implementabili in scenari reali dove la dinamica dell'ambiente (e quindi le proprietà di miscelazione) è ignota.