在无 MEC 的 MDP 中使用 Q-Learning 进行可达性分析

arXiv:2610.01781v1 发布类型：cross 摘要：针对可达性规约的强化学习（RL）是序贯决策的基础。已有研究确立了收敛至最优策略的渐近性质，但仅限于基于模型的方法，这类方法必须显式估计底层马尔可夫决策过程（MDP）的转移概率。我们提出了 Quasar，这是首个在不含非终端最大内端分量（MEC）的 MDP 子类上为可达性提供渐近保证的无模型算法；通过标准的 MEC 商构造，每个 MDP 都可以规约到这一基础子类。我们的算法遵循经典的 Q-learning 方法，利用时序差分更新，在完全不学习转移概率的情况下收敛至最优策略。由此得到的学习器将基于模型方法所需的 O(|S|^2|A|) 内存占用降低至 O(|S||A|)。在标准化的 Quantitative Verification Benchmark Set 上，与此前基于模型的最先进方法相比，我们的算法仅需数量级更少的样本即可收敛至最优策略。这些成果共同构成了迈向可达性学习实际部署的具体一步，也推动了规约引导的强化学习的发展。