On the Variance of Temporal Difference Learning and its Reduction Using Control Variates

Technische Samenvatting: Over de variantie van Temporal Difference Learning en de reductie daarvan met behulp van Control Variates

Probleemstelling
Beleidsevaluatie (policy evaluation) is een fundamentele uitdaging in reinforcement learning (RL). Terwijl Monte Carlo (MC)-methoden onbevooroordeelde schattingen van waardefuncties bieden, lijden ze aan een hoge variantie door de noodzaak om over volledige trajecten te middelen. Daartegenover staat Temporal Difference (TD) learning, dat bootstrapping gebruikt (het updaten van schattingen op basis van andere schattingen) om variantie te verminderen, maar dit introduceert bias. Het precieze mechanisme waarmee TD variantie vermindert, met name in het online regime, en hoe dit asymptotisch vergeleken kan worden met MC, is een onderwerp gebleven van genuanceerde discussie. Bovendien is de theoretische rechtvaardiging van Direct Advantage Estimation (DAE) met betrekking tot variantiereductie, ondanks het empirische succes in deep RL, beperkt gebleven tot convergentie-eigenschappen in plaats van een rigoureuze analyse van de variantie-bounds vergeleken met standaard TD.

Methodologie
De auteurs analyseren de variantie van multi-step TD-learning binnen een gefaseerde (synchrone) setting met gebruik van tabulaire representaties. Deze setting abstraheert de complexiteiten die gepaard gaan met asynchrone updates en stochastische benaderingen weg, waardoor een duidelijkere isolatie van variantiemechanismen mogelijk is.

1. Variantie-decompositie: Het artikel leidt een recursierelatie af voor de variantie van multi-step TD-updates. Door deze recursie uit te breiden, vergelijken de auteurs de asymptotische variantie van TD met MC-schatters.
2. Control Variate Framework: De auteurs kaderen de advantage functie ($A^\pi$) als een control variate voor beleidsevaluatie. Ze maken gebruik van het concept van regressie-gecorrigeerde control variates, waarbij de advantage functie gelijktijdig met de waardefunctie wordt geschat om de variantie van de return-schatter te minimaliseren.
3. Direct Advantage Estimation (DAE): Het artikel analyseert DAE (Pan et al., 2022) als een beperkt kleinste-kwadratenprobleem. Door de schattingen van de advantage functie te behandelen als nuisance parameters in een regressiekader, herformuleren de auteurs de DAE-update regel om expliciet de structuur ervan als een regressie-gecorrigeerde control variate te tonen.
4. Empirische Validatie: Theoretische claims worden geïllustreerd met zorgvuldig ontworpen Chain MDP-omgevingen. Deze experimenten variëren de mate van stochastiek (reward masking, sticky transitions) en de dekking van de state-action ruimte om de asymptotische gedragingen van MC, TD en DAE onder verschillende condities te testen.

Belangrijkste Bijdragen

1. Asymptotische Variantie-bound van TD: De auteurs bewijzen dat in zowel gefaseerde (synchrone) als IID (asynchrone) settings, de asymptotische variantie van multi-step TD-learning boven begrensd wordt door die van Monte Carlo-methoden.

   • Mechanisme: Het artikel identificeert dat TD variantie niet enkel vermindert via een bias-variance tradeoff, maar door effectief te aggregeren over een grotere pool van onafhankelijke trajecten. Wanneer de bootstrapping-states divers en zwak gecorreleerd zijn, vermindert het middelen van hun waarden de variantie. Omgekeerd, als de bootstrapping-states identiek zijn (sterk gecorreleerd), neemt het vermogen van TD om variantie te reduceren af, en nadert het asymptotisch de variantie van MC.
   • Horizon Effect: Voor een vast aantal samples veroorzaken kortere horizon updates (kleinere $k$) minder variantie dan single long-horizon updates.

2. DAE als Regressie-gecorrigeerde Control Variate: Het artikel demonstreert dat de advantage functie als een control variate voor MC-schatters kan dienen. Verder stellen zij vast dat Direct Advantage Estimation (DAE) een vorm is van een regressie-gecorrigeerde control variate die gelijktijdig de waarde- en advantage functies schat.

   • Variantie-bound: In de limiet van grote samples bereikt DAE een strakkere boven grens op de variantie vergeleken met standaard TD. Specifiek wordt de variantie van DAE begrensd door de variantie van een MC-schatter die is aangepast met de advantage functie (MC-A), die op zichzelf lager is dan of gelijk aan de variantie van standaard MC.

3. Empirische Illustraties:

   • In deterministische omgevingen, waar bootstrapping-states identiek zijn, faalt TD in het reduceren van variantie ten opzichte van MC, wat de theoretische afhankelijkheid van trajectdiversiteit bevestigt.
   • In stochastische transitie omgevingen vertoont TD de verwachte bias-variance tradeoff, en convergeert DAE snel (vergelijkbaar met Bellman-iteraties) omdat de advantage functie de variantie volledig verklaart.
   • In reward masking scenario's (waar de reward-variantie niet door acties kan worden verklaard), kan de advantage van DAE de variantie niet volledig elimineren, wat resulteert in een kleine asymptotische kloof vergeleken met Bellman-iteraties, maar het presteert nog steeds beter dan TD.
   • In low-coverage settings (ondergesamplede actieruimtes) kan DAE lijden onder small-sample bias door onbetrouwbare advantage schattingen, maar het convergeert nog steeds naar een lagere Mean Squared Error (MSE) dan TD, wat duidt op robuustheid zelfs met imperfecte control variates.

Resultaten en Betekenis
Dit artikel biedt een rigoureuze theoretische verklaring voor de variantiereductie van bootstrapping, waarbij het verder gaat dan de intuïtieve "bias-variance tradeoff" naar een mechanisme gebaseerd op trajectaggregatie. Het verheldert dat de superioriteit van TD ten opzichte van MC afhankelijk is van de diversiteit van de bootstrapping-states.

Verder biedt het werk een theoretische fundering voor DAE, door het empirische succes van DAE in deep RL te verklaren door het te kaderen als een control variate methode. De resultaten suggereren dat het benutten van de advantage functie als een control variate theoretisch een strakkere variantie-bounds kan bereiken dan standaard TD.

Beperkingen en Reikwijdte
De auteurs merken enkele beperkingen op:

• De theoretische resultaten zijn afgeleid voor gefaseerde en IID settings; generalisatie naar realistische Markoviaanse sampling-schema's blijft een open vraag.
• De analyse richt zich op variantiereductie; DAE brengt extra computationele kosten met zich mee (oplossen van kleinste kwadraten) en vereist meer opslag.
• De strakke variantie-bounds voor DAE vertrouwen op een groot-sample benadering waarbij de control variate coëfficiënten optimaal zijn. Hoewel empirische resultaten voordelen suggereren in small-sample regimes, wordt een rigoureuze analyse van de small-sample bias in DAE overgelaten aan toekomstig werk.

Het artikel concludeert dat het begrijpen van de aggregatie van onafhankelijke trajecten centraal staat voor de variantiereductie van TD, en dat control variate regressie (via DAE) een principieel pad biedt om variantie verder te reduceren.