This page is dedicated to start discussions about the article "Finite-Sample Analysis of Bellman Residual Minimization".
Feel free to post any comment, sugggestion, question, correction, extension... I will enjoy discussing this with you.
- Abstract:
"We consider the Bellman residual minimization approach for solving discounted Markov decision problems, where we assume that a generative model of the dynamics and rewards is available. At each policy iteration step, an approximation of the value function for the current policy is obtained by minimizing an empirical Bellman residual dened on a set of n states drawn i.i.d. from a distribution \mu, the immediate rewards, and the next states sampled from the model. Our main result is a generalization bound for the Bellman residual in linear approximation spaces. In particular, we prove that the empirical Bellman residual approaches the true (quadratic) Bellman residual in \mu-norm with a rate of order O(1/\sqrt{n}). This result implies that minimizing the empirical residual is indeed a sound approach for the minimization of the true Bellman residual which guarantees a good approximation of the value function for each policy. Finally, we derive performance bounds for the resulting approximate policy iteration algorithm in terms of the number of samples n and a measure of how well the function space is able to approximate the sequence of value functions."
- Discussion:
We have a poorer estimation rate of O(1/\sqrt{n}) instead of O(1/n) and it is an open question to whether an improved rate for Bellman residuals can be obtained. The main reason is explained in Remark 1 p.8.
- Future work:
Improve the rate of convergence by means of improved statistical techniques.
