🤖 machine learning

Mean-based algorithms: A lower bound and regret

Dit artikel stelt een theoretische ondergrens vast voor de leersnelheid van gemiddelde-gebaseerde algoritmen in bandit-settings met een onbekende horizon, stelt twee nieuwe algoritmen voor die bestaande methoden generaliseren, en demonstreert dat hoewel ze iets langzamer kunnen convergeren, ze een concurrerende prestatie kunnen leveren en snijden met de klasse van no-regret algoritmen.

Oorspronkelijke auteurs: Julius Durmann, Amelie Kleber

Gepubliceerd 2026-06-04

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Julius Durmann, Amelie Kleber

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 "Slimme Koper"

Stel je voor dat je een koper bent die probeert de beste koffiebar te vinden in een nieuwe stad. Je hebt een lijst met 10 zaken, maar je weet niet welke de beste is. Je kunt slechts één zaak per dag bezoeken en de koffie proeven.

Mean-based algoritmen zijn als een specifiek type koper dat een zeer eenvoudige regel volgt: "Als een zaak me in het verleden slechte koffie heeft gegeven, zal ik er bijna nooit meer naartoe gaan."

Ze houden een voortschrijdend gemiddelde bij van hoe goed de koffie van elke zaak is. Als Winkel A een verschrikkelijk gemiddelde heeft, geeft deze koper deze winkel een zeer lage waarschijnlijkheid om bezocht te worden. Als Winkel B een geweldig gemiddelde heeft, bezoekt deze koper die vaak.

Het artikel stelt drie hoofdvragen over dit type koper:

Hoe snel kunnen ze leren?
Is er een limiet aan hoe snel ze kunnen leren?
Zijn ze "slim" genoeg om grote fouten te vermijden (regret/spijt)?

1. Het Probleem: De "Onbekende Horizon" en "Blinde Proeverijen"

In veel informatica-problemen weet het algoritme precies hoeveel dagen het de tijd heeft om te winkelen (de "tijdshorizon"). Maar in het echte leven weet je niet of je een week of een jaar in deze stad zult zijn. Dit wordt een onbekende horizon genoemd.

Ook in dit specifieke scenario krijgt de koper alleen de kans om de koffie te proeven die hij zelf heeft besteld (bandit feedback). Hij krijgt niet te zien hoe de koffie bij de andere 9 zaken die dag geproefd zou hebben. Dit maakt leren moeilijker omdat men moet gissen.

2. De "Snelheidslimiet" (De Lower Bound)

De auteurs ontdekten een fundamentele snelheidslimiet voor deze kopers.

Beschouw de "leersnelheid" ( $\gamma_t$ ) als de geduldsdrempel van de koper.

Hoge Geduld (Hoge Drempel): De koper is erg kieskeurig. Ze stoppen pas met het bezoeken van een zaak als de koffie echt, echt slecht is vergeleken met de rest. Ze blijven nog lang nieuwe zaken verkennen.
Laag Geduld (Lage Drempel): De koper is ongeduldig. Ze stoppen met het bezoeken van een zaak, zelfs als deze slechts iets minder goed is dan de beste.

De Ontdekking: Het artikel bewijst dat je niet te ongeduldig mag zijn.
Als de koper zijn drempel te laag instelt (om te snel te willen leren), zal hij te vroeg stoppen met verkennen. Hij kan een zaak die eigenlijk goed was, opgeven, simpelweg omdat hij door toeval een paar slechte koppen koffie kreeg.

De auteurs vonden een wiskundige "vloer" voor dit geduld. Het is alsover zeggen: "Hoe slim je ook bent, je kunt niet sneller stoppen met het verkennen van nieuwe koffiezaken dan een specifieke snelheid, anders zul je definitief een fout maken."

De Analogie: Stel je voor dat je probeert de beste route naar je werk te vinden. Als je te snel stopt met het proberen van nieuwe routes omdat één route iets langzamer was, mis je misschien de perfecte route die alleen op regenachtige dagen verschijnt. Het artikel bewoudt dat er een minimaal bedrag aan "ronddwalen" is dat je moet doen om zeker te weten dat je de beste optie niet mist.

3. Twee Nieuwe "Kopers" (De Algoritmen)

De auteurs creëerden twee nieuwe versies van deze "mean-based" koper die ook werken wanneer je niet weet hoe lang je in de stad zult zijn en alleen je eigen koffie kunt proeven.

De "Iets Greedier" Koper: Een variatie op de klassieke "epsilon-greedy" strategie. Hij houdt zich voornamelijk aan de beste bekende zaak, maar probeert af en toe een nieuwe om er zeker van te zijn.
De "Gewogen" Koper: Een variatie op het beroemde "Exp3" algoritme. Hij geeft meer gewicht aan zaken met goede gemiddelden uit het verleden, maar behoudt nog steeds een kleine kans om anderen te proberen.

Het Resultaat: Toen ze deze nieuwe kopers testten tegenover standaardmodellen, ontdekten ze dat hoewel de "mean-based" kopers in het begin iets langzamer waren, ze uiteindelijk bijkwamen en net zo goed presteerden. Ze waren niet zo traag als eerdere studies suggereerden.

4. De "Regret" Vraag: Zijn Ze Exploitabel?

In de economie is er een angst dat "mean-based" kopers exploiteerbaar zijn.

Het Scenario: Een slimme koffiebarhouder (de "Principal") weet dat de koper de regel "slecht gemiddelde = niet bezoeken" volgt. De eigenaar kan de koper op dag één een gratis, fantastische koffie geven om hem te misleiden te laten denken dat die zaak de beste is. Daarna verhoogt de eigenaar de prijzen of verlaagt de kwaliteit, en de koper blijft terugkomen omdat hun "gemiddelde" nog steeds hoog is.

Het artikel onderzoekt of deze kopers ook last hebben van Regret (foute keuzes maken die hen geld kosten).

De Bevinding: "Mean-based" zijn betekent niet automatisch dat je last zult hebben van regret.
De Twist: De auteurs laten zien dat het mogelijk is om een koper te ontwerpen die zowel "mean-based" is (volgt de eenvoudige regel) als "no-regret" (niet in de val loopt).

Het is alsover zeggen: "Je kunt een eenvoudige koper zijn die slechte koffie vermijdt, maar als je je regels correct afstemt, kun je ook slim genoeg zijn om niet te worden opgelicht door een slimme koffiebarhouder."

Samenvatting van de Belangrijkste Punten

De Regel: Mean-based algoritmen zijn eenvoudig: "Vermijd dingen die gemiddeld slecht zijn geweest."
De Limiet: Er is een harde wiskundige limiet aan hoe snel deze algoritmen kunnen leren. Als ze proberen sneller te leren dan deze limiet, zullen ze falen omdat ze te vroeg stoppen met verkennen.
De Prestatie: De nieuwe algoritmen die in het artikel worden voorgesteld, werken goed. Ze zijn competitief met andere beroemde algoritmen, ook al zijn ze in het begin iets langzamer.
De Veiligheid: Deze algoritmen kunnen zo worden ontworpen dat ze "veilig" zijn (no-regret), wat betekent dat ze niet noodzakelijkerwijs makkelijk te misleiden zijn, in tegenstelling tot wat sommige eerdere studies suggereerden.

Kortom, het artikel vertelt ons dat hoewel deze eenvoudige "vermijd de slechte zaken" algoritmen een snelheidslimiet hebben, ze nog steeds krachtige, betrouwbare instrumenten zijn om te leren in onzekere omgevingen.

Technische Samenvatting: Gemiddelde-gebaseerde Algoritmen: Een Ondergrens en Regret

Probleemstelling

Het artikel onderzoekt gemiddelde-gebaseerde algoritmen binnen de context van online leren, specifiek gericht op de multi-armed bandit (MAB) setting met bandit-feedback en een onbekende tijdshorizon.

Gemiddelde-gebaseerde algoritmen worden gedefinieerd door het principe dat een agent acties met lage gemiddelde historische beloningen in de toekomst met een lage waarschijnlijkheid moet selecteren. Hoewel recente literatuur suggereert dat deze algoritmen gunstig convergeren naar serieel niet-gedomineerde acties (wat de Nash-evenwichten in economische spellen benadert), wijzen empirische studies erop dat ze lijden onder een trage convergentie vergeleken met gevestigde algoritmen in scenario's met bandit-feedback. Bovendien is er een spanning tussen de "exploiteerbaarheid" van deze algoritmen in principal-agent-spellen en hun theoretische convergentiegaranties.

De specifieke uitdagingen die worden aangepakt zijn:

Het definiëren van gemiddelde-gebaseerde algoritmen voor de onbekende-horizon setting (waarbij het totale aantal rondes $T$ niet vooraf bekend is).
Het bepalen van de theoretische limieten op de definiërende snelheidsreeks van het algoritme, $\gamma_t$ , die de drempel controleert voor het vermijden van "gedomineerde" acties.
Het verhelderen van de relatie tussen gemiddelde-gebaseerde algoritmen en no-external-regret algoritmen, in het bijzonder of een algoritme beide eigenschappen tegelijkertijd kan bezitten onder bandit-feedback.

Methodologie

1. Definities en Preliminairen

De auteurs formaliseren twee definities van gemiddelde-gebaseerde algoritmen:

$\gamma_t$ -gemiddelde-gebaseerd: Gebaseerd op huidige gemiddelde beloningen $\alpha_t(a)$ . Als $\alpha_t(a') - \alpha_t(a) > \gamma_t$ , dan is de kans om in stap $t+1$ actie $a$ te kiezen hoogstens $\gamma_t$ .
Predictieve $\gamma_t$ -gemiddelde-gebaseerd: Gebaseerd op de gemiddelde beloningen van de volgende stap $\alpha_{t+1}$ .

Het artikel stelt vast dat deze definities wederzijds converteerbaar zijn en richt zich op de niet-predictieve variant voor de bandit-setting.

2. Voorgestelde Algoritmen

De auteurs stellen twee algoritmen voor die zijn aangepast voor bandit-feedback en onbekende horizontons:

Gegeneraliseerde $\epsilon$ -Greedy: Een variant waarbij acties als "gedomineerd" worden beschouwd als hun geschatte cumulatieve beloning aanzienlijk lager is dan die van andere acties. Het algoritme wijst een kleine waarschijnlijkheid $\epsilon_t$ toe aan gedomineerde acties en verdeelt de resterende waarschijnlijkheid over de niet-gedomineerde acties.
Mean-Based Exp3: Een variant van het Exp3-algoritme (Exponential-weight algorithm for Exploration and Exploitation). Het maakt gebruik van multiplicatieve gewichten gebaseerd op geschatte cumulatieve beloningen, met een exploratiecomponent $\epsilon_t$ om voldoende bemonstering te garanderen.

Beide algoritmen maken gebruik van belang-gewogen estimators om het gebrek aan volledige feedback op te vangen.

3. Afleiding van de Theoretische Ondergrens

Om de fundamentele limiet te bepalen van hoe snel deze algoritmen kunnen leren, leiden de auteurs een ondergrens af voor de snelheidsreeks $\gamma_t$ .

Adversariële Constructie: Ze construeren twee specifieke adversariële omgevingen ( $x'_t$ en $x''_t$ ) die het exploratie-exploitatie dilemma uitbuiten. In deze omgevingen moet een algoritme onderscheid maken tussen twee acties die aanvankelijk op elkaar lijken maar later uiteenlopen.
Onderscheidbaarheidsargument: Vanwege de bandit-feedback, als het algoritme een specifieke actie te zelden speelt (om een kleine $\gamma_t$ te voldoen), kan het niet onderscheid maken tussen de twee omgevingen.
Afleiding van de Ongelijkheid: Door de kans te analyseren dat een gedomineerde actie wordt gekozen in deze geconstrueerde omgevingen, leiden ze een noodzakelijke ongelijkheid af: $\sum_{t=t_1}^{t_c-1} \gamma_t + k \cdot \gamma_{t_c} \geq 1$ .
Asymptotische Analyse: Ze benaderen deze som met integralen om aan te tonen dat elke snelheidsreeks die sneller afneemt dan $O(1/\sqrt{t})$ (specifiek, elke reeks waar $\gamma_t \in o(1/\sqrt{t})$ ) de voorwaarde schendt die vereist is om een gemiddelde-gebaseerd algoritme te zijn in de bandit-setting.

4. Regret-Analyse

De auteurs analyseren de intersectie van gemiddelde-gebaseerde algoritmen en no-external-regret algoritmen. Ze demonstreren dat hoewel gemiddelde-gebaseerde algoritmen niet automatisch geen-regret garanderen (en in specifieke adversariële opstellingen met zeer kleine $\gamma_t$ lineaire regret kunnen lijden), er configuraties bestaan (met name bepaalde parametriseringen van Exp3) die zowel de gemiddelde-gebaseerde eigenschap als de no-external-regret eigenschap bezitten.

Belangrijkste Bijdragen

Eerste Ondergrens op $\gamma_t$ : Het artikel biedt de eerste formele ondergrens voor de snelheidsreeks $\gamma_t$ van gemiddelde-gebaseerde algoritmen in de bandit-feedback setting. Het stelt vast dat $\gamma_t$ niet sneller kan afnemen dan $O(1/\sqrt{t})$ . Specifiek is elke reeks $\gamma_t \in o(1/\sqrt{t})$ ongeldig voor gemiddelde-gebaseerde algoritmen in deze setting.
Unknown-Horizon Algoritmen: De auteurs stellen twee concrete gemiddelde-gebaseerde algoritmen voor (gegeneraliseerde $\epsilon$ -greedy en mean-based Exp3) die effectief functioneren zonder voorafgaande kennis van de tijdshorizon $T$ .
Reconciliatie van Definities: Het werk verheldert de relatie tussen predictieve en niet-predictieve gemiddelde-gebaseerde definities door aan te tonen dat ze converteerbaar zijn.
Regret-Mean-Based Overlap: Het artikel bewijst dat de verzameling gemiddelde-gebaseerde algoritmen en de verzameling no-external-regret algoritmen niet disjunct zijn. Het construeert een specifieke Exp3-variant die zowel gemiddelde-gebaseerd als no-regret is.
Empirische Validatie: Door middel van numerieke experimenten laten de auteurs zien dat hoewel gemiddelde-gebaseerde algoritmen mogelijk iets langzamer convergeren dan hun standaard tegenhangers, ze een concurrerende prestatie kunnen leveren in zowel stochastische MAB-settings als economische spellen (Bertrand oligopolie).

Resultaten

Theoretische Resultaten

Ondergrens: De reeks $\gamma_t = \frac{1}{2\sqrt{t}+1}$ wordt geïdentificeerd als een kritische drempel. Elke reeks die strikt sneller afneemt dan deze (bijv. $\gamma_t = 1/t^{0.51}$ of $\gamma_t = 1/t$ ) wordt bewezen ongeldig te zijn voor gemiddelde-gebaseerde algoritmen onder bandit-feedback.
Regret: Het artikel bevestigt dat gemiddelde-gebaseerde algoritmen niet inherent "exploiteerbaar" zijn op een manier die no-regret garanties uitsluit. Er bestaan algoritmen die zowel gemiddelde-gebaseerd als no-regret zijn.

Empirische Resultaten

Stochastische MAB: In een 10-arm bandit experiment liet de voorgestelde mean-based Exp3 (met $\alpha=1/2$ ) een iets tragere convergentie naar de optimale actie zien vergeleken met een standaard Exp3-configuratie, maar het verschil was marginaal. De $\epsilon$ -greedy varianten vertoonden prestaties die afhankelijk waren van de exploratiesnelheid.
Bertrand Oligopolie: In een herhaald prijzen-spel convergeerde het mean-based Exp3 algoritme aanzienlijk sneller naar het Nash-evenwicht dan eerder waargenomen in soortgelijke literatuur (bijv. Bichler et al., 2025). De mean-based $\epsilon$ -greedy algoritmen waren trager, wat werd toegeschreven aan excessieve exploratie wanneer de dominantiedrempel hoog was.

Betekenis en Claims

Het artikel claimt een fundamentele limiet te bieden op de prestaties van gemiddelde-gebaseerde algoritmen. De afgeleide ondergrens op $\gamma_t$ verklaart waarom deze algoritmen vaak traag leren: om aan de gemiddelde-gebaseerde voorwaarde te voldoen (het vermijden van gedomineerde acties) zonder volledige feedback, moet het algoritme een bepaald niveau van exploratie behouden. Als de exploratiesnelheid te snel daalt (d.w.z. $\gamma_t$ wordt te klein), kan het algoritme niet onderscheid maken tussen omgevingen en wordt het gedwongen om gedomineerde acties te spelen, wat de gemiddelde-gebaseerde definitie schendt.

De auteurs positioneren hun werk als een noodzakelijke stap in het verzoenen van de "exploiteerbaarheid"-zorgen in principal-agent-spellen met de convergentiegaranties in de speltheorie. Door aan te tonen dat gemiddelde-gebaseerd en no-regret eigenschappen samen kunnen bestaan, suggereren ze dat gemiddelde-gebaseerde algoritmen een levensvatbaar alternatief zijn voor economische leerscenario's, mits de snelheid $\gamma_t$ zorgvuldig wordt gekozen om de afgeleide ondergrens te respecteren.

Het artikel concludeert dat hoewel gemiddelde-gebaseerde algoritmen niet universeel sneller zijn dan standaard no-regret algoritmen, ze een onderscheidende klasse van leeringsdynamica bieden die concurrerend kan zijn, met name in settings waar convergentie naar serieel niet-gedomineerde strategieën het primaire doel is. Het werk laat de vraag open of er een algoritme kan worden geconstrueerd dat exact de theoretische ondergrens $\gamma_t \approx 1/\sqrt{t}$ kan evenaren terwijl het een optimale regret behoudt.