Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability

Probleemstelling

Het paper behandelt de statistische efficiëntie van offline learning in Contextual Bandits (CB's) wanneer het leerdoel Forward-Kullback-Leibler (Forward-KL) regularisatie omvat. De doelfunctie wordt gedefinieerd als:
$$J_{FKL}(\pi) := \mathbb{E}[r] - \eta^{-1} \text{KL}(\pi_{\text{ref}} \| \pi)$$
waarbij $r$ de beloning is, $\eta$ de inverse regularisatiesterkte is, en $\pi_{\text{ref}}$ een referentie (gedrags)beleid is.

Hoewel reverse-KL regularisatie ($\text{KL}(\pi \| \pi_{\text{ref}})$) uitgebreid is bestudeerd en is aangetoond dat het $\tilde{O}(\epsilon^{-1})$ steekproefcomplexiteit (snelle snelheden) toestaat onder single-policy concentrability (waarbij het gedragsbeleid alleen het optimale beleid dekt), blijft het Forward-KL geval een open probleem. Bestaande analyses voor Forward-KL zijn ofwel niet toepasbaar of resulteren in trage $\tilde{O}(\epsilon^{-2})$ snelheden. Bovendien is het onduidelijk of single-policy concentrability voldoende is voor Forward-KL, gezien het feit dat Forward-KL "mass-covering" is (het bestraft $\pi \to 0$ waar $\pi_{\text{ref}} > 0$) in plaats van "mode-seeking", wat mogelijk sterkere dekkingaannames vereist.

Het paper streeft ernaar twee kernvragen te beantwoorden:

1. Wat is de statistische snelheid van besluitvorming voor Forward-KL geregulariseerde doelen?
2. Is single-policy concentrability voldoende voor rate-optimaal offline learning in deze setting?

Methodologie

De auteurs stellen een gestroomlijnde analyse voor voor Forward-KL-Regularized Pessimistic Contextual Bandits (FKL-PCB). De methodologie wijkt aanzienlijk af van eerdere werken die vertrouwen op Taylor-ontwikkelingen en de Gemiddelde Waarde Stelling (MVT).

1. Afwijzing van traditionele MVT-gebaseerde analyse:
Eerdere werken die geregulariseerde doelen analyseren, gebruiken vaak een Taylor-ontwikkeling rond een tussenliggend punt $\bar{u}$ (via de Gemiddelde Waarde Stelling) om de suboptimaliteitskloof te ontleden. Voor reverse-KL vertonen de resulterende termen een monotonie-eigenschap onder pessimisme die het mogelijk maakt om de fout te begrenzen met single-policy concentrability.
Echter, de auteurs demonstreren (via Lemma 5.3) dat voor Forward-KL de afgeleide van de term voor suboptimaliteitsontleding een "tilted skewness" van een gecentreerde willekeurige variabele omvat. Het teken van deze afgeleide is onbepaald, wat betekent dat het monotonie-argument faalt. Bijgevolg kunnen standaard MVT-gebaseerde routines geen snelle snelheden bereiken zonder terug te grijpen naar sterkere (all-policy) concentrability-aannames.

2. Convex-analytische pijplijn:
Om de beperkingen van MVT te omzeilen, introduceren de auteurs een nieuwe bewijstechniek gebaseerd op convex geconjugeerden en Bregman-divergenties:

• Dual perspectief: Ze karakteriseren de geregulariseerde doelfunctie via zijn convex geconjugeerde over het waarschijnlijkheidssimplex.
• Self-bounding argument: Ze leiden een identiteit af voor de suboptimaliteitskloof (Lemma 5.5) die de fout direct uitdrukt in termen van het kwadraat van het verschil tussen de ware beloning en de pessimistische schatting, gewogen door de verhouding van het optimale beleid tot het referentiebeleid.
• Kernidentiteit: De centrale technische bijdrage is de ongelijkheid:
  $$\text{SubOpt}_{FKL}(\hat{\pi}) \leq 2\eta \sum_{a} \frac{(\pi^*_{FKL}(a))^2}{\pi_{\text{ref}}(a)} (r(a) - \hat{r}(a))^2$$
  Deze grens hangt alleen af van de single-policy concentrability-coëfficiënt $C_{\pi^*} = \sup \frac{\pi^*}{\pi_{\text{ref}}}$, waardoor er geen behoefte is aan all-policy concentrability.

3. Algoritmeontwerp:
Het paper presenteert FKL-PCB, een pessimistisch algoritme voor zowel tabulaire als functbenaderingssettings:

• Schatting: Gebruikt least-squares om de beloningsfunctie te schatten.
• Pessimisme: Trekt een strafterm (vertrouwensgrens) af om ervoor te zorgen dat de geschatte beloning $\hat{r}$ met hoge waarschijnlijkheid een ondergrens heeft die gelijk is aan de ware beloning $r$.
• Optimalisatie: Geeft het beleid uit dat het pessimistische geregulariseerde doel maximaliseert.

Belangrijkste bijdragen en resultaten

1. Snelle bovengrenzen voor steekproefcomplexiteit:
Het paper stelt de eerste $\tilde{O}(\epsilon^{-1})$ bovengrenzen voor steekproefcomplexiteit vast voor Forward-KL geregulariseerde offline CB's onder single-policy concentrability:

• Tabulaire setting: $\tilde{O}\left( \eta (C_{\pi^*})^2 |S||A| \epsilon^{-1} \right)$.
• Functiebenadering: $\tilde{O}\left( \eta C_{\pi^*} D^2_{\pi^*} \log N_G \epsilon^{-1} \right)$, waarbij $D^2_{\pi^*}$ een $D^2$-type concentrability-coëfficiënt is en $N_G$ het overkappingsgetal van de functieklassen is.
• Deze resultaten verbeteren de vorige state-of-the-art $\tilde{O}(\epsilon^{-2})$ grens van Aminian et al. (2025) en verlichten de eis van all-policy concentrability naar single-policy concentrability.

2. Minimax-ondergrenzen:
De auteurs leveren passende ondergrenzen om de nauwkeurigheid van hun bovengrenzen aan te tonen:

• Tabulaire ondergrens: $\Omega(\eta |S||A| \epsilon^{-1})$ in het regime van hoge regularisatie. Dit bevestigt dat de lineaire afhankelijkheid van $\eta$ en de $1/\epsilon$-snelheid optimaal zijn.
• Faseovergang: De ondergrenzen onthullen een "faseovergang" vergelijkbaar met reverse-KL. In het regime van lage regularisatie (groot $\eta$) keert de steekproefcomplexiteit terug naar de trage $\tilde{O}(\epsilon^{-2})$ snelheid, wat aangeeft dat regularisatie noodzakelijk is om snelle snelheden te bereiken.

3. Technische nieuwheid:
Het paper stelt dat de "convex-analytische pijplijn" tabulaire en functiebenaderingssettings verenigt en de bewijsroutines op basis van de Gemiddelde Waarde Stelling volledig omzeilt. Deze aanpak wordt gepresenteerd als van onafhankelijk belang voor het analyseren van andere divergentie-geregulariseerde besluitvormingsproblemen.

Betekenis en claims

Het paper positioneert zichzelf als het eerste werk dat de statistische snelheden voor Forward-KL regularisatie in offline learning exact karakteriseert. De primaire betekenis ligt in:

• Oplossen van een open probleem: Het beslecht de vraag of single-policy concentrability voldoende is voor Forward-KL, met een bevestigend antwoord en snelle snelheden.
• Verenigende theorie: Het toont aan dat de "mass-covering" aard van Forward-KL niet inherent sterkere dekkingaannames vereist dan de "mode-seeking" reverse-KL, mits een nieuwe analytische aanpak wordt gebruikt.
• Algoritmische eenvoud: Het laat zien dat een minimalistisch op pessimisme gebaseerd algoritme (FKL-PCB) voldoende is om deze optimale snelheden te bereiken, zonder complexe algoritmische aanpassingen.

De auteurs blijven bescheiden wat toekomstige richtingen betreft, en merken op dat hoewel ze de sufficientie vaststellen, de necessiteit van single-policy concentrability voor Forward-KL (zelfs in multi-armed bandits) een open vraag blijft. Bovendien wordt het afleiden van een ondergrens die specifiek voor de $D^2$-type concentrability in functiebenadering overeenkomt met de bovengrens, overgelaten aan toekomstig werk.