acceptodds
Under review as a conference paper at ICLR 2027

Constructive Softmax Training for Certified In-Context Policy Improvement

Abstract

We establish a constructive connection between finite noisy training and policy improvement with frozen Transformer parameters. For finite discounted Markov decision processes sharing a state–action space and discount factor, we train a structured Transformer with standard softmax attention to reproduce an explicit temporal-difference teacher update. A two-stage projected curriculum of designed probes learns three update coefficients and the free attention scores from arbitrary initialization within prescribed parameter boxes. The resulting uniform operator-error bound controls repeated evaluation as target policies and value estimates change using the same deployment record. An outer greedy policy-improvement loop repeatedly calls the frozen evaluator, reusing a single trajectory collected by a fixed behavior policy. Under the stated coverage, mixing, and training conditions, the complete procedure returns an -optimal policy with a high-probability certificate bounding its suboptimality. At fixed confidence and structural and conditioning constants, sufficient budgets are labeled operator examples and unique deployment transitions, where bounds label noise. Training iterations, evaluation depth, and improvement rounds each grow logarithmically in . A two-task lower bound matches the deployment accuracy exponent when pretraining provides no information about the new task. Controlled experiments recover the teacher update from multiple initializations, show that training accuracy matters for repeated evaluation, and demonstrate policy improvement on unseen tasks. The RMS policy-uniform teacher Bellman residual decays approximately as .

Primary area:
reinforcement learning
Keywords:
in-context reinforcement learning, reinforcement learning theory, softmax Transformers, sample complexity, training convergence, policy improvement, confidence sets

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_2mx3OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper provides a highly-constrained SoftMax-Transformer setup that aims to learn a pre-constructed TD-operator from finite noisy supervision(via an attention matrix W to form a weighted combination of the classical Bellman residuals). Only three TD coefficients and n(n-1) attention scores are trained with the remaining architecture frozen. On deployment, the model parameters are frozen, policy evaluation and greedy policy improvement iteratively take place on an single trajectory collected by a fixed behavior policy. Policy performance bounds and a high-probability suboptimality certificate are established under the stated assumptions.

Critical strengths
  1. The paper is fluent with proper introduction and related work citations, and uses an additional table to help reader understand what are the incremental contributions. Formulas and algorithms are beautifully organized that greatly enhances readability.
  2. A clear theoretical flow from Theorem A.2 and Corollary A.3 eventually landed in an connection between the finite noisy operator training and the returned policy quality. A high-probability suboptimality guarantee is proved by explicitly analyzing four types or errors.
  3. The paper explicitly addressed the potential statistical dependence derived from the same reused deployment trajectory. Adaptive policy selection and repeated evaluation on single trajectory are enabled by a simultaneous concentration bound over deterministic target policies.
Critical weaknesses
  1. The paper provides an additional finite-sample and finite-step operator-error guarantee w.r.t. the work of Xie et al. (2026). However, those might heavily rely on the carefully designed identification probes, training curriculum and the highly-constrained Transformer architecture. Though the authors acknowledges those limitations, an additional baseline using ordinary MDP trajectories to jointly train TD coefficients and attention scores would be favorable for comparison.
  2. The theoretical guarantee that a single-reused-trajectory could support repeated policy evaluation is heavily dependent on the strong full state-action coverage and the geometric mixing assumptions. Though limitation acknowledged, certain state-action pairs might have zero stationary probability under a fixed behavior policy, causing the assumption to fail while very low stationary probabilities might require an impractically large sample budget.
Questions for authors
  1. To what extent do the probes and curriculum affect the training procedure? Will this method generalize to ordinary MDP trajectories or mixed-data joint training that matches the provided budget?
  2. Could the authors further investigate how a behavior policy could potentially satisfy Assumption 3.1 in practical deployment or whether the conditions should be relaxed?
  3. The authors acknowledge that the sufficient certificate bounds remain uninformative given the tested budgets, therefore, could the authors provide an example of a nontrivial certificate (C_J < 2B) that is computed without privileged true-MDP information?
2 comments

Thank you for the precise reading of the contribution relative to Xie et al. The revised PDF marks all additions in blue.

Q1 / W1 (role of probes; ordinary trajectories?). Singletons make the three coefficients identifiable independently of attention; two-record reward probes make each free score identifiable through r0crℓ(Axu)r_0c_r\ell(A_{xu}). The runs use a mixture of 3/43/4 ordinary examples and 1/41/4 probes, so probes need only be present at mass pmin⁡p_{\min}. On ordinary-trajectory joint training we have a proved obstruction rather than an untested gap: Proposition B.10 gives a noiseless label law with every probe at positive mass and teacher excitation, yet a nonoptimal stationary point of the joint loss. Hence the staged guarantee, with local joint GD as an optional refinement. We agree your baseline is the right empirical complement and will add it to the final version, reported as succeeding without a guarantee if that is what we find.

Q2 / W2 (coverage and mixing). Your concern is correct: the sufficient occupation threshold is conservative and grows as μ0\mu_0 shrinks, so small stationary probabilities do translate into large budgets for the advance guarantee.

We chose to remove the dependence rather than defend it. New Proposition A.13 shows the deployed certificate does not need Assumption 3.1: the finite-loop recursion holds on the residual event alone, with the realized teacher norm ρ^j=∥I−Wm+γTmπj∥∞\widehat\rho_j=\|I-W_m+\gamma T_m^{\pi_j}\|_\infty computed from the record, the deterministic operator bound and clipping, and nothing downstream reintroduces the occupation event. Assumption 3.1 now buys only an a priori rate. We measure ρ^j=0.756\widehat\rho_j=0.756 on the ring and 0.7650.765 on the random-kernel family, against certified 0.8950.895 and 0.9640.964 (Table 6). A pair with zero stationary probability is never observed, and no estimator can evaluate it; but the learner now detects this on its own record and reports 2B2B when a factor reaches one. We do not take the pessimistic-readout relaxation because the lower envelope is not computed inside the network; §3.1 now gives this as the rationale for the selection slack.

Q3 (non-trivial certificate without privileged information). Yes, for the trained model: the five frozen checkpoints give C8<2BC_8<2B in all 750 cells at m=1,048,576m=1{,}048{,}576 (mean 5.5955.595), and mean 3.0093.009 against 6.6676.667 at m=4,194,304m=4{,}194{,}304, realized gap 00 (Appendix C.1.7). Its inputs are the realized norm (record and policy table), the residual radius (record and known constants), and LG∥θ^−θ⋆∥2L_G\|\widehat\theta-\theta^\star\|_2, a deterministic function of the checkpoint. None uses PP or rr; the true model only reports the realized gap. Two caveats: the primary radius requires deterministic rewards (our banks have them), while the mixture radius, which needs only bounded rewards, crosses at 2,097,1522{,}097{,}152 (mean 5.8685.868); and the certificate is informative, not tight.

Xie et al. Table 1 now separates the premises, which makes the trade explicit: their softmax result is for prescribed parameters, with asymptotic loss optimality and an on-policy trajectory of the evaluated policy; ours trains by finite noisy GD and re-encodes one behavior trajectory for each new target policy, at the price of designed probes and a constrained architecture.

Thank you for the detailed response and revisions. Proposition A.13 and the new results in Appendix C.1.7 meaningfully address my concerns about coverage-dependent certification and the absence of a nontrivial certificate example. I appreciate your clarification of the distinction between the record-based certificate and the coverage-dependent a priori guarantee, as well as the clearer comparison with Xie et al.

Concern about training generality remains. Proposition B.10 explains why a global joint-GD guarantee does not follow from the stated excitation conditions alone, but does not directly replace the requested ordinary-trajectory joint-training comparison, which is still deferred to the final version. The training guarantee remains bounded to designed probes and the constrained architecture. The reported nontrivial certificates are also limited to checkpoints trained with noiseless labels and evaluated on small tabular tasks.

I appreciate these substantive improvements and will maintain my overall rating.

Reviewer_HyPyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper presents a constructive framework for in-context policy improvement using structured Transformers with softmax attention. The method trains an evaluator with a two-stage curriculum to approximate temporal-difference (TD) updates, then freezes it and applies repeated policy evaluation and greedy improvement using the same rollout trajectories. The paper provides theoretical guarantees on training error, sample complexity, and policy suboptimality, supported by experiments on small Markov decision processes (MDPs).

Critical strengths
  • Interesting theoretical question. The paper studies an important problem: how finite, noisy pretraining can enable reliable in-context policy improvement at deployment time without updating the model's parameters.

  • Detailed theoretical analysis. The work provides explicit bounds on training error, deployment-time sample complexity, and policy suboptimality. The analysis also accounts for repeated policy evaluation and the reuse of the same trajectories.

Critical weaknesses
  • Highly restrictive model construction. The proposed Transformer relies on a carefully hand-designed architecture with fixed attention masks, routing operations, and update structures. Only the attention scores and three TD coefficients are learned. This differs significantly from training a standard Transformer and limits how well the theoretical results apply to practical RL models.

  • Strong dependence on designed training data. The training scheme relies on specially constructed probes and supervision from a predefined TD teacher. These conditions are hard to satisfy with ordinary interaction trajectories. Moreover, since the teacher's update rule is already explicitly specified, the practical benefit of learning it rather than implementing it directly is unclear.

Questions for authors
  • Strong assumptions and unclear scalability. The theoretical guarantees require full state-action coverage, geometric mixing, and known problem-dependent constants. Although the paper reports favorable sample complexity with respect to the target accuracy, the hidden constants may depend heavily on the size of the state-action space, the discount factor, and the coverage conditions. It remains unclear whether these guarantees are meaningful for larger or more complex environments.

  • Limited experimental validation. The main experiments are conducted on a simple MDP with four states and two actions. The larger-scale experiments still use small tabular environments and simplified training setups. In addition, the learned evaluator largely matches the specified teacher and an empirical model-based planner, but shows no significant advantage over standard reinforcement learning methods. Experiments in more realistic environments would strengthen the contribution.

  • Limited practical evidence for policy certification. Although policy certification is a core contribution, Appendix C.1.1 acknowledges that the theoretical certificate bounds remain uninformative within the tested experimental budgets.

5 comments

Thank you. We would like to address any correctness concern directly: the listed weaknesses concern scope and assumptions rather than validity, so if there is a specific claim you believe incorrect, please name it and we will respond immediately. The revised PDF marks all additions in blue.

Weakness 1 (restrictive construction). Agreed on the substance, and §1 now says it: the architecture is dimensioned by nn and cs⋆=γc_s^\star=\gamma, so a pretraining family shares ∣S∣∣A∣|\mathcal S||\mathcal A| and the discount.

Simplifications of this kind are the norm in the theory of in-context RL, because no end-to-end result exists for training an unrestricted Transformer; every row of Table 1 makes one, in the architecture, the training premise, or both. Lin et al. use ReLU attention with clipping and assume a solution of the empirical likelihood objective rather than analyzing an optimizer. Wang et al. (2025) use linear attention with fixed masks and study expected pretraining updates. Wang et al. (2026) use linear attention in a sparse looped parameter space, with prompts that enumerate all states and use expected rather than sampled successors, and obtain loss optimality only as depth grows. Xie et al. keep softmax attention but with hand-constructed parameters in a sparse looped space, with loss optimality only as context length and then depth grow. Liang & Lai use one-layer linear attention and prove local convergence of population gradient flow from near the optimum. Lee et al. and Dong et al. do not analyze the architecture, and assume the model returns the exact target distribution or optimizer. Against these, our construction keeps standard softmax normalization and replaces an assumed optimum or population flow by finite, noisy projected gradient descent from an arbitrary start in the parameter box. The price is the one you identify: the routing is prescribed, and only the scores and three coefficients are trained.

Weakness 2a (designed data and teacher supervision). Supervision from a specified algorithm is the standard ICRL premise: Algorithm Distillation imitates learning histories, DPT trains on optimal actions, and Lin et al. analyze imitating an expert algorithm; our TD teacher plays that role. Three points on the probes:

What they are. A probe is a one- or two-record input whose teacher output isolates one parameter group (eq. (3)). A singleton record receives attention weight one, so the increment Gθ(D,Q)−QG_\theta(\mathcal D,Q)-Q reads off crc_r, cpc_p or csc_s; on a two-record probe, coordinate xx is r0crℓ(Axu)r_0c_r\ell(A_{xu}), so each score is read through a sigmoid. Like impulse inputs in system identification, they are algebraic, not trajectories.

Why we use them. Plain regression on a mixture can stall. Proposition B.10 gives a law that puts mass on every probe and has a positive-definite teacher Gram, yet its joint loss has a non-optimal interior stationary point. Separate group losses give a quadratic coefficient fit and a contracting score recursion, which lets finite noisy gradient descent succeed from any start in the box (Theorem A.2).

What they do not restrict. Probes are needed only in pretraining, with positive probability in an otherwise arbitrary stream (Assumption 3.3; 1/401/40 each in our runs). Deployment uses one ordinary behavior trajectory, and the training guarantee transfers to it because it holds uniformly over all inputs (Corollary A.3), with no distributional match to training. With attention prescribed (Appendix A.1.3), no probe is needed: the loss over ordinary examples is quadratic in cc, and the only condition is a full-rank coefficient Gram, as in linear TD analysis (Bhandari et al.); singletons are one sufficient law (Proposition B.5).

Weakness 2b (why learn a specified rule). This is the sharpest question, and we accept its premise: the teacher can be written down without data, and the paper does not propose a way to build a TD evaluator. Its object is the learning procedure. In-context learning theory takes the same stance: gradient descent on linear regression is known in closed form, and von Oswald et al. (2023), Ahn et al. (2023) and Zhang, Frei & Bartlett (2024) ask whether trained Transformers implement it. ICRL systems are likewise trained on algorithm-generated targets and deployed frozen, so two questions matter: does finite, noisy training recover the target inside softmax attention, and how does the remaining training error behave when the frozen model is reused for control? Implementing the teacher directly sidesteps both. We show that finitely many noisy projected gradient steps from any start in the box reach a uniform operator error eope_{\rm op} (Theorem A.2, Corollary A.3), and that eope_{\rm op} enters the certificate on the same footing as the statistical residual bmb_m, through (eop+bm)∑ℓ<Lρℓ(e_{\rm op}+b_m)\sum_{\ell<L}\rho^\ell, so a trained evaluator is certified like an exact one, at an explicit price. §1 now says so.

Q1 (hidden constants, scalability). §4 now brings these from the appendix into the main text. With n=∣S∣∣A∣n=|\mathcal S||\mathcal A| state–action pairs and balanced coverage μ0=1/n\mu_0=1/n, Corollary A.21 needs mm unique behavior transitions with

m≳n4H2(1−γ)4log⁡nδ+n2B2ϵ2(1−γ)8(∣S∣log⁡∣A∣+log⁡nδ),m\gtrsim\frac{n^4H^2}{(1-\gamma)^4}\log\frac{n}{\delta}+\frac{n^2B^2}{\epsilon^2(1-\gamma)^8}\Big(|\mathcal S|\log|\mathcal A|+\log\frac{n}{\delta}\Big),

where HH is the mixing constant and B=Rmax⁡/(1−γ)B=R_{\max}/(1-\gamma). One record serves all JJ improvements: the cost is mm, not JmJm. In the state and action spaces the terms are of order ∣S∣4∣A∣4|\mathcal S|^4|\mathcal A|^4 (occupation) and ∣S∣3∣A∣2log⁡∣A∣/ϵ2|\mathcal S|^3|\mathcal A|^2\log|\mathcal A|/\epsilon^2 (accuracy), the ∣S∣log⁡∣A∣|\mathcal S|\log|\mathcal A| from uniformity over data-dependent greedy policies. In both, the n2/(1−γ)2n^2/(1-\gamma)^2 from e2τe^{2\tau} is necessary for uniform sup-norm contraction (Proposition B.27), not a proof artifact. New Proposition A.13 keeps the first term out of the deployed certificate: it runs on the residual event alone, with the realized teacher norm (0.7560.756 against the certified 0.8950.895), not μ0\mu_0, HH or κ\kappa. The learner needs none of μ0\mu_0, HH or κ\kappa: they enter only the advance prediction of how large mm must be. At any record length the certificate is valid, and when the realized norm is not below 11 it reports the trivial bound 2B2B; coverage and mixing decide when it is informative, never whether it holds. The ϵ−2\epsilon^{-2} rate is unavoidable even with the exact teacher (Theorem A.22).

Q2 (experiments). "No advantage over standard RL" is not the claim under test: on a four-state tabular MDP an exact model-based planner should win, and the frozen evaluator matching it is the success criterion for an implementation-faithfulness experiment. The agreement is exact for a reason now proved in Lemma B.15: at teacher coefficients the evaluator's fixed point is the empirical-model value of the record, for every τ\tau (verified to 1.11×10−151.11\times10^{-15}). We concede the scale limitation (§7) and claim no large-scale results.

Q3 (evidence for certification). Please see the general response: the certificate is now non-vacuous for the trained checkpoints on the submitted instance, all 750 cells at m≈106m\approx10^6, mean C8=3.009C_8=3.009 against 2B=6.6672B=6.667 at the largest budget (Appendix C.1.7). On framing, the contribution is the construction and its validity — containment of a common Q⋆Q^\star while the evaluated policies change, and Dj+1≤Cj+1D_{j+1}\le C_{j+1} without assuming the critic is feasible. Whether CJC_J was small at a pilot budget was a question about one constant, which we have identified and reduced.

Dear Reviewer,

Thank you again for your review. Before the discussion closes, we wanted to make sure our response reached you. It addresses each of your points: the explicit sample requirement and its dependence on the state and action spaces (Q1), the role of the probes and of the TD teacher (W2), and a non-vacuous certificate for the trained checkpoints (Q3, Appendix C.1.7). All additions are marked in color in the revised PDF.

If these answers resolve your concerns, we would appreciate it if you would consider revisiting your assessment. If anything remains unclear, we would be glad to respond while the discussion is still open.

Best regards, The authors

Reviewer_YUD2OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper considers in-context reinforcement learning where a transformer-based policy is pre-trained on a set of (S, A, R, S') tuples on a wide-range of MDPs before deployed on new MDPs. The authors propose a method by pre-training a critic using a structured softmax-attention operator by learning the TD-coefficients and attention score. At deployment, the frozen critic is used to construct a reconstruct the policy greedily. For a prescribed curriculum, the authors prove that their method converges linearly to the optimal policy, up to an error that depends on depth of the transformer, and the coverage of the behaviour policy used to collect the data. The authors further conduct on a tabular MDP to support their theoretical results.

Critical strengths

None

Critical weaknesses

The proposed method is similar to TD-evaulaton combined with greedy improvement on an offline-dataset. At the moment, it's unclear what is the benefit and novelty of considering the in-context RL setting. Furthermore in comparison to prior in-context RL works, it's unclear wether the present theoretical results are better than prior works and if the assumptions are stronger/weaker.

Questions for authors
  • In Table 1, could you provide details of the assumptions required and precise guarantee? At the moment it's unclear what improvements does the proposed method attain compared to prior work.
  • Is it possible to provide the exact objective that is being optimized?
  • What is the intuition of the prescribed teacher and τ\tau (line 201)?
  • On line 257, since the dataset of comprised of many (unknown) tasks, what is the precise definition of V⋆V^\star?
  • On line 288 mentions that the "regression formulation is standard". Could you provide the regression explicitly? At the moment, it's construction is unclear.
  • For Assumption 3, could you clarify the meaning of "Every input in (3) is recognizable from the input alone"? It's unclear what (i) the inputs are and (ii) why the identification is probabilistic.
  • For the certificate, what happens when the intersection is empty? In particular, what is the consequence of marking the widths unavailable and why is the reward-bound fallback of 2B2B justified?
9 comments

Thank you for the detailed questions; we answer all seven inline, and the revised PDF (additions in blue) now states each answer where you looked for it. If a specific claim seems incorrect to you, please point to it and we will address it directly.

Main weakness. The deployment procedure is approximate policy iteration with TD evaluation on a reused offline trajectory. The submission attributed it to Bertsekas (2011) and Scherrer (2014) in §2 and at the propagation lemma (now B.22); §1 now says so directly, and §2 adds the offline-RL concentrability framing. The contribution is not the control loop but the evaluator inside it: a finite softmax Transformer produced by a specified finite optimizer from noisy labels, whose operator error is carried through to the true suboptimality of the returned policy, with a computable certificate. No prior ICRL analysis connects finite training error to a bound on the deployed policy.

Q1 (Table 1). Table 1 now separates architecture, training premise and deployment data for every row. The sets do not nest. Weaker than prior work: no ERM oracle, population limit, asymptotics or initialization condition. Stronger: designed probes (Assumption 3.3), an architecture dimensioned by nn, and uniform coverage with mixing (Assumption 3.1) — though the deployed certificate no longer needs the last (general response).

Q2 (the objective). Yes: it is Equation (4) in §3.1. Training runs projected gradient descent on it in two stages, both reusing the same NN examples; Appendix A.1 gives the full procedure and Theorem A.2 its guarantee.

Stage 1 (coefficients). The loss is half the squared Euclidean distance between the coefficient vector c=(cr,cp,cs)c=(c_r,c_p,c_s) and an empirical target c^\hat c, computed from the mean labels of the three singleton probes (Equation (11), Appendix A.1). Each step is projected onto the box [−C,C]3[-C,C]^3.

Stage 2 (attention scores). With the coefficients frozen at the stage-1 output cˉ\bar c, the loss sums, over every output coordinate xx and every two-record probe UuU_u (u<nu<n), the squared difference between the model's prediction cˉrℓ(Axu)\bar c_r\ell(A_{xu}) and that probe's mean label at coordinate xx divided by r0r_0, where ℓ\ell is the logistic sigmoid. Each step is projected onto ∣Axu∣≤MA|A_{xu}|\le M_A.

Averaging labels within each probe group first, rather than over all examples, weights the groups equally regardless of how often each appears.

Q3 (teacher and τ\tau). The teacher is the parameter setting at which block (2) computes exactly one TD update: c⋆=(1,−1,γ)c^\star=(1,-1,\gamma) makes the bracket Rt+1−Q(xt)+γQ(yt)R_{t+1}-Q(x_t)+\gamma Q(y_t), and A⋆A^\star puts a score gap τ\tau on the diagonal so that attention at query xx concentrates on records whose source address is xx. Larger τ\tau sharpens addressing: d⋆d_\star in (6) lower-bounds the attention mass on matching addresses, κ=d⋆−(1+γ)/2\kappa=d_\star-(1+\gamma)/2 is the contraction margin, and ρ=1−κ\rho=1-\kappa the rate. At finite τ\tau the update is a smoothed Jacobi step. Lemma B.15 adds that τ\tau does not change the converged values, only the rate.

Q4 (V⋆V^\star). V⋆V^\star is the optimal value of the single deployment MDP M⋆M^\star; §3 now says so where it is defined. Pretraining examples are algebraic operator inputs with teacher labels, not tasks, and carry no information about M⋆M^\star. Theorem A.22 is the formal counterpart: task-independent pretraining cannot reduce the deployment requirement.

Q5 (the regression). Equation (7) is the regression model: Yi=Gθ⋆(Ui)+ζiY_i=G_{\theta^\star}(U_i)+\zeta_i, E[ζi∣Ui]=0\mathbb E[\zeta_i\mid U_i]=0, ∥ζi∥2≤σ\|\zeta_i\|_2\le\sigma, i.i.d. across ii. Its regression function is the teacher's raw update, realized exactly by the model class, and the losses (4) are its least-squares objectives on the probe groups. "Standard" referred only to the noise model; §3.2 now says this.

Q6 (Assumption 3.3). The inputs are the four probe families in (3): singletons UR,UP,USU_R,U_P,U_S fixing the coefficients, and two-record probes UuU_u fixing the scores. "Recognizable" means group membership is a deterministic function of UiU_i, read before its label, so the losses group examples without labels. It is probabilistic only because probes arrive in an i.i.d. mixture with mass at least pmin⁡p_{\min}; §3.2 now states this.

Q7 (empty intersection, 2B2B). On the confidence event no intersection is empty (proved). An empty one therefore certifies that the event failed, voiding the accumulated certificates from that round; only 2B2B is reported. That fallback needs no event: ∥V⋆−Vπ∥∞≤2Rmax⁡/(1−γ)=2B\|V^\star-V^\pi\|_\infty\le2R_{\max}/(1-\gamma)=2B for every policy. §3.1 now states this in the main text.

Thank you for your reply. I still have several concerns.

For table 1, while it is helpful to include information about the deployment data, it is still unclear how the present method compares to prior work. For example, how does the policy improvement guarantee of Theorem 4.1 compare to [1, Proposition 4.2]

To clarify, I am asking for the objective that ICRL is maximizing.

Furthermore, it's still not clear what the probes are for. Could you give some intuition on how they are used for this method and what issues may arise if Assn. 3.3 is not satisfied?

[1] Dong, Juncheng, et al. "In-context reinforcement learning from suboptimal historical data." arXiv preprint arXiv:2601.20116 (2026).

Thank you for the follow-up.

1. Theorem 4.1 versus Dong et al., Proposition 4.2. Their Proposition 4.2 concerns πτ⋆\pi^\star_\tau, the exact maximizer of the KL-regularized advantage objective (their (3)) given the task τ\tau, and lower-bounds its task-averaged improvement over the behavior policy:

Eτ[Gτ(πτ⋆)−Gτ(πτb)]≥η1−γEτ[CτD]−2γ(1−γ)2Eτ[CτACτD/2].\mathbb E_\tau\big[G_\tau(\pi^\star_\tau)-G_\tau(\pi^b_\tau)\big]\ge\frac{\eta}{1-\gamma}\mathbb E_\tau[C^D_\tau]-\frac{2\gamma}{(1-\gamma)^2}\mathbb E_\tau\Big[C^A_\tau\sqrt{C^D_\tau/2}\Big].

Theorem 4.1 concerns the policy πJ\pi_J returned by the trained, frozen network on one deployment MDP, and upper-bounds its gap to the optimal policy: with probability at least 1−δ1-\delta,

∥V⋆−VπJ∥∞≤CJ≤2BγJ+2(1−γ)2[BρL+eop+bmκ].\Vert V^\star-V^{\pi_J}\Vert_\infty\le C_J\le 2B\gamma^J+\frac{2}{(1-\gamma)^2}\Big[B\rho^L+\frac{e_{\rm op}+b_m}{\kappa}\Big].

Dong et al., Prop. 4.2Theorem 4.1
Policy boundedExact population optimizer, given the taskReturned by the trained Transformer from its context
QuantityImprovement over behavior, averaged over tasksGap to the optimal policy, for each task and every start state
SignRight side nonnegative only when advantages are smallAlways an upper bound; at most ϵ\epsilon under explicit budgets
TrainingNot in the boundNN noisy labels and finitely many gradient steps, any start
Deployment dataOnline or offline context; its size is not in the boundmm transitions from one trajectory, reused JJ times
ComputableNoCJC_J is computed from the record
ArchitectureNot analyzed; exact optimizer assumedSoftmax attention, trained; finite MDPs sharing nn and γ\gamma

What each row means:

  • Policy bounded. Their bound is for πτ⋆\pi^\star_\tau, which is given the task and solves their objective (3) exactly. The trained Transformer only approximates it, and the bound does not cover that approximation. Ours is for the policy the trained network actually returns.
  • Quantity. Theirs compares with the behavior policy, averaged over the task distribution. Ours compares with the optimal policy, on each task separately and uniformly over start states.
  • Sign. Their right side is a positive term minus a positive term, so it guarantees improvement only when the advantage term is small; otherwise it is negative and says nothing. Ours is always a valid upper bound, and Theorem 4.1 gives budgets that make it at most any ϵ>0\epsilon>0.
  • Training. Their bound does not depend on the pretraining sample or the optimizer. Ours includes the training error eope_{\rm op}, controlled by NN noisy labels and finitely many projected gradient steps from any initialization (Theorem A.2).
  • Deployment data. Their bound does not depend on how many transitions the context holds. Ours depends on the mm deployment transitions through the residual radius bm∝m−1/2b_m\propto m^{-1/2}, and one trajectory serves all JJ rounds, so the cost is mm, not JmJm.
  • Computable. Their CτDC^D_\tau and CτAC^A_\tau depend on πτ⋆\pi^\star_\tau and on the true advantages of the unknown task, so the right side cannot be evaluated at deployment. CJC_J is a number the learner computes from what it has: the record, the frozen checkpoint (through eope_{\rm op}), and known constants such as δ\delta, Rmax⁡R_{\max} and γ\gamma. After deployment one therefore knows, with probability at least 1−δ1-\delta, how far the returned policy can be from optimal, without knowing the MDP.
  • Architecture. Their bound is architecture-agnostic because it assumes the exact optimizer is reached, so it does not say whether any particular network reaches it. Ours is proved for softmax attention, the mechanism used in practice, and covers how training reaches the target and what the trained model then guarantees; the price is a class of finite MDPs that share nn and γ\gamma.

Theorem 4.1 also implies a statement of their type: for any start distribution, G(πJ)−G(πb)≥[G(πopt)−G(πb)]−CJG(\pi_J)-G(\pi^b)\ge[G(\pi^{\rm opt})-G(\pi^b)]-C_J, so improvement over the behavior policy is certified whenever its gap exceeds the computed CJC_J. The results are complementary: theirs explains why advantage weighting helps at the population level; ours shows what a trained softmax network actually delivers on a new task, at finite sample sizes, with a bound the learner can check.

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

The paper gives a constructive path from finite, noisy operator supervision to policy improvement with frozen parameters. A structured softmax Transformer learns three temporal-difference coefficients and a gauge-fixed attention-score matrix using a two-stage curriculum of singleton and two-record probes. Uniform operator accuracy is combined with concentration for one covered, geometrically mixing behavior trajectory, teacher contraction, and approximate policy iteration. The resulting procedure reuses the trajectory across adaptively selected target policies and returns a policy together with a high-probability suboptimality certificate. At fixed structural and conditioning constants, the sufficient training and deployment sample budgets scale as O(1+σ2ϵ−2)O(1+\sigma^2\epsilon^{-2}) and O(ϵ−2)O(\epsilon^{-2}), respectively. Experiments illustrate operator recovery, repeated evaluation, and transfer across small tabular tasks.

The contribution is a rigorous constructive composition under substantial architectural and supervision restrictions. I did not identify a blocking error in the central proof chain.

Critical strengths
  1. Clear accounting of resources. The paper separately counts training examples, optimization steps, deployment transitions, evaluation loops, and improvement rounds, and gives explicit sufficient budgets for each (Theorem 4.1, Appendix A.4). The authors are careful to present these as sufficient rather than necessary, and only the deployment rate is paired with a matching lower bound. I found this transparency helpful.

  2. Reuse of a single trajectory is addressed directly. The same deployment data are used both to choose each new policy and to evaluate it. Rather than collecting fresh data each round, the authors construct one confidence event that holds simultaneously for all deterministic policies, so policies selected from the data are covered as well (Section 5; Lemmas B.12–B.15). As presented, this is a sensible way to handle the dependence, and the proof outline makes the idea easy to follow.

  3. Readable structure. The main theorem, Algorithm 1, and the proof outline in Section 5 are clearly written, and the overall chain (training accuracy → repeated evaluation → policy improvement → certificate) is easy to follow at a high level.

  4. An informative depth experiment. Appendix C.1.2 shows that more evaluation depth helps an accurately trained checkpoint but hurts an early one. This is a simple, clear illustration of why training accuracy matters when the learned update is applied repeatedly.

Critical weaknesses
  1. The learning problem is heavily simplified. Only three TD coefficients and the attention-score matrix are trained; routing, masks, and the rest of the architecture are fixed by hand, and training uses hand-designed "probe" inputs rather than ordinary trajectories. Under this setup, coefficient fitting is a small quadratic problem and attention fitting reduces to separate scalar fits. I suspect the global convergence result depends on this simplification, so it seems to say little about how ordinary Transformers are trained. The authors disclose these restrictions, but it would help to state explicitly which insights are expected to survive outside this setup.

  2. The certificate is not informative in any reported experiment. The authors state (Appendix C.1.1, line 2406) that "at the tested budgets, the sufficient certificate bounds remain uninformative." Since certified improvement is part of the title and main claim, it would strengthen the paper to show at least one setting where the certificate gives a non-trivial bound, or to explain roughly how large the budgets would need to be.

  3. Noisy training is not carried through to the control experiments. As I read Section 6 and Appendix C.1, the policy-improvement experiments use checkpoints trained on clean labels, while the noisy-label experiments report only operator error. Running the existing noisy checkpoints through the same deployment experiments would better support the end-to-end claim.

  4. The study is confined to small tabular problems. All experiments use 8 to 32 state–action pairs, and the method requires enumerating state–action pairs, covering all of them, and fixing the architecture by hand. The authors do not claim to address large-scale models, but the introduction motivates the work with in-context RL as practiced today, and I struggle to see the connection to practical post-training. A short discussion of which components could extend beyond small tabular MDPs would help readers judge the scope of the contribution.

Questions for authors
  1. Is there any parameter or budget regime, even a hypothetical one, in which the certificate CJC_J is smaller than the trivial bound 2B2B? If this is impractical to compute, which part of the bound is the main obstacle?

  2. In Figure 2, the learned evaluator, the teacher, and the empirical-model planner reach the same policy gaps to displayed precision. Does the converged teacher evaluator in fact compute the same values as empirical planning? If so, how should readers interpret the tradeoff in τ\tau described after Theorem 4.1: is it a real statistical cost, or a feature of the current bound?

  3. What happens when the noisy-label checkpoints from Appendix C.1.4 are used in the policy-improvement experiments? Does the policy gap degrade as the analysis predicts?

  4. How do the authors expect this method to scale to larger models and realistic problems, such as LLM-scale in-context RL? The model, the number of probes, and the sample bounds all grow with the number of state–action pairs nn, and in T5 the attention error already rises sharply from n=8n=8 to n=32n=32. Which parts of the construction would still apply once states can no longer be enumerated?

3 comments

Thank you — particularly for reading the proof chain closely enough to report no blocking error. All four questions turned out to be answerable on the existing material, and all four answers are now in the revised PDF (in blue).

Q1 / Weakness 2 (a regime with CJ<2BC_J<2B, and the obstacle). Please see the general response and new Appendix C.1.7: the certificate is non-vacuous for the trained checkpoints on the submitted ring tasks at m≈106m\approx10^6. The obstacle was the deployment residual radius, not training error or the contraction factor: at m=1024m=1024 the operator radius is 1.15×10−31.15\times10^{-3} against a residual radius of 130.79130.79.

Q2 (does the converged teacher compute empirical planning; is the τ\tau trade-off real?). Yes, by an identity, now Lemma B.15. At teacher coefficients, grouping the update by source address gives F(Q)(x)−Q(x)=∑uWxu[r^(u)−Q(u)+γ(P^πQ)(u)]F(Q)(x)-Q(x)=\sum_u W_{xu}[\widehat r(u)-Q(u)+\gamma(\widehat P^{\pi}Q)(u)], so the empirical-model value Q^=(I−γP^π)−1r^\widehat Q=(I-\gamma\widehat P^{\pi})^{-1}\widehat r is a fixed point for every τ\tau and every weight matrix; contraction gives uniqueness, and depth LL gives agreement up to Bρ^ LB\widehat\rho^{\,L}, about 10−1510^{-15} at L=128L=128. A direct check on the T2 records gives a maximum fixed-point residual of 1.11×10−151.11\times10^{-15}.

The trade-off splits three ways, as §4 now states:

  • τ\tau does not affect the converged values.
  • eτ=Ω(n/(1−γ))e^{\tau}=\Omega(n/(1-\gamma)) is a real cost of uniform sup-norm contraction; Proposition B.27 proves it necessary.
  • Its appearance in the residual radius is a feature of that bound; the radii of Appendix B.5.5 reduce it, and the realized norm (Proposition A.13) avoids the uniform requirement on the record at hand.

Q3 / Weakness 3 (noisy checkpoints through control). You were right that C.1.4 stopped at operator error. Appendix C.1.4 now carries the 30 noisy checkpoints (σ=0.01\sigma=0.01) through the unchanged T2 deployment on the stored records: 81,000 paired cells across both families, no retraining. Every final policy matches its paired clean control, so the realized gaps match (mean D8=0.001473D_8=0.001473 at m=1024m=1024 for every NN). The certified side moves as predicted (Table 4): the operator radius falls from 38.1338.13 to 5.2655.265 as NN goes from 256 to 8192, and EjE_j from 705.8705.8 to 568.5568.5, while C8C_8 stays at 2B2B because the residual fills the box at m=1024m=1024. EjE_j also exceeds the measured evaluation error (0.0470.047) by four orders, which we now report. One consequence we state plainly: these noisy radii exceed the level at which any context length could make their certificate informative, so the T6 certificates are for the clean checkpoints.

Q4 / Weakness 4 (scale; attention error from n=8n=8 to 32). In T5 the learned policies agree with the teacher on every evaluated state at all three sizes. The rising ∥A−A⋆∥F\|A-A^\star\|_F reflects a fixed budget of 262,144 steps while p=n(n−1)+3p=n(n-1)+3 grows from 59 to 995; Appendix C.1.6 now labels T5 a descriptive comparison rather than a scaling study. On what survives beyond enumeration, §7 now says: the control layer needs only an evaluator with a uniform operator bound and a valid Lipschitz factor, so extending beyond tabular addresses reduces to building such evaluators, while the tabular addressing and the union term ∣S∣log⁡∣A∣|\mathcal S|\log|\mathcal A| are tied to enumeration. We do not claim a path to LLM-scale ICRL.

Weakness 1. We agree; §7 now states which parts are architecture-independent (the separation of pretraining from task identification, and the reuse analysis) and which are not (the training guarantee).

Dear Reviewer,

Thank you for your positive and careful review. We have posted a response and a revised PDF (additions marked in color) that address the points you raised, including the certificate for the trained model (Appendix C.1.7) and the noisy-checkpoint deployment results (Appendix C.1.4).

We would be grateful to know whether these address your remaining questions, and we are happy to clarify anything further before the discussion closes.

Best regards, The authors

Dear Reviewer BLNn,

Thank you again for your careful and constructive review. As the discussion period closes today, we wanted to check whether our response addressed your main points:

  • the scope of the learned problem and which insights carry beyond the structured setting;
  • the informativeness of the certificate, including which term dominates the bound;
  • propagating noisy-label checkpoints through the policy-improvement experiments [see Section/Appendix X].

If anything remains unclear, we would be glad to clarify before the deadline. We would also be grateful if your final assessment could reflect any points you consider resolved.

Comments on the paper

2 comments

Common response

We thank all four reviewers. We have uploaded a revised PDF in which every addition is marked in blue; theorem numbers below refer to it. Three reviewers (BLNn W2/Q1, HyPy Q3, 2mx3 Q3) ask whether the certificate is ever non-trivial and which term is the obstacle. We answer that here; reviewer-specific replies follow in each thread.

A non-vacuous certificate for the trained model (new Appendix C.1.7). The certificate CJC_J is the procedure's computable upper bound on the true suboptimality ∥V⋆−VπJ∥∞\|V^\star-V^{\pi_J}\|_\infty of the returned policy, valid with probability at least 1−δ1-\delta (δ=0.1\delta=0.1) and computed from the deployment record without the true model. Every policy satisfies the trivial bound 2B=6.6672B=6.667, so the certificate is informative only below it. We deployed the five frozen C.1 curriculum checkpoints — the paper's own weights, with no retraining — on the 50 submitted ring tasks with newly simulated trajectories, three per task: 750 checkpoint–record cells, at J=8J=8 and L=128L=128 as in T2. The certificate does not affect the returned policies; what is new are its inputs. Each row declares one residual radius in advance, with its own confidence allocation; we do not pick the best row after the fact.

residual radius\matrixfirst prefix with all\cr750 cells C8<2B\matrix{\text{first prefix with all}\cr\text{750 cells }C_8<2B}\matrixmean\crC8\matrix{\text{mean}\cr C_8}\matrixmax\crC8\matrix{\text{max}\cr C_8}
transition empirical Bernstein (Lemma B.21)1,048,5761{,}048{,}5765.5955.5955.7175.717
grid-regularized mixture (Cor. B.20)2,097,1522{,}097{,}1525.8685.8685.9665.966
fixed-regularizer self-normalized (Lemma B.19)4,194,3044{,}194{,}3044.8504.8504.9434.943
submitted radius (Lemma B.16)beyond 4,194,3044{,}194{,}304——

At m=4,194,304m=4{,}194{,}304 the first radius gives mean C8=3.009C_8=3.009, with observed policy gap 00. The first row requires deterministic rewards, which our task banks have; the other two need only bounded rewards.

Why it was vacuous. The certificate propagates an evaluation radius E=BρL+(eop+bm)∑ℓ<LρℓE=B\rho^{L}+(e_{\rm op}+b_m)\sum_{\ell<L}\rho^{\ell}, made of a depth term, the training error eope_{\rm op} and the finite-context residual bmb_m; it falls below 2B2B roughly once E<B(1−γ)2=0.3E<B(1-\gamma)^2=0.3. At m=1024m=1024 the depth term is negligible at L=128L=128 and eop=LG∥θ^−θ⋆∥2e_{\rm op}=L_G\|\widehat\theta-\theta^\star\|_2 averages 1.15×10−31.15\times10^{-3}, but the submitted residual radius is bm=130.79b_m=130.79, 19.619.6 times the range 2B2B, so E≈536E\approx536. That bound charges every transition the largest attention weight eτ≈148e^{\tau}\approx148 and divides by mm, whereas only visits to the query address carry that weight and the realized normalizer is about 19m19m. New Appendix B.5.5 gives radii that use the realized weights (self-normalized bounds) or the empirical successor frequencies (empirical Bernstein), both computed from the record. The realized teacher norm — 0.7560.756 on the ring against the certified ρ=0.895\rho=0.895 — also cuts the factor 1/(1−ρ)1/(1-\rho) multiplying the residual from 9.59.5 to 4.14.1. Together these make the certificate cross.

Coverage and mixing leave the deployed certificate. New Proposition A.13 shows that the deployed certificate does not need the occupation threshold behind Assumption 3.1: the finite-loop recursion holds on the residual event alone, using the teacher norm the learner computes from its record, the deterministic operator bound and clipping. Assumption 3.1 now buys only an a priori contraction rate; the deployed certificate checks its own factor and reports 2B2B if any factor reaches one (no occurrences). This answers 2mx3's Q2 and removes μ0\mu_0, HH and κ\kappa from the constants in HyPy's Q1.

Scope. The crossings are on the ring family. Confidence is per task–record for the declared radius, not joint across cells or radii. Arithmetic is ordinary floating point. And the certificate is informative, not tight: 3.0093.009 against 6.6676.667 while the realized gap is 00.

Changes in the revised PDF (all in blue):

  1. Appendix C.1.7 (T6): the decomposition, realized norms for both families, the crossing tables, scope.
  2. Proposition A.13: the certificate on the residual event with the realized norm; Theorem A.14 updated.
  3. Appendix B.5.5: four residual radii with proofs, and a table of their conditions.
  4. Table 1: a deployment-data column, with the premises of each work separated.
  5. §4: explicit constants (Corollary A.21), the necessity result (Proposition B.27), the occupation threshold and the deployed certificate.
  6. Appendix C.1.4: noisy-label checkpoints through deployment (Table 4). Lemma B.15: the teacher's fixed point is the empirical-model value.
  7. ZjZ_j reported as a diagnostic: 540 ring and 335 random-kernel decreases of aja_j gave zero strict improvements.
  8. §1 scope and framing, §2 concentrability, §3 clarifications, §7 scope and future work.
Reviewer_HyPyOpenReview ↗

Response

Dear Authors,

Thank you for your rebuttal. I have gone through the further explanation. I think the theory is intersesting and the rebuttal helps clarify the main points. But the method still relies a lot on hand-designed architecture and training setup, so not clear how well it generalizes. Experiments are also limited to small tabular tasks. Therefore, I decided to keep my score.

Best regards,

Reviewer

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.