Sintesi Tecnica: Un briciolo di libertà fa la differenza: Algoritmi Classici e Quantistici per il Reinforcement Learning sotto un Modello Generativo

Definizione del Problema

Il documento affronta il problema dell'apprendimento di processi decisionali di Markov (MDP) in un contesto online, concentrandosi specificamente sulla minimizzazione del regret (la differenza tra la ricompensa accumulata dall'agente e quella di una politica ottimale). Gli autori considerano tre distinti setting di MDP:

1. MDP a orizzonte finito: Le interazioni avvengono su un numero fisso di passi $H$.
2. MDP a orizzonte infinito scontato: Le interazioni continuano indefinitamente con ricompense scontate da un fattore $\gamma \in [0, 1)$.
3. MDP a orizzonte infinito non scontato: Le interazioni continuano indefinitamente con criteri di ricompensa media, focalizzandosi specificamente su MDP debolmente comunicanti.

Una sfida centrale nel Reinforcement Learning (RL) è il compromesso tra esplorazione ed esploitazione (exploration-exploitation trade-off). Nel setting classico, gli agenti devono apprendere le probabilità di transizione $p(\cdot|s, a)$ interagendo con l'ambiente. Nel setting quantistico, sorge un problema fondamentale: gli standard oracle quantistici permettono la sovrapposizione e le operazioni inverse, il che può portare a misure di regret non definite se l'agente interagisce con l'ambiente in modo quantistico durante l'intero processo di apprendimento. Inoltre, i precedenti lavori di RL quantistico che tentavano di ottenere un regret polilogaritmico nel tempo $T$ si basavano su ipotesi errate riguardanti l'applicazione coerente della stima dell'ampiezza quantistica.

Metodologia

Il Modello Ibrido Online-Offline RL

Per risolvere i problemi definitori del regret nel RL quantistico e per sfruttare gli speedup quantistici, gli autori propongono un modello di RL ibrido online-offline. Questo modello separa il processo di apprendimento in due fasi distinte:

1. Fase Online (Esplorazione): L'agente interagisce con l'ambiente in modo classico. Sceglie azioni, riceve ricompense e osserva le transizioni di stato. Crucialmente, il regret si accumula durante questa fase. L'agente non ha accesso ad oracle quantistici qui.
2. Fase Offline (Apprendimento Generativo): All'agente viene concessa la "libertà" di interagire con l'ambiente tramite un modello generativo.
   • Nella fase offline classica, l'agente accede a un oracle di campionamento $C_p$ che restituisce stati successivi $s'$ dato $(s, a)$.
   • Nella fase offline quantistica, l'agente accede a un oracle quantistico $Q_p$ (e alla sua inversa) che prepara sovrapposizioni di stati successivi.
   • Vincolo: Il numero di chiamate all'oracle nella fase offline è limitato da una funzione della lunghezza della precedente fase online $\tau$, specificamente $O(\tau^\beta)$, dove $\beta \in [0, \infty)$ è un parametro di "budget". Ciò impedisce all'agente di ottenere una politica quasi ottimale con regret zero semplicemente interrogando eccessivamente l'oracle.

Approccio Algoritmico

Gli algoritmi proposti (Algoritmo 1) progrediscono per epoche. In ogni epoca $\ell$:

1. Computazione Offline: Utilizzando i dati raccolti nella fase online precedente (lunghezza $\tau_{\ell-1}$), l'agente calcola una politica $\epsilon_\ell$-ottimale.
   • Classico: Utilizza algoritmi sample-optimal noti (ad es. Sidford et al.) per calcolare le politiche.
   • Quantistico: Gli autori introducono nuovi algoritmi quantistici per calcolare le politiche ottimali sotto un modello generativo. Questi algoritmi utilizzano la stima della media quantistica (Kothari e O'Donnell) e la ricerca del minimo/massimo quantistica (Dürr e Høyer) per accelerare l'iterazione del valore (value iteration).
2. Esecuzione Online: La politica calcolata $\pi^{(\ell)}$ viene eseguita nell'ambiente per una durata determinata da un trucco del raddoppio (doubling trick) (aumentando l'orizzonte di un fattore 2 o $2H$).
3. Analisi del Regret: Il regret totale è limitato dalla somma della sub-ottimalità delle politiche utilizzate in ogni fase online.

Principali Contributi Tecnici

1. Nuovi Algoritmi Quantistici per Modelli Generativi:

   • Orizzonte Finito: Gli autori progettano algoritmi quantistici che migliorano la complessità di query rispetto ai metodi classici. Combinano la value iteration quantizzata con tecniche di riduzione della varianza. La complessità di query è $\tilde{O}(\min\{H^{2.5}SA/\epsilon, H^3S\sqrt{A}/\epsilon\})$, migliorando la dipendenza da $H$ e $A$ rispetto ai limiti classici.
   • Orizzonte Infinito Scontato: Si ottengono miglioramenti simili, con complessità di query $\tilde{O}(\min\{\Gamma^{1.5}SA/\epsilon, \Gamma^3S\sqrt{A}/\epsilon\})$.
   • Orizzonte Infinito Non Scontato: Questo è un nuovo contributo. Gli autori propongono un algoritmo quantistico per MDP debolmente comunicanti assumendo che l'operatore di Bellman ottimale sia una contrazione $\nu$-span a $J$-stadi. La complessità è $\tilde{O}(\Lambda S \sqrt{A} / \epsilon)$.

2. Correzione di Precedenti Lavori di RL Quantistico:
   Il documento critica lavori precedenti (ad es. Ganguly et al., Zhong et al.) che dichiaravano un regret polilogaritmico. Gli autori sostengono che tali lavori assumevano erroneamente che la stima dell'ampiezza quantistica potesse essere eseguita su una collezione di stati memorizzati anziché richiedere applicazioni sequenziali e coerenti dell'oracle e della sua inversa. Il modello ibrido proposto corregge questo punto imponendo una distinta fase offline in cui tali operazioni coerenti possono essere eseguite senza incorrere in regret.

3. Limiti del Regret sotto il Modello Ibrido:
   Gli autori derivano i limiti del regret sia per i setting classici che per quelli quantistici come funzione del parametro di budget $\beta$:

   • Orizzonte Finito:
     • Classico: $\tilde{O}(\sqrt{HSAT})$ (corrispondente allo stato dell'arte) quando $\beta \ge 2$.
     • Quantistico: $\tilde{O}(\min\{H^{1.5}SA, H^2S\sqrt{A}\} T^{1-\beta})$ per $\beta < 1$, e polilogaritmico in $T$ per $\beta \ge 1$.
   • Orizzonte Infinito Scontato:
     • Quantistico: Ottiene un regret $\tilde{O}(\text{polylog}(T))$ quando $\beta \ge 1$, superando la barriera classica $\Omega(\sqrt{T})$.
   • Orizzonte Infinito Non Scontato:
     • Quantistico: Ottiene un regret $\tilde{O}(\Lambda S \sqrt{A} \cdot \text{polylog}(T))$ per $\beta \ge 1$, migliorando significativamente il limite $\tilde{O}(\Lambda S^5 A^4)$ dei precedenti lavori quantistici.

Risultati e Significato

Il documento sostiene che il "briciolo di libertà" fornito dalla fase offline generativa permette un sostanziale miglioramento dell'efficienza dell'apprendimento.

• Vantaggio Quantistico: Il risultato più significativo è la dimostrazione che i computer quantistici possono raggiungere un regret polilogaritmico nell'orizzonte temporale $T$ (specificamente quando $\beta \in [1, 2)$), mentre gli algoritmi classici sono fondamentalmente limitati a un regret $\Omega(\sqrt{T})$ in questi setting. Ciò rappresenta un miglioramento esponenziale nella dipendenza da $T$.
• Dipendenza dai Parametri: Gli algoritmi quantistici migliorano la dipendenza dalla dimensione dello spazio degli stati $S$, dello spazio delle azioni $A$ e dell'orizzonte $H$ (o orizzonte efficace $\Gamma$) rispetto sia agli algoritmi classici che ai precedenti tentativi quantistici.
• Validità del Modello: Il documento stabilisce che il modello ibrido online-offline è un framework necessario e significativo per il RL quantistico. Esso risolve l'ambiguità nella definizione del regret nelle interazioni quantistiche e corregge le falle teoriche della letteratura precedente che assumeva un'esplorazione quantistica priva di regret senza tale separazione.

Gli autori concludono che, sebbene il vantaggio esponenziale quantistico in $T$ svanisca quando il budget $\beta$ è molto grande ($\beta \ge 2$, dove anche gli algoritmi classici raggiungono un regret polilogaritmico), esiste un intervallo critico ($\beta \in [1, 2)$) in cui i computer quantistici forniscono un vantaggio sostanziale. Il documento identifica questo intervallo come l'area primaria in cui gli speedup quantistici nel RL sono più impattanti sotto il modello proposto.