Geometric Variance Reduction in Markov Chains: Application to Value Function and Gradient Estimation

Rémi Munos 1, 2
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : We study a variance reduction technique for Monte Carlo estimation of functionals in Markov chains. The method is based on designing sequential control variates using successive approximations of the function of interest V. Regular Monte Carlo estimates have a variance of O(1/N), where N is the number of sample trajectories of the Markov chain. Here, we obtain a geometric variance reduction O(ρ^N) (with ρ<1) up to a threshold that depends on the approximation error V-AV, where A is an approximation operator linear in the values. Thus, if V belongs to the right approximation space (i.e. AV=V), the variance decreases geometrically to zero. An immediate application is value function estimation in Markov chains, which may be used for policy evaluation in a policy iteration algorithm for solving Markov Decision Processes. Another important domain, for which variance reduction is highly needed, is gradient estimation, that is computing the sensitivity ∂αV of the performance measure V with respect to some parameter α of the transition probabilities. For example, in policy parametric optimization, computing an estimate of the policy gradient is required to perform a gradient optimization method. We show that, using two approximations for the value function and the gradient, a geometric variance reduction is also achieved, up to a threshold that depends on the approximation errors of both of those representations.
Type de document :
Article dans une revue
Journal of Machine Learning Research, Journal of Machine Learning Research, 2006, 7, pp.413-427
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00117153
Contributeur : Rémi Munos <>
Soumis le : jeudi 30 novembre 2006 - 11:39:42
Dernière modification le : jeudi 10 mai 2018 - 02:04:13
Document(s) archivé(s) le : mardi 6 avril 2010 - 23:41:14

Fichier

fast_mc_jmlr.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00117153, version 1

Collections

Citation

Rémi Munos. Geometric Variance Reduction in Markov Chains: Application to Value Function and Gradient Estimation. Journal of Machine Learning Research, Journal of Machine Learning Research, 2006, 7, pp.413-427. 〈inria-00117153〉

Partager

Métriques

Consultations de la notice

349

Téléchargements de fichiers

121