Technische Samenvatting: De Terminale Representatie in Reinforcement Learning

Probleemstelling

In Reinforcement Learning (RL) is representatieleer cruciaal voor spatio-temporele abstractie. Twee gevestigde benaderingen zijn de Successor Representation (SR) en de Default Representation (DR). De SR codeert toestanden op basis van toekomstige visitatie-trajecten, waarbij de transitiedynamiek onafhankelijk van beloningen wordt vastgelegd. De DR breidt dit uit door deze trajecten te wegen met beloningen, waardoor de structuur van credit-assignment wordt geïntegreerd.

Echter, beide representaties kampen met beperkingen bij toepassing op downstream-taken zoals option discovery, reward shaping en transfer learning:

1. Computationele overhead: Het gebruik van de DR of SR voor deze taken vereist doorgaans eigendecompositie (of machtsiteratie) om eigenvectoren te extraheren. Dit legt een computationele kostenpost op van $O((S^+)^2)$ of hoger per query en gaat uit van symmetrische (reversibele) transitiedynamiek, een conditie die vaak wordt geschonden in praktische RL-omgevingen waar policies directioneel zijn.
2. Dimensionaliteit: De SR en DR zijn gedefinieerd over de volledige toestandsruimte ($S^+ \times S^+$), die groot en inefficiënt kan zijn om op te slaan en te leren.
3. Indirecte kennis: Hoewel de DR beloningsgewogen trajecten codeert, isoleert het de bereikbaarheid en wenselijkheid van terminale toestanden niet expliciet in een formaat dat direct bruikbaar is zonder verdere spectrale analyse.

Methodologie: De Terminale Representatie (TR)

De auteurs stellen de Terminale Representatie (TR) voor, een structureel onderscheidende formulering die is ontworpen om beloningsgewogen trajecten specifiek met betrekking tot terminale toestanden te coderen.

Theoretische Fundering

De TR is afgeleid binnen het kader van Linearly-Solvable Markov Decision Processes (LMDPs). In een LMDP kan de optimale waardefunctie $v(s)$ worden getransformeerd naar een geëxponentieerde waarde $z(s) = e^{v(s)/\lambda}$, die voldoet aan de lineaire vergelijking:
$$z(s) = e^{R(s)/\lambda} \sum_{s'} P_\mu(s'|s)z(s')$$
waarbij $P_\mu$ een default policy is en $\lambda$ een temperatuurparameter.

Door de toestandsruimte te splitsen in niet-terminale toestanden ($S$) en terminale toestanden ($T$), leiden de auteurs de TR-matrix $M$ af als:
$$M = (I_S - D_S)^{-1} D_T$$
waarbij $D_S = R_S P_S$ de niet-terminale dynamiek vertegenwoordigt en $D_T = R_S P_T$ de transities van niet-terminale naar terminale toestanden vertegenwoordigt. Hierbij zijn $R_S$ en $R_T$ diagonale matrices van geëxponentieerdeerde beloningen.

De TR maakt zero-shot recovery van de optimale geëxponentieerdeerde waarden $z$ mogelijk voor elke configuratie van terminale beloningen $y$ (waarbij $y(\tau) = e^{R(\tau)/\lambda}$) via de lineaire relatie:
$$z = M y$$

Leeralgoritmen

Het artikel stelt de convergentie vast van twee leeralgoritmen voor $M$:

1. Dynamic Programming (Model-Based): Een iteratieve update-regel $M_{k+1} = D_T + D_S M_k$ is bewezen te convergeren naar de ware TR.
2. Sample-Based (Model-Free): Een temporal difference (TD) stijl update-regel is afgeleid voor online leren:
   $$\hat{M}(s_t) \leftarrow (1 - \alpha_t)\hat{M}(s_t) + \alpha_t e^{r_t/\lambda} \hat{M}^+(s_{t+1})$$
   waarbij $\hat{M}^+$ een uitgebreide mapping is die transities naar terminale toestanden afhandelt. Theorem 4.2 bewijst dat dit convergeert naar $M$ onder standaard stochastische benaderingscondities.

Belangrijke Theoretische Eigenschappen

• Dimensionaliteit: De TR is een $S \times T$ matrix. Omdat het aantal terminale toestanden $T$ vaak veel kleiner is dan de totale toestandsruimte $S^+$, is de TR aanzienlijk compacter dan de $S^+ \times S^+$ DR.
• Direct Gebruik (Geen Eigendecompositie): De kolommen van de TR komen direct overeen met de informatie die gewoonlijk via eigenvectoren van de DR wordt geëxtraheerd. Theorem 7.1 demonstreert dat de top-eigenvector van de DR structureel is samengesteld uit een TR-kolom (specifiek de kolom die overeenkomt met de meest wenselijke terminale toestand) en een geometrische reeks. Zo vangt de TR dezelfde onderliggende structurele kennis zonder dat eigendecompositie nodig is.
• Afhandeling van Asymmetrie: In tegen tegenstelling tot eigenvector-gebaseerde benaderingen die vertrouwen op de reversibiliteit van transitiedynamiek (symmetrie) om reële eigenwaarden te garanderen, is de TR inherent asymmetrisch en goed gedefinieerd onder willekeurige, niet-reversibele dynamiek.
• Compositionaliteit: De TR ondersteunt zero-shot compositionaliteit. Als een nieuwe taak een lineaire combinatie is van basis-taken met verschillende terminale beloningen, kan de optimale waardefunctie worden hersteld door de overeenkomstige kolommen van de TR lineair te combineren, waardoor het opnieuw leren van basis-waardefuncties wordt omzeild.
• Beloningsequivalentie: De auteurs bewijzen dat LMDPs met transitie-afhankelijke of state-action-afhankelijke beloningen kunnen worden gemapt naar equivalente LMDPs met state-afhankelijke beloningen, wat ervoor zorgt dat de TR-theorie breed toepasbaar is op verschillende beloningsformuleringen.

Experimentele Resultaten

De auteurs evalueren de TR tegenover de SR en DR over vier downstream-toepassingen in grid-world omgevingen (Four Rooms, RiverSwim, SixArms):

1. Option Discovery: In de "covering eigenoptions" taak wordt de TR gebruikt om options te genereren door direct kolommen te extraheren (zonder eigenvectorberekening). Varianten die de kolom van de hoogste-belonings terminale toestand gebruiken of alle kolommen gebruiken, behaalden competitieve prestaties met de DR-gebaseerde RACE en SR-gebaseerde CEO methoden, waarbij ze vaak hogere gemiddelde beloningen bereikten door agenten direct naar wenselijke doelen te duwen.
2. Reward Shaping: Het gebruik van de TR om potential-based shaping rewards te construeren ($\hat{r}_t = 1 - M(s_{t+1}, \tau)$) leverde prestaties op die identiek waren aan de DR en superieur aan de SR. Dit bevestigt het vermogen van de TR om de noodzakelijke structurele informatie voor efficiënte navigatie te vangen zonder eigendecompositie.
3. Count-Based Exploration: Het gebruik van de norm van de TR als een exploratiebonus in de RiverSwim en SixArms omgevingen resulteerde in prestaties die bijna identiek waren aan de DR en significant beter dan de SR.
4. Transfer Learning: Wanneer terminale beloningen tussen taken veranderden, werd de TR gebruikt om kennis te transfereren. Het presteerde vergelijkbaar met Default Features (DF) (de policy-onafhankelijke DR-variant) en presteerde beter dan Successor Features (SF) over diverse basis-policy configuraties, zonder een expliciete feature learning stap.

Betekenis en Claims

Het artikel claimt dat de Terminale Representatie een levensvatbaar, computationeel efficiënt alternatief biedt voor de SR en DR. De primaire betekenis ligt in:

• Efficiëntie: Het vermindert de dimensionaliteit van de representatie en elimineert de noodzaak voor dure eigendecompositie, waardoor de query-complexiteit wordt verminderd van $O((S^+)^2)$ naar $O(1)$ voor kolomextractie.
• Robuustheid: Het functioneert correct onder niet-symmetrische (niet-reversibele) transitiedynamiek, een veelvoorkomend scenario in RL waar eigenvector-methoden kunnen falen of complexe eigenwaarden kunnen opleveren.
• Directe Toepasbaarheid: Het codeert kennis over terminale toestanden expliciet, wat directe toepassing mogelijk maakt in reward shaping, option discovery en transfer learning zonder tussenliggende spectrale analyse.

De auteurs houden een bescheiden standpunt aan en merken op dat hoewel de TR competitief is met de DR, het niet fundamenteel superieur is in alle semantische aspecten; in plaats daarvan biedt het een compacter en computationeel hanteibaar mechanisme om toegang te krijgen tot dezelfde onderliggende structurele kennis met betrekking tot terminale toestanden. Toekomstig werk wordt gesuggereerd om de TR uit te breiden naar hoog-dimensionale omgevingen via functie-approximatie en om situaties te behandelen zonder expliciet gedefinieerde terminale toestanden.