Pith. sign in

REVIEW 18 references

The paper proves that full trajectory data turns offline policy evaluation into a polynomial-sample problem under linear q^pi-realizability and concentrability, provided the behavior policy is known.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

First polynomial-sample policy-evaluation algorithm for offline RL under all-policy linear q-realizability, concentrability, and trajectory data, plus a tighter policy-optimization bound.

T0 review reviewed 2026-08-04 challenge →

arxiv 2510.03494 v2 pith:CU2FIGIJ submitted 2025-10-03 cs.LG stat.ML

Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Fixed-Horizon Offline RL with Linear $q^\pi$-Realizability and Concentrability

Volodymyr Tkachuk , Csaba Szepesv\'ari , Xiaoqi Tan This is my paper
classification cs.LG stat.ML MSC 68Q3290C40
keywords offline reinforcement learningpolicy evaluationtrajectory datalinear q^pi-realizabilityconcentrabilityfitted Q-evaluationskippy Bellman operatorsfinite-horizon MDP
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper shows that policy evaluation in finite-horizon offline reinforcement learning becomes statistically efficient — sample complexity polynomial in the feature dimension, horizon, coverage constant, and inverse accuracy, and independent of the number of states — when the data are full trajectories, every policy's state-action value function is exactly linear in known features, and the data-collecting policy is known. This closes the evaluation half of a gap left by an earlier trajectory-data result, which had achieved the same kind of guarantee only for policy optimization. The learner does not need to identify which states are problematic; it builds a family of candidate estimates indexed by 'modified' MDPs that skip low-range states, and selects among them by minimizing the empirical expected advantage of the evaluation policy over the corresponding skippy policy. A tighter ridge-regression analysis also sharpens the earlier policy-optimization sample complexity by a factor of C0 d. The one caveat the paper itself flags is that the evaluation algorithm must know the behavior policy; the abstract's 'same assumptions' framing hides this extra condition, and removing it is left as future work.

Core claim

Under Assumptions 1–3 — linear q^pi-realizability for all memoryless policies, trajectory data generated by a behavior policy, and concentrability bounded by C0 — the paper proves (Theorem 1) that Algorithm 2, called LIN-q^pi-FQE, returns a value estimate vhat for any evaluation policy pi_e with |v^{pi_e}(s1) - vhat| <= eps with probability at least 1 - delta as soon as n = Theta~(C0^5 H^7 d^3 / eps^2 + L_phi^2) trajectories are available and pi_b is known. The proof works through skippy Bellman operators: since linear realizability does not imply Bellman completeness, the MDP is implicitly modified so that states whose q-values hardly depend on the action (low-range states) are 'skipped' by

What carries the argument

The central objects are skippy Bellman operators and modification sets G. A modification G encodes a smoothed decision to 'skip' a state — replacing its action choices with the behavior policy's distribution — whenever the range of q-values across actions at that state is small. The correct modification G* is unknown, so the learner enumerates a family of plausible modifications; for each G, the skippy Bellman policy and optimality operators define regression targets that depend on the whole future of a trajectory, which is exactly why trajectory data is needed. The key identity is that the q-function of the skippy policy pi^e_G satisfies a fixed-point equation under these operators, so fitt

Load-bearing premise

The load-bearing premise is that the learner knows the exact action probabilities of the data-generating policy; if it does not, Algorithm 2 cannot compute the skippy policies its selection rule compares, and the advantage-minimization argument collapses.

What would settle it

Simulate the exact setting of Theorem 1 with d=2, H=2, a known behavior policy, and an evaluation policy that differs from pi_b, taking the number of trajectories at the theorem's order of magnitude. If the observed error |vhat - v^{pi_e}(s1)| exceeds epsilon on more than delta of repetitions, the theorem's concentration lemmas cannot both hold. A more targeted check is to verify Lemma 15 directly: the minimizer of Eq. (12) should have empirical advantage at most alpha + 2 eps_tilde + zeta_2; a violation would locate the break in the proof.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Policy evaluation in finite-horizon offline RL is no longer subject to the state-space-size lower bound once full rollouts are available and every policy's q-function is linear; Theorem 1 gives a poly(d, H, C0, 1/eps) bound independent of |S|.
  • The same proof machinery improves the trajectory-data policy-optimization guarantee: the earlier sample complexity drops by a factor of C0 d.
  • The learner needs only the features of states along each trajectory, not the state identities themselves, so the approach applies when states are unobserved but features are available.
  • The advantage-minimization criterion gives a workable way to run fitted Q-evaluation without Bellman completeness: among candidate estimates, choose the one with smallest empirical expected advantage between the evaluation policy and its skippy counterpart.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Editorial: the known-behavior-policy condition may be the real price of trajectory data for evaluation. If pi_b must be learned or is misspecified, the advantage criterion in Eq. (12) becomes biased; a natural extension is to estimate pi_b from the same trajectories and measure how the bound degrades.
  • Editorial: the 'skip low-range states' idea is a model-simplification mechanism that could plausibly transfer to non-linear function classes or approximate realizability, since the modification error is controlled separately by the threshold alpha.
  • Editorial: the improved ridge-regression concentration (d/n instead of d^2/n) is likely reusable in other least-squares-based offline RL analyses to tighten exponents beyond the two theorems here.
  • Editorial: fully realizing this approach would require making the candidate sets Q_eval and Q_opt computationally tractable; the paper explicitly leaves efficient computation as future work.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Axiom & Free-Parameter Ledger

3 free parameters · 6 axioms · 0 invented entities

The paper introduces no empirical free parameters fitted to data; the listed quantities are analysis hyperparameters. The load-bearing domain assumptions are exact all-policy linear realizability, full-trajectory data with known behavior policy, and finite concentrability. The skippy MDP/operator is a mathematical construction, not a new physical entity. The main external load is carried by Lemmas 19, 12, 22, and 23 from prior work, mostly by the same authors.

free parameters (3)
  • skip threshold alpha = O~(C0^{5/2} H^{5/2} d^{3/2} / sqrt(n)) for eval (Eq. 20), O~(C0^{3/2} H^{5/2} d^{3/2} / sqrt(n)) for opt (Eq. 24)
    Analysis hyperparameter balancing modification error H*alpha against estimation error; chosen by hand to minimize the final bound, not fitted to data.
  • ridge regularization sqrt(lambda) = H^{3/2} d / L_tilde_theta (Eq. 30)
    Regularization in the empirical covariance used by the least-squares sets; chosen analytically to make the confidence-radius and concentration arguments close.
  • confidence radius beta = sqrt(lambda) L_tilde_theta + beta_bar (Eq. 31)
    Expands least-squares estimates to include true parameters with high probability; definition is analytic, not data-dependent.
axioms (6)
  • domain assumption Assumption 1: exact linear q^pi-realizability for every memoryless policy with known features and norm bounds
    Used throughout; Lemma 5 converts it into skippy Bellman completeness, so if it fails the central argument breaks. Approximate extension is mentioned but not proved.
  • domain assumption Assumption 2 with known behavior policy: trajectories are full rollouts from pi_b, and Theorem 1 additionally requires pi_b known
    Trajectory structure is what makes the skippy targets computable; known pi_b is required by Algorithm 2 and Remark 11. If pi_b is unknown, the advantage objective Eq. (12) cannot be evaluated.
  • domain assumption Assumption 3: concentrability coefficient C0 bounds all admissible distributions by the behavior marginals
    Used pervasively via Lemma 13 to convert expectations under arbitrary policies into expectations under the data distribution; if C0 is infinite, the bounds are vacuous.
  • standard math Lemma 19 from Tkachuk et al. (2024): skippy returns are linearly realizable with parameter norm L_theta(8 H^2 d0/alpha + 1)
    Loaded from prior work by the same group; it is parameter-free and has a proof in the cited paper, so it is treated as background rather than circular.
  • standard math Existence of a near-optimal design G* of size d0 = ceil(4d log log d + 16) (Todd 2016)
    Used to discretize the policy-parameter set and define the approximate range function; cited from a standard convex-geometry reference.
  • standard math Concentration tools: Hoeffding, covering numbers of Euclidean balls, Hsu et al. random-design ridge regression, performance-difference lemma
    Standard results invoked in Lemmas 14, 24, 26-28; Lemma 24's invocation of Hsu et al. is the one whose proof step was flagged as questionable.

reviewed 2026-08-04 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Fixed-Horizon Offline RL with Linear $q^\pi$-Realizability and Concentrability." pith.science (2026). https://pith.science/paper/CU2FIGIJ

@misc{pith2026251003494,
  author       = {Pith},
  title        = {Pith review of: Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Fixed-Horizon Offline RL with Linear $q^\pi$-Realizability and Concentrability},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CU2FIGIJ}},
  note         = {Machine review of arXiv:2510.03494}
}
Share X Bluesky LinkedIn Reddit HN
abstract

We study finite-horizon offline reinforcement learning (RL) with function approximation for both policy evaluation and policy optimization. Prior work established that statistically efficient learning is impossible for either of these problems when the only assumptions are that the data has good coverage (concentrability) and the state-action value function of every policy is linearly realizable ($q^\pi$-realizability) (Foster et al., 2021). Recently, Tkachuk et al. (2024) gave a statistically efficient learner for policy optimization, if in addition the data is assumed to be given as trajectories. In this work we present a statistically efficient learner for policy evaluation under the same assumptions. Further, we show that the sample complexity of the learner used by Tkachuk et al. (2024) for policy optimization can be improved by a tighter analysis.

Figures

Figures reproduced from arXiv: 2510.03494 by Csaba Szepesv\'ari, Volodymyr Tkachuk, Xiaoqi Tan.

Figure 1
Figure 1. Figure 1: The features for both MDPs are ϕ(s1, ·) = (1), ϕ(s3, ·) = (0.5), ϕ(·, ·) = (0) otherwise. Left: Linearly q π -realizable. Right: Linear MDP, due to skipping s1 via the up action. however, the reward for taking the up action is 1, while the reward for taking the down action is 0.5. As such, to satisfy linear q π -realizability, the features for the linear function class F can be defined as ϕ(s1, ·) = 1, sin… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 4 linked inside Pith

  1. [1]

    Learning theory from first principles

    Francis Bach. Learning theory from first principles. MIT press, 2024

    2024

  2. [2]

    Provably efficient exploration in policy optimization

    Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283--1294. PMLR, 2020

    2020

  3. [3]

    Information-theoretic considerations in batch reinforcement learning

    Jinglin Chen and Nan Jiang. Information-theoretic considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042--1051. PMLR, 2019

    2019

  4. [4]

    Offline reinforcement learning: Fundamental barriers for value function approximation

    Dylan J Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline reinforcement learning: Fundamental barriers for value function approximation. arXiv preprint arXiv:2111.10919, 2021

    Pith/arXiv arXiv 2021

  5. [5]

    Probability inequalities for sums of bounded random variables

    Wassily Hoeffding. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding, pages 409--426, 1994

    1994

  6. [6]

    Random design analysis of ridge regression

    Daniel Hsu, Sham M Kakade, and Tong Zhang. Random design analysis of ridge regression. In Conference on learning theory, pages 9--1. JMLR Workshop and Conference Proceedings, 2012

    2012

  7. [7]

    Offline reinforcement learning: Role of state aggregation and trajectory data

    Zeyu Jia, Alexander Rakhlin, Ayush Sekhari, and Chen-Yu Wei. Offline reinforcement learning: Role of state aggregation and trajectory data. arXiv preprint arXiv:2403.17091, 2024

    Pith/arXiv arXiv 2024

  8. [8]

    Offline reinforcement learning in large state spaces: Algorithms and guarantees

    Nan Jiang and Tengyang Xie. Offline reinforcement learning in large state spaces: Algorithms and guarantees. Statistical Science, 2024

    2024

  9. [9]

    Provably efficient reinforcement learning with linear function approximation

    Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pages 2137--2143. PMLR, 2020

    2020

  10. [10]

    Batch policy learning under constraints

    Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In International Conference on Machine Learning, pages 3703--3712. PMLR, 2019

    2019

  11. [11]

    Sample and oracle efficient reinforcement learning for mdps with linearly-realizable value functions

    Zakaria Mhammedi. Sample and oracle efficient reinforcement learning for mdps with linearly-realizable value functions. arXiv preprint arXiv:2409.04840, 2024

    Pith/arXiv arXiv 2024

  12. [12]

    Finite-time bounds for fitted value iteration

    R \'e mi Munos and Csaba Szepesv \'a ri. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9 0 (5), 2008

    2008

  13. [13]

    Markov decision processes: discrete stochastic dynamic programming

    Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014

    2014

  14. [14]

    Trajectory data suffices for statistically efficient learning in offline rl with linear qpi-realizability and concentrability

    Volodymyr Tkachuk, Gell \'e rt Weisz, and Csaba Szepesv \'a ri. Trajectory data suffices for statistically efficient learning in offline rl with linear qpi-realizability and concentrability. Advances in Neural Information Processing Systems, 37: 0 83268--83313, 2024

    2024

  15. [15]

    Minimum-volume ellipsoids: Theory and algorithms

    Michael J Todd. Minimum-volume ellipsoids: Theory and algorithms. SIAM, 2016

    2016

  16. [16]

    High-dimensional probability: An introduction with applications in data science, volume 47

    Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018

    2018

  17. [17]

    Online rl in linearly qpi-realizable mdps is as easy as in linear mdps if you learn what to ignore

    Gell \'e rt Weisz, Andr \'a s Gy \"o rgy, and Csaba Szepesv \'a ri. Online rl in linearly qpi-realizable mdps is as easy as in linear mdps if you learn what to ignore. arXiv preprint arXiv:2310.07811, 2023

    Pith/arXiv arXiv 2023

  18. [18]

    Learning near optimal policies with low inherent bellman error

    Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978--10989. PMLR, 2020

    2020

This paper was first reviewed by deepseek-v4-flash on August 4, 2026.