R-GTD: A Geometric Analysis of Gradient Temporal-Difference Learning in Singular Regimes

Technische Samenvatting: R-GTD: Een Geometrische Analyse van Gradient Temporal-Difference Learning in Singuliere Regimes

Probleemstelling
Gradient Temporal-Difference (GTD) leeralgoritmen, met name GTD2, zijn gevestigde methoden voor off-policy beleidsbeoordeling met lineaire functiebenadering. Ze minimaliseren de Mean-Square Projected Bellman Error (MSPBE) om een benadering van de waardenfunctie te vinden die voldoet aan de Bellman-vergelijking binnen een kenmerkruimte. De theoretische convergentiegaranties van bestaande GTD-methoden berusten echter op een restrictieve aanname: de Feature Interaction Matrix (FIM), gedefinieerd als $\Phi^\top D_\beta (\gamma P^\pi - I) \Phi$, moet niet-singulier zijn. In de praktijk kan de FIM singulier of bijna singulier (ill-geconditioneerd) worden, wat leidt tot instabiliteit, divergentie of verslechterde prestaties. Hoewel eerdere werken hebben geprobeerd dit aan te pakken via regularisatie, hangen hun theoretische garanties vaak af van andere sterk restrictieve voorwaarden, zoals het beperken van de optimale oplossing tot de oorsprong of het aannemen van globale niet-singulariteit om foutgrenzen af te leiden. Bovendien blijft de geometrische relatie tussen geregelde oplossingen en de oorspronkelijke GTD2-oplossingsset in singuliere regimes onverkend.

Methodologie
De auteurs stellen R-GTD (Regularized Gradient Temporal-Difference) voor, een nieuw algoritme afgeleid van een herformulering van het optimalisatiedoel. De kernmethodologie omvat de volgende stappen:

1. Herformulering van het Doel: De auteurs breiden het beperkte optimalisatieprobleem van GTD2 uit door een hulpvariabele (slack variable) $w$ en een kwadratische strafterm in te voeren. Dit leidt tot een geregelde optimalisatieprobleem (Probleem 4) dat een gewogen som minimaliseert van de geprojecteerde Bellman-fout en een term die de hulpvariabele betreft.
2. Zadelpunt-formulering: Dit beperkte probleem wordt herschreven als een convex-concaaf min-max zadelpuntprobleem (Probleem 5) met behulp van een Lagrangiaan-functie. De Lagrangiaan blijkt sterk convex te zijn in de priraalvariabelen ($\theta, w$) en concaaf in de duale variabele ($\lambda$), wat het bestaan van een uniek zadelpunt garandeert, zelfs wanneer de FIM singulier is.
3. Afleiding van het Algoritme: Door Primal-Dual Gradient Dynamics (PDGD) toe te passen op de Lagrangiaan, leiden de auteurs de R-GTD-updateregels af (Algoritme 1). Deze regels incorporeren importance sampling voor off-policy data en updaten drie parameters: de gewichten van de waardenfunctie ($\theta$), de hulpvariabele ($w$) en de duale variabele ($\lambda$).
4. Geometrische Analyse: Het artikel biedt een rigoureuze geometrische analyse van het oplossingsgedrag. Het karakteriseert de R-GTD-oplossing als een verstoring van de GTD2-oplossingsset. Specifiek analyseert het het limietgedrag naarmate de regularisatieparameter $c \to \infty$, met onderscheid tussen niet-singuliere en singuliere gevallen.

Belangrijkste Bijdragen
Het artikel levert drie primaire bijdragen:

• Verwijdering van Aannames over Niet-Singulariteit: R-GTD garandeert convergentie naar een unieke oplossing zonder dat de FIM niet-singulier hoeft te zijn. In tegenstelling tot eerdere geregelde methoden die extra restrictieve voorwaarden opleggen om singulariteiten te behandelen, bereikt R-GTD dit door zijn specifieke formulering zonder extra aannames.
• Geometrische Karakterisering en Foutgrenzen: De auteurs bieden een gedetailleerde geometrische analyse van het singuliere regime. Ze stellen expliciete foutgrenzen vast tussen de R-GTD-oplossing en de ware geprojecteerde oplossing. In het singuliere geval bewijzen ze dat de R-GTD-oplossing convergeert naar de orthogonale projectie van de GTD2-oplossingsset op het complement van de nult ruimte van de matrix $G = M^\top B^{-1} M$. Dit verduidelijkt precies welke oplossing binnen de affiene GTD2-set wordt geselecteerd door de regularisatie.
• Empirische Validatie: Het algoritme wordt gevalideerd in situaties waar de FIM strikt singulier is. Experimenten tonen aan dat R-GTD consistent convergeert naar een uniek zadelpuntoplossing met grotere stabiliteit vergeleken met GTD2 en andere geregelde baselines (bijv. Ghiassian et al., 2020; Yu, 2017).

Resultaten

• Convergentie: Theoretische analyse bevestigt dat de continue-tijd dynamiek van R-GTD globaal convergeert naar een uniek zadelpunt. Met behulp van de Ordinary Differential Equation (ODE)-methode wordt aangetoond dat de stochastische iteraten van Algoritme 1 met waarschijnlijkheid één convergeren naar deze oplossing.
• Foutgrenzen: In het niet-singuliere geval wordt de fout tussen de R-GTD-oplossing en de GTD2-oplossing begrensd door $O(1/c)$. In het singuliere geval convergeert de R-GTD-oplossing naar een specifiek element van de GTD2-affiene oplossingsset (die welke orthogonaal is op de nult ruimte van $G$) met een foutgrens van $O(1/c)$.
• Experimentele Prestaties: In experimenten met singuliere MDP's, Baird's tegenvoorbeeld en stochastische omgevingen (Frozen Lake) onderdrukt R-GTD consistent de nult-ruimtecomponent die instabiliteit veroorzaakt in standaard GTD2. Het bereikt een lagere finale fout en een verminderde variantie vergeleken met basismethoden, met name wanneer de FIM ill-geconditioneerd is. Sensitiviteitsanalyse suggereert dat intermediaire waarden van de regularisatieparameter $c$ (bijv. $c \in [1, 4]$) de beste afweging bieden tussen stabiliteit en bias.

Betekenis
Het artikel beweert dat R-GTD een theoretische kloof overbrugt in het begrijpen van GTD-learning onder singuliere omstandigheden. Door de aanname van niet-singulariteit te verwijderen, biedt het een robuust kader voor off-policy beoordeling in scenario's waar kenmerkinteracties degenereren. De geometrische analyse biedt een precies inzicht in hoe regularisatie een unieke oplossing selecteert uit de potentieel oneindige set van GTD2-oplossingen, waarbij stabiliteit wordt gewaarborgd zonder de kerntheoretische structuur van GTD2 te offeren. De auteurs merken op dat de huidige analyse beperkt is tot lineaire functiebenadering en asymptotische convergentie, waardoor niet-lineaire benadering en garanties voor eindige tijd worden gelaten als richtingen voor toekomstig werk.