揭示通信型马尔可夫决策过程的后悔下界新复杂性
The regret lower bound for communicating Markov Decision Processes
- 通过优化问题刻画后悔下界，融合探索与共探索机制
- 证明下界在标准类MDP中可还原已有结果，且具计算难解性
- 适合研究强化学习理论与算法复杂性的学者参考
本文将问题依赖设定下的后悔下界从遍历马尔可夫决策过程（MDP）扩展至通信型MDP。尽管遍历MDP的后悔下界已明确且可被有效算法达到，我们证明通信型MDP的下界显著更复杂。该下界重新审视了一致学习代理所必需的探索行为，并指出最优区域必须相对于次优区域被过度访问，这一现象称为共探索。同时，我们发现探索与共探索行为与对导航结构在对数尺度上的精细分析所导出的导航约束紧密交织。最终的下界表达为一个优化问题的解，在许多标准类MDP中可退化为已有结果。从计算角度看，该问题在一般情况下为Σ₂ᴾ-难，甚至验证可行域成员资格也是coNP-难。我们进一步提出一种构造性近似算法以逼近该下界。
原文摘要 · Abstract (English)
This paper is devoted to the extension of the regret lower bound beyond ergodic Markov decision processes (MDPs) in the problem dependent setting. While the regret lower bound for ergodic MDPs is well-known and reached by tractable algorithms, we prove that the regret lower bound becomes significatively more complex in communicating MDPs. Our lower bound revisits the necessary explorative behavior of consistent learning agents and further explains that all optimal regions of the environment must be overvisited compared to sub-optimal ones, a phenomenon that we refer to as co-exploration. In tandem, we show that these two explorative and co-explorative behaviors are intertwined with navigation constraints obtained by scrutinizing the navigation structure at logarithmic scale. The resulting lower bound is expressed as the solution of an optimization problem that, in many standard classes of MDPs, can be specialized to recover existing results. From a computational perspective, it is provably $Σ_2^\textrm{P}$-hard in general and as a matter of fact, even testing the membership to the feasible region is coNP-hard. We further provide an algorithm to approximate the lower bound in a constructive way.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。