Technische Samenvatting: Online KL-geregulariseerd Reinforcement Learning met Functiebenadering onder Mis-specificatie

1. Probleemformulering

Dit werk behandelt het probleem van KL-geregulariseerde contextuele bandits en episodisch reinforcement learning (RL) onder algemene functiebenadering wanneer de gekozen modelklasse mis-gespecificeerd is.

In standaardinstellingen rusten theoretische garanties vaak op de realiseerbaarheidsveronderstelling, die stelt dat de werkelijke belonings- of waardefuncties exact binnen de geleerde functieklasse liggen. Echter, in praktische toepassingen zoals Reinforcement Learning from Human Feedback (RLHF) en Large Language Model (LLM) post-training, gebruiken leerders frequent beperkte functieklassen (bijv. lineaire of low-rank modellen) die complexe, niet-lineaire beloningsstructuren niet perfect kunnen vatten. Dit leidt tot model-mis-specificatie, waarbij zelfs met oneindige data de beste voorspeller in de gekozen klasse een niet-nul benaderingsbias behoudt.

De specifieke doelstellingen zijn:

• Contextuele Bandits: Het minimaliseren van de cumulatieve KL-regret tegen een KL-optimale Gibbs-policy, gedefinieerd door een referentiepolicy $\pi_{\text{ref}}$ en een regularisatieparameter $\eta$.
• Episodische RL: Het minimaliseren van de cumulatieve KL-regret in een episodische MDP-setting, waarbij policy-updates worden geregulariseerd door een KL-straf ten opzichte van stage-wise referentiepolicies.

De kernuitdaging is dat bestaande mis-specificatieanalyses voor standaard belonings-regret formuleringen niet direct overdraagbaar zijn naar KL-geregulariseerde settings vanwege structurele verschillen in de optimalisatiegeometrie en Bellman-targets.

2. Methodologie

2.1 Mis-specificatie Formuleringen

De auteurs introduceren specifieke mis-specificatievoorwaarden afgestemd op de KL-geregulariseerde doelstelling:

• Contextuele Bandits: Een puntgewijze mis-specificatie formulering waarbij de kwadratische fout tussen de ware beloning $R^\star$ en de beste benaderaar in de klasse $\mathcal{R}$ wordt begrensd door $\zeta_{\text{Bandit}}^2$.
• Episodische RL: Een stage-wise mis-specificatie voorwaarde uitgelijnd met KL-geregulariseerde Bellman-targets. Deze begrenst de fout tussen de ware Bellman-backup (inclusief de log-partition operator) en de beste benaderaar in de stage-wise functieklasse $\mathcal{R}_h$, begrensd door $\zeta_{\text{RL}}$.

2.2 Algoritmen

Het artikel stelt twee regressie-gebaseerde algoritmen voor die optimisme incorporeren om onzekerheid en mis-specificatie te hanteren:

1. MR-KL-UCB (Contextuele Bandits):

   • Past een Empirical Risk Minimizer (ERM) toe op geobserveerde data.
   • Berekent een onzekerheidsbonus gebaseerd op de eluder-dimensie van de functieklasse.
   • Voegt het bekende mis-specificatieniveau $\zeta_{\text{Bandit}}$ toe aan de bonus.
   • Update de policy met behulp van een Gibbs-distributie afgeleid van de optimistische beloningsschatting: $\pi_t(a|x) \propto \pi_{\text{ref}}(a|x) \exp(\eta \hat{R}_t(x,a))$.

2. MR-KL-LSVI (Episodische RL):

   • Een uitbreiding van Least-Squares Value Iteration (LSVI) naar de KL-geregulariseerde setting.
   • Voert backward planning uit: in elke stage $h$ worden de regressie-labels opnieuw berekend met de continuatie-waarde van de volgende stage.
   • Past een stage-wise ERM toe, berekent een onzekerheidsbonus en voegt het mis-specificatieniveau $\zeta_{\text{RL}}$ toe.
   • Update de policy via Gibbs policy improvement ten opzichte van de stage-wise referentiepolicy.
   • Gebruikt een soft-value update (log-partition operator) om de KL-regularisatie te hanteren.

2.3 Theoretische Analyse Technieken

De analyse combineert verschillende geavanceerde technieken:

• Gibbs Variational Identity: Maakt gebruik van de exacte relatie tussen de KL-gap en het verschil in scores om de regret te begrenzen.
• Quadratic Self-Bounding: Stelt vast dat de KL-gap tussen de geleerde policy en de optimale policy wordt begrensd door het kwadraat van het verschil in hun scorefuncties (optimisme-gap).
• Reductie naar Bellman-residuals: Converteert gekwadrateerde on-policy Q-gaps naar gekwadrateerde Bellman-residual termen, waardoor KL-specifieke bijdragen worden geïsoleerd.
• Freedman's Inequality: Wordt gebruikt om voorspelbare sommen van gekwadrateerde bonuses uit te lijnen met gerealiseerde sommen, wat zorgt voor garanties met een hoge waarschijnlijkheid.

3. Belangrijkste Bijdragen

1. Nieuwe Mis-specificatie Formuleringen: Het artikel definieert de eerste KL-uitgelijnde mis-specificatievoorwaarden voor zowel contextuele bandits (puntgewijs) als episodische RL (stage-wise langs Bellman-paden).
2. Algoritmisch Ontwerp: Het introduceert MR-KL-UCB en MR-KL-LSVI, die optimisme-bonussen expliciet kalibreren aan bekende mis-specificatieniveaus ($\zeta$) terwijl ze de Gibbs-policy structuur behouden die vereist is voor KL-geregulariseerde doelstellingen.
3. Regret Garanties met Hoge Waarschijnlijkheid: De auteurs stellen high-probability KL-regret bounds vast die de statistische complexiteit (via de eluder-dimensie) expliciet scheiden van de benaderingsfout door mis-specificatie.
   • Voor bandits: $O(\eta \sqrt{\log(N_R T/\delta) \cdot d(\mathcal{R}, \lambda, T)} + T\zeta_{\text{Bandit}}^2)$.
   • Voor RL: $\tilde{O}(\eta H^2 \sqrt{d_{\text{RL}}(\lambda, T)} + \eta H^3 T \zeta_{\text{RL}}^2)$.
4. Herstel van Realiseerbare Casussen: De analyse toont aan dat wanneer het mis-specificatieniveau nul is ($\zeta = 0$), de bounds de state-of-the-art garanties voor realiseerbare KL-geregulariseerde settings herstellen.

4. Resultaten

De belangrijkste theoretische resultaten (Theorem 5.1 en Corollary 5.4) bieden de volgende garanties:

• Contextuele Bandits: Onder het puntgewijze mis-specificatiemodel schaalt de cumulatieve KL-regret met de vierkantswortel van de eluder-dimensie van de functieklasse en lineair met de totale tijdshorizon $T$ vermenigvuldigd met de gekwadrateerde mis-specificatiefout $\zeta_{\text{Bandit}}^2$.
• Episodische RL: Onder de stage-wise mis-specificatievoorwaarde schaalt de regret met de horizon $H$, de regularisatieparameter $\eta$, de geaggregeerde eluder-dimensie en de gekwadrateerde mis-specificatiefout $\zeta_{\text{RL}}^2$. De bound bevat een expliciete term voor de som van gekwadrateerde bonuses, die wordt gecontroleerd door het mis-specificatieniveau.

Deze resultaten gelden met een hoge waarschijnlijkheid ($1-\delta$) en nemen conditieel sub-Gaussische ruis aan.

5. Betekenis en Claims

Het artikel claimt een kritieke kloof te vullen in het theoretische begrip van RLHF en preference-based learning, waar model-mis-specificatie gebruikelijk is maar vaak genegeerd wordt in theoretische analyses.

• Brug tussen Theorie en Praktijk: Door verder te gaan dan de realiseerbaarheidsveronderstelling, biedt dit werk een realistischer theoretisch kader voor moderne RL-toepassingen waarbij eenvoudige functieklassen (zoals lineaire modellen) worden gebruikt om complexe beloningslandschappen te benaderen.
• Structureel Inzicht: De analyse benadrukt dat KL-geregulariseerde doelstellingen specifieke geometrische uitdagingen introduceren (bijv. log-partition operators en Gibbs-policies) die afwijkende mis-specificatievoorwaarden vereisen vergeleken met standaard belonings-regret formuleringen.
• Robuustheid: De voorgestelde algoritmen blijken robuust tegen benaderingsfouten; ze verslechteren geleidelijk naarmate het mis-specificatieniveau toeneemt, in plaats van volledig te falen zoals sommige realiseerbaarheids-afhankelijke bounds zouden suggereren.

De auteurs merken op dat hun model puntgewijze mis-specificatie en light-tailed ruis veronderstelt. Zij erkennen dat het uitbreiden van deze garanties naar on-policy mis-specificatie maten, heavy-tailed settings, en bredere feedbackmodellen (zoals preference-based formuleringen buiten de huidige scope) een belangrijke richting is voor toekomstig werk.