Technische Samenvatting: Verbeterde Grenzen voor Reward-Agnostische en Reward-Free Exploratie

Probleemformulering

Dit artikel behandelt de uitdaging van exploratie in episodische, eindhorizontale, tabulaire Markov-beslissingsprocessen (MDP's), waarbij de agent opereert zonder externe beloningssignalen waar te nemen tijdens de dataverzamelfase. De auteurs bestuderen twee specifieke kaders:

1. Reward-Free Exploratie (RFE): De agent verkent een onbekende omgeving zonder enig beloningssignaal. Het doel is om een beleid te produceren dat $\epsilon$-optimaal is voor elke willekeurige beloningsfunctie die na de exploratiefase wordt onthuld.
2. Reward-Agnostische Exploratie (RAE): Vergelijkbaar met RFE, maar de beloningsfunctie wordt getrokken uit een kleine, vooraf gedefinieerde eindige klasse (grootte polynomiaal in $|S|, |A|, H$). Het doel is om een $\epsilon$-optimaal beleid te vinden voor de specifieke beloning die uit deze klasse is getrokken.

De kernmoeilijkheid ligt in het verzamelen van voldoende data om de overgangsdynamiek van staat-actie nauwkeurig te schatten zonder de begeleiding van een beloningssignaal, zodat het resulterende model de berekening van bijna-optimale beleidslijnen voor downstream-taken ondersteunt.

Methodologie

De voorgestelde aanpak vervangt de afhankelijkheid van meerdere onafhankelijke no-regret subroutines uit eerdere werken door een geünificeerde online leerprocedure. Het algoritme (Algoritme 1) werkt in drie fasen:

1. Creatie van Exploratiebeleid

In plaats van meerdere stochastische no-regret-algoritmen uit te voeren (zoals gedaan door Jin et al., 2020b; Li et al., 2024b), maken de auteurs gebruik van één enkele run van een Online Mirror Descent (OMD)-algoritme over een reeks zorgvuldig geconstrueerde hulpbeloningsfuncties.

• Mechanisme: Het algoritme genereert een reeks beloningen $\{\lambda_t\}$ die zijn ontworpen om de agent te sturen naar minder bezochte staat-actiesparen. De beloning op stap $t$ is omgekeerd evenredig met het bezoekaantal van het staat-actiespaar (plus een constante $c$ om bezoeken met lage waarschijnlijkheid te hanteren).
• Optimalisatieperspectief: Dit proces wordt geformuleerd als het ongeveer oplossen van een convex optimalisatieprobleem over de ruimte van geldige bezettingsmaten. Specifiek streeft het ernaar om de negatieve log-barrièredoelfunctie $f(\mu) = -\sum \log \mu_h(s,a)$ te minimaliseren.
• Betekenis: Door gebruik te maken van één online MDP-algoritme (aangepast van Rosenberg & Mansour, 2019) in plaats van Frank-Wolfe-stijl iteraties, reduceert de methode significant de termen van lage orde in de steekproefcomplexiteit. Het hergebruikt steekproeven gedurende het leerproces om een "beleidsdekking" te construeren die zorgt voor bijna-uniforme exploratie van significante staat-actie-triplets.

2. Schatting van Dynamiek

Met behulp van het in Stap 1 gegenereerde exploratiebeleid verzamelt de agent $N$ trajecten. Om de temporele correlaties inherent aan trajectdata te hanteren, maken de auteurs gebruik van een tweevoudig subsampling-kader (Li et al., 2024a). Deze techniek splitst de dataset in een hoofdset en een hulpset om statistische onafhankelijkheid te induceren, wat toelaat om een empirische overgangskernel $\hat{P}$ te construeren met strikte concentratiegaranties.

3. Schatting van Beleid

Zodra de ware beloningsfunctie wordt onthuld, berekent het algoritme een $\epsilon$-optimaal beleid met behulp van pessimisme in het gezicht van onzekerheid.

• Het algoritme construeert een empirische MDP met behulp van $\hat{P}$ en de onthulde beloning.
• Het past een strafterm $b_h(s,a)$ toe die is afgeleid van concentratieongelijkheden in de stijl van Bernstein op de Q-waarde-schattingen. Deze straf schaalt met de empirische variantie en bezoekaantallen, waardoor het beleid wordt ontmoedigd om slecht gedekte staat-actiesparen te bezoeken.
• Het uiteindelijke beleid $\hat{\pi}$ is het optimale beleid voor deze pessimistische empirische MDP.

Belangrijkste Bijdragen en Resultaten

1. Verbeterde Steekproefcomplexiteit voor Reward-Agnostische Exploratie (RAE)

Het artikel presenteert een nieuw algoritme dat de optimale hoge-orde steekproefcomplexiteit voor RAE bereikt, en overeenkomt met de ondergrens voor Best Policy Identification (BPI).

• Resultaat: De steekproefcomplexiteit is $O\left(\frac{|S||A|H^3 \ell_0^3}{\epsilon^2} + \frac{|S|^2|A|H^4 \ell_0^3}{\epsilon}\right)$.
• Verbetering: Hoewel eerdere werken (Li et al., 2024b) de optimale hoge-orde term $O(|S||A|H^3/\epsilon^2)$ bereikten, leden hun grenzen onder een term van hoge complexiteit met lage orde, waardoor de grens alleen optimaal was voor extreem kleine $\epsilon$. De voorgestelde methode reduceert deze term van lage orde significant, waardoor het algoritme toepasbaar wordt op een breder scala aan nauwkeurigheidsparameters.

2. Strakke Ondergrens voor Reward-Free Exploratie (RFE)

De auteurs bewijzen een strakke ondergrens voor de steekproefcomplexiteit van RFE in tijdsinhomogene MDP's.

• Resultaat: Elk RFE-algoritme vereist $\Omega\left(\frac{|S|^2|A|H^3}{\epsilon^2}\right)$ trajecten in verwachting.
• Betekenis: Dit lost een conjectuur van Li et al. (2024b) op dat de minimax-ondergrens voor tijdsinhomogene RFE een factor $H$ groter is dan het tijds-homogene geval. Dit stelt vast dat bestaande bovengrenzen (bijv. M´enard et al., 2021) optimaal zijn tot op logaritmische factoren.

3. Theoretisch Kader

Het artikel biedt een nieuw technisch perspectief door de creatie van exploratiebeleid te koppelen aan het minimaliseren van een log-barrièredoelfunctie over bezettingsmaten. Het toont aan dat een online mirror descent-benadering deze oplossing efficiënter kan benaderen dan eerdere op Frank-Wolfe gebaseerde methoden, waardoor de afhankelijkheid van probleemdimensies in de termen van lage orde wordt verminderd.

Betekenis en Claims

Het artikel beweert de theoretische understanding van exploratie zonder beloningen te bevorderen door:

1. Exploratie en Exploitatie te Ontwarren: Het verduidelijkt de intrinsieke steekproefcomplexiteit van exploratie in eindhorizontale MDP's.
2. Praktijktoepasbaarheid van RAE: Door de restrictieve eisen aan de nauwkeurigheidsparameter $\epsilon$ uit eerdere optimale grenzen te versoepelen, maakt de voorgestelde methode reward-agnostische exploratie praktisch, zelfs in regimes met gemiddelde nauwkeurigheid.
3. Volledigheid van Karakterisering: De combinatie van de nieuwe bovengrens voor RAE en de strakke ondergrens voor RFE biedt een complete minimax-karakterisering van de steekproefcomplexiteit voor deze problemen (tot op logaritmische factoren).

De auteurs stellen expliciet dat hun focus ligt op de theoretische analyse van eindhorizontale, tabulaire MDP's, en laten niet-tabulaire MDP's en empirische resultaten over als avenues voor toekomstig werk. Zij claimen geen onmiddellijke toepassing op specifieke real-world domeinen zoals robotica of geneeskunde, maar benadrukken eerder de fundamentele theoretische verbeteringen die dergelijke toepassingen mogelijk maken.