AsyncQVI: Asynchronous-Parallel Q-Value Iteration for Discounted Markov Decision Processes with Near-Optimal Sample Complexity

2018/12/03 by Yibo Zeng, Fei Feng, Zeng, Yibo +3
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Formal Methods in Verification #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1812.00885

openalex publication_date 2018/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we propose AsyncQVI, an asynchronous-parallel Q-value iteration for discounted Markov decision processes whose transition and reward can only be sampled through a generative model. Given such a problem with |S| states, |A| actions, and a discounted factor γ∈(0,1), AsyncQVI uses memory of size O(|S|) and returns an ε-optimal policy with probability at least 1-δ using O((|S||A|)/((1-γ)⁵ε²)log(\frac1δ)) samples. AsyncQVI is also the first asynchronous-parallel algorithm for discounted Markov decision processes that has a sample complexity, which nearly matches the theoretical lower bound. The relatively low memory footprint and parallel ability make AsyncQVI suitable for large-scale applications. In numerical tests, we compare AsyncQVI with four sample-based value iteration methods. The results show that our algorithm is highly efficient and achieves linear parallel speedup.

Citations

• Massively Parallel Methods for Deep Reinforcement Learning
• Playing Atari with Deep Reinforcement Learning
• Reinforcement learning in robotics: A survey
• Accelerated Methods for Deep Reinforcement Learning
• Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model
• Sample-Optimal Parametric Q-Learning Using Linearly Additive Features
• Reinforcement Learning through Asynchronous Advantage Actor-Critic on a GPU
• Model-Based Reinforcement Learning with a Generative Model is Minimax\n Optimal

Related

• Empirical Q-Value Iteration
• Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexity
• Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model
• Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
• Truncated Variance Reduced Value Iteration