Empirical Value Iteration for Approximate Dynamic Programming Conference Paper uri icon


  • We propose a simulation based algorithm, Empirical Value Iteration (EVI) algorithm, for finding the optimal value function of an MDP with infinite horizon discounted cost criteria when the transition probability kernels are unknown. Unlike simulation based algorithms using stochastic approximation techniques which give only asymptotic convergence results, we give provable, non-asymptotic performance guarantees in terms of sample complexity results: given > 0 and > 0, we specify the minimum number of simulation samples n(; ) needed in each iteration and the minimum number of iterations t(; ) that are sufficient for the EVI to yield, with a probability at least 1 - , an approximate value function that is at least close to the optimal value function. 2014 American Automatic Control Council.

name of conference

  • 2014 American Control Conference

published proceedings


author list (cited authors)

  • Haskell, W. B., Jain, R., & Kalathil, D.

citation count

  • 1

complete list of authors

  • Haskell, William B||Jain, Rahul||Kalathil, Dileep

publication date

  • July 2014