Technische Samenvatting: Een beetje vrijheid doet een groot verschil: Klassieke en Kwantumalgoritmen voor Reinforcement Learning onder een Generatief Model

Probleemstelling

Het artikel behandelt het probleem van het leren van Markov-beslissingsprocessen (MDP's) in een online setting, met een specifieke focus op het minimaliseren van regret (het verschil tussen de geaccumuleerde beloning van de agent en die van een optimale policy). De auteurs beschouwen drie verschillende MDP-instellingen:

1. Eindige-horizon MDP's: Interacties vinden plaats over een vast aantal stappen $H$.
2. Oneindige-horizon gedisconteerde MDP's: Interacties gaan oneindig door met beloningen die worden gedisconteerd door een factor $\gamma \in [0, 1)$.
3. Oneindige-horizon ongedisconteerde MDP's: Interacties gaan oneindig door met een gemiddelde beloningscriteria, specifiek gericht op zwak communicerende MDP's.

Een centrale uitdaging in Reinforcement Learning (RL) is de exploratie-exploitatie-trade-off. In de klassieke setting moeten agenten transitiekansen $p(\cdot|s, a)$ leren terwijl ze interageren met de omgeving. In de kwantumsetting ontstaat een fundamenteel probleem: standaard kwantumorakels staan superpositie en inverse operaties toe, wat kan leiden tot ongedefinieerde regret-maten als de agent gedurende het leerproces op een kwantumachtige wijze met de omgeving interacteert. Bov�endien vertrouwden eerdere kwantum RL-werken die streefden naar polylogarithmische regret in tijd $T$ op gebrekkige aannames met betrekking tot de coherente toepassing van kwantum-amplitude-estimatie.

Methodologie

Het Hybride Online-Offline RL-model

Om de definitiesproblemen van regret in kwantum RL op te lossen en om kwantumversnellingen te benutten, stellen de auteurs een hybride online-offline RL-model voor. Dit model scheidt het leerproces in twee afzonderlijke fasen:

1. Online Fase (Exploratie): De agent interageert klassiek met de omgeving. De agent kiest acties, ontvangt beloningen en observeert toestandoversgangen. Cruciaal is dat regret accumuleert tijdens deze fase. De agent heeft hier geen toegang tot kwantumorakels.
2. Offline Fase (Generatief Leren): De agent krijgt "vrijheid" om met de omgeving te interageren via een generatief model.
   • In de klassieke offline fase heeft de agent toegang tot een sampling-orakel $C_p$ dat volgende toestanden $s'$ teruggeeft gegeven $(s, a)$.
   • In de kwantum offline fase heeft de agent toegang tot een kwantumorakel $Q_p$ (en zijn inverse) dat superposities van volgende toestanden voorbereidt.
   • Restrictie: Het aantal orakeloproepen in de offline fase wordt begrensd door een functie van de lengte van de voorgaande online fase $\tau$, specifiek $O(\tau^\beta)$, waarbij $\beta \in [0, \infty)$ een "budget"-parameter is. Dit voorkomt dat de agent een bijna optimale policy met nul regret verkrijgt door simpelweg het orakel excessief te bevragen.

Algoritmische Aanpak

De voorgestelde algoritmen (Algoritme 1) vorderen in epochen. In elke epoche $\ell$:

1. Offline Computatie: Gebruikmakend van de gegevens verzameld in de vorige online fase (lengte $\tau_{\ell-1}$), berekent de agent een $\epsilon_\ell$-optimale policy.
   • Klassiek: Gebruikt bekende sample-optimale algoritmen (bijv. Sidford et al.) om policies te berekenen.
   • Kwantum: De auteurs introduceren nieuwe kwantumalgoritmen voor het berekenen van optimale policies onder een generatief model. Deze algoritmen maken gebruik van kwantum gemiddelde schatting (Kothari en O'Donnell) en kwantum minimum/maximum zoeken (Dürr en Høyer) om value iteration te versnellen.
2. Online Executie: De berekende policy $\pi^{(\ell)}$ wordt uitgevoerd in de omgeving voor een duur die wordt bepaald door een doubling trick (het vergroten van de horizon met een factor 2 of $2H$).
3. Regret Analyse: De totale regret wordt begrensd door de sub-optimaliteit van de gebruikte policies in elke online fase op te tellen.

Belangrijke Technische Bijdragen

1. Nieuwe Kwantumalgoritmen voor Generatieve Modellen:

   • Eindige-horizon: De auteurs ontwerpen kwantumalgoritmen die de klassieke query-complexiteit verbeteren. Ze combineren gekwantiseerde value iteration met variantiereductie-technieken. De query-complexiteit is $\tilde{O}(\min\{H^{2.5}SA/\epsilon, H^3S\sqrt{A}/\epsilon\})$, wat de afhankelijkheid van $H$ en $A$ verbetert ten opzichte van klassieke bounds.
   • Oneindige-horizon gedisconteerd: Vergelijkbare verbeteringen worden bereikt, met een query-complexiteit van $\tilde{O}(\min\{\Gamma^{1.5}SA/\epsilon, \Gamma^3S\sqrt{A}/\epsilon\})$.
   • Oneindige-horizon ongedisconteerd: Dit is een nieuwe bijdrage. De auteurs stellen een kwantumalgoritme voor voor zwak communicerende MDP's onder de aanname dat de optimale Bellman-operator een $J$-staps $\nu$-span contractie is. De complexiteit is $\tilde{O}(\Lambda S \sqrt{A} / \epsilon)$.

2. Correctie van Voorgaande Kwantum RL-werken:
   Het artikel bekritiseert eerdere werken (bijv. Ganguly et al., Zhong et al.) die beweerden polylogarithmische regret te bereiken. De auteurs stellen dat deze werken onjuist aannamen dat kwantum amplitude-estimatie kon worden uitgevoerd op een collectie van opgeslagen toestanden, in plaats van het vereisen van sequentiële, coherente toepassingen van het orakel en zijn inverse. Het voorgestelde hybride model corrigeert dit door een duidelijke offline fase af te dwingen waar dergelijke coherente operaties kunnen worden uitgevoerd zonder regret op te lopen.

3. Regret Bounds onder het Hybride Model:
   De auteurs leiden regret-bounds af voor zowel klassieke als kwantumsettings als functie van de budget-parameter $\beta$:

   • Eindige-horizon:
     • Klassiek: $\tilde{O}(\sqrt{HSAT})$ (komt overeen met state-of-the-art) wanneer $\beta \ge 2$.
     • Kwantum: $\tilde{O}(\min\{H^{1.5}SA, H^2S\sqrt{A}\} T^{1-\beta})$ voor $\beta < 1$, en polylogarithmisch in $T$ voor $\beta \ge 1$.
   • Oneindige-horizon gedisconteerd:
     • Kwantum: Bereikt $\tilde{O}(\text{polylog}(T))$ regret wanneer $\beta \ge 1$, waarmee de klassieke $\Omega(\sqrt{T})$ barrière wordt doorbroken.
   • Oneindige-horizon ongedisconteerd:
     • Kwantum: Bereikt $\tilde{O}(\Lambda S \sqrt{A} \cdot \text{polylog}(T))$ regret voor $\beta \ge 1$, wat een significante verbetering is ten opzichte van de $\tilde{O}(\Lambda S^5 A^4)$ bound van eerdere kwantumwerken.

Resultaten en Betekenis

Het artikel claimt dat de "beetje vrijheid" geboden door de offline generatieve fase een substantiële verbetering in leer-efficiëntie mogelijk maakt.

• Kwantumvoordeel: Het meest significante resultaat is de demonstratie dat kwantumcomputers polylogarithmische regret kunnen bereiken in de tijdshorizon $T$ (specifiek wanneer $\beta \in [1, 2)$), terwijl klassieke algoritmen in deze settings fundamenteel beperkt zijn tot $\Omega(\sqrt{T})$ regret. Dit vertegenwoordigt een exponentiële verbetering in de afhankelijkheid van $T$.
• Parameterafhankelijkheid: De kwantumalgoritmen verbeteren de afhankelijkheid van de grootte van de toestandsruimte $S$, de actieruimte $A$ en de horizon $H$ (of effectieve horizon $\Gamma$) vergeleken met zowel klassieke algoritmen als eerdere kwantumpogingen.
• Model Validiteit: Het artikel vestigt het hybride online-offline model als een noodzakelijk en betekenisvol kader voor kwantum RL. Het lost de ambiguïteit op bij het definiëren van regret in kwantuminteracties en corrigeert de theoretische gebreken in eerdere literatuur die aannam dat er regret-vrije kwantum-exploratie mogelijk was zonder dergelijke scheiding.

De auteurs concluderen dat hoewel het exponentiële kwantumvoordeel in $T$ verdwijnt wanneer het budget $\beta$ zeer groot is ($\beta \ge 2$, waar klassieke algoritmen ook polylogarithmische regret bereiken), er een kritieke range bestaat ($\beta \in [1, 2)$) waarin kwantumcomputers een substantieel voordeel bieden. Het artikel identificeert deze range als het primaire gebied waar kwantumversnellingen in RL het meest impactvol zijn onder het voorgestelde model.