Technische Samenvatting: Reinforcement Learning met Actie-Getriggerde Observaties

1. Probleemdefinitie

Het artikel behandelt een specifieke klasse van Partially Observable Markov Decision Processes (POMDP's) waarbij de beschikbaarheid van staatsobservaties niet exogeen of vaststaat, maar actie-getriggerd is. In standaard RL observeert een agent de nieuwe staat na elke actie. In veel praktische scenario's (bijv. klinische diagnostiek, financiële handel) is het verkrijgen van een staatsobservatie kostbaar, onbetrouwbaar of vereist het een specifieke actie om een observatie te triggeren.

De auteurs formaliseren deze setting als Action-Triggered Sporadically Traceable Markov Decision Processes (ATST-MDP's).

• Mechanisme: Wanneer een agent in staat $s$ actie $a$ uitvoert, ontvangt hij een beloning en gaat het milieu over naar $s'$. Cruciaal is dat $s'$ niet altijd wordt geobserveerd. Met een waarschijnlijkheid $\beta(a)$ vindt een "observatiegebeurtenis" (data-burst) plaats, die $s'$ en de cumulatieve beloning sinds de laatste burst onthult. Met een waarschijnlijkheid $1-\beta(a)$ wordt er geen staatfeedback verstrekt.
• Uitdaging: De agent moet simultaan de controle-policy optimaliseren en beslissen wanneer observaties getriggerd moeten worden (door acties te kiezen met een hogere $\beta(a)$) om onzekerheid te verminderen, waarbij de kosten van informatieverwerving worden afgewogen tegen de prestaties van de controle.
• Onderscheid: In tegenstelling tot standaard POMDP's waar observaties ruizig maar frequent zijn, of RL met exogene vertragingen waarbij feedback simpelweg laat is, kenmerken ATST-MDP's zich door endogene vertragingen, waarbij de keuze van de acties van de agent direct de frequentie van de staat-onthulling bepaalt.

2. Methodologie

2.1 Geaugmenteerde Toestandsruimte en Bellman-vergelijkingen

Om de partiële observeerbaarheid aan te pakken, definiëren de auteurs een geaugmenteerde toestandsruimte $\mathcal{X} = \mathcal{S} \times \mathcal{A}^{<\infty}$. Een geaugmenteerde staat $x = (s_1, a_1, \dots, a_n)$ bestaat uit de laatst geobserveerde staat $s_1$ en de sequentie van acties die sinds die observatie zijn uitgevoerd.

• Voldoendheid: De geaugmenteerde staat dient als een voldoende statistiek voor de historie, waardoor het probleem behandeld kan worden als een volledig observeerbare MDP op $\mathcal{X}$.
• Dynamiek: De transitie op $\mathcal{X}$ is een mengeling: met waarschijnlijkheid $\beta(a)$ reset de staat naar de nieuw geobserveerde staat $s'$; met waarschijnlijkheid $1-\beta(a)$ wordt de actiesequentie aangevuld ($x \leftarrow x \cdot a$).
• Bellman-vergelijkingen: De auteurs leiden Bellman-optimaliteitsvergelijkingen af voor waardefuncties $V^\pi$ en $Q^\pi$ op deze geaugmenteerde ruimte, en bewijzen het bestaan van een optimale geaugmenteerde policy $\pi^*$.

2.2 Actie-sequentie Herformulering

In het besef dat de geaugmenteerde toestandsruimte oneindig vertakt, stelt de auteur een herformulering voor op basis van de vernieuwingsstructuur (renewal structure) van data-bursts. In plaats van actie-per-actie te beslissen, committeert de agent zich aan een actie-sequentie $a \in \mathcal{A}^\mathbb{N}$ bij elke data-burst, en voert deze uit totdat de volgende observatie plaatsvindt.

• Dit transformeert het probleem in een beslissingsproces over $(\mathcal{S}, \mathcal{A}^\mathbb{N})$.
• De waardefunctie $K^\pi(s, a)$ vertegenwoordigt de verwachte gedisconteerde beloning die wordt geaccumuleerd vanaf staat $s$ door sequentie $a$ uit te voeren tot de volgende data-burst, plus de continuatiewaarde van de onthulde staat.

2.3 Lineaire Representatie onder de Lineaire MDP-aanname

Om de oneindig-dimensionale actie-sequentieruimte hanteerbaar te maken, neemt het artikel een Lineaire MDP-structuur aan (Aanname 4.1), waarbij transitiekernels en beloningen lineair zijn in een feature-map $\phi(s, a)$.

• Kerninzicht: Onder deze aanname bezit de actie-sequentie waardefunctie $K^\pi$ een lineaire representatie in een einddimensionale feature-map $\psi: \mathcal{S} \times \mathcal{A}^\mathbb{N} \to \mathbb{R}^{2d}$.
• Constructie: De feature-map $\psi$ wordt geconstrueerd met behulp van actie-matrices $M_a$ (afgeleid van de transitiedynamiek) en observatiekansen $\beta_a$. Specifiek codeert $\psi$ de evolutie van features over de actie-sequentie en de waarschijnlijkheid dat er bij elke stap een data-burst plaatsvindt.
• Resultaat: $K^\pi(s, a) = \langle \psi(s, a), v^\pi_{1,2} \rangle$, waarbij $v^\pi_{1,2}$ een policy-afhankelijke vector is. Dit maakt het gebruik van standaard regressie-gebaseerde methoden mogelijk ondanks de oneindige actieruimte.

2.4 Schatting en Leeralgoritme

Het artikel stelt ATST-LSVI-UCB voor (Action-Triggered Sporadically Traceable Least-Squares Value Iteration met Upper Confidence Bounds).

• Feature-schatting: Omdat de ware feature-map $\psi$ onbekend is, schat het algoritme de onderliggende actie-matrices $M_a$ en observatiekansen $\beta_a$ in vanuit exploratieve data middels ridge-regressie en empirische gemiddelden. Stelling 4.6 en Bijlage 4.9 bieden non-asymptotische steekproefcomplexiteitsgrenzen voor het construeren van een $\epsilon$-admissibele benadering van $\psi$.
• Algoritme: Het algoritme werkt in episodes met geometrische horizonten. Het voert backward value iteration uit op de geschatte feature-map om optimistische waarde-inschattingen te berekenen (met behulp van UCB-bonussen) en voert de meest winstgevende (greedy) actie-sequenties uit.
• Optimalisatie: Hoewel de actieruimte oneindig is, wordt de optimalisatie $\max_a K(s, a)$ uitgevoerd over de compacte afbeelding van de feature-map. In de praktijk kan dit benaderd worden door te beperken tot eindige diepte of uiteindelijk periodieke sequenties.

3. Belangrijkste Bijdragen

1. Formalisering van ATST-MDP's: Een nieuw kader voor RL in omgevingen waar de beschikbaarheid van observaties een functie is van de gekozen actie, wat de kloof overbrugt tussen standaard MDP's en algemene POMDP's.
2. Theoretische Fundamenten: Afleiding van Bellman-vergelijkingen op de geaugmenteerde toestandsruimte en bewijs van het bestaan van een optimale policy.
3. Lineaire Representatie: Demonstratie dat onder de lineaire MDP-aanname de waardefunctie over actie-sequenties lineair is in een einddimensionale feature-map, wat efficiënt leren mogelijk maakt.
4. Algoritme en Regret Bounds: Voorstel van ATST-LSVI-UCB, een optimistisch value iteration algoritme. De auteurs bewijzen een regret-grens van $\tilde{O}(\sqrt{d^3 K (1-\gamma)^{-3}})$ voor episodisch leren, wat overeenkomt met de bekende optimale snelheid voor volledig observeerbare lineaire MDP's.
5. Steekproefcomplexiteit: Vaststelling van steekproefcomplexiteitsgaranties voor het schatten van de actie-sequentie feature-map vanuit data, waarbij aangetoond wordt dat dit polynomiaal is in dimensie $d$ en onafhankelijk is van de grootte van de toestandsruimte $|\mathcal{S}|$.

4. Resultaten

• Theoretisch: De regret-grens komt overeen met de state-of-the-art voor lineaire MDP's met volledige observeerbaarheid, ondanks de toegevoegde complexiteit van partiële observeerbaarheid en actie-getriggerde vertragingen. De grens schaalt met de feature-dimensie $d$, het aantal episodes $K$, en de inverse van de kortingsfactor $(1-\gamma)$.
• Empirisch: Experimenten in twee tabular omgevingen, RiverSwim (exploratie-zwaar) en RiverBalance (stabilisatie-zwaar), demonstreren de levensvatbaarheid van het algoritme.
  • In RiverSwim versnelden schaarse observaties (lage $\beta$) verrassend genoeg de convergentie door langere open-loop commitments (exploratie) te stimuleren.
  • In RiverBalance leverden frequente observaties (hoge $\beta$) hogere beloningen op, omdat de taak staat-afhankelijke correcties vereiste om stabiliteit te handhaven.
  • De resultaten benadrukken dat de optimale observatiefrequentie taakafhankelijk is.

5. Betekenis en Claims

Het artikel claimt een theoretische fundering te bieden voor reinforcement learning in omgevingen met actie-getriggerde staatsobservaties. De significantie ligt in:

• Bruggen Slaan: Het adresseert een specifieke, praktisch relevante klasse van POMDP's (actieve perceptie, kostbare sensoren) waar algemene POMDP-methoden moeite mee hebben vanwege computationele onhandelbaarheid.
• Hanteerbaarheid: Door gebruik te maken van de vernieuwingsstructuur geïnduceerd door data-bursts en de lineaire MDP-aanname, transformeert het een onhandelbaar probleem van partiële observeerbaarheid naar een hanteerbaar lineair regressieprobleem.
• Optimaliteit: Het bereikt regret-rates die vergelijkbaar zijn met volledig observeerbare settings, wat suggereert dat de "kosten" van sporadische observeerbaarheid kunnen worden gemitigeerd als het observatiemechanisme begrepen en benut wordt.
• Beloningsvrije Schatting: De feature-map schatting is beloningsvrij, wat betekent dat het structurele leren van de omgeving (dynamiek en observatiekansen) kan worden losgekoppeld van de specifieke beloningsfunctie, wat flexibele policy-adaptatie mogelijk maakt.

De auteurs merken op dat toekomstig werk zich moet richten op het ontwerpen van efficiënte benaderingsschema's voor de oneindige actie-sequentie optimalisatie en het ontwikkelen van volledig online algoritmen die adaptief feature-schattingen verfijnen zonder vooraf verzamelde exploratieve data.