acceptodds
Under review as a conference paper at ICLR 2027

MATE: Solving Contextual Markov Decision Processes with Memory of Accumulated Transition Embeddings

Abstract

We propose MATE, a simple yet effective memory architecture for Contextual Markov Decision Processes (CMDPs), a family of MDPs parameterized by an unobserved context. In CMDPs, an optimal agent adapts online by updating its posterior belief over contexts with every new transition. MATE replaces this intractable update with a memory that additively accumulates transition embeddings, leveraging the posterior's permutation invariance to retain provably sufficient expressiveness. This design avoids both the growing per-step rollout cost of Transformers and the backpropagation through time of recurrent networks. We further propose STORE, a training algorithm that exploits the additive structure of MATE to train on a random subset of transitions per episode while reusing stored embeddings for the rest. STORE keeps the low cost of truncated-window training, yet it places no limit on the memory horizon and matches full-episode training in expectation. Across diverse benchmarks, MATE matches the performance of standard sequence-model baselines while being substantially faster to compute. Replacing truncated-window training with STORE lets MATE learn dependencies longer than the subset size and yields further performance gains.

Primary area:
reinforcement learning
Keywords:
Contextual MDPs, Meta-Reinforcement Learning, Memory-Based Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_5szFOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper addresses contextual Markov decision processes (CMDPs) in which the context is fixed within an episode but cannot be observed directly, using the sum of transition embeddings as memory. It motivates this structure through the permutation invariance of the context posterior and proposes STORE: recomputing embeddings for a random subset, reusing the remaining cached embeddings, and training at randomly sampled loss positions. When the cache exactly matches the current encoder, the encoder gradient scaled by T/k is an unbiased estimator of the full-trajectory gradient.

Critical strengths
  1. The architecture matches the problem structure. Proposition 4.1 on p. 5 and the theoretical appendix on pp. 14–17 provide explicit arguments for expressivity and gradient estimation. The main value lies in turning existing ideas about permutation-invariant representations into a memory architecture for policy and value networks, while enabling random-subset training to cover the full history.

  2. Efficiency and long-term memory are supported by experiments. Results on MuJoCo, Meta-World, and T-Maze cover reward variation, dynamics variation, and long-range memory. Figures 2–4 on pp. 6–8 support MATE’s efficiency and the benefits of STORE. With k=100, STORE still achieves the maximum return on Passive T-Maze at length 800, demonstrating that the training subset length can be separated from the length of usable history. The improvements on Meta-World are also more convincing than results restricted to already saturated tasks.

Critical weaknesses
  1. Performance and timing protocols are not fully aligned. Table 3 on p. 18 indicates that the GPT-2 performance results on Hopper and Walker use one layer, whereas Section B.3 on p. 19 states that Table 2 times a two-layer GPT-2. Full-run training times for Mamba and STORE are estimated through cross-device calibration, with a calibration error of approximately 20%; they are not all measured directly under a common setup. The “Measured” caption of Table 2 on p. 6 should explicitly identify these differences. Small gaps, such as 4.2 versus 4.5 hours on Cheetah-Vel, are insufficient to support a robust advantage on every task.

  2. Applicability is evaluated only in environments selected or adapted to fit the CMDP assumptions. Appendix C (pp. 20-22) describes settings with a fixed context within each episode and observations intended to be Markov given that context. In particular, T-Maze is explicitly modified to satisfy the CMDP formulation. These choices limit the evidence for applicability to more general environments, where hidden state or temporal dependencies may not be captured by a fixed context. The authors should clarify the scope of applicability and how much the reported performance depends on these environment choices and adaptations.

Questions for authors
  1. On representative long-memory tasks, how do STORE’s benefits change with exact caches or more frequent refreshes? Do the same advantages hold when Mamba or SplAgger is included and final or sustained performance is reported?
  2. Are there existing third-party benchmark environments on which MATE can be evaluated directly, without modifying their observations, rewards, or dynamics to satisfy the CMDP assumptions?
2 comments

Dear Reviewer 5szF,

Thank you for recognizing the strengths of MATE and STORE, and for catching the gaps in our timing protocol.


W1. Timing protocols are not aligned with Table 3 or measured under a common setup, and small gaps (4.2 vs. 4.5 h) do not support an advantage on every task.

We aligned the timing protocol with Table 3 (one-layer GPT-2 on Hopper-Param and Walker-Param), measured all models under a common setup, and updated Table 2 in the revised PDF. MATE is now 1.10–1.75× faster than every memory baseline on every task, far beyond the s.d. over seeds (≤2.1%). On Cheetah-Vel, 4.2 vs. 4.5 h becomes 0.87 vs. 0.98 h.

The common setup is a single RTX 5090 that runs one model at a time, with the full training time extrapolated from its rate after warm-up (App. B.3). The original Table 2 instead timed full runs, which take up to ten days on V100s, so it had to combine cross-device results by calibration. The extrapolation avoids this calibration error.

W2 & Q2. The CMDP assumptions limit the scope of applicability. Are there existing third-party benchmarks on which MATE can be evaluated directly? T-Maze is explicitly modified to satisfy the CMDP formulation.

We respectfully note that the CMDP setting is broad rather than narrow. It is the standard formulation of meta-RL, where a family of MDPs is parameterized by a context (Beck et al., 2025). The same structure arises in real-world problems such as sim-to-real transfer, healthcare, and autonomous driving, where physical parameters, patients, and road surfaces act as contexts governing the dynamics (Kirk et al., 2023).

Many existing meta-RL benchmarks are CMDPs by construction. All benchmarks in Fig. 2 needed no changes to satisfy the CMDP assumptions. T-Maze, in contrast, is not a meta-RL benchmark but a memory benchmark included to test the memory horizon, so casting it as a CMDP required modifications.

Q1-1. On long-memory tasks, how does STORE's performance change with exact caches or more frequent refreshes?

On a long-memory task (Table R1), STORE surprisingly matches or outperforms the exact cache and 2× and 4× more frequent refreshes at every LL except 1000. We see the same trend on Meta-World and conjecture that the inexact embeddings regularize training (see our response to Reviewer 3cw7, Q2). The exception at L=1000L=1000 suggests that the refresh ratio k/Tk/T should not be too low. We are running 2 more seeds to confirm these results and will update Table R1.

Table R1. STORE (k=100k=100) with different refresh rates. Maximum return on Active T-Maze, mean over 3 seeds. r×r\times refresh re-embeds rkrk transitions per update but backpropagates through only kk.

VariantL=200L=20040040060060080080010001000
1× refresh (STORE, Fig. 3 seeds 0–2)1.001.000.940.760.58
2× refresh1.001.000.870.630.62
4× refresh1.001.000.760.710.71
L/kL/k× refresh (exact cache)1.001.000.870.730.72

Q1-2. Do the advantages hold with Mamba or SplAgger, and in final or sustained performance?

We ran Mamba and SplAgger on T-Maze after the submission (Table R2). On the unsaturated Active T-Maze, STORE performs best at L≤400L\le400 but falls behind Mamba at L≥600L\ge600. The final return (italic in Table R2) shows the same trends. Our response to Reviewer 3cw7 (Q3) explains why the two returns agree.

STORE likely falls behind at large LL because the key information in T-Maze comes at the first step: MATE weighs all transitions equally, so the cue makes up only about 1/T1/T of the memory. Mamba can avoid this by learning to keep the cue in its hidden state and ignore the uninformative corridor steps.

The main advantage of STORE, however, is that it can learn dependencies longer than the subset size kk (up to L=8kL=8k on Passive T-Maze). Contiguous-window training, the default in prior work, cannot go beyond kk: GPT-2 fails to learn dependencies even one step longer than kk (Fig. 8).

Table R2. Maximum (final) return on Passive / Active T-Maze, mean over 5 seeds. Final return: mean over the last 10% of training. Bold: best maximum; italic: best final.

LLSTOREMambaSplAgger
2001.00 (1.00) / 1.00 (1.00)1.00 (1.00) / 0.92 (0.84)1.00 (0.99) / 1.00 (0.96)
4001.00 (1.00) / 1.00 (1.00)1.00 (0.99) / 0.88 (0.83)0.93 (0.87) / 0.92 (0.86)
6001.00 (0.98) / 0.89 (0.86)1.00 (1.00) / 0.97 (0.95)1.00 (0.98) / 0.78 (0.73)
8001.00 (1.00) / 0.80 (0.76)1.00 (1.00) / 0.87 (0.84)1.00 (0.98) / 0.71 (0.66)
10000.63 (0.57) / 0.54 (0.50)1.00 (0.99) / 0.81 (0.77)0.82 (0.78) / 0.57 (0.50)

We are glad to clarify any remaining concerns and hope our responses are reflected in your final assessment.

Best regards, The Authors

AuthorsOpenReview ↗

Table R1 Update

Dear Reviewer 5szF,


We have finished 2 more seeds and updated Table R1 to 5 seeds. As before, less frequent refreshes (i.e., inexact embeddings) can sometimes perform better. Unlike before, STORE is no longer the best at L=600L=600 and 800800, and the results show a more consistent trend where more frequent refreshes become optimal as LL grows.

Table R1 (Updated). STORE (k=100k=100) with different refresh rates. Maximum return on Active T-Maze, mean over 5 seeds. r×r\times refresh re-embeds rkrk transitions per update but backpropagates through only kk.

VariantL=200L=20040040060060080080010001000
1× refresh (STORE, Fig. 3)1.001.000.890.800.54
2× refresh1.001.000.920.780.64
4× refresh1.001.000.860.830.71
L/kL/k× refresh (exact cache)1.001.000.880.760.72

We hope this update is helpful, and we are happy to clarify anything further.

Reviewer_3cw7OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper focuses on contextual MDPs where the context is unobservable and remains fixed within a single round, and proposes the memory architecture MATE. MATE independently encodes and accumulates each transition in the history, using the resulting vector as the memory representation of the history. This achieves a constant memory update cost per step and supports parallel computation along the time dimension during training. The authors further propose STORE: at each update, it randomly recalculates a subset of transition embeddings, reuses the remaining cached embeddings, and computes the reinforcement learning loss at independently sampled time steps, thereby training long-range memory at a lower computing cost. Experimental results show that MATE reduces training time while maintaining performance comparable to baselines; when combined with STORE, it can learn long-range dependencies beyond the subset size and further improve rewards on some tasks.

Critical strengths

The method proposed in this paper is simple and efficient. Its theoretical foundation is based on observations regarding the invariance of the order under the posterior distribution. For the proposed memory-based method, the paper also presents a corresponding training algorithm and experimentally validates the algorithm’s effectiveness.

Critical weaknesses

Experimental and ablation analyses remain insufficient, particularly lacking systematic validation of the key mechanisms underlying STORE.

Questions for authors
  1. Is the comparison between STORE algorithm and other algorithms fair? Based on the description in Appendix B.1, STORE appears to have a broader range for selecting memory. Existing experiments have not conducted ablation studies.

  2. How can we address the shift caused by STORE reusing the original embeddings? During the encoder update process, the model mixes embeddings generated by the previous encoder with those generated by the new encoder. Won’t this introduce contamination into the training?

  3. In Figure 3, does the term “maximum evaluation return” refer to measuring the best performance achieved during training? If so, can the STORE method consistently outperform other methods in terms of some final performance metric?

2 comments

Dear Reviewer 3cw7,

We appreciate your constructive feedback. Below, we address your concern (W1) and answer your questions (Q1–Q3).


W1. Insufficient ablations, in particular for the key mechanisms of STORE.

We provide an additional ablation in Table R1. STORE (Alg. 1) has two mechanisms: random subsets, which spread the re-embedded transitions SS and the loss steps S′S' (kk each) over the episode, and reuse of stored embeddings, which lets the memory at a loss step include every earlier transition. Table R1 adds them one at a time to contiguous-window training, the default in prior work.

Table R1. Ablation of STORE. MATE on Active T-Maze, L=600L=600 (T=L+3T=L+3), k=100k=100. Maximum and final return (mean over the last 10% of training), averaged over 3 seeds. Both mechanisms of STORE are critical.

AlgorithmTransitions in memory at loss step ttMax / Final
Contiguous windowthose in the window before tt0.00 / 0.00
+ Random subsetsthose in SS before tt0.53 / 0.50
+ Reuse (STORE)all before tt0.94 / 0.92

On T-Maze, a return of 0 means the agent reaches the junction but picks no goal, 0.5 means it guesses, and 1 means it recalls the cue from the first transition. Contiguous windows cap the memory horizon at k<Tk<T (Sec. 5), so they can reach at most 0.5. We believe they stay near 0 because they include the end of the episode less often than random subsets do.

Q1. Is the comparison with other algorithms fair, given STORE's broader range for selecting memory (App. B.1)?

If "other algorithms" means contiguous-window training, the comparison is fair in compute, and on T-Maze STORE even costs less. In Fig. 2, STORE and contiguous-window training both encode kk transitions and compute the loss at kk steps per update. They differ only in whether these kk are contiguous or random, so the broader range adds almost no training time (Tab. 2). On T-Maze, STORE uses k=100k=100, while all other agents use k=Tk=T.

If "other algorithms" means the other memory baselines (e.g., GPT-2, LSTM), they cannot select memory from such a broad range at the same cost as STORE. STORE can do this because MATE's memory is a sum of per-transition embeddings, so any embedding can be replaced without touching the others (Sec. 5). Training the baselines on random subsets without reuse (Table R1, second row) is possible in principle, but unnatural for sequence models. We have not run it yet, but would be happy to add it if you are interested.

Q2. How can the shift from reusing the original embeddings be addressed? Won't it hurt training?

First of all, STORE does not keep reusing the original embeddings, since each stored embedding is updated whenever it is re-embedded (Alg. 1, line 6). Moreover, our additional experiments (Table R2) suggest that the remaining shift does not need to be addressed further. It is measurable, but it does not hurt training and even raises the final return.

Table R2. STORE / exact cache, which sets zˉi=sg(Eψ(xi))\bar z_i=\mathrm{sg}(E_\psi(x_i)) for all ii before each update, as Prop. 5.1 assumes. Errors$^\ast$ and final return are averaged over the last 10% of training and 3 seeds. STORE has a larger error but a higher final return.

Error (ziz_i)Error (mean)Final return
ML100.86 / 0.640.36 / 0.122377 / 2156
ML450.79 / 0.590.32 / 0.111661 / 1348
Active T-Maze (L=600L=600)0.38 / 0.310.19 / 0.160.92 / 0.83

∗^\ast ∥v−vˉ∥/∥v∥\|v-\bar v\|/\|v\| for v=ziv=z_i (i∈Si\in S) and their mean over SS.

The shift is measurable, as STORE's error is larger than that of the exact cache, whose error comes only from dropout noise in the encoder. This noise is fairly large per embedding (ML10: 0.64) but much smaller for the mean (0.12).

The shift raises the final return. We conjecture that the extra noise on the memory regularizes training, like dropout. Consistent with this, STORE has about twice the TD loss of the exact cache on Meta-World, yet a higher return.

Q3. Is the maximum evaluation return in Fig. 3 the best during training? Can STORE outperform others in final return?

Yes, it is the best during training, and each evaluation return is the mean over 64 environments. STORE still outperforms others in final return on Active T-Maze at L=400L=400, 600600, and 800800, as in Fig. 3.

This is because the maximum return exceeds the final return only by evaluation noise, as in Table R1. On T-Maze, the expected return of a policy is 0, 0.5, or 1 (see W1), or 0.75 on Active T-Maze if it solves the task only for one of the two distractor values. With 64 environments, the evaluation return stays close to these levels.


Thank you for the time and care you put into reviewing our work. If any concern remains, we would be happy to clarify it further. If our responses address your main concerns, we would appreciate it if this could be reflected in your evaluation.

Best regards, The Authors

AuthorsOpenReview ↗

Short summary of our response

Dear Reviewer 3cw7,

Thank you again for your review. As you may be busy and the discussion period ends soon, here is a short summary of our response.


  • W1 (ablation of STORE): We ran an ablation (Table R1) that adds the two mechanisms of STORE, random subsets and reuse of stored embeddings, one at a time. Both are critical: the return on Active T-Maze goes from 0.00 to 0.53 to 0.94.

  • Q1 (fairness): STORE and contiguous-window training encode the same number of transitions (kk) and compute the loss at the same number of steps per update, so the compute is matched. On T-Maze, STORE even uses a smaller kk.

  • Q2 (embedding shift): Stored embeddings are refreshed whenever they are re-embedded. Compared with an exact cache (Table R2), the shift is measurable but does not hurt training, and STORE even reaches a higher final return.

  • Q3 (max vs. final return): The maximum return is the best return during training, and the final return shows the same trends: STORE is still the best agent in Fig. 3 on Active T-Maze at L=400L=400–800800. Mamba, added in our response to Reviewer 5szf (Q1-2), outperforms STORE at large LL.


We would be happy to clarify any remaining concern. Otherwise, we would be grateful if you could consider updating your evaluation.

Best regards, The Authors

Reviewer_gxpkOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces a new memory architecture for contextual MDPs (CMPDs).

Specifically, CMDPs are MDPs that contain an unobserved latent factor, C, which is static during a given episode.

This paper exploits that the posterior is invariant to the ordering of the transitions by suggesting an embedding mechanism, phi(X_t), for as the memory representation. Here X_t is a transition at time t.

To maintain order-invariance the memory vector is the sum of the embeddings up to time t. The simplicity of the memory structure also has computational advantages since it be computed in parallel and in linear time.

Both theory and experiments show that this simple memory representation is sufficient for CMDPs, resulting in compelling performance and computational efficiency.

Finally, the authors also present a further efficiency improvement whereby only a random subset of transitions receives backwards gradients at a given timestep.

Critical strengths
  • this is a simple, well motivated method that is well suited for the problem domain.
  • The results are compelling and the evaluation is reasonable.
Critical weaknesses

-None

Questions for authors
  • how did you tune your hyper-parameters?
  • did you have any comparisons to state-space models?
  • the choice of learning algorithm is slightly odd -- what about e.g. PPO?
1 comment

Dear Reviewer gxpk,

Thank you for the time and effort you put into reviewing our paper, and for recognizing MATE as a simple, well-motivated method that suits the problem domain and achieves compelling results. Below, we answer your questions (Q1–Q3).


Q1. How did you tune your hyper-parameters?

We tuned only the hyperparameters that affect training stability, kept the others at their initial values, and used the same values for every memory architecture.

RL is less stable than supervised learning, especially in memory-based RL with sequence models. To let every memory architecture train reliably across all benchmarks and allow a meaningful comparison, we tuned the target update rate, the learning rate, and the gradient clipping threshold (Tables 4 and 5). Larger values of all three speed up training but reduce stability, so we chose them conservatively, as the smallest values with which training still progressed well.

We set the remaining RL hyperparameters based on Ni et al. (2023) and AMAGO (Grigsby et al., 2024a;b), adapting them to our setting. For example, the freeze-critic setting in Table 4 follows the recommendation of Ni et al. (2023). The architecture settings in Table 3 were not tuned either. Instead, we scaled the memory size and depth roughly with task complexity and adapted the subset size kk from the AMAGO codebase. The only architecture-specific choice is GPT-2's single layer on Hopper-Param and Walker-Param, where two layers performed poorly.

Q2. Did you have any comparisons to state-space models?

Yes. Mamba (Gu & Dao, 2024), one of our memory baselines, is a state-space model. Fig. 2 compares Mamba with MATE on the four MuJoCo tasks and Meta-World ML10/ML45: Mamba attains the highest return on Ant-Dir and Walker-Param, while MATE attains a higher return on ML10 and ML45. Table 2 and Fig. 4 compare their compute cost: MATE trains 1.4–1.9× faster than Mamba (Table 2), and its memory module runs about 2× faster in rollout and 2–5× faster in update across all tested sequence lengths (Fig. 4). We also ran Mamba on T-Maze after the submission and report the results in our response to Reviewer 5szF (Q1-2), where Mamba outperforms MATE + STORE as the maze gets longer.

Q3. The choice of learning algorithm is slightly odd. What about, e.g., PPO?

We use SAC and DDQN because our codebase and baselines follow the off-policy memory-based RL setup of Ni et al. (2023) and AMAGO (Grigsby et al., 2024a;b).

PPO can also be used with MATE without changes, since MATE does not depend on a specific RL algorithm. STORE should carry over as well, and its stored embeddings would stay nearly exact because PPO updates on freshly collected data. We expect this combination to be an interesting extension.

We nonetheless could not include PPO results, as we focused our compute budget on more memory baselines and benchmarks. Since our work proposes MATE as a memory architecture, we prioritized comparing it with more memory baselines and testing it on a wider range of memory capabilities. Specifically, we compared MATE with GPT-2, LSTM, SplAgger, Mamba, and a memory-free Markov policy across MuJoCo, Meta-World, T-Maze, Alchemy, and Vehicle Racing. We note the off-policy-only evaluation as a limitation in Sec. 7 of the revised paper.


References

  • Tianwei Ni, Michel Ma, Benjamin Eysenbach, and Pierre-Luc Bacon. When do transformers shine in rl? decoupling memory from credit assignment. Advances in Neural Information Processing Systems, 36:50429–50452, 2023.
  • Jake Grigsby, Jim Fan, and Yuke Zhu. Amago: Scalable in-context reinforcement learning for adaptive agents. In International Conference on Learning Representations, volume 2024, pp. 26919–26952, 2024a.
  • Jake Grigsby, Justin Sasek, Samyak Parajuli, Daniel Adebi, Amy Zhang, and Yuke Zhu. Amago-2: Breaking the multi-task barrier in meta-reinforcement learning with transformers. Advances in Neural Information Processing Systems, 37:87473–87508, 2024b.
  • Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. In First conference on language modeling, 2024.

Thank you again for your encouraging review and thoughtful questions.

Kind regards, The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.