Theory essentials
Where the guarantees come from. Bandit regret is on the Foundations line, where it is read early; this line is the depth behind it, taken to taste.
What you will learn
By now you have used TD, policy gradients and exploration bonuses on faith. Their guarantees exist, and knowing where they hold tells you when an algorithm's failure is a bug and when it is a theorem.
Szepesvári's compact overview, the theory monograph on sample complexity, PAC-MDP and exploration, and the convergence results for TD with function approximation and for policy gradients.
You can state the conditions under which the core algorithms converge, and recognise which of them your agent violates.
Szepesvári, 2010
Algorithms for Reinforcement Learning
Compact, rigorous overview of core algorithms and their analysis.
Reference.
Resources
Agarwal, Jiang, Kakade & Sun, working monograph 2019–2022
Reinforcement Learning: Theory and Algorithms
Sample complexity, PAC-MDP, policy-gradient convergence, exploration theory.
The modern theory reference.
Resources
Tsitsiklis & Van Roy 1997; Jaakkola, Jordan & Singh 1994
Convergence of TD and Q-learning
TD with function approximation and stochastic-approximation convergence.
Why the deadly triad bites.
Resources
- Tsitsiklis & Van Roy 1997 (paper)
- Jaakkola, Jordan & Singh 1994 (paper)
Agarwal, Kakade, Lee & Mahajan, JMLR 2021
On the Theory of Policy Gradient Methods
Convergence of policy-gradient methods.
Guarantees behind Phase 3.