Technisch overzicht: Bayesian Anytime Pareto Set Identificatie voor Multi-Objective Multi-Armed Bandits

Probleemdefinitie

Het artikel behandelt het Multi-Objective Multi-Armed Bandit (MOMAB) probleem, met een specifieke focus op Pareto Set Identification (PSI). In tegenstelling tot standaard single-objective banditproblemen die streven naar het maximaliseren van de cumulatieve beloning (regret-minimalisatie) of het identificeren van één beste arm, omvat MOMAB het gelijktijdig optimaliseren van meerdere, potentieel conflicterende doelstellingen. In deze setting is geen enkele arm optimaal over alle criteria; in plaats daarvan bestaat er een verzameling van Pareto-optimale armen ($P^\star$) die de optimale afruil (trade-offs) vertegenwoordigen.

De specifieke uitdaging die wordt aangepakt is de Anytime PSI formulering. Terwijl de bestaande literatuur uitgebreid de fixed-budget (minimaliseren van fout na een vast aantal samples) en fixed-confidence (minimaliseren van samples om een doel nauwkeurigheid te bereiken) settings heeft behandeld, is er een gat in algoritmen die een geldige, continu bijgewerkte schatting van de Pareto-verzameling kunnen bieden na elke observatie zonder een vooraf gedefinieerde stopregel. Dit is cruciaal voor real-world toepassingen waar besluitvormers de voortgang moeten monitoren en experimenten dynamisch kunnen beëindigen op basis van betrouwbaarheidsniveaus in plaats van rigide middelenbeperkingen.

Methodologie: Top-Two Pareto Front Thompson Sampling (TTPFTS)

De auteurs introduceren Top-Two Pareto Front Thompson Sampling (TTPFTS), het eerste Bayesiaanse anytime-algoritme dat is ontworpen voor het MOMAB PSI-probleem. Het algoritme breidt de principes van Top-Two Thompson Sampling (TTTS) van single-objective best-arm identification uit naar het multi-objective domein.

Kernmechanisme

In plaats van doelstellingen te scalariseren met een voorkeursvector (wat het probleem zou reduceren tot een single-objective probleem), opereert TTPFTS direct op de Pareto-fronten. Op elk tijdstip $t$:

1. Posterior Sampling: Het algoritme samplet gemiddelde beloningsvectoren $\tilde{\theta}^{(t)}_a$ voor alle $K$ armen uit hun respectieve posterior distributies, geconditioneerd op de historie $H(t-1)$.
2. Front Identificatie: Op basis van deze samples identificeert het de Eerste Pareto Front ($F^\star_1$), bestaande uit armen die niet worden gedomineerd door enige andere gesamplede arm.
3. Stochastische Selectie: Een Bernoulli-proef met waarschijnlijkheid $\rho$ bepaalt welke front wordt verkend:
   • Met waarschijnlijkheid $\rho$: Een arm wordt uniform willekeurig geselecteerd uit de Eerste Front ($F^\star_1$). Dit richt zich op het verifiëren van armen die momenteel als optimaal worden beschouwd.
   • Met waarschijnlijkheid $1-\rho$: Het algoritme verwijdert $F^\star_1$ en identificeert de Tweede Pareto Front ($F^\star_2$) uit de resterende armen. Een arm wordt vervolgens uniform willekeurig geselecteerd uit $F^\star_2$. Dit bevordert de exploratie van de meest veelbelovende suboptimale armen (uitdagers) om te testen of zij zijn onderschat of om hun suboptimale status te bevestigen.
4. Update: De geselecteerde arm wordt getrokken, de beloning wordt geobserveerd, en de historie wordt bijgewerkt. Het algoritme onderhoudt te allen tijde een aanbevelingsset $\hat{P}^\star_t$ (de Pareto-verzameling van de posterior gemiddelden).

Theoretische Garanties

Het artikel biedt een bewijs van asymptotische correctheid (Theorem 1). Onder standaardveronderstellingen (eindige armen, consistente posteriors, strikte Pareto-gaps en voldoende exploratie), convergeert de schatting $\hat{P}^\star_t$ van het algoritme met waarschijnlijkheid 1 naar de ware Pareto-verzameling $P^\star$ als $t \to \infty$. Het bewijs steunt op Lemma 1, dat vaststelt dat TTPFTS een oneindige exploratie van alle armen bijna zeker garandeert, waardoor wordt voorkomen dat een arm permanent uit het samplingsproces wordt "bevroren".

Belangrijkste Bijdragen

1. Eerste Anytime Bayesiaans Algoritme voor MOMAB PSI: TTPFTS vult het gat in de literatuur met betrekking tot anytime-algoritmen voor Pareto-verzameling identificatie, en biedt een flexibel alternatief voor fixed-budget en fixed-confidence benaderingen.
2. Nieuwe Onzekerheidskwantificatie (UQ) Metriek: De auteurs introduceren een metriek die onafhankelijk is van de grondwaarheid om de betrouwbaarheid van de huidige Pareto-voorspelling van het algoritme te schatten. Deze metriek berekent de Bhattacharyya overlap tussen de posterior dichtheden van de armen in de geschatte eerste front ($\hat{P}^\star_1$) en de tweede front ($\hat{P}^\star_2$).
   • Hoge overlap duidt op hoge onzekerheid (moeilijkheid om optimaal van suboptimaal te onderscheiden).
   • Lage overlap duidt op hoge betrouwbaarheid (duidelijke scheiding tussen de fronten).
   • Deze metriek dient als een real-time proxy voor de identificatieprestaties, wat dynamische stopcriteria mogelijk maakt.
3. Real-World Toepassing in Moleculaire Ontdekking: Het algoritme wordt gevalideerd in een uitdagende, ultra-grote synthesis-on-demand moleculaire bibliotheek setting (94 miljoen kandidaten), waarbij wordt aangetoond dat het nuttig is voor het identificeren van moleculen die conflicterende eigenschappen (Structurele Gelijkenis en LogP) optimaliseren.

Empirische Resultaten

Synthetische Benchmarks

TTPFTS werd geëvalueerd tegen state-of-the-art fixed-budget algoritmen (Successive Rejects en Successive Halving varianten van Empirical Gap Elimination, EGE) over acht synthetische omgevingen met variërende Pareto-front geometrieën en dimensies.

• Prestaties: TTPFTS presteerde consequent beter dan Uniform Sampling en de EGE-SH algoritme. Het behaalde prestatie-gelijkwaardigheid met EGE-SR (de sterkste fixed-budget baseline) in alle omgevingen, ondanks de striktere anytime constraint.
• Schaalbaarheid: In omgevingen met grote actieruimtes (bijv. $K=200$), presteerde TTPFTS aanzienlijk beter dan EGE-varianten, wat suggereert dat de posterior-gestuurde allocatie van TTPFTS effectiever is dan rigide gap-gebaseerde eliminatie in grootschalige problemen.
• Robuustheid: Het algoritme presteerde goed, zelfs met zwakke prior-aannames (uniforme priors).

Casestudy Moleculaire Ontdekking

Bij de exploratie van een 94-miljoen verbindingen bibliotheek:

• Efficiëntie: TTPFTS identificeerde moleculen die perfect overeenkwamen met de grondwaarheid Pareto-front (52 moleculen) terwijl slechts 0,05% van de database werd geëvalueerd.
• Vergelijking: Het presteerde significant beter dan zowel Random Search (die nul optimale moleculen vond) als de state-of-the-art active learning methode MolPAL.
• Onzekerheid Correlatie: De voorgestelde UQ-metriek vertoonde een sterke negatieve correlatie met de Jaccard-metriek (nauwkeurigheid). Naarmate het algoritme zijn Pareto-verzameling schatting verbeterde, nam de onzekerheidsmetriek af, wat het gebruik ervan als een betrouwbare, grondwaarheid-onafhankelijke indicator van convergentie valideert.

Betekenis en Claims

Het artikel claimt dat TTPFTS een robuuste methodologie biedt voor het monitoren van leerprogressie in complexe, multi-objective settings zonder kennis te vereisen van de ware Pareto-front. Door een anytime exploratiestrategie te combineren met een nieuwe onzekerheidskwantificatiemetriek, transformeert dit werk het Pareto-verzameling identificatieprobleem van een statische samplingtaak naar een dynamisch besluitvormingssysteem.

De auteurs benadrukken dat deze aanpak besluitvormers in staat stelt om:

• Dynamisch te bepalen wanneer de Pareto-front voldoende is opgelost om een experiment te beëindigen.
• De afweging tussen computationele middelen en ontdekkingsvertrouwen te optimaliseren.
• Deze voordelen toe te passen op real-world scenario's zoals drug discovery, waar uitputtende screening onhaalbaar is en voorkeuren niet vooraf bekend hoeven te zijn.

Het artikel blijft bescheiden over finite-time error bounds, en erkent dat hoewel asymptotische correctheid bewezen is, het afleiden van expliciete finite-time rates een uitdaging blijft, vergelijkbaar met de uitdagingen die standaard Thompson Sampling in het verleden ervoer. De auteurs argumenteren echter dat de combinatie van asymptotische correctheid, sterke empirische prestaties en het praktische nut van de onzekerheidsmetriek TTPFTS een significante vooruitgang maakt in multi-objective besluitvorming.