Technische Samenvatting: Pure Exploratie voor een Goede Policy in Versterkingsleren met Bandit-feedback

1. Probleemformulering

Dit artikel behandelt het probleem van Good Policy Identification (GPI) binnen het kader van Pure Exploratie in Versterkingsleren (RL). In tegenstelling tot het traditionele Best Policy Identification (BPI)-doel, dat streeft naar het identificeren van een (bijna-)optimale policy met hoge zekerheid, richt GPI zich op het vinden van een policy die voldoet aan een specifieke prestatiedrempel.

Formeel, gegeven een episodisch Markov Decision Process (MDP) met onbekende overgangsdynamica $P$ en initiële verdeling $p$, een eindige toestandsruimte $S$, actieruimte $A$ en horizon $H$, wordt de agent een beloningsdrempel $\mu_0$ verstrekt. Het doel is om een $\delta$-Probably Approximately Correct ($\delta$-PAC) algoritme te ontwerpen dat:

• Positief geval: Als er een policy $\pi$ bestaat zodanig dat zijn verwachte totale beloning $V^\pi_0(s_0) \ge \mu_0$, het algoritme zo'n policy moet uitvoeren met een waarschijnlijkheid van ten minste $1-\delta$.
• Negatief geval: Als de waarde van de optimale policy $V^*_0(s_0) < \mu_0$, moet het algoritme "Geen" uitvoeren met een waarschijnlijkheid van ten minste $1-\delta$.

De prestatiemetriek is de verwachte steekproefcomplexiteit (het verwachte aantal onderzochte episodes, aangeduid als $\tau$) die nodig is om tot een correcte beslissing te komen. Het artikel sluit expliciet het geval uit waar $V^*_0(s_0) = \mu_0$, omdat eerdere werken (Degenne en Koolen [2019]) hebben vastgesteld dat elk $\delta$-PAC algoritme in dit grensgeval oneindig veel steekproeven zou vereisen.

2. Methodologie: BEE-GPI

De auteurs stellen een nieuw algoritme voor genaamd BEE-GPI (Balanced Exploration-Exploitation for Good Policy Identification). Het algoritme werkt in fasen $k=1, 2, \dots$, waarbij elke fase bestaat uit een adaptief exploratiefase gevolgd door een beslissingsvertakkingsmechanisme.

Belangrijkste Componenten:

1. Exploratiefase (ES-BPI-UCRL):

   • Deze fase maakt gebruik van een Early-Stopping BPI-UCRL-orakel. Het hanteert een optimistische bemonsteringsstrategie (gelijkend op BPI-UCRL) om de overgangskernen en waardenfuncties te schatten.
   • Cruciaal introduceert het een nieuw early-stopping mechanisme. Het orakel controleert bij elke stap twee voorwaarden:
     • Voorwaarde (3): Een ondergrens voor de waarde van de huidige optimistische policy overschrijdt $\mu_0$ (gecorrigeerd met een factor $C$). Als dit wordt voldaan, wordt een kandidaat-policy geïdentificeerd.
     • Voorwaarde (4): Een bovengrens voor de optimale waardenfunctie ligt onder $\mu_0$. Als dit wordt voldaan, wordt het geval als negatief verklaard.
   • Als geen van beide voorwaarden wordt voldaan en het exploratiebudget $T^{ee}_k$ niet is overschreden, gaat het algoritme door met bemonsteren.

2. Beslissingsvertakking:

   • Als het orakel "Niet Voltooid" retourneert, gaat het algoritme door naar de volgende fase met een strakkere fouttolerantie $\delta_k$ en een verhoogd budget.
   • Als het orakel "Geen" retourneert maar de zekerheid onvoldoende is ($\delta_k \ge \delta/10$), gaat het algoritte door naar de volgende fase om de $\delta$-PAC-garantie te waarborgen.
   • Als het orakel een kandidaat-policy $\hat{\pi}_k$ retourneert, gaat het algoritme over naar de Exploitatiefase.

3. Exploitatie en Verificatie:

   • In deze fase wordt de kandidaat-policy $\hat{\pi}_k$ herhaaldelijk uitgevoerd om zijn ware waarde te schatten.
   • Het algoritme construeert een betrouwbaarheidsinterval voor de empirische gemiddelde beloning. Als de ondergrens van het betrouwbaarheidsinterval binnen een specifiek steekproefbudget $\mu_0$ overschrijdt, wordt de policy als oplossing uitgevoerd.
   • Als het budget wordt uitgeput zonder verificatie, keert het algoritme terug naar de exploratiefase van de volgende iteratie.

3. Belangrijkste Bijdragen

Het artikel levert drie primaire theoretische bijdragen:

1. Formalisatie van GPI: De auteurs definiëren het Good Policy Identification-probleem formeel in de setting met vaste zekerheid, en onderscheiden dit van $\epsilon$-BPI. Zij benadrukken dat standaard $\epsilon$-BPI-reducties suboptimaal zijn voor GPI, omdat de kloof $V^*_0(s_0) - \mu_0$ a priori onbekend is, wat de keuze van $\epsilon$ moeilijk maakt.
2. Algoritmeontwerp en Bovengrenzen: Zij stellen BEE-GPI voor en leiden theoretisch onderbouwde bovengrenzen af voor de steekproefcomplexiteit voor zowel positieve als negatieve gevallen.
   • Positieve gevallen: De steekproefcomplexiteit is begrensd door $O\left(\frac{H^2 \log(1/\delta)}{(V^*_0(s_0) - \mu_0)^2}\right) + O\left(\frac{\text{poly}(S, A, H)}{(V^*_0(s_0) - \mu_0)^2}\right)$.
   • Negatieve gevallen: De grens bevat termen die gekoppeld zijn aan de grootte van de toestands- en actieruimte, specifiek $O\left(\frac{(H+1)^4 SA \log(1/\delta)}{(V^*_0(s_0) - \mu_0)^2}\right)$.
3. Ondergrenzen en Bijna-Optimaliteit: De auteurs stellen ondergrenzen vast voor het GPI-probleem met behulp van geconstrueerde "Uniform Instances" (voor positieve gevallen) en "Tree Instances" (voor negatieve gevallen).
   • Zij bewijzen dat voor positieve gevallen elk $\delta$-PAC algoritme een steekproefcomplexiteit moet hebben van $\Omega\left(\frac{H \log(1/\delta)}{(V^*_0 - \mu_0)^2} + \frac{H^2 SA}{(V^*_0 - \mu_0)^2}\right)$.
   • Voor negatieve gevallen is de ondergrens $\Omega\left(\frac{HSA \log(1/\delta)}{(\mu_0 - V^*_0)^2}\right)$.
   • Deze resultaten tonen aan dat BEE-GPI bijna-optimaal is, waarbij de kloof tussen boven- en ondergrenzen beperkt is tot polynoomfactoren van $S, A, H$.

4. Resultaten en Analyse

Theoretische Inzichten

• Ontkoppeling van Logaritmische Termen: Een significante bevinding is dat voor positieve gevallen de coëfficiënt van de $\log(1/\delta)$-term in de steekproefcomplexiteit $O(H^2)$ is en onafhankelijk is van de grootte van de toestandsruimte $S$ en de actieruimte $A$. Dit staat in schril contrast met standaard BPI-reducties, waarbij de coëfficiënt typisch polynomiaal schaalt met $S$ en $A$.
• Asymmetrie: Er is een inherente asymmetrie tussen positieve en negatieve gevallen. Waar positieve gevallen efficiënte identificatie van een goede policy toestaan zonder de volledige toestands-actieruimte te verkennen, vereisen negatieve gevallen globale exploratie om te certificeren dat geen enkele policy de drempel haalt, vandaar de afhankelijkheid van $S$ en $A$ in de $\log(1/\delta)$-term.

Numerieke Experimenten

De auteurs valideren hun aanpak met twee klassieke omgevingen: Single Chain en Double Chain MDP's.

• Opzet: Zij vergelijken BEE-GPI met het state-of-the-art BPI-UCRL algoritme (Kaufmann et al. [2021]). Om een eerlijke vergelijking te waarborgen, wordt BPI-UCRL de orakelparameter $\epsilon = V^*_0 - \mu_0$ verstrekt, waardoor het aanzienlijke voorkennis heeft.
• Vondsten: Over diverse drempels $\mu_0$ heen vereist BEE-GPI consequent aanzienlijk minder episodes om een gekwalificeerde policy te identificeren in vergelijking met BPI-UCRL. De empirische resultaten bevestigen het theoretische voordeel van het ontkoppelen van de $\log(1/\delta)$-term van de grootte van de toestands- en actieruimte.

5. Betekenis en Claims

Het artikel stelt dat BEE-GPI een efficiëntere oplossing biedt voor praktische RL-scenario's waar het vinden van de absolute optimale policy onnodig of computationeel onhaalbaar is, maar het vinden van een "voldoende goede" policy (die een benchmark overschrijdt) cruciaal is.

• Praktische Relevantie: De auteurs citeren toepassingen in medische informatica (het identificeren van behandelingen die een standaard van zorg overschrijden), cloud computing (het voldoen aan Service Level Agreements) en financiën (het halen van ROI-benchmarks) waar het doel drempelbevrediging is in plaats van optimaliteit.
• Theoretische Vooruitgang: Door GPI te formaliseren en bijna-optimale grenzen te bieden, overbrugt dit werk de kloof tussen theoretische pure exploratie en praktische op drempels gebaseerde vereisten. Het toont aan dat de steekproefcomplexiteit aanzienlijk kan worden gereduceerd wanneer het doel wordt versoepeld van optimaliteit naar drempelbevrediging, met name in het geval van positieve gevallen.
• Toekomstige Richtingen: De auteurs suggereren bescheiden dat toekomstig werk zou kunnen bestaan uit het afleiden van strakkere, gevalafhankelijke grenzen en het uitbreiden van dit kader naar grootschalige MDP's met behulp van functiebenadering.

Kortom, het artikel stelt vast dat het identificeren van een policy die een beloningsdrempel haalt fundamenteel verschilt van het identificeren van de beste policy, en stelt een algoritme voor dat dit onderscheid benut om superieure steekproefefficiëntie te bereiken, met name wanneer de kloof tussen de optimale waarde en de drempel de primaire drijver van de moeilijkheid is.