title: An Online Policy Gradient Algorithm for Markov Decision Processes with Continuous States and Actions.
abstract: We consider the learning problem under an online Markov decision process (MDP) aimed at learning the time-dependent decision-making policy of an agent that minimizes the regret-the difference from the best fixed policy. The difficulty of online MDP learning is that the reward function changes over time. In this letter, we show that a simple online policy gradient algorithm achieves regret O(√T) for T steps under a certain concavity assumption and O(log T) under a strong concavity assumption. To the best of our knowledge, this is the first work to present an online MDP algorithm that can handle continuous state, action, and parameter spaces with guarantee. We also illustrate the behavior of the proposed online policy gradient method through experiments.
authors.affiliation: Tokyo Institute of Technology, Meguro, Tokyo 152-8552, Japan mycw45@gmail.com.
authors.forename: Yao
authors.initials: Y
authors.lastname: Ma
authors.affiliation: Tianjian University of Science and Technology, Tian-Jin 30022, China tingting@tust.edu.cn.
authors.forename: Tingting
authors.initials: T
authors.lastname: Zhao
authors.affiliation: Kyushu University, Fukuoka 819-0395, Japan hatano@inf.kyushu-u.ac.jp.
authors.forename: Kohei
authors.initials: K
authors.lastname: Hatano
authors.affiliation: University of Tokyo, Tokyo 113-0033, Japan sugi@k.u-tokyo.ac.jp.
authors.forename: Masashi
authors.initials: M
authors.lastname: Sugiyama