Pith. sign in

REVIEW 3 major objections 4 minor 39 references

Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates

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

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

Pith's one-line read Any constant learning rate drives stochastic gradient bandits to the optimal arm

desk verdict A plausible and clearly written extension that would be a strong result, but the central proof invokes an eventual-dominance limit that Lemma 5 does not establish; as written, the main theorem is not proven. read the letter →

arxiv 2502.07141 v1 pith:5UKTH5YG submitted 2025-02-11 cs.LG

Jincheng Mei , Bo Dai , Alekh Agarwal , Sharan Vaswani , Anant Raj , Csaba Szepesvari , Dale Schuurmans This is my paper · ORCID
classification cs.LG MSC 68Q3262L20
keywords stochasticgradientbanditssoftmaxpolicyconstantlearningratemulti-armedalmostsureconvergenceexploration-exploitationREINFORCEnon-convexoptimization
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 proves that the stochastic gradient bandit algorithm—the softmax policy-gradient update applied to a multi-armed bandit—converges almost surely to the globally optimal policy for every constant learning rate $\eta>0$, not just small ones. Prior theory required decaying or sufficiently small step sizes to control gradient noise and smoothness. The new argument shows the algorithm always explores in a minimal sense: with probability one it never samples a single action forever, and at least two actions are sampled infinitely often. From there, the paper proves by contradiction that the optimal arm must be sampled infinitely often and that the probabilities of all sub-optimal arms decay to zero. Because the learning rate is the only hyperparameter of the algorithm, the result means no step-size tuning is needed for asymptotic optimality.

What carries the argument

The paper's central objects are the sampling counts $N_t(a)$ and the softmax probability ratios $\pi_t(i)/\pi_t(j)$. The extended Borel-Cantelli lemma ties $N_\infty(a)=\infty$ to divergence of $\sum_t \pi_t(a)$, letting the authors reason about exploration through probabilities alone. A ratio-explosion lemma (Lemma 5) is then combined with a 'sandwich' lemma (Lemma 6) showing the expected reward $\pi_{\theta_t}^\top r$ eventually lies between the best and worst infinitely-sampled actions. The convergence argument itself uses a progress/noise decomposition: $\theta_t(a)$ is written as cumulative expected updates plus a martingale noise term, with Freedman's inequality controlling the noise so that cumulative progress dominates.

What would settle it

Run Algorithm 1 with $K=3$, distinct rewards, and a very large constant $\eta$ while tracking the probability ratios between an action sampled infinitely often and one sampled finitely often; a path with positive probability on which this ratio has infinite supremum but does not converge to $\infty$ would break Lemma 6's sandwich bound and the recursive step of Theorem 2. More directly, a counterexample to the claimed strengthening of Lemma 5—two softmax sequences with $N_\infty(i)=\infty$, $N_\infty(j)<\infty$, and $\limsup \pi_i/\pi_j=\infty$ but $\liminf$ finite—would show the proof needs an additional argument.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2: under Assumption 1 (distinct mean rewards), Algorithm 1 with any constant learning rate $\eta>0$ satisfies $\pi_{\theta_t}(a^*)\to 1$ almost surely, where $a^*$ is the best arm. The proof first establishes Lemma 2, that at least two actions are sampled infinitely often, so the algorithm cannot permanently commit to one arm no matter how large $\eta$ is. It then rules out the possibility that the optimal action is sampled only finitely often using a contradiction based on the ratio of probabilities between an infinitely-sampled sub-optimal action and the optimal action. Once $N_\infty(a^*)=\infty$ is known, the argument shows recursively that the worst infinitely-sampled sub-optimal action, then the next, and so on, drift to $-\infty$ in parameter space while $\theta_t(a^*)\to\infty$, forcing every sub-optimal probability ratio to zero. The paper also derives an $O(\log T/T)$ bound on average sub-optimality after a burn-in time.

Load-bearing premise

The proof needs the property that when one action is sampled infinitely often and another only finitely often, the ratio of their probabilities eventually grows without bound, but the stated lemma proves only that the supremum of that ratio is infinite, not that the ratio itself tends to infinity.

Editorial extensions

If this is right

  • Any constant learning rate is asymptotically safe: no schedule, decay, or problem-specific small step size is needed for the gradient bandit to reach the optimal policy almost surely.
  • Large constant learning rates do not cause the failure mode seen in natural or normalized policy gradient, where the algorithm can commit to a sub-optimal arm with positive probability.
  • After a finite burn-in time, the averaged sub-optimality gap decays as $O(\log T/T)$ regardless of the constant learning rate used.
  • The probability of sampling sub-optimal arms tends to zero even though, by Lemma 2, at least one sub-optimal arm is sampled infinitely often.

Reading between the lines

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

  • Beyond the paper: the distinct-mean-rewards assumption may be removable, since the authors note that in the exact-gradient setting the set of initializations approaching tied softmax policies has measure zero.
  • Beyond the paper: the plateau behavior seen for large learning rates suggests a time-dependent schedule that starts small and increases the learning rate later could combine fast early progress with fast final convergence; the authors raise this as an open question.
  • Beyond the paper: if the asymptotic rate depends on $1/\eta$ as the simulations suggest, then very large learning rates trade longer transient plateaus for sharper final convergence, implying a two-stage analysis is needed to predict actual performance.
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 the softmax-parameterized stochastic gradient bandit algorithm (Algorithm 1) and claims that, for any constant learning rate eta > 0, the policy converges almost surely to the globally optimal one-hot policy. The main technical contributions are: (i) a proof that the algorithm cannot sample a single action forever (Lemma 2); (ii) a proof for the two-action case (Theorem 1); (iii) a recursive contradiction argument for general K using the set of infinitely sampled actions A_infty (Theorem 2); and (iv) an averaged suboptimality rate O(log T / T) (Theorem 3). The proof is built around a progress/noise decomposition and several supporting lemmas on sampling counts and softmax ratios. The paper also presents simulations with K = 4 arms for learning rates eta in {1,10,100,1000} showing convergence in most runs, with occasional long plateaus for large eta.

Significance. If the main theorem is correct, it is a significant result: it removes learning-rate tuning as a requirement for asymptotic optimality of a basic stochastic gradient bandit method, in a regime where standard smoothness-based and noise-control arguments do not apply. The proof strategy based on sampling counts and cumulative progress versus cumulative noise is promising, and the paper is largely self-contained: it introduces no fitted constants or tuned parameters, relies on standard concentration inequalities (Freedman's inequality and the extended Borel-Cantelli lemma), and the K = 2 proof (Theorem 1) is a clean application of the progress/noise framework. The simulations align qualitatively with the claimed convergence, while also honestly displaying long plateaus for large learning rates. However, the general-K proof currently has a load-bearing gap: Lemma 5 is too weak for the way it is used, and the gap propagates through Lemma 6 and Theorem 2. For this reason the central claim is not established as written, although the result may well be true and fixable.

major comments (3)
  1. [Appendix B, Lemma 5] Lemma 5 proves only that sup_t pi_t(i)/pi_t(j) = infinity when N_infty(i)=infinity and N_infty(j)<infinity; its contradiction argument does not show that the ratio tends to infinity. However, Lemma 6 and Theorem 2 repeatedly use the stronger eventual-dominance statement. In particular, Eq. (143) states that pi_t(a*)/pi_t(a^-) -> infinity for every a^- in A^-(i2), and Eq. (145) bounds the reciprocal by a small constant for all sufficiently large t. These claims are not consequences of Lemma 5. A softmax sequence with pi_j ~ 2^{-t} and pi_i taking large values only on sparse blocks satisfies N_infinity(i)=infinity, N_infinity(j)<infinity, and sup ratio = infinity, while the ratio has liminf 0, so every eventual bound used later fails. The manuscript does not rule out such behavior under Algorithm 1; therefore the proof is incomplete at this load-bearing step.
  2. [Appendix B, Lemma 6 and Section 3.4] Lemma 6 is the tool that produces the sandwich r(i1) < pi^T_theta_t r < r(i2) for all sufficiently large t. Its proof relies on the same unproved eventual-dominance property in Eqs. (177)-(179) and (184)-(186). Lemma 6 is then invoked in both cases of Theorem 2: in the first case to obtain Eq. (92), and in the second case to obtain Eq. (120) and to run the recursive argument culminating in Eqs. (146)-(149). Since Lemma 6 is not established, the recursive escalation from i1 to i2 to i3 in the proof of Theorem 2 is unsupported. The central claim for K > 2 therefore does not follow from the written proof, even though the K = 2 argument does not use Lemma 5 and appears unaffected.
  3. [Appendix C, Theorem 3] Theorem 3 inherits the gap in Theorem 2. Its proof begins by invoking Theorem 2 to assert that pi_t(a*) -> 1, and Eq. (251) then uses this convergence to derive the O(log T / T) averaged bound. Because Theorem 2 is not established for general K without the missing eventual-dominance lemma, the rate result is likewise conditional on the same fix. I would treat Theorem 3 as a consequence to be revisited after the main convergence proof is repaired.
minor comments (4)
  1. [Throughout] The notation eta in Theta(1) is nonstandard here: the statement and proofs consider an arbitrary positive constant learning rate, not a rate that is bounded both above and below. Using 'any constant eta > 0' directly would avoid confusion.
  2. [Appendix D, Figure 2 caption] The caption says 'Figures 2a and 2a are based on a single run'; the second reference should likely be '2b', and the text around Figure 2b should be checked for consistency.
  3. [Appendix B, Lemmas 8-10] The proofs of Lemmas 8-10 handle the confidence event E1 in a somewhat informal way, writing that for a fixed omega there exists a delta such that omega is in E1. A rigorous treatment should choose a countable sequence delta_n down to 0 and apply a union bound so that the conclusion holds almost surely on the event N_infinity(a)=infinity; this is a presentation issue rather than a substantive gap.
  4. [Section 4] The discussion of the trade-off between large and small learning rates is useful, but the claim that larger eta gives faster final-stage convergence is based only on the displayed runs; the paper does not provide a quantitative analysis of the plateau length or the final-stage rate. Adding a few summary statistics across seeds would strengthen the empirical section.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence proof is self-contained given standard concentration inequalities, and the self-citations to prior work are for standard identities and supporting lemmas, not for the target result.

full rationale

The paper's central claim, Theorem 2, is not assumed in its inputs: Assumption 1 only rules out tied reward means, and Algorithm 1 is defined independently of the claimed limit. The proof introduces no fitted constants or data-dependent parameters; the learning rate is arbitrary and the analysis is asymptotic. The progress/noise decomposition follows the authors' earlier papers, but it is re-derived here: Lemma 7 proves the needed concentration bound from Freedman's inequality (Lemma 4), which is cited both to the external sources [10, 7] and to the authors' [24, Theorem C.3], so the self-citation is not the only support. Proposition 1 is a standard importance-sampling identity. Lemmas 8-12 are technical consequences of this concentration bound and the softmax parameterization. The only substantive concern is that Lemma 5 proves only sup_t \pi_t(i)/\pi_t(j)= \infty when N_\infty(i)=\infty and N_\infty(j)<\infty, whereas Lemma 6 and the proof of Theorem 2 repeatedly use stronger eventual inequalities such as \pi_t(a^-)/\pi_t(i_2) being uniformly small for large t. That is an unproved strengthening and a correctness gap, but it is not circularity: the desired limit is not included in the hypotheses, and no fitted quantity or self-citation forces the conclusion. The stated limitations (Assumption 1, the bandit-only setting, and the open learning-rate characterization) are explicit and do not smuggle in the result. Overall, the derivation has independent content and no load-bearing circular step.

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

There are no fitted constants or invented physical or algorithmic entities. The proof is parameter-free given the softmax parameterization and bounded-reward assumption. The main extra load-bearing premise is the implicit eventual-dominance property of probability ratios, which is not established by the lemma cited for it.

assumptions (4)
  • domain assumption True mean rewards of distinct actions are unequal (Assumption 1).
    Needed for strict inequalities in Eq. (17) and the definition of Delta in Eq. (106). The authors note in Remark 1 that removing this assumption is open.
  • domain assumption Rewards are bounded in [-Rmax, Rmax] and have densities with respect to a finite measure (Eq. 1).
    Used for the bounded-noise martingale concentration in Lemma 7 and throughout the proofs. The simulation uses Gaussian rewards with unbounded support, which the paper acknowledges does not technically satisfy this assumption.
  • ad hoc to paper Eventual dominance of infinitely-sampled actions over finitely-sampled actions in probability ratio.
    Used in Lemma 6 and Theorem 2 as if Lemma 5 implied a limit of pi(i)/pi(j) -> infinity. Lemma 5 as stated only gives an unbounded supremum, so this is an unproved strengthening that the central proof depends on.
  • standard math Standard probability tools: extended Borel-Cantelli lemma and Freedman's inequality.
    These are invoked as Lemmas 3 and 4 and are standard results. They are not specific to this paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates." pith.science (2026). https://pith.science/paper/5UKTH5YG

@misc{pith2026250207141,
  author       = {Pith},
  title        = {Pith review of: Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5UKTH5YG}},
  note         = {Machine review of arXiv:2502.07141}
}
read the original abstract

We provide a new understanding of the stochastic gradient bandit algorithm by showing that it converges to a globally optimal policy almost surely using \emph{any} constant learning rate. This result demonstrates that the stochastic gradient algorithm continues to balance exploration and exploitation appropriately even in scenarios where standard smoothness and noise control assumptions break down. The proofs are based on novel findings about action sampling rates and the relationship between cumulative progress and noise, and extend the current understanding of how simple stochastic gradient methods behave in bandit settings.

Figures

Figures reproduced from arXiv: 2502.07141 by the authors.

Figure 1
Figure 1. Log sub-optimality gap, log (r(a ∗ ) − π ⊤ θt r), plotted against the logarithm of time, log t, in a 4-action problem with various learning rates, η. Each subplot shows a run with a specific learning rate. The curves in a subplot correspond to 10 different random seeds. Theory predicts that essentially all seeds will lead to a curve converging to zero (−∞ in these plots). For a discussion of the results, see the tex… view at source ↗
Figure 2
Figure 2. Visualization in a two-action stochastic bandit problem. Here the rewards are defined as [PITH_FULL_IMAGE:figures/full_fig_p034_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 28 canonical work pages

  1. [24]

    Stochastic Gradient Succeeds for Bandits

    Jincheng Mei, Zixin Zhong, Bo Dai, Alekh Agarwal, Csaba Szepesvari, and Dale Schuurmans. Stochastic gradient succeeds for bandits. arXiv preprint arXiv:2402.17235, 2024

    work page Pith review arXiv 2024

  2. [1]

    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

    work page 2021

  3. [2]

    Analysis of thompson sampling for the multi-armed bandit problem

    Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39–1. JMLR Workshop and Conference Proceedings, 2012

    work page 2012

  4. [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(2):235–256, 2002

    2002

  5. [4]

    Large-scale machine learning with stochastic gradient descent

    Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMP- STAT’2010: 19th International Conference on Computational StatisticsParis France, August 22-27, 2010 Keynote, Invited and Contributed Papers, pages 177–186. Springer, 2010

    work page 2010

  6. [5]

    Probability

    Leo Breiman. Probability. SIAM, 1992

    work page 1992

  7. [6]

    Fast global convergence of natural policy gradient methods with entropy regularization

    Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4):2563–2578, 2022

    work page 2022

  8. [7]

    Improved risk tail bounds for on-line algorithms

    Nicolò Cesa-bianchi and Claudio Gentile. Improved risk tail bounds for on-line algorithms. In Y . Weiss, B. Schölkopf, and J. Platt, editors, Advances in Neural Information Processing Systems, volume 18. MIT Press, 2005

    work page 2005

Show all 39 references
  1. [8]

    Regret analysis of a markov policy gradient algorithm for multi-arm bandits

    Denis Denisov and Neil Walton. Regret analysis of a markov policy gradient algorithm for multi-arm bandits. arXiv preprint arXiv:2007.10229, 2020

    2007 arXiv

  2. [9]

    Beyond exact gradients: Convergence of stochastic soft-max policy gradient methods with entropy regularization

    Yuhao Ding, Junzi Zhang, and Javad Lavaei. Beyond exact gradients: Convergence of stochastic soft-max policy gradient methods with entropy regularization. arXiv preprint arXiv:2110.10117, 2021

    2021 arXiv

  3. [10]

    Freedman

    David A. Freedman. On Tail Probabilities for Martingales. The Annals of Probability, 3(1):100 – 118, 1975. 10

    1975

  4. [11]

    An alternate policy gradient estimator for softmax policies

    Shivam Garg, Samuele Tosatto, Yangchen Pan, Martha White, and A Rupam Mahmood. An alternate policy gradient estimator for softmax policies. arXiv preprint arXiv:2112.11622, 2021

    2021 arXiv

  5. [12]

    Stochastic first-and zeroth-order methods for nonconvex stochastic programming

    Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013

    2013

  6. [13]

    A natural policy gradient

    Sham M Kakade. A natural policy gradient. In Advances in neural information processing systems, pages 1531–1538, 2002

    2002

  7. [14]

    Asymptotically efficient adaptive allocation rules

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

    1985

  8. [15]

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

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

    2023

  9. [16]

    Bandit algorithms

    Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020

    2020

  10. [17]

    Softmax policy gradient methods can take exponential time to converge

    Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Softmax policy gradient methods can take exponential time to converge. In Conference on Learning Theory, pages 3107–3110. PMLR, 2021

    2021

  11. [18]

    Towards principled, practical policy gradient for bandits and tabular mdps

    Michael Lu, Matin Aghaei, Anant Raj, and Sharan Vaswani. Towards principled, practical policy gradient for bandits and tabular mdps. arXiv preprint arXiv:2405.13136, 2024

    2024 arXiv

  12. [19]

    The role of baselines in policy gradient optimization

    Jincheng Mei, Wesley Chung, Valentin Thomas, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. The role of baselines in policy gradient optimization. Advances in Neural Information Processing Systems, 35:17818–17830, 2022

    2022

  13. [20]

    Understanding the effect of stochasticity in policy optimization

    Jincheng Mei, Bo Dai, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. Understanding the effect of stochasticity in policy optimization. Advances in Neural Information Processing Systems, 34:19339–19351, 2021

    2021

  14. [21]

    Leveraging non-uniformity in first-order non-convex optimization

    Jincheng Mei, Yue Gao, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. Leveraging non-uniformity in first-order non-convex optimization. In International Conference on Machine Learning, pages 7555–7564. PMLR, 2021

    2021

  15. [22]

    Escaping the gravitational pull of softmax

    Jincheng Mei, Chenjun Xiao, Bo Dai, Lihong Li, Csaba Szepesvári, and Dale Schuurmans. Escaping the gravitational pull of softmax. Advances in Neural Information Processing Systems, 33:21130–21140, 2020

    2020

  16. [23]

    On the global convergence rates of softmax policy gradient methods

    Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pages 6820–6829. PMLR, 2020

    2020

  17. [25]

    Robust stochastic ap- proximation approach to stochastic programming

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

    2009

  18. [26]

    Training language models to follow instructions with human feedback

    Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. arXiv preprint arXiv:2203.02155, 2022

    2022 arXiv

  19. [27]

    Direct preference optimization: Your language model is secretly a reward model

    Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36, 2024

    2024

  20. [28]

    A stochastic approximation method

    Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400–407, 1951

    1951

  21. [29]

    Trust region policy optimization

    John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889–1897, 2015

    2015

  22. [30]

    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

  23. [31]

    Reinforcement Learning: An Introduction

    Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT Press, 2018. 11

    2018

  24. [32]

    Policy gradient methods for reinforcement learning with function approximation

    Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999

    1999

  25. [33]

    On the likelihood that one unknown probability exceeds another in view of the evidence of two samples

    William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285–294, 1933

    1933

  26. [34]

    Simple statistical gradient-following algorithms for connectionist reinforcement learning

    Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8:229–256, 1992

    1992

  27. [35]

    Large stepsize gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency

    Jingfeng Wu, Peter L Bartlett, Matus Telgarsky, and Bin Yu. Large stepsize gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency. arXiv preprint arXiv:2402.15926, 2024

    2024 arXiv

  28. [36]

    A general sample complexity analysis of vanilla policy gradient

    Rui Yuan, Robert M Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 3332–3380. PMLR, 2022

    2022

  29. [37]

    On the convergence and sample efficiency of variance-reduced policy gradient method.Advances in Neural Information Processing Systems, 34:2228–2240, 2021

    Junyu Zhang, Chengzhuo Ni, Csaba Szepesvari, Mengdi Wang, et al. On the convergence and sample efficiency of variance-reduced policy gradient method.Advances in Neural Information Processing Systems, 34:2228–2240, 2021

    2021

  30. [38]

    Sample efficient reinforcement learning with reinforce

    Junzi Zhang, Jongho Kim, Brendan O’Donoghue, and Stephen Boyd. Sample efficient reinforcement learning with reinforce. arXiv preprint arXiv:2010.11364, 2020

    2010 arXiv

  31. [39]

    noise”) (52) Pt(a) := Et[θt+1(a)] − θt(a). (“progress

    Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58(6):3586–3612, 2020. 12 A Asymptotic Convergence Lemma 1. Using Algorithm 1 with any constant η...

    2020

Pith tools

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