Chapter 1 of 8: Before the lecture
Levine uses the simulation lemma to show tabular model-based RL error grows quadratically in the horizon.
Sample complexity in reinforcement learning theory asks how far an algorithm's learned values fall from optimal given a finite number of samples. Levine sets aside exploration by assuming a generative model, then analyses a tabular model-based method that estimates transition probabilities by counting. Hoeffding's inequality and a total variation bound show the estimated dynamics concentrate at a rate of . The simulation lemma, with a linear-algebraic form of the Bellman evaluation operator whose infinity norm is bounded by , turns model error into Q-function error. The result bounds policy suboptimality, with error quadratic in the effective horizon. The session assumes Markov Decision Processes, Bellman equations, basic probability and matrix norms, and draws on the Agarwal, Jiang, Kakade and Sun textbook.
Sample complexity in reinforcement learning theory asks how far an algorithm's learned values fall from optimal given a finite number of samples. Levine sets aside exploration by assuming a generative model, then analyses a tabular model-based method that estimates transition probabilities by counting. Hoeffding's inequality and a total variation bound show the estimated dynamics concentrate at a rate of . The simulation lemma, with a linear-algebraic form of the Bellman evaluation operator whose infinity norm is bounded by , turns model error into Q-function error. The result bounds policy suboptimality, with error quadratic in the effective horizon. The session assumes Markov Decision Processes, Bellman equations, basic probability and matrix norms, and draws on the Agarwal, Jiang, Kakade and Sun textbook.
RL Theory Textbook
This lecture
Lecture 50 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