Dynamic policy programming

By Mohammad Gheshlaghi Azar, Vicenç Gómez, Hilbert J. Kappen. 2010

138 citations recorded by the source corpus.

In this paper, we propose a novel policy iteration method, called dynamic policy programming (DPP), to estimate the optimal policy in the infinite-horizon Markov decision processes. We prove the finite-iteration and asymptotic l\infty-norm performance-loss bounds for DPP in the presence of approximation/estimation error. The bounds are expressed in terms of the l\infty-norm of the average accumulated error as opposed to the l\infty-norm of the error in the case of the standard approximate value iteration (AVI) and the approximate policy iteration (API). This suggests that DPP can achieve a better performance than AVI and API since it averages out the simulation noise caused by Monte-Carlo sampling throughout the learning process. We examine this theoretical results numerically by com- paring the performance of the approximate variants of DPP with existing reinforcement learning (RL) methods on different problem domains. Our results show that, in all cases, DPP-based algorithms outperform other RL methods by a wide margin.

Subfields: Artificial Intelligence, Computer Networks and Communications, 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 Computer Networks and Communications

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Trust-PCL: An Off-Policy Trust Region Method for Continuous Control (2017, methodology): “termined, which we have found to be especially crucial in cases where the reward distribution changes dramatically during training. Most previous work on softmax consistency (e.g., Fox et al. (2016); Azar et al. (2012); Nachum et al. (2017)) have only been evaluated on relatively simple tasks, inclu”
Bridging the Gap Between Value and Policy Based Reinforcement Learning (2017, methodology): “In particular, this operator has been used by [5] to propose an iterative algorithm converging to the optimal maximum reward policy inspired by the work of [15, 39].”
PGQ: Combining policy gradient and Q-learning (2016, methodology): “We conclude with some numerical examples that provide empirical evidence of improved data efﬁciency and stability of PGQ.”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, neutral): “The update rule we derive is similar to that used in ‘soft’ Q-learning (so-called since the ‘hard’ max is replaced with a soft-max) [6, 16, 18, 30, 47].”
A unified view of entropy-regularized Markov decision processes (2017, methodology): “We next show that the Dynamic Policy Programming (DPP) algorithm of Azar et al. (2012) and the Trust-Region Policy Optimization (TRPO) algorithm of Schulman et al. (2015) are both approximate variants of Mirror Descent with the Bregman divergence D C .”
f-Divergence constrained policy improvement (2017, background): “In (4), the divergence is added as a penalty, as suggested by Azar and Kappen (2012).”
Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes (2019, unknown): “In terms of the concentrability coefficient, there are a notable set of provable average case guarantees for the MD-MPI algorithm [Geist et al., 2019] (see also [Azar et al., 2012, Scherrer et al., 2015]), which are stated in terms of various norms of function approximation error.”
Safe Policy Iteration (2013, background): “A few approaches (Perkins & Precup, 2002; Kakade & Langford, 2002; Wagner, 2011; Azar et al., 2012) to this problem, instead of iterating on a sequence of greedy policies computed on approximated action– value functions, propose converging algorithms that exploit smaller updates in the space of…”
An information-theoretic approach to curiosity-driven reinforcement learning (2012, background): “[28,2]) addresses the problem of finding closed-form solutions to reinforcement learning problems, by reformulating the optimization objective.”
Provably Efficient Exploration in Policy Optimization (2019, background): “Meanwhile, theoretically, vanilla policy gradient can be shown to suﬀer from exponentially large variance in the well-known “combination lock” setting (Kakade, 2003; Leﬄer et al., 2007; Azar et al., 2012a), which only has a ﬁnite state space.”
Improving Policy Gradient by Exploring Under-appreciated Rewards (2016, background): “Some of these value-based methods have proposed a softening of Q-values which can be interpreted as adding a form of maximum-entropy regularizer (Asadi & Littman, 2016; Azar et al., 2012; Fox et al., 2016; Ziebart, 2010).”
G-Learning: Taming the Noise in Reinforcement Learning via Soft Updates (2015, methodology): “Other works have used related methods for reinforcement learning [32, 33, 34, 35, 36].”
On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift (2019, methodology): “We then consider the Natural Policy Gradient (NPG) algorithm (Kakade, 2001) (also see Bagnell and Schneider (2003); Peters and Schaal (2008)), which can be considered a quasi second-order method due to the use of its particular preconditioner, and provide an iteration complexity to achieve an -optim”
Sample-based informationl-theoretic stochastic optimal control (2014, methodology): “The data set is subsequently used to improve the estimate of the value function.”
A Theory of Regularized Markov Decision Processes (2019, methodology): “Dynamic Policy Programming (DPP) [Azar et al., 2012] is a reparametrization of a value iteration scheme regularized by a KL penalty between consecutive policies.”
Black-Box Policy Search with Probabilistic Programs (2015, unknown): “ptimal control [van den Broek et al., 2010]. Path integral approaches have been applied to reinforcement learning problems in a number of studies [Theodorou et al., 2007, Theodorou and Todorov, 2012, Azar and Kappen, 2012]. Related approaches [Rawlik et al., 2010, 2012] minimize the KL divergence be”
Exponentially Weighted Imitation Learning for Batched Historical Data (2018, unknown): “Consider the problem π̃ = arg max π′∈Π ((1− γ)βLdπ,π(π′)−DdπKL(π ′||π)) (3) which has an analytical solution in the policy space Π [Azar et al., 2012, Appendix A, Proposition 1] π̃(a|s) = π(a|s) exp(βAπ(s, a) + C(s)) (4) where C(s) is a normalizing factor to ensure that ∑ a∈A π̃(a|s) = 1 for each…”
Munchausen Reinforcement Learning (2020, methodology): “Yet, their experiment involves a small number of interactions, while the function estimated by DPP is naturally diverging.”
Hierarchical Relative Entropy Policy Search (2014, result): “We show that our Hierarchical REPS can learn versatile solutions while also showing an increased performance in terms of learning speed and quality of the found policy in comparison to the nonhierarchical approach.”