- Rating
- 1
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper focus on fixed-policy TD evaluation to study the context sizes in in-context reinforcement learning. They found that the context size should be at least the dimension of Krylov space spanned by the transition kernal. Also, they characterize the error under the limited context size. Their experiments supports their theoretical prediction on the limited context window error. At last, the conduct experiments to illustrate the storage efficieny of their method.
Critical strengths
The experiments to support their theorems are clear.
Critical weaknesses
The paper is not well presented. The contribution of this paper is not clear to me.
Questions for authors
-
The paper presentation is not clear to me: what contribution is made by this paper uniquely? And what techniques are used in this paper to distinguish from previous works? Section 4 provides a series of results, but it is a general storage-efficient method for me. I believe that other storage-efficient mthods have been adopted in practice, while there is no fair compaison. Therefore, I can only get the conclusion that: "this paper analyzes a storage-efficient method", rather than "a supirior method is proposed in this paper".
-
The paper compared storage to other works in Table 1. However, those works do not focus on storage efficiency. Is this comparison fair?
3 comments
- References
[1] Wang, Jiuqi, Ethan Blaser, Hadi Daneshmand, and Shangtong Zhang. "Transformers Can Learn Temporal Difference Methods for In-Context Reinforcement Learning." The Thirteenth International Conference on Learning Representations (ICLR). 2025.
[2] Wang, Jiuqi, Rohan Chandra, and Shangtong Zhang. "Towards Provable Emergence of In-Context Reinforcement Learning." Advances in Neural Information Processing Systems 38 (NeurIPS). 2025.
[3] Xie, Zixuan, Xinyu Liu, Rohan Chandra, and Shangtong Zhang. "Convergence and Emergence of In-Context Reinforcement Learning with Chain of Thought." arXiv preprint arXiv:2605.07123. 2026.
[4] Xie, Zixuan, Xinyu Liu, Claire Chen, Shuze Daniel Liu, Rohan Chandra, and Shangtong Zhang. "Beyond Linear Attention: Softmax Transformers Implement In-Context Reinforcement Learning." arXiv preprint arXiv:2605.07333. 2026.
[5] Arnoldi, Walter E. "The Principle of Minimized Iterations in the Solution of the Matrix Eigenvalue Problem." Quarterly of Applied Mathematics 9, no. 1: 17–29. 1951.
[6] Saad, Yousef. "Analysis of Some Krylov Subspace Approximations to the Matrix Exponential Operator." SIAM Journal on Numerical Analysis 29, no. 1: 209–228. 1992.
[7] Freund, Roland W. "Model Reduction Methods Based on Krylov Subspaces." Acta Numerica 12: 267–319. 2003.
[8] Likhosherstov, Valerii, Krzysztof M. Choromanski, Jared Quincy Davis, Xingyou Song, and Adrian Weller. "Sub-Linear Memory: How to Make Performers SLiM." Advances in Neural Information Processing Systems 34 (NeurIPS), 2021.
Dear Reviewer aPFW,
Thank you again for your valuable feedback. As the discussion period is approaching its end, we would greatly appreciate it if you could review our rebuttal and let us know if you have any remaining concerns.
Thank you for your time and consideration.
We thank reviewer aPFW for the valuable comments and suggestions. We have revised the paper to better highlight our theoretical contributions. Please find our response below.
- Main contribution: Characterizing context complexity
Our primary motivation is to understand how much Transformer context is needed for in-context reinforcement learning. To this end, we theoretically characterize the context complexity of in-context RL through a natural algebraic structure, the Krylov subspace. Specifically, we establish that the Krylov dimension exactly characterizes the minimum context dimension required for a Transformer to reproduce TD learning. To the best of our knowledge, no prior work has provided such a theoretical characterization of the context complexity required for in-context RL. We have made this contribution more explicit in the abstract, introduction, and corresponding theoretical sections.
- Unique technical novelty
Our technical novelty consists of two main parts: (1) an exact characterization of the minimum context dimension required for TD learning (2) an approximation analysis that quantifies the error when the available context dimension is smaller than the minimum required for exact TD learning.
Unlike prior Transformer constructions that implement TD learning while retaining the transition history [1,2,3,4], we compresses raw transitions into a Krylov representation, and prove its optimality. This characterizes the context complexity of in-context reinforcement learning. We realize the compression and the TD-learning updating within the forward pass of a fixed-parameter Transformer. Moreover, we bridge theoretical context complexity and practical memory costs by establishing tight upper and lower bounds on retained task memory, achieving an optimal complexity of Θ(nkL) for exact representations.
We further analyze the setting when the context dimension below the dimension for exact TD learning. We establish matching upper and lower bounds for the optimal dimension-m approximation error, i.e.,
\Theta\left(\gamma^m \max\left\\{1,\frac{1}{m(1-\gamma)}\right\\}\right),
Compared with classical Arnoldi [4,5] and Krylov projection methods [6], our approach achieves a strictly tighter upper bound. Moreover, we prove that these traditional methods are provably suboptimal and cannot attain the minimax-optimal rate.
Additionally, we believe that our approximation framework has the potential to further strengthen classical Krylov-based approximation methods and extend their applicability to broader trajectory-approximation problems.
- Purpose of Table 1
We would like to clarify that Table 1 is intended to compare theoretical complexity characterizations and guarantees, rather than compression performance. The reported memory values serve only to provide a more intuitive interpretation of the theoretical complexity measures. Such comparisons of theoretical guarantees are also common in compression complexity literature. For example, Tables 1 and 2 of [8] compare compressed and uncompressed methods in terms of theoretical complexity and numerical memory consumption.
For compression performance, we compare against seven compression methods and sparse TD under the same TD-learning setting (Table 3 and Appendix H.13, Table 17). At an error tolerance of 10−2, our Krylov+POD context achieves significantly lower retained memory than existing compression methods across all eight tasks: 2.5–63.2× over truncated SVD, 3.5–53.0× over random projection, and 1.06–2.22× over POD. It also outperforms sparse TD in retained memory on seven of the eight tasks. POD–Galerkin remains 1.02–1.31× more compact, partly because our fixed attention executor additionally stores position tags and a query token.
In summary, our central contribution is a theoretical characterization of Transformer context complexity for in-context RL, together with an approximation analysis when the available context is insufficient. The compression experiments provide additional empirical validation of our theoretical insights.
Due to space limitations, the references are provided in the following comment.