分解马尔可夫决策过程中近最优强化学习

Mar, 2014

分解马尔可夫决策过程中近最优强化学习

Near-optimal Regret Bounds for Reinforcement Learning in Factored MDPs

Ian Osband, Benjamin Van Roy

TL;DR通过采用 posterior sampling reinforcement learning (PSRL) 算法和 upper confidence bound algorithm (UCRL-Factored) 算法，在已知为 factored MDP 系统中，可将 regret 值多项式缩小到编码所需的 factored MDP 参数数量级别，从而大大减少了学习时间。

Abstract

Any learning algorithm over markov decision processes (MDPs) will have worst-case regret $\Omega(\sqrt{SAT})$ where $T$ is the elapsed time and $S$ and $A$ are the cardinalities of the state and action spaces. In many settings of interest $S$ and $A$ may be so huge that it is impossibl