🤖 machine learning

A Broader View of Thompson Sampling

Dit artikel verduidelijkt het mechanisme achter het succes van Thompson Sampling door dit te herformuleren als een online optimalisatiealgoritme dat een stationair Bellman-optimale beleid nabootst, waarbij hebzucht wordt geregulariseerd door resterende onzekerheid, en biedt aldus een nieuw kader voor het begrijpen van zijn dynamiek en het verbeteren van beleidsplannen.

Oorspronkelijke auteurs: Yanlin Qu, Hongseok Namkoong, Assaf Zeevi

Gepubliceerd 2026-05-28

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yanlin Qu, Hongseok Namkoong, Assaf Zeevi

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Plaatje: De "Mysterie" van een Bekend Algoritme Oplossen

Stel je voor dat je een chef-kok bent die probeert het beste recept voor een nieuw gerecht te vinden. Je hebt twee ingrediënten (laten we ze Arm 1 en Arm 2 noemen), maar je weet niet welke er beter smaakt. Je moet blijven koken om te leren, maar je wilt ook nu al het beste gerecht aan je klanten serveren. Dit is het klassieke "Multi-Armed Bandit" probleem: het vinden van een balans tussen exploratie (nieuwe dingen proberen om te leren) en exploitatie (gebruik maken van wat je weet dat het beste werkt).

Decennia lang was één specifieke methode, Thompson Sampling, de gouden standaard. Het is beroemd omdat het in de praktijk ongelooflijk goed werkt. In tegenstelling tot andere methoden waarbij de regels duidelijk zijn (zoals "kies altijd de optie met de hoogste zekerheidsscore"), voelde Thompson Sampling een beetje als magie. Het werkt, maar niemand kon precies uitleggen waarom het leren en verdienen zo perfect in evenwicht brengt.

Dit paper trekt de gordijnen open. De auteurs tonen aan dat Thompson Sampling niet zomaar een gelukkig giswerk is; het is eigenlijk een geavanceerd online optimalisatie-algoritme. Ze ontdekten dat het werkt door een specifiek type "regret" (het verschil tussen wat je kreeg en wat je had kunnen krijgen) te minimaliseren, terwijl het "geregulariseerd" (geleid) wordt door een maatstaf voor onzekerheid.

Het Kernidee: Een Nieuwe Manier om "Regret" te Meten

Om het paper te begrijpen, moeten we kijken naar hoe ze succes meten.

De Oude Manier (Gediscounterde Beloningen):
Stel je voor dat je een videospelletje speelt waarbij punten die je nu krijgt 100% waard zijn, maar punten die je later krijgt slechts 90%, dan 81%, en zo verder. Dit heet "diskouteren". Het beroemde Gittins Index beleid maakt gebruik hiervan. Het is geweldig voor het spel, maar het heeft een gebrek: het kan stoppen met het verkennen van een potentieel betere optie te vroeg, omdat de toekomstige punten niet de moeite lijken waard. In de echte wereld, waar we over een lange periode alles mogelijk willen leren, kan dit een vergissing zijn.

De Nieuwe Manier van het Paper (Kwadratische Regret):
De auteurs stellen een nieuwe manier voor om naar het probleem te kijken. In plaats van de toekomst te diskouteren, kijken ze naar het kwadraat van de regret.

Analogie: Stel je voor dat je een auto bestuurt.
- Lineaire Regret: Als je 1 mijl van koers wijkt, ben je 1 mijl verkeerd. Als je 10 mijl van koers wijkt, ben je 10 mijl verkeerd.
- Kwadratische Regret: Als je 1 mijl van koers wijkt, ben je 1 mijl verkeerd. Maar als je 10 mijl van koers wijkt, ben je nu 100 "eenheden" slecht rijden.
- Waarom dit belangrijk is: Door de fout te kwadrateren, wordt het algoritme zeer gevoelig voor grote fouten. Het dwingt het systeem om enorme fouten te vermijden, wat van nature leidt tot een strategie die genoeg exploreert om niet vast te komen zitten op een slecht pad, maar niet zo veel dat het tijd verspilt.

De auteurs noemen dit "Faithful Stationarization". Het is een ingewikkelde manier van zeggen: "We hebben een wiskundige regel gevonden die in de tijd hetzelfde blijft (stationair), maar toch perfect het doel vastlegt om langetermijnfouten te minimaliseren (faithful)."

De "Geheime Ingrediënten": Onzekerheid versus Spanning

Het paper onthult dat Thompson Sampling werkt door een wiskundig probleem op te lossen dat er zo uitziet:

Minimaliseer (Fout) + (Onzekerheidsstraf)

De auteurs breken dit op in twee concurrerende krachten:

Gierigheid (Exploitatie): Je wilt de arm kiezen die op dit moment het beste lijkt om de meeste beloning te krijgen.
Regularisatie (Exploratie): Je hebt een "straf" nodig om te voorkomen dat je te gierig bent. Deze straf is gebaseerd op hoeveel je niet weet.

De Ontdekking:
De auteurs vonden dat Thompson Sampling een specifiek type straf gebruikt genaamd Biserial Covariance.

De Metafoor: Stel je voor dat je wedt op een paardenren.
- Logica van Thompson Sampling: "Ik weet niet zeker welk paard zal winnen. Hoe onzekerder ik ben (hoe meer de paarden op elkaar lijken), hoe meer ik moet wedden op de outsider om te zien of ze kunnen winnen." Het meet Onzekerheid.
- De "Bellman-Optimale" Logica (Het Ideaal): De auteurs berekenden wat het perfecte algoritme zou doen. Ze ontdekten dat het perfecte algoritme niet alleen kijkt naar onzekerheid; het kijkt naar Spanning.
- De Metafoor: "Ik ben onzeker, maar is het het risico waard om over te stappen? Als het leidende paard eigenlijk heel sterk is en de outsider zwak, dan moet ik niet overstappen, zelfs niet als ik een beetje onzeker ben. Maar als het leidende paard wankel is en de outsider sterk, dan is de spanning hoog, en moet ik overstappen."

Het Probleem:
Thompson Sampling wordt soms "te nieuwsgierig". Het blijft een slecht presterende optie verkennen alleen maar omdat er een beetje onzekerheid is, zelfs wanneer de "spanning" (het voordeel van overstappen) eigenlijk laag is. Het is alsof je elke 30 seconden de oven controleert omdat je nerveus bent, terwijl het recept zegt dat de taart prima is.

De Oplossing: Een "Eén-Staps" Fix

Het paper bekritiseert Thompson Sampling niet alleen; het biedt een manier om het op te lossen met dezelfde logica die het "perfecte" algoritme aandrijft.

Ze stellen een Policy Improvement-stap voor.

Analogie: Stel je voor dat je een student bent die een toets maakt.
- Thompson Sampling: Je beantwoordt de vragen op basis van je huidige ingeving.
- De Verbetering: Voordat je het papier inlevert, neem je even de tijd om je antwoorden te bekijken en te vragen: "Als ik had geweten wat ik weet na het beantwoorden van deze vraag, zou ik mijn antwoord dan hebben veranderd?"
- Het Resultaat: De auteurs tonen aan dat het doen van deze één enkele stap van "vooruitkijken" bijna alle gebreken van Thompson Sampling oplost. Het transformeert het algoritme van iets dat puur wordt gedreven door "onzekerheid" naar iets dat wordt gedreven door "spanning".

In hun experimenten sloot deze ene tweak 90% van het prestatieverschil tussen het beroemde Thompson Sampling en hun theoretische "perfecte" algoritme.

Samenvatting van Belangrijkste Leerpunten

Thompson Sampling is een Optimalisator: Het is niet zomaar een heuristiek; het is een algoritme dat een specifiek type kwadratische fout minimaliseert.
Het Gebrek: Het vertrouwt op "Onzekerheid" (hoe verward ik ben) in plaats van "Spanning" (is het de moeite waard om over te stappen?). Dit maakt dat het soms te veel exploreert.
De Fix: Door een standaard "policy improvement"-stap toe te passen (één stap vooruit kijken), kunnen we het algoritme veranderen zodat het zich richt op "Spanning".
Het Resultaat: Deze simpele aanpassing maakt het algoritme bijna perfect, presteert het bijna even goed als de theoretisch beste mogelijke strategie, zonder dat er complexe nieuwe wiskunde nodig is.

Het paper zegt in wezen: "We hebben het geheimrecept voor Thompson Sampling ontdekt. Het is geweldig, maar als je het kruidje (de regularisatie) een beetje aanpast om je te richten op het juiste type spanning, wordt het nog beter."

Technische Samenvatting: Een Breder Perspectief op Thompson Sampling

Probleemstelling
Thompson Sampling (TS) is een veelgebruikte heuristiek voor het Multi-Armed Bandit (MAB)-probleem, bekend om zijn empirische succes en theoretische regret-grenzen. In tegenstelling tot Upper Confidence Bound (UCB) of Gittins-indexbeleid, blijft het expliciete optimalisatieprincipe dat de balans tussen exploratie en exploitatie bij TS regelt, ondoorzichtig. Waar Gittins (1979) de Bayesiaanse MAB formuleerde als een Markov Beslissingsproces (MDP) om een optimaal beleid af te leiden, vertrouwt die aanpak op oneindige-horizont afgekwakte beloningen. Deze formulering leidt tot "onvolledig leren" (het falen om de optimale arm oneindig vaak te identificeren), wat in strijd is met het doel van regret-minimalisatie over een eindige horizon, centraal in de MAB-literatuur (Robbins 1952; Lai en Robbins 1985). Het artikel adresseert het gat in het begrip van TS door een "trouwe" stationaire formulering te zoeken die in overeenstemming is met regret-minimalisatie over een eindige horizon, terwijl de hanteerbaarheid van dynamische programmering behouden blijft.

Methodologie
De auteurs stellen een raamwerk voor van trouwe stationarisatie om het niet-stationaire probleem van regret-minimalisatie over een eindige horizon te herformuleren tot een stationair online optimalisatieprobleem.

Doelstelling met Kwart Regret: In plaats van cumulatief regret $R_T$ direct te minimaliseren of afgekwakte beloningen te gebruiken, introduceren de auteurs het minimaliseren van de cumulatieve kwadratische regret $R_2$ . Zij stellen een grens vast: $R_T \leq \sqrt{R_2 \cdot T}$ . Het minimaliseren van de som van kwadratische regrets over een oneindige horizon $R_2(Q; \pi_0) = \mathbb{E}[\sum r^2(q_t; \pi_t)]$ zorgt ervoor dat het beleid de optimale regret-snelheid van $O(\sqrt{T})$ bereikt, terwijl het een stationair doel biedt.
Stationaire Bellman-vergelijking: Dit nieuwe doel levert een stationaire Bellman-vergelijking op voor de waardenfunctie $V(\pi_t)$ (de minimale toekomstige kwadratische regret):
$V(\pi_t) = \min_{q_t} \left[ r^2(q_t; \pi_t) + q_t \cdot \mathbb{E}_{\pi_t}[V(\pi_{t+1}) | A_t = \cdot] \right]$
In tegenstelling tot de Gittins-index (die lineaire afgekwakte beloning maximaliseert), is deze minimalisatie kwadratisch in de actieprobabiliteiten, wat leidt tot een gerandomiseerd optimaal beleid in plaats van een deterministisch beleid.
Online Optimalisatievorm: Door een variabeletransformatie met focus op de verwachte beloning in de volgende ronde $x_t$ , leiden de auteurs af dat het $R_2$ -optimale beleid ( $Q_{R2}$ ) de vorm aanneemt van een online optimalisatieprobleem:
$x_{R2}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{R2}(\pi_t) x_t \right]$
Hier vertegenwoordigt de eerste term directe exploitatie (gierigheid) en de tweede term een lineaire regularisatie die exploratie voorstelt. De regularisator $\nu_{R2}(\pi_t)$ is afgeleid uit de Bellman-vergelijking en meet de spanning tussen exploratie en exploitatie (het verschil in toekomstige waarde tussen het trekken van armen).
Hertolking van Thompson Sampling: De auteurs tonen aan dat Thompson Sampling exact dezelfde online optimalisatievorm toelaat:
$x_{TS}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{TS}(\pi_t) x_t \right]$
Echter, is hun regularisator $\nu_{TS}(\pi_t)$ de biseriale covariantie tussen het beloningsverschil ( $\theta_1 - \theta_2$ ) en de identiteit van de optimale arm ( $\text{sign}(\theta_1 - \theta_2)$ ). Deze regularisator meet onzekerheid over welke arm beter is, in plaats van de spanning tussen directe beloning en toekomstige waarde.

Belangrijkste Bijdragen

Trouwe Stationarisatie: Het artikel introduceert een stationaire formulering (minimalisatie van kwadratische regret) die de essentie van regret-minimalisatie over een eindige horizon behoudt, en zo het gat overbrugt tussen heuristisch sampling en principed dynamische programmering.
Structurele Unificatie: Het onthult dat zowel Thompson Sampling als het Bellman-optimale beleid ( $Q_{R2}$ ) voorbeelden zijn van online optimalisatiealgoritmen die gierigheid afwegen tegen een regularisator.
Mechanisme-identificatie: Het artikel identificeert het specifieke mechanisme dat TS drijft: het regulariseert gierigheid op basis van onzekerheid (biseriale covariantie), terwijl het optimale beleid regulariseert op basis van spanning (verschil in toekomstige waarde).
Beleidverbetering: Door gebruik te maken van het Bellman-raamwerk, stellen de auteurs een standaardstap voor beleidsverbetering voor TS voor. Door de waardenfunctie van TS te evalueren en deze terug te koppelen in de Bellman-vergelijking, leiden ze een verbeterd beleid af ( $Q_{TS'}$ ) dat een spanningsgebaseerde regularisator gebruikt.

Resultaten

Prestatiekloof: Numerieke experimenten op Gaussische en Bernoulli-bandieten tonen aan dat het $R_2$ -optimale beleid ( $Q_{R2}$ ) aanzienlijk lagere cumulatieve regret bereikt dan Thompson Sampling. De kloof wordt toegeschreven aan het feit dat de regularisator van TS een onzekerheidsmaat is die de "spanning" niet vastlegt wanneer de leidende arm onzeker is, maar de suboptimale arm overmatig wordt geëxploiteerd.
Informatie-gestuurd Sampling (IDS): Het artikel vindt dat IDS, een andere heuristiek, dezelfde spanningsgebaseerde regularisatorstructuur deelt als $Q_{R2}$ en bijna identiek presteert aan het Bellman-optimale beleid, waardoor informatietheoretische en dynamische programmeringsperspectieven worden verbonden.
Eén-staps Verbetering: Een enkele stap voor beleidsverbetering toegepast op Thompson Sampling sluit ongeveer 90% van de prestatiekloof tussen TS en het Bellman-optimale referentiepunt. Deze verbetering transformeert de regularisator van TS effectief van een onzekerheidsmaat naar een spanningsmaat.
Structurele Eigenschap in K-arme Geval: In de K-arme setting wijst het Bellman-optimale beleid (en het verbeterde TS) op elk moment positieve waarschijnlijkheid toe aan maximaal twee armen, terwijl standaard TS positieve waarschijnlijkheid kan toekennen aan alle armen. De stap voor beleidsverbetering verleent TS deze structurele spaarzaamheid.

Betekenis
Het artikel claimt een "breder perspectief" op Thompson Sampling te bieden door het te herformuleren als een online optimalisatiealgoritme. Deze lens:

Legt de Heuristiek uit: Het verduidelijkt dat TS exploratie en exploitatie in evenwicht brengt door gierigheid te regulariseren met een maat voor residuale onzekerheid.
Identificeert Beperkingen: Het wijst erop dat de afhankelijkheid van TS van onzekerheid in plaats van spanning leidt tot suboptimaal gedrag in specifieke regimes (bijvoorbeeld wanneer de optimale arm onzeker is, maar de suboptimale arm duidelijk overmatig wordt geëxploiteerd).
Maakt Principed Verbetering Mogelijk: Het biedt een rigoureus raamwerk voor het verbeteren van posterior-samplingalgoritmen. Door de regularisator af te stemmen op de Bellman-optimale spanningsmaat, tonen de auteurs aan dat TS aanzienlijk kan worden verbeterd met minimale rekenkundige overhead (een enkele beleidsiteratiestap), waardoor het dichter bij het theoretische optimum komt zonder zijn op sampling gebaseerde aard op te geven.