提出新方法解决非安全LTL规划中策略迭代不收敛问题
Exact Model-Free Policy Iteration for Co-safe LTL Planning
- 用折扣代理识别约束集，破解贝尔曼方程解的不唯一性
- 结合无折扣评估与贪心改进，确保找到最优策略
- 理论证明几乎必然收敛，适合形式化验证场景
本文研究有限马尔可夫决策过程中的非模型强化学习，针对可安全线性时序逻辑（sc-LTL）目标。通过标准产品构造，该问题可转化为最大可达性目标。传统基于样本的自举方法（如TD或Q-learning）可能因贝尔曼方程的非压缩性与解的不唯一性而无法收敛至最优策略。本文提出一种两步式无模型强化学习方法：首先利用折扣代理识别一个约束集以解决解的不唯一性；随后采用无折扣策略评估与贪心策略改进，保证找到最优解。理论证明策略评估步骤几乎必然收敛，策略迭代算法在有限步内终止于最优策略。数值实验在随机网格世界中验证了方法的有效性。
原文摘要 · Abstract (English)
This work studies model-free reinforcement learning for co-safe linear temporal logic (sc-LTL) objectives in finite Markov decision processes, which can be reduced to maximal reachability objectives via the standard product construction. For this problem, direct sample-based bootstrap methods (e.g., TD or Q-learning) may fail to converge to optimal policies due to the noncontractive nature and nonuniqueness of solutions to the Bellman equation. We develop a new two-step model-free reinforcement learning method that first uses a discounted surrogate to identify a clamp set that resolves this nonuniqueness, and then applies undiscounted policy evaluation and greedy policy improvement with guarantees of finding an optimal solution. We prove almost-sure convergence of the policy evaluation step and finite termination of the policy iteration algorithm at an optimal policy. These theoretical results are validated through numerical experiments on a stochastic grid world.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。