Opening Towards a Statistical Foundation for Reinforcement Learning
Towards a Statistical Foundation for Reinforcement Learning
- Length
- 1 h
- Level
- Graduate
- Recorded
- UC Berkeley2023
Chapter 1 of 5: Theoretical foundations of reinforcement learning
Zanette sets exponential lower bounds for RL with function approximation against problem-dependent regret.
Statistical foundations of reinforcement learning rest on regret, sample complexity and the limits of learning from fixed data, as Zanette shows in UC Berkeley's CS 285. He starts from regret, the cumulative loss against an optimal policy, and worst-case tabular bounds by Jaksch et al. ('10) and Azar et al. ('17). Problem-dependent measures then show that weak memory or local dynamics, as in contextual bandits, make problems easier. With function approximation, sequential decision-making can be exponentially harder than supervised learning as the horizon grows. Offline learning is analysed through distribution shift and coverage coefficients, trading policy value against estimation uncertainty, with Markov decision processes and concentration inequalities assumed.
Statistical foundations of reinforcement learning rest on regret, sample complexity and the limits of learning from fixed data, as Zanette shows in UC Berkeley's CS 285. He starts from regret, the cumulative loss against an optimal policy, and worst-case tabular bounds by Jaksch et al. ('10) and Azar et al. ('17). Problem-dependent measures then show that weak memory or local dynamics, as in contextual bandits, make problems easier. With function approximation, sequential decision-making can be exponentially harder than supervised learning as the horizon grows. Offline learning is analysed through distribution shift and coverage coefficients, trading policy value against estimation uncertainty, with Markov decision processes and concentration inequalities assumed.
Systematic understanding of easy / hard problems
Fundamental statistical limits
Learning from historical data

This lecture
Lecture 64 of 73 of Deep Reinforcement Learning.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in
Algorithms with guarantees that apply to any problem
Jaksch et al., '10
Bartlett et al., '12
Dann and Brunskill, '15
Azar et al., '17
Dann et al., '19
Zanette and Brunskill '19
Schulman et al., 2017
Szepesvári and Munos, 2005
Yang and Wang, 2019
Cheng and Jiang, 2019
Duan and Wang, 2020
Zanette, ICML 2021 [long oral]
Zanette, ICML 2021
ICML 2021 (long oral)
Information-theoretic lower bound
Wang, Foster, Kakade, 2021
Weisz, Amortila, Szepesvári, 2021
Zanette et al. NeurIPS '21
Zanette and Wainwright, NeurIPS '22 (long oral)
Xie, Cheng, Jiang, Mineiro, Agarwal, 2021
Uheara and Sun, 2021
Jin et al. '21, Liu et al. '20, Yin et al. '21, Rashidinejad et al. '21, Kidambi et al. '20, Yu et al. '20
Zanette and Brunskill, ICML '19
Zanette, ICML '21 (long oral)
Zanette, Wainwright, Brunskill, NeurIPS '21