Analyzing Approximate Value Iteration Algorithms

2017-09-14 · Arunselvan Ramaswamy, Shalabh Bhatnagar

In this paper, we consider the stochastic iterative counterpart of the value iteration scheme wherein only noisy and possibly biased approximations of the Bellman operator are available. We call this counterpart as the approximate value iteration (AVI) scheme. Neural networks are often used as function approximators, in order to counter Bellman's curse of dimensionality. In this paper, they are used to approximate the Bellman operator. Since neural networks are typically trained using sample data, errors and biases may be introduced. The design of AVI accounts for implementations with biased approximations of the Bellman operator and sampling errors. We present verifiable sufficient conditions under which AVI is stable (almost surely bounded) and converges to a fixed point of the approximate Bellman operator. To ensure the stability of AVI, we present three different yet related sets of sufficient conditions that are based on the existence of an appropriate Lyapunov function. These Lyapunov function based conditions are easily verifiable and new to the literature. The verifiability is enhanced by the fact that a recipe for the construction of the necessary Lyapunov function is also provided. We also show that the stability analysis of AVI can be readily extended to the general case of set-valued stochastic approximations. Finally, we show that AVI can also be used in more general circumstances, i.e., for finding fixed points of contractive set-valued maps.

📄 PDF Abstract BibTeX arXiv:1709.04673

Code (0)

등록된 구현이 없습니다.

Unifying Value Iteration, Advantage Learning, and Dynamic Policy Programming

2017-10-30 · Tadashi Kozuno, Eiji Uchibe, Kenji Doya

Approximate dynamic programming algorithms, such as approximate value iteration, have been successfully applied to many complex reinforcement learning tasks, and a better approximate dynamic programming algorithm is expe…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Approximate Modified Policy Iteration

2012-05-14 · Bruno Scherrer, Victor Gabillon, Mohammad Ghavamzadeh, Matthieu Geist

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 Classification

Quantum Reinforcement Learning via Policy Iteration

2022-03-03 · El Amine Cherrat, Iordanis Kerenidis, Anupam Prakash

Quantum computing has shown the potential to substantially speed up machine learning applications, in particular for supervised and unsupervised learning. Reinforcement learning, on the other hand, has become essential f…

Decision Making reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Error Propagation for Approximate Policy and Value Iteration

2010-12-01 · NeurIPS 2010 12 · Amir-Massoud Farahmand, Csaba Szepesvári, Rémi Munos

We address the question of how the approximation error/Bellman residual at each iteration of the Approximate Policy/Value Iteration algorithms influences the quality of the resulted policy. We quantify the performance lo…

Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes

2017-10-27 · Aaron Sidford, Mengdi Wang, Xian Wu, Yinyu Ye

In this paper we provide faster algorithms for approximately solving discounted Markov Decision Processes in multiple parameter regimes. Given a discounted Markov Decision Process (DMDP) with $|S|$ states, $|A|$ actions,…