acceptodds
Under review as a conference paper at ICLR 2027

When Does Curvature Help Offline Value Selection?

Abstract

Repeated Bellman updates fit the same finite dataset more closely, but need not improve the true value estimate. We study risk calibration and estimator selection with fixed linear features. Joint reward, transition, and Gram-matrix uncertainty changes both the variance and the mean of a finite iterate; omitting the mean correction can miss an order- risk term. We derive a same-data risk score for smooth value estimators and extend its guarantees to ordinary independent and identically distributed (iid) transitions through local conditioning and an explicit fallback on ill-conditioned datasets. For one-state problems, a characterization for any sample size and finite candidate bank identifies when the correction's downward shift improves selection and when it hurts. We also show why an endpoint-scale oracle bound alone cannot certify improvement over convergence. Matched experiments evaluate 19,800 independent datasets, including 7,200 iid datasets with overlapping features, using matched ridge, normalized-difference tournaments, paired intervals, and independent pilot comparators for each candidate family. Curvature gives modest, statistically resolved gains within both checkpoints and ridge, but independent pilots reveal much larger remaining selection gaps. Severe small-sample miscalibration and the cost of covariance estimation remain important limits. We report guards that reject the population and conservative confidence checks that certify no fits; neither calibration nor useful selection follows from an observed inverse margin alone.

Primary area:
reinforcement learning
Keywords:
offline reinforcement learning, Bellman iteration, risk estimation, estimator selection, finite-sample analysis

Reviews

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

This paper studies fixed-policy evaluation with fixed linear features. Starting from θ0=0\theta_0=0, checkpoint KK performs KK exact least-squares fitted Bellman updates on the same dataset; K=∞K=\infty corresponds to the LSTD solution. The paper asks which checkpoint to retain when only that dataset is available.

On the theoretical side, the paper expands the iterates jointly in the reward, transition, and Gram-matrix errors. At order 1/n1/n, the risk of a finite checkpoint contains a signed term, 2dK⊤M EqK2d_K^\top M\,\mathbb{E}q_K, which couples the checkpoint's population bias with the estimator's second-order mean shift. Variance-only calculations miss this term. The paper illustrates it with two examples and shows how treating the Gram matrix as fixed can introduce spurious noise.

The authors then propose a score that compares each candidate with the LSTD endpoint. The score includes a covariance correction and an endpoint-curvature correction, 2(fK−h)⊤Mβ^2(f_K-h)^\top M\hat\beta. Because the candidate's own curvature cancels, the same score applies to any smooth candidate family, including ridge. The theoretical results are:

  • A calibration error of order n−3/2n^{-3/2} for a fixed candidate (Theorem 18);
  • The impossibility of exactly unbiased risk estimation from finitely many Bernoulli transitions (Theorem 17);
  • An oracle inequality with an additive term of order 1/n1/n (Theorem 2), along with a local version for ordinary iid transitions that uses condition-number gating and a fallback to zero (Theorem 4, Proposition 5);
  • A proof that this additive term is at least eight times the endpoint risk (Proposition 7);
  • For the single-state model, an exact characterization of when curvature improves selection for any nn and any finite candidate library (Theorem 8), an explicit example in which curvature helps (Proposition 6), and a proof that any advantage eventually vanishes (Corollary 9).

The experiments use four synthetic suites.

Critical strengths
  1. Exact results and careful claims. The paper gives exact rational results that readers can verify, and it demonstrates its own limitations:

    • Proposition 7 shows that the oracle bound cannot guarantee an improvement over LSTD.
    • Section 5.4 reports that, at n=8n=8, the score bias is about twelve times the true risk.
    • Appendix G reports that the conservative certificate fails on every dataset.
  2. The cancellation identity and a matched experimental protocol. Eq. (71) shows that the score needs only the endpoint's curvature, so the same correction applies to ridge and to union candidate libraries. The authors use this property to make the comparisons fair:

    • The same data budget for all methods;
    • The same score across candidate families;
    • Paired confidence intervals;
    • Fixed baselines tuned on independent pilot data, which distinguish a weak candidate family from a weak selector.
Critical weaknesses
  1. The experiments show that curvature helps very little, and its benefit cannot be predicted in advance.

    • Curvature lowers the risk of the selected candidate by only 0.9 to 2.2 points, and the selector still trails a fixed choice tuned on pilot data by about 13 to 25 points.
    • The frozen-Gram ablation outperforms the full score on the weighted (.51 vs. .57), sampling (.53 vs. .59), and iid (.55 vs. .57) suites, and ties it on the tabular suite. Yet joint Gram uncertainty is exactly what Section 3.3 and the contributions paragraph emphasize.
    • With the same score, ridge outperforms checkpoint selection on all four suites.
    • Proposition 11 relies on a construction with zero true variance, so it does not establish how often this effect matters.

    Theorem 8 shows that, in the scalar model with a positive reward, the correction always favors smaller predictions and therefore induces more shrinkage toward the zero initialization. The observed gains could thus reflect either better calibration or extra shrinkage in weak-signal settings. Because the paper reports neither the selected KK and λ\lambda nor any strong-signal suite, it cannot distinguish between these explanations.

    This matters because checkpoint selection for exact linear FQE has limited practical appeal on its own: both the endpoint and ridge are cheap to compute, and the paper claims no computational savings. The empirical case therefore rests entirely on a small effect that may be an artifact of the chosen experimental settings.

  2. Beyond the scalar model, the theory does not answer the paper's own question.

    • The selection guarantees are too loose. The additive terms in Theorems 2 and 4 are at least eight times the endpoint risk, so neither theorem can establish a gain over LSTD.
    • The calibration constants break down at the sample sizes studied. In Section 5.4, the score bias is 0.105, whereas the risk is only 0.0085.
    • Theorem 8 depends on the unknown true value vv. It sums the identity (a−v)2−(b−v)2=(a−b)(a+b−2v)(a-v)^2-(b-v)^2=(a-b)(a+b-2v) over the counts, so it identifies when curvature helps only if vv is known.
    • The sample sizes required by Corollary 9 are astronomical. For the paper's own example (γ=4/5\gamma=4/5, p=1/2p=1/2, candidate library {2,∞}\{2,\infty\}), its sufficient condition requires n>1.6×105n > 1.6\times10^{5}. For the experimental candidate library (Kmax⁡=128K_{\max}=128, γ=0.95\gamma=0.95), the same formula gives about 109910^{99} at p=0.9p=0.9 and about 1016410^{164} at p=0.5p=0.5.
    • The multidimensional case offers only diagnostics. Beyond the scalar model, the paper provides only a test that can rule out a switch in the selected candidate.

    The tools are all standard: the second-order delta method, SURE-style corrections, bounded differences, and constrained risk lower bounds. The scope is also narrow: fixed features, d≤8d\le 8, 24 states, realizable rewards, zero initialization, and iid transitions.

Questions for authors
  1. Please report the distributions of the selected KK and λ\lambda under the full score, the score without curvature, and the frozen-Gram score. Please also add a strong-signal suite in which the endpoint is nearly optimal, as well as a suite with misspecified features. If the curvature gains persist in these settings, that would support the calibration explanation; if they reverse, that would indicate they come from extra shrinkage.
  2. Did LSTD-Tournament, ridge with a holdout set, and the fixed eight-update method use the same gating and fallback to zero as the score-based methods? If not, how were the 891 datasets that triggered the fallback counted in each method's normalized risk? How would the iid results change if the thresholds were chosen without population margins, for example from independent pilot data?
  3. Why does the frozen-Gram score still win on the grouped suites when the population covariance is used?
5 comments
AuthorsOpenReview ↗

Response to Reviewer qiCE (1/3): calibration or shrinkage? (W1, Q1)

Thank you for a detailed and accurate review. Your shrinkage reading is correct. The curvature gain comes from data-adaptive shrinkage of the endpoint toward zero rather than from better calibration of individual candidates, and the revised abstract, Sec. 1 and Sec. 5.3 now say so.

What the curvature term does. Completing the square shows that the full score ranks candidates by their squared MM-distance to the target t=h^−β^t=\hat h-\hat\beta, plus the covariance penalty, and Sec. 4 now states this. In one state with known reward, β^=V∞/h^\hat\beta=V_\infty/\hat h, where V∞V_\infty is the endpoint's estimated variance, so t=h^(1−V∞/h^2)t=\hat h(1-V_\infty/\hat h^2) is a variance-adaptive shrinkage of the endpoint toward zero, and Thm 8 says exactly when this shrinkage helps (Sec. 4.3). In any dimension, when the full and no-curvature scores select different predictions (a switch), the full score's choice ff always has the smaller value of f⊤Mβ^f^\top M\hat\beta (Appendix U.1).

Controls (Appendix U.2, Table 5). Each control except the last replaces β^\hat\beta in the curvature term 2(fK−h^)⊤Mβ^2(f_K-\hat h)^\top M\hat\beta by another vector, which we call a tilt, and keeps everything else. The table reports each score minus the no-curvature score.

ScoreTabularWeightedSamplingiid
β^\hat\beta (full score)−2.20 [−2.67, −1.73]−0.89 [−1.20, −0.58]−1.74 [−2.17, −1.31]−1.16 [−1.41, −0.91]
pilot mean of β^\hat\beta0.25 [−0.05, 0.54]0.55 [0.32, 0.77]0.30 [0.08, 0.52]0.22 [0.05, 0.38]
random direction0.06 [−0.27, 0.40]0.14 [−0.15, 0.43]−0.10 [−0.47, 0.27]0.26 [0.04, 0.48]
−β^-\hat\beta2.90 [2.53, 3.27]1.60 [1.25, 1.96]1.69 [1.32, 2.06]1.85 [1.55, 2.16]
3β^3\hat\beta−3.49 [−4.41, −2.57]−1.48 [−2.18, −0.79]−3.13 [−3.85, −2.41]−2.07 [−2.50, −1.64]
no curvature, penalty ×1.5−3.94 [−4.75, −3.13]−3.57 [−4.48, −2.65]−4.25 [−5.21, −3.29]−1.03 [−1.61, −0.46]

The average of β^\hat\beta over independent pilot datasets keeps the average tilt but not its variation, and it removes the gain. A random direction of the same norm also removes it, while flipping the sign hurts, so the gain needs a data-dependent tilt with the sign of β^\hat\beta. Larger multiples of β^\hat\beta help more, and 3β^3\hat\beta, our largest, is the best multiple in all four suites. A 1.5-fold penalty without curvature matches the full score in iid and beats it in the other three suites. We chose these multipliers on the test data and do not recommend them. Both are worse than no curvature in the higher-signal iid suite of part 2/3 (Table 8).

The shrinkage is toward zero, not toward the starting point (Appendix U.5, Table 9). With θ0=0\theta_0=0, as in the paper, the two coincide. To separate them, we reran the iid suite on the same datasets with checkpoints started at 2θ⋆2\theta^\star or θ⋆/2\theta^\star/2, where θ⋆\theta^\star is the true parameter, which no selector sees. If the gain were shrinkage toward the start, it would vanish from 2θ⋆2\theta^\star, but full minus no curvature is −1.70 [−1.92, −1.48] from 2θ⋆2\theta^\star and −1.65 [−1.90, −1.41] from θ⋆/2\theta^\star/2. From 2θ⋆2\theta^\star, curvature switches no longer favor earlier checkpoints (303 later, 250 earlier), and the full score wins on 82% of them. The 1.5-fold penalty, which shrinks toward the start, is worse than the full score by 2.12 [1.49, 2.76]. This matches the algebra, because the target h^−β^\hat h-\hat\beta does not involve θ0\theta_0.

In theory, the correction still removes the leading-order bias of a fixed candidate's score (Thm 18).

AuthorsOpenReview ↗

Response to Reviewer qiCE (2/3): selected K and λ, new suites and the frozen Gram (W1, Q1, Q3)

Q1: selected KK and λ\lambda (Appendix U.1, Tables 3–4). On gate-passing datasets, the full score's most common choices are K=0K=0, the zero prediction (31–38% of datasets), and λ=1\lambda=1, the largest ridge value (28–38%), against 30–34% and 26–36% for the no-curvature score. Most of the full score's checkpoint choices have K≤4K\le4. Curvature changes the selected checkpoint on 12–23% of datasets, and the full score wins on 55–63% of these switches. The frozen-Gram and full scores coincide in the tabular suite. In the other suites, the frozen-Gram score picks an earlier checkpoint than the full score on 25–49% of datasets and a later one on about 1% or fewer.

Calibration does not improve where the gains are (Appendix U.3, Tables 6–7). For K≤4K\le4, the full score minus true risk averages −.160, −.088, −.051 and −.103 times the endpoint risk in the four suites, while the no-curvature average is near zero. At the smallest nn the full score's absolute error is also larger, for example .40 against .18 in the tabular suite at n=16n=16 (Table 6), the setting with the largest gain (−5.22 points, Table 7). At the largest sizes the gains are small or absent: −0.29 [−0.63, 0.05] in tabular at n=256n=256 and +0.02 [−0.21, 0.25] in iid at n=1024n=1024.

Q1: higher signal (Appendix U.4, Table 8). We drew new iid datasets at signal levels 1 and 2 instead of .06 and .35, and the best pilot-chosen checkpoint then has .76–.77 of the endpoint's risk. Curvature no longer helps, and at level 2 it slightly hurts, which by your criterion points to shrinkage: full minus no curvature is +0.13 [−0.35, 0.60] at level 1 and +0.65 [0.16, 1.15] at level 2. At n=1024n=1024, where that checkpoint has .93 of the endpoint's risk, the difference is +0.52 [0.12, 0.92].

Q1: misspecified features (Appendix U.4). We added (b/2)cos⁡(6αs)(b/2)\cos(6\alpha_s) to the value, with b∈{.06,.35}b\in\lbrace.06,.35\rbrace the original signal level. It is orthogonal to every feature, because the features are a constant and cosines and sines of jαsj\alpha_s with j≤4j\le4, where αs=2πs/24\alpha_s=2\pi s/24. The gain persists, at −1.12 [−1.37, −0.88] against the projected fixed point and −1.10 [−1.31, −0.88] against the true value. By your criterion this points toward calibration. The suite is still weak-signal, however, since the best pilot-chosen checkpoint has .43 and .48 of the endpoint's risk, and the pilot mean of β^\hat\beta again removes the gain.

A larger design (Appendix U.5, Table 9). We drew new datasets with 48 states, d∈{12,16}d\in\lbrace12,16\rbrace and n∈{256,1024,4096}n\in\lbrace256,1024,4096\rbrace, gating each configuration at half its population margins. Full minus no curvature is −0.73 [−0.87, −0.59] overall, −1.71 at n=256n=256 and −0.04 [−0.16, 0.09] at n=4096n=4096. Here the 1.5-fold penalty is worse than the full score, by 0.74 [0.31, 1.17].

As you say, the benefit cannot be predicted in advance (Appendix U.6). Within each original suite, configurations with a larger median ratio ∥β^∥M/∥h^∥M\lVert\hat\beta\rVert_M/\lVert\hat h\rVert_M gain more, with Spearman correlations between this median and full minus no curvature from −.56 to −.77. However, the median cannot be computed from one dataset, mainly tracks nn and does not transfer across designs.

Q3: why freezing still wins in the grouped suites (Lemma 23, Appendix U.7). Prop. 11 only shows existence. The grouped suites (weighted and sampling) use features Φ=EQ\Phi=EQ, where EE is the group-indicator matrix and QQ a fixed orthogonal matrix. Every estimator then depends only on B^=Q⊤γT^Q\hat B=Q^\top\gamma\hat TQ and b^=Q⊤rˉ\hat b=Q^\top\bar r, built from the group transition frequencies T^\hat T and mean group rewards rˉ\bar r, and not on the weighted group masses Λ^\hat\Lambda. Gram fluctuations therefore never move any estimator. The frozen-Gram derivatives along changes in Λ^\hat\Lambda are generally nonzero, however, so the frozen score adds variance that no estimator has. The population covariance cannot remove it, because the error lies in the derivative. Empirically, the frozen score also underestimates the risk of early candidates, so it selects earlier checkpoints and larger ridge parameters and shrinks more (Tables 3, 4 and 6). This extra shrinkage wins where shrinkage pays, but not consistently at higher signal: at signal level 2, full minus frozen is +2.81 [0.13, 5.50] in the weighted suite but −6.01 [−9.34, −2.69] in the sampling suite (Table 11). Lemma 23 does not apply to the iid suite, where the population covariance reverses the frozen-Gram advantage at the original signal levels (Table 14). At signal levels 1 and 2 the frozen-Gram score loses to the full score there by 37.63 and 59.17 points (Table 8). Sec. 1 now says that joint treatment is needed for a correct risk approximation but not necessarily for better selection.

AuthorsOpenReview ↗

Response to Reviewer qiCE (3/3): effect size, ridge, theory and gating (W1, W2, Q2)

Effect size and the pilot gap (W1). We agree that the gains are modest: 0.89–2.20 points (Table 2). The pilot-tuned fixed baselines estimate min⁡KRK\min_K R_K, the comparator in Thms 2 and 4, from 1,000 independent pilot datasets per setting, and, as you note, Table 1's 13–25-point gaps show that our selector is far from it.

Ridge and practical appeal (W1). We agree that choosing KK for exact linear fitted Q-evaluation is not a compelling target on its own and that ridge is the better family under our score. We claim no computational saving. Ridge selected by our score beats holdout-and-refit ridge in every suite, by 17.46–24.66 points, and checkpoint selection by the full score beats LSTD-Tournament in three suites and ties it in the weighted suite (Table 13). Shrinking the endpoint to h^(1−tr(MV∞)/∥h^∥M2)+\hat h(1-\mathrm{tr}(MV_\infty)/\lVert\hat h\rVert_M^2)_+, with no selection, is about as good as score-selected ridge in iid. Against checkpoint selection by the full score, it gains 3.31 points and ridge gains 3.49 (Tables 9 and 13). This shrunken endpoint is better than score-selected ridge in our larger design (46.7 against 48.6, Appendix U.5) but worse in the tabular and grouped suites (Tables 2, 5 and 13).

Oracle bounds (W2). Prop. 7 proves that the additive term of Thm 2, which Thm 4 shares, is at least eight times the leading endpoint risk, so neither bound can certify a gain over LSTD. Sec. 1 now presents the oracle bound only as keeping adaptive same-data selection at the endpoint's order-1/n1/n risk.

Calibration at the studied sizes (W2). We agree; our own experiments are affected too. In the cyclic iid configurations with d=8d=8 and γ=.95\gamma=.95, the population ratio σmin⁡(A−F)/λmin⁡(A)\sigma_{\min}(A-F)/\lambda_{\min}(A) is (29/1600)/(1/8) = .145 (Appendix G). These configurations are thus worse conditioned than the n=8n=8 example of Sec. 5.4, whose one-state value 1−γp1-\gamma p is .335. At n=64n=64, 23.4% of iid datasets fail the gate, and part 2/3 reports the realized calibration.

Thm 8 depends on vv (W2). Its proof is your identity summed over the counts, so Thm 8 maps the parameter space rather than giving a data-driven test, as Sec. 1 now says. For the Prop. 6 example, the exact risk of the no-curvature selector minus that of the full selector is +.087, +.030 and −.009 at n=8n=8, 16 and 32 (Appendix U.9, Table 15). At n=8n=8 the full selector (.134) beats the endpoint (.273) but loses to the fixed checkpoint K=2K=2 (.091).

Cor. 9 (W2). Your arithmetic is correct, and Cor. 9 is only an asymptotic sufficient condition. In your example the exact risks show that curvature stops helping at n=32n=32 and that from n=64n=64 on both selectors match the endpoint's risk to four decimals, so 1.6×1051.6\times10^5 reflects slack in the condition. For the experimental bank, part 2/3 shows that the empirical gain is already small or absent at our largest sample sizes.

Scope and tools (W2). We agree that beyond one state we cannot say when curvature helps or hurts, and Sec. 1 now names this as the main open problem. The tools are standard, and one addition is the second-order cancellation: comparing each candidate with the endpoint cancels the candidate's own mean shift, so only the endpoint's shift must be estimated (Eq. 71). The new experiments relax zero initialization, realizability, d≤8d\le8 and the 24-state design, while fixed features and iid blocks remain limitations (Sec. 6).

Q2: gating. Yes. In the iid suite the final output of every method goes through the same full-data gate, including the fixed eight-update method, the pilot-tuned baselines, and the refitted tournament and holdout-ridge outputs (Sec. 5.1, Appendix T.5). All methods therefore return zero on the same 891 failing datasets, which stay in every average with the loss of the zero prediction, so every paired contrast is exactly zero there. On the 6,309 passing datasets the ordering of the nine iid methods in Table 12 is unchanged, and full minus no curvature is −1.38 [−1.69, −1.07]. As you suspected, the primary thresholds came from known design margins, and Sec. 4.2 now says so. We therefore also set each test dataset's thresholds to half the empirical margins of its own independent pilot dataset of size mm. Fallbacks then drop from 891 to 228 for m=nm=n and to 585 for m=4nm=4n. The ordering is unchanged, and full minus no curvature is −1.20 [−1.47, −0.94] for m=nm=n and −1.39 [−1.63, −1.15] for m=4nm=4n. Sec. 5.4 now summarizes this.

If the revision addresses your concerns, we would be grateful if you would consider updating your assessment.

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

This paper discusses a joint empirical-moment expansion with an explicit remainder and then specializes smooth risk correction to dependent value estimates. The provided clear realizable cancellation example demonstrates why Gram-matrix uncertainty cannot generally be ignored.

The authors establish a scalar finite-bank characterization valid for arbitrary sample sizes and discount factors, including an explicit noisy example in which curvature improves risk for selected candidates but becomes detrimental beyond a boundary. This result does not constitute a general selection law for coupled features.

The sampling theorem conditions only in a neighborhood of the population moments and specifies a zero fallback outside that region. The associated oracle bound achieves an endpoint-scale risk rate, but does not establish that correction improves selection: its constants are insufficient to certify gains over the endpoint. The authors compare candidate families using the same all-data score and evaluate normalization, oracle selection, and covariance estimation.

The experiments cover overlapping features with random Gram matrices and normalized-difference LSTD-Tournament.

Critical strengths

It is great to see the main contribution of a theoretical analysis of the terms governing risk, accompanied by explicit evidence of when estimating those terms improves selection. Neither the correction nor the endpoint oracle rate supersedes established principles of risk estimation.

Critical weaknesses

It seems that more discussions on the background and literature could be added.

Questions for authors

Is this paper restricted to the linear MDPs setting? Adding a clear part about the problem setting would be helpful.

Is this paper restrict to MDP and reinforcement learning? Bellman updates and the setup in line 096 seems to be quite related to MDPs, but a formal definition and introduction is missing.

If so, can you add more discussions on the related works in MDPs?

Also, adding more discussions on related works and why this paper is novel among them would be helpful.

3 comments
AuthorsOpenReview ↗

Response to Reviewer t4HY: setting, related work and novelty

Thank you for your kind review.

Q1: Is the paper restricted to linear MDPs? No. We do not assume the linear Markov decision process (MDP) model of Yang & Wang (2019) and Jin et al. (2020), in which transitions and rewards are linear in known features. We only approximate the value of one fixed target policy by a linear function of fixed features, as least-squares temporal-difference (LSTD) learning and fitted Q-evaluation do. We assume no structure on the transition kernel or the reward, only that the observations are bounded, independent and identically distributed (iid) blocks and that the feature moment matrices stay well conditioned. Our 24-state overlapping-feature suite is not a linear MDP, since its two transition kernels have rank 24, whereas a linear MDP with d≤8d\le8 features would have rank at most 8 (Appendix T.1). Without sampling error, stable updates converge to a fixed point that equals the true value if that value is linear in the features and otherwise solves the projected Bellman equation (Sec. 2.1).

Q2: Is it restricted to MDPs and RL? Its questions and experiments are, and more narrowly concern offline evaluation of one fixed policy rather than policy optimization. Some proofs are more general (Appendix V.1): Thms 2 and 18 are proved for smooth maps of iid averages, and Thm 15 for any recursion of the form A^θk+1=F^θk+g^\hat A\theta_{k+1}=\hat F\theta_k+\hat g.

The formal definition you asked for (near l. 96) now opens Sec. 2.1. It defines the discounted MDP, the target policy π\pi, its value QπQ^\pi, the Bellman equation and the data, and it says that update (1), whose endpoint is the LSTD solution, is the least-squares sample version of the Bellman equation. Appendix V.1 lists the assumptions of each main result.

Q3: related work in MDPs (Sec. 6, Appendix V.2). Sec. 6 now credits the closest prior work, Mannor, Simester, Sun & Tsitsiklis (2007), who give second-order approximations of the bias and variance of the value computed from an estimated tabular model. Among other lines of work, linear off-policy evaluation (for example Duan et al., 2020) studies the error of the converged estimate and inference for it, whereas we choose among iterates computed from the same data. Finite-sample and regularized LSTD analyses (for example Lazaric et al., 2012) motivate our ridge candidates, and we add a common score rather than a new regularizer. Offline model selection compares candidates through Bellman residuals, tournaments (Liu et al., 2025) or Lepski-type rules based on confidence intervals (Su et al., 2020). MAGIC (Thomas & Brunskill, 2016) and covariance penalties such as Mallows' CpC_p (Mallows, 1973; Efron, 2004) also estimate risk on the same data. Our score is such a covariance penalty with an added term that corrects for the endpoint's second-order mean shift.

Q4: what is new. The tools are classical, and Mannor et al. (2007) already cover the converged tabular estimate. To our knowledge, four parts are new.

  1. A checkpoint KK that stops before convergence has a population bias dKd_K, and the quadratic term qKq_K of its error generally has a nonzero mean. Their cross term 2dK⊤M EqK2d_K^\top M\,\mathbb E q_K, where MM weights the prediction error, enters the risk at order 1/n1/n, the same as the variance. We derive this term jointly for reward, transition and Gram-matrix errors (Eq. 7, Thm 15).
  2. Comparing each candidate with the endpoint cancels the candidate's own second-order mean shift, so one score, computed without splitting the data, applies to checkpoints, ridge estimates and their union (Eq. 71).
  3. The guarantees for a fixed candidate's score and the oracle bound extend to ordinary iid transitions, whose single-observation Gram matrices are singular. The analysis needs invertibility only near the population moments, and the estimator returns zero on datasets that fail a conditioning check (Thm 4, Prop. 5).
  4. In one state, Thm 8 gives the exact condition under which the correction helps or hurts, for any nn and any finite set of candidates. It depends on the unknown value, so it describes where curvature helps but is not a test on data. Thm 17 shows that no exactly unbiased risk estimate exists with finitely many Bernoulli transitions.

After reading responses and reviews, I decide to not change the scores.

AuthorsOpenReview ↗

Response to Reviewer t4HY (follow-up)

Thank you for reading our responses and the other reviews, and for telling us your decision, which we respect.

Your review asked about the problem setting, the related work and the novelty, and the revised paper now addresses each of these points directly.

Problem setting. Section 2.1 opens with a formal definition of the policy evaluation problem and states that we do not assume a linear MDP. Appendix V.1 lists the assumptions of each main result.

Related work and novelty. Section 6 names the closest prior work, Mannor et al. (2007), who give second-order approximations of the bias and variance of the tabular plug-in value estimate. We add linear features with a random Gram matrix, the cross term of a checkpoint that stops before convergence, and a selection score that uses this term on the same data, together with an analysis of that selection. Appendix V.2 covers further related work in offline RL.

Limits. Section 1 states that the one-state result is not a general selection law for coupled features, and that the oracle bound cannot certify a gain over the converged solution. Following the other reviews, the abstract and Section 5.3 now present the curvature gains as data-adaptive shrinkage of the converged solution toward zero and report that these gains weaken, vanish or slightly reverse at higher signal, with the supporting controls in Appendix U.

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

The paper studies estimator selection in offline policy evaluation with fixed linear features, where repeated fitted Bellman updates reuse the same dataset. It explains how joint uncertainty in rewards, transitions, and the feature Gram matrix affects both the variance and the mean of the resulting value estimates. In particular, omitting the mean-curvature correction can miss an order -1/n contribution to the risk of a finite checkpoint.

The authors derive a same-data risk score for smooth value estimators, establish fixed-estimator calibration and separate selection guarantees, and extend the analysis to ordinary iid transitions using conditioning gates and an explicit fallback. Exact scalar examples characterize when curvature correction improves selection and when it hurts. Experiments compare checkpoint selection, matched ridge selection, tournament methods, and independent pilot-selected fixed estimators. Curvature produces modest within-family improvements, while substantial selection gaps, covariance-estimation costs, and small-sample failures remain.

Critical strengths
  1. Treating the Gram matrix, transition moment, and reward moment jointly is important because their effects can cancel. The exact random-Gram example makes this point convincingly: freezing Gram uncertainty can create spurious uncertainty even when the empirical endpoint is exact.

  2. It does not equate approximate unbiasedness of a fixed candidate’s score with accurate adaptive selection. The endpoint-scale oracle bound, its inability to certify improvement over convergence, and the distinction between observed conditioning and a confidence certificate are all useful clarifications.

  3. Applying the same score to ridge helps separate the benefit of the risk correction from the choice of checkpoint regularization. Independent pilot comparators expose remaining selection gaps. The authors also report unfavorable results, including better aggregate performance from matched ridge, cases where freezing Gram uncertainty helps, and severe small-sample score bias.

Critical weaknesses
  1. The explicit help/harm characterization is for the one-state setting. In multiple dimensions, the calibration and selection bounds do not directly identify when adding curvature will improve the selected estimator. The experiments reinforce this distinction: curvature gives statistically resolved but modest improvements, while covariance estimation, higher-order effects, and adaptive selection remain entangled. This limits the work’s value as an operational selection rule, although it does not invalidate its analytical contribution.

  2. The work describes the suite sizes and broad design choices, but I could not find complete definitions of the overlapping-feature construction, asymmetric transition dynamics, and full configuration grids, or a linked implementation. These details matter because the reported curvature effects are relatively small and the covariance-ablation behavior differs across designs. This appears addressable through a precise experimental appendix or accompanying code.

Questions for authors

Could you clarify the experimental specifications needed to reproduce Tables 1 and 2, particularly the overlapping-feature construction, asymmetric transition kernels, full configuration grids, and exact checkpoint bank? If these details are included in supplementary code, please indicate where they can be found.

1 comment
AuthorsOpenReview ↗

Response to Reviewer UCp1: help or harm beyond one state, and the experimental specification

Thank you for a balanced review.

W1: help or harm beyond one state. We agree. Thm 8 is our only exact characterization of when curvature helps. The multidimensional results (Thms 2, 4 and 18, Prop. 5) control calibration and the scale of the risk, and Sec. 1 now names this gap as the main open problem. Sec. 4.3 adds that in one state the correction shrinks the endpoint h^\hat h toward zero, more so when its estimated variance is large, and Thm 8 maps exactly when this helps. In several dimensions we know only which way curvature moves the selection. When the full and no-curvature scores select different predictions, the full score's choice ff has the smaller value of f⊤Mβ^f^\top M\hat\beta, where β^\hat\beta is the endpoint's estimated mean shift (Appendix U.1). This does not say whether the change helps. A configuration's median ratio ∥β^∥M/∥h^∥M\lVert\hat\beta\rVert_M/\lVert\hat h\rVert_M ranks configurations by gain within each original suite but not across designs (Appendix U.6), so it cannot predict help or harm either.

W1: what drives the gain (Appendix U). The gain disappears when β^\hat\beta is replaced by its average over pilot datasets or by a random direction (Table 5). In the iid suite it persists when the checkpoints start at twice the true parameter instead of zero, and a no-curvature score with a 1.5-fold covariance penalty, which shrinks toward the start, is then worse than the full score by 2.12 (Table 9). So the gain is data-adaptive shrinkage toward zero, not toward the start. It is not better calibration either. At the smallest nn, where the gains are largest, the full score's calibration error, including higher-order and covariance-estimation error, is larger than the no-curvature score's (Tables 6–7). With the true model's curvature term the score is worse in every suite (full minus this variant, tabular to iid: −2.44, −1.26, −1.98 and −1.36), but with the true covariance it is better (+2.764 to +4.258, Table 14), so covariance estimation has its own cost. At higher signal the gain weakens, vanishes or slightly reverses, and in a larger 48-state design it is −0.73 overall but only −0.04 at n=4096n=4096 (Tables 8, 9 and 11).

Why the covariance ablation differs by design. Sec. 5.3 now explains this. The grouped suites (weighted and sampling) use rotated group indicators as features, so every fitted estimator is invariant to fluctuations in the weighted share of observations per group (Lemma 23). The frozen-Gram derivatives along these fluctuations are generally nonzero, so freezing adds variance that no estimator has and that the population covariance cannot remove. Empirically, the frozen score then shrinks more, which pays in these weak-signal designs (Tables 3, 4 and 14). Freezing changes nothing in the tabular suite, and in the iid suite the population covariance reverses the frozen-Gram advantage (Table 14).

W2 and Q: experimental specification. We agree that the submitted paper lacked these details. The new Appendix T gives the complete specification needed to regenerate Tables 1–2 and Appendix U, including the four items you list.

  • Appendix T.1 gives the overlapping-feature construction. There are 24 states with angles αs=2πs/24\alpha_s=2\pi s/24 and d∈{4,8}d\in\lbrace4,8\rbrace trigonometric features, a constant followed by cos⁡(jαs)\cos(j\alpha_s) and sin⁡(jαs)\sin(j\alpha_s) for j=1,2,…j=1,2,\dots, scaled so that the evaluation matrix is M=I/dM=I/d. Current states are drawn uniformly, so a dataset need not contain every state.
  • Appendix T.1 also gives both kernels. The cyclic kernel stays, moves forward, moves back or terminates with probabilities .5, .25, .15 and .1. The asymmetric kernel adds .35+.1cos⁡αs.35+.1\cos\alpha_s to staying, .2+.1sin⁡αs.2+.1\sin\alpha_s to moving forward, .15 to jumping five states ahead and .05/24.05/24 to every state, and the remaining mass terminates.
  • Appendices T.1–T.3 give the full grids. The iid grid crosses the two kernels, d∈{4,8}d\in\lbrace4,8\rbrace, γ∈{.75,.95}\gamma\in\lbrace.75,.95\rbrace, signal levels .06 and .35, and n∈{64,256,1024}n\in\lbrace64,256,1024\rbrace, which gives 48 settings with 150 datasets each. The two grouped suites have 24 settings each, and the tabular suite has 36.
  • Appendix T.4 gives the exact checkpoint bank, K∈{0,1,2,3,4,6,8,12,16,24,32,48,64,96,128,∞}K\in\lbrace0,1,2,3,4,6,8,12,16,24,32,48,64,96,128,\infty\rbrace started from θ0=0\theta_0=0, and the ten ridge values.
  • Appendix T.5 specifies the baselines and the shared gate, Appendix T.6 the pilot-tuned baselines and every seed, and Appendix T.7 the computation steps.

If the revision addresses your concerns, we would be grateful if you would consider updating your assessment.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to all reviewers

We thank the reviewers for their careful reviews. In the replies, "l. NNN" is a line number in the submitted PDF, and all other references are to the revised PDF. Differences are in points of normalized risk (risk relative to the endpoint, ×100), negative values favor the first method named, and brackets give paired 95% intervals.

The main change in our interpretation. Our score's curvature term corrects for the second-order mean shift of the endpoint, the converged least-squares temporal-difference (LSTD) estimate. New controls support Reviewer qiCE's shrinkage reading of this term. In our experiments it improves selection by shrinking the endpoint toward zero by a data-dependent amount, not by estimating each candidate's risk more accurately. Its gains weaken, vanish or slightly reverse when the true values are larger relative to the noise. The abstract, Sec. 1 and Sec. 5.3 now say this, the new Appendix U gives the evidence on the same 19,800 test datasets and on new ones, and the theorems are unchanged. Our score compares each candidate with the endpoint on all the data. With or without the curvature term, selecting checkpoints by it beats our holdout-and-refit ridge in all four suites and the LSTD-Tournament selector in three, an advantage we now credit to classical covariance penalties (Mallows, 1973; Efron, 2004).

Presentation and reproducibility.

  • Sec. 2.1 now defines the setting formally, without assuming a linear Markov decision process (MDP). Sec. 6 and the new Appendix V add related work, including the closest prior work (Mannor et al., 2007).
  • The new Appendix T gives the complete experimental specification.
  • Sec. 1 now names the main open problem, when curvature helps beyond one state. It also says that our exact one-state result (Thm 8) depends on the unknown value, so it maps the parameter space rather than giving a data-driven test.
  • Secs. 2–4 now open with a one-sentence summary. Symbols that the submitted main text left undefined, such as R0R_0, R2R_2 and JJ in Eq. 15, are defined where they first appear, and Table 1 and Figure 1 have self-contained captions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.