Technische Samenvatting: Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning

1. Probleemstelling

De centrale vraag in dit onderzoek is het kwantificeren van de finit-time (niet-asymptotische) convergentiesnelheid van de Centrale Limietstelling (CLT) voor twee specifieke structuren: vector-waardige martingaalverschillen en functies van Markov-ketens.

Hoewel de asymptotische efficiëntie van stochastische benaderingsalgoritmen (zoals TD-learning) vaak via de CLT wordt begrepen, is in de machine learning de behoefte aan sample complexity (hoeveel data is er nodig voor een bepaalde nauwkeurigheid?) cruciaal. Bestaande literatuur biedt vaak bounds voor zwakkere afstandsmaten of beperkt zich tot scalaire waarden. Dit paper richt zich op de Wasserstein-afstand voor vector-waardige processen, wat een sterkere en meer toepasbare maatstaf is.

2. Methodologie

De auteur hanteert een drieledige methodologische aanpak:

• Stein's Methode & Lindeberg-decompositie: Om de convergentie naar een multivariate normale verdeling te bewijzen, combineert de auteur de Lindeberg-decompositie met Stein's methode. Er wordt gebruikgemaakt van de regulariteitseigenschappen van de oplossing van de Stein-vergelijking voor vector-waardige willekeurige variabelen (gebaseerd op werk van Gallouët et al. en Fang et al.).
• Poisson-vergelijking: Om de stap te maken van martingalen naar Markov-ketens, wordt de Poisson-vergelijking gebruikt. Hiermee kan een functie van een Markov-keten worden ontbonden in een martingaalverschil plus een 'residue' term (de oplossing van de Poisson-vergelijking), waardoor de CLT-resultaten voor martingalen direct toepasbaar worden op Markov-processen.
• Polyak-Ruppert Averaging Analyse: Voor de toepassing op TD-learning wordt de dynamiek van de algoritme-iteraten geanalyseerd door ze te modelleren als een Markoviaans sprong-lineair systeem. De convergentie van de gemiddelde iteraten ($\bar{\theta}_n$) wordt onderzocht met behulp van stochastische benaderingstechnieken.

3. Belangrijkste Bijdragen

1. Niet-asymptotische CLT voor Martingalen: Een nieuwe bound voor de Wasserstein-afstand tussen een genormaliseerde som van martingaalverschillen en een multivariate normale verdeling, waarbij de impact van de asymptotische covariantie $\Sigma_\infty$ expliciet wordt meegenomen.
2. Niet-asymptotische CLT voor Markov-ketens: De uitbreiding van de martingaal-resultaten naar Markov-ketens (zowel voor eindige toestandsruimtes als algemene toestandsruimtes met Lyapunov-condities), waarbij de convergentiesnelheid wordt gekoppeld aan de ergodische eigenschappen van de keten.
3. Toepassing op TD-learning: Een bewijs van de convergentiesnelheid van de Polyak-Ruppert gemiddelde iteraten in Temporal Difference (TD) learning, waarbij rekening wordt gehouden met Markoviaanse ruis.

4. Belangrijkste Resultaten

• Martingaal CLT (Theorem 1): De convergentie naar de normale verdeling in Wasserstein-afstand wordt beperkt door termen die afhangen van de momenten van de martingaalverschillen en de snelheid waarmee de conditionele covariantie $\Sigma_k$ convergeert naar $\Sigma_\infty$.
• Markov-keten CLT (Theorem 2 & 3):
  • Voor eindige, irreducibele en aperiodieke ketens is de convergentiesnelheid $O(n^{-1/2} \log n)$ (indien derde momenten bestaan) of $O(n^{-\beta/2})$ voor $\beta \in (0,1)$.
  • Voor algemene toestandsruimtes onder een Lyapunov-driftconditie worden vergelijkbare snelheden bereikt.
• TD-learning (Theorem 4): Voor TD-learning met een afnemende stapgrootte $\epsilon_k = 1/(k+1)^\delta$ (met $\delta \in (0.5, 1)$), convergeert de gemiddelde schatting $\bar{\theta}_n$ naar de optimale waarde $\theta^*$ met een snelheid van:
  $$O\left(\max\left(\frac{\sqrt{\log n}}{n^{\delta-0.5}}, \frac{1}{n^{(1-\delta)/2}}\right)\right)$$

5. Significantie

Dit werk is wetenschappelijk significant omdat het een brug slaat tussen de theoretische probabiliteit (Stein's methode) en de praktische statistische leertheorie (Reinforcement Learning).

• Theoretisch: Het biedt een verfijndere analyse van de convergentie van vector-waardige processen dan eerder werk, met name door de focus op de Wasserstein-afstand en de expliciete rol van de asymptotische covariantie.
• Praktisch: Het geeft fundamentele inzichten in de optimalisatie van TD-learning. Het bevestigt dat het middelen van iteraten (averaging) effectief is om de variantie te minimaliseren, en biedt een theoretisch kader om de optimale parameters (zoals de exponent $\delta$ van de stapgrootte) te kiezen voor een snelle convergentie in omgevingen met Markoviaanse ruis.