Pith. sign in

REVIEW 3 major objections 5 minor 65 references

Auto-exploration for online reinforcement learning

T0 review · 3 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read Online reinforcement learning can explore on its own — without knowing mixing rates or stationary distributions — and still match the optimal O(ε⁻²) sample complexity.

desk verdict A real and significant claim of algorithm-independent O(ε^{-2}) sample complexity for online RL, resting on a strong mixing-optimal-policy assumption and several deferred proofs that referees should scrutinize. read the letter →

arxiv 2512.06244 v3 pith:AAGY6JAZ submitted 2025-12-06 cs.LG cs.AImath.OC

Caleb Ju , Guanghui Lan This is my paper · ORCID
classification cs.LGcs.AImath.OC MSC 90C1590C3090C4060J1068T05
keywords auto-explorationsamplecomplexitypolicymirrordescentonlinereinforcementlearningmixingtimelinearfunctionapproximationlast-iterateconvergencediscountedMDP
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

The paper tries to establish that online reinforcement learning can be made to explore both states and actions automatically, without knowing the Markov chain's mixing time or stationary distribution, and still achieve the standard O(ε⁻²) sample complexity. The setting is infinite-horizon discounted MDPs with finite states and actions, and the key structural premise is that a deterministic optimal policy induces an irreducible, geometrically mixing Markov chain that visits every state with positive stationary probability. Under that premise, the paper proves last-iterate convergence for a stochastic policy mirror descent algorithm using a data-driven 'dynamic mixing time': with probability 1−δ the gap is at most ε times modest log factors, and the total sample count is Õ(D_expl(δ)·ε⁻²) with D_expl(δ) independent of the algorithm's path. The same idea is then extended to linear function approximation, where the same rate is obtained up to an explicit function-approximation bias, and a computable certificate allows early stopping. A sympathetic reader takes away that the algorithm-dependent exploration terms that could be arbitrarily large in earlier bounds can be replaced by algorithm-independent problem constants, and the resulting methods are parameter-free.

What carries the argument

The device carrying the argument is the dynamic mixing time ṁ^π(π,ς) built from the discounted hitting time h^π_m(z)=γ^{m−τ_m^π(z)}: the algorithm records the last visit to each non-rare state-action pair and mixes until the worst-case truncation bias is below ς(1−γ). Because the hitting time is observable, this converts unknown mixing constants into a stopping rule, which is why the method is parameter-free. Two supporting pieces: Proposition 3.3 shows that if the optimal policy mixes then any policy that plays optimal actions with probability at least π also mixes with explicit constants (implicit state exploration); and the tabular estimator assigns a large placeholder value to 'rare' pai

What would settle it

Build a two-state discounted MDP whose optimal policy at state 1 chooses an action that self-loops with probability 1, while state 2 is reachable only through a strictly suboptimal action. Here the optimal chain never visits state 2, so ν*=0 and D_expl(δ) in Theorem 3.5 is infinite. Run SPMD with the TOMC estimator and dynamic mixing time under a fixed sample budget: if the last-iterate gap fails to reach the stated ε·log-factor level within Õ(ε⁻²) samples, the assumption is doing the work; if it succeeds, Assumption 3.2 is conservative. Either outcome decides how universal the auto-exploratio

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.5 and Corollary 5.2: under Assumption 3.2, SPMD with the TOMC estimator and the dynamic mixing time solves the tabular problem to ε-accuracy with probability 1−δ using Õ(|A|^{1−p}[log(|Z|/δ)]² D_expl(δ) / ((1−γ)⁵ ε²)) samples, where D_expl(δ) is expressed only through the optimal policy's mixing rate ρ*, stationary lower bound ν*, and the action-ratio exponent ¯b — no algorithm-dependent quantities. The same rate holds for SPMD+CTD with linear function approximation (Corollary 5.2), up to a function-approximation error ϵ_app,∞, with D_expl(δ) again algorithm-independent. The paper presents this as the first parameter-free, algorithm-independent O(ε⁻²) sample co

Load-bearing premise

Everything rests on Assumption 3.2: the deterministic optimal policy's Markov chain must be irreducible, visit every state with stationary probability at least ν* > 0, and mix geometrically with rate ρ* < 1; if the optimal policy is absorbing or leaves some state transient, the tabular sample bound degrades, with D_expl(δ) containing the factor (ν*)^{-3}.

Editorial extensions

If this is right

  • A practitioner can run the tabular algorithm with no knowledge of mixing rates, stationary distributions, or the difficulty parameter and receive a last-iterate policy with a high-probability O(ε⁻²) guarantee.
  • Algorithm-dependent exploration terms that could be arbitrarily large in prior work — terms tied to intermediate policies — are replaced by D_expl(δ), which depends only on the problem's optimal policy.
  • In linear function approximation, explicit exploration is shown to hedge function-approximation bias rather than state exploration; when that bias is small, state exploration (ε^(S)_π=0) can be removed entirely.
  • The anytime CTD estimator removes multi-epoch restarts and works with fixed step sizes, simplifying implementation while retaining convergence guarantees.
  • The advantage gap function certificate enables early termination: if the computed gap is small, the algorithm stops and returns a policy certified up to a factor (1−γ)^{-1}.

Reading between the lines

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

  • The load-bearing role of Assumption 3.2 is easy to underestimate: if the unique optimal policy is absorbing at some state, then ν*=0 for that chain and D_expl(δ) is infinite, leaving the tabular bound with no stated substitute. The advertised relaxation to 'any exploring policy' is argued only in the linear-approximation setting and in a single sentence, so the general scope is narrower than the a
  • Since ν* and ρ* never enter the algorithm, an empirical probe is possible: run the dynamic mixing time on an MDP with a known optimal policy that mixes quickly and compare per-iteration sample counts to the bound's prediction; the log factors may dominate at practical scales.
  • The discounted hitting-time device could plausibly transfer to other on-policy value-based methods, such as Q-learning variants, as a generic route to parameter-free exploration, but the paper does not attempt that transfer.
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

3 major / 5 minor

Summary. The paper proposes 'auto-exploration' variants of stochastic policy mirror descent (SPMD) for infinite-horizon discounted MDPs, in tabular and linear-function-approximation settings. The main claim is that, under an algorithm-independent assumption that a deterministic optimal policy is irreducible and mixing (Assumption 3.2), a parameter-free algorithm reaches, with high probability, a last-iterate optimality gap of O(ε·polylog) using O(D_expl(δ)·ε^{-2}) samples, where D_expl(δ) depends only on the MDP and not on iterates of the algorithm. The tabular mechanism is a data-driven dynamic mixing time (16) with the TOMC estimator (12); the LFA mechanism uses a discounted state-visitation sampling distribution (28), an anytime conditional temporal difference method, and a doubling-trick certificate via an advantage gap function. The paper claims this is the first algorithm-independent O(ε^{-2}) sample complexity under weaker exploration assumptions.

Significance. If the technical claims are correct, the paper is a meaningful step in online RL theory: it removes algorithm-dependent parameters from the leading-order sample complexity and gives implementable, parameter-free procedures for both tabular and linear-function-approximation settings. The dynamic mixing time, the discounted-visitation sampling distribution, and the robust estimator are valuable algorithmic ideas. The paper also gives explicit constants and attempts last-iterate high-probability guarantees, which are stronger than ergodic guarantees. However, the advertised algorithm-independent bound is affected by a quantitative mismatch between the per-iteration sample bound and the final complexity, and a central relaxation claim is asserted rather than proved. The significance is therefore conditional on repair of those points.

major comments (3)
  1. [Theorem 3.5, Eq. (22) vs Eq. (24)] The displayed sample complexity is inconsistent with the proof. The per-iteration bound (24) ends with O~( |A| (log(|Z|/(εδ)))^2 / ((1−γ) ν_t (1−ρ_t)) ), where the |A| factor comes from the lower bound λ^{π_t}(z) ≥ ν_t·π̲ and π̲ = |A|^{-1}(1−γ)/polylog. Multiplying by k = O~( |A|^{1−p} / ((1−γ)^4 ε^2) ) gives O~( |A|^{2−p} ... / ((1−γ)^5 ν(1−ρ) ε^2) ), not the |A|^{1−p} shown in the first bound of (22). The subsequent algorithm-independent bound therefore carries a missing factor of |A| (equivalently, D_expl(δ) should be |A|^{2b̄+1} if the final complexity is |A|^{1−p}D_expl, or the final complexity should be |A|^{2−p}D_expl). Since the headline is an O(ε^{-2}) algorithm-independent complexity, this factor must be reconciled.
  2. [After Corollary 5.2, Section 5.2] Please either provide a full proof of the relaxation or explicitly state that the LFA result also requires a mixing optimal policy (or a separate argument with a different D_expl).
  3. [Lemmas 2.3, 2.4, 4.4-4.6, Corollary 4.11] I recommend adding the missing proofs in an appendix or providing a detailed step-by-step reduction to the cited results.
minor comments (5)
  1. [Section 1] Typo: 'holds holds' appears in the paragraph citing [38].
  2. [Section 4.1] 'Throughout this session' should be 'Throughout this section'.
  3. [Proposition 3.3 proof, Eq. (18)] The notation in the displayed inequality (18) is confusing: ν* is used both as a scalar lower bound and as a vector stationary distribution. Please rewrite this step with clear notation and explain the claimed componentwise bound.
  4. [Lemma 3.1] The lemma states 'for any fixed z∈Z' but the relevant set appears to be the non-rare set Z_π(π̲); please clarify the domain of z.
  5. [Theorem 3.5 / Eq. (24)] The log factor in (24) is log(|Z|/(εδ)) whereas the theorem statement uses log(|Z|/δ). If these are meant to be absorbed by O~, please state the convention explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the main sample-complexity claims are derived from Assumption 3.2 via explicit bounds, not by fitting or renaming the target quantities.

full rationale

The derivation chain is self-contained in the relevant sense. Theorem 3.5's algorithm-independent bound D_expl(δ) is obtained from Assumption 3.2 through Proposition 3.3 and inequality (25): the stationary lower bound ν_t ≥ π̄^b̄ ν*/2 and mixing rate bound ρ_t ≤ 1 − π̄^b̄(ν*)²/(2b̄) are proved, not assumed, and D_expl(δ) is then expressed only in terms of the problem constants ν*, ρ*, b̄, |A|, γ, and δ. The dynamic mixing time (16) is data-driven and its analysis in Lemma 3.1 is a high-probability bound on the discounted hitting time, not a reconstruction of the optimality gap it later certifies. The LFA lower-bound estimate in Corollary 5.2 sets κ = (1−γ)f/|S| and justifies it directly from the definition of the discounted state visitation distribution κ^π_{s_or,f}(s) ≥ (1−γ)f/|S|; this is a structural inequality, not a fitted parameter. The paper does cite prior work by the same authors, especially [39], [38], and [26], for lemmas such as SPMD analysis, Q-function estimators, and the advantage gap function, but these are external supporting results rather than the paper's target claim, and no 'uniqueness theorem' or ansatz is imported by self-citation to force the conclusion. The acknowledged limitation that Assumption 3.2 may be necessary when the dynamic mixing time exceeds a budget is a robustness/correctness caveat, not a circular step. Overall, no prediction in the paper reduces by construction to its inputs, and the score is therefore 0.

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

Tabular results rest on a single structural assumption (Assumption 3.2) plus standard martingale/mixing toolbox lemmas, with an algorithm that is genuinely parameter-free (π̄, ς, α, k are explicit formulas, not fitted). The LFA results add user inputs κ, f, s_or; κ is the only load-bearing one, because Theorem 4.12's validity condition (38) refers to the algorithm's own iterates — but Algorithm 3 converts κ into a guess-and-check parameter certified by the advantage gap function, so no circularity survives in the final guarantee. No constant anywhere is fitted to data; the price is that the 'algorithm-independent' constants carry |A|^{2b̄} and (ν*)^{-3}-type factors that can be extremely large.

free parameters (3)
  • κ — lower-bound estimate of discounted state visitation = (1−γ)f/|S| works under Assumption 3.2 (Cor 5.2); otherwise found by doubling (Alg. 3)
    Theorem 4.12 requires κ ≤ min_{0≤t≤k−1} min_s κ^{π_t}_{s_or,f}(s); a too-large κ invalidates the guarantees, so it drives Algorithm 3's guess-and-check. Not fitted to data, but an input whose validity depends on the algorithm's own iterates.
  • f — frequency parameter in the CTD sampling distribution (28) = user-chosen; f = 0 suggested in Cor. 5.3 when approximation error is small
    Any f > 0 preserves convergence; the sample complexity scales as 1/f⁴ (Cor. 5.2). A user knob, not determined by the problem.
  • s_or — arbitrary origin state for discounted-visitation sampling = arbitrary, chosen per iteration (Alg. 2, Line 3)
    Appears in the constants via ν_or in Lemma 4.6; guarantees hold for any choice, so it is a free but harmless input.
assumptions (5)
  • domain assumption Assumption 3.2: there exists a deterministic optimal policy π* whose Markov chain is irreducible; ν*(s) ≥ ν* > 0 ∀s; ‖Pr^{π*}(s_τ=·|s₀) − ν*‖_tv ≤ C*(ρ*)^τ with C* ≤ 2, ρ* ∈ [1/2, 1).
    The entire auto-exploration mechanism — tabular (Theorem 3.5) and LFA (Corollary 5.2) — flows from this premise via Proposition 3.3. If no such policy exists, the algorithm-independent D_expl bounds collapse. The claimed relaxation to 'any exploring policy' is only sketched and only for the LFA setting.
  • domain assumption Bounded regularized cost: c(·,·) + h_π(·|s)(s) ∈ [0,1]; hence Q̄ = (1−γ)^{-1} and M_h ≤ Q̄.
    Normalization set in §2.1 and used throughout Proposition 2.2 and Theorems 3.5/4.12 to set α, k, ς.
  • standard math Standard probability tools: Hoeffding/Azuma-Hoeffding, Markov's inequality, union bounds, plus last-iterate analysis from Jain-Nagaraj-Netrapalli [21] and Orabona-Pal [48].
    Invoked in Proposition 2.2, Lemma 2.3, Lemma 4.6, and Proposition 4.8; several steps are deferred with 'nearly identical to [21, Lemma 3.2/3.6]' or 'identical to [39, Lemma 5.5]'.
  • domain assumption Finite S, A; Φ ∈ R^{|Z|×d} full column rank for linear function approximation; linear span guarantees global optimality.
    Setup of §2.1 and §4.1; full rank is stated as WLOG by dropping dependent columns. The linearity assumption is what limits the LFA results to feature spaces that may not contain Q^π.
  • domain assumption Well-posedness of the projected Bellman equation (26): min_s κ^{π}_{s_or,f}(s) > 0 and ε^{(A)}_π ≤ (1−γ) min_s κ(s)/4 (Prop 4.1); plus the κ lower-bound condition (38) for Theorem 4.12.
    Proposition 4.1 proves (26) is solvable under these conditions, but the condition (38) refers to visitation quantities of the algorithm's own intermediate policies; Algorithm 3 attempts to satisfy it by guessing κ. This is the closest the paper comes to a circular input, resolved by the certificate.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Auto-exploration for online reinforcement learning." pith.science (2026). https://pith.science/paper/AAGY6JAZ

@misc{pith2026251206244,
  author       = {Pith},
  title        = {Pith review of: Auto-exploration for online reinforcement learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AAGY6JAZ}},
  note         = {Machine review of arXiv:2512.06244}
}
abstract

The exploration-exploitation dilemma in reinforcement learning (RL) is a fundamental challenge to efficient RL algorithms. Existing algorithms for finite state and action discounted RL problems address this by assuming sufficient exploration over both state and action spaces. However, this yields non-implementable algorithms and sub-optimal performance. To resolve these limitations, we introduce a new class of methods with auto-exploration, or methods that automatically explore both state and action spaces. Auto-exploration can be applied in both the tabular and linear function approximation setting. Under algorithm-independent assumptions on the existence of an exploring optimal policy, both settings attain $O(\epsilon^{-2})$ sample complexity to solve to $\epsilon$ error. These complexities are novel since they avoid algorithm-dependent parameters seen in prior works, which may be arbitrarily large. The methods are also simple to implement because they are parameter-free. We achieve these results by integrating auto-exploration into policy mirror descent to avoid the (unknown) stationary distribution seen in prior art. In the tabular setting, we introduce a dynamic exploration time with a data-driven stopping time, while for linear function approximation we propose a new sampling distribution based on the discounted visitation distribution that covers a more general class of Markov chains.

Figures

Figures reproduced from arXiv: 2512.06244 by the authors.

Figure 1
Figure 1. Visualization of which policy is used to sample at each time period. Each dot represents the [PITH_FULL_IMAGE:figures/full_fig_p018_1.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

65 extracted references · 10 linked inside Pith

  1. [39]

    Policy mirror descent inherently explores action space

    Yan Li and Guanghui Lan. Policy mirror descent inherently explores action space. SIAM Journal on Optimization, 35(1):116–156, 2025

    2025

  2. [45]

    A minimal-assumption analysis of q-learning with time-varying policies

    Phalguni Nanda and Zaiwei Chen. A minimal-assumption analysis of q-learning with time-varying policies. arXiv preprint arXiv:2510.16132, 2025

    arXiv 2025

  3. [1]

    PC-PG: Policy cover directed explo- ration for provable policy gradient learning

    Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. PC-PG: Policy cover directed explo- ration for provable policy gradient learning. Advances in neural information processing systems, 33:13399–13412, 2020

    2020

  4. [2]

    Model-based reinforcement learning with a gen- erative model is minimax optimal

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

    2020

  5. [3]

    On the theory of policy gradient methods: Optimality, approximation, and distribution shift

    Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1–76, 2021

    2021

  6. [4]

    A natural actor-critic framework for zero-sum markov games

    Ahmet Alacaoglu, Luca Viano, Niao He, and V olkan Cevher. A natural actor-critic framework for zero-sum markov games. In International Conference on Machine Learning, pages 307–366. PMLR, 2022

    2022

  7. [5]

    Finite-time analysis of the multiarmed bandit problem

    Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235–256, 2002

    2002

  8. [6]

    Gambling in a rigged casino: The adversarial multi-armed bandit problem

    Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th annual foundations of computer science, pages 322–331. IEEE, 1995

    1995

Show all 65 references
  1. [7]

    Near-optimal regret bounds for reinforcement learning

    Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008

    2008

  2. [8]

    Applying reinforcement learning towards automat- ing resource allocation and application scalability in the cloud

    Enda Barrett, Enda Howley, and Jim Duggan. Applying reinforcement learning towards automat- ing resource allocation and application scalability in the cloud. Concurrency and Computation: Practice and Experience, 25(12):1656–1674, 2013

    2013

  3. [9]

    Dynamic programming and stochastic control processes

    Richard Bellman. Dynamic programming and stochastic control processes. Information and control, 1(3):228–239, 1958

    1958

  4. [10]

    Stochastic optimal control: the discrete-time case, vol- ume 5

    Dimitri Bertsekas and Steven E Shreve. Stochastic optimal control: the discrete-time case, vol- ume 5. Athena Scientific, 1996

    1996

  5. [11]

    Provably efficient exploration in policy opti- mization

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

    2020

  6. [12]

    Faster last-iterate convergence of policy optimization in zero-sum Markov games

    Shicong Cen, Yuejie Chi, Simon S Du, and Lin Xiao. Faster last-iterate convergence of policy optimization in zero-sum Markov games. arXiv preprint arXiv:2210.01050, 2022

    2022 arXiv

  7. [13]

    Non-asymptotic guarantees for average-reward q-learning with adaptive stepsizes

    Zaiwei Chen. Non-asymptotic guarantees for average-reward q-learning with adaptive stepsizes. arXiv preprint arXiv:2504.18743, 2025. 32

    2025 arXiv

  8. [14]

    Finite- sample analysis of nonlinear stochastic approximation with applications in reinforcement learning

    Zaiwei Chen, Sheng Zhang, Thinh T Doan, John-Paul Clarke, and Siva Theja Maguluri. Finite- sample analysis of nonlinear stochastic approximation with applications in reinforcement learning. Automatica, 146:110623, 2022

    2022

  9. [15]

    Last-iterate conver- gent policy gradient primal-dual methods for constrained mdps

    Dongsheng Ding, Chen-Yu Wei, Kaiqing Zhang, and Alejandro Ribeiro. Last-iterate conver- gent policy gradient primal-dual methods for constrained mdps. Advances in Neural Information Processing Systems, 36:66138–66200, 2023

    2023

  10. [16]

    Learning rates for Q-learning

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

    2003

  11. [17]

    A theoretical analysis of deep Q-learning

    Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep Q-learning. In Learning for dynamics and control, pages 486–489. PMLR, 2020

    2020

  12. [18]

    Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model

    Mohammad Gheshlaghi Azar, R ´emi Munos, and Hilbert J Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91(3):325–349, 2013

    2013

  13. [19]

    Chattering in SARSA(λ)

    Geoffrey J Gordon. Chattering in SARSA(λ). Technical Report CMU, 1996

    1996

  14. [20]

    Sim2real in robotics and automation: Applications and challenges

    Sebastian H ¨ofer, Kostas Bekris, Ankur Handa, Juan Camilo Gamboa, Melissa Mozifian, Florian Golemo, Chris Atkeson, Dieter Fox, Ken Goldberg, John Leonard, et al. Sim2real in robotics and automation: Applications and challenges. IEEE transactions on automation science and engi...

    2021

  15. [21]

    Making the last iterate of sgd informa- tion theoretically optimal

    Prateek Jain, Dheeraj M Nagaraj, and Praneeth Netrapalli. Making the last iterate of sgd informa- tion theoretically optimal. SIAM Journal on Optimization, 31(2):1108–1130, 2021

    2021

  16. [22]

    Doubly robust off-policy value evaluation for reinforcement learning

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

    2016

  17. [23]

    Is Q-learning provably efficient? Advances in neural information processing systems, 31, 2018

    Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably efficient? Advances in neural information processing systems, 31, 2018

    2018

  18. [24]

    Towards tight bounds on the sample complexity of average-reward MDPs

    Yujia Jin and Aaron Sidford. Towards tight bounds on the sample complexity of average-reward MDPs. In International Conference on Machine Learning, pages 5055–5064. PMLR, 2021

    2021

  19. [25]

    Policy optimization over general state and action spaces

    Caleb Ju and Guanghui Lan. Policy optimization over general state and action spaces. arXiv preprint arXiv:2211.16715, 2022

    2022

  20. [26]

    Strongly-polynomial time and validation analysis of policy gradient methods

    Caleb Ju and Guanghui Lan. Strongly-polynomial time and validation analysis of policy gradient methods. arXiv preprint arXiv:2409.19437, 2024

    2024

  21. [27]

    Approximately optimal approximate reinforcement learning

    Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the nineteenth international conference on machine learning, pages 267–274, 2002

    2002

  22. [28]

    Efficiently breaking the curse of horizon in off-policy eval- uation with double reinforcement learning

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

    2022

  23. [29]

    A systematic review on reinforcement learning-based robotics within the last decade

    Md Al-Masrur Khan, Md Rashed Jaowad Khan, Abul Tooshil, Niloy Sikder, MA Parvez Mahmud, Abbas Z Kouzani, and Abdullah-Al Nahid. A systematic review on reinforcement learning-based robotics within the last decade. IEEE Access, 8:176598–176623, 2020

    2020

  24. [30]

    Finite-sample analysis of two-time-scale natural actor–critic algorithm.IEEE Transactions on Automatic Control, 68(6):3273–3284, 2022

    Sajad Khodadadian, Thinh T Doan, Justin Romberg, and Siva Theja Maguluri. Finite-sample analysis of two-time-scale natural actor–critic algorithm.IEEE Transactions on Automatic Control, 68(6):3273–3284, 2022. 33

    2022

  25. [31]

    Georgios Kotsalis, Guanghui Lan, and Tianjiao Li. Simple and optimal methods for stochastic variational inequalities, ii: Markovian noise and policy evaluation in reinforcement learning.SIAM Journal on Optimization, 32(2):1120–1155, 2022

    2022

  26. [32]

    Policy mirror descent for reinforcement learning: Linear convergence, new sam- pling complexity, and generalized problem classes

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

    2023

  27. [33]

    Bandit algorithms

    Tor Lattimore and Csaba Szepesv ´ari. Bandit algorithms. Cambridge University Press, 2020

    2020

  28. [34]

    Near-optimal sample complexity for MDPs via anchoring

    Jongmin Lee, Mario Bravo, and Roberto Cominetti. Near-optimal sample complexity for MDPs via anchoring. arXiv preprint arXiv:2502.04477, 2025

    2025 arXiv

  29. [35]

    Markov chains and mixing times, volume 107

    David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathe- matical Soc., 2017

    2017

  30. [36]

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

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

    2024

  31. [37]

    Accelerated and instance-optimal policy evaluation with linear function approximation

    Tianjiao Li, Guanghui Lan, and Ashwin Pananjady. Accelerated and instance-optimal policy evaluation with linear function approximation. SIAM Journal on Mathematics of Data Science, 5(1):174–200, 2023

    2023

  32. [38]

    Stochastic first-order methods for average-reward markov decision processes

    Tianjiao Li, Feiyang Wu, and Guanghui Lan. Stochastic first-order methods for average-reward markov decision processes. Mathematics of Operations Research, 2024

    2024

  33. [40]

    Homotopic policy mirror descent: policy conver- gence, algorithmic regularization, and improved sample complexity

    Yan Li, Guanghui Lan, and Tuo Zhao. Homotopic policy mirror descent: policy conver- gence, algorithmic regularization, and improved sample complexity. Mathematical Programming, 207(1):457–513, 2024

    2024

  34. [41]

    Human-level control through deep reinforcement learning

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

    2015

  35. [42]

    Optimal oracle inequalities for pro- jected fixed-point equations, with applications to policy evaluation

    Wenlong Mou, Ashwin Pananjady, and Martin J Wainwright. Optimal oracle inequalities for pro- jected fixed-point equations, with applications to policy evaluation. Mathematics of Operations Research, 48(4):2308–2336, 2023

    2023

  36. [43]

    Error bounds for approximate value iteration

    R ´emi Munos. Error bounds for approximate value iteration. In Proceedings of the National Conference on Artificial Intelligence, volume 20, page 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005

    1999

  37. [44]

    Finite-time bounds for fitted value iteration

    R ´emi Munos and Csaba Szepesv ´ari. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008

    2008

  38. [46]

    Robust stochastic approximation approach to stochastic programming

    Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574– 1609, 2009

    2009

  39. [47]

    Numerical optimization

    Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 2006. 34

    2006

  40. [48]

    Parameter-free stochastic optimization of variationally coherent functions

    Francesco Orabona and D ´avid P´al. Parameter-free stochastic optimization of variationally coherent functions. arXiv preprint arXiv:2102.00236, 2021

    2021 arXiv

  41. [49]

    Training language models to follow instructions with human feedback

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

    2022

  42. [50]

    Markov decision processes: discrete stochastic dynamic programming

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

    2014

  43. [51]

    Random features for large-scale kernel machines

    Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007

    2007

  44. [52]

    Invertibility of random matrices: norm of the inverse

    Mark Rudelson. Invertibility of random matrices: norm of the inverse. Annals of Mathematics, pages 575–600, 2008

    2008

  45. [53]

    High- dimensional continuous control using generalized advantage estimation

    John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv:1506.02438, 2015

    2015 arXiv

  46. [54]

    Proximal policy optimization algorithms

    John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017

    2017 arXiv

  47. [55]

    A state-distribution matching approach to non- episodic reinforcement learning

    Archit Sharma, Rehaan Ahmad, and Chelsea Finn. A state-distribution matching approach to non- episodic reinforcement learning. arXiv preprint arXiv:2205.05212, 2022

    2022 arXiv

  48. [56]

    Markov decision processes for screening and treatment of chronic diseases

    Lauren N Steimle and Brian T Denton. Markov decision processes for screening and treatment of chronic diseases. In Markov decision processes in practice, pages 189–222. Springer, 2017

    2017

  49. [57]

    Reinforcement learning: An introduction, volume 1

    Richard S Sutton, Andrew G Barto, et al. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998

    1998

  50. [58]

    A provably efficient sample collection strategy for reinforcement learning

    Jean Tarbouriech, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. A provably efficient sample collection strategy for reinforcement learning. Advances in Neural Information Processing Systems, 34:7611–7624, 2021

    2021

  51. [59]

    Finding good policies in average- reward Markov decision processes without prior knowledge

    Adrienne Tuynman, R ´emy Degenne, and Emilie Kaufmann. Finding good policies in average- reward Markov decision processes without prior knowledge. Advances in Neural Information Processing Systems, 37:109948–109979, 2024

    2024

  52. [60]

    What are the statistical limits of offline RL with linear function approximation? arXiv preprint arXiv:2010.11895, 2020

    Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offline RL with linear function approximation? arXiv preprint arXiv:2010.11895, 2020

    2010 arXiv

  53. [61]

    Estimating the mixing time of ergodic markov chains

    Geoffrey Wolfer and Aryeh Kontorovich. Estimating the mixing time of ergodic markov chains. In Conference on Learning Theory, pages 3120–3159. PMLR, 2019

    2019

  54. [62]

    Rates of convergence for empirical processes of stationary mixing sequences

    Bin Yu. Rates of convergence for empirical processes of stationary mixing sequences. The Annals of Probability, pages 94–116, 1994

    1994

  55. [63]

    The ingredients of real-world robotic reinforcement learning

    Henry Zhu, Justin Yu, Abhishek Gupta, Dhruv Shah, Kristian Hartikainen, Avi Singh, Vikash Kumar, and Sergey Levine. The ingredients of real-world robotic reinforcement learning. arXiv preprint arXiv:2004.12570, 2020

    2004 arXiv

  56. [64]

    Uncertainty quantification and exploration for reinforcement learning

    Yi Zhu, Jing Dong, and Henry Lam. Uncertainty quantification and exploration for reinforcement learning. Operations Research, 72(4):1689–1709, 2024

    2024

  57. [65]

    Finite-sample analysis for sarsa with linear function approximation

    Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for sarsa with linear function approximation. Advances in neural information processing systems, 32, 2019. 35

    2019

Pith tools

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