Convergence Guarantees of Model-free Policy Gradient Methods for LQR with Stochastic Data

1. Probleemstelling

Het artikel richt zich op het Lineair Kwantitatief Regelaar (LQR) probleem voor systemen die blootgesteld zijn aan additieve stochastische ruis (Gaussische ruis). Het centrale probleem is het optimaliseren van een beleidsfunctie (policy) wanneer de systeemdynamica (de matrices $A$ en $B$) onbekend zijn.

In tegenstelling tot eerdere werken die zich richtten op deterministische systemen of systemen met bounded ruis, analyseert dit werk scenario's waar de ruis ongebonden is (zoals Gaussische ruis). Dit introduceert twee grote uitdagingen voor model-vrije (model-free) methoden:

1. Onnauwkeurige gradiëntschatting: Omdat de dynamica onbekend is, moeten gradiënten worden geschat via nulde-orde optimalisatie (zeroth-order optimization) op basis van trajectdata. Bij aanwezigheid van ruis zijn deze schattingen onnauwkeurig.
2. Convergentiegaranties: Bestaande theorieën voor beleidsgradiënt (Policy Gradient - PG) methoden gaan vaak uit van exacte gradiënten of bounded ruis. Er ontbreekt een uitgebreide analyse die de onzekerheid van de schattingen kwantificeert en de propagatie van deze fouten door het algoritme analyseert, specifiek voor oneindige horizon LQR met ongebonden ruis.

2. Methodologie

De auteurs gebruiken een combinatie van controletheorie en stochastische optimalisatie-theorie:

• Probleemformulering: Het doel is het minimaliseren van de gemiddelde oneindige-horizon kostenfunctie $C(K)$ voor een lineair systeem met ruis. De kostenfunctie is niet-convex, maar voldoet aan de eigenschap van gradiënt-dominantie (gradient domination), wat cruciaal is voor het bewijzen van globale convergentie.
• Model-Vrije Schatting:
  • In plaats van het systeem te identificeren, gebruiken ze nulde-orde optimalisatie. Hierbij wordt de gradiënt geschat door de kostenfunctie te evalueren bij kleine perturbaties van de beleidsmatrix $K$.
  • Ze introduceren een event-based analyse om om te gaan met de ongebonden aard van de ruis. In plaats van aan te nemen dat trajecten strikt bounded zijn, analyseren ze de waarschijnlijkheid dat de toestanden binnen bepaalde grenzen blijven.
• Adaptieve Stapgrootte: Er wordt een adaptieve stapgrootte-scheme voorgesteld die afhankelijk is van de huidige kosten $C(K_i)$. Dit staat in contrast met vaste stapgroottes in eerdere werken.
• Variance Reduction: Om de sample complexiteit (het aantal benodigde simulaties/rollouts) te verminderen, wordt een variance reduction techniek geïntroduceerd. Dit gebeurt door een "baseline" functie te gebruiken die de verwachte kosten schat, waardoor de variatie in de gradiëntschatting wordt verminderd.

3. Belangrijkste Bijdragen

1. Foutgrenzen voor Schattingen:
   De auteurs leiden nieuwe finite-sample foutgrenzen af voor de geschatte gradiënt ($\hat{\nabla}C(K)$) en de geschatte covariantiematrix ($\hat{\Sigma}_K$). Deze grenzen houden expliciet rekening met vier bronnen van fout:

   • Ruis in de data ($\epsilon_d$).
   • Beperkte lengte van de rollouts ($\epsilon_l$).
   • Beperkt aantal rollouts in de nulde-orde schatting ($\epsilon_n$).
   • Bias door het gladmaken (smoothing) van de functie ($\epsilon_r$).

2. Globale Convergentiegaranties:
   Er worden probabilistische convergentiegaranties bewezen voor zowel Policy Gradient Descent (PGD) als Natural Policy Gradient (NPG) methoden.

   • Het bewijs toont aan dat de algoritmen convergeren naar een oplossing binnen een gewenste nauwkeurigheidsmarge $\epsilon$, met een bepaalde waarschijnlijkheid $1-\delta$.
   • De analyse toont aan dat de convergentie snelheid lineair is, maar wordt vertraagd door de schattingsfouten (gekwantificeerd door een parameter $\sigma$).

3. Variance Reduction en Sample Complexiteit:
   De paper introduceert en analyseert een variance reduction techniek specifiek voor deze context. Ze bewijzen dat het gebruik van een geschatte baseline leidt tot een provable verbetering in de sample complexiteit. Dit betekent dat minder data (rollouts) nodig is om dezelfde nauwkeurigheid te bereiken, vooral bij hoge ruisniveaus.

4. Adaptieve Stapgrootte Analyse:
   Er wordt aangetoond dat adaptieve stapgroottes (die afnemen naarmate de ruis toeneemt of de kosten dalen) beter presteren dan vaste stapgroottes. Dit voorkomt divergentie bij hoge ruisniveaus en versnelt de convergentie in de vroege fasen.

4. Resultaten

• Theoretische Resultaten:

  • De paper levert gesloten formules voor parameters zoals de exploratiestraal ($r$), de rollout-lengte ($l$) en het aantal rollouts ($n$) die nodig zijn om een specifieke foutmarge en waarschijnlijkheid te garanderen.
  • Het bewijst dat model-vrije PG-methoden met stochastische data kwalitatief vergelijkbare convergentiegaranties hebben als in ruisvrije scenario's, maar met een straf in de vorm van:
    • Een groter aantal benodigde samples voor een gegeven nauwkeurigheid.
    • Een kleiner bereik van toegestane stapgroottes.
    • Een langzamere convergentiesnelheid.

• Numerieke Simulaties:

  • Simulaties bevestigen dat bij hoge ruisniveaus een te grote stapgrootte leidt tot divergentie, terwijl een adaptieve (kleinere) stapgrootte convergentie herstelt.
  • De variance reduction techniek toont een duidelijke prestatieverbetering bij hoge ruisniveaus, wat overeenkomt met de theoretische voorspellingen.
  • NPG met adaptieve stapgroottes convergeert sneller dan met vaste stapgroottes en behaalt vergelijkbare nauwkeurigheid ondanks toenemende ruis.

5. Betekenis en Impact

Deze studie is significant omdat het een ontbrekende schakel vormt in de theorie van reinforcement learning voor controleproblemen:

• Robuustheid: Het karakteriseert de robuustheid van model-vrije PG-methoden tegenover stochastische ruis, een veelvoorkomend fenomeen in de echte wereld.
• Praktische Richtlijnen: Het biedt ingenieurs concrete richtlijnen voor het afstellen van algoritme-parameters (zoals stapgrootte en aantal samples) op basis van het verwachte ruisniveau van het systeem.
• Fundamentele Vooruitgang: Het is een van de eerste werken dat een holistische analyse biedt die de onzekerheid van de nulde-orde schatting koppelt aan de propagatie door het algoritme voor oneindige horizon LQR, inclusief probabilistische garanties voor ongebonden ruis.

Kortom, het werk bewijst dat model-vrije optimalisatie voor LQR met ruis theoretisch onderbouwd en praktisch haalbaar is, mits de parameters zorgvuldig worden gekozen op basis van de afgeleide foutgrenzen.