KL-learning: Online solution of Kullback-Leibler control problems

We introduce a stochastic approximation method for the solution of an ergodic Kullback-Leibler control problem. A Kullback-Leibler control problem is a Markov decision process on a finite state space in which the control cost is proportional to a Kullback-Leibler divergence of the controlled transit...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2012-02
Main Authors: Bierkens, Joris, Kappen, Bert
Format: Article
Language:English
Subjects:
Algorithms
Distance learning
Divergence
Machine learning
Markov analysis
Markov processes
Transition probabilities
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce a stochastic approximation method for the solution of an ergodic Kullback-Leibler control problem. A Kullback-Leibler control problem is a Markov decision process on a finite state space in which the control cost is proportional to a Kullback-Leibler divergence of the controlled transition probabilities with respect to the uncontrolled transition probabilities. The algorithm discussed in this work allows for a sound theoretical analysis using the ODE method. In a numerical experiment the algorithm is shown to be comparable to the power method and the related Z-learning algorithm in terms of convergence speed. It may be used as the basis of a reinforcement learning style algorithm for Markov decision problems.
ISSN:2331-8422