提出新算法实现平均奖励POMDP的近最优后悔率,突破已有方法局限。
Achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ Regret in Average-Reward POMDPs with Known Observation Models
- 设计基于信念的确定性策略类与动作独立估计器,提升数据效率。
- 首次获得 $ ilde{ m O}( oot T o)$ 的后悔界,优于现有最优方法。
- 适用于已知观测模型但未知转移模型的强化学习场景。
我们研究无限时域平均奖励部分可观测马尔可夫决策过程(POMDP),其转移模型未知而观测模型已知。以往方法受限于两类:(i) 频率学方法依赖非最优随机策略保证各动作被选择的最小概率;(ii) 贝叶斯方法使用最优策略类但需强估计一致性假设。本文通过为转移模型提供便捷的估计保证,并引入一种利用最优确定性信念策略类的乐观算法,克服上述限制。改进了现有估计技术,对每个动作的转移矩阵提供独立理论保障。不同于以往无法融合不同策略样本的方法,我们提出一种新颖且简单的估计器,打破此瓶颈。结合提出的动作独立乐观采样-上置信界(Action-wise OAS-UCRL)算法与更紧的理论分析,首次实现相对于最优策略的 $ ilde{ m O}( oot T o)$ 忽略对数项的后悔率,优于当前最优技术。数值模拟验证了该方法在基准对比中的有效性。
原文摘要 · Abstract (English)
We tackle average-reward infinite-horizon POMDPs with an unknown transition model but a known observation model, a setting that has been previously addressed in two limiting ways: (i) frequentist methods relying on suboptimal stochastic policies having a minimum probability of choosing each action, and (ii) Bayesian approaches employing the optimal policy class but requiring strong assumptions about the consistency of employed estimators. Our work removes these limitations by proving convenient estimation guarantees for the transition model and introducing an optimistic algorithm that leverages the optimal class of deterministic belief-based policies. We introduce modifications to existing estimation techniques providing theoretical guarantees separately for each estimated action transition matrix. Unlike existing estimation methods that are unable to use samples from different policies, we present a novel and simple estimator that overcomes this barrier. This new data-efficient technique, combined with the proposed \emph{Action-wise OAS-UCRL} algorithm and a tighter theoretical analysis, leads to the first approach enjoying a regret guarantee of order $\mathcal{O}(\sqrt{T \,\log T})$ when compared against the optimal policy, thus improving over state of the art techniques. Finally, theoretical results are validated through numerical simulations showing the efficacy of our method against baseline methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。