# Empirical Q-Value Iteration

arXiv: https://arxiv.org/abs/1412.0180 · HTML: https://mlsanity.com/paper/1412.0180/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Nov 2014.

## Built on by (most cited first, 7 of 7)

- [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022)
- [Sample Complexity of Robust Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.01506/) (2021)
- [Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2303.02783/) (2023)
- [Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coverage](https://mlsanity.com/paper/2310.18434/) (2023)
- [Truncated Variance Reduced Value Iteration](https://mlsanity.com/paper/2405.12952/) (2024)
- [Faster Q-Learning Algorithms for Restless Bandits](https://mlsanity.com/paper/2409.05908/) (2024)
- [Learning the Model While Learning Q: Finite-Time Sample Complexity of Online SyncMBQ](https://mlsanity.com/paper/2402.11877/) (2024)

## Abstract (arXiv)

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.