Learn · NPTEL

Course10610870046 lectures

Stochastic Approximation: Theory and Applications

Prof. Gugan Chandrashekhar Mallika Thoppe · IISc Bangalore

Start with lecture 1 At NPTEL

About

Stochastic approximation refers to a class of iterative algorithms that can locate zeroes or optimal points of functions in scenarios where the function evaluations are compromised by noise. These algorithms are prominently utilized in regression, system identification, adaptive control, and increasingly in reinforcement learning and machine learning. This course will explore the design, theoretical convergence, and convergence rates of these algorithms, with a particular emphasis on applications in reinforcement learning

Intended audience: UG, Masters and Ph.D. students in Computer Science and Engineering/Electronics and Communication Engineerings/Mathematics

Prerequisites: Real analysis, Measure-theoretic Probability, Optimization, Design and Analysis of Algorithms, Ordinary Differential Equations

Lectures

Week 1 Introduction to Stochastic Approximation

  1. Overview of Stochastic Approximation YouTube
  2. Estimating the Mean of a Random Variable YouTube
  3. Estimating change rates of webpages YouTube
  4. An Introduction to Reinforcement Learning. YouTube
  5. Policy Evaluation in Reinforcement Learning YouTube

Week 2 Foundations of Probability for Stochastic Approximation

  1. Probability Spaces- A Measure Theoretic Perspective YouTube
  2. Random Variables as Measurable Maps YouTube
  3. Expectation of Random Variable as Lebesgue Integration YouTube
  4. Conditional Expectation: A Formal Introduction YouTube
  5. Properties of Conditional Expectation. YouTube

Week 3 Understanding Martingales and Their Convergence in Discrete Time

  1. Martingales: Definition and Examples YouTube
  2. Doob’s Uncrossing Lemma YouTube
  3. Doob’s Forward Convergence Theorem for Supermartingales YouTube
  4. $L^2$ Martingales YouTube
  5. Revisiting the Martingale Convergence Theorem via Stopped Processes YouTube

Week 4 Foundations of ODE Analysis: Existence and Stability

  1. Existence and Uniqueness of Solutions to Ordinary Differential Equations YouTube
  2. Continuity of ODE Solutions with Respect to Initial Conditions YouTube
  3. Asymptotic Behaviour of Solutions to ODEs YouTube
  4. Stability of ODEs and Lyapunov Methods YouTube

Week 5 An Ordinary Differential Equation Approach to Stochastic Approximation

  1. Foundations of Stochastic Approximation – Assumptions and Key Definitions YouTube
  2. Almost Sure Convergence of Stochastic Approximation Iterates YouTube
  3. Concluding the Convergence Proof: Internal Chain Transitivity, Connectedness, and Invariance YouTube

Week 6 Stochastic Approximation: The ODE Method - From Iterates to Flow

  1. How Stochastic Approximation Iterates Track an ODE: The Key Lemma YouTube
  2. Proof of the Key Lemma - Part I YouTube
  3. Proof of the Key Lemma - Part II YouTube
  4. Extensions, Variants, and Applications of Stochastic Approximation YouTube

Week 7 Advances in Stochastic Approximation: Linear SA and Its Convergence Rates

  1. Convergence Rate for Linear Stochastic Approximation - Part 1 YouTube
  2. Convergence Rate for Linear Stochastic Approximation - Part 2 YouTube
  3. Lower Bounds and the Minimax Risk in Estimation YouTube

Week 8 Stability of Stochastic Approximation

  1. Stability Requirements in Stochastic Approximation YouTube
  2. Almost Sure Boundedness of Iterates: Theorem and Example YouTube

Week 9 Two-Time Scale Stochastic Recursive Inclusions for Distributed Robust Mean Estimation

  1. Distributed Estimation of the Mean of a Random Vector YouTube
  2. Robust Distributed Learning under Adversaries YouTube
  3. Motivation for Stochastic Recursive Inclusion in Distributed Mean Estimation YouTube
  4. Well-Posedness of Differential Inclusions YouTube

Week 10 Almost Sure Convergence in Distributed Robust Mean Estimation

  1. Convergence of Distributed Robust Mean Estimation Iterates through the Lens of Differential Inclusions YouTube
  2. Almost Sure Convergence via Robbins–Siegmund Theorem – Part 1 YouTube
  3. Almost Sure Convergence via Robbins–Siegmund Theorem – Part 2 YouTube

Week 11 Reinforcement Learning through Stochastic Approximation: The Temporal Difference Algorithm

  1. Introduction to Reinforcement Learning and Value Function Approximation YouTube
  2. Temporal Difference Algorithm Through the Lens of Stochastic Approximation YouTube
  3. How Good Is the TD Solution? Fixed Point Analysis in Linear Approximation YouTube
  4. Almost Sure Convergence Analysis of Temporal Difference Learning via the ODE Method YouTube

Week 12 Q-Learning: Stochastic Approximation Algorithm, and Convergence Analysis

  1. Best Policy Algorithm for Q-Value Functions: A Stochastic Approximation Formulation YouTube
  2. Asymptotic Analysis of Q-Learning Algorithm YouTube
  3. Asymptotic Behaviour of the Q-Learning Limit ODE — A Switching Systems Perspective YouTube
  4. Concluding the Asymptotic Analysis of Q-Learning YouTube

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IISc Bangalore
Department
Computer Science and Engineering
Teacher
Prof. Gugan Chandrashekhar Mallika Thoppe
Level
Graduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed