Technische Samenvatting: On-Policy en Off-Policy Leren voor Grote Actieruimtes

Probleemstelling

De thesis behandelt de fundamentele uitdaging van leren in interactieve systemen, specifiek contextuele bandits, waarbij de actieruimte $K$ extreem groot is (variërend van duizenden tot miljoenen). In dergelijke settings kampen standaardalgoritmen voor zowel on-policy (online) als off-policy (offline) leren met ernstige schaalbaarheidsbelemmeringen:

• On-Policy: Standaard exploratiestrategieën zoals Thompson Sampling (TS) of Upper Confidence Bound (UCB) vertrouwen doorgaans op disjuncte modellen waarbij elke actie een onafhankelijke parameter heeft. In grote actieruimtes is het onafhankelijk leren van elke parameter statistisch inefficiënt, wat leidt tot een hoge cumulatieve regret. Daartegenover staan gezamenlijke modellen die parameters over alle acties delen, die vaak computationeel onhandelbaar zijn vanwege de $O(K^2)$ of $O(K^3)$ complexiteit van het onderhouden en bijwerken van een volledige covariantie-matrix.
• Off-Policy: Leren van statische gelogde data verzameld door een loggingsbeleid $\pi_0$ staat voor drie hoofdproblemen:
  1. Statistische Inefficiëntie: Directe methoden (DM) lijden onder hoge bias wanneer acties zelden worden waargenomen.
  2. Variantie: Inverse Propensity Scoring (IPS) estimators vertonen een exploderende variantie wanneer de loggingskans $\pi_0(a|x)$ klein is.
  3. Optimalisatie-onhandelbaarheid: De thesis betoogt dat in grote actieruimtes het optimalisatielandschap van standaard IPS-gebaseerde doelstellingen zeer niet-concaaf wordt met vlakke plateaus en exponentieel veel lokale maxima, waardoor gradiëntgebaseerde optimizers falen, ongeacht de statistische kwaliteit van de estimator.

Methodologie en Bijdragen

De thesis is verdeeld in twee delen en stelt nieuwe methoden voor voor elk leerparadigma.

Deel I: On-Policy Leren (Het schalen van Thompson Sampling)

De kerninzicht is het behouden van de flexibiliteit van disjuncte beloningsmodellen door de introductie van gestructureerde Bayesiaanse priors die informatie delen over acties heen.

1. Mixed-Effect Thompson Sampling (meTS) - Hoofdstuk 3

• Methodologie: De auteurs introduceren een hiërarchisch Bayesiaans model waarbij actieparameters $\theta_a$ gekoppeld zijn via $L$ gedeelde latente effectparameters $\Psi = (\psi_\ell)_{\ell \in [L]}$. Het generatieve proces gaat uit van $\theta_a | \Psi \sim p_0(\cdot|\Psi)$.
• Algoritme: meTS voert hiërarchische sampling uit: eerst het samplen van de globale effecten $\Psi_t$ uit hun posterior, en vervolgens het samplen van individuele actieparameters $\theta_{t,a}$ geconditioneerd op $\Psi_t$.
• Theoretische Resultaten: Voor lineair-Gaussische modellen leiden de auteurs exacte gesloten vorm posterior-updates af. Ze bewijzen een Bayesiaanse regret bound van $\tilde{O}(\sqrt{Td K_{eff}})$, waarbij $K_{eff}$ het effectieve aantal acties is. Wanneer het aantal effecten $L \ll K$, is $K_{eff} \ll K$, wat een multiplicatieve verbetering oplevert ten opzichte van standaard TS.
• Complexiteit: De methode reduceert de geheugencomplexiteit van $O(K^2d^2)$ naar $O((L^2 + K)d^2)$ en de runtime van $O(K^3d^3)$ naar $O((L^3 + K)d^3)$.
• Extensies: Het framework wordt uitgebreid naar Generalized Linear Models (GLMs) met behulp van behapbare Laplace-approximaties.

2. Diffusion Thompson Sampling (dTS) - Hoofdstuk 4

• Methodologie: Om complexere, niet-lineaire afhankelijkheden tussen acties te vangen, vervangen de auteurs de enkelvoudige latente structuur door een diepe hiërarchie van latente variabelen die worden beheerd door vooraf getrainde diffusiemodellen. De prior wordt gedefinieerd als een Markovketen van latente variabelen $\psi_L \to \dots \to \psi_1 \to \theta_a$ verbonden door niet-lineaire linkfuncties $f_\ell$.
• Algoritme: dTS maakt gebruik van een recursief inferentieproces. Het benadert de onhandelbare posterior door een "posterior diffusiemodel" te onderhouden waarbij de linkfuncties en covarianten worden bijgewerkt via Gaussian-achtige updates (combinatie van prior precisie en data precisie) zonder terug te propageren door het neurale netwerk.
• Theoretische Resultaten: In een lineair-Gaussische setting schaalt de regret bound met het effectieve aantal acties en de som van de varianties over de $L$ lagen. De complexiteit schaalt lineair met $L$, oftewel $O((L+K)d^2)$, wat een verbetering is ten opzichte van meTS.
• Significantie: Dit demonstreert dat diepe generatieve modellen niet alleen gebruikt kunnen worden voor representatie, maar ook om de onzekerheid te structureren die nodig is voor efficiënte exploratie.

Deel II: Off-Policy Leren (Adresseren van Estimatie en Optimalisatie)

De thesis daagt het heersende "estimatie-gecentreerde" paradigma uit en stelt drie complementaire benaderingen voor.

1. Structured Direct Method (sDM) - Hoofdstuk 6

• Methodologie: Analoog aan meTS introduceert sDM een gedeelde latente vector $\psi$ om actieparameters in de offline setting te koppelen. Het berekent de posterior over latente effecten en de conditionele posteriors voor actieparameters.
• Resultaten: De auteurs bewijzen dat sDM een convergentie van $O(1/\sqrt{n})$ bereikt in Bayesiaanse suboptimaliteit zonder de restrictieve "full logging support" assumptie te vereisen. De bound hangt af van de uitlijning tussen het loggingsbeleid en het optimale beleid.
• Inzicht: Onder het overwogen Bayesiaanse suboptimaliteitscriterium wordt aangetoond dat greedische beleid optimaal zijn en beter kunnen presteren dan pessimistische beleid, wat contrasteert met frequentistische settings waar pessimisme vaak noodzakelijk is.

2. Optimalisatie is belangrijker dan Estimatie - Hoofdstuk 7

• Methodologie: De auteurs demonstreren dat in grote actieruimtes de optimalisatiefout de estimatiefout domineert. Standaard IPS-gebaseerde doelstellingen induceren niet-concaaf landschappen die optimizers vangen.
• Voorstel: In plaats van de waarde te schatten en vervolgens te optimaliseren, pleit de thesis voor Policy-Weighted Log-Likelihood (PWLL) doelstellingen:
  $$\hat{U}_g(\pi) = \frac{1}{n} \sum_{i=1}^n g(R_i, \pi_0(A_i|X_i)) \log \pi(A_i|X_i)$$
• Resultaten: Voor lineaire softmax-beleid zijn PWLL-doelstellingen concaaf (en sterk concaaf met $\ell_2$-regularisatie), wat een unieke globale maximum garandeert. Experimenten op datasets met tot wel één miljoen acties tonen aan dat deze eenvoudige, stabiele doelstellingen consistent beter presteren dan geavanceerde waarde-estimator-gebaseerde methoden.

3. Geprincipeerde Pessimisme voor Exponential Smoothing - Hoofdstuk 8

• Methodologie: Om de variantie van IPS aan te pakken, introduceren de auteurs differentieerbare Exponential Smoothing (ES) estimators die interpoleren tussen geen regularisatie en sterke variantiereductie.
• Theorie: Een tweezijdige PAC-Bayesiaanse generalisatiebound wordt afgeleid voor deze geregulariseerde estimators. Deze bound ontleedt de fout in divergentie, regularisatiebias en resterende variantie.
• Toepassing: De bound levert een volledig differentieerbare, pessimistische leerdoelstelling die geoptimaliseerd kan worden via stochastic gradient ascent. Het framework is verenigd om andere regularisaties zoals clipping en impliciete exploratie te dekken.
• Extensie: De auteurs introduceren ook Logarithmic Smoothing (LS), een zachte, differentieerbare alternatief voor clipping dat nauwere concentratiebounds bereikt.

Experimentele Resultaten

De voorgestelde methoden worden gevalideerd op zowel synthetische als real-world datasets:

• On-Policy: In synthetische lineaire en logistische bandits presteren meTS en dTS significant beter dan baselines (LinTS, GLM-TS, HierTS), waarbij het prestatieverschil groter wordt naarmate de actieruimte $K$ toeneemt. In MovieLens experimenten (recommender systemen) bereikt meTS de laagste regret, zelfs wanneer het ware beloningsmodel misspecified is, wat robuustheid aantoont.
• Off-Policy:
  • sDM presteert beter dan standaard Direct Methods, met winsten die toenemen naarmate $K$ groeit.
  • PWLL doelstellingen (Hoofdstuk 7) presteren consistent beter dan state-of-the-art IPS-gebaseerde methoden op datasets met tot wel één miljoen acties, en tonen superieure robuustheid aan tegen hyperparameter tuning.
  • De PAC-Bayesiaanse pessimistische doelstellingen (Hoofdstuk 8) behalen betere beloningen dan baselines (inclusief London et al. en Sakhi et al.) over diverse kwaliteiten van het loggingsbeleid, vooral wanneer het loggingsbeleid niet uniform is.

Significantie en Claims

De thesis claimt de kloof te overbruggen tussen theoretische bandit-algoritmen en de beperkingen van moderne industriële systemen (bijv. recommender systemen met miljoenen items). Het centrale argument is dat schalen naar grote actieruimtes het volgende vereist:

1. Het Structureren van Onzekerheid: Het gebruik van hiërarchische en diffusie-gebaseerde priors om statistische kracht te delen over acties heen (On-Policy).
2. Herwaardering van Doelstellingen: Erkenning dat in grote ruimtes de hanteerbaarheid van het optimalisatielandschap even cruciaal is als de statistische nauwkeurigheid van de estimator (Off-Policy).
3. Differentiabel Pessimisme: Het ontwikkelen van theoretisch gefundeerde, doch computationeel haalbare, pessimistische doelstellingen die variantie en bias controleren zonder te vertrouwen op onhandelbare constanten.

Het werk stelt dat door af te stappen van onafhankelijke actiemodellering en standaard waarde-estimatie, contextuele bandits effectief ingezet kunnen worden in omgevingen waar de actieruimtes routinematig duizenden of miljoenen overstijgen.