Gradient based policy optimization of constrained Markov decision processes

MaRDI QIDQ4925757zbMATH OpenFDO

Authors Vikram Krishnamurthy, Felisa J. Vázquez-Abad

Publication date 12 June 2013

Full work available at URL https://arxiv.org/abs/1110.4946

zbMATH Keywords

asymptotic biasstochastic approximation algorithmspherical coordinate parametrization

Mathematics Subject Classification ID

Markov and semi-Markov decision processes (90C40)

Abstract: We present on-line policy gradient algorithms for computing the locally optimal policy of a constrained, average cost, finite state Markov Decision Process. The stochastic approximation algorithms require estimation of the gradient of the cost function with respect to the parameter that characterizes the randomized policy. We propose a spherical coordinate parametrization and present a novel simulation based gradient estimation scheme involving weak derivatives (measure-valued differentiation). Such methods have substantially reduced variance compared to the widely used score function method. Similar to neuro-dynamic programming algorithms (e.g. Q-learning or Temporal Difference methods), the algorithms proposed in this paper are simulation based and do not require explicit knowledge of the underlying parameters such as transition probabilities. However, unlike neuro-dynamic programming methods, the algorithms proposed here can handle constraints and time varying parameters. Numerical examples are given to illustrate the performance of the algorithms. This paper was originally written in 2004. One reason we are putting this on arxiv now is that the score function gradient estimator continues to be used in the online reinforcement learning literature even though its variance grows as $O(n)$ given $n$ data points (for a Markov process). In comparison the weak derivative estimator has significantly smaller variance of $O(1)$ as reported in this paper (and elsewhere).

Recommendations

• scientific article; zbMATH DE number 4088775
• Approximate gradient methods in policy-space optimization of Markov reward processes
• An actor-critic algorithm with function approximation for discounted cost constrained Markov decision processes
• Constrained Discounted Dynamic Programming
• Adaptive control of constrained Markov chains

Cited in

(8)

• Potentials based optimization with embedded Markov chain for stochastic constrained system
• scientific article; zbMATH DE number 4088775 (Why is no real title available?)
• A basic formula for performance gradient estimation of semi-Markov decision processes
• Random search for constrained Markov decision processes with multi-policy improvement
• An actor-critic algorithm with function approximation for discounted cost constrained Markov decision processes
• Approximate gradient methods in policy-space optimization of Markov reward processes
• Stochastic approximations for finite-state Markov chains
• An Online Policy Gradient Algorithm for Markov Decision Processes with Continuous States and Actions

This page was built for publication: Gradient based policy optimization of constrained Markov decision processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4925757)