未知 MDP 中几乎必然可达性的证书学习与验证

研究在未知 MDP 中仅凭采样访问验证策略是否满足几乎必然可达性，其正确性由 ranking supermartingale（RSM）证书见证。结果表明：无额外信息时既无法学习也无法验证此类证书；但在已知非零转移概率下界 p_min 的温和限制下，可用 PAC 式保证学习到正确证书。实验显示基于 p_min 的充分条件虽可靠但偏保守，条件失效时学到的证书在真实 MDP 上往往仍有效。