Quantum-Inspired Episode Selection for Monte Carlo Reinforcement Learning via QUBO Optimization

Sintesi Tecnica: Selezione degli Episodi Ispirata al Quantum per il Monte Carlo Reinforcement Learning tramite Ottimizzazione QUBO

Enunciato del Problema
Il Reinforcement Learning (RL) Monte Carlo (MC) affronta sfide significative riguardanti l'efficienza dei campioni, in particolare in ambienti caratterizzati da ricompense sparse, spazi di stato ampi e traiettorie temporalmente correlate. I metodi MC standard si basano sull'assunto che i campioni di dati siano indipendenti e identicamente distribuiti (i.i.d.), un assunto violato dalla natura markoviana delle traiettorie RL. Di conseguenza, gli stimatori MC soffrono di:

1. Propagazione della Varianza: I rendimenti presentano una varianza cumulativa, richiedendo un numero di episodi ($N_s$) che scala come $O(\epsilon^{-2})$ per ridurre l'errore di stima.
2. Diluizione Subottimale delle Traiettorie: Negli domini a ricompensa scarsa, lo stimatore viene diluito da traiettorie a bassa ricompensa, rendendo necessaria una crescita esponenziale della dimensione del campione per garantire una copertura sufficiente dei percorsi ottimali.
3. Esplosione Combinatoria: Teoricamente, la selezione di un sottoinsieme ottimale di $m$ episodi da $N$ candidati per massimizzare l'accuratezza della stima del valore è un problema NP-difficile isomorfo alla selezione delle caratteristiche (feature selection) e al set cover, con uno spazio di soluzioni di $\binom{N}{m}$.

Metodologia
Gli autori propongono MC+QUBO, un framework che riformula il processo di selezione degli episodi come un problema di Ottimizzazione Binaria Quadratica Non Vincolata (QUBO). Invece di utilizzare tutti gli episodi campionati per gli aggiornamenti della policy, il metodo filtra un batch di traiettorie per selezionare un sottoinsieme che massimizzi la ricompensa cumulativa promuovendo al contempo la copertura dello spazio degli stati (diversità).

• Formulazione QUBO: Il problema di selezione è codificato come:
  $$\min_{x \in \{0,1\}^n} \left( -\alpha \sum_{i=1}^n R_i x_i + \gamma \sum_{i<j} w_{ij} x_i x_j \right)$$
  Dove:

  • $x_i = 1$ indica la selezione dell'episodio $\tau_i$.
  • $R_i$ è la ricompensa cumulativa dell'episodio $i$.
  • $w_{ij}$ rappresenta la similarità a coppie tra gli episodi (ad esempio, la similarità di Jaccard tra gli insiemi di stati visitati).
  • $\alpha$ è un moltiplicatore di scala della ricompensa, e $\gamma$ pesa la penalità di similarità.
  • Il termine lineare ($-\alpha R_i$) favorisce gli episodi ad alta ricompensa, mentre il termine quadratico ($\gamma w_{ij}$) penalizza la ridondanza, incoraggiando la selezione di traiettorie diverse.

• Solver Ispirati al Quantum: Il problema QUBO viene risolto utilizzando sampler ispirati al quantum "black-box", specificamente Simulated Quantum Annealing (SQA) e Simulated Bifurcation (SB).

  • SQA imita l'annealing quantistico utilizzando aggiornamenti stocastici classici e Monte Carlo path-integral per simulare il tunneling quantistico tra minimi di energia.
  • SB utilizza un approccio di sistema dinamico classico in cui le variabili continue evolvono verso stati binari attraverso fenomeni di biforcazione.
  • Gli autori trattano questi solver come oracoli che forniscono soluzioni approssimate di alta qualità entro budget computazionali pratici.

• Integrazione: Il flusso di lavoro prevede la generazione di un batch di episodi, il calcolo di ricompense e similarità, la formulazione del QUBO, l'invio del problema al solver e l'utilizzo della migliore soluzione osservata (il vettore binario $x^*$) per determinare quali episodi utilizzare per aggiornare la tabella dei valori d'azione $Q(s, a)$ tramite MC a prima visita (first-visit MC).

Contributi Chiave

1. Riformulazione della Selezione degli Episodi: Il documento stabilisce un legame formale tra la selezione degli episodi MC e l'ottimizzazione combinatoria, dimostrando che il problema di selezione può essere mappato in una formulazione QUBO.
2. Integrazione Algoritmica: Introduce una pipeline concreta (Algoritmo 2) che inserisce un passaggio di filtraggio basato su QUBO tra il campionamento delle traiettorie e la valutazione della policy nel tipico apprendimento MC.
3. Validazione Empirica: Lo studio valuta il metodo su ambienti GridWorld a orizzonte finito di varie dimensioni ($3\times3$ a $20\times20$), confrontando MC+QUBO con un baseline MC vanilla.

Risultati
Gli esperimenti condotti in ambienti GridWorld dimostrano che MC+QUBO supera costantemente il vanilla MC in termini di velocità di convergenza e qualità della policy finale.

• Scalabilità: Il divario di prestazioni si amplia in ambienti più grandi ($\ge 10\times10$), dove le ricompense scarse e la crescita esponenziale dello spazio degli stati tipicamente ostacolano la valutazione MC standard.
• Convergenza: MC+QUBO converge in meno batch concentrandosi su traiettorie informative e diverse, filtrando efficacementamente gli episodi ridondanti.
• Insight di Design: Gli autori osservano che dare priorità alla copertura dello spazio degli stati (impostando l'influenza del peso della ricompensa vicino allo zero) ha prodotto un apprendimento più equilibrato e una migliore generalizzazione rispetto alla selezione guidata dalla ricompensa, che tendeva a causare una convergenza più rapida ma meno stabile.
• Prestazioni del Solver: I solver ispirati al quantum (SQA e SB) hanno superato gli euristiche classiche (come Tabu Search e Simulated Annealing) in questo contesto. La latenza computazionale era dominata dalla comunicazione in cloud piuttosto che dal tempo del solver stesso (che era trascurabile per $n \le 200$).

Significatività e Rivendicazioni
Il documento sostiene che l'integrazione dell'ottimizzazione ispirata al quantum come subroutine decisionale nel reinforcement learning offre un potenziamento pratico ai metodi MC, particolarmente per problemi con ricompense scarse e traiettorie correlate. Unendo RL e ottimizzazione combinatoria, lo studio suggerisce una via per algoritmi in cui i metodi quantistici e ispirati al quantum guidano attivamente il processo di apprendimento per superare l'inefficienza dei campioni.

Gli autori rimangono modesti riguardo all'ambito, notando che, sebbene il framework mostri potenziale in GridWorld, sono necessari lavori futuri per esplorare estensioni al controllo continuo, al RL gerarchico e ai sistemi multi-agente, nonché il deployment su hardware quantistico reale. L'attuale lavoro serve come prova di concetto per l'uso di solver ispirati alla fisica per ottimizzare la fase di selezione dei dati nel reinforcement learning.