Pith. sign in

REVIEW 9 minor 1 cited by

Statistical and Algorithmic Foundations of Reinforcement Learning

T0 review · 0 major / 9 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read This tutorial argues that reinforcement learning's sample complexity is now essentially settled across major settings: model-based algorithms achieve minimax optimality with a simulator, online, offline, and under robustness, while…

desk verdict A solid, accurate tutorial that synthesizes the known minimax sample-complexity results for tabular RL; the only new-looking piece (VPO) is properly attributed and its key assumption is a gauge choice the authors should have explained. read the letter →

arxiv 2507.14444 v1 pith:HZWMJ46K submitted 2025-07-19 stat.ML cs.AIcs.LGmath.OCmath.STstat.TH

Yuejie Chi , Yuxin Chen , Yuting Wei This is my paper
classification stat.MLcs.AIcs.LGmath.OCmath.STstat.TH MSC 68Q3290C4062C20
keywords reinforcementlearningsamplecomplexityminimaxoptimalityMarkovdecisionprocessesmodel-basedalgorithmsQ-learningofflinefromhumanfeedback
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 tutorial surveys the statistical and algorithmic foundations of reinforcement learning, aiming to pin down, for each major RL setting, the minimal number of samples needed to learn a near-optimal policy and which algorithms achieve that minimum. Its central claim is that model-based algorithms that first estimate the transition kernel and then plan are minimax optimal in the generative-model, online, offline, and robust settings: the sample size $SA/((1-\gamma)^3\varepsilon^2)$ suffices for a simulator, and matching lower bounds show no algorithm can do better. Along the way the paper shows that vanilla Q-learning is suboptimal by a factor of $1/(1-\gamma)$, that pessimism makes offline RL sample-optimal under single-policy concentrability, and that value-incentivized preference optimization can remove explicit uncertainty quantification from RLHF. A sympathetic reader would care because these results convert a field of heuristic algorithms into a set of provable benchmarks, telling practitioners exactly when a method is leaving samples on the table.

What carries the argument

The recurring machinery is the Bellman optimality operator and its contraction property, together with statistically calibrated variants: optimistic Bellman operators equipped with Bernstein-style bonuses for online exploration, pessimistic Bellman operators that subtract lower-confidence-bound penalties for offline learning, and the robust Bellman operator with a strong-duality reduction for uncertainty sets. These operators are combined with non-asymptotic concentration inequalities and minimax lower bounds that hinge on the effective horizon $1/(1-\gamma)$. In the RLHF section, the load-bearing identity is the closed-form relation between the KL-regularized optimal policy and the reward function, $r(x,y)=\beta(\log\pi_r(y|x)-\log\pi_{\mathrm{ref}}(y|x)+\log Z(r,x))$, which converts reward estimation into direct policy optimization and, under the calibration assumption, expresses the optimal value $J^\star(r)$ as $-\beta\,\mathbb{E}_{x\sim\rho,y\sim\pi_{\mathrm{cal}}(\cdot|x)}[\log\pi_r(y|x)-\log\pi_{\mathrm{ref}}(y|x)]$.

What would settle it

Generate a preference dataset from a Bradley-Terry model whose true reward is not calibrated under any given fixed distribution, run the VPO objective (90) with that calibration distribution, and compare the returned policy to the one that maximizes the KL-regularized value of the true reward; a systematic difference shows the calibration assumption is load-bearing.

Watch

Extended reading notes

Core claim

The paper's organizing discovery is that the sample complexity of tabular reinforcement learning is now essentially settled, up to logarithmic factors, across several canonical settings. With a generative model, the perturbed model-based algorithm (Algorithm 2) returns an $\varepsilon$-optimal policy whenever the total number of samples exceeds the order of $SA/((1-\gamma)^3\varepsilon^2)$ (Theorem 1), and Theorem 2 shows no algorithm can succeed with fewer samples, establishing full-range minimax optimality. Synchronous Q-learning, by contrast, requires $\tilde{O}(SA/((1-\gamma)^4\varepsilon^2))$ samples with a matching algorithm-dependent lower bound (Theorems 3 and 4), exposing a gap of $1/(1-\gamma)$ caused by over-estimation bias. In online episodic RL, the MVP algorithm attains regret $\tilde{O}(\sqrt{SAH^3K})$ with no burn-in cost (Theorem 6). In offline RL, value iteration with pessimistic Bernstein penalties (VI-LCB) achieves $\tilde{O}(SC^\star/((1-\gamma)^3\varepsilon^2))$ samples where $C^\star$ is the single-policy concentrability coefficient, matching the minimax lower bound (Theorems 7 and 8). The survey further presents results for policy optimization (global convergence of projected PG, exponential-time hardness of softmax PG, linear convergence of entropy-regularized NPG), distributionally robust MDPs where TV uncertainty does not increase sample complexity (Theorem 14), and RLHF where value-incentivized preference optimization attains optimal regret without explicit uncertainty estimation.

Load-bearing premise

The tutorial's VPO method assumes the true reward satisfies a zero-mean calibration condition under a fixed distribution, but it never explains how to construct or verify that distribution; if the condition fails, the objective loses the meaning the proof relies on.

Editorial extensions

If this is right

  • Model-based algorithms become the default statistical benchmark: in tabular environments with a simulator, any algorithm with sample complexity worse than $SA/((1-\gamma)^3\varepsilon^2)$ is provably leaving samples on the table.
  • Plain Q-learning's suboptimality is intrinsic, not an artifact of analysis, so practitioners seeking minimax efficiency should adopt variance-reduced or perturbed variants.
  • Offline RL is feasible even when the transition model cannot be estimated uniformly, as long as the data covers the optimal policy's reachable state-action pairs, quantified by the single-policy concentrability coefficient.
  • Robustness under total-variation uncertainty is essentially free in terms of sample complexity, so worst-case planning can be added to a nominal simulator at little statistical cost.
  • In RLHF, reward calibration plus a value-incentivized regularizer yields optimal online and offline rates without explicit uncertainty quantification, simplifying alignment pipelines.

Reading between the lines

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

  • The tutorial's results suggest that estimation-then-planning is not just a heuristic: in tabular MDPs, statistical optimality and model-based plug-in estimation coincide, and this may carry over to hybrid settings that combine offline and online data.
  • The VPO analysis rests on the calibration Assumption 1, but the paper does not say how a practitioner should choose or validate $\pi_{\mathrm{cal}}$; if the true reward fails the zero-mean condition, the equivalence in equation (89) breaks, so the practical scope of VPO depends on this unaddressed design choice.
  • One could test the framework's reach by extending the sample-complexity scalings to function approximation: the results imply that effective horizon and coverage, not ambient dimensionality, should govern sample requirements in well-structured MDPs.
  • The minimax lower bounds in the survey are information-theoretic, meaning any future algorithm, including deep RL, must obey the same sample limits unless it exploits additional structure beyond the tabular model.
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

0 major / 9 minor

Summary. This manuscript is a tutorial on the statistical and algorithmic foundations of reinforcement learning. It covers five RL settings—generative model (simulator) access, online episodic RL, offline RL, distributionally robust RL, and RL with human feedback—and three main algorithmic families: model-based methods, value-based methods (Q-learning, TD learning), and policy optimization (policy gradient, natural policy gradient, entropy-regularized methods). For each setting, the paper surveys non-asymptotic sample-complexity guarantees, minimax lower bounds, and algorithm-dependent lower bounds, with particular emphasis on results that are optimal up to logarithmic factors. The exposition is organized around key principles such as optimism in the face of uncertainty, pessimism in offline settings, variance reduction, and reward calibration. Theorems are stated with citations to the published literature, and several algorithms are presented in pseudocode.

Significance. If the surveyed results are correct, this is a valuable synthesis that will be useful for graduate students and researchers entering RL theory. The paper's strengths are its coherent presentation of minimax sample-complexity results across multiple RL paradigms, its clear statements of lower bounds that benchmark the upper bounds, and its discussion of practical considerations (e.g., the gap between theory and practice in Section 9). Many of the presented bounds come from the authors' own recent work, but they are published in peer-reviewed venues and are benchmarked against independent lower bounds (e.g., Azar et al. [6], Jin et al. [46], Domingues et al. [33]). The tutorial also provides a helpful perspective on the role of distributional robustness and RLHF in modern RL. The main limitation is that the paper is a survey rather than a new contribution, and the reliance on the authors' own work could be balanced with more external perspectives; however, this does not affect the technical soundness.

minor comments (9)
  1. [Section 2.1] The word "staionary" in the first paragraph of Section 2.1 should be corrected to "stationary".
  2. [Section 3.3.2] The learning-rate condition in Eq (29a) uses log^3 T in the denominators, but the following paragraph describes the two learning-rate schemes using log^2 T; these should be reconciled to avoid confusion.
  3. [Section 3.3.3] The sentence about the over-estimation bias is garbled; it should read that Q-learning suffers from over-estimation bias when replacing the expectation inside the max by its empirical estimate.
  4. [Section 4.3] The inline "[burn-in cost of Azar et al. [7]]" in the sentence about UCBVI's regret bound is an editorial artifact and should be removed, with the condition K ≳ S^3 A H^3 stated as a normal mathematical condition.
  5. [Section 5.3, Eq (49)] The Bernstein-style penalty is misformatted; the variance term should be inside the square root, and the second term should read (2 c_b log(N/((1−γ)δ)))/((1−γ) N(s,a)).
  6. [Section 6.1, Theorem 11] The lower-bound statement "at least c1 η S2 c2/(1−γ)" is garbled by the typesetting; it should be formatted as a power of S (e.g., c_1 η S^{c_2/(1−γ)}) so the exponential dependence on the horizon is clear.
  7. [Section 7.2, Theorem 14] The notation for the sample size is inconsistent: N is introduced as the number of samples per state-action pair, but the theorem states the total-sample condition as "N SA ≥ ..."; please clarify by defining the total sample count explicitly or by writing the per-pair condition N ≥ ... .
  8. [Section 8.2, Eqs (87)–(90)] The derivation of Eq (89) from Assumption 1 is correct, but the explanatory sentence ("where the second step follows because the bracketed term is independent of y...") is unclear and should be rewritten. It would also be helpful to state explicitly that Assumption 1 is a gauge-fixing normalization: recentering r0(x,y) by subtracting E_{πcal}[r0(x,·)] yields a reward in R with identical preference probabilities and identical KL-regularized optimal policy, so the assumption is not restrictive in practice.
  9. [Title] The title of the PDF header contains a stray space ("F oundations"), which should be removed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the tutorial reports externally verifiable published results, and the VPO calibration condition is a gauge-fixing choice rather than a premise that smuggles in the conclusion.

full rationale

This paper is a tutorial and survey, not an original derivation of new theorems. Its central claim is that the surveyed sample-complexity results constitute the current state of the art, and that claim is supported by citations to peer-reviewed proofs, many of which are benchmarked against independent minimax lower bounds (e.g., Theorem 2 from Azar et al. [6], the online lower bound from Domingues et al. [33], and the Q-learning lower bound in Theorem 4 from Li et al. [67]). The authors do cite their own prior work heavily (Theorems 1, 3, 4, 5, 7, 8, 11, 13, 14, and the VPO section), but the cited results are not defined in terms of the tutorial's assertions; they are externally published theorems with stated assumptions that do not include the tutorial's conclusions. Under the rule that self-citation is not itself circularity, these citations do not raise the score. The only in-paper derivation that could look like a circular step is the VPO identity (89), which expresses J*(r) under Assumption 1 (Eq. 87). On inspection, Assumption 1 is not a restrictive empirical premise: the paper explicitly notes that the Bradley-Terry reward is identifiable only up to a prompt-dependent shift, and the calibration condition E_{x~rho, y~pi_cal}[r(x,y)] = 0 selects one representative from each equivalence class. For any reward r0, the recentered reward r0(x,y) - E_{y~pi_cal(.|x)}[r0(x,.)] satisfies Assumption 1, leaves pairwise preference probabilities unchanged (prompt-dependent shifts cancel in differences), and leaves the KL-regularized optimal policy pi_r unchanged (a y-independent shift cancels in the softmax normalization). Thus the derivation of (89) uses the calibration condition as a gauge fix, not as an input that already contains the conclusion. The regularized objective (90) is then algebraically equivalent to DPO with an extra KL-type term; this is a rewriting, not a circular reduction. No fitted parameter is relabeled as a prediction, and no uniqueness or optimality assertion is imported solely from the authors' prior work without independent support. The survey is self-contained against external benchmarks, and its most fragile-looking assumption is a presentation gap rather than a circularity defect.

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

The tutorial does not introduce new free parameters or entities; the constants in the bounds (c0, c1, cb, etc.) are universal constants, not fitted to data. The listed axioms are standard modeling assumptions from the cited literature that the survey imports.

assumptions (7)
  • standard math Bellman optimality operator is a γ-contraction in the sup norm.
    Used throughout Sections 2-7 as the basis for value iteration and its convergent variants.
  • standard math Existence of a deterministic optimal policy for discounted MDPs.
    Invoked in Section 2.1 (eq. 6) and in the robust MDP section (Section 7.1, eq. 66).
  • domain assumption Generative model returns independent samples from the true transition kernel.
    Central to Section 3 and Section 7.2, enabling direct estimation of P(s'|s,a).
  • domain assumption Single-policy concentrability coefficient C* is finite.
    The offline RL results in Section 5 assume C* = max d⋆(s,a)/d_b(s,a) is bounded; the guarantee scales with C*.
  • domain assumption Uncertainty set in RMDPs is (s,a)-rectangular.
    Section 7.1 defines U_ρ^σ(P0) as a product over state-action pairs, a necessary tractability condition for the robust Bellman equation.
  • domain assumption Calibration assumption for the true reward (Assumption 1).
    Section 8.2, eq. (87): requires E_{x~ρ,y~πcal}[r⋆(x,y)] = 0, which is essential for the equivalence (89).
  • domain assumption Bradley-Terry preference model.
    Section 8.1, eq. (78) assumes pairwise preferences follow the Bradley-Terry model with a logistic link.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Statistical and Algorithmic Foundations of Reinforcement Learning." pith.science (2026). https://pith.science/paper/HZWMJ46K

@misc{pith2026250714444,
  author       = {Pith},
  title        = {Pith review of: Statistical and Algorithmic Foundations of Reinforcement Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HZWMJ46K}},
  note         = {Machine review of arXiv:2507.14444}
}
read the original abstract

As a paradigm for sequential decision making in unknown environments, reinforcement learning (RL) has received a flurry of attention in recent years. However, the explosion of model complexity in emerging applications and the presence of nonconvexity exacerbate the challenge of achieving efficient RL in sample-starved situations, where data collection is expensive, time-consuming, or even high-stakes (e.g., in clinical trials, autonomous systems, and online advertising). How to understand and enhance the sample and computational efficacies of RL algorithms is thus of great interest. In this tutorial, we aim to introduce several important algorithmic and theoretical developments in RL, highlighting the connections between new ideas and classical topics. Employing Markov Decision Processes as the central mathematical model, we cover several distinctive RL scenarios (i.e., RL with a simulator, online RL, offline RL, robust RL, and RL with human feedback), and present several mainstream RL approaches (i.e., model-based approach, value-based approach, and policy optimization). Our discussions gravitate around the issues of sample complexity, computational efficiency, as well as algorithm-dependent and information-theoretic lower bounds from a non-asymptotic viewpoint.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalization

    stat.ML 2026-04 unverdicted novelty 6.0 of 10

    Q-learning with PD2Z/LD2Z step sizes admits sharp non-asymptotic bounds, a tail Polyak–Ruppert CLT, and a time-uniform Gaussian approximation, establishing a best-of-both-worlds rate-and-bias tradeoff.

Reference graph

Works this paper leans on

162 extracted references · 69 canonical work pages · cited by 1 Pith paper

  1. [22]

    The Thirteenth International Conference on Learning Representations

    Cen S, Mei J, Goshvadi K, Dai H, Yang T, Yang S, Schuurmans D, Chi Y, Dai B (2025) Value-incentivized preference optimization: A unified approach to online and offline RLHF. The Thirteenth International Conference on Learning Representations

    2025

  2. [6]

    Azar MG, Munos R, Kappen HJ (2013) Minimax PAC bounds on the sample complex- ity of reinforcement learning with a generative model.Machine learning 91(3):325–349

    2013

  3. [46]

    Jin C, Allen-Zhu Z, Bubeck S, Jordan MI (2018) Is Q-learning provably efficient? Advances in Neural Information Processing Systems , 4863–4873

    2018

  4. [33]

    Algorithmic Learning Theory , 578–598 (PMLR)

    Domingues OD, M´ enard P, Kaufmann E, Valko M (2021) Episodic reinforcement learn- ing in finite MDPs: Minimax lower bounds revisited. Algorithmic Learning Theory , 578–598 (PMLR)

    2021

  5. [1]

    CS Dept., UW Seattle, Seattle, WA, USA, Tech

    Agarwal A, Jiang N, Kakade SM, Sun W (2019) Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep 32:96

    2019

  6. [2]

    Advances in neural information processing systems 33:20095–20107

    Agarwal A, Kakade S, Krishnamurthy A, Sun W (2020) Flambe: Structural complex- ity and representation learning of low rank MDPs. Advances in neural information processing systems 33:20095–20107

    2020

  7. [3]

    Agarwal A, Kakade S, Yang LF (2020) Model-based reinforcement learning with a generative model is minimax optimal.Conference on Learning Theory, 67–83 (PMLR). 32

    2020

  8. [4]

    Journal of Machine Learning Research 22(98):1–76

    Agarwal A, Kakade SM, Lee JD, Mahajan G (2021) On the theory of policy gradi- ent methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research 22(98):1–76

    2021

Show all 162 references
  1. [5]

    Advances in neural information processing systems 19

    Auer P, Ortner R (2006) Logarithmic online regret bounds for undiscounted reinforce- ment learning. Advances in neural information processing systems 19

    2006

  2. [7]

    International Conference on Machine Learning , 263–272 (PMLR)

    Azar MG, Osband I, Munos R (2017) Minimax regret bounds for reinforcement learn- ing. International Conference on Machine Learning , 263–272 (PMLR)

    2017

  3. [8]

    Systems & control letters 61(12):1203–1208

    Beck CL, Srikant R (2012) Error bounds for constant step-size Q-learning. Systems & control letters 61(12):1203–1208

    2012

  4. [9]

    Proceedings of the National Academy of Sciences of the United States of America 38(8):716

    Bellman R (1952) On the theory of dynamic programming. Proceedings of the National Academy of Sciences of the United States of America 38(8):716

    1952

  5. [10]

    Bertsekas DP (2017) Dynamic programming and optimal control (4th edition) (Athena Scientific)

    2017

  6. [11]

    Mathemat- ical Programming 167(2):235–292

    Bertsimas D, Gupta V, Kallus N (2018) Data-driven robust optimization. Mathemat- ical Programming 167(2):235–292

    2018

  7. [12]

    Management Science 65(2):604–618

    Bertsimas D, Sim M, Zhang M (2019) Adaptive distributionally robust optimization. Management Science 65(2):604–618

    2019

  8. [13]

    International Conference on Artificial Intelligence and Statistics , 2386– 2394 (PMLR)

    Bhandari J, Russo D (2021) On the linear convergence of policy gradient methods for finite MDPs. International Conference on Artificial Intelligence and Statistics , 2386– 2394 (PMLR)

    2021

  9. [14]

    Operations Research 72(5):1906–1927

    Bhandari J, Russo D (2024) Global optimality guarantees for policy gradient methods. Operations Research 72(5):1906–1927

    2024

  10. [15]

    Operations Research 69(3):950–973

    Bhandari J, Russo D, Singal R (2021) A finite time analysis of temporal difference learning with linear function approximation. Operations Research 69(3):950–973

    2021

  11. [16]

    Mathematics of Operations Research 44(2):565–600

    Blanchet J, Murthy K (2019) Quantifying distributional model risk via optimal trans- port. Mathematics of Operations Research 44(2):565–600

    2019

  12. [17]

    International Conference on Machine Learning , 1056–1066 (PMLR)

    Bourel H, Maillard O, Talebi MS (2020) Tightening exploration in upper confidence reinforcement learning. International Conference on Machine Learning , 1056–1066 (PMLR)

    2020

  13. [18]

    the method of paired comparisons

    Bradley RA, Terry ME (1952) Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika 39(3/4):324–345

    1952

  14. [19]

    2022 IEEE 61st Conference on Decision and Control (CDC) , 2833–2838 (IEEE)

    Cen S, Chen F, Chi Y (2022) Independent natural policy gradient methods for poten- tial games: Finite-time global convergence with entropy regularization. 2022 IEEE 61st Conference on Decision and Control (CDC) , 2833–2838 (IEEE)

    2022

  15. [20]

    Operations Research 70(4):2563– 2578

    Cen S, Cheng C, Chen Y, Wei Y, Chi Y (2022) Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research 70(4):2563– 2578

    2022

  16. [21]

    The Eleventh International Conference on Learning Representations

    Cen S, Chi Y, Du SS, Xiao L (2023) Faster last-iterate convergence of policy optimiza- tion in zero-sum Markov games. The Eleventh International Conference on Learning Representations

    2023

  17. [23]

    Journal of Machine Learning Research 25(4):1–48

    Cen S, Wei Y, Chi Y (2024) Fast policy extragradient methods for competitive games with entropy regularization. Journal of Machine Learning Research 25(4):1–48

    2024

  18. [24]

    Advances in neural information processing systems 30

    Cesa-Bianchi N, Gentile C, Lugosi G, Neu G (2017) Boltzmann exploration done right. Advances in neural information processing systems 30

    2017

  19. [25]

    Cesa-Bianchi N, Lugosi G (2006) Prediction, learning, and games (Cambridge univer- sity press). 33

    2006

  20. [26]

    The Annals of Statistics 53(1):426–456

    Chen F, Mei S, Bai Y (2025) Unified algorithms for RL with decision-estimation coefficients: PAC, reward-free, preference-based learning and beyond. The Annals of Statistics 53(1):426–456

    2025

  21. [27]

    International Conference on Machine Learning , 1042–1051 (PMLR)

    Chen J, Jiang N (2019) Information-theoretic considerations in batch reinforcement learning. International Conference on Machine Learning , 1042–1051 (PMLR)

    2019

  22. [28]

    arXiv preprint arXiv:2002.00874

    Chen Z, Maguluri ST, Shakkottai S, Shanmugam K (2020) Finite-sample anal- ysis of stochastic approximation using smooth convex envelopes. arXiv preprint arXiv:2002.00874

    2020 arXiv

  23. [29]

    arXiv preprint arXiv:2102.01567

    Chen Z, Maguluri ST, Shakkottai S, Shanmugam K (2021) A Lyapunov theory for finite-sample guarantees of asynchronous Q-learning and TD-learning variants. arXiv preprint arXiv:2102.01567

    2021 arXiv

  24. [30]

    arXiv preprint arXiv:2502.14208

    Chen Z, Zhang S, Zhang Z, Haque SU, Maguluri ST (2025) A non-asymptotic theory of seminorm lyapunov stability: From deterministic to stochastic iterative algorithms. arXiv preprint arXiv:2502.14208

    2025 arXiv

  25. [31]

    Advances in Neural Information Processing Systems 37:1750–1810

    Clavier P, Shi L, Le Pennec E, Mazumdar E, Wierman A, Geist M (2024) Near- optimal distributionally robust reinforcement learning with generallp norms. Advances in Neural Information Processing Systems 37:1750–1810

    2024

  26. [32]

    Thirty-seventh Conference on Neural Informa- tion Processing Systems

    Ding W, Shi L, Chi Y, Zhao D (2023) Seeing is not believing: Robust reinforcement learning against spurious correlation. Thirty-seventh Conference on Neural Informa- tion Processing Systems

    2023

  27. [34]

    arXiv preprint arXiv:1901.09311

    Dong K, Wang Y, Chen X, Wang L (2019) Q-learning with UCB exploration is sample efficient for infinite-horizon MDP. arXiv preprint arXiv:1901.09311

    2019 arXiv

  28. [35]

    arXiv preprint arXiv:2103.10897

    Du SS, Kakade SM, Lee JD, Lovett S, Mahajan G, Sun W, Wang R (2021) Bilin- ear classes: A structural framework for provable generalization in rl. arXiv preprint arXiv:2103.10897

    2021 arXiv

  29. [36]

    The Annals of Statistics 49(3):1378–1406

    Duchi JC, Namkoong H (2021) Learning models with uniform performance via distri- butionally robust optimization. The Annals of Statistics 49(3):1378–1406

    2021

  30. [37]

    Journal of machine learning Research 5(Dec):1–25

    Even-Dar E, Mansour Y (2003) Learning rates for Q-learning. Journal of machine learning Research 5(Dec):1–25

    2003

  31. [38]

    International conference on machine learning, 1467–1476 (PMLR)

    Fazel M, Ge R, Kakade S, Mesbahi M (2018) Global convergence of policy gradi- ent methods for the linear quadratic regulator. International conference on machine learning, 1467–1476 (PMLR)

    2018

  32. [39]

    arXiv preprint arXiv:2112.13487

    Foster DJ, Kakade SM, Qian J, Rakhlin A (2021) The statistical complexity of inter- active decision making. arXiv preprint arXiv:2112.13487

    2021 arXiv

  33. [40]

    Operations Research 71(6):2291–2306

    Gao R (2023) Finite-sample guarantees for Wasserstein distributionally robust opti- mization: Breaking the curse of dimensionality. Operations Research 71(6):2291–2306

    2023

  34. [41]

    Advances in neural information processing sys- tems 23:2613–2621

    Hasselt H (2010) Double Q-learning. Advances in neural information processing sys- tems 23:2613–2621

    2010

  35. [42]

    International Conference on Machine Learning , 12790–12822 (PMLR)

    He J, Zhao H, Zhou D, Gu Q (2023) Nearly minimax optimal reinforcement learning for linear markov decision processes. International Conference on Machine Learning , 12790–12822 (PMLR)

    2023

  36. [43]

    Mathematics of Operations Research 30(2):257–280

    Iyengar GN (2005) Robust dynamic programming. Mathematics of Operations Research 30(2):257–280

    2005

  37. [44]

    Journal of Machine Learning Research 11:1563–1600

    Jaksch T, Ortner R, Auer P (2010) Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research 11:1563–1600

    2010

  38. [45]

    Advances in neural information processing systems 36:80674–80689

    Ji X, Li G (2023) Regret-optimal model-free reinforcement learning for discounted mdps with short burn-in time. Advances in neural information processing systems 36:80674–80689. 34

    2023

  39. [47]

    International Conference on Machine Learning , 4870–4879 (PMLR)

    Jin C, Krishnamurthy A, Simchowitz M, Yu T (2020) Reward-free exploration for reinforcement learning. International Conference on Machine Learning , 4870–4879 (PMLR)

    2020

  40. [48]

    Advances in neural information processing systems 34:13406–13418

    Jin C, Liu Q, Miryoosefi S (2021) Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems 34:13406–13418

    2021

  41. [49]

    Conference on Learning Theory , 2137–2143 (PMLR)

    Jin C, Yang Z, Wang Z, Jordan MI (2020) Provably efficient reinforcement learn- ing with linear function approximation. Conference on Learning Theory , 2137–2143 (PMLR)

    2020

  42. [50]

    arXiv preprint arXiv:2405.12952

    Jin Y, Karmarkar I, Sidford A, Wang J (2024) Truncated variance reduced value iteration. arXiv preprint arXiv:2405.12952

    2024 arXiv

  43. [51]

    arXiv preprint arXiv:2212.09900

    Jin Y, Ren Z, Yang Z, Wang Z (2022) Policy learning” without” overlap: Pessimism and generalized empirical Bernstein’s inequality. arXiv preprint arXiv:2212.09900

    2022 arXiv

  44. [52]

    International Conference on Machine Learning , 5055–5064 (PMLR)

    Jin Y, Sidford A (2021) Towards tight bounds on the sample complexity of average- reward mdps. International Conference on Machine Learning , 5055–5064 (PMLR)

    2021

  45. [53]

    Jin Y, Yang Z, Wang Z (2021) Is pessimism provably efficient for offline RL? Interna- tional Conference on Machine Learning , 5084–5096

    2021

  46. [54]

    Advances in neural information processing systems , 315–323

    Johnson R, Zhang T (2013) Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems , 315–323

    2013

  47. [55]

    Kakade S (2003) On the sample complexity of reinforcement learning . Ph.D. thesis, University of London

    2003

  48. [56]

    Advances in neural information process- ing systems , 1531–1538

    Kakade SM (2002) A natural policy gradient. Advances in neural information process- ing systems , 1531–1538

    2002

  49. [57]

    Advances in neural information processing systems , 996–1002

    Kearns MJ, Singh SP (1999) Finite-sample convergence rates for Q-learning and indi- rect algorithms. Advances in neural information processing systems , 996–1002

    1999

  50. [58]

    SIAM Journal on Math- ematics of Data Science 3(4):1013–1040

    Khamaru K, Pananjady A, Ruan F, Wainwright MJ, Jordan MI (2021) Is temporal difference learning optimal? an instance-dependent analysis. SIAM Journal on Math- ematics of Data Science 3(4):1013–1040

    2021

  51. [59]

    Khodadadian S, Jhunjhunwala PR, Varma SM, Maguluri ST (2021) On the linear con- vergence of natural policy gradient algorithm.2021 60th IEEE Conference on Decision and Control (CDC) , 3794–3799 (IEEE)

    2021

  52. [60]

    IEEE Transactions on Automatic Control 27(1):137–146

    Kumar P, Becker A (1982) A new family of optimal adaptive controllers for markov chains. IEEE Transactions on Automatic Control 27(1):137–146

    1982

  53. [61]

    Advances in applied mathematics 6(1):4–22

    Lai TL, Robbins H (1985) Asymptotically efficient adaptive allocation rules. Advances in applied mathematics 6(1):4–22

    1985

  54. [62]

    Lan G (2023) Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes.Mathematical programming 198(1):1059–1106

    2023

  55. [63]

    Reinforcement learning, 45–73 (Springer)

    Lange S, Gabel T, Riedmiller M (2012) Batch reinforcement learning. Reinforcement learning, 45–73 (Springer)

    2012

  56. [64]

    International Con- ference on Algorithmic Learning Theory , 320–334 (Springer)

    Lattimore T, Hutter M (2012) PAC bounds for discounted MDPs. International Con- ference on Algorithmic Learning Theory , 320–334 (Springer)

    2012

  57. [65]

    Lattimore T, Szepesv´ ari C (2020)Bandit algorithms (Cambridge University Press)

    2020

  58. [66]

    arXiv preprint arXiv:2005.01643

    Levine S, Kumar A, Tucker G, Fu J (2020) Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643

    2020 arXiv

  59. [67]

    Operations Research 72(1):222–236

    Li G, Cai C, Chen Y, Wei Y, Chi Y (2024) Is Q-learning minimax optimal? a tight sample complexity analysis. Operations Research 72(1):222–236

    2024

  60. [68]

    Advances in Neural Information Processing Systems , volume 35, 15353–15367

    Li G, Chi Y, Wei Y, Chen Y (2022) Minimax-optimal multi-agent RL in Markov games with a generative model. Advances in Neural Information Processing Systems , volume 35, 15353–15367. 35

    2022

  61. [69]

    The Annals of Statistics 52(1):233–260

    Li G, Shi L, Chen Y, Chi Y, Wei Y (2024) Settling the sample complexity of model- based offline reinforcement learning. The Annals of Statistics 52(1):233–260

    2024

  62. [70]

    Advances in Neural Information Processing Systems 34

    Li G, Shi L, Chen Y, Gu Y, Chi Y (2021) Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems 34

    2021

  63. [71]

    Mathematical Programming 1–96

    Li G, Wei Y, Chi Y, Chen Y (2023) Softmax policy gradient methods can take expo- nential time to converge. Mathematical Programming 1–96

    2023

  64. [72]

    Operations Research 72(1):203–221

    Li G, Wei Y, Chi Y, Chen Y (2024) Breaking the sample size barrier in model-based reinforcement learning with a generative model. Operations Research 72(1):203–221

    2024

  65. [73]

    Advances in neural information processing systems 33:12861–12872

    Li G, Wei Y, Chi Y, Gu Y, Chen Y (2020) Breaking the sample size barrier in model- based reinforcement learning with a generative model. Advances in neural information processing systems 33:12861–12872

    2020

  66. [74]

    IEEE Transactions on Information Theory 68(1):448–473

    Li G, Wei Y, Chi Y, Gu Y, Chen Y (2021) Sample complexity of asynchronous q- learning: Sharper analysis and variance reduction. IEEE Transactions on Information Theory 68(1):448–473

    2021

  67. [75]

    The Thirty Seventh Annual Conference on Learning Theory , 3431–3436 (PMLR)

    Li G, Yan Y, Chen Y, Fan J (2024) Minimax-optimal reward-agnostic exploration in reinforcement learning. The Thirty Seventh Annual Conference on Learning Theory , 3431–3436 (PMLR)

    2024

  68. [76]

    Advances in Neural Information Processing Systems 36

    Li G, Zhan W, Lee JD, Chi Y, Chen Y (2024) Reward-agnostic fine-tuning: Provable statistical benefits of hybrid reinforcement learning. Advances in Neural Information Processing Systems 36

    2024

  69. [77]

    International Conference on Machine Learning , 6248–6258 (PMLR)

    Liu X, Hsieh PC, Hung YH, Bhattacharya A, Kumar P (2020) Exploration through reward biasing: Reward-biased maximum likelihood estimation for stochastic multi- armed bandits. International Conference on Machine Learning , 6248–6258 (PMLR)

    2020

  70. [78]

    Games and economic behavior 10(1):6–38

    McKelvey RD, Palfrey TR (1995) Quantal response equilibria for normal form games. Games and economic behavior 10(1):6–38

    1995

  71. [79]

    International Conference on Machine Learning , 6820–6829 (PMLR)

    Mei J, Xiao C, Szepesvari C, Schuurmans D (2020) On the global convergence rates of softmax policy gradient methods. International Conference on Machine Learning , 6820–6829 (PMLR)

    2020

  72. [80]

    Conference on Learning Theory, 2947–2997 (PMLR)

    Mou W, Li CJ, Wainwright MJ, Bartlett PL, Jordan MI (2020) On linear stochas- tic approximation: Fine-grained Polyak-Ruppert and non-asymptotic concentration. Conference on Learning Theory, 2947–2997 (PMLR)

    2020

  73. [81]

    Munos R (2007) Performance bounds in lp-norm for approximate value iteration.SIAM journal on control and optimization 46(2):541–561

    2007

  74. [82]

    Operations Research 53(5):780–798

    Nilim A, El Ghaoui L (2005) Robust control of Markov decision processes with uncer- tain transition matrices. Operations Research 53(5):780–798

    2005

  75. [83]

    (2022) Training language models to follow instructions with human feedback

    Ouyang L, Wu J, Jiang X, Almeida D, Wainwright C, Mishkin P, Zhang C, Agarwal S, Slama K, Ray A, et al. (2022) Training language models to follow instructions with human feedback. Advances in neural information processing systems 35:27730–27744

    2022

  76. [84]

    International Conference on Artificial Intelligence and Statistics, 9582–9602 (PMLR)

    Panaganti K, Kalathil D (2022) Sample complexity of robust reinforcement learn- ing with a generative model. International Conference on Artificial Intelligence and Statistics, 9582–9602 (PMLR)

    2022

  77. [85]

    IEEE Transactions on Information Theory 67(1):566–585

    Pananjady A, Wainwright MJ (2020) Instance-dependent ℓ∞-bounds for policy eval- uation in tabular reinforcement learning. IEEE Transactions on Information Theory 67(1):566–585

    2020

  78. [86]

    arXiv preprint arXiv:2203.01387

    Prudencio RF, Maximo MR, Colombini EL (2022) A survey on offline reinforcement learning: Taxonomy, review, and open problems. arXiv preprint arXiv:2203.01387

    2022 arXiv

  79. [87]

    Puterman ML (2014) Markov decision processes: discrete stochastic dynamic program- ming (John Wiley & Sons)

    2014

  80. [88]

    Conference on Learning Theory 3185–3205

    Qu G, Wierman A (2020) Finite-time analysis of asynchronous stochastic approxima- tion and Q-learning. Conference on Learning Theory 3185–3205. 36

    2020

  81. [89]

    Advances in Neural Information Processing Systems 36

    Rafailov R, Sharma A, Mitchell E, Manning CD, Ermon S, Finn C (2023) Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems 36

    2023

  82. [90]

    IEEE Transactions on Informa- tion Theory 68(12):8156–8196

    Rashidinejad P, Zhu B, Ma C, Jiao J, Russell S (2022) Bridging offline reinforcement learning and imitation learning: A tale of pessimism. IEEE Transactions on Informa- tion Theory 68(12):8156–8196

    2022

  83. [91]

    Proceedings of the 35th International Conference on Neural Information Pro- cessing Systems, 15621–15634

    Ren T, Li J, Dai B, Du SS, Sanghavi S (2021) Nearly horizon-free offline reinforcement learning. Proceedings of the 35th International Conference on Neural Information Pro- cessing Systems, 15621–15634

    2021

  84. [92]

    The Annals of Math- ematical Statistics 400–407

    Robbins H, Monro S (1951) A stochastic approximation method. The Annals of Math- ematical Statistics 400–407

    1951

  85. [93]

    The Thirty-eighth Annual Conference on Neural Information Processing Systems

    Salgia S, Chi Y (2024) The sample-communication complexity trade-off in federated Q-learning. The Thirty-eighth Annual Conference on Neural Information Processing Systems

    2024

  86. [94]

    The Thirty Seventh Annual Conference on Learning Theory , 4511–4547 (PMLR)

    Samsonov S, Tiapkin D, Naumov A, Moulines E (2024) Improved high-probability bounds for the temporal difference learning algorithm via exponential stability. The Thirty Seventh Annual Conference on Learning Theory , 4511–4547 (PMLR)

    2024

  87. [95]

    Shani L, Efroni Y, Mannor S (2020) Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps.Proceedings of the AAAI Conference on Artificial Intelligence , volume 34, 5668–5675

    2020

  88. [96]

    Journal of Machine Learning Research 25(200):1–91

    Shi L, Chi Y (2024) Distributionally robust model-based offline reinforcement learn- ing with near-optimal sample complexity. Journal of Machine Learning Research 25(200):1–91

    2024

  89. [97]

    International Conference on Machine Learning (PMLR)

    Shi L, Gai J, Mazumdar E, Chi Y, Wierman A (2025) Breaking the curse of mul- tiagency in robust multi-agent reinforcement learning. International Conference on Machine Learning (PMLR)

    2025

  90. [98]

    International Conference on Machine Learning 19967–20025

    Shi L, Li G, Wei Y, Chen Y, Chi Y (2022) Pessimistic Q-learning for offline rein- forcement learning: Towards optimal sample complexity. International Conference on Machine Learning 19967–20025

    2022

  91. [99]

    Advances in Neural Information Processing Systems 36

    Shi L, Li G, Wei Y, Chen Y, Geist M, Chi Y (2024) The curious price of distributional robustness in reinforcement learning with a generative model. Advances in Neural Information Processing Systems 36

    2024

  92. [100]

    International Confer- ence on Machine Learning , 44909–44959 (PMLR)

    Shi L, Mazumdar E, Chi Y, Wierman A (2024) Sample-efficient robust multi-agent reinforcement learning in the face of environmental uncertainty. International Confer- ence on Machine Learning , 44909–44959 (PMLR)

    2024

  93. [101]

    Advances in Neural Information Processing Systems , 5186–5196

    Sidford A, Wang M, Wu X, Yang L, Ye Y (2018) Near-optimal time and sample complexities for solving Markov decision processes with a generative model. Advances in Neural Information Processing Systems , 5186–5196

    2018

  94. [102]

    Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , 770–787 (SIAM)

    Sidford A, Wang M, Wu X, Ye Y (2018) Variance reduced value iteration and faster algorithms for solving Markov decision processes. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , 770–787 (SIAM)

    2018

  95. [103]

    The Eleventh International Conference on Learning Representations

    Song Y, Zhou Y, Sekhari A, Bagnell D, Krishnamurthy A, Sun W (2023) Hybrid RL: Using both offline and online data can make RL efficient. The Eleventh International Conference on Learning Representations

    2023

  96. [104]

    Conference on Learning Theory, 2803–2830 (PMLR)

    Srikant R, Ying L (2019) Finite-time error bounds for linear stochastic approximation andtd learning. Conference on Learning Theory, 2803–2830 (PMLR)

    2019

  97. [105]

    Proceedings of the 23rd international conference on Machine learn- ing, 881–888

    Strehl AL, Li L, Wiewiora E, Langford J, Littman ML (2006) PAC model-free rein- forcement learning. Proceedings of the 23rd international conference on Machine learn- ing, 881–888

    2006

  98. [106]

    Machine learning 3(1):9–44

    Sutton RS (1988) Learning to predict by the methods of temporal differences. Machine learning 3(1):9–44

    1988

  99. [107]

    Sutton RS, Barto AG (2018) Reinforcement learning: An introduction (MIT press). 37

    2018

  100. [108]

    Advances in neural information processing systems 12

    Sutton RS, McAllester D, Singh S, Mansour Y (1999) Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems 12

    1999

  101. [109]

    Szepesv´ ari C (2010) Algorithms for reinforcement learning.Synthesis lectures on arti- ficial intelligence and machine learning 4(1):1–103

    2010

  102. [110]

    Proceedings of the 27th International Conference on Machine Learning (ICML-10) , 1031–1038

    Szita I, Szepesv´ ari C (2010) Model-based reinforcement learning with nearly tight exploration complexity bounds. Proceedings of the 27th International Conference on Machine Learning (ICML-10) , 1031–1038

    2010

  103. [111]

    The Thirty-eighth Annual Conference on Neural Information Processing Systems

    Tan K, Fan W, Wei Y (2024) Hybrid reinforcement learning breaks sample size bar- riers in linear MDPs. The Thirty-eighth Annual Conference on Neural Information Processing Systems

    2024

  104. [112]

    Tan K, Fan W, Wei Y (2025) Actor-critics can achieve optimal sample efficiency.arXiv preprint arXiv:2505.03710

    2025 arXiv

  105. [113]

    Proceedings of the Fourth Connectionist Models Summer School

    Thrun S, Schwartz A (1993) Issues in using function approximation for reinforcement learning. Proceedings of the Fourth Connectionist Models Summer School

    1993

  106. [114]

    IEEE Transactions on Automatic Control 42(5):674–690

    Tsitsiklis J, Van Roy B (1997) An analysis of temporal-difference learning with func- tion approximation. IEEE Transactions on Automatic Control 42(5):674–690

    1997

  107. [115]

    Machine learning 16(3):185–202

    Tsitsiklis JN (1994) Asynchronous stochastic approximation and Q-learning. Machine learning 16(3):185–202

    1994

  108. [116]

    International Conference on Learning Representations

    Uehara M, Sun W (2022) Pessimistic model-based offline reinforcement learning under partial coverage. International Conference on Learning Representations

    2022

  109. [117]

    International Conference on Machine Learning , 35300–35338 (PMLR)

    Wagenmaker A, Pacchiano A (2023) Leveraging offline data in online reinforcement learning. International Conference on Machine Learning , 35300–35338 (PMLR)

    2023

  110. [118]

    arXiv preprint arXiv:1905.06265

    Wainwright MJ (2019) Stochastic approximation with cone-contractive operators: Sharp ℓ∞-bounds for Q-learning. arXiv preprint arXiv:1905.06265

    2019 arXiv

  111. [119]

    arXiv preprint arXiv:1906.04697

    Wainwright MJ (2019) Variance-reduced Q-learning is minimax optimal. arXiv preprint arXiv:1906.04697

    2019 arXiv

  112. [120]

    International Conference on Machine Learning , 10653–10662 (PMLR)

    Wan Y, Naik A, Sutton RS (2021) Learning and planning in average-reward Markov decision processes. International Conference on Machine Learning , 10653–10662 (PMLR)

    2021

  113. [121]

    Advances in neural information pro- cessing systems 34:23009–23022

    Wang B, Yan Y, Fan J (2021) Sample-efficient reinforcement learning for linearly- parameterized MDPs with a generative model. Advances in neural information pro- cessing systems 34:23009–23022

    2021

  114. [122]

    Mathematics of Operations Research

    Wang M (2019) Randomized linear programming solves the Markov decision problem in nearly linear (sometimes sublinear) time. Mathematics of Operations Research

    2019

  115. [123]

    Advances in neural information process- ing systems 33:17816–17826

    Wang R, Du SS, Yang L, Salakhutdinov RR (2020) On reward-free reinforcement learning with linear function approximation. Advances in neural information process- ing systems 33:17816–17826

    2020

  116. [124]

    Advances in Neural Information Processing Systems 33:6123–6135

    Wang R, Salakhutdinov RR, Yang L (2020) Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems 33:6123–6135

    2020

  117. [125]

    arXiv preprint arXiv:2311.09018

    Wang S, Si N, Blanchet J, Zhou Z (2023) On the foundation of distributionally robust reinforcement learning. arXiv preprint arXiv:2311.09018

    2023 arXiv

  118. [126]

    Machine learning 8(3-4):279–292

    Watkins CJ, Dayan P (1992) Q-learning. Machine learning 8(3-4):279–292

    1992

  119. [127]

    PhD thesis, King’s College, University of Cambridge

    Watkins CJCH (1989) Learning from delayed rewards. PhD thesis, King’s College, University of Cambridge

    1989

  120. [128]

    Math- ematics of Operations Research 38(1):153–183

    Wiesemann W, Kuhn D, Rustem B (2013) Robust Markov decision processes. Math- ematics of Operations Research 38(1):153–183

    2013

  121. [129]

    Machine learning 8(3-4):229–256

    Williams RJ (1992) Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning 8(3-4):229–256

    1992

  122. [130]

    Connection Science 3(3):241–268

    Williams RJ, Peng J (1991) Function optimization using connectionist reinforcement learning algorithms. Connection Science 3(3):241–268. 38

    1991

  123. [131]

    International Conference on Machine Learning , 37157– 37216 (PMLR)

    Woo J, Joshi G, Chi Y (2023) The blessing of heterogeneity in federated Q-learning: Linear speedup and beyond. International Conference on Machine Learning , 37157– 37216 (PMLR)

    2023

  124. [132]

    Forty-first International Conference on Machine Learning

    Woo J, Shi L, Joshi G, Chi Y (2024) Federated offline reinforcement learning: Collabo- rative single-policy coverage suffices. Forty-first International Conference on Machine Learning

    2024

  125. [133]

    arXiv preprint arXiv:2410.16106

    Wu W, Li G, Wei Y, Rinaldo A (2024) Statistical inference for temporal difference learning with linear function approximation. arXiv preprint arXiv:2410.16106

    2024 arXiv

  126. [134]

    arXiv preprint arXiv:2502.13822

    Wu W, Wei Y, Rinaldo A (2025) Uncertainty quantification for markov chains with application to temporal difference learning. arXiv preprint arXiv:2502.13822

    2025 arXiv

  127. [135]

    The Journal of Machine Learning Research 23(1):12887–12922

    Xiao L (2022) On the convergence rates of policy gradient methods. The Journal of Machine Learning Research 23(1):12887–12922

    2022

  128. [136]

    The Eleventh International Conference on Learning Represen- tations

    Xie T, Foster DJ, Bai Y, Jiang N, Kakade SM (2023) The role of coverage in online reinforcement learning. The Eleventh International Conference on Learning Represen- tations

    2023

  129. [137]

    Advances in neural information processing systems 34:27395–27407

    Xie T, Jiang N, Wang H, Xiong C, Bai Y (2021) Policy finetuning: Bridging sample- efficient offline and online reinforcement learning. Advances in neural information processing systems 34:27395–27407

    2021

  130. [138]

    Mathe- matics of Operations Research 37(2):288–300

    Xu H, Mannor S (2012) Distributionally robust Markov decision processes. Mathe- matics of Operations Research 37(2):288–300

    2012

  131. [139]

    IEEE Transactions on Information Theory 69(11):7185–7219

    Yan Y, Li G, Chen Y, Fan J (2023) The efficacy of pessimism in asynchronous Q- learning. IEEE Transactions on Information Theory 69(11):7185–7219

    2023

  132. [140]

    Operations research 72(6):2430–2445

    Yan Y, Li G, Chen Y, Fan J (2024) Model-based reinforcement learning for offline zero-sum markov games. Operations research 72(6):2430–2445

    2024

  133. [141]

    International Conference on Machine Learning , 6995–7004

    Yang L, Wang M (2019) Sample-optimal parametric Q-learning using linearly additive features. International Conference on Machine Learning , 6995–7004

    2019

  134. [142]

    International Conference on Machine Learning , 10746– 10756 (PMLR)

    Yang L, Wang M (2020) Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. International Conference on Machine Learning , 10746– 10756 (PMLR)

    2020

  135. [143]

    The Thirty-eighth Annual Conference on Neural Information Processing Systems

    Yang T, Cen S, Wei Y, Chen Y, Chi Y (2024) Federated natural policy gradient and actor critic methods for multi-task reinforcement learning. The Thirty-eighth Annual Conference on Neural Information Processing Systems

    2024

  136. [144]

    International Conference on Machine Learning (PMLR)

    Yang T, Dai B, Xiao L, Chi Y (2025) Incentivize without bonus: Provably efficient model-based online multi-agent RL for markov games. International Conference on Machine Learning (PMLR)

    2025

  137. [145]

    The Annals of Statis- tics 50(6):3223–3248

    Yang W, Zhang L, Zhang Z (2022) Toward theoretical understandings of robust Markov decision processes: Sample complexity and asymptotics. The Annals of Statis- tics 50(6):3223–3248

    2022

  138. [146]

    International Conference on Artificial Intelligence and Statistics , 1567–1575 (PMLR)

    Yin M, Bai Y, Wang YX (2021) Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. International Conference on Artificial Intelligence and Statistics , 1567–1575 (PMLR)

    2021

  139. [147]

    Interna- tional Conference on Learning Representations

    Yin M, Duan Y, Wang M, Wang YX (2022) Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. Interna- tional Conference on Learning Representations

    2022

  140. [148]

    Advances in neural information processing systems 34

    Yin M, Wang YX (2021) Towards instance-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems 34

    2021

  141. [149]

    SIAM Journal on Optimization 33(2):1061–1091

    Zhan W, Cen S, Huang B, Chen Y, Lee JD, Chi Y (2023) Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence. SIAM Journal on Optimization 33(2):1061–1091

    2023

  142. [150]

    Advances in Neural Information Processing Systems 33:21024–21037

    Zhang H, Chen H, Xiao C, Li B, Liu M, Boning D, Hsieh CJ (2020) Robust deep rein- forcement learning against adversarial perturbations on state observations. Advances in Neural Information Processing Systems 33:21024–21037. 39

    2020

  143. [151]

    Advances in Neural Information Processing Systems 34:1582–1593

    Zhang W, Zhou D, Gu Q (2021) Reward-free model-based reinforcement learning with linear function approximation. Advances in Neural Information Processing Systems 34:1582–1593

    2021

  144. [152]

    Advances in Neural Information Processing Systems 33:11734–11743

    Zhang X, Ma Y, Singla A (2020) Task-agnostic exploration in reinforcement learning. Advances in Neural Information Processing Systems 33:11734–11743

    2020

  145. [153]

    Conference on Learning Theory, 5213–5219 (PMLR)

    Zhang Z, Chen Y, Lee JD, Du SS (2024) Settling the sample complexity of online reinforcement learning. Conference on Learning Theory, 5213–5219 (PMLR)

    2024

  146. [154]

    accepted to Journal of the ACM

    Zhang Z, Chen Y, Lee JD, Du SS (2025) Settling the sample complexity of online reinforcement learning. accepted to Journal of the ACM

    2025

  147. [155]

    Conference on Learning Theory, 4528–4531 (PMLR)

    Zhang Z, Ji X, Du S (2021) Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. Conference on Learning Theory, 4528–4531 (PMLR)

    2021

  148. [156]

    Conference on Learning Theory, 3858–3904 (PMLR)

    Zhang Z, Ji X, Du S (2022) Horizon-free reinforcement learning in polynomial time: the power of stationary policies. Conference on Learning Theory, 3858–3904 (PMLR)

    2022

  149. [157]

    Advances in Neural Information Processing Sys- tems 33

    Zhang Z, Zhou Y, Ji X (2020) Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Sys- tems 33

    2020

  150. [158]

    International Conference on Machine Learning , 12653– 12662 (PMLR)

    Zhang Z, Zhou Y, Ji X (2021) Model-free reinforcement learning: from clipped pseudo- regret to sample complexity. International Conference on Machine Learning , 12653– 12662 (PMLR)

    2021

  151. [159]

    The Twelfth International Conference on Learning Rep- resentations

    Zheng Z, Gao F, Xue L, Yang J (2024) Federated Q-learning: Linear regret speedup with low communication cost. The Twelfth International Conference on Learning Rep- resentations

    2024

  152. [160]

    International Conference on Artificial Intelligence and Statistics , 3331–3339 (PMLR)

    Zhou Z, Zhou Z, Bai Q, Qiu L, Blanchet J, Glynn P (2021) Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. International Conference on Artificial Intelligence and Statistics , 3331–3339 (PMLR)

    2021

  153. [161]

    arXiv preprint arXiv:2410.07616

    Zurek M, Chen Y (2024) The plug-in approach for average-reward and discounted MDPs: Optimal sample complexity analysis. arXiv preprint arXiv:2410.07616

    2024 arXiv

  154. [162]

    The Thirty-eighth Annual Conference on Neural Information Processing Systems

    Zurek M, Chen Y (2024) Span-based optimal sample complexity for weakly commu- nicating and general average reward MDPs. The Thirty-eighth Annual Conference on Neural Information Processing Systems

    2024

Pith tools

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