Convergence Rates of Posterior Distributions in Markov Decision Process

2019/07/22 by Zhen Li, Li, Zhen, Eric B. Laber +1
Decision Sciences · Computer Science · Mathematics · #Advanced Bandit Algorithms Research #Reinforcement Learning in Robotics #Markov Chains and Monte Carlo Methods

paper · pdf · doi:10.48550/arxiv.1907.09083

Abstract

In this paper, we show the convergence rates of posterior distributions of the model dynamics in a MDP for both episodic and continuous tasks. The theoretical results hold for general state and action space and the parameter space of the dynamics can be infinite dimensional. Moreover, we show the convergence rates of posterior distributions of the mean accumulative reward under a fixed or the optimal policy and of the regret bound. A variant of Thompson sampling algorithm is proposed which provides both posterior convergence rates for the dynamics and the regret-type bound. Then the previous results are extended to Markov games. Finally, we show numerical results with three simulation scenarios and conclude with discussions.

Related

• Posterior sampling for reinforcement learning: worst-case regret bounds
• Markov decision processes: on the convergence of the Monte-Carlo first visit algorithm
• On rates of convergence for posterior distributions under misspecification
• Learning Unknown Markov Decision Processes: A Thompson Sampling Approach
• Markov Decision Processes with Long-Term Average Constraints