Optimistic initialization and greediness lead to polynomial time learning in factored MDPs
Optimistic initialization and greediness lead to polynomial time learning in factored MDPs
复制标题
乐观初始化和贪婪导致分解 MDP 中的多项式时间学习
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
András Lörincz
中科院分区：
文献类型：
--
作者：
I. Szita;András Lörincz
本文提出了一种因子马尔可夫决策过程（fmdp）的多项式时间强化学习算法。因子乐观初始模型（FOIM）算法在传统的基础上保持了FMDP的经验模型，并对其模型始终遵循贪婪策略。该算法的唯一技巧是乐观地初始化模型。证明了在适当的初始化条件下(1)FOIM收敛于近似迭代（AVI）不动点；（ii）智能体做出非近最优决策（相对于AVI的解）的步数在所有相关量上都是多项式；（iii）算法的每步成本也是多项式。据我们所知，FOIM是第一个具有这些属性的算法。
In this paper we propose an algorithm for polynomial-time reinforcement learning in factored Markov decision processes (FMDPs). The factored optimistic initial model (FOIM) algorithm, maintains an empirical model of the FMDP in a conventional way, and always follows a greedy policy with respect to its model. The only trick of the algorithm is that the model is initialized optimistically. We prove that with suitable initialization (i) FOIM converges to the fixed point of approximate value iteration (AVI); (ii) the number of steps when the agent makes non-near-optimal decisions (with respect to the solution of AVI) is polynomial in all relevant quantities; (iii) the per-step costs of the algorithm are also polynomial. To our best knowledge, FOIM is the first algorithm with these properties.