On the Role of Computation in Reinforcement Learning

Technische Samenvatting: Over de Rol van Computatie in Reinforcement Learning

Probleemstelling
De standaard visie op Reinforcement Learning (RL) beschouwt beleidsregels (policies) als statische functies die toestanden naar acties mappen, waarbij een vaste hoeveelheid computatie wordt besteed ongeacht de complexiteit van de beslissing. Dit paradigma verwart het aantal parameters (geheugen) met de hoeveelheid computatie (tijd). Hoewel het schalen van het aantal parameters (de wet van Moore) een veelgebruikte strategie is geweest, kan de benodigde computatie om optimale beslissingen te nemen over verschillende grootordes variëren tussen verschillende toestanden. Statische, massieve beleidsregels zijn vaak inefficiënt, en computationeel beperkte beleidsregels kunnen falen bij het generaliseren naar taken met een langere horizon, waarbij ze in plaats daarvan heuristieken leren die overfitten op trainingsdistributies. Het artikel adresseert het gebrek aan een formele taal om computatie en parameters in RL van elkaar te onderscheiden en onderzoekt of beleidsregels met vaste parameters kunnen profiteren van variabele, verhoogde computationele tijd.

Methodologie
Het artikel benadert het probleem via twee complementaire lenzen: theoretische formalisering en empirische validatie.

1. Theoretisch Kader:

   • De auteurs formaliseren RL-beleidsregels als begrensde computationele modellen met behulp van Turingmachines.
   • Ze definiëren tijdgebonden beleidsregels ($\Pi_t$) als die implementeerbaar zijn door een Turingmachine die binnen $t(|s|)$ stappen stopt.
   • Ze introduceren de Policy Hierarchy Theorem, die bewijst dat voor tijd-constructeerbare functies $g(n) \in o(t(n)/\log t(n))$, er Markov Beslissingsprocessen (MDP's) bestaan waarbij beleidsregels met hogere computatiebudgetten ($\Pi_t$) willekeurig beter presteren dan die met lagere budgetten ($\Pi_g$).
   • Verder bewijzen ze de Long Horizon Generalization Theorem, die aantoont dat beleidsregels met lage computatie kunnen overfitten op trainingstaken (het optimale waardefunctie matchen op trainingsdata), maar falen in het generaliseren naar testtaken met een langere horizon, terwijl beleidsregels met hoge computatie deze uitgebreide taken wel kunnen oplossen.

2. Architecturaal Voorstel:

   • Om deze theorieën te testen, stellen de auteurs een minimale recurrente architectuur voor, de Interpolation Recurrent Unit (IRU).
   • De IRU is een vereenvoudigde variant van LSTM/GRU-blokken, bestaande uit twee lineaire lagen (Forget en Input) die interpoleren tussen de vorige celtoestand en een nieuwe lokale berekening.
   • De architectuur past dit blok $N$ keer toe tijdens een forward pass (recurrente stappen), waardoor de beleidsregel een variabele hoeveelheid computatie ($N$) kan gebruiken terwijl het aantal parameters constant blijft.
   • Het volledige netwerk (IRU-$N$) bevat een initiële lineaire laag, $N$ recurrente blokken met skip-verbindingen, en een finale output-kop.

3. Experimentele Opzet:

   • Experimenten werden uitgevoerd over 31 taken die variëren van discrete (Boxpick, Lightsout) tot continue (OGBench) domeinen, inclusief zowel online als offline RL-instellingen.
   • De baselines omvatten standaard Feedforward Netwerken (MLP) en Residuële Netwerken (ResNet). Cruciaal was dat de ResNet-baseline zo is ontworpen dat deze een vergelijkbare effectieve diepte (computatie) heeft, maar aanzienlijk meer parameters (tot 5x), terwijl de MLP vergelijkbare parameters heeft maar minder computatie.
   • De studie evalueerde prestaties op trainingstaken en, cruciaal, op ongeziene taken met een langere horizon om generalisatie te meten.

Kernbijdragen

• Formalisering van Computatie-gebonden Beleidsregels: Het artikel levert het eerste formele bewijs dat het verhogen van de computationele tijd (onderscheidend van het aantal parameters) het mogelijk maakt om problemen op te lossen en te generaliseren naar langere horizonten die theoretisch onmogelijk zijn voor beleidsregels met een lagere computatie.
• Minimale Recurrente Architectuur: De introductie van de IRU, een lichtgewicht architectuur die in staat is om computatie te schalen via recurrente stappen zonder het aantal parameters te verhogen.
• Value of Compute Metric: Een voorgestelde numerieke maatstaf, de Value of Compute (VoC), analoog aan de Value of Information in POMDP's. Deze metriek schat de winst of het verlies in waarde wanneer een agent tijdelijk zijn computatiebudget voor een specif aantal stappen verhoogt.
• Ontkoppeling van Computatie en Parameters: Empirisch bewijs dat de prestatiewinsten voortkomen uit verhoogde expressiviteit (computatie) in plaats van enkel een grotere modelcapaciteit (parameters).

Resultaten

• Prestatieschaalbaarheid: In zowel discrete als continue omgevingen leidde het verhogen van het aantal recurrente stappen ($N$) van 1 naar 10 tot een significante verbetering van de succesratio's. In uitdagende taken zoals Boxpick en OGBench steeg de prestatie tot wel 10-voudig.
• Generalisatie: IRU-beleidsregelingen die getraind zijn op korte-horizon taken, generaliseerden significant beter naar ongeziene lange-horizon taken vergeleken met MLPs en ResNets. Opvallend genoeg presteerde IRU beter dan ResNets met 5 keer zoveel parameters op evaluatietaken met een lange horizon.
• Sample Efficiëntie: IRU-architecturen vertoonden een hogere sample efficiëntie en convergeerden naar een hogere asymptotische prestatie met minder omgevingsstappen.
• Bron van Verbetering: "Yoked" experimenten (waarbij een passieve agent wordt getraind op data verzameld door een actieve agent) onthulden dat het primaire voordeel van extra computatie voortkomt uit de expressiviteit van de beleidsregel (het vermogen om complexe oplossingen te leren van data) in plaats van verbeterde exploratie of datakwaliteit. De passieve agent, getraind op data van een lage-computatie actieve agent, presteerde slecht, tenzij deze zelf over hoge computatie beschikte.
• Ablatie: De IRU-architectuur presteerde beter dan standaard LSTMs en Recurrent ResNets in termen van snelheid en parameter-efficiëntie, wat suggereert dat specifieke gating-mechanismen noodzakelijk zijn om de voordelen van extra computatie effectief te benutten.

Significantie en Claims
Het artikel claimt het perspectief op RL te verschuiven van statische functie-approximatie naar een computationeel perspectief waarbij tijd en geheugen twee verschillende assen zijn. De auteurs stellen dat:

1. Computatie een afzonderlijke hulpbron is: Het verhogen van de computationele tijd kan bewezen de prestaties en generalisatie verbeteren zonder de omvang van de hypotheseklasse (parameters) te vergroten, waardoor de overfitting-problemen die gepaard gaan met grotere statische modellen worden vermeden.
2. Generalisatie via Iteratie: Iteratieve computatie stelt beleidsregels in staat om algoritmische oplossingen te leren die extrapoleren naar langere horizonten, een fenomeen dat wordt waargenomen bij taalmodellen maar voorheen onvoldoende werd verkend in RL zonder pre-training of multi-task curricula.
3. Beperkingen van Statische Perspectieven: De resultaten suggereren dat standaard MDP-aannames (bijv. het bestaan van een deterministische optimale beleidsregel) mogelijk niet standhouden onder computationele beperkingen, wat mogelijk verklaart waarom niet-Markoviaanse beleidsregels soms nodig zijn, zelfs in volledig geobserveerde taken.

De auteurs concluderen dat hoewel hun werk een minimale architectuur gebruikt om deze effecten te isoleren, de bevindingen suggereren dat toekomstige RL-systemen moeten overwegen om adaptieve computatiestrategieën te gebruiken, waarbij de hoeveelheid computatie dynamisch wordt geschaald op basis van de moeilijkheidsgraad van de huidige toestand.