# Stochastic Approximation: Theory and Applications

- Institution: IISc Bangalore
- Department: Computer Science and Engineering
- Teacher: Prof. Gugan Chandrashekhar Mallika Thoppe
- Level: Graduate
- Language: English
- Subjects: Computer science, Engineering
- Source: [NPTEL](https://nptel.ac.in/courses/106108700)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/106108700)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

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

1. [Overview of Stochastic Approximation](https://invisiblenetwork.ai/learn/nptel/106108700/7ecbb68defb7) (YouTube)
2. [Estimating the Mean of a Random Variable](https://invisiblenetwork.ai/learn/nptel/106108700/c39186bc2c3d) (YouTube)
3. [Estimating change rates of webpages](https://invisiblenetwork.ai/learn/nptel/106108700/2c5d22e7ae2f) (YouTube)
4. [An Introduction to Reinforcement Learning.](https://invisiblenetwork.ai/learn/nptel/106108700/5aa8cebd678a) (YouTube)
5. [Policy Evaluation in Reinforcement Learning](https://invisiblenetwork.ai/learn/nptel/106108700/8faa4e1efe6c) (YouTube)
6. [Probability Spaces- A Measure Theoretic Perspective](https://invisiblenetwork.ai/learn/nptel/106108700/b36116aa0e5d) (YouTube)
7. [Random Variables as Measurable Maps](https://invisiblenetwork.ai/learn/nptel/106108700/aee0b270332d) (YouTube)
8. [Expectation of Random Variable as Lebesgue Integration](https://invisiblenetwork.ai/learn/nptel/106108700/fbcab436b99a) (YouTube)
9. [Conditional Expectation: A Formal Introduction](https://invisiblenetwork.ai/learn/nptel/106108700/e3d62f24c15b) (YouTube)
10. [Properties of Conditional Expectation.](https://invisiblenetwork.ai/learn/nptel/106108700/c5c4c389c026) (YouTube)
11. [Martingales: Definition and Examples](https://invisiblenetwork.ai/learn/nptel/106108700/05f990ae94d0) (YouTube)
12. [Doob’s Uncrossing Lemma](https://invisiblenetwork.ai/learn/nptel/106108700/1502d815f272) (YouTube)
13. [Doob’s Forward Convergence Theorem for Supermartingales](https://invisiblenetwork.ai/learn/nptel/106108700/31755036447f) (YouTube)
14. [$L^2$ Martingales](https://invisiblenetwork.ai/learn/nptel/106108700/e9dcc9d1e308) (YouTube)
15. [Revisiting the Martingale Convergence Theorem via Stopped Processes](https://invisiblenetwork.ai/learn/nptel/106108700/8a4865fe18f0) (YouTube)
16. [Existence and Uniqueness of Solutions to Ordinary Differential Equations](https://invisiblenetwork.ai/learn/nptel/106108700/e3d8c0439a57) (YouTube)
17. [Continuity of ODE Solutions with Respect to Initial Conditions](https://invisiblenetwork.ai/learn/nptel/106108700/4a84bc336a23) (YouTube)
18. [Asymptotic Behaviour of Solutions to ODEs](https://invisiblenetwork.ai/learn/nptel/106108700/2d103e41d11f) (YouTube)
19. [Stability of ODEs and Lyapunov Methods](https://invisiblenetwork.ai/learn/nptel/106108700/f69644e4d8a5) (YouTube)
20. [Foundations of Stochastic Approximation – Assumptions and Key Definitions](https://invisiblenetwork.ai/learn/nptel/106108700/2f579507b83f) (YouTube)
21. [Almost Sure Convergence of Stochastic Approximation Iterates](https://invisiblenetwork.ai/learn/nptel/106108700/19a21b54a9ab) (YouTube)
22. [Concluding the Convergence Proof: Internal Chain Transitivity, Connectedness, and Invariance](https://invisiblenetwork.ai/learn/nptel/106108700/5fbee256206b) (YouTube)
23. [How Stochastic Approximation Iterates Track an ODE: The Key Lemma](https://invisiblenetwork.ai/learn/nptel/106108700/b810b381db92) (YouTube)
24. [Proof of the Key Lemma - Part I](https://invisiblenetwork.ai/learn/nptel/106108700/e50975284c51) (YouTube)
25. [Proof of the Key Lemma - Part II](https://invisiblenetwork.ai/learn/nptel/106108700/5b3c9164a192) (YouTube)
26. [Extensions, Variants, and Applications of Stochastic Approximation](https://invisiblenetwork.ai/learn/nptel/106108700/fadfd9b8788f) (YouTube)
27. [Convergence Rate for Linear Stochastic Approximation - Part 1](https://invisiblenetwork.ai/learn/nptel/106108700/d28e4c9a83f0) (YouTube)
28. [Convergence Rate for Linear Stochastic Approximation - Part 2](https://invisiblenetwork.ai/learn/nptel/106108700/f785cc9f9c33) (YouTube)
29. [Lower Bounds and the Minimax Risk in Estimation](https://invisiblenetwork.ai/learn/nptel/106108700/4ebaaeff7b68) (YouTube)
30. [Stability Requirements in Stochastic Approximation](https://invisiblenetwork.ai/learn/nptel/106108700/8510ac590fc3) (YouTube)
31. [Almost Sure Boundedness of Iterates: Theorem and Example](https://invisiblenetwork.ai/learn/nptel/106108700/530ff96fb0de) (YouTube)
32. [Distributed Estimation of the Mean of a Random Vector](https://invisiblenetwork.ai/learn/nptel/106108700/d016bf3fb9d1) (YouTube)
33. [Robust Distributed Learning under Adversaries](https://invisiblenetwork.ai/learn/nptel/106108700/0e144e9e733c) (YouTube)
34. [Motivation for Stochastic Recursive Inclusion in Distributed Mean Estimation](https://invisiblenetwork.ai/learn/nptel/106108700/3e69ce12514d) (YouTube)
35. [Well-Posedness of Differential Inclusions](https://invisiblenetwork.ai/learn/nptel/106108700/b68ebc54cb8a) (YouTube)
36. [Convergence of Distributed Robust Mean Estimation Iterates through the Lens of Differential Inclusions](https://invisiblenetwork.ai/learn/nptel/106108700/5f28e9284761) (YouTube)
37. [Almost Sure Convergence via Robbins–Siegmund Theorem – Part 1](https://invisiblenetwork.ai/learn/nptel/106108700/f5399a1ceb04) (YouTube)
38. [Almost Sure Convergence via Robbins–Siegmund Theorem – Part 2](https://invisiblenetwork.ai/learn/nptel/106108700/499aa69252e5) (YouTube)
39. [Introduction to Reinforcement Learning and Value Function Approximation](https://invisiblenetwork.ai/learn/nptel/106108700/97e19db17d03) (YouTube)
40. [Temporal Difference Algorithm Through the Lens of Stochastic Approximation](https://invisiblenetwork.ai/learn/nptel/106108700/101678f70663) (YouTube)
41. [How Good Is the TD Solution? Fixed Point Analysis in Linear Approximation](https://invisiblenetwork.ai/learn/nptel/106108700/fc633a7ccb9d) (YouTube)
42. [Almost Sure Convergence Analysis of Temporal Difference Learning via the ODE Method](https://invisiblenetwork.ai/learn/nptel/106108700/31267caa7b7a) (YouTube)
43. [Best Policy Algorithm for Q-Value Functions: A Stochastic Approximation Formulation](https://invisiblenetwork.ai/learn/nptel/106108700/c5c2d9c99120) (YouTube)
44. [Asymptotic Analysis of Q-Learning Algorithm](https://invisiblenetwork.ai/learn/nptel/106108700/dfa9f5a9b5e6) (YouTube)
45. [Asymptotic Behaviour of the Q-Learning Limit ODE — A Switching Systems Perspective](https://invisiblenetwork.ai/learn/nptel/106108700/43e7f71d45a8) (YouTube)
46. [Concluding the Asymptotic Analysis of Q-Learning](https://invisiblenetwork.ai/learn/nptel/106108700/48b5b89db69e) (YouTube)