Derivatives of Logarithmic Stationary Distributions for Policy Gradient Reinforcement Learning
Neural ComputationPublished 20 October 2009Open access
Tetsuro Morimura, Eiji Uchibe, Junichiro Yoshimoto, Jan Peters, Kenji Doya
Citations19
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A method for estimating the log stationary state distribution derivative (LSD) as a useful form of the derivative of the stationary state distributions through backward Markov chain formulation and a temporal difference learning framework is proposed.
Abstract
Most conventional policy gradient reinforcement learning (PGRL) algorithms neglect (or do not explicitly make use of) a term in the average reward gradient with respect to the policy parameter. That term involves the derivative of the stationary state distribution that corresponds to the sensitivity of its distribution to changes in the policy parameter. Although the bias introduced by this omission can be reduced by setting the forgetting rate gamma for the value functions close to 1, these algorithms do not permit gamma to be set exactly at gamma = 1. In this article, we propose a method for estimating the log stationary state distribution derivative (LSD) as a useful form of the derivative of the stationary state distribution through backward Markov chain formulation and a temporal difference learning framework. A new policy gradient (PG) framework with an LSD is also proposed, in which the average reward gradient can be estimated by setting gamma = 0, so it becomes unnecessary to learn the value functions. We also test the performance of the proposed algorithms using simple benchmark tasks and show that these can improve the performances of existing PG methods.
Keywords
Computer ScienceBusiness, Management and Accounting
Journal of Artificial Intelligence ResearchReinforcement Learning: A Survey
8,831 Citations1996Leslie Pack Kaelbling, Michael L. Littman +1 more
Central issues of reinforcement learning are discussed, including trading off exploration and exploitation, establishing the foundations of the field via Markov decision theory, learning from delayed reinforcement, constructing empirical models to accelerate learning, making use of generalization and hierarchy, and coping with hidden state.
Machine LearningSimple statistical gradient-following algorithms for connectionist reinforcement learning
7,386 Citations1992Ronald J. Williams
This article presents a general class of associative reinforcement learning algorithms for connectionist networks containing stochastic units that are shown to make weight adjustments in a direction that lies along the gradient of expected reinforcement in both immediate-reinforcement tasks and certain limited forms of delayed-reInforcement tasks, and they do this without explicitly computing gradient estimates.
MIT Press eBooksIntroduction to Reinforcement Learning
6,868 Citations1998Richard S. Sutton, Andrew G. Barto
In Reinforcement Learning, Richard Sutton and Andrew Barto provide a clear and simple account of the key ideas and algorithms of reinforcement learning.
Policy Gradient Methods for Reinforcement Learning with Function Approximation
4,982 Citations1999Richard S. Sutton, David McAllester +2 more
This paper proves for the first time that a version of policy iteration with arbitrary differentiable function approximation is convergent to a locally optimal policy.
Machine LearningLearning to Predict by the Methods of Temporal Differences
3,894 Citations1988Richard S. Sutton
This article introduces a class of incremental learning procedures specialized for prediction-that is, for using past experience with an incompletely known system to predict its future behavior, and proves their convergence and optimality for special cases and relate them to supervised-learning methods.
Machine LearningLearning to predict by the methods of temporal differences
2,758 Citations1988Richard S. Sutton
Neural ComputationReinforcement Learning in Continuous Time and Space
989 Citations2000Kenji Doya
A reinforcement learning framework for continuous-time dynamical systems without a priori discretization of time, state, and action based on the Hamilton-Jacobi-Bellman (HJB) equation for infinite-horizon, discounted reward problems is presented and algorithms for estimating value functions and improving policies with the use of function approximators are derived.
NeurocomputingNatural Actor-Critic
736 Citations2008Jan Peters, Stefan Schaal
This paper investigates a novel model-free reinforcement learning architecture, the Natural Actor-Critic, where the actor updates are based on stochastic policy gradients employing Amari's natural gradient approach, while the critic obtains both the natural policy gradient and additional parameters of a value function simultaneously by linear regression.
SIAM Journal on Control and OptimizationOnActor-Critic Algorithms
694 Citations2003Vijay R. Konda, John N. Tsitsiklis
This article proposes and analyzes a class of actor-critic algorithms in which the critic uses temporal difference learning with a linearly parameterized approximation architecture, and the actor is updated in an approximate gradient direction, based on information provided by the critic.
Machine LearningLinear Least-Squares algorithms for temporal difference learning
639 Citations1996Steven J. Bradtke, Andrew G. Barto
Two new temporal diffence algorithms based on the theory of linear least-squares function approximation, LS TD and RLS TD, are introduced and prove probability-one convergence when it is used with a function approximator linear in the adjustable parameters.
Policy Gradient Methods for Robotics
511 Citations2006Jan Peters, Stefan Schaal
An overview on learning with policy gradient methods for robotics with a strong focus on recent advances in the field is given and how the most recently developed methods can significantly improve learning performance is shown.
Communications of the ACMLikelihood ratio gradient estimation for stochastic systems
408 Citations1990Peter W. Glynn
This article describes two important problems which motivate the study of efficient gradient estimation algorithms and presents the likelihood ratio gradient estimator in a general setting in which the essential idea is most transparent, and derives likelihood-ratio-gradient estimators for both time-homogeneous and non-time homogeneous discrete-time Markov chains.
Journal of Artificial Intelligence ResearchInfinite-Horizon Policy-Gradient Estimation
333 Citations2001J. Baxter, P. L. Bartlett
GPOMDP, a simulation-based algorithm for generating a biased estimate of the gradient of the average reward in Partially Observable Markov Decision Processes (POMDPs) controlled by parameterized stochastic policies, is introduced.
Elsevier eBooksLearning Without State-Estimation in Partially Observable Markovian Decision Processes
328 Citations1994Satinder Singh, Tommi Jaakkola +1 more
A new framework for learning without state-estimation in POMDPs is developed by including stochastic policies in the search space, and by defining the value or utility of a distribution over states.
Journal of Machine Learning ResearchVariance Reduction Techniques for Gradient Estimates in Reinforcement Learning
322 Citations2004Evan Greensmith, Peter L. Bartlett +1 more
Lecture notes in computer scienceNatural Actor-Critic
310 Citations2005Jan Peters, Sethu Vijayakumar +1 more
Machine LearningTechnical Update: Least-Squares Temporal Difference Learning
297 Citations2002Justin A. Boyan
This paper updates Bradtke and Barto's work in three significant ways: first, it presents a simpler derivation of the LSTD algorithm; second, it generalizes from λ = 0 to arbitrary values of λ; at the extreme of κ, the resulting new algorithm is shown to be a practical, incremental formulation of supervised linear regression.
Neural NetworksA stochastic reinforcement learning algorithm for learning real-valued functions
294 Citations1990Vijaykumar Gullapalli
A stochastic reinforcement learning algorithm for learning functions with continuous outputs using a connectionist network that learns to perform an underconstrained positioning task using a simulated 3 degree-of-freedom robot arm.
Machine LearningIncremental multi-step Q-learning
289 Citations1996Jing Peng, Ronald J. Williams
A novel incremental algorithm that combines Q-learning with the TD(λ) return estimation process, which is typically used in actor-critic learning, leading to faster learning and also helping to alleviate the non-Markovian effect of coarse state-space quatization.
Recursive Estimation and Time-Series Analysis: An Introduction
262 Citations1984Peter Young
Gradient Descent for General Reinforcement Learning
239 Citations1998Leemon C. Baird, Andrew Moore
A simple learning rule is derived, the VAPS algorithm, which can be instantiated to generate a wide range of new reinforcement-learning algorithms, and allows policy-search and value-based algorithms to be combined, thus unifying two very different approaches to reinforcement learning into a single Value and Policy Search algorithm.
AutomaticaAverage cost temporal-difference learning
142 Citations1999John N. Tsitsiklis, Benjamin Van Roy
A variant of temporal-di ! erence learning that approximates average and di ! erential costs of an irreducible aperiodic Markov chain and provides a bound on the resulting approximation error that exhibits an interesting dependence on the ` mixing time a of the Markov chain.
Journal of Artificial Intelligence ResearchExperiments with Infinite-Horizon, Policy-Gradient Estimation
139 Citations2001J. Baxter, Peter L. Bartlett +1 more
Algorithms that perform gradient ascent of the average reward in a partially observable Markov decision process (POMDP) based on GPOMDP, an algorithm introduced in a companion paper (Baxter & Bartlett, 2001), which computes biased estimates of the performance gradient in POMDPs.
IEEE Transactions on Automatic ControlConvergence Results for Some Temporal Difference Methods Based on Least Squares
101 Citations2009Huizhen Yu, Dimitri P. Bertsekas
An average cost method is introduced, patterned after the known discounted cost method, and it is proved its convergence for a range of constant stepsize choices and the convergence rate is optimal within the class of temporal difference methods.
ANU Open Research (Australian National University)Policy-Gradient Algorithms for Partially Observable Markov Decision Processes
75 Citations2003Douglas Aberdeen
This thesis develops several improved algorithms for learning policies with memory in an infinite-horizon setting including an application written for the Bunyip cluster that won the international Gordon-Bell prize for price/performance in 2001.
Birkhäuser Boston eBooksClassical and Spatial Stochastic Processes
54 Citations1999Rinaldo B. Schinazi
Machine LearningOn Average Versus Discounted Reward Temporal-Difference Learning
47 Citations2002John N. Tsitsiklis, Benjamin Van Roy
An analytical comparison between discounted and average reward temporal-difference learning with linearly parameterized approximations suggests that the computational advantages of average reward TD may have been caused by inappropriate basis function scaling rather than fundamental differences in problem formulations or algorithms.
Lecture notes in computer scienceOptimizing Average Reward Using Discounted Rewards
39 Citations2001Sham M. Kakade
A bound is provided on the average reward of the policy obtained by solving the Bellman equations which depends on the relationship between the discount factor and the mixingtime of the Markov chain.
Annals of Operations ResearchHow to optimize discrete-event systems from a single sample path by the score function method
39 Citations1990R.Y. Rubinstein
A method for deriving the optimal solution of a class of mathematical programming problems, associated with discrete-event systems and in particular with queueing models, while using asingle sample path (single simulation experiment) from the underlying process.
Policy Search via Density Estimation
32 Citations1999Andrew Y. Ng, Ronald Parr +1 more
Dual Representations for Dynamic Programming and Reinforcement Learning
31 Citations2007Tao Wang, Michael Bowling +1 more
This paper presents a modified dual of the standard linear program that guarantees a globally normalized state visit distribution is obtained, and derives novel dual forms of dynamic programming, including policy evaluation, policy iteration and value iteration to derive new forms of Sarsa and Q-learning.
Average cost temporal-difference learning
30 Citations2002John N. Tsitsiklis, Benjamin Van Roy
A variant of temporal-difference learning that approximates average and differential costs of an irreducible aperiodic Markov chain and provides a bound on the resulting approximation error that exhibits an interesting dependence on the "mixing time" of the Markov chain.
Stable Dual Dynamic Programming
26 Citations2007Tao Wang, Michael Bowling +2 more
This paper investigates the convergence properties of these dual algorithms both theoretically and empirically, and shows how they can be scaled up by incorporating function approximation.
Lecture notes in computer scienceA New Natural Policy Gradient by Stationary Distribution Metric
13 Citations2008Tetsuro Morimura, Eiji Uchibe +2 more
A Riemannian metric for the joint distribution of the state-action, which is directly linked with the average reward, is proposed and derived, and a new NPG named "Natural State-action Gradient"(NSG) is derived).
Neural Information Processing SystemsA Generalized Natural Actor-Critic Algorithm
13 Citations2009Tetsuro Morimura, Eiji Uchibe +2 more
A generalized Natural Gradient that linearly interpolates the two FIMs is described and an efficient implementation for the gNG learning based on a theory of the estimating function, the generalized Natural Actor-Critic (gNAC) algorithm is proposed.
A semiparametric statistical approach to model-free policy evaluation
9 Citations2008Tsuyoshi Ueno, Motoaki Kawanabe +3 more
LSTD-based policy evaluation from the new view-point of semiparametric statistical inference is discussed, showing that the estimator can be obtained from a particular estimating function which guarantees its convergence to the true value asymptotically, without specifying a model of the environment.
Artificial Life and RoboticsNatural actor-critic with baseline adjustment for variance reduction
4 Citations2008Tetsuro Morimura, Eiji Uchibe +1 more
A baseline function for the estimation of a natural policy gradient with respect to variance is discussed, and a condition in which an optimal baseline function that reduces the variance is equivalent to the state value function is demonstrated.
NAIST Digital Library (Nara Institute of Science and Technology)Policy gradient reinforcement learning with log stationary distribution gradients
2 Citations2007Tetsuro Morimura, Eiji Uchibe +2 more