Accelerated algorithms for temporal difference learning methods
dc.contributor.advisor | Bacon, Pierre-Luc | |
dc.contributor.author | Rankawat, Anushree | |
dc.date.accessioned | 2023-08-03T18:24:56Z | |
dc.date.available | NO_RESTRICTION | fr |
dc.date.available | 2023-08-03T18:24:56Z | |
dc.date.issued | 2023-06-19 | |
dc.date.submitted | 2022-12 | |
dc.identifier.uri | http://hdl.handle.net/1866/28496 | |
dc.subject | Temporal difference learning | fr |
dc.subject | Stochastic Approximation | fr |
dc.subject | Accelerated methods | fr |
dc.subject | Momentum methods | fr |
dc.subject | Reinforcement learning | fr |
dc.subject | Approximate Dynamic Programming | fr |
dc.subject | Function approximation | fr |
dc.subject | Conservation laws | fr |
dc.subject | Convergence rates | fr |
dc.subject | Machine learning | fr |
dc.subject | Méthodes des différences temporelles | fr |
dc.subject | Approximation Stochastique | fr |
dc.subject | Méthodes accélérées | fr |
dc.subject | Méthodes de quantité de mouvement | fr |
dc.subject | Apprentissage par renforcement | fr |
dc.subject | Programmation dynamique approchée | fr |
dc.subject | Lois de conservation | fr |
dc.subject | Taux de convergence | fr |
dc.subject | Apprentissage automatique | fr |
dc.subject.other | Artificial intelligence / Intelligence artificielle (UMI : 0800) | fr |
dc.title | Accelerated algorithms for temporal difference learning methods | fr |
dc.type | Thèse ou mémoire / Thesis or Dissertation | |
etd.degree.discipline | Informatique | fr |
etd.degree.grantor | Université de Montréal | fr |
etd.degree.level | Maîtrise / Master's | fr |
etd.degree.name | M. Sc. | fr |
dcterms.abstract | L'idée centrale de cette thèse est de comprendre la notion d'accélération dans les algorithmes d'approximation stochastique. Plus précisément, nous tentons de répondre à la question suivante : Comment l'accélération apparaît-elle naturellement dans les algorithmes d'approximation stochastique ? Nous adoptons une approche de systèmes dynamiques et proposons de nouvelles méthodes accélérées pour l'apprentissage par différence temporelle (TD) avec approximation de fonction linéaire : Polyak TD(0) et Nesterov TD(0). Contrairement aux travaux antérieurs, nos méthodes ne reposent pas sur une conception des méthodes de TD comme des méthodes de descente de gradient. Nous étudions l'interaction entre l'accélération, la stabilité et la convergence des méthodes accélérées proposées en temps continu. Pour établir la convergence du système dynamique sous-jacent, nous analysons les modèles en temps continu des méthodes d'approximation stochastique accélérées proposées en dérivant la loi de conservation dans un système de coordonnées dilaté. Nous montrons que le système dynamique sous-jacent des algorithmes proposés converge à un rythme accéléré. Ce cadre nous fournit également des recommandations pour le choix des paramètres d'amortissement afin d'obtenir ce comportement convergent. Enfin, nous discrétisons ces ODE convergentes en utilisant deux schémas de discrétisation différents, Euler explicite et Euler symplectique, et nous analysons leurs performances sur de petites tâches de prédiction linéaire. | fr |
dcterms.abstract | The central idea of this thesis is to understand the notion of acceleration in stochastic approximation algorithms. Specifically, we attempt to answer the question: How does acceleration naturally show up in SA algorithms? We adopt a dynamical systems approach and propose new accelerated methods for temporal difference (TD) learning with linear function approximation: Polyak TD(0) and Nesterov TD(0). In contrast to earlier works, our methods do not rely on viewing TD methods as gradient descent methods. We study the interplay between acceleration, stability, and convergence of the proposed accelerated methods in continuous time. To establish the convergence of the underlying dynamical system, we analyze continuous-time models of the proposed accelerated stochastic approximation methods by deriving the conservation law in a dilated coordinate system. We show that the underlying dynamical system of our proposed algorithms converges at an accelerated rate. This framework also provides us recommendations for the choice of the damping parameters to obtain this convergent behavior. Finally, we discretize these convergent ODEs using two different discretization schemes, explicit Euler, and symplectic Euler, and analyze their performance on small, linear prediction tasks. | fr |
dcterms.language | eng | fr |
UdeM.ORCIDAuteurThese | 0000-0001-9973-0027 | fr |
Files in this item
This item appears in the following Collection(s)
This document disseminated on Papyrus is the exclusive property of the copyright holders and is protected by the Copyright Act (R.S.C. 1985, c. C-42). It may be used for fair dealing and non-commercial purposes, for private study or research, criticism and review as provided by law. For any other use, written authorization from the copyright holders is required.