Chapter 1 of 2: Theoretical analysis of fitted Q-iteration
Fitted Q-iteration admits an error bound that splits into a sampling term and an approximation term. Levine, in session 51 of UC Berkeley's CS 285, models exact Q-iteration with the Bellman optimality operator. He then defines an empirical operator built from sample averages of rewards and transitions. Hoeffding's inequality and a total variation bound control the sampling error, which shrinks with the square root of sample size. Unrolling the contraction of the Bellman backup in the infinity norm shows initialization effects vanish, leaving error that scales quadratically with the effective horizon. The argument follows the RL Theory Textbook by Agarwal, Jiang, Kakade and Sun, on slides by Aviral Kumar.

Your comment is kept while you sign up.Sign in
Bounds the asymptotic error of fitted Q-iteration and shows it grows quadratically with the effective horizon.
Fitted Q-iteration admits an error bound that splits into a sampling term and an approximation term. Levine, in session 51 of UC Berkeley's CS 285, models exact Q-iteration with the Bellman optimality operator. He then defines an empirical operator built from sample averages of rewards and transitions. Hoeffding's inequality and a total variation bound control the sampling error, which shrinks with the square root of sample size. Unrolling the contraction of the Bellman backup in the infinity norm shows initialization effects vanish, leaving error that scales quadratically with the effective horizon. The argument follows the RL Theory Textbook by Agarwal, Jiang, Kakade and Sun, on slides by Aviral Kumar.
RL Theory Textbook
This lecture
Lecture 51 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.