MATE: Solving Contextual Markov Decision Processes with Memory of Accumulated Transition Embeddings
Himchan Hwang, Hyeokju Jeong, Gene Chung, Seungyeon Kim, Sangwoong Yoon, Frank Chongwoo Park · 2026
Read MATE: Solving Contextual Markov Decision Processes with Memory of Accumulated Transition Embeddings by Himchan Hwang, Hyeokju Jeong, Gene Chung, Seungyeon Kim, Sangwoong Yoon, Frank Chongwoo Park (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-17431.txt.
Introduction
Hwang and colleagues propose MATE, a memory design for contextual Markov decision processes, where an unseen context shapes each task. Instead of tracking an intractable posterior belief over contexts, MATE keeps a sum-aggregated memory that exploits permutation invariance for proven sufficient expressiveness. It avoids transformers' growing rollout cost and recurrent nets' gradient troubles. Tests match sequence-model baselines on diverse benchmarks at lower compute cost.
Catalog record
| CREATOR | Himchan Hwang, Hyeokju Jeong, Gene Chung, Seungyeon Kim, Sangwoong Yoon, Frank Chongwoo Park |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48714 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.17431
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
MATE: Solving Contextual Markov Decision Processes with Memory of Accumulated Transition Embeddings Himchan Hwang, Hyeokju Jeong, Gene Chung, Seungyeon Kim, Sangwoong Yoon, Frank Chongwoo Park Abstract We propose MATE, a simple yet effective memory architecture for solving Contextual Markov Decision Processes (CMDPs), a family of MDPs parameterized by an unobserved context. In CMDPs, an optimal agent can adapt online by maintaining the posterior belief over contexts. MATE replaces this intractable posterior with a sum-aggregated memory, leveraging the posterior’s permutation invariance to retain provably sufficient expressiveness. Compared to prior memory architectures, MATE avoids the growing per-step rollout cost of Transformers and the gradient issues commonly associated with Recurrent Neural Networks (RNNs). Extensive evaluations across diverse benchmarks demonstrate that MATE provides clear computational advantages while achieving performance comparable to standard sequence-model baselines. 1 Introduction Solving Contextual Markov Decision Processes (CMDPs) ( 19 ) enables RL agents to operate beyond fixed simulation environments, extending to real-world applications with inherent variations, such as sim-to-real transfer, healthcare, and autonomous driving ( 24 ) . In these settings, environmental variations are governed by a latent context. To adapt effectively, an optimal agent must infer this context from its interaction history—a capability beyond the reach of standard state-dependent policies. A prominent solution is memory-based RL, where sequence models are trained end-to-end to encode transition histories into a policy-accessible memory. 27 demonstrated the efficacy of this approach using RNNs, outperforming prior specialized methods. More recently, 15 ; 16 achieved strong performance in multi-task and long-horizon domains by leveraging Transformer architectures. However, these architectures face distinct limitations: RNNs suffer from gradient instabilities ( 7 ; 29 ) and preclude temporal parallelization during the update step ( 26 ) . Conversely, Transformers incur quadratic computational costs with respect to sequence length during both the update step and trajectory rollout, often necessitating a limited context window ( 6 ) . In this paper, we propose a memory-based RL agent that exploits the permutation invariance of the context posterior in CMDPs (see Figure 1 ). In a CMDP, the posterior belief over the context is invariant to the ordering of transition data. We argue that an optimal memory-based RL agent should inherently incorporate this inductive bias. While bidirectional Transformers can capture such invariance, the cost of re-encoding the full history at each step is prohibitive. Thus, causal Transformers are generally utilized in memory-based RL despite lacking this property. Figure 1 : Overview of MATE. MATE represents the memory m_{t} as a summation of transition embeddings, serving as a tractable substitute for the intractable posterior p(c|x_{1:t}) . By preserving the permutation invariance of the posterior, \pi_{\theta} is provably capable of representing the optimal policy \pi^{*} , despite its structural simplicity. Motivated by this perspective, we propose MATE ( M emory of A ccumulated T ransition E mbeddings), a sum-aggregated memory architecture for solving CMDPs (see lower-left of Figure 1 ). By design, MATE guarantees permutation invariance across transition histories while avoiding the complexity of recurrent layers and attention mechanisms. Notably, MATE preserves the computational advantages of prior approaches: it enables temporal parallelization during the update step (like Transformers) while maintaining a linear computational cost with respect to sequence length (like RNNs). While 4 employed a similar mean aggregation of linear embeddings as a baseline, we extend this idea by adopting sum aggregation over embeddings produced by arbitrary neural networks. We validate our model from both theoretical and empirical perspectives. Theoretically, we show that an agent equipped with MATE retains sufficient expressiveness to represent the optimal policy by leveraging permutation invariance in CMDPs. Empirically, we demonstrate that MATE achieves competitive or superior performance compared to Transformer and RNN baselines across diverse benchmarks. Our results highlight its effective adaptation to variations in dynamics, rewards, and tasks (MuJoCo, Meta-World), as well as its handling of long-term memorization and credit assignment challenges (T-Maze). 2 Preliminaries 2.1 Contextual MDP A Contextual Markov Decision Process (CMDP) ( 19 ) is defined as a set of MDPs \{(\mathcal{S},\mathcal{A},P_{c})\mid c\in\mathcal{C}\} , where \mathcal{S} , \mathcal{A} , and \mathcal{C} denote the state, action, and context spaces. The unobserved context c determines the transition kernel P_{c} , given by p(s_{t+1},r_{t}|s_{t},a_{t},c) . A CMDP can be viewed as a special case of a partially observable MDP (POMDP) ( 8 ) where the unobserved state is the context. The goal in a CMDP is to find an optimal policy \pi^{*} that maximizes the expected discounted return under the context prior p(c) : \displaystyle\max_{\pi}\ \mathbb{E}_{c\sim p(c),\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{t}\right], (1) where \gamma is the discount factor. Thus, the optimal agent generalizes across MDPs induced by different contexts and adapts to the current MDP within an episode. For CMDPs, the optimal policy and value function can be expressed as functions of the current state s_{t} and the posterior belief over contexts p(c|x_{1:t}) : \displaystyle\pi^{*}(a_{t}|s_{t},p(c|x_{1:t})),\quad V^{*}(s_{t},p(c|x_{1:t})). (2) Here, x_{t}=(s_{t-1},a_{t-1},r_{t-1},s_{t}) denotes the transition at time t . This formulation is derived by casting the CMDP as an MDP with an augmented state s_{t}^{+}=(s_{t},p(c|x_{1:t})) ( 11 ; 39 ) . However, exact posterior inference is typically intractable, as it requires knowledge of the unknown transition kernel P_{c} and may not admit a finite-dimensional representation. 2.2 Memory-based RL To learn history-dependent policies as required in CMDPs ( Equation 2 ), leveraging sequence models to compress the transition history into a latent memory has emerged as a promising approach ( 27 ; 5 ; 15 ; 16 ) . In this work, we refer to this general framework as memory-based RL . Memory-based RL employs a memory network m_{\psi} , parametrized by \psi , that summarizes the transition history into a finite-dimensional memory m_{t}=m_{\psi}(x_{1:t})\in\mathbb{R}^{m} . This is then used to condition the memory-augmented policy and value networks: \displaystyle\pi_{\theta}(a_{t}|s_{t},m_{t}),\quad V_{\phi}(s_{t},m_{t}). (3) All networks are jointly trained with RL. Existing methods vary in the critic formulation ( V_{\phi} , Q_{\phi} , or none) and in how the networks are conditioned (on (s_{t},m_{t}) or on m_{t} alone). We use Equation 3 as a representative case in our analysis. Transformers ( 15 ; 16 ; 32 ) and RNNs ( 10 ; 27 ; 5 ) , or their variants ( 3 ; 4 ; 21 ) , are the standard choices for m_{\psi} . RNNs offer the advantage of constant inference costs during rollout, but their recurrent nature often leads to gradient instabilities during the update step ( 7 ; 29 ) . Transformers excel at long-term memorization ( 28 ) , but their reliance on attention mechanisms incurs linearly growing inference costs per rollout step. 3 Methods In this section, we introduce M emory of A ccumulated T ransition E mbeddings ( MATE ), a simple sum-aggregated memory architecture for CMDPs that addresses the limitations of Transformers and RNNs. We first formalize permutation invariance in CMDPs in Section 3.1 , which serves as the foundation of our model. We then describe the detailed architecture of MATE and its computational advantages over Transformers and RNNs in Section 3.2 . In Section 3.3 , we establish that MATE provides a theoretically grounded representation for solving CMDPs. Finally, we introduce a normalization technique in Section 3.4 to prevent memory divergence in practice. 3.1 Permutation Invariance in CMDPs The permutation invariance of the context posterior p(c|x_{1:t}) is a fundamental property in