Infinite-Horizon Policy-Gradient Estimation

By Jonathan Baxter, Peter L. Bartlett. 2001

834 citations recorded by the source corpus.

Gradient-based approaches to direct policy search in reinforcement learning have received much recent attention as a means to solve problems of partial observability and to avoid some of the problems associated with policy degradation in value-function methods. In this paper we introduce 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. A similar algorithm was proposed by Kimura, Yamamura, and Kobayashi (1995). The algorithm's chief advantages are that it requires storage of only twice the number of policy parameters, uses one free parameter β ∈ [0, 1] (which has a natural interpretation in terms of bias-variance trade-off), and requires no knowledge of the underlying state. We prove convergence of GPOMDP, and show how the correct choice of the parameter β is related to the mixing time of the controlled POMDP. We briefly describe extensions of GPOMDP to controlled Markov chains, continuous state, observation and control spaces, multiple-agents, higher-order derivatives, and a version for training stochastic policies with internal states. In a companion paper (Baxter, Bartlett, & Weaver, 2001) we show how the gradient estimates generated by GPOMDP can be used in both a traditional stochastic gradient algorithm and a conjugate-gradient procedure to find local optima of the average reward.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Aligning Language Models with Preferences through f-divergence Minimization (2023, methodology): “Based on the similarity to policy gradients, we adopt the widely used baseline technique from RL, as previously studied in Williams (1992); Baxter & Bartlett (2001); Schulman et al. (2016) and in the context of DPG in (Korbak et al., 2022b).”
Neural Approaches to Conversational AI (2018, neutral): “We describe policy gradient in the simpler bounded-length trajectory case, although it can be extended to problems when the trajectory length is unbounded (Baxter and Bartlett, 2001; Baxter et al., 2001).”
Deep learning in neural networks: An overview (2014, methodology): “An important class of DS methods for NNs are Policy Gradient methods (Williams, 1986, 1988, 1992a; Sutton et al., 1999a; Baxter and Bartlett, 2001; Aberdeen, 2003; Ghavamzadeh and Mahadevan, 2003; Kohl and Stone, 2004; Wierstra et al., 2008; Rückstieß et al., 2008; Peters and Schaal, 2008b,a; Sehnke”
From Importance Sampling to Doubly Robust Policy Gradient (2019, neutral): “…problem now (one in the biased dynamics model), we choose state-baseline with Ṽ as a computationally-cheap variance reduction method to speed up the computation (c.f. Section 5.4), and use a different discount factor γ′ (again for variance reduction (Baxter & Bartlett, 2001; Jiang et al., 2015)).”
Trajectory-wise Control Variates for Variance Reduction in Policy Gradient Methods (2019, background): “The following theorem shows the size of each term when the policy is Gaussian, which is commonly the case for problems with continuous actions.”
Dual Policy Iteration (2018, background): “…Iteration (API) [10, 8, 14, 17, 27], including conservative API (CPI) [14], API driven by learned critics [26], or gradient-based API with stochastic policies [9, 6, 13, 28], have played a central role in Reinforcement Learning (RL) for decades and motivated many modern practical RL algorithms.”
P3O: Policy-on Policy-off Policy Optimization (2019, background): “Both of these entail a large variance for policy gradients (Kakade and Langford, 2002; Baxter and Bartlett, 2001) and a number of techniques exist to mitigate the variance.”
On Learning to Think: Algorithmic Information Theory for Novel Combinations of Reinforcement Learning Controllers and Recurrent Neural World Models (2015, methodology): “1, except that C is now an FNN or RNN trained by evolutionary algorithms [200, 255, 105, 56, 68] applied to NNs [165, 321, 180, 259, 72, 90, 89, 110, 94], or by policy gradient methods [314, 315, 316, 274, 18, 1, 63, 128, 313, 210, 192, 191, 256, 85, 312, 190, 82, 93][245, Sec.”
Dynamic policy programming (2010, background): “…performance guarantee of the induced policy (Farahmand et al., 2010; Thiery and Scherrer, 2010; Munos, API and AVI are expressed in terms of the supremum, with respect to (w.r.t.) the number of iterations, of the approximation errors: where γ denotes the discount factor, k · k is the ℓ ∞ -norm…”
One Big Net For Everything (2018, background): “6.6], or reinforcement learning [29, 90, 101, 76] through policy gradients [104, 91, 3, 1, 13, 30, 103, 48, 82, 22, 102, 42] [76, Sec.”
Optimizing the CVaR via Sampling (2014, methodology): “…successfully applied in diverse domains such as queueing systems, inventory management, and financial engineering (Fu 2006), and also in reinforcement learning (RL; Sutton and Barto, 1998), where it is commonly known as the policy gradient method (Baxter and Bartlett 2001; Peters and Schaal 2008).”
Safe Exploration in Continuous Action Spaces (2018, methodology): “We now show how to solve problem (1) using the policy gradient algorithm (Baxter & Bartlett, 2001) via a simple addition to the policy itself.”
ProMP: Proximal Meta-Policy Search (2018, methodology): “In the inﬁ-nite horizon MDP case, Baxter & Bartlett (2001) derived a decomposition of the hessian.”
Reinforcement Planning: RL for optimal planners (2012, background): “as derived in [10]) can be applied straightforwardly.”
Policy Evaluation Networks (2020, methodology): “However, the practice of policy gradient methods has evolved towards the use of discounting as a knob to control the bias-variance tradeoff (Xi-Ren Cao & Yat-Wah Wan, 1998; Baxter & Bartlett, 2001).”
Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent (2019, background): “…θ i is: This result can be seen as an extension of the policy gradient Theorem [ Sutton et al. , 2000; Glynn and L’ecuyer, 1995; Williams, 1992a; Baxter and Bartlett, 2001] to imperfect information games and has been used under several forms: for a detailed derivation, see [Srinivasan et al. ,…”