Pith. sign in

REVIEW 4 major objections 4 minor 109 references

On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures

T0 review · 4 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read This survey argues that the statistical complexity of offline RL is now tightly characterized for tabular, linear, and parametric models, with pessimism and marginalized importance sampling as the mechanisms that attain it.

desk verdict Useful niche survey with a clean map, but the headline claim of tight statistical complexity outruns the displayed asymptotic theorems. read the letter →

arxiv 2501.02089 v1 pith:RTZWRHDB submitted 2025-01-03 cs.LG cs.AI

Ming Yin , Mengdi Wang , Yu-Xiang Wang This is my paper · ORCID
classification cs.LGcs.AI MSC 62F1262C2068Q3268T05
keywords offlinereinforcementlearningoff-policyevaluationpolicyinstance-dependentboundsmarginalizedimportancesamplingpessimismlow-adaptiveexplorationsamplecomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This review article makes the case that offline reinforcement learning, not online exploration, is the right model for most real-world sequential decision problems, because logging data is usually fixed and experimentation is costly or unsafe. Within that setting, it surveys a body of results whose collective claim is that the statistical complexity of the two central tasks — evaluating a fixed policy (OPE) and learning a near-optimal policy (OPL) — is now tightly understood for tabular MDPs and for linear and parametric differentiable function approximation. The survey contrasts worst-case minimax guarantees with instance-dependent bounds, and argues that pessimistic, variance-aware estimators achieve both forms of optimality: matching Cramér–Rao lower bounds in evaluation and producing intrinsic bounds in learning that reveal which problem instances are easy or hard. It then reviews low-adaptive exploration as the middle ground between offline and online RL, where near-optimal regret is achievable with only $O(\log \log T)$ policy switches or batches in the tabular setting.

What carries the argument

The load-bearing machinery is a pair of ideas. First, marginalized importance sampling (MIS): the change-of-measure identity $v^\pi = \mathbb{E}_\mu[\sum_{t=1}^H (d^\pi_t(s_t)/d^\mu_t(s_t)) r^\pi_t(s_t)]$ lets an estimator track marginal state density ratios instead of the exploding cumulative ratio $\rho_{1:t}$, and the iterative law of total variance (Lemma 3.3) shows the variance lower bound is only $O(H^2)$ rather than exponential. Second, pessimism with variance-dependent uncertainty: the penalty $\Gamma_h(s,a) = \tilde O(\sqrt{\mathrm{Var}_{\hat P_{s,a}}(\hat r_h + \hat V_{h+1})/n_{s,a}} + H/n_{s,a})$ converts aleatoric variance into a per-state adaptive learning difficulty, and in function approximation the same idea is carried by variance-weighted least squares with reweighted Gram matrices. The survey also relies on semiparametric efficiency theory, via influence functions for the linear and parametric FQE lower bounds, and on policy-elimination schedules with G-optimal experiment design for the low-adaptive results.

What would settle it

A concrete check would be to simulate a tabular MDP with known transition probabilities, a behavior policy satisfying Assumption 1, and finite state and action spaces, then compare the MSE of TMIS against the Cramér–Rao variance of Theorem 3.1 at increasing $n$: if $\lim n \cdot \mathrm{MSE}$ exceeds that bound, the optimality claim fails. Symmetrically, a linear MDP satisfying Assumption 2 and policy completeness where an estimator beats the variance $\sigma^2$ of Theorem 4.1 would refute the claimed lower bound.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the apparent curse of horizon in off-policy evaluation is not fundamental: by replacing cumulative importance ratios with marginalized density ratios $d^\pi_t/d^\mu_t$, the tabular marginalized importance sampling (TMIS) estimator achieves mean-squared error that matches a Cramér–Rao lower bound, making it asymptotically efficient and locally minimax optimal. For function approximation, the survey reports analogous efficiency: linear Fitted Q-Evaluation is asymptotically normal with the semiparametrically optimal variance, and parametric FQE inherits the same property under realizability, Bellman completeness, and a gradient-covariance coverage condition. For offline policy learning, pessimistic value iteration with a Bernstein-style, variance-aware penalty yields an instance-dependent bound whose leading term is $\sum_{h,(s,a)} d^{\pi^*}_h(s,a) \sqrt{\mathrm{Var}_{P}(r_h+V^*_{h+1})/(n d^\mu_h(s,a))}$, which subsumes known minimax rates and speeds up automatically on deterministic or partially deterministic systems. Together these results support the survey's conclusion that the statistical complexity of offline RL is now characterized tightly, both in the worst case and per instance, across the tabular, linear, and parametric hierarchy.

Load-bearing premise

The survey's usefulness rests on the correctness of the theorems it cites, several from the authors' earlier papers, so if a key tight bound (for instance, TMIS's asymptotic efficiency or the linear FQE variance formula) were wrong or not original, the claimed tight characterization of these problems would lose its basis.

Editorial extensions

If this is right

  • Off-policy evaluation in tabular RL can be done with mean squared error $\Theta(\tau_s \tau_a H^2/n)$, exponentially improving over importance sampling's $\exp(H)/n$; even on-policy evaluation can be made asymptotically more efficient than Monte Carlo averaging.
  • Linear and parametric FQE estimators are asymptotically normal with the optimal variance, so bootstrap-based confidence intervals for policy values are justified in these models.
  • Offline policy learning bounds that carry $\mathrm{Var}_P(r_h+V^*_{h+1})$ imply that deterministic or partially deterministic environments can be learned at $1/n$ or faster rates than the worst-case $1/\sqrt n$.
  • Low-adaptive exploration can achieve $\tilde O(\sqrt{T})$ regret with $O(\log \log T)$ batches in tabular RL and $O(H)$-batch reward-free exploration in linear MDPs, so near-online performance is possible with few deployments.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The intrinsic bound's factorization into distribution mismatch and environmental variation suggests a computable per-instance hardness score $\sum_{s,a} d_{\pi^*}(s,a) \sqrt{\mathrm{Var}/(n d_\mu)}$, which could be used as a diagnostic for when offline RL will succeed on a given logged dataset before running a full algorithm.
  • If the low-adaptive lower bounds are tight, closing the gap between $\tilde O(\sqrt{T})$ regret with $O(\log T)$ batches, the current state for linear MDPs, and the $\Omega(\log \log T)$ lower bound would require a fundamentally different mechanism than doubling, likely one combining variance-weighted pessimism with staged policy elimination.
  • The survey's message that on-policy Monte Carlo is not efficient suggests a practical recommendation: even when the logging and target policies coincide, long-horizon evaluation should use model-based or marginalized estimators rather than direct return averaging, unless the environment is nearly deterministic.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 4 minor

Summary. This manuscript is a survey of recent statistical results for offline policy evaluation (OPE), offline policy learning (OPL), and low-adaptive exploration in tabular, linear, and parametric differentiable reinforcement-learning models. It synthesizes results, mostly from the authors' prior work, on marginalized importance sampling, fitted Q-evaluation, pessimistic value iteration, variance-weighted FQI, and batched exploration, and it presents the main theorem statements together with proof sketches and open problems. The paper's central claim is that the statistical complexity of these problems is now tightly characterized, with algorithms that are not only minimax optimal but also adaptive to individual problem instances.

Significance. If the quoted theorems are accurate, the survey is a useful and well-organized synthesis of an active area. Its strengths include a clear taxonomy of coverage assumptions, a careful explanation of why importance-sampling OPE suffers a curse of horizon, and a readable account of instance-dependent bounds and of the pessimism principle. The paper is open about being a niche survey and does not claim new technical results. Its main weaknesses are that its utility depends entirely on the correctness of cited theorems and that the conclusion overstates the OPE results: several of the displayed 'optimality' statements are asymptotic efficiency results rather than finite-sample minimax characterizations, and this distinction is blurred in the abstract and conclusion. The survey would be a solid contribution after these claims are qualified and after the technical errors in the displayed statements are corrected.

major comments (4)
  1. [Section 3.3, Theorem 3.4, Eq. (7)] The displayed MSE expansion conditions the variance on s_t only, while the Cramér–Rao bound in Theorem 3.1 and the limiting expression in the paragraph after Theorem 3.4 both condition on (s_t, a_t). As printed, the variance term is strictly larger by the law of total variance, so the claimed equality with the CR bound is false. If this is a typographical error, the equation must be corrected; if not, the asymptotic-efficiency claim does not follow. This is load-bearing because the paper's headline 'tight characterization' of tabular OPE rests on the exact match between this expansion and Theorem 3.1.
  2. [Sections 3.3, 4.1, 4.2 and Conclusion] Theorems 3.4, 4.1, and 4.2 are asymptotic statements: Theorem 3.1 is a variance lower bound for unbiased estimators, and the local asymptotic minimaxity invoked after Theorem 3.4 is an asymptotic property under parametric regularity. The abstract and conclusion nevertheless claim that the statistical complexity of OPE is 'tightly characterized' and that the algorithms are 'optimal for every problem instance separately.' These claims are stronger than the displayed theorems. Please qualify the OPE statements as asymptotic efficiency under regularity conditions and reserve 'finite-sample minimax' for the OPL results that have matching finite-sample lower bounds.
  3. [Section 5.2 and Section 6.1, Eq. (16)] The survey presents instance-dependent upper bounds such as Eq. (13) and Eq. (16) but does not state matching instance-dependent lower bounds. The heading 'Towards instance optimality' and the conclusion's statement that the algorithms are 'optimal for every problem instance separately' require such lower bounds, unless the authors explicitly say these are instance-adaptive upper bounds. Either include the relevant lower-bound statements from the cited literature or soften the language. This matters because the claimed advance over worst-case minimax bounds is precisely the instance-level optimality.
  4. [Section 7.1] The text says APEVE achieves 'near-optimal regret O~(sqrt(H^4 S^2 A T)) ... optimal up to a factor of HS.' With the standard tabular regret lower bound Ω(sqrt(H^3 S A T)), the gap is sqrt(HS), not HS. If the lower bound used in the cited work is different, the exact expression should be stated; as written, the claimed gap factor is inconsistent with the quoted rates and should be verified.
minor comments (4)
  1. [Section 7.2, Theorem 7.2] The citation in the theorem statement reads 'Theorem 7.2 and 7.2 of [73]'; this appears to be a reference-number typo and should be corrected to the actual theorem numbers.
  2. [Appendix A, Example 2] In the second curse-of-horizon example, the text says 'random variable sum_{t=1}^H pi_t/mu_t ~ N(HE_log, HV_log)' and 'product ... ~ LogNormal'; the sum should be over log(pi_t/mu_t), and the normal approximation is for sum_t log(pi_t/mu_t), not for sum_t pi_t/mu_t. This typo makes the CLT argument confusing.
  3. [Throughout] There are several typographical errors, including 'time-inhomogenuous' in Section 2.1, 'generating generating function' in Appendix A, and 'regraded' in Section 4.1. A careful proofreading pass is needed.
  4. [Section 3.2, Eq. (3) and surrounding text] The notation r^pi_t(s) before Eq. (3) is defined as an expectation over actions under pi, but the earlier reward notation r(s,a) is used as an expected reward; please make the distinction between realized rewards and expected rewards consistent throughout the paper.

Circularity Check

0 steps flagged · score 2.0 of 10

Survey with heavy but disclosed self-citation; no derivation reduces to its inputs, so no significant circularity.

full rationale

This is a review article, not an original derivation, so the usual circularity failure modes (fitting a parameter and calling it a prediction, defining X in terms of Y, importing a uniqueness theorem from the authors' own prior work) do not apply. The theorems quoted in Sections 3.3, 4.1, 4.2, 5, 6, and 7 are imported from cited papers, many authored by the same researchers (e.g., [93, 97] for MIS/TMIS, [15, 28] for linear FQE, [104] for parametric FQE, [102] for parametric OPL, and [73, 74] for low-adaptive RL). The paper explicitly disclaims novelty: 'the topics and results covered in this paper focus on a niche that the coauthors studied in the past few years... we do not make any claims about novelty and precedence of scientific discovery.' A peer-reviewed external result does not become an input of this paper merely because the survey chooses to present it; the cited papers are independently published and falsifiable. The only internal anomaly is a conditioning mismatch in Eq. (7), where the displayed MSE conditions Var[...] on s_t while the asymptotic-efficiency paragraph and Theorem 3.1 condition on (s_t, a_t); this is a correctness or typographical issue, not a circularity, and it does not turn the survey's conclusion into a restatement of its assumptions. Because the survey's central claim is a literature summary rather than a new derivation, no step reduces by construction to a fitted value or to a self-citation chain; the score is at the low end.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The survey introduces no new entities or fitted parameters. Its claims inherit the coverage and realizability assumptions from the original papers. The correctness of the cited proofs and the absence of prior identical results are background premises.

assumptions (5)
  • domain assumption Assumption 1: bounded state and policy density ratios for tabular OPE (dπ_t/dµ_t finite, π/µ finite).
    Necessary for importance-weight estimators to have finite variance; used in the CR lower bound and TMIS efficiency result (Section 3.3).
  • domain assumption Assumption 4: uniform data coverage dm := min_{h,s,a} dµ_h(s,a) > 0.
    Used in minimax optimal OPL results and as a baseline for instance-dependent bounds (Section 5.1).
  • domain assumption Assumption 6: single policy coverage, dµ > 0 wherever dπ* > 0.
    Minimal assumption for the intrinsic offline learning bound of Theorem 5.1 (Section 5.2).
  • domain assumption Assumption 7: realizability and Bellman completeness for parametric F.
    Used in Theorem 6.2 for parametric OPL, and in Section 4.2 for FQE efficiency.
  • domain assumption Assumption 9: uniform coverage for parametric function class with gradient covariance lower bounded by κI.
    Used in the parametric OPL results; generalizes Assumption 8 (linear case).

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures." pith.science (2026). https://pith.science/paper/RTZWRHDB

@misc{pith2026250102089,
  author       = {Pith},
  title        = {Pith review of: On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RTZWRHDB}},
  note         = {Machine review of arXiv:2501.02089}
}
read the original abstract

This article reviews the recent advances on the statistical foundation of reinforcement learning (RL) in the offline and low-adaptive settings. We will start by arguing why offline RL is the appropriate model for almost any real-life ML problems, even if they have nothing to do with the recent AI breakthroughs that use RL. Then we will zoom into two fundamental problems of offline RL: offline policy evaluation (OPE) and offline policy learning (OPL). It may be surprising to people that tight bounds for these problems were not known even for tabular and linear cases until recently. We delineate the differences between worst-case minimax bounds and instance-dependent bounds. We also cover key algorithmic ideas and proof techniques behind near-optimal instance-dependent methods in OPE and OPL. Finally, we discuss the limitations of offline RL and review a burgeoning problem of \emph{low-adaptive exploration} which addresses these limitations by providing a sweet middle ground between offline and online RL.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

109 extracted references · 69 canonical work pages

  1. [1]

    Im- proved algorithms for linear stochastic bandits

    Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Im- proved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011

    2011

  2. [2]

    Model-based reinforcement learning with a generative model is minimax op- timal

    Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax op- timal. In Conference on Learning Theory, pages 67–83. PMLR, 2020

    2020

  3. [3]

    Degenerate nonlinear programming with a quadratic growth condition

    Mihai Anitescu. Degenerate nonlinear programming with a quadratic growth condition. SIAM Journal on Optimization, 10 (4):1116–1135, 2000

    2000

  4. [4]

    Fitted q- iteration in continuous action-space mdps

    András Antos, Csaba Szepesvári, and Rémi Munos. Fitted q- iteration in continuous action-space mdps. Advances in neural information processing systems, 20, 2007

    2007

  5. [5]

    Learning the target network in function space

    Kavosh Asadi, Yao Liu, Shoham Sabach, Ming Yin, and Rasool Fakoor. Learning the target network in function space. Interna- tional Conference on Machine Learning, 2024

    2024

  6. [6]

    Finite-time analysis of the multiarmed bandit problem, 2002

    P Auer. Finite-time analysis of the multiarmed bandit problem, 2002

    2002

  7. [7]

    Minimax regret bounds for reinforcement learning

    Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In Interna- tional conference on machine learning, pages 263–272. PMLR, 2017

    2017

  8. [8]

    Prov- ably efficient q-learning with low switching cost

    Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Prov- ably efficient q-learning with low switching cost. Advances in Neural Information Processing Systems, 32, 2019

    2019

Show all 109 references
  1. [9]

    Training a helpful and harmless assistant with reinforcement learning from human feedback

    Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. Technical Report, 2022

    2022

  2. [10]

    Dynamic programming

    Richard Bellman. Dynamic programming. science, 153(3731): 34–37, 1966

    1966

  3. [11]

    Online learning with switching costs and other adaptive adversaries

    Nicolo Cesa-Bianchi, Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. Advances in Neural Information Processing Systems, 26, 2013

    2013

  4. [12]

    Information-theoretic considera- tions in batch reinforcement learning

    Jinglin Chen and Nan Jiang. Information-theoretic considera- tions in batch reinforcement learning. In International Confer- ence on Machine Learning, pages 1042–1051. PMLR, 2019

    2019

  5. [13]

    Deep reinforcement learning from human preferences

    Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017

    2017

  6. [14]

    Pes- simistic nonlinear least-squares value iteration for offline rein- forcement learning

    Qiwei Di, Heyang Zhao, Jiafan He, and Quanquan Gu. Pes- simistic nonlinear least-squares value iteration for offline rein- forcement learning. arXiv preprint arXiv:2310.01380, 2023

    2023 arXiv

  7. [15]

    Minimax-optimal off- policy evaluation with linear function approximation

    Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off- policy evaluation with linear function approximation. In Inter- national Conference on Machine Learning , pages 2701–2709. PMLR, 2020

    2020

  8. [16]

    Dou- bly robust policy evaluation and learning

    Miroslav Dudík, John Langford, and Lihong Li. Dou- bly robust policy evaluation and learning. arXiv preprint arXiv:1103.4601, 2011

    2011 arXiv

  9. [17]

    Tree-based batch mode reinforcement learning

    Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learn- ing Research, 6, 2005

    2005

  10. [18]

    Discovering faster matrix multipli- cation algorithms with reinforcement learning

    Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J R Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, et al. Discovering faster matrix multipli- cation algorithms with reinforcement learning....

    2022

  11. [19]

    Theory of statistical estimation

    Ronald Aylmer Fisher. Theory of statistical estimation. In Mathematical proceedings of the Cambridge philosophical so- ciety, volume 22, pages 700–725. Cambridge University Press, 1925

    1925

  12. [20]

    A prov- ably efficient algorithm for linear markov decision process with low switching cost

    Minbo Gao, Tianle Xie, Simon S Du, and Lin F Yang. A prov- ably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint arXiv:2101.00494, 2021

    2021 arXiv

  13. [21]

    Batched multi-armed bandits problem

    Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. Advances in Neural In- formation Processing Systems, 32, 2019

    2019

  14. [22]

    Off-policy deep rein- forcement learning by bootstrapping the covariate shift

    Carles Gelada and Marc G Bellemare. Off-policy deep rein- forcement learning by bootstrapping the covariate shift. InPro- ceedings of the AAAI Conference on Artificial Intelligence, vol- ume 33, pages 3647–3655, 2019

    2019

  15. [23]

    Minimax pac bounds on the sample complexity of rein- forcement learning with a generative model

    Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kap- pen. Minimax pac bounds on the sample complexity of rein- forcement learning with a generative model. Machine learning, 91:325–349, 2013

    2013

  16. [24]

    Maxmin expected utility with non-unique prior

    Itzhak Gilboa and David Schmeidler. Maxmin expected utility with non-unique prior. Journal of mathematical economics, 18 (2):141–153, 1989

    1989

  17. [25]

    Approximate solutions to Markov decision processes

    Geoffrey J Gordon. Approximate solutions to Markov decision processes. Carnegie Mellon University, 1999

    1999

  18. [26]

    Networkgym: Reinforcement learn- ing environments for multi-access traffic management in net- work simulation

    Momin Haider, Ming Yin, Menglei Zhang, Arpit Gupta, Jing Zhu, and Yu-Xiang Wang. Networkgym: Reinforcement learn- ing environments for multi-access traffic management in net- work simulation. Advances in Neural Information Processing Systems (NeurIPS 2024)-Dataset and Benchmark, 2024

    2024

  19. [27]

    Consistent on-line off-policy evaluation

    Assaf Hallak and Shie Mannor. Consistent on-line off-policy evaluation. In International Conference on Machine Learning, pages 1372–1383. PMLR, 2017

    2017

  20. [28]

    Bootstrapping fitted q-evaluation for off- policy inference

    Botao Hao, Xiang Ji, Yaqi Duan, Hao Lu, Csaba Szepesvari, and Mengdi Wang. Bootstrapping fitted q-evaluation for off- policy inference. In International Conference on Machine Learning, pages 4074–4084. PMLR, 2021

    2021

  21. [29]

    Effi- cient estimation of average treatment effects using the estimated propensity score

    Keisuke Hirano, Guido W Imbens, and Geert Ridder. Effi- cient estimation of average treatment effects using the estimated propensity score. Econometrica, 71(4):1161–1189, 2003

    2003

  22. [30]

    A generalization of sampling without replacement from a finite universe

    Daniel G Horvitz and Donovan J Thompson. A generalization of sampling without replacement from a finite universe. Jour- nal of the American statistical Association , 47(260):663–685, 1952

    1952

  23. [31]

    Towards deployment-efficient reinforcement learning: Lower bound and optimality

    Jiawei Huang, Jinglin Chen, Li Zhao, Tao Qin, Nan Jiang, and Tie-Yan Liu. Towards deployment-efficient reinforcement learning: Lower bound and optimality. InInternational Confer- ence on Learning Representations, 2022

    2022

  24. [32]

    Aleatoric and epis- temic uncertainty in machine learning: An introduction to con- cepts and methods

    Eyke Hüllermeier and Willem Waegeman. Aleatoric and epis- temic uncertainty in machine learning: An introduction to con- cepts and methods. Machine learning, 110(3):457–506, 2021. STATISTICAL COMPLEXITY FOR OFFLINE AND LOW-ADAPTIVE RL 19

    2021

  25. [33]

    Doubly robust off-policy value eval- uation for reinforcement learning

    Nan Jiang and Lihong Li. Doubly robust off-policy value eval- uation for reinforcement learning. In International conference on machine learning, pages 652–661. PMLR, 2016

    2016

  26. [34]

    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

  27. [35]

    Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pages 5084–5096

    Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pages 5084–5096. PMLR, 2021

    2021

  28. [36]

    Double reinforcement learning for efficient off-policy evaluation in markov decision processes

    Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient off-policy evaluation in markov decision processes. Journal of Machine Learning Research, 21(167):1– 63, 2020

    2020

  29. [37]

    Efficiently breaking the curse of horizon in off-policy evaluation with double reinforce- ment learning

    Nathan Kallus and Masatoshi Uehara. Efficiently breaking the curse of horizon in off-policy evaluation with double reinforce- ment learning. Operations Research, 70(6):3282–3302, 2022

    2022

  30. [38]

    Near-optimal reinforce- ment learning in polynomial time

    Michael Kearns and Satinder Singh. Near-optimal reinforce- ment learning in polynomial time. Machine learning, 49:209– 232, 2002

    2002

  31. [39]

    Introduction to empirical processes and semiparametric inference, volume 61

    Michael R Kosorok. Introduction to empirical processes and semiparametric inference, volume 61. Springer, 2008

    2008

  32. [40]

    Offline reinforcement learning with fisher divergence critic regularization

    Ilya Kostrikov, Rob Fergus, Jonathan Tompson, and Ofir Nachum. Offline reinforcement learning with fisher divergence critic regularization. In International Conference on Machine Learning, pages 5774–5783. PMLR, 2021

    2021

  33. [41]

    Conservative q-learning for offline reinforcement learning

    Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. Ad- vances in Neural Information Processing Systems , 33:1179– 1191, 2020

    2020

  34. [42]

    Minimax theory

    John Lafferty, Han Liu, and Larry Wasserman. Minimax theory. Lecture notes on Statistical Machine Learning, 2008. URL http: //www.stat.cmu.edu/~larry/=sml/Minimax.pdf

    2008

  35. [43]

    Batch policy learning under constraints

    Hoang Le, Cameron V oloshin, and Yisong Yue. Batch policy learning under constraints. In International Conference on Ma- chine Learning, pages 3703–3712. PMLR, 2019

    2019

  36. [44]

    Offline reinforcement learning: Tutorial, review, and perspec- tives on open problems

    Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspec- tives on open problems. arXiv preprint arXiv:2005.01643 , 2020

    2005 arXiv

  37. [45]

    Breaking the sample size barrier in model-based reinforcement learning with a generative model

    Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances in neural informa- tion processing systems, 33:12861–12872, 2020

    2020

  38. [46]

    Offline reinforcement learning with closed-form policy improvement operators

    Jiachen Li, Edwin Zhang, Ming Yin, Qinxun Bai, Yu-Xiang Wang, and William Yang Wang. Offline reinforcement learning with closed-form policy improvement operators. In Interna- tional Conference on Machine Learning , pages 20485–20528. PMLR, 2023

    2023

  39. [47]

    Unbi- ased offline evaluation of contextual-bandit-based news article recommendation algorithms

    Lihong Li, Wei Chu, John Langford, and Xuanhui Wang. Unbi- ased offline evaluation of contextual-bandit-based news article recommendation algorithms. In Proceedings of the fourth ACM international conference on Web search and data mining, pages 297–306, 2011

    2011

  40. [48]

    Monte Carlo strategies in scientific computing, volume 10

    Jun S Liu and Jun S Liu. Monte Carlo strategies in scientific computing, volume 10. Springer, 2001

    2001

  41. [49]

    Breaking the curse of horizon: Infinite-horizon off-policy es- timation

    Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite-horizon off-policy es- timation. Advances in neural information processing systems , 31, 2018

    2018

  42. [50]

    Off-policy policy gradient with stationary distribution cor- rection

    Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brun- skill. Off-policy policy gradient with stationary distribution cor- rection. In Uncertainty in artificial intelligence , pages 1180–

  43. [51]

    Provably good batch off-policy reinforcement learning without great exploration

    Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brun- skill. Provably good batch off-policy reinforcement learning without great exploration. Advances in neural information pro- cessing systems, 33:1264–1274, 2020

    2020

  44. [52]

    Mildly conservative q-learning for offline reinforcement learning

    Jiafei Lyu, Xiaoteng Ma, Xiu Li, and Zongqing Lu. Mildly conservative q-learning for offline reinforcement learning. Ad- vances in Neural Information Processing Systems , 35:1711– 1724, 2022

    2022

  45. [53]

    the distribution-norm to the res- cue

    Odalric-Ambrym Maillard, Timothy A Mann, and Shie Man- nor. How hard is my mdp?" the distribution-norm to the res- cue". Advances in Neural Information Processing Systems, 27, 2014

    2014

  46. [54]

    Faster sorting algorithms discovered using deep reinforcement learn- ing

    Daniel J Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Leurent, Shariq Iqbal, Jean-Baptiste Lespiau, Alex Ahern, et al. Faster sorting algorithms discovered using deep reinforcement learn- ing. Nature, 618(7964):257–263, 2023

    2023

  47. [55]

    Neural adaptive video streaming with pensieve

    Hongzi Mao, Ravi Netravali, and Mohammad Alizadeh. Neural adaptive video streaming with pensieve. In Proceedings of the conference of the ACM special interest group on data commu- nication, pages 197–210, 2017

    2017

  48. [56]

    Deployment-efficient reinforce- ment learning via model-based offline optimization

    Tatsuya Matsushima, Hiroki Furuta, Yutaka Matsuo, Ofir Nachum, and Shixiang Gu. Deployment-efficient reinforce- ment learning via model-based offline optimization. In Inter- national Conference on Learning Representations, 2021

    2021

  49. [57]

    Dependent central limit theorems and in- variance principles

    Donald L McLeish. Dependent central limit theorems and in- variance principles. the Annals of Probability , 2(4):620–628, 1974

    1974

  50. [58]

    Variance-aware off-policy evaluation with linear function ap- proximation

    Yifei Min, Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Variance-aware off-policy evaluation with linear function ap- proximation. Advances in neural information processing sys- tems, 34:7598–7610, 2021

    2021

  51. [59]

    Human-level control through deep reinforcement learning

    V olodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Mar- tin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. na- ture, 518(7540):529–533, 2015

    2015

  52. [60]

    Bootstrapping: A nonparametric approach to statistical infer- ence

    Christopher Z Mooney, Robert D Duval, and Robert Duvall. Bootstrapping: A nonparametric approach to statistical infer- ence. Number 95. sage, 1993

    1993

  53. [61]

    Finite-time bounds for fit- ted value iteration

    Rémi Munos and Csaba Szepesvári. Finite-time bounds for fit- ted value iteration. Journal of Machine Learning Research , 9 (5), 2008

    2008

  54. [62]

    Marginal mean models for dynamic regimes

    Susan A Murphy, Mark J van der Laan, James M Robins, and Conduct Problems Prevention Research Group. Marginal mean models for dynamic regimes. Journal of the American Statisti- cal Association, 96(456):1410–1423, 2001

    2001

  55. [63]

    Dualdice: Behavior-agnostic estimation of discounted stationary distribu- tion corrections

    Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribu- tion corrections. Advances in neural information processing systems, 32, 2019

    2019

  56. [64]

    Algaedice: Policy gradient from ar- bitrary experience

    Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. Algaedice: Policy gradient from ar- bitrary experience. arXiv preprint arXiv:1912.02074, 2019

    1912 arXiv

  57. [65]

    Optimal medication dosing from suboptimal clinical ex- amples: A deep reinforcement learning approach

    Shamim Nemati, Mohammad M Ghassemi, and Gari D Clif- ford. Optimal medication dosing from suboptimal clinical ex- amples: A deep reinforcement learning approach. In 2016 38th annual international conference of the IEEE engineering in medicine and biology society (EMBC) , pages...

    2016

  58. [66]

    On sample-efficient of- fline reinforcement learning: Data diversity, posterior sampling and beyond

    Thanh Nguyen-Tang and Raman Arora. On sample-efficient of- fline reinforcement learning: Data diversity, posterior sampling and beyond. Advances in neural information processing sys- tems, 36, 2024. 20

    2024

  59. [67]

    On instance-dependent bounds for offline reinforcement learning with linear function approximation

    Thanh Nguyen-Tang, Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora. On instance-dependent bounds for offline reinforcement learning with linear function approximation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 9310–9318, 2023

    2023

  60. [68]

    Training language models to follow instructions with human feedback.Advances in neural information processing systems, 35:27730–27744, 2022

    Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agar- wal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback.Advances in neural information processing systems, 35:277...

    2022

  61. [69]

    Batched bandit problems

    Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit problems. The Annals of Statistics, 44(2):660 – 681, 2016

    2016

  62. [70]

    Approximate Dynamic Programming: Solv- ing the curses of dimensionality , volume 703

    Warren B Powell. Approximate Dynamic Programming: Solv- ing the curses of dimensionality , volume 703. John Wiley & Sons, 2007

    2007

  63. [71]

    Eligibility traces for off-policy policy evalua- tion

    Doina Precup. Eligibility traces for off-policy policy evalua- tion. Computer Science Department Faculty Publication Series, page 80, 2000

    2000

  64. [72]

    Markov decision processes

    Martin L Puterman. Markov decision processes. Handbooks in operations research and management science , 2:331–434, 1990

    1990

  65. [73]

    Near-optimal deployment effi- ciency in reward-free reinforcement learning with linear func- tion approximation

    Dan Qiao and Yu-Xiang Wang. Near-optimal deployment effi- ciency in reward-free reinforcement learning with linear func- tion approximation. In International Conference on Learning Representations, 2023

    2023

  66. [74]

    Sample- efficient reinforcement learning with loglog (t) switching cost

    Dan Qiao, Ming Yin, Ming Min, and Yu-Xiang Wang. Sample- efficient reinforcement learning with loglog (t) switching cost. In International Conference on Machine Learning , pages 18031–18061. PMLR, 2022

    2022

  67. [75]

    Logarithmic switch- ing cost in reinforcement learning beyond linear mdps

    Dan Qiao, Ming Yin, and Yu-Xiang Wang. Logarithmic switch- ing cost in reinforcement learning beyond linear mdps. ISIT- 2024, 2024

    2024

  68. [76]

    Bridging offline reinforcement learning and im- itation learning: A tale of pessimism

    Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and im- itation learning: A tale of pessimism. Advances in Neural In- formation Processing Systems, 34:11702–11716, 2021

    2021

  69. [77]

    Nearly horizon-free offline reinforcement learning

    Tongzheng Ren, Jialian Li, Bo Dai, Simon S Du, and Sujay Sanghavi. Nearly horizon-free offline reinforcement learning. Advances in neural information processing systems, 34:15621– 15634, 2021

    2021

  70. [78]

    Mastering the game of go with deep neural networks and tree search

    David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Lau- rent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484–489, 2016

    2016

  71. [79]

    Mastering the game of go without human knowledge

    David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354–359, 2017

    2017

  72. [80]

    Learning to summarize with human feed- back

    Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea V oss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to summarize with human feed- back. Advances in Neural Information Processing Systems, 33: 3008–3021, 2020

    2020

  73. [81]

    Reinforcement learn- ing: An introduction

    Richard S Sutton and Andrew G Barto. Reinforcement learn- ing: An introduction. MIT press, 2018

    2018

  74. [82]

    Finite time bounds for sampling based fitted value iteration

    Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference on Machine learning , pages 880–887, 2005

    2005

  75. [83]

    Semiparametric theory and missing data, volume 4

    Anastasios A Tsiatis. Semiparametric theory and missing data, volume 4. Springer, 2006

    2006

  76. [84]

    Minimax weight and q-function learning for off-policy evaluation

    Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for off-policy evaluation. In International Conference on Machine Learning , pages 9659–

  77. [85]

    Asymptotic statistics, volume 3

    Aad W Van der Vaart. Asymptotic statistics, volume 3. Cam- bridge university press, 2000

    2000

  78. [86]

    High-dimensional statistics: A non- asymptotic viewpoint, volume 48

    Martin J Wainwright. High-dimensional statistics: A non- asymptotic viewpoint, volume 48. Cambridge university press, 2019

    2019

  79. [87]

    Provably efficient reinforcement learning with linear function approxi- mation under adaptivity constraints

    Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learning with linear function approxi- mation under adaptivity constraints. Advances in Neural Infor- mation Processing Systems, 34:13524–13536, 2021

    2021

  80. [88]

    On gap-dependent bounds for offline reinforcement learning

    Xinqi Wang, Qiwen Cui, and Simon S Du. On gap-dependent bounds for offline reinforcement learning. Advances in Neural Information Processing Systems, 35:14865–14877, 2022

    2022

  81. [89]

    Opti- mal and adaptive off-policy evaluation in contextual bandits

    Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudık. Opti- mal and adaptive off-policy evaluation in contextual bandits. In International Conference on Machine Learning , pages 3589–

  82. [90]

    Behavior regularized offline reinforcement learning

    Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning. arXiv preprint arXiv:1911.11361, 2019

    1911 arXiv

  83. [91]

    On the optimality of batch policy optimization algorithms

    Chenjun Xiao, Yifan Wu, Jincheng Mei, Bo Dai, Tor Lattimore, Lihong Li, Csaba Szepesvari, and Dale Schuurmans. On the optimality of batch policy optimization algorithms. In Interna- tional Conference on Machine Learning , pages 11362–11371. PMLR, 2021

    2021

  84. [92]

    Q* approximation schemes for batch reinforcement learning: A theoretical comparison

    Tengyang Xie and Nan Jiang. Q* approximation schemes for batch reinforcement learning: A theoretical comparison. In Conference on Uncertainty in Artificial Intelligence , pages 550–559. PMLR, 2020

    2020

  85. [93]

    Towards optimal off-policy evaluation for reinforcement learning with marginal- ized importance sampling

    Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off-policy evaluation for reinforcement learning with marginal- ized importance sampling. Advances in Neural Information Processing Systems, 32, 2019

    2019

  86. [94]

    Bellman-consistent pessimism for offline rein- forcement learning

    Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline rein- forcement learning. Advances in neural information processing systems, 34:6683–6694, 2021

    2021

  87. [95]

    Policy finetuning: Bridging sample-efficient offline and online reinforcement learning

    Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34:27395–27407, 2021

    2021

  88. [96]

    Nearly minimax optimal offline rein- forcement learning with linear function approximation: Single- agent mdp and markov game.arXiv preprint arXiv:2205.15512, 2022

    Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. Nearly minimax optimal offline rein- forcement learning with linear function approximation: Single- agent mdp and markov game.arXiv preprint arXiv:2205.15512, 2022

    2022 arXiv

  89. [97]

    Asymptotically efficient off- policy evaluation for tabular reinforcement learning

    Ming Yin and Yu-Xiang Wang. Asymptotically efficient off- policy evaluation for tabular reinforcement learning. InInterna- tional Conference on Artificial Intelligence and Statistics, pages 3948–3958. PMLR, 2020

    2020

  90. [98]

    Towards instance-optimal of- fline reinforcement learning with pessimism

    Ming Yin and Yu-Xiang Wang. Towards instance-optimal of- fline reinforcement learning with pessimism. Advances in neu- ral information processing systems, 34:4065–4078, 2021

    2021

  91. [99]

    Near-optimal prov- able uniform convergence in offline policy evaluation for rein- forcement learning

    Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal prov- able uniform convergence in offline policy evaluation for rein- forcement learning. In International Conference on Artificial Intelligence and Statistics, pages 1567–1575. PMLR, 2021

    2021

  92. [100]

    Near-optimal of- fline reinforcement learning via double variance reduction

    Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal of- fline reinforcement learning via double variance reduction. Ad- vances in neural information processing systems , 34:7677– 7688, 2021. STATISTICAL COMPLEXITY FOR OFFLINE AND LOW-ADAPTIVE RL 21

    2021

  93. [101]

    Near-optimal offline reinforcement learning with linear rep- resentation: Leveraging variance information with pessimism

    Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. Near-optimal offline reinforcement learning with linear rep- resentation: Leveraging variance information with pessimism. arXiv preprint arXiv:2203.05804, 2022

    2022 arXiv

  94. [102]

    Offline rein- forcement learning with differentiable function approximation is provably efficient

    Ming Yin, Mengdi Wang, and Yu-Xiang Wang. Offline rein- forcement learning with differentiable function approximation is provably efficient. International Conference on Learning Representations, 2023

    2023

  95. [103]

    Tighter problem- dependent regret bounds in reinforcement learning without do- main knowledge using value function bounds

    Andrea Zanette and Emma Brunskill. Tighter problem- dependent regret bounds in reinforcement learning without do- main knowledge using value function bounds. In International Conference on Machine Learning , pages 7304–7312. PMLR, 2019

    2019

  96. [104]

    Off-policy fitted q-evaluation with differentiable func- tion approximators: Z-estimation and inference theory

    Ruiqi Zhang, Xuezhou Zhang, Chengzhuo Ni, and Mengdi Wang. Off-policy fitted q-evaluation with differentiable func- tion approximators: Z-estimation and inference theory. In In- ternational Conference on Machine Learning , pages 26713– 26749. PMLR, 2022

    2022

  97. [105]

    Gen- dice: Generalized offline estimation of stationary values

    Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. Gen- dice: Generalized offline estimation of stationary values. In In- ternational Conference on Learning Representations, 2020

    2020

  98. [106]

    Near-optimal regret bounds for multi-batch reinforcement learning

    Zihan Zhang, Yuhang Jiang, Yuan Zhou, and Xiangyang Ji. Near-optimal regret bounds for multi-batch reinforcement learning. Advances in Neural Information Processing Systems, 35:24586–24596, 2022

    2022

  99. [107]

    A nearly optimal and low-switching algorithm for reinforcement learning with general function approximation

    Heyang Zhao, Jiafan He, and Quanquan Gu. A nearly optimal and low-switching algorithm for reinforcement learning with general function approximation. Advances in Neural Informa- tion Processing Systems, 2024

    2024

  100. [108]

    Deep reinforcement learning for page- wise recommendations

    Xiangyu Zhao, Long Xia, Liang Zhang, Zhuoye Ding, Dawei Yin, and Jiliang Tang. Deep reinforcement learning for page- wise recommendations. In Proceedings of the 12th ACM con- ference on recommender systems, pages 95–103, 2018

    2018

  101. [109]

    Nearly minimax optimal reinforcement learning for linear mixture markov decision processes

    Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning The- ory, pages 4532–4576. PMLR, 2021

    2021

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.