Adaptive Prior Selection in Gaussian Process Bandits with Thompson Sampling

Each language version is independently generated for its own context, not a direct translation.

Stel je voor dat je een grote, onbekende stad moet verkennen om de beste plek te vinden voor een nieuw restaurant. Je hebt geen kaart, maar je hebt wel een paar verschillende gidsen (de "priors") bij je.

Elke gids heeft een eigen idee van hoe de stad eruitziet:

Gids A denkt dat de stad vol smalle steegjes zit.
Gids B denkt dat alles op grote boulevards ligt.
Gids C denkt dat de stad een groot park is.

Het probleem is: Je weet niet welke gids het juiste idee heeft. Als je naar de verkeerde gids luistert, loop je misschien uren rond in een doodlopend straatje (dit noemen we "regret" of "spijt" in de wetenschap).

In de wereld van kunstmatige intelligentie (AI) heet dit het Gaussian Process Bandit probleem. Het gaat vaak over het vinden van de beste instellingen voor complexe machines (zoals het afstellen van een zelfrijdende auto of het ontwerpen van een nieuw medicijn), waarbij elke test duur of tijdrovend is.

Het oude probleem: De "Gokker" vs. De "Wiskundige"

Vroeger hadden wetenschappers twee manieren om met deze onzekere gidsen om te gaan:

De Wiskundige (UCB): Deze methode is extreem voorzichtig en optimistisch. Hij zegt: "Laten we aannemen dat Gids A misschien gelijk heeft, en gaan we die plek testen die volgens Gids A het allerbelangrijkste is!" Het probleem is dat deze methode vaak te veel tijd besteedt aan het testen van gidsen die waarschijnlijk fout zijn, omdat ze "te optimistisch" zijn. Ze blijven vastlopen in de verkeerde steegjes.
De Gokker (Thompson Sampling): Deze methode is slimmer. Hij zegt: "Ik kies willekeurig een gids, maar ik geef meer kans aan de gidsen die tot nu toe het beste hebben gepresteerd." Dit werkt vaak beter, maar als je geen idee hebt welke gids de juiste is, kan het nog steeds misgaan.

De nieuwe oplossing: Twee slimme strategieën

De auteurs van dit paper (Jack Sandberg en Morteza Haghir Chehreghani) hebben twee nieuwe manieren bedacht om de juiste gids te vinden zonder te veel tijd te verspillen. Ze noemen hun methoden PE-GP-TS en HP-GP-TS.

1. PE-GP-TS: De "Cursus-ontvanger" (Prior-Elimination)

Stel je voor dat je een groep van 10 gidsen hebt. Je geeft ze allemaal een opdracht.

Als Gids A zegt: "Ga naar het noorden, daar is een meer," en jij loopt erheen en ziet alleen een droge woestijn, dan zeg je: "Oké, Gids A, je bent ontslagen. Je kunt niet meer mee."
Je blijft dit doen tot je alleen nog maar de gidsen over hebt die consistent goed presteren.

De truc: In het verleden deden wetenschappers dit met de "Wiskundige" methode, wat betekende dat ze te optimistisch waren en soms gidsen onterecht vasthielden. Deze nieuwe methode gebruikt de "Gokker"-methode. Ze laten de gidsen een gok doen, en als hun voorspelling te ver afwijkt van de werkelijkheid, worden ze direct uitgesloten. Dit voorkomt dat je te lang vastzit in een slechte strategie.

2. HP-GP-TS: De "Slimme Manager" (HyperPrior)

Deze methode is nog slimmer. In plaats van gidsen te ontslaan, houdt deze manager een vertrouwensscore bij voor elke gids.

Elke keer als je een test doet, kijkt de manager: "Welke gids had de beste voorspelling?"
Als Gids A het goed deed, krijgt hij meer vertrouwen (hij krijgt een hogere kans om de volgende keer te kiezen).
Als Gids B het slecht deed, krijgt hij minder vertrouwen.

Het verschil: De manager kiest niet zomaar een gids, maar kiest op basis van de kans dat die gids de juiste is. Het is alsof je een team hebt waar je continu de beste presteerder belooft en de slechtere presteerders minder kansen geeft, zonder ze direct te ontslaan. Dit werkt vaak het snelst en het efficiëntst.

Waarom is dit belangrijk?

Stel je voor dat je een elektrische auto ontwikkelt. Je wilt de batterij zo instellen dat hij het langst meegaat, maar je weet niet welke chemische samenstelling het beste werkt. Je hebt 100 verschillende theorieën (gidsen) over welke chemie werkt.

Als je de oude methoden gebruikt, test je misschien 50 keer een chemie die nooit werkt, omdat je te optimistisch was. Dat kost veel geld en tijd.
Met de nieuwe methoden van dit paper, leer je snel welke theorieën fout zijn en focus je je op de juiste theorieën.

De resultaten in het kort

De auteurs hebben hun nieuwe methoden getest op:

Verzonnen data: Simpele wiskundige puzzels.
Echte data: Temperatuurmetingen in een lab, verkeersdata op snelwegen en regenval in de VS.

De uitkomst:

Hun nieuwe methoden (vooral de "Slimme Manager") vonden de beste oplossing sneller en met minder fouten dan de oude methoden.
Ze bleven niet vastzitten in de verkeerde opties.
Ze konden zelfs werken als er heel veel gidsen (theorieën) waren, zonder dat het proces trager werd.

Conclusie

Kortom: Dit paper leert computers hoe ze sneller kunnen leren in een onbekende wereld. Door slimme manieren te gebruiken om te kiezen tussen verschillende theorieën (priors), kunnen ze de beste oplossing vinden met minder proefjes en minder verspilde tijd. Het is alsof je een navigator hebt die niet alleen de weg wijst, maar ook zelf leert welke gidsen je kunt vertrouwen.

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het artikel "Adaptive Prior Selection in Gaussian Process Bandits with Thompson Sampling" in het Nederlands.

Titel: Adaptieve Prior-selectie in Gaussian Process Bandits met Thompson Sampling

Auteurs: Jack Sandberg en Morteza Haghir Chehreghani (Chalmers University of Technology & University of Gothenburg)

1. Probleemstelling

Gaussian Process (GP) bandits bieden een krachtig raamwerk voor het optimaliseren van onbekende functies (blackbox-optimalisatie) met ruis, zoals hyperparameter-tuning of drug discovery. Een cruciale aanname in de meeste theoretische werken is dat de GP-prior (de aannames over de gladheid en structuur van de functie, bepaald door de kernel en hyperparameters) bekend is.

In de praktijk is dit echter zelden het geval. Practici vertrouwen vaak op Maximum Likelihood Estimation (MLE) om hyperparameters te selecteren, wat geen theoretische garanties biedt in sequentiële besluitvormingsproblemen. Bestaande methoden voor onbekende priors (zoals PE-GP-UCB) gebruiken vaak "dubbel optimistische" strategieën (Upper Confidence Bound - UCB) die leiden tot over-exploratie.

Het doel van dit werk is het ontwikkelen van algoritmen die zowel de optimale arm (actie) als de juiste prior selecteren, terwijl ze de regret (het verschil tussen de beste mogelijke beloning en de werkelijke beloning) minimaliseren, zonder afhankelijk te zijn van een vooraf bekende prior.

2. Methodologie

De auteurs stellen twee nieuwe algoritmen voor die gebaseerd zijn op Gaussian Process Thompson Sampling (GP-TS), in plaats van UCB. Beide algoritmen werken met een eindige verzameling van mogelijke priors $\mathcal{P}$ .

A. Prior-Elimination GP-TS (PE-GP-TS)

Dit algoritme is een extensie van het bestaande PE-GP-UCB, maar vervangt de UCB-selectie door Thompson Sampling.

Mechanisme:
1. Voor elke actieve prior $p \in \mathcal{P}_t$ wordt een functie $\tilde{f}_{t,p}$ getrokken uit de posterior.
2. De arm $x_t$ en prior $p_t$ worden geselecteerd die het hoogste $\tilde{f}_{t,p}(x)$ opleveren.
3. Eliminatie: Na het observeren van de beloning wordt de voorspellingsfout $\eta_t$ berekend. Als de cumulatieve voorspellingsfout van een prior een bepaalde drempelwaarde $V_t$ overschrijdt, wordt die prior uit de set van actieve priors verwijderd.
Voordeel: In tegenstelling tot PE-GP-UCB (dat twee lagen optimisme heeft: de UCB en de selectie van de prior), heeft PE-GP-TS slechts één laag optimisme (de posterior sampling). Dit vermindert het risico op over-exploratie.

B. HyperPrior GP-TS (HP-GP-TS)

Dit is een volledig Bayesiaanse aanpak die gebruikmaakt van een bi-level sampling scheme.

Mechanisme:
1. Er wordt een prior $p_t$ getrokken uit de hyperposterior (de verdeling over de priors zelf).
2. Vervolgens wordt een functie $\tilde{f}_t$ getrokken uit de posterior van die specifieke prior.
3. De arm $x_t$ wordt geselecteerd op basis van $\tilde{f}_t$ .
4. De hyperposterior wordt bijgewerkt op basis van de likelihood van de nieuwe observatie onder de verschillende priors.
Voordeel: In plaats van te vertrouwen op optimistische priors, selecteert dit algoritme priors die waarschijnlijk zijn. Het vermijdt de "dubbele optimisme" van UCB-methoden en is computatievriendelijker dan methoden die verwachtingen over de hele hyperposterior integreren (zoals SCoreBO), omdat het slechts één steekproef per stap vereist.

3. Theoretische Analyse en Regret Bounden

De auteurs analyseren de regret (spijt) van beide algoritmen onder verschillende aannames:

PE-GP-TS:
- De regret-bound is van orde $O(\sqrt{T \log T \cdot |\mathcal{P}| \cdot \hat{\gamma}_T})$ , waarbij $T$ de horizon is, $|\mathcal{P}|$ het aantal priors, en $\hat{\gamma}_T$ de ergste-case maximale informatiewinst (MIG).
- Deze bound komt overeen met die van PE-GP-UCB, maar bevat een extra term die afhangt van de onzekerheid van de optimale arm onder de juiste prior.
- Het bewijs toont aan dat de ware prior $p^*$ met hoge waarschijnlijkheid nooit wordt geëlimineerd.
HP-GP-TS:
- De Bayesiaanse regret-bound is van orde $O(\sqrt{T \log T \cdot \bar{\gamma}_T})$ , waarbij $\bar{\gamma}_T$ de gemiddelde maximale informatiewinst is over de hyperprior.
- Belangrijk: De bound hangt niet af van $|\mathcal{P}|$ (het aantal priors) in de hoofdterm, maar van de gemiddelde complexiteit van de priors. Dit is een theoretisch voordeel ten opzichte van eliminatiemethoden als de priors variëren in complexiteit.
- De extra term in de bound representeert de "kosten van het leren van de prior". Empirisch blijkt deze term sublineair te groeien.
Kritiek op bestaand werk: De auteurs identificeren technische fouten in het bewijs van het regret-bound voor het MixTS-algoritme (Hong et al., 2022b) in lineaire bandit-settings, wat de noodzaak onderstreept voor hun eigen rigorieuze analyse.

4. Experimentele Resultaten

De algoritmen zijn getest op drie synthetische setups (verschillende kernels, lengteschalen, en subruimtes) en drie real-world datasets (Intel Berkeley, PeMS verkeer, PNW neerslag).

Vergelijking met Baselines:

Baselines: PE-GP-UCB, SCoreBO, Fully Bayesian Expected Improvement (EEI), en MAP GP-TS (greedy selectie).
Resultaten:
- HP-GP-TS en EEI presteren consistent het beste, met de laagste cumulatieve regret, vaak dicht bij de "Oracle" (waarbij de ware prior bekend is).
- PE-GP-TS presteert beter dan PE-GP-UCB en vaak beter dan de Oracle GP-UCB, wat aantoont dat Thompson Sampling efficiënter is dan UCB voor prior-selectie.
- SCoreBO heeft vaak de hoogste regret, ondanks dat het goed is in het reduceren van hyperposterior-onzekerheid.
- MAP GP-TS (greedy) heeft vaak hogere variantie en regret door onder-exploratie.

Schalingsgedrag:

Bij het verhogen van het aantal priors $|\mathcal{P}|$ (in de lengteschaal- en subruimte-experimenten) blijft de regret van HP-GP-TS stabiel en dicht bij de Oracle.
De regret van eliminatiemethoden (PE-GP-TS/UCB) neemt toe met $\sqrt{|\mathcal{P}|}$ .
Prior-selectie nauwkeurigheid: HP-GP-TS selecteert de ware prior aanzienlijk vaker dan PE-GP-TS en PE-GP-UCB. PE-methoden hebben een bias naar "optimistische" priors (zoals Matérn 3/2 of korte lengteschalen) die vaak niet de ware prior zijn, maar wel hoge voorspelde beloningen geven.

5. Bijdragen en Betekenis

De belangrijkste bijdragen van dit werk zijn:

Nieuwe Algoritmen: Introductie van PE-GP-TS en HP-GP-TS voor adaptieve prior-selectie in GP-bandits.
Theoretische Garantie: Het afleiden van scherpe regret-bounden voor beide algoritmen, waarbij HP-GP-TS een bound heeft die onafhankelijk is van het aantal priors in de hoofdterm.
Kritische Analyse: Het identificeren van fouten in eerdere bewijzen voor MixTS, wat de theoretische basis voor dit vakgebied versterkt.
Empirische Superioriteit: Het aantonen dat Thompson Sampling-gebaseerde methoden superieur zijn aan UCB-gebaseerde eliminatiemethoden en andere Bayesiaanse optimalisatie-approaches, vooral door het verminderen van over-exploratie.

Significantie:
Dit werk lost een praktisch probleem op (onbekende priors) op met een theoretisch onderbouwde oplossing. Het toont aan dat het vermijden van "dubbel optimisme" (door Thompson Sampling te gebruiken in plaats van UCB) leidt tot efficiëntere exploratie en snellere convergentie naar de optimale oplossing, zelfs in complexe scenario's met veel mogelijke priors. Dit maakt de methoden zeer relevant voor real-world toepassingen zoals automatische hyperparameter-tuning en wetenschappelijk experimentontwerp.