Learning What to Recommend: Minimax Optimal Simple Regret in Logistic Bandits

Probleemformulering
Dit artikel onderzoekt stochastische logistische bandieten onder het simple-regret-doel. In deze setting interacteert een leerling over $T$ rondes met een omgeving, kiest acties $A_t$ uit een verzameling $\mathcal{A}$ en observeert Bernoulli-beloningen $X_t$ met gemiddelde $\mu(\phi(A_t)^\top \theta^*)$, waarbij $\mu$ de sigmoidfunctie is, $\phi$ een bekende kenmerkafbeelding is, en $\theta^*$ een onbekende parameter in $\mathbb{R}^d$ is. In tegenstelling tot cumulatieve regret, waarbij het doel is om de som van beloningen tijdens exploratie te maximaliseren, evalueert het simple-regret-doel de leerling uitsluitend op de kwaliteit van een enkele uiteindelijke aanbeveling $\hat{a}$ na $T$ rondes. De regret wordt gedefinieerd als het verschil tussen de verwachte beloning van de optimale actie en de verwachte beloning van de aanbevolen actie.

Een kritieke uitdaging in logistische bandieten is de niet-uniforme informativiteit van acties. Door de sigmoid-link leveren acties in "verzadigde" gebieden (waar het gemiddelde van de beloning dicht bij 0 of 1 ligt) bijna deterministische beloningen op, maar bieden ze weinig informatie over de parameter $\theta^*$. Daarentegen zijn acties nabij de oorsprong (waar de sigmoid het steilst is) zeer informatief, maar kunnen ze lagere directe beloningen opleveren. Dit creëert een geometrie waarbij de acties die het beste zijn voor directe beloning (exploitatie) verschillen van die welke het beste zijn voor het identificeren van de optimale actie (exploratie).

Methodologie
De auteurs stellen twee kromme-bewuste algoritmen voor die zijn ontworpen om gebruik te maken van de lokale geometrie van de sigmoidfunctie:

1. MULOG (Max-Uncertainty-Log): Een deterministisch zuiver-exploratiealgoritme.

   • Mechanisme: MULOG onderhoudt een betrouwbaarheidsset $W_t$ voor $\theta^*$ en construeert een kromme-gewogen ontwerpmatrix $L_t$. De onzekerheidsscore voor een actie $a$ en parameter $\theta$ wordt gedefinieerd als $U(a, \theta, L_t) = \sqrt{\dot{\mu}(\phi(a)^\top \theta)} \|\phi(a)\|_{L_t^{-1}}$, waarbij $\dot{\mu}$ de afgeleide van de sigmoid is (die de lokale kromming vertegenwoordigt).
   • Selectie: In elke ronde selecteert het algoritme het actie-parameterpaar $(A_t, \theta_t)$ dat deze onzekerheidsscore maximaliseert.
   • Beëindiging: Na $T$ rondes retourneert het de actie die gierig is ten opzichte van een parametervector die is bemonsterd uit de uiteindelijke betrouwbaarheidsset.
   • Optimalisatie: Voor eindige actieverzamelingen reduceert de selectiestap tot het oplossen van een eindige collectie convexe optimalisatieproblemen.

2. THATS (Try Hard Thompson Sampling): Een gerandomiseerd, rekenkundig lichter alternatief.

   • Mechanisme: In plaats van te zoeken naar de exacte maximale onzekerheid, bemonstert THATS een richting $\tilde{\theta}_t$ uit een Gaussische verdeling met middelpunt nul en covariantie $L_t^{-1}$.
   • Selectie: Het selecteert de actie die de gerandomiseerde onzekerheidsscore $\sqrt{\dot{\mu}(\phi(a)^\top \bar{\theta}_t)} |\phi(a)^\top \tilde{\theta}_t|$ maximaliseert, waarbij $\bar{\theta}_t$ een beperkte maximum-likelihood-schatting is.
   • Afweging: Deze benadering vermijdt de convexe optimalisatie die door MULOG wordt vereist, maar brengt statistische kosten met zich mee, wat resulteert in een iets losser regret-bound.

Belangrijkste Bijdragen

• Minimax Ondergrens: Het artikel stelt een minimax-ondergrens van de eerste orde vast van de orde $\Omega\left(\frac{d}{\sqrt{\kappa^* T}}\right)$, waarbij $\kappa^*$ de inverse helling van de sigmoid bij de optimale actie is (d.w.z. $\kappa^* = 1/\dot{\mu}(\phi(a^*)^\top \theta^*)$).
  • Distinct Hardheidsmechanisme: In tegenstelling tot ondergrenzen voor cumulatieve regret (bijv. Abeille et al., 2021) die vertrouwen op de kosten van informatie (de leerling dwingend om bijna-optimale armen te spelen), wordt deze ondergrens afgeleid uit een constructie van een "verschoven verzadigde hyperkubus". In deze constructie worden zowel statistische informatie als waardegevoeligheid gecontroleerd door dezelfde lokale kromming in een verzadigd gebied. Dit onthult dat het probleem moeilijk blijft, zelfs met de vrijheid om puur voor informatie te bemonsteren, als de optimale actie in een vlak gebied van de sigmoid ligt.
• Optimale Algoritmen:
  • MULOG bereikt een simple-regret-bovengrens van $\tilde{O}\left(\frac{d}{\sqrt{\kappa^* T}}\right)$, wat overeenkomt met de ondergrens tot op logaritmische factoren. Dit is de eerste directe zuiver-exploratiegarantie voor logistische bandieten die instance-wise minimax-optimaliteit bereikt.
  • THATS bereikt een grens van $\tilde{O}\left(\frac{d^{3/2}}{\sqrt{\kappa^* T}}\right)$. De extra factor $\sqrt{d}$ ontstaat door het gebruik van een geometrie-agnostische gerandomiseerde benadering van de richting van maximale onzekerheid.
• Geometrisch Inzicht: De auteurs tonen aan dat de ergste-case-geometrie (verschoven verzadigde instanties) niet het enige geval is. Ze tonen aan dat "informatieve laag-belonende acties" (probes) kunnen bestaan in de actieverzameling. Deze acties liggen in het gebied met hoge kromming van de sigmoid, waardoor ze aanzienlijke informatie bieden over de optimale richting, ondanks dat ze lage verwachte beloningen hebben.

Resultaten

• Theoretisch: De afgeleide grenzen bevestigen dat de moeilijkheid van logistische simple regret wordt beheerst door de kromming bij de optimale actie. De algoritmen controleren succesvol de onzekerheid in de kromme-gewogen kenmerkrichtingen.
• Empirisch: Experimenten op zowel "moeilijke" geometrieën (verschoven verzadigde hyperkubussen) als "makkelijke" geometrieën (met toegevoegde informatieve probe-armen) ondersteunen de theoretische bevindingen:
  • Op moeilijke instanties presteren MULOG en THATS zoals voorspeld door de minimax-grenzen.
  • Op makkelijke instanties met probe-armen presteren zuiver-exploratiemethoden (MULOG en THATS) aanzienlijk beter dan cumulatieve-regret-baselines (zoals Cumulative Thompson Sampling en online-naar-batch-conversies). De zuiver-exploratiemethoden bemonsteren actief de laag-belonende, hoog-informatieve probes, waardoor het aantal rondes dat nodig is om een lage simple-regret-drempel te bereiken drastisch wordt verminderd.
  • Cumulatieve-regret-methoden slagen er niet in om deze probes effectief te benutten, omdat hun online-naar-batch-conversie de opname van laag-belonende acties in de uiteindelijke aanbevelingsverdeling bestraft.

Betekenis
Het artikel beweert dat zuivere exploratie in logistische bandieten een onderscheidende geometrie bezit ten opzichte van cumulatieve regret-problemen. De primaire bijdrage is het identificeren dat de lokale kromming bij de optimale actie ($\kappa^*$) de bepalende factor is voor de minimax-rate van de eerste orde. Door algoritmen te ontwikkelen die expliciet rekening houden met deze kromming, bereiken de auteurs minimax-optimale prestaties in het ergste geval. Bovendien onderstreept het werk een praktische implicatie: in situaties zoals A/B-testen of het verzamelen van data voor beloningsmodellen, kan het actief zoeken naar "informatieve maar laag-belonende" acties de identificatie van het beste uiteindelijke beleid aanzienlijk versnellen, een gedrag dat standaard cumulatieve-regret-algoritmen structureel niet kunnen vertonen. De resultaten dienen als startpunt voor een scherpere theorie van besluitgerichte exploratie in niet-lineaire bandieten.