Heavy-Ball Q-Learning with Residual Weighting Correction

Technische Samenvatting: Heavy-Ball Q-Learning met Residuele Wegingscorrectie

Probleemstelling
Q-learning is een fundamentele methode in reinforcement learning (RL) voor het leren van optimale Q-functies zonder een expliciet transitiemodel. Hoewel standaard Q-learning convergeert op basis van de contractie-eigenschap van de Bellman-optimaliteitsoperator, kan deze contractie zwak zijn wanneer de kortingsfactor $\gamma$ dicht bij één ligt, wat leidt tot trage convergentie. Bestaande acceleratiemethoden, zoals momentum-gebaseerde updates, PID-type iteraties en rank-one correcties, missen vaak strikte theoretische garanties die bewijzen dat ze standaard Q-learning overtreffen, met name in controle-omgevingen waar het actieve greedistische beleid dynamisch verandert. Een specifieke uitdaging ontstaat bij het toepassen van heavy-ball momentum op Q-learning met niet-uniforme bemonsteringsgewichten: de standaard weegmatrix vernietigt de "gemeenschappelijke eigenvector"-eigenschap (specifiek de vector van enen) die vereist is voor bepaalde spectrale analyses, wat het moeilijk maakt om acceleratie theoretisch te certificeren.

Methodologie
Het artikel stelt een Corrected Heavy-Ball Q-Learning (HBCQL) methode voor en vestigt de convergentie- en acceleratie-eigenschappen ervan met behulp van een Switched Linear System (SLS) raamwerk.

1. Residuele Wegingscorrectie (CQL):
   De auteurs introduceren eerst een "gecorrigeerde" Q-learning update (Algoritme 2) om de loss van de gemeenschappelijke eigenvector in standaard gewogen Q-learning aan te pakken. Ze vervangen de standaard diagonale bemonsteringsmatrix $D$ door een correctiematrix $H = \delta \Pi_d + D(I - \Pi_d)$, waarbij $\Pi_d = \mathbf{1}d^\top$. Deze matrix $H$ is ontworpen zodanig dat deze de constante vector $\mathbf{1}$ naar een scalaire veelvoud van zichzelf afbeeldt ($H\mathbf{1} = \delta\mathbf{1}$), waardoor een gemeenschappelijke eigenvector voor de gemiddelde dynamica van het algoritme wordt hersteld. Deze correctie behoudt het fixpunt $Q^\star$ terwijl het een specifieke structurele decompositie mogelijk maakt.

2. Heavy-Ball Momentum:
   De methode breidt de gecorrigeerde Q-learning uit door een heavy-ball momentumterm $\eta(Q_k - Q_{k-1})$ toe te voegen (Algoritme 3). Dit transformeert de eerste-orde recursie in een tweede-orde systeem.

3. SLS en Joint Spectral Radius (JSR) Analyse:
   Het kernanalytische instrument is de representatie van de Q-learning foutdynamica als een Switched Linear System. Het schakelsignaal wordt bepaald door de greedy actie-selectie in de Bellman-operator. De convergentiesnelheid wordt gekarakteriseerd door de Joint Spectral Radius (JSR) van de geassocieerde familie van schakelmatrices.

   • Decompositie: De auteurs decomponeren de toestandsruimte in de subruimte gespannen door de gemeenschappelijke eigenvector (of invariante subruimte in het heavy-ball geval) en de orthogonale complement van deze subruimte.
   • Acceleratiemechanisme: De analyse toont aan dat de JSR van het volledige systeem de maximum is van de JSR van het geprojecteerde systeem (orthogonaal aan de gemeenschappelijke richting) en de spectrale radius van de dynamica langs de gemeenschappelijke richting. De correctiematrix $H$ maakt het mogelijk om de dynamica langs de gemeenschappelijke richting onafhankelijk te tunen via de parameter $\delta$. De heavy-ball term $\eta$ kan vervolgens worden gebruikt om de convergentie langs deze specifieke richting te versnellen zonder de geprojecteerde dynamica negatief te beïnvloeden, mits $\eta$ voldoende klein is.

4. Extensie naar Lineaire Functie-approximatie:
   Het raamwerk wordt uitgebreid naar lineaire functie-approximatie (LQL). Een vergelijkbare correctiematrix $G$ wordt geconstrueerd in de feature-ruimte om de existentie van een gemeenschappelijke eigenvectorrichting te waarborgen (gespannen door een vector $c$ waarvoor $\Phi c = \mathbf{1}$). Dezelfde SLS en JSR analyse levert analoge convergentie- en acceleratie-resultaten op.

Belangrijkste Bijdragen

• Corrected Q-Learning (CQL): De voorstel van een structurele correctie aan de Q-learning update die de gemeenschappelijke eigenvector-eigenschap herstelt voor niet-uniforme bemonstering, wat een rigoureuze spectrale analyse mogelijk maakt.
• Theoretische Acceleratiegarantie: De afleiding van voldoende voorwaarden (Assumpties 4.1, 4.2 en 5.1) waaronder de HBCQL-methode een strikt kleinere JSR heeft dan zowel de standaard Q-learning als de gecorrigeerde Q-learning (zonder momentum). Dit biedt een "gecertificeerde snelheid" voor acceleratie in een specifieke analytisch identificeerbare richting.
• SLS/JSR Raamwerk: De toepassing van Switched Linear Systems en Joint Spectral Radius analyse op Q-learning, wat een complementair perspectief biedt op standaard contractie-argumenten. Deze aanpak behandelt expliciet het schakelende karakter van het greedy beleid.
• Extensie naar Functie-approximatie: Generalisatie van de correctie en de acceleratietheorie naar lineaire functie-approximatie-omgevingen.

Resultaten

• Convergentie: Het artikel bewijst dat onder de gestelde assumpties de fout-recursie uniform exponentieel convergeert naar nul (of naar een ruis-nabijheid in het stochastische geval) met een snelheid die begrensd wordt door de JSR.
• Acceleratie: Theoretische analyse (Theorem 5.1 en 10.1) demonstreert dat voor kleine momentumparameters $\eta$, de JSR van het heavy-ball gecorrigeerde systeem strikt kleiner is dan die van de standaard of gecorrigeerde baseline.
• Numerieke Illustraties:
  • In een deterministische tabulaire setting bereikte HBCQL een relatieve foutdrempel aanzienlijk sneller dan CQL.
  • In een stochastische tabulaire setting verminderde HBCQL de mediane tijd om een specifieke foutdrempel te bereiken vergeleken met zowel standaard Q-learning als CQL.
  • In lineaire functie-approximatie settings (zowel deterministisch als stochastisch), presteerde de heavy-ball gecorrigeerde methode (HBCLQL) consequent beter dan de standaard en gecorrigeerde lineaire Q-learning methoden in termen van convergentiesnelheid.

Betekenis en Claims
Het artikel claimt een precieze certificering van acceleratie te bieden in één analytisch identificeerbare richting, in plaats van een volledige-richting acceleratietheorema. De auteurs benadrukken dat de bijdrage een theoretische garantie is voor een specifieke geometrische richting, wat nieuw inzicht biedt in de geometrie van heavy-ball Q-learning.

Het werk onderscheidt zich van de bestaande momentum-gebaseerde literatuur door:

1. Te focussen op de controle-omgeving (waar het beleid verandert) in plaats van enkel op policy evaluatie.
2. Het gebruik van SLS en JSR analyse in plaats van vaste-beleid spectrale argumenten of louter stochastische benaderingsgrenzen.
3. Het bieden van een structurele correctie die de acceleratie-analyse hanteerbaar maakt voor niet-uniforme bemonstering, een scenario waarin standaard heavy-ball Q-learning een gebrek aan een gemeenschappelijke eigenvector vertoont.

De auteurs merken op dat de acceleratiegarantie voorwaardelijk is op de "projected gap" assumptie (dat de geprojecteerde dynamica sneller zijn dan de gemeenschappelijke richting dynamica) en kleine momentumparameters. Zij beweren geen universele acceleratie voor alle parameterkeuzes of alle MDP's, maar identificeren een regime waarin de methode theoretisch gegarandeerd sneller is. De analyse wordt primair uitgevoerd op deterministische gemiddelde dynamica, met extensies naar stochastische settings via standaard conditional-mean argumenten.