Technische Samenvatting: Op Kosten Gesorteerde Haalbaarheid voor Multi-Armed Bandits met Kosten Subsidie

Probleemformulering

Dit artikel behandelt het probleem van Multi-Armed Bandits met Kosten Subsidie (MAB-CS), een raamwerk ontworpen voor kostengevoelige online besluitvorming waarbij het doel is om de cumulatieve kosten te minimaliseren onder een kwaliteitsbeperking. In tegenstelling tot standaard MAB's die de cumulatieve beloning maximaliseren, streeft MAB-CS naar de goedkoopste arm onder die welke voldoen aan een drempel voor de verwachte minimale beloning.

De hier onderzochte specifieke setting omvat een kwaliteitsbeperking die is gedefinieerd ten opzichte van de onbekende beste beloning in het systeem. Gegeven een set armen $\mathcal{A} = \{a_1, \dots, a_K\}$ met verwachte beloningen $\mu_k$ en bekende bemonsteringskosten $c_k$, is de haalbare verzameling $S = \{a_k \in \mathcal{A} \mid \mu_k \geq \mu_{CS}\}$. De drempel is gedefinieerd als $\mu_{CS} = (1-\alpha)\mu^*$, waarbij $\mu^* = \max_{a_k \in \mathcal{A}} \mu_k$ de onbekende beste beloning is en $\alpha \in (0, 1)$ een subsidiefactor is. De optimale arm $a^*$ is de goedkoopste arm in de haalbare verzameling $S$.

Het artikel definieert twee regret-metrics:

1. Kostenregret: De extra kosten die worden gemaakt ten opzichte van de optimale arm $a^*$.
2. Kwaliteitsregret: De straf die wordt opgelegd wanneer de verwachte beloning van de geselecteerde arm onder de haalbaarheidsdrempel $\mu_{CS}$ valt.

De kernuitdaging ligt in het gezamenlijk minimaliseren van deze regrets, terwijl gelijktijdig de onbekende drempel $(1-\alpha)\mu^*$ wordt geschat en de goedkoopste haalbare arm wordt geïdentificeerd zonder voorafgaande kennis van $\mu^*$.

Methodologie: Het COF-algoritme

De auteurs stellen het Cost-Ordered Feasibility (COF)-algoritme voor om het MAB-CS-probleem op te lossen. COF werkt door armen te evalueren in oplopende volgorde van hun bekende kosten. Voor elke kandidaat-arm $a_\ell$ bepaalt het algoritme de haalbaarheid door deze te vergelijken met een set "gating arms" (armen die duurder zijn dan $a_\ell$).

Belangrijke mechanismen in COF zijn:

• Op Kosten Gesorteerde Evaluatie: Armen worden sequentieel getest van goedkoopst naar duurst. De eerste arm die als haalbaar wordt beschouwd, wordt geselecteerd als de optimale arm voor de rest van de horizon.
• Combineren van Steekproeven (Aggregatie): Om te bepalen of een kandidaat-arm $a_\ell$ onhaalbaar is, vertrouwt COF niet op één paarsgewijze vergelijking. In plaats daarvan aggregeert het bewijs uit vergelijkingen met alle armen die in staat zijn $a_\ell$ te diskwalificeren. Het berekent een bovengrens voor de waarschijnlijkheid dat $a_\ell$ haalbaar is ten opzichte van elke gating arm en beschouwt $a_\ell$ als onhaalbaar zodra het product van deze probabilities onder een tolerantie $\delta$ daalt.
• Exclusieve Bemonstering: Als het aantal steekproeven van een kandidaat-arm achterblijft bij dat van de meest bemonsterde gating arm, bemonstert COF de kandidaat exclusief om "in te halen", waardoor het totale aantal suboptimale steekproeven wordt verminderd.
• BAI-Filter: Tijdens de evaluatie van een kandidaat hanteert COF een filter dat het bemonsteren van gating arms stopt waarvan de Upper Confidence Bounds (UCB) onder de Lower Confidence Bound (LCB) van een andere gating arm vallen. Dit voorkomt het verspillen van steekproeven aan armen die statistisch onwaarschijnlijk de arm met de beste beloning ($i^*$) zijn.

Theoretische Bijdragen

Het artikel biedt een rigoureuze theoretische analyse van MAB-CS, waarbij zowel onder- als bovengrenzen voor regret worden vastgesteld.

1. Instance-afhankelijke Ondergrenzen:

   • De auteurs leiden ondergrenzen af voor het verwachte aantal steekproeven voor goedkope armen (kosten $< c_{a^*}$) en duurdere armen (kosten $> c_{a^*}$).
   • Een nieuwe bijdrage is een gezamenlijke ondergrens voor een verzameling armen. Deze grens weerspiegelt het inzicht dat een arm kan worden gecertificeerd als onhaalbaar als zijn beloning slechter is dan de gesubsidieerde beloning van een willekeurige andere arm, en niet alleen van de arm met de beste beloning $i^*$. Dit generaliseert eerdere grenzen die $i^*$ als een eenheid behandelden.

2. Bovengrenzen voor Regret voor COF:

   • Het artikel stelt instance-afhankelijke bovengrenzen vast voor de verwachte cumulatieve kosten en kwaliteitsregret voor COF.
   • Voor goedkope armen wordt aangetoond dat de grens orde-optimaal is, en overeenkomt met de $O(\log T / \Delta_{Q,k}^2)$-afhankelijkheid die in de ondergrenzen wordt gevonden.
   • Voor duurdere armen hangt de grens af van het maximum van twee termen: één gerelateerd aan het gat tussen de arm en de optimale arm, en een andere gerelateerd aan het gezamenlijke gat dat nodig is om de beste goedkope arm te elimineren. De auteurs merken een lichte discrepantie op tussen de onder- en bovengrenzen voor duurdere armen, wat suggereert dat er ruimte is voor verbetering in de theoretische analyse van de steekproefcomplexiteit.

Experimentele Resultaten

De auteurs valideren COF door middel van uitgebreide simulaties op:

• Real-world datasets: Goodreads (boekbeoordelingen) en MovieLens (filmboordelingen), waarbij genres dienen als bandit-arms.
• Synthetische instanties: Handmatig ontworpen problemen om specifieke algoritmische gedragingen te testen.

Belangrijkste Bevindingen:

• Prestaties: COF presteert consequent beter dan baseline-algoritmen, waaronder ETC-CS (exploratie met vast budget), PE-CS (paarsgewijze eliminatie), UCB-CS en TS-CS.
• Robuustheid: In tegenstelling tot UCB-CS en TS-CS, die kunnen lijden onder lineaire regret door onjuist goedkope, onhaalbare armen op te nemen in hun empirisch haalbare verzamelingen, behoudt COF sub-lineaire regret door de haalbaarheid strikt te testen.
• Gevoeligheid voor Subsidiefactor: Hoewel PE-CS iets beter presteert voor zeer kleine subsidiefactoren ($\alpha$) vanwege strakkere betrouwbaarheidsintervallen in regimes met hoge steekproefaantallen, vermijdt COF de plateauvorming in prestaties die bij PE-CS wordt waargenomen naarmate $\alpha$ toeneemt.
• Ablatiestudies: Experimenten bevestigen dat de functies "combineren van steekproeven" en "exclusieve bemonstering" cruciaal zijn voor de efficiëntie van het algoritme, en de regret aanzienlijk verminderen ten opzichte van varianten zonder deze mechanismen.

Betekenis en Beweringen

Het artikel beweert dat COF een kwalitatief superieur theoretisch raamwerk en empirische prestaties biedt voor kostengevoelige bandit-problemen waarbij de kwaliteitsbeperking relatief is ten opzichte van de onbekende beste beloning.

• Theoretische Vooruitgang: Het werk biedt de eerste instance-afhankelijke ondergrenzen die gezamenlijk de steekproefcomplexiteit van meerdere armen karakteriseren, en biedt dieper inzicht in de structurele uitdagingen van MAB-CS dan eerdere worst-case of single-arm analyses.
• Algoritmische Efficiëntie: Door een dedicated Best Arm Identification (BAI)-fase om $\mu^*$ te vinden voordat de haalbaarheid wordt getest, te vermijden, reduceert COF onnodige bemonstering. De strategie van "combineren van steekproeven" stelt het algoritme in staat onhaalbare armen efficiënter te elimineren dan paarsgewijze vergelijkingsmethoden.
• Praktische Toepasbaarheid: De auteurs benadrukken de relevantie van MAB-CS voor real-world scenario's zoals LLM-modelrouting, waarbij verschillende modellen variërende kosten en onbekende kwaliteit hebben, en het systeem kosten moet afwegen tegen een prestatievloer die relatief is ten opzichte van het beste beschikbare model. Evenzo is het raamwerk van toepassing op de selectie van advertentiemodi en de levering van content voor streamingdiensten.

De auteurs concluderen dat, hoewel COF orde-optimale prestaties bereikt voor goedkope armen en sterke empirische resultaten laat zien, toekomstig werk de kloof tussen de onder- en bovengrenzen voor duurdere armen moet aanpakken en kosten-biased bemonsteringsvarianten moet verkennen voor toepassingen met sterk ongelijke kostenverdelingen.