Pith. sign in

REVIEW 3 major objections 4 minor 57 references

Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs

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

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

Pith's one-line read Episodic RL has a gap-dependent regret bound whose variance term is provably necessary.

desk verdict Strong variance-aware gap-dependent regret bound for MVP, with a real but repairable presentation flaw where a stated lemma is weaker than its proof. read the letter →

arxiv 2506.06521 v1 pith:L625PECA submitted 2025-06-06 cs.LG stat.ML

Shulun Chen , Runlong Zhou , Zihan Zhang , Maryam Fazel , Simon S. Du This is my paper
classification cs.LGstat.ML MSC 68Q3290C40
keywords episodictabularMDPsgap-dependentregretvariance-awareconditionaltotalvarianceMonotonicValuePropagationlowerboundlogarithmicreinforcementlearning
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

Reinforcement learning in episodic tabular MDPs usually carries a worst-case regret of $\widetilde{O}(\sqrt{K})$, but many real instances are easier because some actions are clearly better and the environment is nearly deterministic. This paper claims that a single algorithm, Monotonic Value Propagation (MVP), provably exploits both structures at once: with high probability its regret is $\widetilde{O}\big(\sum_{\Delta_h(s,a)>0} (H^2 \log K \wedge \mathrm{Var}_{\max}^{\mathrm{c}})/\Delta_h(s,a) + \sum_{\Delta_h(s,a)=0} (H^2 \wedge \mathrm{Var}_{\max}^{\mathrm{c}})/\Delta_{\min} + SAH^4(S\vee H) \cdot \log K\big)$. Here $H$ is the horizon and $\Delta_h(s,a)$ is the suboptimality gap of action $a$ at state $s$ and step $h$; the new quantity $\mathrm{Var}_{\max}^{\mathrm{c}}$ is the maximum expected total variance over trajectories conditioned on visiting a particular state at a particular step. The same paper proves a matching lower bound $\Omega\big(\sum_{\Delta_h(s,a)>0} (H^2 \wedge \mathrm{Var}_{\max}^{\mathrm{c}})/\Delta_h(s,a) \cdot \log K\big)$, showing that this conditional variance is unavoidable even when the usual unconditional variance is $O(1)$. If the claims hold, MVP is simultaneously near-optimal in the minimax, variance-dependent, and gap-dependent senses, and the right variance measure for instance-dependent regret is identified.

What carries the argument

The load-bearing object is the maximum conditional total variance, $\mathrm{Var}_{\max}^{\mathrm{c}} := \max_{\pi,s,h} \mathbb{E}_\pi\!\big[\sum_{h'=1}^H \mathrm{Var}^{\ast}_{h'}(s_{h'},a_{h'}) \,\big|\, s_h = s\big]$, where $\mathrm{Var}^{\ast}_h(s,a)$ is the variance of the reward plus the next-state optimal value at tuple $(s,a,h)$. It measures how much randomness the learner faces when trying to learn one particular state-step pair, including pairs that are visited only rarely. The proof machinery has three parts: a surplus decomposition that lower-bounds each suboptimality gap by an expected sum of future clipped surpluses; a weighted-sum argument that multiplies this inequality by the per-tuple variance and uses a Cauchy-Schwarz step to turn a cross-term inequality into the $\sum (H^2 \wedge \mathrm{Var}_{\max}^{\mathrm{c}})/\Delta$ bound; and a concentration lemma showing that, under bounded total reward, any policy's conditional total variance is at most $O(H^2 \log H)$, which supplies the $H^2$ cap in the regret.

What would settle it

Implement MVP on the four-state layered MDP from the lower-bound construction: state $A$ moves to bandit state $B$ with probability $1/(LH)$, state $B$ has actions with success probabilities $1/2 \pm \Delta/4\sqrt{L}$ and rewards $0$ or $\sqrt{L}$, and $C$/$D$ are terminal reward states. With $L \in (1,H^2)$ and small gaps, the paper predicts regret with leading coefficient $\sum_{h,a} L/\Delta_h(B,a)$; the claim fails if the empirical coefficient is smaller, or if an alternative algorithm that only tracks the unconditional variance matches the same regret.

Watch

Extended reading notes

Core claim

The paper's central claim, stated on its own terms, is that the MVP algorithm attains the high-probability regret bound $\widetilde{O}\big(\sum_{\Delta_h(s,a)>0} (H^2 \log K \wedge \mathrm{Var}_{\max}^{\mathrm{c}})/\Delta_h(s,a) + (H^2 \wedge \mathrm{Var}_{\max}^{\mathrm{c}})|Z_{\mathrm{opt}}|/\Delta_{\min} + SAH^4(S\vee H)\log K\big)$, and that the leading term is tight up to logarithmic factors. The lower bound is constructive: for any target conditional variance $L \in [1,H^2]$ and any small gap set, there is an MDP with $\mathrm{Var}_{\max}^{\mathrm{c}} = \Theta(L)$ but $\mathrm{Var}_{\max} = O(1)$, on which every algorithm suffers regret at least $\Omega(\sum_{i:\Delta_i>0} (L/\Delta_i)\log K)$. The construction routes the learner through a bandit state that is visited with probability about $1/L$, so each such state-step pair accumulates $L/\Delta$ regret even though its contribution to unconditional variance is tiny. This establishes the paper's key conclusion: a gap-dependent regret bound written with the unconditional total variance is provably too optimistic, and the conditional variance $\mathrm{Var}_{\max}^{\mathrm{c}}$ — plus the $H^2$ cap on it — is the right object for this problem.

Load-bearing premise

The whole argument assumes Assumption 1, that the total reward collected in any one episode is at most $H$; if only per-step rewards were bounded, the key bound $\mathrm{Var}_{\max}^{\mathrm{c}} = O(H^2 \log H)$ would not follow, and the $H^2$ dependence in the regret bound would break down.

Editorial extensions

If this is right

  • On MDPs where every suboptimality gap $\Delta_h(s,a)$ is bounded away from zero, MVP's regret is at most logarithmic in $K$, so a near-deterministic or well-separated environment is learned much faster than the worst-case $\widetilde{O}(\sqrt{K})$ rate.
  • Since $\mathrm{Var}_{\max}^{\mathrm{c}} \le H Q^*$, the new bound is never worse than earlier variance-aware gap-dependent bounds, and its worst-case $H^2$ factor improves on the $H^3$--$H^6$ prefactors of StrongEuler, Q-learning, AMB, and UCB-Advantage listed in the paper's comparison.
  • The matching lower bound means the leading $\sum (H^2 \wedge \mathrm{Var}_{\max}^{\mathrm{c}})/\Delta_h(s,a)$ term cannot be replaced by a term based on $\mathrm{Var}_{\max}$; rare high-variance state-step pairs are the reason.
  • The $\Delta_{\min}$ term of the upper bound now carries a worst-case coefficient $H^2 \wedge \mathrm{Var}_{\max}^{\mathrm{c}}$, improving on the $H Q^*$ and $H^3 Q^*$ coefficients of previous gap-dependent analyses.
  • The weighted-sum-of-gaps technique itself is independent of MVP's details, so the same proof route should yield variance-aware gap-dependent bounds for other optimistic or model-free algorithms.

Reading between the lines

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

  • The upper bound uses $H^2 \log K \wedge \mathrm{Var}_{\max}^{\mathrm{c}}$ while the lower bound is $H^2 \wedge \mathrm{Var}_{\max}^{\mathrm{c}}$; in the regime $\mathrm{Var}_{\max}^{\mathrm{c}} \in [H^2, H^2\log K]$ the extra logarithmic factor is likely removable by a more careful concentration or clipping argument.
  • Remark 2 of the paper suggests excluding hard-to-reach states from $\mathrm{Var}_{\max}^{\mathrm{c}}$; making that exclusion formal would shrink the bound further and is a natural next step.
  • The lower-bound construction implies that exploration should be tuned per state-step pair, in proportion to conditional variance divided by gap, rather than by a single global variance estimate; this is a practical design rule the paper does not state.
  • The Cauchy-Schwarz step in the proof does not use the tabular transition structure in an essential way, so the weighted-sum technique is a credible route to variance-aware gap-dependent bounds for linear MDPs and general function classes.
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 / 4 minor

Summary. The paper studies gap-dependent regret for episodic tabular MDPs with bounded total reward per trajectory (Assumption 1). It analyzes the MVP algorithm and claims an upper bound whose leading term is O( (H^2 log K ∧ Var^c_max)/Δ + (H^2 ∧ Var^c_max)|Zopt|/Δ_min + SAH^4(S∨H) ) log K, where Var^c_max is a newly introduced maximum conditional total variance. It also proves a lower bound showing that dependence on Var^c_max is necessary, even when the unconditional variance Var_max is O(1). The proof proceeds by clipping surpluses, bounding weighted sums of suboptimality gaps, and then applying concentration and martingale arguments.

Significance. If the central technical claim were fully established, the paper would make a meaningful contribution: it introduces a variance metric that is finer than the per-step variance Q* used in prior gap-dependent bounds, it improves the worst-case H-dependence in the gap-dependent terms to H^2, and it gives a lower bound separating Var^c_max from Var_max. The weighted-sum-of-gaps analysis is a promising and potentially transferable technique, and the paper is explicit about the assumptions and the algorithm's constants. However, the upper-bound proof as written has a load-bearing gap in the control of conditional total variance, so the significance of the result is contingent on repairing that step.

major comments (3)
  1. [Section 3, Definition 2; Remark 2; Corollary 4; Lemma 8] There is a direct internal contradiction about the magnitude of Var^c_max. Corollary 4 and Lemma 8 show that, for every policy π and every (h,s), the conditional expected total variance is at most 160 H^2 (log(4(H+1))+1), which is O(H^2 log H). Taking the maximum over π,h,s in Definition 2 therefore gives Var^c_max = O(H^2 log H) under Assumption 1. Remark 2, however, states that Var^c_max can be as large as Θ(H^3). These two statements cannot both be correct. The authors must either correct Remark 2 or restrict/add to the definition; if Var^c_max is always O(H^2 log H), the claimed improvement over the prior HQ* ≤ H^3 dependence is still real but should be stated with the correct bound.
  2. [Section B.1, Eq. (10), Lemma 10] Lemma 10 is the key bridge from the clipped surplus analysis to the final regret decomposition, but its proof uses an inequality that the cited results do not provide. The proof requires Eπ[∑_{h'=h}^H Var*_{h'}(s_{h'},a_{h'}) | s_h=s] ≤ H^2 ∧ Var^c_max, citing 'Theorem 4' (presumably Corollary 4) and the definition of Var^c_max. Corollary 4 only gives the bound 160 H^2(log(4(H+1))+1), which is larger than H^2 by a logarithmic factor. If instead Remark 2 is taken seriously and Var^c_max = Θ(H^3), then H^2∧Var^c_max = H^2 and the printed Corollary 4 is again insufficient. In both readings, the subtraction in Eq. (10) can be a factor Ω(log H) too large, so the conclusion V̄^k_h(s) ≥ V^k_h(s) − Δ_min/3 is not established. Since Lemmas 11–13 and the final regret bound in Theorem 5 all depend on Lemma 10, the upper bound is not proved as written. A sharper O(H^2) conditional total variance bound is needed, or the clipping threshold must be adjusted and the extra logarithmic factor absorbed explicitly.
  3. [Corollary 4 proof, Eq. (7)] The proof of Corollary 4 also needs clarification. The expression V*_{h1'}(s_{h1'}, a_{h1'}) is undefined as written; it appears to be a typo for Q*. More importantly, the step labeled (7) replaces Q* by V*_h, which changes the sum by the nonnegative sum of suboptimality gaps, and no argument is given for why the squared expectation remains an upper bound after this replacement. Because Corollary 4 is the cited justification for the critical bound in Lemma 10, this derivation should be written out carefully or replaced with a precise citation to the corresponding lemma in Zhou et al. [2023].
minor comments (4)
  1. [Section 5, Discussion] In the sentence 'This example shows a separation between unconditional variance Var^c_max and conditional variance Var_max', the two variance names are swapped: Var^c_max is the conditional quantity and Var_max is the unconditional quantity. The sentence should be corrected.
  2. [Section 3, Definition 2] Definition 2 sums h1' from 1 to H while Corollary 4 and Lemma 8 condition on s_h=s and sum from h to H. The definition should clarify whether past steps are included, because the distinction affects the claimed bound on Var^c_max and the contradiction in Remark 2.
  3. [Section 4.3, proof sketch] The proof sketch refers to 'Cauchy-Schwartz'; the standard spelling is 'Cauchy-Schwarz'. Also, the transition from Eq. (6) to the displayed inequality involving R^2 is abbreviated to the point of being difficult to follow; a reference to the formal derivation in Section B.4 would help.
  4. [Lemma 10] Lemma 10 cites 'Theorem 4', but there is no Theorem 4 in the paper; the intended reference is Corollary 4. The cross-reference should be fixed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the upper bound is a first-principles regret analysis and the lower bound uses an external bandit result; the flagged Lemma 10 issue is a proof gap, not a circular step.

full rationale

The upper bound is a self-contained derivation for the previously proposed MVP algorithm. Regret is decomposed via surpluses, the optimism property of MVP (Lemma 9) is imported from the authors' prior analysis, and the weighted-gap argument in Section B.4 converts concentration inequalities and variance definitions into the final bound. No parameter is fitted to the regret quantity and no prediction is statistically forced by an earlier fit. The self-citations to Zhang et al. [2024] for optimism and Zhou et al. [2023] for total-variance concentration are independent results with stated assumptions that do not include the target gap-dependent regret bound; under the review rules these are real evidence, not circularity. The lower bound (Theorem 3/6) reduces a constructed MDP to Bernoulli bandits and invokes the external Lai-Robbins lower bound, so the L/Delta log K dependence is argued rather than assumed. I therefore find no circular step. I do flag, as a correctness risk rather than a circularity, the skeptic-identified gap in Section B.1: Lemma 10 requires the expected conditional future total variance to be at most order H^2 (specifically, to subtract the Delta_min/6 clipping loss), but the printed Corollary 4 establishes only O(H^2 log H), and Remark 2 allows Var_c_max to be as large as Theta(H^3). This is a possible missing proof or a slack bound, not an equivalence between input and output, so it does not raise the circularity score. The paper also honestly acknowledges that the |Zopt|(H^2 ^ Var_c_max)/Delta_min term is unmatched by the lower bound, which further indicates that the claimed result is not engineered to be tautological.

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

The proof rests on the bounded-total-reward assumption, standard concentration inequalities, the inherited optimism property of MVP, and the Lai-Robbins bandit lower bound. No free parameters are fitted to data; the hand-chosen constants in Algorithm 1 are standard and do not affect the asymptotic bound.

free parameters (1)
  • Algorithm constants c1, c2, c3 = c1=2, c2=2, c3=10
    Hand-chosen constants in the MVP bonus term (Algorithm 1). The proof needs c3 >= c1^2 for optimism; the asymptotic result does not depend on their exact values.
assumptions (5)
  • domain assumption Assumption 1: total reward of any trajectory is at most H
    Used throughout the proof to bound the variance of the value function and to establish Var^c_max <= O(H^2 log H) via the martingale concentration in Lemma 8. Invoked in Section 3 and Appendix B.
  • standard math Standard concentration inequalities (Bennett, Freedman, empirical Bernstein)
    State high-probability bounds for estimates of rewards, transitions, and variances in Lemma 6.
  • domain assumption Optimism property of MVP (Lemma 9) established in Zhang et al. 2024/2021a
    The analysis assumes Q_k and V_k are optimistic upper bounds with high probability; the proof is cited from prior work by the same authors.
  • standard math Lai-Robbins lower bound for multi-armed bandits
    Core external benchmark used in the lower bound construction (Section 5 and Appendix C).
  • domain assumption Realizability and smallness conditions on the lower-bound gaps (|I| >= SH and Delta_i < sqrt(L))
    Assumptions in Theorem 6 that ensure the constructed MDP has the intended gap structure and the bandit reduction applies.
invented entities (1)
  • Maximum conditional total variance Var^c_max
    purpose: New problem-dependent quantity used in the regret bound; the upper bound scales with it and the lower bound shows it is necessary.
    A math definition, not a physical entity. Its main justification is the paper's own lower bound, not an external falsifiable prediction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs." pith.science (2026). https://pith.science/paper/L625PECA

@misc{pith2026250606521,
  author       = {Pith},
  title        = {Pith review of: Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L625PECA}},
  note         = {Machine review of arXiv:2506.06521}
}
abstract

We consider the gap-dependent regret bounds for episodic MDPs. We show that the Monotonic Value Propagation (MVP) algorithm achieves a variance-aware gap-dependent regret bound of $$\tilde{O}\left(\left(\sum_{\Delta_h(s,a)>0} \frac{H^2 \log K \land \mathtt{Var}_{\max}^{\text{c}}}{\Delta_h(s,a)} +\sum_{\Delta_h(s,a)=0}\frac{ H^2 \land \mathtt{Var}_{\max}^{\text{c}}}{\Delta_{\mathrm{min}}} + SAH^4 (S \lor H) \right) \log K\right),$$ where $H$ is the planning horizon, $S$ is the number of states, $A$ is the number of actions, and $K$ is the number of episodes. Here, $\Delta_h(s,a) =V_h^* (a) - Q_h^* (s, a)$ represents the suboptimality gap and $\Delta_{\mathrm{min}} := \min_{\Delta_h (s,a) > 0} \Delta_h(s,a)$. The term $\mathtt{Var}_{\max}^{\text{c}}$ denotes the maximum conditional total variance, calculated as the maximum over all $(\pi, h, s)$ tuples of the expected total variance under policy $\pi$ conditioned on trajectories visiting state $s$ at step $h$. $\mathtt{Var}_{\max}^{\text{c}}$ characterizes the maximum randomness encountered when learning any $(h, s)$ pair. Our result stems from a novel analysis of the weighted sum of the suboptimality gap and can be potentially adapted for other algorithms. To complement the study, we establish a lower bound of $$\Omega \left( \sum_{\Delta_h(s,a)>0} \frac{H^2 \land \mathtt{Var}_{\max}^{\text{c}}}{\Delta_h(s,a)}\cdot \log K\right),$$ demonstrating the necessity of dependence on $\mathtt{Var}_{\max}^{\text{c}}$ even when the maximum unconditional total variance (without conditioning on $(h, s)$) approaches zero.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

57 extracted references · 41 canonical work pages

  1. [1]

    Navigating to the best policy in markov decision processes

    Aymen Al Marjani, Aur \'e lien Garivier, and Alexandre Proutiere. Navigating to the best policy in markov decision processes. Advances in Neural Information Processing Systems, 34: 0 25852--25864, 2021

    work page 2021

  2. [2]

    Logarithmic online regret bounds for undiscounted reinforcement learning

    Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. Advances in neural information processing systems, 19, 2006

    2006

  3. [3]

    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: 0 235--256, 2002

    work page 2002

  4. [4]

    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

  5. [5]

    Minimax regret bounds for reinforcement learning

    Mohammad Gheshlaghi Azar, Ian Osband, and R \'e mi Munos. Minimax regret bounds for reinforcement learning. In International conference on machine learning, pages 263--272. PMLR, 2017

    2017

  6. [6]

    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. arXiv preprint arXiv:1205.2661, 2012

    arXiv 2012

  7. [7]

    Regret analysis of stochastic and nonstochastic multi-armed bandit problems

    S \'e bastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning , 5 0 (1): 0 1--122, 2012

    2012

  8. [8]

    Top-k off-policy correction for a reinforce recommender system

    Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H Chi. Top-k off-policy correction for a reinforce recommender system. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 456--464, 2019

    work page 2019

Show all 57 references
  1. [9]

    Variance-aware sparse linear bandits

    Yan Dai, Ruosong Wang, and Simon S Du. Variance-aware sparse linear bandits. arXiv preprint arXiv:2205.13450, 2022

    2022 arXiv

  2. [10]

    Policy certificates: Towards accountable reinforcement learning

    Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learning, pages 1507--1516. PMLR, 2019

    2019

  3. [11]

    Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning

    Christoph Dann, Teodor Vanislavov Marinov, Mehryar Mohri, and Julian Zimmert. Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34: 0 1--12, 2021

    2021

  4. [12]

    Gap-dependent bounds for two-player markov games

    Zehao Dou, Zhuoran Yang, Zhaoran Wang, and Simon Du. Gap-dependent bounds for two-player markov games. In International Conference on Artificial Intelligence and Statistics, pages 432--455. PMLR, 2022

    2022

  5. [13]

    Cascaded gaps: Towards logarithmic regret for risk-sensitive reinforcement learning

    Yingjie Fei and Ruitu Xu. Cascaded gaps: Towards logarithmic regret for risk-sensitive reinforcement learning. In International Conference on Machine Learning, pages 6392--6417. PMLR, 2022

    2022

  6. [14]

    Efficient bias-span-constrained exploration-exploitation in reinforcement learning

    Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-span-constrained exploration-exploitation in reinforcement learning. In International Conference on Machine Learning, pages 1578--1586. PMLR, 2018

    2018

  7. [15]

    Logarithmic regret for reinforcement learning with linear function approximation

    Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 4171--4180. PMLR, 2021

    2021

  8. [16]

    Tackling heavy-tailed rewards in reinforcement learning with function approximation: Minimax optimal and instance-dependent regret bounds

    Jiayi Huang, Han Zhong, Liwei Wang, and Lin Yang. Tackling heavy-tailed rewards in reinforcement learning with function approximation: Minimax optimal and instance-dependent regret bounds. Advances in Neural Information Processing Systems, 36: 0 56576--56588, 2023

    2023

  9. [17]

    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

  10. [18]

    Reward-free exploration for reinforcement learning

    Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870--4879. PMLR, 2020

    2020

  11. [19]

    Planning in markov decision processes with gap-dependent sample complexity

    Anders Jonsson, Emilie Kaufmann, Pierre M \'e nard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning in markov decision processes with gap-dependent sample complexity. Advances in Neural Information Processing Systems, 33: 0 1253--1263, 2020

    2020

  12. [20]

    Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture mdps

    Yeoneung Kim, Insoon Yang, and Kwang-Sung Jun. Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture mdps. Advances in Neural Information Processing Systems, 35: 0 1060--1072, 2022

    2022

  13. [21]

    Asymptotically efficient adaptive allocation rules

    Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6 0 (1): 0 4--22, 1985

    1985

  14. [22]

    Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning

    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: 0 17762--17776, 2021

    2021

  15. [23]

    Continuous control with deep reinforcement learning

    Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971, 2015

    2015 arXiv

  16. [24]

    Deep reinforcement learning for dynamic treatment regimes on medical registry data

    Ying Liu, Brent Logan, Ning Liu, Zhiyuan Xu, Jian Tang, and Yangzhi Wang. Deep reinforcement learning for dynamic treatment regimes on medical registry data. In 2017 IEEE international conference on healthcare informatics (ICHI), pages 380--385. IEEE, 2017

    2017

  17. [25]

    Best policy identification in discounted mdps: Problem-specific sample complexity

    AA Marjani and Alexandre Proutiere. Best policy identification in discounted mdps: Problem-specific sample complexity. arXiv preprint arXiv:2009.13405, 2020

    2009 arXiv

  18. [26]

    Empirical bernstein bounds and sample variance penalization

    Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.3740, 2009

    2009 arXiv

  19. [27]

    Ucb momentum q-learning: Correcting the bias without forgetting

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

    2021

  20. [28]

    Reinforcement learning for optimized trade execution

    Yuriy Nevmyvaka, Yi Feng, and Michael Kearns. Reinforcement learning for optimized trade execution. In Proceedings of the 23rd international conference on Machine learning, pages 673--680, 2006

    2006

  21. [29]

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

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

    2023

  22. [30]

    Exploration in structured reinforcement learning

    Jungseul Ok, Alexandre Proutiere, and Damianos Tranos. Exploration in structured reinforcement learning. Advances in Neural Information Processing Systems, 31, 2018

    2018

  23. [31]

    Why is posterior sampling better than optimism for reinforcement learning? In International conference on machine learning, pages 2701--2710

    Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International conference on machine learning, pages 2701--2710. PMLR, 2017

    2017

  24. [32]

    Reinforcement learning in linear mdps: Constant regret and representation selection

    Matteo Papini, Andrea Tirinzoni, Aldo Pacchiano, Marcello Restelli, Alessandro Lazaric, and Matteo Pirotta. Reinforcement learning in linear mdps: Constant regret and representation selection. Advances in Neural Information Processing Systems, 34: 0 16371--16383, 2021

    2021

  25. [33]

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

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

    2016

  26. [34]

    Non-asymptotic gap-dependent regret bounds for tabular mdps

    Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32, 2019

    2019

  27. [35]

    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

  28. [36]

    Variance-aware regret bounds for undiscounted reinforcement learning in mdps

    Mohammad Sadegh Talebi and Odalric-Ambrym Maillard. Variance-aware regret bounds for undiscounted reinforcement learning in mdps. In Algorithmic Learning Theory, pages 770--805. PMLR, 2018

    2018

  29. [37]

    Optimistic linear programming gives logarithmic regret for irreducible mdps

    Ambuj Tewari and Peter Bartlett. Optimistic linear programming gives logarithmic regret for irreducible mdps. Advances in Neural Information Processing Systems, 20, 2007

    2007

  30. [38]

    Near instance-optimal pac reinforcement learning for deterministic mdps

    Andrea Tirinzoni, Aymen Al Marjani, and Emilie Kaufmann. Near instance-optimal pac reinforcement learning for deterministic mdps. Advances in neural information processing systems, 35: 0 8785--8798, 2022

    2022

  31. [39]

    Optimistic pac reinforcement learning: the instance-dependent view

    Andrea Tirinzoni, Aymen Al-Marjani, and Emilie Kaufmann. Optimistic pac reinforcement learning: the instance-dependent view. In International Conference on Algorithmic Learning Theory, pages 1460--1480. PMLR, 2023

    2023

  32. [40]

    Reinforcement learning with logarithmic regret and policy switches

    Grigoris Velegkas, Zhuoran Yang, and Amin Karbasi. Reinforcement learning with logarithmic regret and policy switches. Advances in Neural Information Processing Systems, 35: 0 36040--36053, 2022

    2022

  33. [41]

    Instance-dependent near-optimal policy identification in linear mdps via online experiment design

    Andrew Wagenmaker and Kevin G Jamieson. Instance-dependent near-optimal policy identification in linear mdps via online experiment design. Advances in Neural Information Processing Systems, 35: 0 5968--5981, 2022

    2022

  34. [42]

    First-order regret in reinforcement learning with linear function approximation: A robust estimation approach

    Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. First-order regret in reinforcement learning with linear function approximation: A robust estimation approach. In International Conference on Machine Learning, pages 22384--22429. PMLR, 2022 a

    2022

  35. [43]

    Beyond no regret: Instance-dependent pac reinforcement learning

    Andrew J Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond no regret: Instance-dependent pac reinforcement learning. In Conference on Learning Theory, pages 358--418. PMLR, 2022 b

    2022

  36. [44]

    On gap-dependent bounds for offline reinforcement learning

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

    2022

  37. [45]

    Near-optimal randomized exploration for tabular markov decision processes

    Zhihan Xiong, Ruoqi Shen, Qiwen Cui, Maryam Fazel, and Simon S Du. Near-optimal randomized exploration for tabular markov decision processes. Advances in neural information processing systems, 35: 0 6358--6371, 2022

    2022

  38. [46]

    Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap

    Haike Xu, Tengyu Ma, and Simon Du. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. In Conference on Learning Theory, pages 4438--4472. PMLR, 2021

    2021

  39. [47]

    Q-learning with logarithmic regret

    Kunhe Yang, Lin Yang, and Simon Du. Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, pages 1576--1584. PMLR, 2021

    2021

  40. [48]

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

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

    2019

  41. [49]

    Regret minimization for reinforcement learning by evaluating the optimal bias function

    Zihan Zhang and Xiangyang Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function. Advances in Neural Information Processing Systems, 32, 2019

    2019

  42. [50]

    Almost optimal model-free reinforcement learningvia reference-advantage decomposition

    Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference-advantage decomposition. Advances in Neural Information Processing Systems, 33: 0 15198--15207, 2020

    2020

  43. [51]

    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. In Conference on Learning Theory, pages 4528--4531. PMLR, 2021 a

    2021

  44. [52]

    Improved variance-aware confidence sets for linear bandits and linear mixture mdp

    Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34: 0 4342--4355, 2021 b

    2021

  45. [53]

    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. In Conference on Learning Theory, pages 3858--3904. PMLR, 2022

    2022

  46. [54]

    Settling the sample complexity of online reinforcement learning

    Zihan Zhang, Yuxin Chen, Jason D Lee, and Simon S Du. Settling the sample complexity of online reinforcement learning. In The Thirty Seventh Annual Conference on Learning Theory, pages 5213--5219. PMLR, 2024

    2024

  47. [55]

    Gap-dependent bounds for q-learning using reference-advantage decomposition

    Zhong Zheng, Haochen Zhang, and Lingzhou Xue. Gap-dependent bounds for q-learning using reference-advantage decomposition. arXiv preprint arXiv:2410.07574, 2024

    2024 arXiv

  48. [56]

    Nearly minimax optimal reinforcement learning for linear mixture markov decision processes

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

    2021

  49. [57]

    Sharp variance-dependent bounds in reinforcement learning: Best of both worlds in stochastic and deterministic environments

    Runlong Zhou, Zhang Zihan, and Simon Shaolei Du. Sharp variance-dependent bounds in reinforcement learning: Best of both worlds in stochastic and deterministic environments. In International Conference on Machine Learning, pages 42878--42914. PMLR, 2023

    2023

Pith tools

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