Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation

1. Probleemstelling

Versterkend leren (RL) in grootschalige of continue omgevingen staat voor ernstige computatierisico's. Traditionele model-gebaseerde algoritmen voor regret-minimalisatie vereisen frequente oproepen aan twee soorten "orakels":

1. Statistisch Schattingsorakel: Wordt gebruikt om het omgevingsmodel (overgangsdynamica en beloningen) te schatten op basis van data.
2. Beleidsoptimalisatie (Plannings)orakel: Wordt gebruikt om het optimale beleid te berekenen op basis van het geschatte model.

Bestaande benaderingen lijden onder twee hoofdbeperkingen:

• Hoge Frequentie van Orakeloproepen: De meeste algoritmen vereisen $O(T)$ oproepen aan deze orakels, waarbij $T$ de tijds horizon is, wat ze computatierisico's maakt voor grote $T$.
• Afhankelijkheid van de Grootte van de Toestand/Actie-ruimte: De complexiteit van plannen schaalt vaak met de kardinaliteit van de toestandruimte ($S$) en de actieruimte ($A$). Dit maakt bestaande methoden onhandelbaar voor omgevingen met grote, oneindige of continue toestand/actie-ruimtes (bijvoorbeeld lineaire MDP's met oneindige toestanden).

Hoewel recent werk (bijvoorbeeld Qian et al., 2024) "offline orakel-efficiëntie" (weinig oproepen aan het schattingsorakel) heeft bereikt voor tabulaire MDP's, schaalt de complexiteit van hun planningsorakel nog steeds met $S$ en $A$ (specifiek $O(HSA \log \log T)$). Het paper adresseert de open vraag: Kunnen we een algoritme ontwerpen dat efficiënt is in zowel schattings- als planningsorakels, met complexiteit die onafhankelijk is van $S$ en $A$, en toepasbaar is op oneindige toestand/actie-ruimtes?

2. Methodologie

De auteurs stellen DOERL (Doubly Oracle-Efficient Reinforcement Learning) voor, een nieuw algoritmisch raamwerk gebaseerd op log-barrière en log-determinant regularisatie. De kerninnovatie ligt in hoe het algoritme de afweging tussen exploratie en exploitatie beheert terwijl het aantal orakeloproepen wordt geminimaliseerd.

Belangrijke Technische Componenten:

1. Epoch-gebaseerd Leren met Getruncateerde Updates:

   • Het interactieproces wordt verdeeld in $N$ epochen. Binnen elke epoch voert het agent een vast beleid uit voor een tijdssegment.
   • Cruciaal is dat het offline schattingsorakel alleen aan het einde van elke epoch (of segment) wordt aangeroepen, waarbij data wordt geaggregeerd om het model te updaten. Dit reduceert het aantal schattingsoproepen tot $O(N)$.
   • Het planningsorakel wordt ook alleen aan het begin van segmenten aangeroepen, wat de planningsfrequentie aanzienlijk reduceert.

2. Vertrouwde Bezettingsmaten:

   • Om het verkennen van zeldzame of onbetrouwbare toestand-actie-overgangen te vermijden, definieert het algoritme een "vertrouwde overgangsset" $\mathcal{T}_m^h$.
   • Overgangen worden alleen als "vertrouwd" beschouwd als de geschatte bezettingsmaat vermenigvuldigd met de overgangskans een drempelwaarde ($1/\zeta_m$) overschrijdt.
   • Dit concept, overgenomen van Qian et al. (2024), is zodanig aangepast dat het berekenbaar is zonder door de volledige beleidsruimte te itereren, wat cruciaal is voor efficiëntie.

3. Regularisatie voor Exploratie:

   • Voor Tabulaire MDP's: Het algoritme gebruikt Log-barrière Regularisatie. De doelstelling voor beleidsoptimalisatie bevat een term $\sum \log(\text{vertrouwde bezettingsmaat} + \beta)$. Dit moedigt de agent aan om toestand-acteparen te bezoeken die "vertrouwd" zijn maar een lage kans hebben, waardoor voldoende exploratie wordt gegarandeerd zonder alle toestanden te hoeven enumereren.
   • Voor Lineaire MDP's (Oneindige Ruimtes): Het algoritme introduceert Log-determinant Regularisatie. In plaats van te sommeren over discrete toestanden, maximaliseert het de log-determinant van de feature-covariantiematrix, gewogen door de vertrouwde bezettingsmaat: $\log \det(\mathbf{K} + \beta \mathbf{I})$. Dit bevordert exploratie van de feature-ruimte, waardoor de agent diverse data verzamelt om de lineaire coëfficiënten nauwkeurig te schatten.

4. Aggregatiestrategie:

   • Het algoritme aggregeert laag-voor-laag schattingen (overgangskernen en beloningen) van het offline orakel tot één globaal model voor de volgende epoch, in plaats van het model bij elke enkele stap bij te werken.

3. Belangrijkste Bijdragen

1. Dubbele Orakel-efficiëntie:

   • Het paper presenteert het eerste algoritme dat zowel statistische schattingsorakel-efficiëntie als beleidsoptimalisatie-orakel-efficiëntie bereikt.
   • Complexiteit van Orakeloproepen: Het algoritme vereist slechts $O(H \log \log T)$ oproepen aan beide orakels wanneer $T$ bekend is (en $O(H \log T)$ wanneer onbekend).
   • Onafhankelijkheid van Dimensies: Cruciaal is dat deze complexiteit strikt onafhankelijk is van de grootte van de toestandruimte ($S$) en de actieruimte ($A$).

2. Extensie naar Oneindige Ruimtes:

   • Het raamwerk wordt gegeneraliseerd naar Lineaire MDP's met oneindige toestandruimtes en willekeurige actieruimtes.
   • Het is het eerste offline orakel-efficiënte algoritme dat sub-lineaire regret bereikt in deze setting, waarmee de "vloek van de dimensionaliteit" die tabulaire methoden teistert, wordt overwonnen.

3. Optimale Regret-grenzen:

   • Tabulaire MDP's: Bereikt de optimale $O(\sqrt{T})$ regret-grens.
   • Lineaire MDP's: Bereikt een sub-lineaire regret-grens van $O(T^{4/5})$ (met logaritmische factoren), wat betekenisvol is voor oneindig-dimensionale settings onder de gegeven orakelbeperkingen.

4. Resultaten

Theoretische garanties zijn vastgesteld voor zowel eindige (tabulaire) als oneindige (lineaire) settings:

• Tabulaire MDP's:

  • Regret: $O(\sqrt{T})$ (optimaal).
  • Orakeloproepen: $O(H \log \log T)$ voor zowel schatting als planning.
  • Vergelijking: Een aanzienlijke verbetering ten opzichte van Qian et al. (2024), die $O(HSA \log \log T)$ planningsoproepen vereiste.

• Lineaire MDP's (Oneindige Toestand/Actie):

  • Regret: $O(T^{4/5} \cdot \text{polylog}(T))$.
  • Orakeloproepen: $O(H \log \log T)$ voor beide orakels.
  • Betekenis: Voorafgaand aan dit werk bestond er geen algoritme dat oneindige-toestand MDP's kon oplossen met dergelijke lage frequentie van orakeloproepen terwijl het sub-lineaire regret behield.

5. Betekenis en Impact

• Brug tussen Theorie en Praktijk: Door de computatierisico's te ontkoppelen van de grootte van de toestand/actie-ruimtes, maakt dit werk model-gebaseerd RL theoretisch haalbaar voor complexe, real-world toepassingen zoals robotica en autonome systemen, waar $S$ en $A$ effectief oneindig zijn.
• Efficiëntie in Grootschalige Systemen: De reductie van orakeloproepen van $O(T)$ of $O(SA)$ naar $O(\log \log T)$ vertegenwoordigt een enorme vermindering van de computatierisico's, waardoor het gebruik van dure offline schatters (zoals diepe neurale netwerken) in RL-lussen mogelijk wordt waar ze eerder te kostbaar waren.
• Nieuw Paradigma voor Exploratie: De integratie van log-barrière en log-determinant regularisatie met "vertrouwde" maten biedt een robuust theoretisch mechanisme voor exploratie dat elegant schaalt met de dimensionaliteit, en fungeert als blauwdruk voor toekomstige algoritmen in hoog-dimensionale besturing.

Samenvattend, dit paper verbetert fundamenteel de state-of-the-art in Versterkend Leren door aan te tonen dat optimale regret kan worden bereikt met minimale computatierisico's (onafhankelijk van de omgevingsgrootte) door een nieuwe combinatie van epoch-gebaseerd leren, vertrouwde maten en determinant-gebaseerde regularisatie.