Sharp analysis of linear ensemble sampling

Technische Samenvatting: Scherpe Analyse van Ensemble Sampling

Probleemstelling
Dit artikel onderzoekt Ensemble Sampling (ES) binnen het kader van stochastische lineaire bandits. In deze setting interageert een leerling gedurende $n$ ronden met een omgeving, waarbij acties $X_t$ worden gekozen uit een gesloten verzameling $\mathcal{X} \subset \mathbb{R}^d$ (doorgaans de eenheidshulsel) om de cumulatieve beloning te maximaliseren. De beloning volgt een lineair model $Y_t = \langle X_t, \theta^* \rangle + \eta_t$, waarbij $\theta^*$ een onbekende parameter is en $\eta_t$ subgaussische ruis. Het doel is om de $n$-staps pseudo-regret te minimaliseren, gedefinieerd als het verschil tussen de cumulatieve beloning van een optimaal beleid en het beleid van de leerling.

Hoewel Thompson Sampling (TS) de gouden standaard is voor exploratie in deze setting, met een hoge-waarschijnlijkheid regret van $\tilde{O}(d^{3/2}\sqrt{n})$, is ES historisch gezien achtergebleven. Eerdere analyses van ES in lineaire bandits vereisten ofwel ensemble-groottes die schalen met het aantal acties (wat hen ongeschikt maakt voor oneindige actiesets) of bereikten suboptimale regret-bounds van $\tilde{O}(d^{5/2}\sqrt{n})$, zelfs met ensemble-groottes die schalen als $O(d \log n)$.

Methodologie
De auteurs analyseren ES met standaard Gaussische perturbaties. Het algoritme onderhoudt een ensemble van $m$ ridge regressie-modellen. Elk model $j$ wordt getraind op de geschiedenis van acties en beloningen, maar met twee cruciale modificaties:

1. Geperturbeerde Prior: Het regularisatietarget is een willekeurige vector $\zeta^j$ getrokken uit een priorverdeling in plaats van nul.
2. Geperturbeerde Data: De geobserveerde beloningen worden opgeblazen met onafhankelijke Gaussische ruis $\xi^j_t$.

De leerling selecteert elke ronde willekeurig één model uit het ensemble en kiest de actie die de voorspelde beloning onder dat model maximaliseert.

De kern van de technische uitdaging is de door adaptatie geïnduceerde afhankelijkheid: hoewel de in de modellen geïnjecteerde ruis onafhankelijk is, zijn de modellen aan elkaar gekoppeld omdat ze worden getraind op data die is verzameld door de actieselecties van het ensemble zelf.

Om dit te overwinnen, gebruiken de auteurs een continu-tijd embedding benadering:

1. Martingaal Representatie: Ze identificeren de ruisprocessen die de modelparameters aansturen als voorspelbare diagonale martingaal-transformaties van de vorm $S_t = \sum D_s \xi_s$, waarbij $D_s$ voorspelbare diagonale matrices zijn.
2. Brownse Embedding: Door gebruik te maken van de Gaussische aard van de perturbaties, bewijzen ze een representatie-lemma (Theorem 5.3) dat aantoont dat deze discrete-tijd martingaal-transformaties exact gerepresenteerd kunnen worden als onafhankelijke standaard Brownse bewegingen geëvalueerd op willekeurige tijdstippen die bepaald worden door de voorspelbare kwadratische variatie van de transformatie.
3. Tijd-Uniforme Exceedance: Deze embedding reduceert het probleem van het controleren van de regret tot het analyseren van de tijd-uniforme exceedance frequenties van $m$ onafhankelijke Brownse bewegingen. Specifiek stellen ze vast dat een voldoende groot deel van deze Brownse bewegingen uniform over de tijd boven een gebogen grens $c\sqrt{t}$ moet blijven. Dit wordt bereikt met behulp van instrumenten uit de stochastische analyse, waaronder de Dambis–Dubins–Schwarz tijd-verandering, Ornstein–Uhlenbeck-processen en boundary-crossing schattingen.

Belangrijkste Bijdragen

1. Scherpe Regret Bound: Het artikel stelt vast dat met een ensemble-grootte van $m = \Theta(d \log n)$, ES een hoge-waarschijnlijkheid regret-bound bereikt van $\tilde{O}(d^{3/2}\sqrt{n})$. Dit komt overeen met de canonieke regret-snelheid van Thompson Sampling.
2. Computationele Efficiëntie: In tegenstelling tot eerdere resultaten die ensemble-groottes vereisten die schalen met het aantal acties (bijv. $m = \Omega(k \log n)$), behoudt dit resultaat een ensemble-grootte die slechts lineair schaalt met de dimensie $d$, wat het geschikt maakt voor oneindige actiesets (zoals de eenheidshulsel) zonder exponentiële discretisatiekosten.
3. Theoretische Ondergrens: De auteurs bewijzen dat als de ensemble-grootte $m \le d/2$ is, er lineaire bandit-instanties bestaan waarin ES een lineaire regret veroorzaakt, wat aantoont dat de $O(d)$ schaling noodzakelijk is.
4. Nieuw Analytisch Perspectief: Het werk introduceert een "continu-tijd lens" voor het analyseren van discrete-tijd adaptieve algoritmen. Door discrete martingalen in onafhankelijke Brownse bewegingen te embedden, isoleren de auteurs de adaptiviteit in de "klokken" (tijd-veranderingen), waardoor een tractabele analyse van het zelf-genormaliseerde exceedance-probleem mogelijk wordt dat met louter discrete methoden onhandelbaar was.

Resultaten

• Theorem 4.1: Voor $m \ge 2000 d \log(n/\delta)$ en specifieke afstemmingsparameters, wordt de $n$-staps regret $R_n$ begrensd door $\tilde{O}(d^{3/2}\sqrt{n})$ met een waarschijnlijkheid van ten minste $1 - 4\delta$.
• Theorem 4.2: Als $m \le d/2$, faalt ES om sublineaire regret te bereiken voor bepaalde probleeminstanties, wat de striktheid van de vereiste voor de ensemble-grootte bevestigt.
• Vergelijking: De resultaten sluiten het gat tussen ES en TS in termen van de schaling van de regret, terwijl de computationele overhead (per ronde kosten) vergelijkbaar blijft met andere methoden, mits $m = \tilde{O}(d)$.

Betekenis en Claims
Het artikel claimt dat de primaire bijdrage het dichten van de kloof is tussen de prestaties van Ensemble Sampling en Thompson Sampling in de stochastische lineaire bandit-setting. De auteurs benadrukken dat hun bewijstechniek een nieuw perspectief op gerandomiseerde exploratie biedt, door een complex adaptief discreet-tijd probleem te reduceren tot een tijd-uniform exceedance probleem voor onafhankelijke Brownse bewegingen.

Ze stellen expliciet dat ze geen andere route kennen naar een scherpe ES-bound, wat de nieuwheid van het gebruik van continu-tijd instrumenten (specifiek de exacte Brownse embedding) om een puur discreet-tijd probleem op te lossen, onderstreept. De auteurs zijn bescheiden over de reikwijdte van hun instrumenten en merken op dat hoewel ze vermoeden dat vergelijkbare resultaten kunnen gelden voor andere perturbatieverdelingen (bijv. Rademacher), het bewijzen hiervan andere instrumenten (zoals Skorokhod embeddings) zou vereisen en een openstaande richting blijft. Ze merken ook op dat hun benadering momenteel steunt op de diagonale structuur van de ruis-transformaties (scalaire veelvouden van de identiteitsmatrix), wat de analyse vereenvoudigt vergeleken met algemene diagonale gevallen.