将强化学习中的确定性等价法看作轨迹树方法的应用，简化了理论证明并改进了样本复杂度。
A View of the Certainty-Equivalence Method for PAC RL as an Application of the Trajectory Tree Method
- 把确定性等价法视为轨迹树方法的实例，用新视角统一分析框架。
- 在奖励假设更弱的情况下，得到更优的样本复杂度上界，尤其在小误差概率时表现更好。
- 适用于非平稳和平稳MDP，为算法设计提供更强理论支撑，适合理论研究者参考。
强化学习使智能体通过观测未知马尔可夫决策过程（MDP）的转移样本，优化自身行为。智能体推理中自然出现的实体是基于观测数据的极大似然估计 $\\-widehat{M}$。著名的确定性等价法（CEM）建议智能体采用 $\\widehat{π}$，即针对 $\\widehat{M}$ 的最优策略。该方法不仅直观，且在某些参数区域对具有生成模型的PAC RL展现出极小化最优样本复杂度。另一看似无关的算法是轨迹树方法（TTM），最初用于大规模部分可观测马尔可夫决策过程（POMDP）中的高效决策时间规划。本文发现，CEM可被视作TTM的一种应用。该视角带来定性优势：（1）对CEM的样本复杂度上界给出更简洁的新证明；（2）在比现有文献更弱的奖励假设下成立。分析适用于非平稳与平稳MDP。定量上，我们在小“误判概率”$δ$的条件下，对非平稳与平稳MDP均获得更优的样本复杂度上界。此外，我们还推导出有限时域MDP的下界，证明了在小$δ$情形下，非平稳MDP的上界达到极小化最优性。
原文摘要 · Abstract (English)
Reinforcement learning (RL) enables an agent interacting with an unknown MDP $M$ to optimise its behaviour by observing transitions sampled from $M$. A natural entity that emerges in the agent's reasoning is $\widehat{M}$, the maximum likelihood estimate of $M$ based on the observed transitions. The well-known \textit{certainty-equivalence} method (CEM) dictates that the agent update its behaviour to $\widehatπ$, which is an optimal policy for $\widehat{M}$. Not only is CEM intuitive, it has been shown to enjoy minimax-optimal sample complexity in some regions of the parameter space for PAC RL with a generative model~\citep{Agarwal2020GenModel}. A seemingly unrelated algorithm is the ``trajectory tree method'' (TTM)~\citep{Kearns+MN:1999}, originally developed for efficient decision-time planning in large POMDPs. This paper presents a theoretical investigation that stems from the surprising finding that CEM may indeed be viewed as an application of TTM. The qualitative benefits of this view are (1) new and simple proofs of sample complexity upper bounds for CEM, in fact under a (2) weaker assumption on the rewards than is prevalent in the current literature. Our analysis applies to both non-stationary and stationary MDPs. Quantitatively, we obtain (3) improvements in the sample-complexity upper bounds for CEM both for non-stationary and stationary MDPs, in the regime that the ``mistake probability'' $δ$ is small. Additionally, we show (4) a lower bound on the sample complexity for finite-horizon MDPs, which establishes the minimax-optimality of our upper bound for non-stationary MDPs in the small-$δ$ regime.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。