Research map / Reinforcement learning / Visual and representation RL
Balancing Context Length and Mixing Times for Reinforcement Learning at Scale
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretically and empirically links policy context length to mixing time in partially observable RL, showing longer contexts (especially Transformers and Decision Transformers) slow reliable policy evaluation.
Problem
Longer context lengths help policies model non-Markovian dependencies but may increase mixing times, making policy evaluation and downstream learning slower; the paper asks whether and how context length limits performance benefits.
Approach
Derives a mixing time bound O(1/(β^g) log(1/ε)) based on the size of strongly connected components in the state-variable dependency graph, and shows that restricting a policy's context length shrinks/loosens this structure, tightening the bound and trading off model expressivity against evaluation time.
Key results
- Decision Transformer with k=25 reaches optimal training accuracy only for k>=50 in general, versus behavior-policy context length 1; its average mixing time at eps=0.01 is 86,834.3 steps versus 3,271.2 steps for the behavior policy.
- In the RGB world online Q-learning experiments over 100 seeds, Transformer models show higher encountered mixing times at intermediate reward rates than MLP, LSTM, and tabular models.
- In the irrelevant-variables toy MDP, the optimal policy has mixing time 17.6 while a policy conditioned on both variables can reach 340.3 mixing time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the Decision Transformer context length to k = 25 | Decision Transformer trained on Minigrid Crossing behavior-policy data · Minigrid Crossing | training accuracy | Helped |
| Increase context length from the behavior policy's k = 1 to Decision Transformer k = 25 | Decision Transformer on Minigrid Crossing · Minigrid Crossing | average mixing time: 11.2 episodes -> 298.1 episodes | Hurt |
| Increase context length | Policies in partially observable environments · Partially observable environments | mixing time | Hurt |
| Use a Transformer instead of tabular, MLP, or LSTM policies | Q-learning agents in RGB world · RGB world | encountered mixing time | Hurt |
| Increase model capacity | MLP and LSTM policies · RGB world | encountered mixing time | No clear effect |
| Increase model capacity | Transformer policies · RGB world | encountered mixing time | Hurt |
| Use unnecessarily large context lengths rather than the minimal context length that achieves 100% training accuracy (ablation) | Decision Transformer · Minigrid Crossing | downstream performance | Hurt |
Surprising findings
- Transformer policies experience higher mixing times than alternative function approximators at intermediate reward rates.
- Decision Transformers need a context length far larger than the behavior policies' context length (k>=50 vs 1) to fit training data.
Limitations
- Theory applies to finite-state MDPs/POMDPs under unichain and aperiodic assumptions; bound may be loose when all variables influence all observations.
- Experiments are small-scale toy and Minigrid domains rather than large-scale environments.
Experimental setup
Datasets: Minigrid Crossing rollouts from 1,000 random deterministic behavior policies 1,000 episodes from REINFORCE agents RGB world environment (T-maze inspired)
Benchmarks: RGB world Minigrid Crossing toy irrelevant-variables and independent-subtasks MDPs
Metrics: epsilon-return mixing time training accuracy average return
Baselines: MLP LSTM tabular Q-learning REINFORCE
Builds on: Kearns and Koller (2000) mixing time bounds Riemer et al. mixing time in continual RL Decision Transformer Kearns and Singh return mixing time
Closest papers by meaning
- XLand-100B: A Large-Scale Multi-Task Dataset for In-Context Reinforcement Learning (ICLR 2025 · similarity 0.89)
- Adaptive Context Length Optimization with Low-Frequency Truncation for Multi-Agent Reinforcement Learning (NeurIPS 2025 · similarity 0.88)
- Towards Provable Emergence of In-Context Reinforcement Learning (NeurIPS 2025 · similarity 0.88)
- Scaling Long-Horizon Agent via Context Folding (ICML 2026 · similarity 0.88)
- Zero-Shot Context Generalization in Reinforcement Learning from Few Training Contexts (NeurIPS 2025 · similarity 0.88)
- MultiScale Contextual Bandits for Long Term Objectives (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.