Empirical Q-Value Iteration
  We propose a new simple and natural algorithm for learning the optimal
Q-value function of a discounted-cost Markov Decision Process (MDP) when the
transition kernels are unknown. Unlike the classical learning algorithms for
MDPs, such as Q-learning and actor-critic algorithms, this algorithm doesn't
depend on a stochastic approximation-based method. We show that our algorithm,
which we call the empirical Q-value iteration (EQVI) algorithm, converges to
the optimal Q-value function. We also give a rate of convergence or a
non-asymptotic sample complexity bound, and also show that an asynchronous (or
online) version of the algorithm will also work. Preliminary experimental
results suggest a faster rate of convergence to a ball park estimate for our
algorithm compared to stochastic approximation-based algorithms.
