Inferring Reward Machines and Transition Machines from Partially Observable Markov Decision Processes
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Reinforcement LearningSimilar Papers 제목 키워드 기반
A Hierarchical Bayesian Approach to Inverse Reinforcement Learning with Symbolic Reward Machines
A misspecified reward can degrade sample efficiency and induce undesired behaviors in reinforcement learning (RL) problems. We propose symbolic reward machines for incorporating high-level task knowledge when specifying …
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Learning Reward Machines from Partially Observed Policies
Inverse reinforcement learning is the problem of inferring a reward function from an optimal policy or demonstrations by an expert. In this work, it is assumed that the reward is expressed as a reward machine whose trans…
Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning
The success of reinforcement learning in typical settings is predicated on Markovian assumptions on the reward signal by which an agent learns optimal policies. In recent years, the use of reward machines has relaxed thi…
Decision Makingreinforcement-learningReinforcement LearningReinforcement Learning (RL)Learning Reward Machines for Partially Observable Reinforcement Learning
Reward Machines (RMs), originally proposed for specifying problems in Reinforcement Learning (RL), provide a structured, automata-based representation of a reward function that allows an agent to decompose problems into …
Partially Observable Reinforcement LearningProblem Decompositionreinforcement-learningReinforcement Learning+1Learning Reward Machines: A Study in Partially Observable Reinforcement Learning
Reinforcement learning (RL) is a central problem in artificial intelligence. This problem consists of defining artificial agents that can learn optimal behaviour by interacting with an environment -- where the optimal be…
Partially Observable Reinforcement LearningProblem Decompositionreinforcement-learningReinforcement Learning+1