Technische Samenvatting: Leren Wanneer te Stoppen: Selectief Imitatieleren onder Arbitraire Dynamische Verschuivingen

1. Probleemformulering

Het artikel adresseert de uitdaging van Imitatieleren (IL) in situaties waar de overgangsdynamiek van de testomgeving willekeurig afwijkt van die van de trainingsomgeving. In klassiek offline IL wordt een leerling, getraind op expertdemonstraties uit een bronomgeving $M$, ingezet in een doelen omgeving $N$. Als de draagvlakken van toestanden in $M$ en $N$ disjunct zijn of significant verschuiven, kan een standaardbeleid willekeurig slecht presteren omdat het niet kan herkennen wanneer zijn trainingsdata geen betrouwbare richtlijnen meer biedt.

De auteurs stellen een kader voor Selectief Imitatieleren, waarbij de leerling de optie krijgt om af te zien (de uitvoering te staken) halverwege een traject wanneer het detecteert dat de huidige staat buiten het betrouwbare draagvlak van zijn trainingsdata valt. Het doel is een selectief beleid $(\pi, \tau)$ te leren, bestaande uit een basisbeleid $\pi$ en een stoptijd $\tau$, dat voldoet aan twee concurrerende doelstellingen:

1. Volledigheid: Het beleid moet zelden afzien in de trainingsomgeving $M$ (d.w.z. $\alpha_M(\pi, \tau) \le \epsilon$).
2. Geldigheid: Het beleid moet lage regret oplopen in de testomgeving $N$ voordat het stopt (d.w.z. $Regret_N(\pi, \tau) \le \epsilon$).

De setting veronderstelt toegang tot:

• Gelabelde trainingsrollouts: State-action paren $(s, a)$ van de expert $\pi^\star$ in omgeving $M$.
• Ongelabelde testrollouts: Alleen-toestand trajecten van de expert $\pi^\star$ in omgeving $N$. Deze asymmetrie modelleert real-world scenario's waar actietelemetrie kostbaar of eigendom is (bijvoorbeeld dashcambeelden van autonoom rijden zonder stuurcommando's).

2. Methodologie: SeqRejectron

Het kernalgoritme, SeqRejectron, generaliseert het Rejectron-algoritme uit selectieve classificatie (Goldwasser et al., 2020) naar sequentiële besluitvorming. Het kerninzicht is dat in plaats van onafhankelijke beslissingen op elk tijdstip te nemen (wat leidt tot een steekproefcomplexiteit afhankelijk van de horizon), het algoritme volledige traject-prefixen certificeert met behulp van een schaarse set van validator-beleiden.

Kernmechanisme

1. Basisbeleid: De leerling selecteert een basisbeleid $\pi_0$ dat consistent is met de trainingsdata (bijvoorbeeld Maximum Likelihood Schatting).
2. Validatorsets: Het algoritme construeert een kleine set "validator"-beleiden $\Phi$ getrokken uit de versieruimte (beleiden consistent met trainingsdata).
3. Stopregel: De leerling voert $\pi_0$ uit en gaat alleen door zolang elke validator in $\Phi$ het eens is met $\pi_0$. Het eerste punt van onenigheid triggert een stop (afzien).
4. Schaarse Validatorverdeling: Een kritische theoretische bijdrage is het bewijs dat een schaarse validatorset (grootte onafhankelijk van de horizon $H$) voldoende is om veiligheid te garanderen. Dit wordt bereikt via een minimax-argument over een nulsomspel tussen een "uitdager" (die een concurrerend beleid kiest) en een "validator" (die een set validators kiest).

Variant voor Verschillende Settings

Het artikel past dit kader toe op drie steeds generaler wordende settings:

• Deterministische Beleiden:

  • Mechanisme: Gebruikt een binaire onenigheidstest. De stoptijd $\tau$ is de eerste stap waar een validator $\pi \in \Phi$ het oneens is met $\pi_0$.
  • Implementatie: De validatorverdeling wordt geconstrueerd met behulp van no-regret dynamiek (specifiek, een oracle-efficiënte reductie naar Weighted Realizable Multiple-Instance Learning).
  • Resultaat: Bereikt horizon-vrije steekproefcomplexiteit $\tilde{O}(\sqrt{\log|\Pi|/n})$ onder schaarse kosten.

• Stochastische Beleiden:

  • Uitdaging: Binaire onenigheid is te grof; verdelingen kunnen op elke stap "zacht" verschillen zonder een enkele alarmerende discrepantie.
  • Mechanisme: Vervangt de binaire test door een cumulatieve Hellinger-afstand stoptijd. De leerling stopt wanneer de opgebouwde gekwadrateerde Hellinger-afstand tussen $\pi_0$ en een validator een drempel $\theta$ overschrijdt.
  • Resultaat: Biedt finite-sample grenzen voor de Hellinger-afstand van gestopte trajecten. Het artikel stelt een $\Omega(1/\epsilon^3)$ ondergrens vast voor gelabelde steekproefcomplexiteit in de stochastische single-step setting, wat overeenkomt met het door kosten gedreven deel van de bovengrens.

• Foutgespecificeerde Beleidklassen:

  • Uitdaging: De expert $\pi^\star$ ligt mogelijk niet binnen de beleidklasse $\Pi$ van de leerling.
  • Mechanisme: Vervangt de harde versieruimte-beperking door een symmetrisch geregulariseerd spel. Validators mogen het oneens zijn met het basisbeleid op brondata, maar deze onenigheid wordt bestraft.
  • Resultaat: Garanties degraderen moeiteloos met de hoeveelheid foutspecificatie (gemeten door de beste-in-klasse foutspecificatiefout $\Delta$).

3. Belangrijkste Bijdragen en Resultaten

Theoretische Garanties

• Horizon-vrije Complexiteit: Voor deterministische beleiden is de steekproefcomplexiteit onafhankelijk van de horizon $H$ (behalve via de totale kostenschaal $C_{max}$), en schaalt als $\tilde{O}(\sqrt{\log|\Pi|/n})$. Dit verbetert naieve stapsgewijze reducties die lijden onder een $O(H^2)$-straf.
• Schaarse Validatie: Het artikel bewijst het bestaan van een validatorverdeling ondersteund op sets van grootte $O(1/\epsilon)$, onafhankelijk van de toestandsruimte, actieruimte of horizon.
• Ondergrenzen: De auteurs bewijzen een $\Omega(1/\epsilon^3)$ ondergrens voor gelabelde steekproefcomplexiteit in de stochastische single-step setting, wat aantoont dat de kubieke afhankelijkheid van $1/\epsilon$ onvermijdelijk is voor door kosten gedreven regimes.
• Robuustheid tegen Foutspecificatie: Het kader breidt zich uit naar agnostische settings waar de expert niet in de klasse zit, met regretgrenzen die schalen met de wortel van de foutspecificatiefout.

Empirische Evaluatie

De auteurs evalueren SeqRejectron in de LunarLander-v3-omgeving.

• Opzet: Training vindt plaats in een windloze omgeving; testen vindt plaats in een winderige omgeving met verschillende initiële impulsen.
• Vondsten: Het algoritme detecteert succesvol dynamiek buiten de verdeling. Door een veiligheidsdrempel $\theta$ af te stemmen, demonstreren de auteurs een trade-off waarbij het beleid minimaal afziet op data binnen de verdeling (training) terwijl het betrouwbaar stopt op data buiten de verdeling (test), waardoor catastrofale fouten worden voorkomen. Het aantal validators bleek robuust, met prestaties die snel verzadigen.

4. Betekenis en Claims

Het artikel claimt afzien te vestigen als een principiële, theoretisch onderbouwde reactie op onvoorziene dynamische verschuivingen in imitatieleren.

• Buiten Heuristieken: In tegenstelling tot robuust RL of domeinrandomisatie-benaderingen die aannames vereisen over de aard van de verschuiving of online toegang tot de testverdeling, biedt SeqRejectron distributie-vrije PAC-garanties met uitsluitend offline data.
• Sequentieel Analoge van PQ Learning: Het werk positioneert zichzelf als een sequentieel analogon van het PQ-learning-kader (Goldwasser et al., 2020), waarbij het vermogen om af te zien wordt uitgebreid van enkele voorspellingen naar volledige traject-prefixen.
• Veiligheidsmechanisme: Door de beslissing over wat te doen te ontkoppelen van wanneer te stoppen, biedt het kader een veiligheidsmechanisme dat voorkomt dat de leerling het systeem in onherstelbare toestanden drijft wanneer zijn trainingsdata oninformatief is.

De auteurs erkennen beperkingen, en merken op dat de stochastische setting momenteel een oracle-efficiënte computationele reductie mist (in tegenstelling tot het deterministische geval) en dat de door variantie gedreven steekproefcomplexiteitspercentages voor stochastische beleiden een open kloof blijven tussen boven- en ondergrenzen. Zij suggereren ook dat toekomstig werk gedeeltelijke structurele kennis (bijvoorbeeld begrenste TV-afstand) zou kunnen incorporeren om de stoppercentages aan de testkant aan te scherpen.