Dynamic approaches for stochastic gradient methods in reinforcement learning

Klein, Sara

PDF
Doktorarbeit-SaraKlein-Druckversion.pdf - Veröffentlichte Version
Download (2MB)

URN:	urn:nbn:de:bsz:180-madoc-685892
Dokumenttyp:	Dissertation
Erscheinungsjahr:	2024
Ort der Veröffentlichung:	Mannheim
Hochschule:	Universität Mannheim
Gutachter:	Döring, Leif
Datum der mündl. Prüfung:	20 Dezember 2024
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Stochastik (Juniorprofessur) (Döring 2015-2016)
Fachgebiet:	510 Mathematik
Freie Schlagwörter (Englisch):	Reinforcement Learning , Stochastic Gradient Methods , Policy Gradient
Abstract:	This work addresses the convergence behaviour of first-order optimization methods in the context of reinforcement learning. Specifically, we analyse the vanilla Policy Gradient (PG) method under softmax parametrization. Initially, we focus on Markov Decision Processes (MDPs) with finite-time horizons, demonstrating that the convergence rate of vanilla PG exhibits an unfavorable and imprecisely determinable dependence on the time horizon. To resolve this issue, we introduce a combination of dynamic programming and policy gradient called finite-time dynamic policy gradient. The use of the dynamic approach much better exploits the structure of the Markovian problem which is reflected in an improved, explicit dependence of the convergence rate on all relevant model parameters. In the second part of this thesis, we extend this concept to discounted MDPs with an infinite-time horizon, where the convergence rate in vanilla PG cannot be explicitly determined with respect to the effective horizon. For the transferred dynamic PG method, we once again establish improved and explicit convergence guarantees. In the third part of this thesis, we analyze the convergence of stochastic gradient methods independently of reinforcement learning. Under the assumption of (weak) gradient domination, we derive almost sure convergence rates in both the global and local settings. The new results find applications in the optimization of analytical neural networks, as well as in the previously discussed classical and dynamical PG methods under softmax parametrization.
Übersetzung des Abstracts:	Diese Arbeit beschäftigt sich mit dem Konvergenzverhalten von Gradientenverfahren erster Ordnung im Kontext von Reinforcement Learning. Dazu wird das klassische Policy-Gradient (PG) Verfahren unter Softmax-Parametrisierung analysiert. Zunächst betrachten wir Markov-Entscheidungsprobleme (MDPs) mit endlichem Zeithorizont und zeigen, dass die Konvergenzrate des PG-Verfahrens eine ungünstige, nicht genau zu bestimmende Abhängigkeit vom Zeithorizont aufweist. Zur Lösung wird Dynamic Programming in das bestehende Verfahren integriert. Der dynamische Ansatz nutz die Markovsche Struktur des MDPs aus und liefert eine verbesserte, explizite Abhängigkeit der Konvergenzrate von allen beteiligten Modellparametern. Im zweiten Teil der Arbeit wird dieses Konzept auf MDPs mit unendlichem Zeithorizont übertragen. Statt des deterministischen Zeithorizonts spielt der erwartete Zeithorizont des unendlichen Problems, abhängig vom Diskontierungsfaktor, eine analoge Rolle. Für das dynamische PG-Verfahren werden erneut bessere und explizite Konvergenzgarantien bewiesen. Im dritten Teil der Arbeit analysieren wir die Konvergenz stochastischer Gradientenmethoden losgelöst vom Reinforcement Learning. Unter der Annahme (schwach) dominierter Gradienten werden fast sichere Konvergenzraten im globalen und lokalen Setting hergeleitet. Die neuen Resultate finden Anwendung in der Optimierung analytischer neuronaler Netze sowie in den zuvor diskutierten klassischen und dynamischen PG-Verfahren unter Softmax-Parametrisierung. (Deutsch)