Rank-One Modified Value Iteration
In this paper, we provide a novel algorithm for solving planning and learning problems of Markov decision processes. The proposed algorithm follows a policy iteration-type update by using a rank-one approximation of the transition probability matrix in the policy evaluation step. This rank-one approximation is closely related to the stationary distribution of the corresponding transition probability matrix, which is approximated using the power method. We provide theoretical guarantees for the convergence of the proposed algorithm to optimal (action-)value function with the same rate and computational complexity as the value iteration algorithm in the planning problem and as the Q-learning algorithm in the learning problem. Through our extensive numerical simulations, however, we show that the proposed algorithm consistently outperforms first-order algorithms and their accelerated versions for both planning and learning problems.
Code (0)
등록된 구현이 없습니다.
Tasks
Q-LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Image Denoising Using Low Rank Minimization With Modified Noise Estimation
Recently, the application of low rank minimization to image denoising has shown remarkable denoising results which are equivalent or better than those of the existing state-of-the-art algorithms. However, due to iterativ…
DenoisingImage DenoisingNoise EstimationApproximate Modified Policy Iteration
Modified policy iteration (MPI) is a dynamic programming (DP) algorithm that contains the two celebrated policy and value iteration methods. Despite its generality, MPI has not been thoroughly studied, especially its app…
General ClassificationOn the Convergence of Modified Policy Iteration in Risk Sensitive Exponential Cost Markov Decision Processes
Modified policy iteration (MPI) is a dynamic programming algorithm that combines elements of policy iteration and value iteration. The convergence of MPI has been well studied in the context of discounted and average-cos…
Computational EfficiencySuccessive Over Relaxation Q-Learning
In a discounted reward Markov Decision Process (MDP), the objective is to find the optimal value function, i.e., the value function corresponding to an optimal policy. This problem reduces to solving a functional equatio…
Q-LearningReinforcement LearningReinforcement Learning (RL)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)