Parameter-Free Heavy-Tailed Bandits

Technische Samenvatting: Parameter-vrije Heavy-Tailed Bandits

Probleemstelling

Het artikel behandelt het probleem van de stochastische multi-armed bandit (MAB) onder heavy-tailed beloningsverdelingen. In deze setting voldoen beloningen $X$ aan een eindige momentvoorwaarde $\mathbb{E}[|X|^{1+\epsilon}] \leq u$ voor een exponent $\epsilon \in (0, 1]$ en een momentgrens $u < +\infty$. Hoewel robuuste schatters optimale regret-snelheden kunnen bereiken wanneer zowel $\epsilon$ als $u$ bekend zijn, missen real-world toepassingen (bijv. financiën, advertenties) vaak betrouwbare schattingen voor deze parameters.

Het kernprobleem, geponeerd als een open vraag door Genalti en Metelli (COLT 2025), is het bepalen van de best mogelijke regret-garanties voor algoritmen die aanname-vrij zijn met betrekking tot $u$ en $\epsilon$. Specifiek onderzoekt het artikel:

1. De fundamentele trade-offs tussen distributie-vrije (worst-case) en distributie-afhankelijke (instantie-specifieke) regret wanneer $u$ onbekend is.
2. De extra kosten die worden veroorzaakt wanneer $\epsilon$ ook onbekend is.
3. Of een enkel algoritme sublineaire regret kan bereiken dat uniform is over alle $\epsilon \in (0, 1]$.

Methodologie

De auteurs hanteren een tweestaps analytische aanpak:

1. $u$-Adaptiviteit (Vaste $\epsilon$): Zij analyseren eerst het scenario waarin $\epsilon$ bekend is maar $u$ onbekend. Ze definiëren twee regret-snelheden:

   • $\Phi_{free}(K, T)$: Een moment-vrije distributie-vrije regret-bound.
   • $\Phi_{dep}(K, T)$: Een gap-sum-genormaliseerde distributie-afhankelijke regret-bound.
     Door een change-of-measure argument te combineren met specifieke instantie-constructies, leiden zij een ondergrens af op het product van deze rates, waarmee ze een "frontier" van haalbare prestaties vaststellen.

2. Algoritme Ontwerp (AdaR-ETC): Om de afgeleide ondergrenzen te evenaren, stellen de auteurs Adaptive Robust ETC (AdaR-ETC) voor. Dit is een Explore-Then-Commit strategie die gebruikmaakt van:

   • Median-of-Means (MoM) Schatter: Om arm-gemiddelden robuust te schatten zonder kennis van $u$ of $\epsilon$ te vereisen.
   • Geplande Exploratie: Het exploratiebudget $L_T$ wordt afgestemd via parameters $\alpha$ (die de horizon-afhankelijkheid controleert) en $q$ (die de arm-afhankelijkheid controleert). In de $u$-adaptieve setting (waar $\epsilon$ bekend is), worden deze parameters expliciet ingesteld op basis van $\epsilon$. Echter, het algoritme kan volledig parameter-vrij worden gemaakt (onbewust van zowel $u$ als $\epsilon$) door het exploratie-schema te kalibreren naar het eindpunt van de eindige variantie $\epsilon = 1$.

3. $(\epsilon, u)$-Adaptiviteit (Onbekende $\epsilon$): De auteurs breiden de analyse uit naar het geval waarin beide parameters onbekend zijn. Ze kalibreren het AdaR-ETC algoritme naar het eindpunt $\epsilon = 1$ (waarbij $q=1/3$ en $\alpha=2/3$) om een enkele, parameter-vrije strategie te creëren. Vervolgens bewijzen ze een pairwise lower bound om aan te tonen dat deze kalibratie een optimale profiel oplevert onder strategieën die de optimale garantie behouden bij $\epsilon=1$.

Belangrijkste Bijdragen en Resultaten

1. De Trade-off Frontier voor Onbekende $u$
Het artikel bewijst dat voor elke strategie die onbewust is van $u$, er een scherpe trade-off bestaat tussen distributie-vrije en distributie-afhankelijke garanties. Specifiek, voor een vaste $\epsilon$:
$$\Phi_{dep}(K, T) \cdot \Phi_{free}(K, T)^{\frac{1+\epsilon}{\epsilon}} = \Omega\left(T^{\frac{1+\epsilon}{\epsilon}}\right)$$
Dit impliceert dat het verbeteren van de worst-case (distributie-vrije) rate noodzakelijkerwijs de instantie-afhankelijke rate verslechtert. De auteurs karakteriseren de "K-frontier" en "T-frontier", en laten zien dat geen enkel algoritme beide tegelijkertijd kan optimaliseren.

2. Het AdaR-ETC Algoritme
Het voorgestelde AdaR-ETC algoritme bereikt regret-bounds die de theoretische frontier evenaren tot aan de logaritmische factoren. Door parameters $\alpha$ en $q$ af te stemmen, kan het algoritme elk werkpunt op de trade-off frontier selecteren.

• Distributie-vrije bound: $\tilde{O}\left(u^{\frac{1}{1+\epsilon}} K^{\frac{\epsilon}{1+\epsilon}(1-q)} T^{\alpha}\right)$
• Distributie-afhankelijke bound: $\tilde{O}\left(K^{q-1} T^{\beta_\alpha}\right)$
  waarbij $\beta_\alpha = (1-\alpha)(1+\epsilon)/\epsilon$.
  Het "gebalanceerde" punt (gelijke afhankelijkheid van $K$ en $T$) levert een rate op van $\tilde{O}\left(u^{\frac{1}{1+\epsilon}} K^{\frac{\epsilon}{1+2\epsilon}} T^{\frac{1+\epsilon}{1+2\epsilon}}\right)$. Voor het geval van eindige variantie ($\epsilon=1$), resulteert dit in een $\tilde{O}(T^{2/3})$ rate, wat strikt slechter is dan de $\tilde{O}(\sqrt{T})$ rate die haalbaar is wanneer $u$ bekend is, wat de "prijs van adaptiviteit" kwantificeert.

3. Limieten van Simultane $(\epsilon, u)$ Adaptiviteit
Wanneer $\epsilon$ ook onbekend is, stellen de auteurs voor om AdaR-ETC te kalibreren naar $\epsilon=1$.

• Pointwise Sublineariteit: Voor elke vaste $\epsilon > 0$ bereikt het gekalibreerde algoritme sublineaire regret.
• Onmogelijkheid van Uniformiteit: Het artikel bewijst dat geen enkele enkele strategie sublineaire regret kan garanderen die uniform is over alle $\epsilon \in (0, 1]$. Naarmate $\epsilon \to 0$, nadert de exponent van $T$ de waarde 1, wat betekent dat de regret lineair wordt.
• Optimaliteit van Kalibratie: Onder de strategieën die de optimale $\tilde{O}(K^{1/3}T^{2/3})$ garantie behouden bij $\epsilon=1$, wordt aangetoond dat de op $\epsilon=1$ gekalibreerde AdaR-ETC frontier-optimaal is voor alle andere $\epsilon$.

Betekenis en Claims

Het artikel claimt het COLT 2025 openstaande probleem met betrekking tot aanname-vrije heavy-tailed bandits te hebben opgelost. De primaire betekenis ligt in:

• Karakterisering van de Statistische Kosten: Het biedt een scherpe karakterisering van de statistische kosten van het adapteren aan onbekende heavy tails, waarbij wordt aangetoond dat adaptatie aan onbekende schaal ($u$) en orde ($\epsilon$) fundamentele trade-offs introduceert in plaats van slechts constante factoren.
• Frontier vs. Oracle: Het stelt vast dat er geen "oracle curve" is die optimaal is voor alle moment-ordes; in plaats daarvan wordt adaptatie beschreven door een frontier.
• Algoritmische Oplossing: Het biedt een eenvoudig, parameter-vrij algoritme (AdaR-ETC) dat deze optimale trade-offs bereikt zonder voorafgaande kennis van de distributie-eigenschappen van de tails.

De auteurs stellen expliciet dat hun resultaten geen oracle rates terugwinnen zonder aanvullende structurele aannames, wat bevestigt dat de "prijs van adaptiviteit" inherent is aan de heavy-tailed setting. Zij identificeren de limieten van uniforme sublineaire regret en suggereren dat toekomstig werk zich moet richten op het ontwerpen van "anytime" versies van het algoritme en het identificeren van de zwakste aanvullende aannames die nodig zijn om oracle rates te herstellen.