Pure Exploration Beyond Reward Feedback: The Role of Post-Action Context

Technische Samenvatting: Pure Exploratie Buiten Beloningsfeedback: De Rol van Context na Actie

Probleemformulering
Dit artikel introduceert een nieuwe variant van het Best Arm Identification (BAI)-probleem binnen de vaste-zekerheidsinstelling van stochastische multi-armed bandits (MAB). In deze instelling, genaamd "BAI met context na actie", kiest de leerder een actie (arm) $X$ en observeert niet alleen de beloning $Y$, maar ook een tussenliggende context $Z$ na de actie. De context $Z$ wordt gegenereerd als gevolg van de gekozen actie, wat dit probleem onderscheidt van standaard contextuele bandits waarbij de context voorafgaat aan de actie.

De auteurs analyseren twee structurele regimes die worden gedefinieerd door het causale verband tussen actie, context en beloning:

1. Scheidende Context: De beloning $Y$ hangt uitsluitend af van de context $Z$, waardoor $X$ en $Y$ conditioneel onafhankelijk zijn gegeven $Z$ ($P(Y|X, Z) = P(Y|Z)$). In dit geval wordt de verdeling van de beloning volledig bepaald door de waargenomen context.
2. Niet-scheidende Context: De beloning $Y$ hangt af van zowel de actie $X$ als de context $Z$ ($P(Y|X, Z) \neq P(Y|Z)$). Hier biedt de context aanvullende informatie, maar is deze geen toereikende statistiek voor de beloning.

Het doel is om de arm met de hoogste verwachte beloning te identificeren met een foutkans van maximaal $\delta$, terwijl de steekproefcomplexiteit (het aantal benodigde rondes) wordt geminimaliseerd.

Methodologie en Algoritmen
Het artikel leidt instance-afhankelijke ondergrenzen voor de steekproefcomplexiteit af voor beide instellingen en stelt algoritmen voor die deze grenzen asymptotisch bereiken.

• Scheidende Instelling:

  • Ondergrens: De auteurs leiden een ondergrens af die afhankelijk is van de frequenties van waargenomen contexten in plaats van de frequenties van getrokken armen. Dit komt omdat, in de scheidende instelling, elke observatie van een specifieke context $Z=j$ informatie verschaft over het gemiddelde van de beloning van die context, ongeacht welke arm deze heeft gegenereerd.
  • Algoritme (STS): Het voorgestelde "Separator Track and Stop" (STS)-algoritme maakt gebruik van een nieuwe bemonsteringsregel genaamd G-tracking. In tegenstelling tot traditionele methoden die de optimale frequenties van het trekken van armen volgen, volgt G-tracking de optimale frequenties van het observeren van contexten. Het behandelt het probleem als een actief off-policy leertaak waarbij de leerder een verdeling over armen kiest om een doelverdeling over contexten te bereiken. Het algoritme lost een convex optimalisatieprobleem op om de optimale contextfrequentie te vinden en gebruikt een geometrische projectie om de volgende armverdeling te selecteren, zodat de waargenomen contextfrequentie convergeert naar het optimale doel.

• Niet-scheidende Instelling:

  • Ondergrens: De afgeleide ondergrens houdt rekening met de gezamenlijke verdeling van acties en contexten.
  • Algoritme (NSTS): Het "Non-Separator Track and Stop" (NSTS)-algoritme breidt het klassieke Track-and-Stop-kader uit. Het maakt gebruik van D-tracking om de optimale proporties van het trekken van specifieke armen te schatten en te volgen, waarbij het gebruik maakt van de gezamenlijke informatie van acties en hun resulterende contexten om de schattingen van de gemiddelde beloningen te verfijnen.

Belangrijkste Bijdragen

1. Probleemdefinitie: Formalisering van BAI met context na actie, met onderscheid tussen scheidende en niet-scheidende structurele regimes.
2. Theoretische Grenzen: Afleiding van instance-afhankelijke ondergrenzen voor de steekproefcomplexiteit voor beide regimes. De scheidende grens blijkt strikt strakker te zijn dan grenzen die zijn afgeleid door de context te negeren.
3. Algoritmedesign:
   • Introductie van G-tracking, een bemonsteringsregel die de frequenties van contextobservatie direct optimaliseert in de scheidende instelling, gebruikmakend van de geometrie van de ruimtelijke context.
   • Uitbreiding van het Track-and-Stop-kader naar de niet-scheidende instelling (NSTS).
4. Suboptimaliteitsanalyse: Theoretisch en empirisch bewijs dat algoritmen die context na actie negeren (zoals standaard Track-and-Stop) strikt suboptimaal zijn. In de scheidende instelling kan het negeren van context leiden tot willekeurig grote toenames in steekproefcomplexiteit, zelfs wanneer de beloningskloven klein zijn, omdat de conditionele onafhankelijkheidsstructuur niet wordt benut.
5. Reductieanalyse: Het artikel analyseert de reductie van het scheidende probleem naar lineaire bandits, en toont aan dat dergelijke reducties de ondergrens voor de steekproefcomplexiteit verhogen in vergelijking met de voorgestelde directe aanpak.

Resultaten

• Theoretisch: De voorgestelde algoritmen (STS en NSTS) zijn bewezen $\delta$-correct en bereiken asymptotische optimaliteit, waarbij ze de afgeleide ondergrenzen benaderen naarmate $\delta \to 0$.
• Empirisch: Experimenten met synthetische data en real-world data (KuaiSAR aanbevelingslogboeken) tonen aanzienlijke prestatiewinsten aan.
  • In de scheidende instelling presteert STS aanzienlijk beter dan baselines (Track-and-Stop en Lazy Track-and-Stop), die vaak falen om binnen redelijke tijdsbestekken te stoppen.
  • In de niet-scheidende instelling reduceert NSTS het aantal benodigde steekproeven aanzienlijk in vergelijking met Track-and-Stop, dat contextinformatie negeert.
  • Tracking-plots bevestigen dat STS convergeert naar de optimale contextfrequentie, terwijl baselines falen om uit te lijnen met de optimale strategie.

Betekenis en Beweringen
Het artikel stelt dat het benutten van context na actie de optimale strategie voor pure exploratie fundamenteel verandert. De auteurs benadrukken dat in scenario's waar tussenliggende observaties (mediatoren) beschikbaar zijn, het negeren ervan leidt tot aanzienlijke inefficiëntie. Specifiek in de scheidende instelling maakt het vermogen om informatie te poolen over verschillende armen die dezelfde context genereren, een veel snellere identificatie van de beste arm mogelijk. Het werk benadrukt dat standaard BAI-algoritmen niet alleen suboptimaal zijn, maar in deze gestructureerde omgevingen willekeurig inefficiënt kunnen zijn. Het artikel concludeert dat toekomstig werk het geval kan aanpakken waarbij de matrix van contextkansen onbekend is, waarbij wordt opgemerkt dat dit niet-convexe uitdagingen introduceert die het ontwerpen van efficiënte algoritmen moeilijk maken.