Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality

Technische Samenvatting: Follow-the-Perturbed-Leader voor Gekoppelde Bandits

Probleemstelling
Dit artikel behandelt het probleem van gekoppelde multi-arm bandits (MAB), een setting waarin de leerder in elke ronde $t$ twee verschillende armen selecteert: één arm $i_t$ voor exploitatie (waarbij het verlies $\ell_{t, i_t}$ wordt opgelopen zonder dit te observeren) en één arm $j_t$ voor exploratie (waarbij het verlies $\ell_{t, j_t}$ wordt geobserveerd zonder dit op te lopen). Dit kader modelleert scenario's zoals ultra-wideband communicatiesystemen (het sensen van een kanaal dat verschilt van het transmissiekanaal) en sim-to-real transfer in robotica. Het doel is het minimaliseren van pseudo-regret, gedefinieerd als het verschil tussen de cumulatieve verliezen opgelopen door de exploitatiekeuzes van de leerder en de cumulatieve verliezen van de beste vaste arm in retrospectief.

Het artikel richt zich op Best-of-Both-Worlds (BOBW) garanties, met als doel het bereiken van:

1. Optimale regret van $O(\sqrt{KT})$ in het adversariële regime (waarbij verliezen worden bepaald door een adaptieve adversary).
2. Bijna-optimale, tijdsonafhankelijke regret van $O(K/\Delta_{\min})$ in het stochastisch beperkt adversariële (SCA) regime (waaronder de standaard stochastische setting), waarbij $\Delta_{\min}$ de minimale suboptimaliteitsgap is.

Methodologie
De auteurs stellen een nieuw beleid voor gebaseerd op het Follow-the-Perturbed-Leader (FTPL) kader, specifiek ontworpen om de computationele knelpunten van bestaande BOBW-beleidslijnen in gekoppelde settings te overwinnen.

• Exploitatiestrategie: De leerder selecteert de exploitatiearm $i_t$ door een verstoord cumulatief verliesraming te minimaliseren:
  $$i_t = \arg\min_{i \in [K]} \left\{ \hat{L}_{t,i} - \frac{r_{t,i}}{\eta_t} \right\}$$
  waarbij $\hat{L}_{t,i}$ de geschatte cumulatieve verliezen is, $\eta_t$ de leersnelheid is, en $r_{t,i}$ i.i.d. willekeurige verstoringen zijn die zijn bemonsterd uit een Pareto-verdeling $P_\alpha$ met vormparameter $\alpha > 1$. Dit type verstoring komt overeen met het $\beta$-Tsallis-INF-beleid (met $\alpha = 1/(1-\beta)$), bekend om het bereiken van BOBW-garanties.

• Exploratiestrategie (Belangrijke Innovatie): In standaard FTPL-banditalgoritmen vereist het construeren van een onbevooroordeelde, op belangrijkheid gewogen (IW) verliesraming doorgaans het kennen van de exacte waarschijnlijkheid $w_{t,i}$ van het selecteren van arm $i$. In gekoppelde bandits moet de exploratiekans $p_{t,i}$ worden ingesteld op basis van $w_{t,i}$. FTPL biedt echter geen gesloten uitdrukking voor $w_{t,i}$ (in tegenstelling tot FTRL), en het schatten van de volledige vector via geometrisch resampling is computationeel duur ($O(K^2)$ of hoger).
  Om dit op te lossen, introduceren de auteurs een surrogaatkans $q_{t,i}$ die direct kan worden berekend uit de huidige verliesramingen zonder resampling of convexe optimalisatie:
  $$q_{t,i} = \left( \frac{1}{1 + \eta_t \hat{L}_{t,i}} \wedge \frac{1}{\sigma_{t,i}^{1/\alpha}} \right)^{\frac{\alpha+1}{2}}$$
  waarbij $\sigma_{t,i}$ de rang is van $\hat{L}_{t,i}$ onder alle armen. De exploratiearm $j_t$ wordt vervolgens geselecteerd volgens de genormaliseerde verdeling $p_{t,i} = q_{t,i} / \sum_j q_{t,j}$. Deze aanpak vermijdt de behoefte aan expliciete $w_{t,i}$-waarden, terwijl de theoretische eigenschappen die nodig zijn voor BOBW-garanties worden behouden.

Belangrijkste Bijdragen

1. Eerste FTPL-gebaseerde BOBW-beleid voor Gekoppelde Bandits: Het artikel presenteert het eerste beleid dat BOBW-garanties bereikt in gekoppelde bandits zonder convexe optimalisatieproblemen op te lossen (vereist door FTRL-gebaseerde benaderingen zoals Decoupled-Tsallis-INF) of resampling-procedures toe te passen (doorgaans vereist voor FTPL-kansschatting).
2. Computationele Efficiëntie: Door de berekening van de volledige kansvector te vervangen door de efficiënt berekenbare surrogaat $q_{t,i}$, verlaagt het voorgestelde beleid de computationele complexiteit per stap. Hoewel het sorteren van de verliesramingen $O(K \log K)$ kost, merken de auteurs op dat een geoptimaliseerde implementatie $O(K)$ updates kan bereiken door rangwijzigingen incrementeel bij te houden. Dit staat in contrast met FTRL-beleidslijnen die bij elke stap iteratieve convexe optimalisatie vereisen (bijvoorbeeld Newton-methode).
3. Theoretische Garanties:
   • Adversariële Regime: Het beleid bereikt een regretgrens van $O(\sqrt{KT})$, wat overeenkomt met de bekende ondergrens voor gekoppelde bandits.
   • Stochastisch/SCA Regime: Het beleid bereikt een regretgrens van $O(K/\Delta_{\min})$ (specifiek $O(\sqrt{K/\Delta_{\min}} \sum_{i \neq i^*} 1/\Delta_i + K/\Delta_{\min})$ voor $\alpha=3$), wat bijna optimaal is en een verbetering biedt ten opzichte van de tijd-afhankelijke grenzen van standaard stochastische bandits.

Resultaten

• Theoretisch: Het artikel levert rigoureuze bewijzen (via regret-decompositie in stabiliteits- en straftermen) die aantonen dat de surrogaatkans $q_{t,i}$ voldoende dicht bij de ware exploitatiekans ligt om de nodige regretgrenzen te handhaven.
• Empirisch: Experimenten op synthetische data (zowel in adversariële als stochastische regimes) en een real-world simulatie met behulp van de MovieLens 100K-dataset tonen aan dat het voorgestelde FTPL-beleid:
  • Lagere cumulatieve regret bereikt in vergelijking met bestaande BOBW-beleidslijnen (Decoupled-Tsallis-INF/FTRL en EXP3).
  • Superieure computationele efficiëntie demonstreert. In het adversariële regime draait het voorgestelde beleid aanzienlijk sneller dan FTRL-gebaseerde baselines. Voor $K=64$ werd de runtimeverhouding van FTRL ten opzichte van FTPL waargenomen als ongeveer 1363 keer trager.
  • Schaalbaar is met het aantal armen $K$, en robuustheid behoudt over variërende gap-groottes $\Delta$.

Betekenis en Beweringen
Het artikel beweert dat de primaire bijdrage het overbruggen van de kloof is tussen de theoretische optimaliteit van FTRL-gebaseerde BOBW-beleidslijnen en de computationele efficiëntie van FTPL in de context van gekoppelde bandits. Door de behoefte aan convexe optimalisatie en resampling te elimineren, stelt de voorgestelde methode FTPL in staat om zijn efficiëntievoordelen volledig te realiseren zonder de regretprestaties te offeren. De auteurs suggereren dat de techniek van het gebruik van efficiënt berekenbare surrogaatkansen in plaats van exacte kansvectoren van toepassing kan zijn op andere algoritmische kaders (zoals de Prod-familie) buiten FTPL, wat potentieel leidt tot verbeterde computationele efficiëntie in bredere bandit-settings. Het werk wordt gemotiveerd door praktische toepassingen in communicatiesystemen en robotica, waar computatietijd per stap kritiek is.