TLDR: A new research paper introduces Transition Machines (TMs) to complement existing Reward Machines (RMs), addressing both transition and reward dependencies in Partially Observable Markov Decision Processes (POMDPs). They propose the Dual Behavior Mealy Machine (DBMM) as a unified framework and an efficient algorithm, DB-RPNI, to infer these automata. This approach, combined with optimization techniques, significantly speeds up the inference process (up to three orders of magnitude) and enables standard reinforcement learning algorithms to effectively solve complex tasks in partially observable environments by restoring the Markov property.
In the realm of artificial intelligence, particularly in reinforcement learning (RL), agents often face the challenge of making decisions in environments where they don’t have complete information about their surroundings. These scenarios are formally known as Partially Observable Markov Decision Processes, or POMDPs. A core difficulty in POMDPs is that identical observations might require different actions depending on the agent’s past experiences, a phenomenon known as non-Markovianity. This makes it incredibly difficult for standard RL algorithms to learn effective strategies.
Historically, a promising approach to tackle this has been the use of ‘Reward Machines’ (RMs). These act as external memory structures, helping agents understand how past events influence future rewards, thereby restoring a more predictable, or Markovian, property to the reward function. However, existing RM approaches have two main limitations: they primarily focus only on reward-based non-Markovianity, and the algorithms used to infer these machines are computationally very expensive, limiting their practical application.
A recent research paper, titled “Inferring Reward Machines and Transition Machines from Partially Observable Markov Decision Processes,” introduces a novel framework to address these challenges. Authored by Yuly Wu, Jiamou Liu, and Libo Zhang from The University of Auckland, the paper proposes a more comprehensive solution for decision-making under uncertainty.
The key insight of this research is that non-Markovian behavior in POMDPs stems from two distinct sources: ‘reward dependencies’ (how rewards are influenced by past context) and ‘transition dependencies’ (how the next unobserved state depends on hidden historical events). While RMs handle the former, the paper introduces ‘Transition Machines’ (TMs) to explicitly model the latter. TMs function similarly to RMs but predict the next observation based on historical context, rather than rewards. This dual approach naturally separates the learning problem, making it more manageable.
To unify the inference process for both TMs and RMs, the researchers propose the ‘Dual Behavior Mealy Machine’ (DBMM). This innovative framework subsumes both types of automata under a single formalism, allowing for a single, efficient algorithm to infer both. The paper then introduces ‘DB-RPNI,’ a passive automata learning algorithm specifically designed to infer DBMMs directly from observed experience traces. This direct inference method avoids the computationally intensive problem reductions that prior works often relied upon.
Furthermore, the research incorporates several optimization techniques to enhance efficiency and the quality of the inferred automata. These include preprocessing steps like ‘Redundant α-Input Removal’ and ‘Trivial β-Input Removal,’ which simplify the data by eliminating irrelevant patterns. A particularly impactful technique is ‘Observation Supplement,’ where observations are augmented with TM states before RM inference. This step effectively decouples transition-based non-Markovianity, leading to more compact and interpretable RMs.
The experimental results are compelling. The proposed method demonstrates significant efficiency advantages over state-of-the-art baselines, achieving speedups of up to three orders of magnitude. For instance, in a 4×4 grid environment, their method took only 3.9 seconds compared to thousands of seconds for other approaches. In larger, more complex environments where baselines failed to complete, their approach successfully inferred the correct automata within minutes. Crucially, the ablation studies confirmed the vital contribution of each optimization component, especially in low-data scenarios.
Ultimately, the practical utility of this approach was validated by integrating the inferred TMs and RMs with a standard Q-learning agent. When trained in a complex 25×25 partially observable grid environment, the agent successfully converged to an optimal policy. This demonstrates that the inferred automata effectively restore the Markov property, enabling standard reinforcement learning algorithms to solve complex, non-Markovian decision-making problems.
Also Read:
- New Framework Enhances Robustness and Efficiency in AI Decision-Making
- Efficient Planning Under Uncertainty: A New Message Passing Approach for AI Agents
While currently focused on deterministic POMDPs, this foundational work paves the way for future extensions to stochastic environments and less stringent data assumptions. For more details, you can read the full research paper here.
