提出新模型与算法，高效推断部分可观测环境下的奖励与状态转移逻辑。
Inferring Reward Machines and Transition Machines from Partially Observable Markov Decision Processes
- 引入过渡机补全奖励机，统一建模非马尔可夫性。
- 提出双行为梅丽机器与高效学习算法，速度比现有方法快1000倍。
- 适合研究强化学习中自动推理结构的学者与工程师。
部分可观测马尔可夫决策过程（POMDP）在众多实际应用中至关重要。尽管强化学习（RL）在完全可观测环境下表现优异，但在部分可观测环境中，由于观测不满足马尔可夫性，从轨迹中学习策略仍具挑战。已有方法通过推断自动机来处理非马尔可夫性，但存在两个局限：1）现有自动机仅针对基于奖励的非马尔可夫性建模，导致问题设定不自然；2）推断算法计算成本过高。为此，本文引入过渡机（TMs）以补充现有奖励机（RMs）。为统一两类自动机的推断，提出双行为梅丽机（DBMM），其包含并扩展了TMs和RMs。进一步提出被动自动机学习算法DB-RPNI，可高效推断DBMM，避免先前工作所需的高代价转换。同时设计优化技术，并识别出能推断最小正确自动机的充分条件。实验表明，该方法相较最先进基线实现最高达三个数量级的速度提升。
原文摘要 · Abstract (English)
Partially Observable Markov Decision Processes (POMDPs) are fundamental to many real-world applications. Although reinforcement learning (RL) has shown success in fully observable domains, learning policies from traces in partially observable environments remains challenging due to non-Markovian observations. Inferring an automaton to handle the non-Markovianity is a proven effective approach, but faces two limitations: 1) existing automaton representations focus only on reward-based non-Markovianity, leading to unnatural problem formulations; 2) inference algorithms face enormous computational costs. For the first limitation, we introduce Transition Machines (TMs) to complement existing Reward Machines (RMs). To develop a unified inference algorithm for both automata types, we propose the Dual Behavior Mealy Machine (DBMM) that subsumes both TMs and RMs. We then introduce DB-RPNI, a passive automata learning algorithm that efficiently infers DBMMs while avoiding the costly reductions required by prior work. We further develop optimization techniques and identify sufficient conditions for inferring the minimal correct automata. Experimentally, our inference method achieves speedups of up to three orders of magnitude over SOTA baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。