改进强化学习中探索的坏周期管理，使累积后悔呈对数增长。
Logarithmic Regret of Exploration in Average Reward Markov Decision Processes
- 用新规则VM替代原有倍增机制，优化策略执行周期
- 坏周期内后悔从线性降至对数级，理论与实践均更优
- 适合研究强化学习探索机制的学者与工程师
在平均奖励马尔可夫决策过程（Average Reward MDP）中，当前最优的最小化后悔算法遵循经典框架：基于模型、乐观且分周期进行。首先，通过扩展值迭代（EVI）从置信区域中计算乐观策略；其次，使用周期（episode）机制，每个周期由倍增技巧（Doubling Trick, DT）或其变体终止。本文在不修改EVI的前提下，提出一种新规则——消失乘法规则（Vanishing Multiplicative, VM），替代原DT。实验与理论表明，采用VM时，算法的后悔表现不劣于甚至优于DT，且单次行为显著改善。关键在于，坏周期（即使用次优策略的周期）的管理效率大幅提升，使探索的后悔变为对数级而非线性。这一突破源于对好周期与坏周期中置信区域动态行为的深入理解。
原文摘要 · Abstract (English)
In average reward Markov decision processes, state-of-the-art algorithms for regret minimization follow a well-established framework: They are model-based, optimistic and episodic. First, they maintain a confidence region from which optimistic policies are computed using a well-known subroutine called Extended Value Iteration (EVI). Second, these policies are used over time windows called episodes, each ended by the Doubling Trick (DT) rule or a variant thereof. In this work, without modifying EVI, we show that there is a significant advantage in replacing (DT) by another simple rule, that we call the Vanishing Multiplicative (VM) rule. When managing episodes with (VM), the algorithm's regret is, both in theory and in practice, as good if not better than with (DT), while the one-shot behavior is greatly improved. More specifically, the management of bad episodes (when sub-optimal policies are being used) is much better under (VM) than (DT) by making the regret of exploration logarithmic rather than linear. These results are made possible by a new in-depth understanding of the contrasting behaviors of confidence regions during good and bad episodes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。