🤖 AI

Functional multi-armed bandit and the best function identification problems

Dit artikel introduceert de functionele multi-armed bandit en best function identification probleemklassen om realistische scenario's zoals competitieve LLM-training aan te pakken, waarbij een nieuw F-LCB reductieschema wordt voorgesteld dat UCB-type algoritmen construeert met bewijsbare regret-bounds gebaseerd op convergentiesnelheden van nietlineaire optimalisatie.

Oorspronkelijke auteurs: Yuriy Dorn, Aleksandr Katrutsa, Ilgam Latypov, Anastasiia Soboleva

Gepubliceerd 2026-06-23

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yuriy Dorn, Aleksandr Katrutsa, Ilgam Latypov, Anastasiia Soboleva

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

Stel je voor dat je een chef bent die probeert het enkele beste recept uit een honderd kandidaten te vinden om te serveren bij een groot banket. Je hebt een beperkte hoeveelheid tijd en ingrediënten (een "budget").

In de oude manier van doen (traditionele methoden), zou je misschien een klein beetje van elke taart bakken, ze proeven, en dan beslissen. Of je zou één taart helemaal afbakken, dan de volgende, en dan de volgende. Beide benaderingen zijn traag en verspillend. Als je 100 taarten hebt, ben je misschien al door je tijd heen voordat je zelfs de eerste paar hebt afgerond.

Dit artikel introduceert een slimmere manier om dit probleem op te lossen, wat de auteurs de Functional Multi-Armed Bandit (FMAB) en het Best Function Identification (BFI) probleem noemen.

Hier is de uitleg van hun idee met eenvoudige analogieën:

1. Het Probleem: De "Black Box" Taartwedstrijd

Normaal gesproken, wanneer computers proberen het beste model te kiezen (zoals een neuraal netwerk voor AI), behandelen ze elk model als een "black box". Ze weten niet hoe de taart rijst of hoe de ingrediënten mengen; ze proeven alleen het resultaat.

De Uitdaging: Het trainen van moderne AI-modellen is als het bakken van een enorme, complexe taart. Het duurt dagen en kost een fortuin aan elektriciteit. Je kunt het je niet veroorloven om elk kandidaat-recept tot het einde toe te bakken om te zien welke het beste is.
Het Doel: Je moet het recept met de laagste fout (de lekkerste taart) vinden en stoppen met het verspillen van tijd aan de slechte recepten zo snel mogelijk.

2. Het Nieuwe Idee: "Slim Proeven" (F-LCB)

De auteurs stellen een nieuw algoritme voor genaamd F-LCB. Zie dit als een zeer slimme sous-chef die niet alleen de taart proeft, maar ook de fysica van het bakken begrijpt.

In plaats van elk recept als een mysterieus pakketje te behandelen, behandelt F-LCB elk recept als een proces met een bekende snelheidslimiet.

De Analogie: Stel je voor dat je weet dat "Recept A" (een eenvoudige sponscake) meestal elke minuut in omvang verdubbelt. "Recept B" (een dichte vruchtentaart) groeit slechts met 1% per minuut.
Hoe F-LCB werkt:
1. Het begint alle recepten een klein beetje te bakken.
2. Het kijkt naar de "Lower Confidence Bound" (LCB). Dit is een chique manier om te zeggen: "Gebaseerd op hoe snel deze taart zou moeten rijzen, wat is het slechtst denkbare scenario voor de uiteindelijke smaak?"
3. Als een taart te langzaam rijst in vergelijking met zijn potentieel, zegt het algoritme: "Deze is waarschijnlijk een verliezer," en stopt het met het bakken ervan.
4. Het stort alle resterende tijd en ingrediënten in de recepten die de meeste belofte tonen.

3. Waarom is dit beter dan de oude manieren?

Het artikel vergelijkt hun methode met twee beroemde concurrenten: Successive Halving en Hyperband.

De Concurrenten: Dit zijn als een chef die het budget elke ronde met de helft vermindert. Hij bakt iedereen een beetje, elimineert de onderste 50%, bakt de rest iets langer, elimineert de onderste 50% opnieuw, enzovoort. Het is efficiënt, maar het is een beetje rigide. Het geeft niet om hoe de taart rijst, alleen om de huidige smaak.
F-LCB (De methode van de auteurs): Deze chef kijkt naar het traject. Als een taart snel rijst, weet F-LCB dat deze snel geweldig zal zijn en focust het zich erop. Als een taart langzaam rijst, weet het dat deze nooit zal inhalen.
Het Resultaat: In hun experimenten (het bakken van digitale taarten op een computer) vond F-LCB het beste model sneller en met minder rekenkracht dan de concurrenten, vooral wanneer het budget krap was.

4. Wat hebben ze bewezen?

De auteurs hebben niet alleen gegokt dat dit zou werken; ze hebben de wiskunde gebruikt om het te bewijzen.

De Lower Bound: Ze hebben bewezen dat er, ongeacht hoe slim je bent, een minimale hoeveelheid tijd is die je moet besteden om de beste taart te vinden.
De Upper Bound: Ze hebben bewezen dat hun F-LCB-algoritme heel dicht bij die minimale tijdslimiet komt. Het is zo efficiënt als wiskundig mogelijk (binnen een kleine foutmarge).

5. Tests in de echte wereld

Ze hebben dit getest in drie scenario's:

Gladde Taarten: Standaard, goed gedrag vertoonde wiskundige functies. F-LCB vond de beste snel.
Ruwe Taarten: Functies die grillig en moeilijk te optimaliseren zijn. F-LCB werkte nog steeds goed.
Neurale Netwerken: Ze gebruikten het om de beste AI-architectuur te kiezen voor een beeldclassificatietaak (het identificeren van objecten in foto's). F-LCB identificeerde het beste model met minder trainingsstappen dan de andere methoden.

Samenvatting

Het artikel zegt: "Stop met blind gokken. Gebruik de bekende snelheid van je optimalisatieproces om te voorspellen welke modellen zullen winnen, en stop met het verspillen van geld aan degenen die nu al aan het verliezen zijn."

Ze hebben een hulpmiddel (F-LCB) gecreëerd dat fungeert als een slimme manager, die constant de voortgang van elke kandidaat controleert, de trage er vroegtijdig mee af snijdt en alle middelen in de winnaar pompt, waardoor er enorme hoeveelheden tijd en geld worden bespaard in het proces.

Technische Samenvatting: Functionele Multi-Armed Bandit en Best Function Identification

1. Probleemstelling

Het artikel behandelt het modelselectieprobleem in scenario's met beperkte computationele budgetten, zoals bij competitieve neurale netwerktraining. De kernuitdaging is het identificeren van de optimale functie (bijv. de beste neurale netwerkarchitectuur of hyperparameterinstelling) uit een verzameling van $K$ kandidaatfuncties $\{f_1, \dots, f_K\}$ , waarbij elke functie $f_i$ is gedefinieerd over een convexe beslissingsverzameling $X_i$ .

De auteurs formaliseren twee nieuwe probleemopstellingen die de klassieke Multi-Armed Bandit (MAB) en Best Arm Identification (BAI) generaliseren:

Functionele Multi-Armed Bandit (FMAB): De agent selecteert op elk tijdstip $t$ een index $i_t$ en een beslissingsvector $x_{t, i_t} \in X_{i_t}$ . Het doel is om de cumulatieve regret te minimaliseren: $R_O(T) = \sum_{t=1}^T [f_{i_t}(x_{t, i_t}) - f^*]$ , waarbij $f^* = \min_{i} \min_{x \in X_i} f_i(x)$ . In tegenstelling tot standaard MAB waar armen willekeurige variabelen zijn, is elke arm hier een onbekende functie die wordt geoptimaliseerd via een black-box oracle (bijv. gradiënten).
Best Function Identification (BFI): De agent streeft ernaar om na $T$ ronden de enkelvoudige beste functie $J_T$ te identificeren, zodanig dat de uiteindelijke regret $R_B(T) = \min_{x \in X_{J_T}} f_{J_T}(x) - f^*$ wordt geminimaliseerd.

Het artikel betoogt dat het reduceren van deze problemen naar standaard MAB (door elk punt $x$ als een arm te behandelen) leidt tot onhaalbare computationele kosten vanwege de continue aard van de beslissingsruimtes. In plaats daarvan maakt het voorgestelde framework gebruik van de interne dynamiek van optimalisatiealgoritmen.

2. Methodologie: Het F-LCB Algoritme

Om FMAB en BFI op te lossen, stellen de auteurs het F-LCB (Functional Lower Confidence Bound) algoritme voor. Dit is een UCB-type algoritme dat betrouwbaarheidsintervallen construeert op basis van de convergentiesnelheden van onderliggende basisoptimalisatiealgoritmen, in plaats van de statistische concentratie van willekeurige variabelen.

Kernmechanisme

Basisoptimizers: Elke kandidaatfunctie $f_i$ is geassocieerd met een basisoptimalisatiealgoritme $A_i$ (bijv. Projected Gradient Descent, Accelerated Gradient Descent) waarvan een specifieke convergentiesnelheid $g_i(k, \delta)$ bekend is.
Lower Confidence Bound (LCB): Het algoritme onderhoudt op elk moment een LCB voor elke functie $i$ :
$LCB_i(k_i, \delta) = f_i(x_{i, k_i}) - g_i(k_i, \delta)$
Hierbij is $k_i$ het aantal iteraties dat aan functie $i$ is toegewezen, en $g_i(k_i, \delta)$ vertegenwoordigt de theoretische bovengrens op de suboptimaliteitskloof na $k_i$ stappen.
Selectieregel: Het algoritme selecteert de arm $i_t$ met de minimale LCB-waarde.
Update: Het voert één iteratie uit van de basisoptimizer $A_{i_t}$ , werkt de functiewaarde bij en herrekent de LCB.
Stopcriterium (voor BFI): Het proces stopt wanneer de kloof tussen de huidige beste schatting en de LCB onder een drempelwaarde $\epsilon$ valt, wat garandeert dat de geïdentificeerde functie binnen $\epsilon$ van het globale optimum ligt.

Het algoritme balanceert effectief tussen exploratie (budget toewijzen aan functies met een hoge onzekerheid of veelbelovend potentieel) en exploitatie (het verfijnen van de beste kandidaat) door direct te reageren wanneer een arms LCB suboptimaal wordt.

3. Belangrijkste Bijdragen

Theoretische Bijdragen

Probleemformulering: Het artikel introduceert de FMAB- en BFI-frameworks en onderscheidt deze formeel van klassieke MAB door armen te modelleren als optimalisatietaken met bekende convergentie-eigenschappen.
Ondergrenzen (Lower Bounds): De auteurs stellen minimax lower bounds vast voor zowel FMAB als BFI in deterministische settings. Deze grenzen zijn afhankelijk van de complexiteit van de functieklassen (bijv. convexe $M$ $M$ -Lipschitz, $L$ $L$ -smooth, $\mu$ $μ$ -sterk convexe).
- Voor bijvoorbeeld convexe $M$ -Lipschitz functies is de ondergrens $\Omega(MR\sqrt{T})$ .
- Voor $\mu$ -sterk convexe en $L$ -smooth functies is de grens $\Omega(R^2)$ .
Regret Upper Bounds: Het artikel bewijst dat het F-LCB algoritme regret upper bounds bereikt die de afgeleide lower bounds benaderen tot aan logaritmische factoren.
- In het deterministische geval hangt de regret af van de convergentiesnelheid $r$ van de basisoptimizer (bijv. $O(\sqrt{T})$ voor $r=1/2$ ).
- In het stochastische geval (inexacte oracles) bevatten de grenzen ruisparameters en gelden ze met een hoge waarschijnlijkheid.

Algoritmische Bijdragen

F-LCB Algoritme: Een nieuw reductieschema dat de convergentiesnelheden van optimalisatieprocessen integreert in het bandit-selectieproces. Het verenigt de arm-selectiestap met de update van de huidige optimaal-benadering.
Flexibiliteit: Het framework staat verschillende basisoptimizers toe voor verschillende armen, mits hun convergentiesnelheden bekend zijn.

4. Experimentele Resultaten

De auteurs valideren F-LCB via numerieke experimenten op synthetische en real-world datasets:

Synthetische Convexe Functies:
- Smooth Convex: F-LCB identificeerde succesvol de functie met het globale minimum onder drie kandidaten, waarbij updates aan suboptimale functies stopten zodra deze geïdentificeerd waren.
- Non-Smooth Convex: Met behulp van stuksgewijs lineaire functies en een subgradient methode, toonde F-LCB convergentie aan naar de optimale functie met een cumulatieve regret die consistent is met de theoretische grenzen.
- Inexact Oracles: In aanwezigheid van gradiëntruis identificeerde F-LCB nog steeds de beste functie, hoewel de convergentiecurves minder duidelijk waren dan in het deterministische geval.
Neurale Netwerk Selectie (BFI):
- Setup: Het algoritme werd toegepast op de CIFAR-100 beeldclassificatietaak, waarbij de beste architectuur werd geselecteerd uit een set van 10 modellen (inclusief MobileNet, ShuffleNet en ResNet varianten) met minder dan 5M parameters.
- Vergelijking: F-LCB werd vergeleken met SuccessiveHalving (SH) en Hyperband.
- Resultaat: F-LCB presteerde beter dan beide baselines in scenario's met een laag budget (bijv. $T=50, 100$ ), waarbij een lagere gemiddelde rang voor het geselecteerde model werd behaald. In tegenstelling tot Hyperband, dat budgetten splitst over meerdere SH-runs, werpt F-LCB modellen niet permanent weg maar wijst het middelen dynamisch toe. In grotere budgetten ( $T \ge 350$ ) presteerde F-LCB vergelijkbaar met SH en identificeerde het consequent het beste model.

5. Betekenis en Claims

Het artikel claimt dat F-LCB een theoretisch gefundeerd alternatief biedt voor heuristische AutoML-methoden (zoals SuccessiveHalving en Hyperband) en puur black-box benaderingen (zoals Bayesian Optimization).

Theoretische Garanties: In tegenstelling tot heuristische methoden maakt F-LCB gebruik van de bekende convergentiesnelheden van optimalisatieprocessen om formele regret-garanties en identificatiegrenzen af te leiden.
Efficiëntie: De aanpak is bijzonder effectief wanneer de computationele budgetten krap zijn, omdat het de sub-exponentiële kosten vermijdt die gepaard gaan met het behandelen van optimalisatieproblemen als standaard MAB's met oneindige hoeveelheden armen.
Toepasbaarheid: Het framework is toepasbaar op elk scenario waar kandidaatmodellen worden opgelost via iteratieve optimalisatie met bekende convergentie-eigenschappen (bijv. convexe relaxaties, specifieke optimalisatiemethode selectie).

Beperkingen erkend door de auteurs

Het artikel merkt expliciet op dat de aanpak voorafgaande kennis vereist van de functionele klasse van het objectief en de convergentiesnelheid $g(k, \delta)$ van het basisalgoritme. Dit is een significante beperking voor deep learning, waarbij de convergentiesnelheden voor niet-convexe neurale netwerktraining niet strikt gedefinieerd zijn op de wijze die het algoritme vereist. Bijgevolg, hoewel de methode werkt voor convexe problemen en specifieke optimalisatietaken, rust de toepassing ervan op algemene neurale netwerktraining op heuristische benaderingen van $g(k)$ .