  We propose universal randomized function approximation-based empirical value
iteration (EVI) algorithms for Markov decision processes. The `empirical'
nature comes from each iteration being done empirically from samples available
from simulations of the next state. This makes the Bellman operator a random
operator. A parametric and a non-parametric method for function approximation
using a parametric function space and the Reproducing Kernel Hilbert Space
(RKHS) respectively are then combined with EVI. Both function spaces have the
universal function approximation property. Basis functions are picked randomly.
Convergence analysis is done using a random operator framework with techniques
from the theory of stochastic dominance. Finite time sample complexity bounds
are derived for both universal approximate dynamic programming algorithms.
Numerical experiments support the versatility and effectiveness of this
approach.
