R-MAX - A general polynomial time algorithm for near-optimal reinforcement learning
R-MAX - A general polynomial time algorithm for near-optimal reinforcement learning
复制标题
DOI：
10.1162/153244303765208377
复制
发表时间：
2003-02-15
影响因子：
6
通讯作者：
Tennenholtz, M
中科院分区：
文献类型：
--
作者：
Brafman, RI;Tennenholtz, M
R-MAX是一种非常简单的基于模型的强化学习算法，可以在多项式时间内获得接近最优的平均奖励。在R-MAX中，智能体始终保持一个完整但可能不准确的环境模型，并根据该模型得出的最优策略进行行动。该模型以一种乐观的方式初始化：所有状态下的所有动作都会返回最大可能的奖励（因此得名）。在执行期间，它会根据代理的观察结果进行更新。R-MAX对之前的几个算法进行了改进：(1)它比Kearns和Singh的E-3算法更简单、更通用，涵盖了零和随机博弈。(2)它具有解决探索与开发困境的内在机制。(3)它正式证明了许多强化学习算法中使用的“不确定性下的乐观主义”偏见。(4)对于单控制器随机博弈的学习，它比Brafman和Tennenholtz的LSG算法更简单、更通用、更高效。(5)推广了Monderer和Termenholtz在重复博弈中学习的算法。(6)迄今为止，这是唯一一种在重复博弈中学习的算法，它被证明是有效的，大大改进和简化了Banos和Megiddo之前的算法。
R-MAX is a very simple model-based reinforcement learning algorithm which can attain near-optimal average reward in polynomial time. In R-MAX, the agent always maintains a complete, but possibly inaccurate model of its environment and acts based on the optimal policy derived from this model. The model is initialized in an optimistic fashion: all actions in all states return the maximal possible reward (hence the name). During execution, it is updated based on the agent's observations. R-MAX improves upon several previous algorithms: (1) It is simpler and more general than Kearns and Singh's E-3 algorithm, covering zero-sum stochastic games. (2) It has a built-in mechanism for resolving the exploration vs. exploitation dilemma. (3) It formally justifies the "optimism under uncertainty" bias used in many RL algorithms. (4) It is simpler, more general, and more efficient than Brafman and Tennenholtz's LSG algorithm for learning in single controller stochastic games. (5) It generalizes the algorithm by Monderer and Termenholtz for learning in repeated games. (6) It is the only algorithm for learning in repeated games, to date, which is provably efficient, considerably improving and simplifying previous algorithms by Banos and by Megiddo.