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.
Code (0)
등록된 구현이 없습니다.
Tasks
Q-LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Accelerated Value Iteration via Anderson Mixing
Acceleration for reinforcement learning methods is an important and challenging theme. We introduce the Anderson acceleration technique into the value iteration, developing an accelerated value iteration algorithm that w…
Atari GamesQ-Learningreinforcement-learningReinforcement Learning (RL)Deflated Dynamics Value Iteration
The Value Iteration (VI) algorithm is an iterative procedure to compute the value function of a Markov decision process, and is the basis of many reinforcement learning (RL) algorithms as well. As the error convergence r…
Reinforcement Learning (RL)Boosted Fitted Q-Iteration
This paper is about the study of B-FQI, an Approximated Value Iteration (AVI) algorithm that exploits a boosting procedure to estimate the action-value function in reinforcement learning problems. B-FQI is an iterat…
regressionReinforcement LearningOptimal Filter Design for Consensus on Random Directed Graphs
Optimal design of consensus acceleration graph filters relates closely to the eigenvalues of the consensus iteration matrix. This task is complicated by random networks with uncertain iteration matrix eigenvalues. Filter…
Inverse Policy Evaluation for Value-based Sequential Decision-making
Value-based methods for reinforcement learning lack generally applicable ways to derive behavior from a value function. Many approaches involve approximate value iteration (e.g., $Q$-learning), and acting greedily with r…
Decision MakingQ-LearningSequential Decision Making