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

Technische Samenvatting: Quantum-geïnspireerde Episode-selectie voor Monte Carlo Reinforcement Learning via QUBO-optimalisatie

Probleemstelling
Monte Carlo (MC) reinforcement learning staat voor aanzienlijke uitdagingen met betrekking tot de efficiëntie van steekproeven, met name in omgevingen die worden gekenmerkt door ijle beloningen (sparse rewards), grote toestandsruimten en temporeel gecorreleerde trajecten. Standaard MC-methoden vertrouwen op de aanname dat datastalen onafhankelijk en identiek verdeeld (i.i.d.) zijn, een aanname die wordt geschonden door het Markoviaanse karakter van RL-trajecten. Bijgevolg lijden MC-schatters aan:

1. Variantie-propagatie: Returns vertonen cumulatieve variantie, wat een aantal episodes ($N_s$) vereist dat schaalt als $O(\epsilon^{-2})$ om de schattingsfout te verminderen.
2. Suboptimale Traject-dilutie: In domeinen met ijle beloningen wordt de schatter verdund door trajecten met lage beloningen, wat een exponentiële groei van de steekproefomvang noodzakelijk maakt om voldoende dekking van optimale paden te garanderen.
3. Combinatorische Explosie: Theoretisch gezien is het selecteren van een optimale subset van $m$ episodes uit $N$ kandidaten om de nauwkeurigheid van de waardeschatting te maximaliseren, een NP-hard probleem dat isomorf is aan feature selectie en set cover, met een oplossingsruimte van $\binom{N}{m}$.

Methodologie
De auteurs stellen MC+QUBO voor, een framework dat het proces van episode-selectie herformuleert als een Quadratic Unconstrained Binary Optimization (QUBO) probleem. In plaats van alle gesamplede episodes te gebruiken voor policy-updates, filtert de methode een batch trajecten om een subset te selecteren die de cumulatieve beloning maximaliseert terwijl de dekking van de toestandsruimte (diversiteit) wordt bevorderd.

• QUBO-formulering: Het selectieprobleem wordt gecodeerd als:
  $$\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)$$
  Waarbij:

  • $x_i = 1$ aangeeft dat episode $\tau_i$ wordt geselecteerd.
  • $R_i$ de cumulatieve beloning is van episode $i$.
  • $w_{ij}$ de paargewijze gelijkenis tussen episodes vertegenwoordigt (bijv. de Jaccard-gelijkenis van bezochte toestandssets).
  • $\alpha$ een belonings-schaleringsmultiplier is, en $\gamma$ de gelijkenis-straf weegt.
  • De lineaire term ($-\alpha R_i$) bevoordeelt episodes met hoge beloningen, terwijl de kwadratische term ($\gamma w_{ij}$) redundantie bestraft, wat de selectie van diverse trajecten aanmoedigt.

• Quantum-geïnspireerde Solvers: Het QUBO-probleem wordt opgelost met behulp van black-box quantum-geïnspireerde samplers, specifiek Simulated Quantum Annealing (SQA) en Simulated Bifurcation (SB).

  • SQA bootst quantum annealing na met klassieke stochastische updates en path-integral Monte Carlo om quantumtunneling tussen energiegeminima te simuleren.
  • SB maakt gebruik van een klassiek dynamisch systeem waarbij continue variabelen naar binaire toestanden evolueren via bifurcatie-fenomenen.
  • De auteurs behandelen deze solvers als orakels die hoogwaardige benaderende oplossingen leveren binnen praktische computationele budgetten.

• Integratie: De workflow omvat het genereren van een batch episodes, het berekenen van beloningen en gelijkenissen, het formuleren van de QUBO, het aanroepen van de solver, en het gebruiken van de best-geobserveerde oplossing (de binaire vector $x^*$) om te bepalen welke episodes worden gebruikt om de actie-waarde tabel $Q(s, a)$ bij te werken via first-visit MC.

Belangrijkste Bijdragen

1. Herformulering van Episode-selectie: Het artikel legt een formele link tussen MC episode-selectie en combinatorische optimalisatie, en toont aan dat het selectieprobleem kan worden gemapt naar een QUBO-formulering.
2. Algoritmische Integratie: Het introduceert een concreet pijplijn (Algoritme 2) die een QUBO-gebaseerde filteringstap tussen traject-sampling en policy-evaluatie in standaard MC-learning plaatst.
3. Empirische Validatie: De studie evalueert de methode op GridWorld-omgevingen met een eindig horizon van variërende grootte ($3\times3$ tot $20\times20$), waarbij MC+QUBO wordt vergeleken met een vanilla MC-baseline.

Resultaten
Experimenten uitgevoerd in GridWorld-omgevingen laten zien dat MC+QUBO consequent beter presteert dan vanilla MC wat betreft convergentiesnelheid en uiteindelijke policy-kwaliteit.

• Schaalbaarheid: Het prestatieverschil wordt groter in grotere omgevingen ($\ge 10\times10$), waar ijle beloningen en exponentiële toestandsruimte-groei typisch de standaard MC-evaluatie hinderen.
• Convergentie: MC+QUBO convergeert in minder batches door de focus van het leren te leggen op informatieve en diverse trajecten, waardoor redundante episodes effectief worden weggefilterd.
• Ontwerpinsicht: De auteurs merken op dat het prioriteren van de dekking van de toestandsruimte (het instellen van de invloed van de beloningsgewicht nabij nul) leidde tot meer gebalanceerd leren en betere generalisatie dan beloningsgestuurde selectie, die de neiging had tot snellere maar minder stabiele convergentie.
• Solver Prestaties: Quantum-geïnspireerde solvers (SQA en SB) presteerden beter dan klassieke heuristieken (zoals Tabu Search en Simulated Annealing) in deze context. De computationele latentie werd gedomineerd door cloud-communicatie in plaats van de solver-tijd zelf (die verwaarloosbaar was voor $n \le 200$).

Betekenis en Claims
Het artikel claimt dat het integreren van quantum-geïnspireerde optimalisatie als een besluitvormingssubroutine in reinforcement learning een praktische verbetering biedt voor MC-methoden, met name voor problemen met ijle beloningen en gecorreleerde trajecten. Door RL te verbinden met combinatorische optimalisatie, suggereert de studie een pad voor algoritmen waarbij quantum en quantum-geïnspireerde methoden het leerproces actief sturen om de inefficiëntie van steekproeven te overwinnen.

De auteurs blijven bescheiden over de reikwijdte en merken op dat, hoewel het framework veelbelovend is in GridWorld, verdere arbeid vereist is om extensies naar continue controle, hiërarchische RL en multi-agent systemen te verkennen, evenals de implementatie op echte quantumhardware. Het huidige werk dient als een proof-of-concept voor het gebruik van natuurkundig geïnspireerde solvers om de dataselectiefase van reinforcement learning te optimaliseren.