Learning Upper Lower Value Envelopes to Shape Online RL: A Principled Approach

Technische Samenvatting: Het leren van bovenste-onderste waarde-enveloppen om Online RL te vormen

Probleemstelling
Het artikel behandelt de fundamentele uitdaging om offline data te benutten om online Reinforcement Learning (RL) te versnellen. Bestaande theoretische garanties voor RL-algoritmen worden vaak geformuleerd in termen van worst-case scenario's, maar neigen te pessimistisch te zijn omdat ze taakspecifieke kenmerken die het leren kunnen faciliteren, negeren. Een veelbelovende richting is het gebruik van voorkennis, zoals vormfunctie-approximaties (shaping functions) van optimale waarde- of Q-functies, om suboptimale regio's te snoeien en de regret-bounds te verkleinen. Eerder werk (bijv. Gupta et al., 2022) gaat er echter van uit dat deze vormfuncties a priori met voldoende nauwkeurigheid worden geleverd. De centrale vraag die dit artikel onderzoekt, is of dergelijke vormfuncties op een principiële manier geleerd kunnen worden uit een batch offline data en vervolgens gebruikt kunnen worden om online exploratie te sturen zonder de theoretische garanties te schenden.

Methodologie
De auteurs stellen een principieel tweefasen-framework voor dat offline leren ontkoppelt van online interactie:

1. Offline Fase (Enveloppe-constructie):

   • Het algoritme verwerkt een batch dataset van $K$ trajecten met behulp van een model-gebaseerde offline RL-aanpak.
   • In tegenstelling tot standaard offline RL, dat vertrouwt op pessimisme om ondergrenzen af te leiden, construeert deze fase waarde-enveloppen: afzonderlijke bovenste ($U_h$) en onderste ($W_h$) grenzen op de optimale waarde-functie $V^\star_h$ en actiewaarde-functie $Q^\star_h$.
   • Deze grenzen worden afgeleid met behulp van optimistische en pessimistische Value Iteration met Bernstein-gebaseerde bonussen.
   • Cruciaal is dat de ruwe offline data na deze fase wordt weggegooid; alleen de geleerde enveloppen worden doorgegeven aan de online fase. Deze scheiding zorgt voor statistische onafhankelijkheid tussen de offline schattingen en de online omgevingsovergangen, wat voldoet aan privacybeperkingen en rigoureuze concentratie-argumenten mogelijk maakt.

2. Online Fase (Envelope-gestuurde Exploratie):

   • Het online algoritme is een variant van UCBVI (Azar et al., 2017), aangepast om de geleerde enveloppen te gebruiken.
   • Waarde-clipping (Value Clipping): Waarde-schattingen worden afgeknipt (clipped) met behulp van de geleerde bovenste en onderste grenzen ($W_h$ en $U_h$).
   • Bonus-schaling (Bonus Scaling): De exploratiebonus wordt aangepast zodat deze afhankelijk is van de breedte van de enveloppe ($D_h = U_h - W_h$) en het bereik van de enveloppe ($R_h$). Specifiek wordt de variantie-term in de Bernstein-bonus geschat met behulp van de geleerde enveloppen in plaats van de onbekende optimale waarde-functie.
   • De methode ondersteunt zowel Q-shaping (het afknippen van Q-waarden) als V-shaping (het afknippen van V-waarden).

Belangrijkste Bijdragen

1. Ontkoppelde Enveloppen: De auteurs introduceren een framework dat gebruikmaakt van afzonderlijke bovenste en onderste grenzen in plaats van een enkele $\beta$-sandwich formulering. Dit staat flexibelere, nauwkeurigere en potentieel asymmetrische benaderingen van de optimale waarde-functie toe.
2. Random Shaping Functies: Het artikel behandelt de vormfuncties als willekeurige variabelen (meetbaar ten opzichte van de offline sigma-algebra) in plaats van als vaste functies. Dit is een significante afwijking van eerder werk waar vormfuncties werden aangenomen als deterministisch of vooraf beschikbaar.
3. Theoretische Garanties met Random Bounds: De auteurs leiden high-probability regret-bounds af die de offline datasetgrootte expliciet verbinden met de online steekproefcomplexiteit. Ze introduceren een aangepaste conditionele empirische Bernstein-ongelijkheid die geldig blijft, zelfs wanneer de grenzen die in het concentratie-argument worden gebruikt, random variabelen zijn die offline zijn geleerd.
4. Privacy Compatibiliteit: Door de ruwe offline data weg te gooien en alleen de waarde-enveloppen te verzenden, zorgt de methode ervoor dat gevoelige state-transition data niet wordt hergebruikt in de online fase, wat privacyzorgen aanpakt.

Resultaten

• Regret Bounds: Theoretische analyse stelt vast dat de regret afhangt van twee interpreteerbare grootheden: $D_{max}$ (de maximale breedte van de geleerde enveloppe) en $R_{max}$ (het maximale bereik van de enveloppe). Naarmate de offline datasetgrootte $K$ toeneemt, convergeert $D_{max}$ naar nul, waardoor onzekerheid-afhankelijke termen in de regret-bound verdwijnen.
• Empirische Prestaties: Experimenten op geparametriseerde gelaagde tabular MDP's laten zien:
  • Reductie van Regret: De voorgestelde methode bereikt substantiële reducties in regret vergeleken met standaard Bernstein UCBVI en Hoeffding UCBVI.
  • Schaalbaarheid: Cumulatieve regret neemt significant af naarmate de offline datasetgrootte $K$ toeneemt.
  • Vergelijking met eerdere methoden: De methode presteert beter dan een versie van UCBVI die simpelweg initiële counts aanvult met offline data (Count-Initialized UCBVI) wat betreft het behoud van privacy, terwijl het competitief blijft. Bovendien presteert het beter dan "Upper-Bonus Shaping" (een variant die Gupta et al., 2022 nabootst met enkel bovenste grenzen), met name wanneer de onderste grens significante informatie biedt (bijv. wanneer het bereik van de optimale waarde ver van nul ligt).

Betekenis en Claims
Het artikel claimt een formele brug te slaan tussen offline pre-training en online fine-tuning. De primaire betekenis ligt in het bewijs dat offline data kan worden ingezet om online exploratie te versnellen zonder dat de online agent toegang nodig heeft tot de ruwe offline dataset of de beschikbaarheid van perfecte vormfuncties vereist. Door de statistische afhankelijkheid tussen offline leren en online interactie rigoureus te behandelen via een filtratie-argument, stellen de auteurs vast dat "het leren van een vormfunctie" theoretisch solide is. Het werk suggereert dat zelfs met beperkte offline data, de resulterende enveloppen effectief de state-action ruimte kunnen snoeien, wat leidt tot bewezen verbeteringen in de steekproefcomplexiteit. De auteurs merken op dat hoewel zij zich richten op tabular MDP's, het framework ontworpen is om uitbreidbaar te zijn naar transfer learning-regimes met gerelateerde maar verschillende MDP's.