Fitted Value Function Iteration with Probability One Contractions

Abstract

This paper studies a value function iteration algorithm based on nonexpansive function approximation and Monte Carlo integration that can be applied to almost all stationary dynamic programming problems. The method can be represented using a randomized fitted Bellman operator and a corresponding algorithm that is shown to be globally convergent with probability one. When additional restrictions are imposed, an OP(n-1/2) rate of convergence for Monte Carlo error is obtained. Show more