Pith. sign in

REVIEW 2 major objections 3 minor 47 references

A new algorithm makes finite-horizon tabular RL regret horizon-free and asymptotically optimal, matching the contextual-bandit lower bound √(SAK) up to logarithmic factors.

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

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

T0 review · deepseek-v4-flash

2026-08-01 11:30 UTC pith:Z44YQVWM

load-bearing objection Genuinely new techniques and a plausible proof, but the formal theorem only proves the H-free claim for K≤H, so the abstract overclaims; worth a careful referee. the 2 major comments →

arxiv 2607.19854 v1 pith:Z44YQVWM submitted 2026-07-22 cs.LG stat.ML

Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence

Runlong Zhou , Zihan Zhang , Maryam Fazel , Simon S. Du This is my paper
classification cs.LG stat.ML MSC 68Q3290C40
keywords horizon-free regrettabular MDPtime-homogeneousminimax optimalcutting projectionclipped variancetotal deviationvariance-aware exploration
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Time-homogeneous tabular reinforcement learning, with finitely many states and actions and per-trajectory reward at most one, is shown to admit a regret bound that does not depend at all on the episode horizon H. The paper proves an algorithm whose regret after K episodes is O(√(SAK log(SAK/δ)) + S^8 A^3 log²(SAK/δ)), so once a horizon-free polynomial burn-in is paid, the leading term matches the Ω(√SAK) contextual-bandit lower bound. A sympathetic reader should care because it means long horizons are not a statistical obstacle for time-homogeneous MDPs once the total reward scale is fixed, and the main blocker was a time-inhomogeneous sequence of optimal value functions that the paper sidesteps using monotonicity.

Core claim

The central claim is that a single algorithm can be both horizon-free and asymptotically optimal: with high probability, total regret is O(√(SAK log(SAK/δ)) + S^8 A^3 log²(SAK/δ)), and no log H appears. The authors identify the true obstacle as the value functions V*_1,...,V*_H, which are time-inhomogeneous even though the transition kernel is not; they show that the monotonicity V*_h ≥ V*_{h+1} lets the value functions be projected onto an S-dimensional grid without adding log H, and that a suitably 'cut' projection keeps residual variance under control. The result is an explicit planning-plus-exploration algorithm whose leading regret is the same as a contextual bandit's.

What carries the argument

The key object is a cutting projection: given an empirical transition row p and a value vector v, CutProj_ε(p,v) keeps only coordinates whose distance from the projected mean exceeds 2ε, so the residual v−CutProj_ε(p,v) contributes only small clipped variance. This is combined with a potential function Φ_h(s)=2Σ_u min{V*_h(s),V*_h(u)}, the proof that the expected one-step deviation plus future potential is bounded by Φ_h(s), and the resulting total-deviation bound E[Σ_h V_x(P, V*_{h+1})] ≤ 2xS per episode independent of H. A horizon-truncation lemma (dropping the last H/m steps costs only O(υ) per episode) converts the remaining suffix into reward-based exploration, and a relaxed monotonic b

Load-bearing premise

The load-bearing premise is the potential-function inequality in Lemma 28: the expected one-step deviation of the true optimal value plus the future potential must not exceed the current potential; if that inequality fails, the clipped-variance bound and the entire horizon-free result collapse.

What would settle it

Search all two-state/two-action MDPs with monotone value sequences and evaluate Eq. (47) of the paper: one transition row and pair (h,s,a) where Φ_h(s) < Σ P(|V*_{h+1}(s')−P V*|+Φ_{h+1}(s')) would break the total-deviation lemma and with it the √(SAK) regret claim.

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

If this is right

  • For K larger than the horizon-free burn-in S^8 A^3 (polylogs suppressed), the regret is O(√(SAK log(SAK/δ))), matching the contextual-bandit minimax rate.
  • The algorithm works with no separate reward-free exploration phase; the reserved suffix H/m is used for exploration only when an unlearned pair is hit.
  • A PAC sample-complexity bound follows: O(SA/ε² + S^8A^3/ε) episodes suffice to output an ε-optimal policy, independent of H.
  • The bound is robust to 'spiky' rewards: only the total reward per trajectory is bounded, not each per-step reward.

Where Pith is reading between the lines

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

  • Beyond the paper: whether the polynomial burn-in S^8 A^3 can be reduced to something like SA is open; a positive answer would make tabular RL statistically indistinguishable from contextual bandits in finite samples.
  • Beyond the paper: the potential-function/total-deviation argument is likely portable to stochastic-shortest-path and discounted settings, where similar time-inhomogeneous value sequences appear.
  • Beyond the paper: the cut-projection idea suggests a general recipe for variance-aware optimism whenever a sequence of test functions is monotone, even if the sequence length is unbounded.
  • Not claimed by the paper: a lower bound on the burn-in term might exist; proving Ω(S^{1+α}A) would show a genuine separation between MDPs and bandits.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 3 minor

Summary. The paper studies finite-horizon, time-homogeneous tabular MDPs with nonnegative totally-bounded rewards, and proposes Algorithm 1 together with a cutting bonus, horizon truncation, and a new total-deviation bound. It claims an H-free regret bound of the form O~(sqrt(SAK) + S^8 A^3), with leading term matching the contextual-bandit lower bound up to polylog factors. The formal version is Theorem 3 in the appendix, which carries several conditions (S>=200, A>=8, m|H, d/(20S log S)>=22, and, in the proof, H>=K). The technical core is an S-dimensional cut projection of the monotone optimal value sequence and a potential-function inequality (Lemma 28) bounding the total clipped variance per episode by O(xS).

Significance. If the claimed H-free near-optimal regret were actually proved for every K, this would be a substantial advance: it would settle the main horizon-dependence question for time-homogeneous tabular MDPs and improve on the prior horizon-free bound of Zhang et al. (2022). The cut-projection construction and the total-deviation potential are novel and technically interesting, and the appendix is unusually detailed. However, the central claim as stated is not supported by the formal theorem. The formal theorem contains a K-dependent condition on H that restricts the regime in which the bound is proven, so the abstract's 'for any K>=1' is not justified. This is a load-bearing gap in the main result, not a presentation issue.

major comments (2)
  1. [Theorem 3 and Appendix D.1] The abstract and Theorem 1 state the bound for 'any K>=1' with no dependence of the horizon on K. The formal Theorem 3, however, requires d/(20S log S)>=22, where d=H/m and m=4S/υ with υ=min{sqrt(SA/(1000K)), 1/(20S log S)}. Since m grows with K, this condition is K-dependent. Rearranging gives H >= 1760 S^2 log S / υ, so when υ=sqrt(SA/(1000K)) the condition forces K <= O(H^2 A/(S^3 log^2 S)). In addition, the proof in Appendix D states 'We work under the explicit conditions S>=200, A>=8, H>=K'; this H>=K assumption is absent from the theorem statement. Thus for any fixed horizon H, the result is only proven for K bounded by a function of H, and it says nothing in the regime K >> H that is central to horizon-free learning. This contradicts the abstract's 'for any K>=1'.
  2. [Abstract vs. Theorem 3 (basic cases)] The claimed 'for any K>=1' fails already in the simplest instantiation of the model. For H=1 the MDP reduces to a contextual bandit and an H-free sqrt(SAK) bound should hold, but Theorem 3 cannot be applied because m=4S/υ must divide H=1 and m is generally not equal to 1; moreover the proof assumes H>=K. More generally, the suffix length H3=H/(20mS log S) is only guaranteed to be a positive integer under the theorem's d/(20SlogS)>=22 condition. This is not a harmless rounding issue: for K large relative to H the algorithm itself is not well-defined. The scope restriction is therefore substantive and invalidates the main claim as written.
minor comments (3)
  1. [Algorithm 1, line 2] The initialization line reads 'and K←H'. Since K is the number of episodes (an input) and the known-triple set is called K, this appears to be a typo; the known-triple set should presumably be initialized to the empty set. Please fix.
  2. [Section C vs. Algorithm 1] The parameter Nknown is set to 10000 log(1/δ) in Algorithm 1 but to 7000 log(1/δ) in Appendix C. These inconsistencies should be reconciled.
  3. [Theorem 3 statement] If the formal theorem is retained with conditions such as S>=200, A>=8, m|H, and H>=K, these should be stated in the main text and reflected in the abstract. Currently the abstract's unconditional claim is incompatible with the formal theorem.

Circularity Check

0 steps flagged

No circular derivation chain: the central new ingredients are proved from scratch, and imported exploration analysis is reproduced rather than assumed.

full rationale

I walked the derivation chain of Theorem 3 and found no step in which a claimed prediction or first-principles result reduces by construction to its own inputs. The five main components are: (i) horizon truncation (Lemma 1, proved in Appendix A.2 from the Bellman recursion and a martingale argument, giving f(H) <= f(H1)+Kυ after the parameter choice m=4S/υ); (ii) optimism of the planned value functions (Lemma 14 and Lemma 26, based on concentration for the cut projection proved in Appendix E); (iii) the variance closure (Lemma 20, whose clipped-variance control relies on Corollary 2, proved from scratch in Appendix F through the potential-function inequality Lemma 28 using only monotonicity V*_h >= V*_{h+1} and Jensen's inequality); (iv) inverse-count bounds (Lemma 15, proved from the frozen-count doubling rule); and (v) the explicit-exploration bound (Lemma 21, Appendix G). The only imported component is the explicit-exploration analysis, which the paper says 'closely follows the original analysis of [40]'; however, the relevant lemmas are restated and proved in Appendices G.5.1-G.5.2 rather than invoked as an unverified self-citation, so this is not load-bearing circularity. No parameter is fitted to a subset of data and then reported as a prediction: υ, m, ϵ, N_ref, and N_known are fixed algorithmic inputs, and the regret bound is obtained by an explicit proof, not by renaming a fitted quantity. The formal theorem's additional conditions (m divides H, d/(20SlogS) >= 22, H >= K) are a real scope restriction on the stated 'any K' claim relative to the abstract, but that is a correctness/scope issue, not a circularity: the proof does not assume the regret bound, and the K-H coupling does not make any equation reduce to an input by definition. Therefore the appropriate circularity score is 0.

Axiom & Free-Parameter Ledger

5 free parameters · 6 axioms · 2 invented entities

The central claim rests on standard domain assumptions (nonnegative totally-bounded rewards, time-homogeneous transitions) plus several ad hoc technical conditions (S≥200, A≥8, H≥K, m divides H, d/(20SlogS)≥22) that are not stated in the abstract. The algorithm's hyperparameters υ, ε, m, N_ref, N_known are chosen by hand for the proof, not fitted to data. No new physical entities are introduced; the dummy states and cut operator are internal proof constructs with no independent falsifiable evidence.

free parameters (5)
  • υ = min{√(SA/(1000K)), 1/(20S log S)}
    Exploration/truncation trade-off parameter; chosen by hand to balance the leading √(SAK) term against the truncation loss Kυ.
  • ε = 1/S²
    Grid resolution for the cut projection; chosen so the cut-set size 4S/ε² is polynomial and the clipped-variance term εS per episode is absorbable.
  • m = 4S/υ
    Truncation denominator; chosen so that Lemma 1's truncation loss is ≤υ and m > S.
  • N_ref = 1025 S² log(1/δ)
    Threshold for known triples; set large enough for the reference-model approximation Lemma 30.
  • N_known = 10000 log(1/δ) in Algorithm 1; 7000 log(1/δ) in Appendix C
    Number of effective exploration calls needed to remove a pair from O. There is an inconsistency between the two values, which leaves the burn-in constant ambiguous.
axioms (6)
  • domain assumption Rewards are nonnegative and total reward per trajectory is ≤1 (totally-bounded reward).
    Stated in Section 2; used to bound V_h^* ∈ [0,1], monotonicity V_h^* ≥ V_{h+1}^*, and per-episode regret ≤1.
  • domain assumption Monotonicity of optimal value functions V_h^*(s) ≥ V_{h+1}^*(s).
    Follows from nonnegative rewards and time-homogeneous transitions; proved in Lemma 28; load-bearing for the cut-projection counting and the total-deviation bound.
  • standard math The Ω(√(SAK)) lower bound for time-homogeneous tabular MDPs (contextual-bandit lower bound).
    Invoked in Section 1 and Table 1 as the benchmark; not proved in this paper.
  • standard math Standard concentration inequalities: Bennett, empirical Bennett, Hoeffding-Azuma, Linear Freedman, Ville, supermartingale drift (Lemmas 2-11).
    Used throughout the appendix; assumed as background.
  • ad hoc to paper Technical conditions: S≥200, A≥8, H≥K, m|H, d/(20S log S)≥22, K≥1000S²A log(1/δ).
    Stated in Theorem 3 and Appendix D; not in the abstract; restrict the scope of the formal theorem.
  • standard math The explicit-exploration analysis of [40] (Lemmas 36, 38-45) is correct under the stated adaptations.
    The analysis of the exploration subroutine (Appendix G) 'largely follows [40]' and imports several lemmas without re-proving them; the present paper's bound inherits their correctness.
invented entities (2)
  • Dummy states z and z1 in the reference model (extended state space S̄ = S ∪ {z,z1}) no independent evidence
    purpose: Used to redirect probability mass of unknown transitions in the clipped true model and reference model for the exploration subroutine
    Proof artifacts; no empirical falsifiable handle; they exist only in the analysis.
  • The cut-projection operator CutProj_ε and the cutting operator Cut_ε no independent evidence
    purpose: Discretizes the monotone value sequence into a small function class while controlling residual variance
    Mathematical construction internal to the proof; no independent evidence.

pith-pipeline@v1.3.0-alltime-deepseek · 61773 in / 18334 out tokens · 160834 ms · 2026-08-01T11:30:20.508227+00:00 · methodology

0 comments
read the original abstract

We study horizon-free regret minimization for finite-horizon time-homogeneous tabular Markov decision processes with $S$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$. We propose a new algorithm and prove a regret upper bound \[\tilde O(\sqrt{SAK}+S^8A^3)\] with failure probability $\delta$, where $K$ is the number of episodes and $\tilde O(\cdot)$ hides $\mathsf{poly}\log(S,A,K,1/\delta)$. Thus, the regret is $H$-free and asymptotically optimal, matching the contextual-bandit lower bound $\Omega(\sqrt{SAK})$ up to logarithmic factors. This completely removes the $\log H$ dependence from the previous $\tilde O(\sqrt{SAK\log H}+S^2A\log H)$ guarantee of Zhang et al. (2021), and drastically improves the prior best horizon-free regret $\tilde O(\sqrt{S^9A^3K})$ of Zhang et al. (2022) asymptotically. The main technical difficulty is that the optimal value functions $\{V_h^*\}_{h=1}^H$ are time-inhomogeneous even though the transition kernel is time-homogeneous. A direct union bound over all value functions typically incurs an additional $\min\{\log H,S\}$ factor. We avoid this factor by (i) exploiting the monotonicity of $V_h^*$ in $h$ and (ii) non-trivially projecting the value functions onto an $S$-dimensional grid. Our analysis relies on three additional ingredients. First, we introduce a horizon-truncation argument that enables reward-based exploration and removes the cost of a separate reward-free exploration phase. Second, we design a cutting bonus that preserves both optimism and the monotonicity needed for planning. Third, we prove a new bound on total deviation for time-homogeneous MDPs, which controls the clipped variance terms in the cutting bonus with adjustable polynomial dependence on $S$ and without any dependence on $H$. Together, these tools yield an asymptotically optimal horizon-free regret guarantee.

discussion (0)

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

Reference graph

Works this paper leans on

47 extracted references · 7 linked inside Pith

  1. [1]

    Optimistic posterior sampling for reinforcement learning: worst-case regret bounds

    Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. InAdvances in Neural Information Processing Systems, pages 1184–1194, 2017

    2017

  2. [2]

    Minimax regret bounds for reinforcement learning

    Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. InProceedings of the 34th International Conference on Machine Learning, pages 263–272, 2017

    2017

  3. [3]

    Regal: a regularization based algorithm for reinforcement learning in weakly communicating mdps

    Peter L Bartlett and Ambuj Tewari. Regal: a regularization based algorithm for reinforcement learning in weakly communicating mdps. InProceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI 2009)), 2009

    2009

  4. [4]

    Brafman and Moshe Tennenholtz

    Ronen I. Brafman and Moshe Tennenholtz. R-max - a general polynomial time algorithm for near- optimal reinforcement learning.J. Mach. Learn. Res., 3(Oct):213–231, March 2003

    2003

  5. [5]

    Provably efficient exploration in policy optimization

    Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. arXiv preprint arXiv:1912.05830, 2019

    Pith/arXiv arXiv 1912

  6. [6]

    Implicit finite-horizon approximation and efficient optimal algorithms for stochastic shortest path.Advances in Neural Information Processing Systems, 34, 2021

    Liyu Chen, Mehdi Jafarnia-Jahromi, Rahul Jain, and Haipeng Luo. Implicit finite-horizon approximation and efficient optimal algorithms for stochastic shortest path.Advances in Neural Information Processing Systems, 34, 2021

    2021

  7. [7]

    Sample complexity of episodic fixed-horizon reinforcement learning

    Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning. InAdvances in Neural Information Processing Systems, pages 2818–2826, 2015

    2015

  8. [8]

    Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning

    Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. InProceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 5717–5727, Red Hook, NY , USA, 2017. Curran Associates Inc

    2017

  9. [9]

    Policy certificates: Towards accountable reinforcement learning

    Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. InProceedings of the 36th International Conference on Machine Learning, pages 1507–1516, 2019

    2019

  10. [10]

    Q-learning with ucb exploration is sample efficient for infinite-horizon mdp.arXiv preprint arXiv:1901.09311, 2019

    Kefan Dong, Yuanhao Wang, Xiaoyu Chen, and Liwei Wang. Q-learning with ucb exploration is sample efficient for infinite-horizon mdp.arXiv preprint arXiv:1901.09311, 2019

    Pith/arXiv arXiv 1901

  11. [11]

    Near optimal exploration-exploitation in non- communicating markov decision processes

    Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Near optimal exploration-exploitation in non- communicating markov decision processes. InAdvances in Neural Information Processing Systems, pages 2994–3004, 2018

    2018

  12. [12]

    Near-optimal regret bounds for reinforcement learning

    Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):1563–1600, 2010

    2010

  13. [13]

    Open problem: The dependence of sample complexity lower bounds on planning horizon

    Nan Jiang and Alekh Agarwal. Open problem: The dependence of sample complexity lower bounds on planning horizon. InConference On Learning Theory, pages 3395–3398, 2018

    2018

  14. [14]

    Is Q-learning provably efficient? InAdvances in Neural Information Processing Systems, pages 4863–4873, 2018

    Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably efficient? InAdvances in Neural Information Processing Systems, pages 4863–4873, 2018

    2018

  15. [15]

    PhD thesis, University of London London, England, 2003

    Sham M Kakade.On the sample complexity of reinforcement learning. PhD thesis, University of London London, England, 2003. 11

    2003

  16. [16]

    Near-optimal reinforcement learning in polynominal time

    Michael J Kearns and Satinder P Singh. Near-optimal reinforcement learning in polynominal time. In Proceedings of the Fifteenth International Conference on Machine Learning, page 260–268, 1998

    1998

  17. [17]

    Near-bayesian exploration in polynomial time

    J Zico Kolter and Andrew Y Ng. Near-bayesian exploration in polynomial time. InProceedings of the 26th annual international conference on machine learning, pages 513–520, 2009

    2009

  18. [18]

    Pac bounds for discounted mdps

    Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. InInternational Conference on Algorithmic Learning Theory, pages 320–334. Springer, 2012

    2012

  19. [19]

    Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning.Advances in Neural Information Processing Systems, 34, 2021

    Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning.Advances in Neural Information Processing Systems, 34, 2021

    2021

  20. [20]

    Horizon-free learning for Markov decision processes and games: Stochasti- cally bounded rewards and improved bounds

    Shengshi Li and Lin Yang. Horizon-free learning for Markov decision processes and games: Stochasti- cally bounded rewards and improved bounds. InProceedings of the 40th International Conference on Machine Learning, volume 202, pages 20221–20252. PMLR, 23–29 Jul 2023

    2023

  21. [21]

    Settling the horizon-dependence of sample complexity in reinforcement learning

    Yuanzhi Li, Ruosong Wang, and Lin F Yang. Settling the horizon-dependence of sample complexity in reinforcement learning. InIEEE Symposium on Foundations of Computer Science, 2021

    2021

  22. [22]

    Empirical Bernstein bounds and sample variance penalization

    Andreas Maurer and Massimiliano Pontil. Empirical Bernstein bounds and sample variance penalization. InConference on Learning Theory, 2009

    2009

  23. [23]

    Ucb momentum q-learning: Correcting the bias without forgetting

    Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. Ucb momentum q-learning: Correcting the bias without forgetting. InInternational Conference on Machine Learning, pages 7609–7618. PMLR, 2021

    2021

  24. [24]

    A unifying view of optimism in episodic reinforcement learning

    Gergely Neu and Ciara Pike-Burke. A unifying view of optimism in episodic reinforcement learning. arXiv preprint arXiv:2007.01891, 2020

    Pith/arXiv arXiv 2007

  25. [25]

    (more) efficient reinforcement learning via posterior sampling

    Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. InAdvances in Neural Information Processing Systems, pages 3003–3011, 2013

    2013

  26. [26]

    Why is posterior sampling better than optimism for reinforcement learning? InProceedings of the 34th International Conference on Machine Learning-Volume 70

    Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? InProceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017

    2017

  27. [27]

    On optimism in model-based reinforcement learning.arXiv preprint arXiv:2006.11911, 2020

    Aldo Pacchiano, Philip Ball, Jack Parker-Holder, Krzysztof Choromanski, and Stephen Roberts. On optimism in model-based reinforcement learning.arXiv preprint arXiv:2006.11911, 2020

    Pith/arXiv arXiv 2006

  28. [28]

    Nearly horizon-free offline reinforcement learning.Advances in neural information processing systems, 34, 2021

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

    2021

  29. [29]

    Worst-case regret bounds for exploration via randomized value functions

    Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. InAdvances in Neural Information Processing Systems, pages 14433–14443, 2019

    2019

  30. [30]

    Non-asymptotic gap-dependent regret bounds for tabular MDPs

    Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular MDPs. InAdvances in Neural Information Processing Systems, pages 1153–1162, 2019

    2019

  31. [31]

    PAC model-free reinforcement learning

    Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. PAC model-free reinforcement learning. InProceedings of the 23rd international conference on Machine learning, pages 881–888. ACM, 2006. 12

    2006

  32. [32]

    An analysis of model-based interval estimation for markov decision processes.Journal of Computer and System Sciences, 74(8):1309–1331, 2008

    Alexander L Strehl and Michael L Littman. An analysis of model-based interval estimation for markov decision processes.Journal of Computer and System Sciences, 74(8):1309–1331, 2008

    2008

  33. [33]

    Model-based reinforcement learning with nearly tight exploration complexity bounds

    István Szita and Csaba Szepesvári. Model-based reinforcement learning with nearly tight exploration complexity bounds. InICML, 2010

    2010

  34. [34]

    Variance-aware regret bounds for undis- counted reinforcement learning in mdps.arXiv preprint arXiv:1803.01626, 2018

    Mohammad Sadegh Talebi and Odalric-Ambrym Maillard. Variance-aware regret bounds for undis- counted reinforcement learning in mdps.arXiv preprint arXiv:1803.01626, 2018

    Pith/arXiv arXiv 2018

  35. [35]

    Stochastic shortest path: Minimax, parameter-free and towards horizon-free regret.Advances in Neural Information Processing Systems, 34, 2021

    Jean Tarbouriech, Runlong Zhou, Simon S Du, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Stochastic shortest path: Minimax, parameter-free and towards horizon-free regret.Advances in Neural Information Processing Systems, 34, 2021

    2021

  36. [36]

    Is long horizon reinforcement learning more difficult than short horizon reinforcement learning? InAdvances in Neural Information Processing Systems, 2020

    Ruosong Wang, Simon S Du, Lin F Yang, and Sham M Kakade. Is long horizon reinforcement learning more difficult than short horizon reinforcement learning? InAdvances in Neural Information Processing Systems, 2020

    2020

  37. [37]

    Randomized exploration is near-optimal for tabular mdp

    Zhihan Xiong, Ruoqi Shen, and Simon S Du. Randomized exploration is near-optimal for tabular mdp. arXiv preprint arXiv:2102.09703, 2021

    Pith/arXiv arXiv 2021

  38. [38]

    Q-learning with logarithmic regret.arXiv preprint arXiv:2006.09118, 2020

    Kunhe Yang, Lin F Yang, and Simon S Du. Q-learning with logarithmic regret.arXiv preprint arXiv:2006.09118, 2020

    Pith/arXiv arXiv 2006

  39. [39]

    Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon

    Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. InConference on Learning Theory, pages 4528–4531. PMLR, 2021

    2021

  40. [40]

    Horizon-free reinforcement learning in polynomial time: the power of stationary policies

    Zihan Zhang, Xiangyang Ji, and Simon Du. Horizon-free reinforcement learning in polynomial time: the power of stationary policies. InConference on Learning Theory, pages 3858–3904. PMLR, 2022

    2022

  41. [41]

    Variance-aware confidence set: Variance- dependent bound for linear bandits and horizon-free bound for linear mixture mdp

    Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. Variance-aware confidence set: Variance- dependent bound for linear bandits and horizon-free bound for linear mixture mdp. InAdvances in Neural Information Processing Systems, 2021

    2021

  42. [42]

    Almost optimal model-free reinforcement learning via reference-advantage decomposition

    Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. InAdvances in Neural Information Processing Systems, 2020. 13 Appendix In this appendix, we provide the proof of the formal version of Theorem 1 as follows. Theorem 3(Formal statement of Theorem 1).Fix Kě1 . Consider a time-hom...

    2020

  43. [43]

    The horizon-truncation lemma implies that the optimal H-step value is withinOpυqof the optimalH 1-step value

    Truncating the horizon; see Appendix D.1.We first compare the original H-step problem with the truncated H1-step problem. The horizon-truncation lemma implies that the optimal H-step value is withinOpυqof the optimalH 1-step value. Therefore, RegretHpKqďRegret H1pKq`Kυ. With our choice of υ, the truncation loss Kυ is absorbed by the leading rOp ? SAKq ter...

  44. [44]

    The proof is a backward induction on h

    Optimism of Qk h and V k h ; see Appendix D.2 and Appendix E.We prove that the planning procedure is optimistic: with high probability, Qk hps, aq ěQ‹ hps, aqand V k hpsq ěV ‹ hpsq for all episodes k, layers hPrH 1s, states s, and actions a. The proof is a backward induction on h. For ps, aqPO k, optimism holds because the algorithm sets Qk hps, aq“1. For...

  45. [45]

    The process is stopped when the trajectory reaches the unlearned set Ok or when the frozen count of a learned pair doubles

    Stopped regret decomposition; see Appendix D.3.We next decompose the truncated regret using the stopping indicators I k h. The process is stopped when the trajectory reaches the unlearned set Ok or when the frozen count of a learned pair doubles. On the optimism and Bellman-error events, the stopped regret is bounded by the sum of the Bellman-error envelo...

  46. [46]

    This requires a variance closure argument for the optimistic values and the optimistic gaps

    Recursive variance and Bellman-error bounds; see Appendix D.4.The main quantitative step is to bound the accumulated Bellman error B. This requires a variance closure argument for the optimistic values and the optimistic gaps. The ordinary variance terms are controlled by the stopped regret structure, while the clipped-variance terms are controlled by the...

  47. [47]

    V ˚ H1`1

    Bounding the exploration error; see Appendix D.5.Finally, we bound the total stopping cost. The doubling events are controlled by the frozen-count doubling rule and contribute only logarithmic factors. The exploration events are controlled through the explicit exploration analysis of Algorithm 3: once a pairps, aqPO has been effectively explored sufficien...