Technische Samenvatting: Sequentiële Off-Policy Learning met Logaritmische Glading

Probleemstelling

Off-policy learning maakt het trainen van beleidsregels mogelijk op basis van gelogde interactiedata die zijn gegenereerd door een gedragsbeleid. Hoewel de theoretische fundamenten van off-policy learning goed zijn vastgesteld in de batch-instelling (waarbij een enkel beleid wordt geleerd uit een statische dataset gegenereerd door één gedragsbeleid), werken realistische systemen anders. In de praktijk worden beleidsregels herhaaldelijk bijgewerkt en opnieuw ingezet op een sequentiële manier: een beleid wordt getraind op alle historische data, ingezet om nieuwe interacties te genereren, en vervolgens opnieuw getraind op het uitgebreide dataset voor de volgende iteratie.

Ondanks de alomtegenwoordigheid van dit sequentiële paradigma in toepassingen zoals aanbevelingssystemen en advertentieplaatsing, blijft het grotendeels theoretisch onontgonnen. Bestaande sequentiële benaderingen vertrouwen vaak op sterke aannames, zoals uniforme dekking van de actieruimte of onrealistische dataverzamelingsstrategieën (bijvoorbeeld exponentieel groeiende batchgroottes). Bovendien zijn huidige state-of-the-art offline algoritmen, die gebruikmaken van het pessimisme-principe en PAC-Bayesiaanse kaders, niet succesvol zijn uitgebreid naar de sequentiële instelling met strikte convergentiegaranties. Dit artikel adresseert de kloof tussen praktische sequentiële inzet en theoretische garanties, met als doel sequentiële off-policy learning-algoritmen te ontwikkelen die zowel theoretisch onderbouwd als empirisch effectief zijn.

Methodologie

De auteurs stellen een kader voor op basis van Contextuele Bandieten, waarbij een agent over tijdstappen $k \geq 0$ interacteert met een datastroom. Bij elke stap wordt een nieuw gedragsbeleid $\pi_k$ ingezet om een batch data $S_k$ te verzamelen, en de agent update zijn beleid met behulp van de cumulatieve geschiedenis $S_{0:k}$.

De methodologie rust op twee hoofdalgorithmische bijdragen, die beide gebruikmaken van Online PAC-Bayesiaanse leertools en Logaritmische Glading (LS)-schatters:

1. Sequentiële Logaritmische Glading (Algoritme 1)

De eerste bijdrage breidt de offline Logaritmische Glading-schatter (geïntroduceerd door Sakhi et al., 2024) uit naar de sequentiële instelling.

• Schatter: Het algoritme gebruikt de standaard LS-regularisator $h_{LS}(p, q, c) = -\frac{p}{\lambda} \log(1 - \frac{\lambda c}{q})$.
• Mechanisme: Bij elke stap $k$ minimaliseert het algoritme een PAC-Bayesiaanse bovengrens op het risico, waarbij de empirische LS-risico over alle geaccumuleerde data $S_{0:k}$ wordt gecombineerd met een KL-divergentie-term ten opzichte van een prior $P$.
• Theoretische Garantie: Stelling 3.2 stelt een generalisatiegrens vast voor de sequentiële output $\pi_{k+1}$. De convergentiesnelheid wordt aangetoond als $O(1/\sqrt{N_k})$, waarbij $N_k$ het totale aantal steekproeven is. Dit komt overeen met de optimale snelheid van de batch-instelling, maar is van toepassing op de sequentiële accumulatie van data.
• Beperking: De auteurs identificeren dat de pseudo-variatie-term in de convergentiegrens niet verdwijnt, zelfs niet als het gedragsbeleid het optimale beleid benadert, wat leidt tot een convergentiesnelheid die niet versnelt tot boven $O(1/\sqrt{N_k})$.

2. Sequentiële Geadjusteerde Logaritmische Glading (Algoritme 2)

Om de trage convergentie van Algoritme 1 te overwinnen, introduceren de auteurs een nieuwe Geadjusteerde Logaritmische Glading (AdjLS)-schatter.

• Schatter: Een nieuwe regularisator wordt gedefinieerd: $h_{adj}(p, q, c) = -\frac{p}{\lambda} \log(1 - \frac{\lambda c}{q(1+\lambda c)})$. Deze aanpassing wijzigt het prestatiedoel om het verschil tussen het risico van het huidige beleid en een gewogen gemiddelde van eerdere risico's te controleren.
• Mechanisme: Algoritme 2 minimaliseert de aangepaste risicoschatter over de cumulatieve data.
• Theoretische Garantie: Stelling 4.4 bewijst dat onder milde aannames (specifiek, dat de optimale acties worden gedekt door de beleidsklasse en dat het probleem een zekere mate van scheidbaarheid heeft, gekwantificeerd door $\Delta_u > 0$), Algoritme 2 een versnelde convergentiesnelheid bereikt van $O(1/N_k^\alpha)$ voor elke $\alpha \in [0.5, 1)$.
• Kerninzicht: In tegenstelling tot de standaard LS-schatter, verdwijnt de foutterm $L(\pi^*, \pi_j)$ van de aangepaste schatter naarmate het gedragsbeleid $\pi_j$ het optimale beleid $\pi^*$ benadert, waardoor snellere convergentie mogelijk wordt.

Belangrijkste Bijdragen

1. Eerste Sequentiële PAC-Bayes Algoritmen: Het artikel presenteert de eerste off-policy PAC-Bayesiaanse algoritmen die specifiek zijn ontworpen voor de sequentiële instelling, en biedt theoretische convergentiegaranties die interpoleren tussen volledig batch- en volledig online regimes.
2. Versnelde Convergentie door Aanpassing: De auteurs identificeren een fundamentele beperking bij het sequentieel toepassen van standaard offline schatters en stellen een principiële aanpassing (AdjLS) voor die onder redelijke aannames bewezen versnelde convergentiesnelheden oplevert.
3. Verlichte Aannames: De theoretische analyse vereist slechts dat de beleidsklasse de optimale acties dekt (Aanname 3.4), wat strikt zwakker is dan de uniforme dekking-aannames die nodig zijn door eerdere sequentiële werken (bijvoorbeeld Zenati et al., 2023).
4. Generalisatie naar Non-IID Contexten: Het kader blijkt aanpasbaar te zijn aan niet-stationaire omgevingen waar contextverdelingen in de loop van de tijd evolueren, waardoor de i.i.d.-aanname voor contexten wordt verlicht.

Empirische Resultaten

De auteurs evalueren hun methoden op standaard multiclass datasets (MNIST, FashionMNIST, EMNIST, CIFAR100) die zijn omgezet in contextuele bandietproblemen.

• Sequentieel versus Batch: Experimenten tonen aan dat het verhogen van het aantal tussentijdse beleidsupdates ($k$) de prestaties van het uiteindelijke beleid consistent verbetert in vergelijking met één enkele batch-update ($k=1$). Dit valideert het voordeel van het sequentiële kader.
• Algoritme Vergelijking:
  • SeqAdjLS (Algoritme 2) presteert consistent beter dan SeqLS (Algoritme 1), wat het theoretische voordeel van de aangepaste schatter bevestigt.
  • Beide voorgestelde methoden presteren aanzienlijk beter dan SCRM (Sequentiële Counterfactual Risk Minimization, Zenati et al., 2023). De auteurs merken op dat SCRM de neiging heeft om te conservatief te zijn, vooral in vroege rondes met kleine batchgroottes, en vertrouwt op onrealistische dataverzamelingsstrategieën (exponentieel groeiende batches) die historische data verwerpen.
• Invloed van Initieel Beleid: De sequentiële benadering toont aanzienlijke winsten wanneer het initiële gedragsbeleid ver van optimaal ligt, met name in hoogdimensionale actieruimtes (bijvoorbeeld CIFAR100 met 100 acties).

Betekenis en Beweringen

Het artikel claimt de theoretische kloof tussen praktische sequentiële off-policy learning en strikte garanties te dichten. Door online PAC-Bayes-technieken te combineren met een nieuwe logaritmische glading-schatter, bieden de auteurs algoritmen die:

• State-of-the-art offline benaderingen generaliseren (door hun prestaties in de batchlimiet te evenaren).
• Versnellen het leren in sequentiële instellingen door gebruik te maken van de progressieve verfijning van het gedragsbeleid.
• Onrealistische aannames (zoals uniforme dekking) vermijden die de toepasbaarheid van bestaande sequentiële methoden belemmeren.

De auteurs benadrukken dat hoewel hun theoretische analyse rust op het feit dat de beleidsklasse optimale acties dekt, dit een significante verlichting is ten opzichte van eerdere werken. Zij concluderen dat de combinatie van online PAC-Bayes en sequentiële contextuele bandieten een veelbelovende richting biedt voor robuust, efficiënt leren in dynamische realistische systemen.