pith. sign in

arxiv: 2606.06043 · v1 · pith:RX6CXGW5new · submitted 2026-06-04 · 📊 stat.ML · cs.LG

Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader

Jongyeong Lee , Junya Honda , Shinji Ito , Chansoo Kim This is my paper

Pith reviewed 2026-06-27 23:39 UTC · model grok-4.3

classification 📊 stat.ML cs.LG
keywords follow-the-perturbed-leaderadaptive learning ratessurrogate probabilitiesbest-of-both-worldsPareto perturbationsbandit problemsonline learning
0
0 comments X

The pith

Surrogate probability functions let follow-the-perturbed-leader achieve best-of-both-worlds guarantees for Pareto perturbations of any shape greater than one.

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

This paper introduces surrogate probability functions for follow-the-perturbed-leader that approximate arm-selection probabilities using only quantities already available during the run, without solving convex optimization. These surrogates support the design of adaptive, probability-dependent learning rates for the optimization-free FTPL algorithm. With them the authors establish best-of-both-worlds regret bounds for FTPL under Pareto perturbations for every shape parameter alpha greater than one, removing the earlier restriction to alpha equal to two. The same surrogate construction also yields best-of-both-worlds performance in the bandit problem with expert advice. The approach therefore adds adaptivity while retaining FTPL's computational simplicity.

Core claim

The paper shows that surrogate probability functions, computed without the exact arm-selection probabilities from convex optimization, suffice to define adaptive learning rates for FTPL. These rates deliver the best-of-both-worlds guarantee for FTPL with Pareto perturbations for every shape parameter alpha larger than one, extending earlier results that held only for alpha equal to two. The same construction also gives best-of-both-worlds performance for FTPL in the setting of bandits with expert advice.

What carries the argument

Surrogate probability functions that estimate selection probabilities from available quantities to support probability-dependent adaptive learning rates in FTPL.

If this is right

  • BOBW regret bounds hold for FTPL with Pareto perturbations for any alpha greater than one
  • BOBW guarantees extend to FTPL in the expert-advice bandit problem
  • The method preserves FTPL's computational efficiency by avoiding convex optimization at each step
  • The surrogate methodology may apply to other optimization-free algorithms that need probability-dependent adaptivity

Where Pith is reading between the lines

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

  • The surrogate technique could be tested on perturbation families other than Pareto to check whether similar BOBW results appear
  • Explicit numerical comparisons of surrogate versus exact-probability regret could quantify the practical overhead
  • The same approximation idea might transfer to full-information online convex optimization where exact probabilities are also expensive to obtain
  • One could examine whether the approach yields improved bounds in non-stationary or drifting environments

Load-bearing premise

The surrogate probability functions approximate the true selection probabilities closely enough that the best-of-both-worlds analysis still goes through.

What would settle it

A concrete bandit instance in which the gap between surrogate and true probabilities grows over time and causes the derived regret bound to be violated.

read the original abstract

Follow-the-regularized-leader framework has shown effectiveness and flexibility in online learning problems, where the choice of learning rates are known to be crucial. Recently, adaptive learning rates defined in terms of the arm-selection probabilities, obtained by solving convex optimization, have achieved improved best-of-both-worlds (BOBW) guarantees in various bandit problems. In contrast, BOBW guarantees for its computationally efficient alternative, follow-the-perturbed-leader (FTPL), remain relatively limited since its optimization-free nature ironically makes the design of adaptive, probability-dependent learning rates non-trivial. To address this challenge, we propose an adaptive learning rate for FTPL by introducing surrogate probability functions that can be computed only from the available quantities, without requiring the exact probabilities. Based on these learning rates with surrogate functions, we provide the BOBW guarantee for FTPL with Pareto perturbations for any shape parameter $\alpha >1$, generalizing prior results restricted to specific choices of $\alpha=2$. We further show the BOBW guarantees for FTPL with adaptive learning rates in the bandit problem with expert advices. Our approach preserves the computational simplicity of FTPL while enabling probability-dependent adaptivity, and the surrogate-based methodology may be of independent interest in other algorithmic frameworks beyond FTPL and learning rate designs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper introduces surrogate probability functions that can be computed from available quantities without solving convex programs, enabling the design of adaptive, probability-dependent learning rates for Follow-the-Perturbed-Leader (FTPL). Using these surrogates, the authors claim best-of-both-worlds (BOBW) regret bounds for FTPL with Pareto perturbations for arbitrary shape parameter α > 1 (generalizing prior α = 2 results) and for the bandit-with-expert-advice setting, while preserving FTPL's computational efficiency.

Significance. If the surrogate approximation error can be controlled uniformly in α, the result would meaningfully extend the range of perturbation distributions for which computationally cheap BOBW guarantees are available in FTPL; the surrogate methodology itself could be reusable in other optimization-free online algorithms.

major comments (3)
  1. [§4.1–4.2] §4.1–4.2 (surrogate definition and properties): no explicit, α-uniform bound is stated on the total-variation or ℓ1 distance between the surrogate probabilities and the exact arm-selection probabilities obtained from the convex program; without such a bound the transfer of the existing α = 2 BOBW analysis to general α > 1 is not justified.
  2. [Theorem 5.2] Theorem 5.2 (BOBW for Pareto FTPL): the regret decomposition invokes the surrogate schedule directly in the adaptive learning-rate term, yet the proof sketch does not quantify how the Pareto tail (which changes with α) interacts with any fixed surrogate error; an α-dependent bias could invalidate the claimed bound as α ↓ 1.
  3. [§6] §6 (bandit-with-expert-advice extension): the same surrogate construction is reused, but the expert-advice setting introduces an additional layer of probability estimation; the paper provides no separate error analysis showing that the surrogate remains sufficiently accurate under this change of measure.
minor comments (2)
  1. [§4] Notation for the surrogate function is introduced without a dedicated display equation; a single numbered definition would improve readability.
  2. [Introduction] The abstract states the result for “any shape parameter α > 1” but the introduction only cites the α = 2 case; a short paragraph contrasting the new range with prior work would help.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive review. The points raised identify gaps in the explicitness of our error bounds and proof details. We address each major comment below and will incorporate the requested clarifications and additional analysis in the revision.

read point-by-point responses

  1. Referee: [§4.1–4.2] §4.1–4.2 (surrogate definition and properties): no explicit, α-uniform bound is stated on the total-variation or ℓ1 distance between the surrogate probabilities and the exact arm-selection probabilities obtained from the convex program; without such a bound the transfer of the existing α = 2 BOBW analysis to general α > 1 is not justified.

    Authors: We agree that an explicit α-uniform bound on the ℓ1 (or total-variation) distance between surrogate and exact probabilities is required to justify extending the α=2 analysis. The current manuscript derives α-dependent bounds but does not isolate a uniform statement. In the revision we will insert a new lemma in §4.2 establishing that the ℓ1 distance is bounded by a constant independent of α (for all α>1), obtained directly from the Pareto tail and the closed-form surrogate definition. This lemma will be placed immediately before the BOBW proofs so that the transfer is fully rigorous. revision: yes

  2. Referee: [Theorem 5.2] Theorem 5.2 (BOBW for Pareto FTPL): the regret decomposition invokes the surrogate schedule directly in the adaptive learning-rate term, yet the proof sketch does not quantify how the Pareto tail (which changes with α) interacts with any fixed surrogate error; an α-dependent bias could invalidate the claimed bound as α ↓ 1.

    Authors: We will expand the proof of Theorem 5.2 to include an explicit decomposition of the surrogate-induced bias term. Using the uniform ℓ1 bound from the new lemma, we will show that the additional error contributed by the Pareto tail is absorbed into the O(√(KT log K)) and O(log T) terms without introducing α-dependent blow-up as α↓1. The revised proof will contain the full calculation of this interaction rather than a sketch. revision: yes

  3. Referee: [§6] §6 (bandit-with-expert-advice extension): the same surrogate construction is reused, but the expert-advice setting introduces an additional layer of probability estimation; the paper provides no separate error analysis showing that the surrogate remains sufficiently accurate under this change of measure.

    Authors: We acknowledge that a dedicated error analysis under the expert-advice change of measure is missing. In the revision we will add a short subsection (new §6.3) that bounds the surrogate approximation error when the base measure is replaced by the expert-weighted distribution. The argument reuses the same uniform ℓ1 bound together with a simple Lipschitz property of the expert probabilities, confirming that the BOBW guarantees continue to hold. revision: yes

Circularity Check

0 steps flagged

No circularity: surrogates are newly defined constructs enabling independent BOBW extension

full rationale

The paper defines surrogate probability functions explicitly as computable approximations from available quantities (without convex optimization), then uses them to derive adaptive rates and BOBW bounds for general α>1. No equation reduces a claimed prediction or guarantee to a fitted input or prior self-citation by construction. The generalization from α=2 is presented as an analytic extension via the surrogates rather than a renaming or self-referential fit. Self-citations, if present, are not load-bearing for the central claim. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 1 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities beyond the surrogate probability functions themselves are described. The surrogate functions are the central new object introduced to bypass exact probability computation.

invented entities (1)
  • surrogate probability functions no independent evidence
    purpose: Approximate arm-selection probabilities using only quantities already available inside FTPL so that adaptive learning rates can be defined without solving convex programs
    Introduced explicitly in the abstract to solve the design problem created by FTPL's optimization-free nature

pith-pipeline@v0.9.1-grok · 5765 in / 1263 out tokens · 22499 ms · 2026-06-27T23:39:33.808415+00:00 · methodology

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

37 extracted references · 3 canonical work pages

  1. [1]

    Perturbation techniques in online learning and optimization

    Jacob Abernethy, Chansoo Lee, and Ambuj Tewari. Perturbation techniques in online learning and optimization. Perturbations, Optimization, and Statistics, 233, 2016

    2016

  2. [2]

    The nonstochastic multiarmed bandit problem

    Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32 0 (1): 0 48--77, 2002

    2002

  3. [3]

    The best of both worlds: S tochastic and adversarial bandits

    S \'e bastien Bubeck and Aleksandrs Slivkins. The best of both worlds: S tochastic and adversarial bandits. In Conference on Learning Theory, pages 42.1--42.23. PMLR, 2012

    2012

  4. [4]

    Improved second-order bounds for prediction with expert advice

    Nicolo Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for prediction with expert advice. Machine Learning, 66 0 (2): 0 321--352, 2007

    2007

  5. [5]

    Geometric resampling in nearly linear time for follow-the-perturbed-leader with best-of-both-worlds guarantee in bandit problems

    Botao Chen, Jongyeong Lee, and Junya Honda. Geometric resampling in nearly linear time for follow-the-perturbed-leader with best-of-both-worlds guarantee in bandit problems. In International Conference on Machine Learning, PMLR, pages 8403--8426, 2025

    2025

  6. [6]

    A further efficient algorithm with best-of-both-worlds guarantees for m -set semi-bandit problem

    Botao Chen, Jongyeong Lee, Chansoo Kim, and Junya Honda. A further efficient algorithm with best-of-both-worlds guarantees for m -set semi-bandit problem. arXiv preprint arXiv:2603.11764, 2026

    work page arXiv 2026

  7. [7]

    A blackbox approach to best of both worlds in bandits and beyond

    Christoph Dann, Chen-Yu Wei, and Julian Zimmert. A blackbox approach to best of both worlds in bandits and beyond. In Conference on Learning Theory, pages 5503--5570. PMLR, 2023

    2023

  8. [8]

    A second-order bound with excess losses

    Pierre Gaillard, Gilles Stoltz, and Tim Van Erven. A second-order bound with excess losses. In Conference on Learning Theory, pages 176--196. PMLR, 2014

    2014

  9. [9]

    Follow-the-Perturbed-Leader achieves best-of-both-worlds for bandit problems

    Junya Honda, Shinji Ito, and Taira Tsuchiya. Follow-the-Perturbed-Leader achieves best-of-both-worlds for bandit problems. In International Conference on Algorithmic Learning Theory, volume 201, pages 726--754. PMLR, 2023

    2023

  10. [10]

    Adaptive best-of-both-worlds algorithm for heavy-tailed multi-armed bandits

    Jiatai Huang, Yan Dai, and Longbo Huang. Adaptive best-of-both-worlds algorithm for heavy-tailed multi-armed bandits. In International Conference on Machine Learning, pages 9173--9200. PMLR, 2022

    2022

  11. [11]

    Hybrid regret bounds for combinatorial semi-bandits and adversarial linear bandits

    Shinji Ito. Hybrid regret bounds for combinatorial semi-bandits and adversarial linear bandits. In Advances in Neural Information Processing Systems, pages 2654--2667, 2021

    2021

  12. [12]

    Adaptive learning rate for follow-the-regularized-leader: Competitive analysis and best-of-both-worlds

    Shinji Ito, Taira Tsuchiya, and Junya Honda. Adaptive learning rate for follow-the-regularized-leader: Competitive analysis and best-of-both-worlds. In Conference on Learning Theory. PMLR, 2024

    2024

  13. [13]

    Improved best-of-both-worlds guarantees for multi-armed bandits: FTRL with general regularizers and multiple optimal arms

    Tiancheng Jin, Junyan Liu, and Haipeng Luo. Improved best-of-both-worlds guarantees for multi-armed bandits: FTRL with general regularizers and multiple optimal arms. In Advances in Neural Information Processing Systems, 2023

    2023

  14. [14]

    Adam Kalai and Santosh S. Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71: 0 291--307, 2005

    2005

  15. [15]

    Sequential choice from several populations

    Michael N Katehakis and Herbert Robbins. Sequential choice from several populations. Proceedings of the National Academy of Sciences, 92 0 (19): 0 8584--8585, 1995

    1995

  16. [16]

    On the optimality of perturbations in stochastic and adversarial multi-armed bandit problems

    Baekjin Kim and Ambuj Tewari. On the optimality of perturbations in stochastic and adversarial multi-armed bandit problems. In Advances in Neural Information Processing Systems, pages 2695--2704, 2019

    2019

  17. [17]

    Follow-the-perturbed-leader for decoupled bandits: Best-of-both-worlds and practicality

    Chaiwon Kim, Jongyeong Lee, and Min-hwan Oh. Follow-the-perturbed-leader for decoupled bandits: Best-of-both-worlds and practicality. International Conference on Machine Learning, 2026

    2026

  18. [18]

    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

  19. [19]

    Bandit algorithms

    Tor Lattimore and Csaba Szepesv \'a ri. Bandit algorithms. Cambridge University Press, 2020

    2020

  20. [20]

    Follow-the-Perturbed-Leader with F réchet-type tail distributions: Optimality in adversarial bandits and best-of-both-worlds

    Jongyeong Lee, Junya Honda, Shinji Ito, and Min-hwan Oh. Follow-the-Perturbed-Leader with F réchet-type tail distributions: Optimality in adversarial bandits and best-of-both-worlds. In Conference on Learning Theory, pages 3375--3430. PMLR, 2024

    2024

  21. [21]

    Revisiting follow-the-perturbed-leader with unbounded perturbations in bandit problems

    Jongyeong Lee, Junya Honda, Shinji Ito, and Min-hwan Oh. Revisiting follow-the-perturbed-leader with unbounded perturbations in bandit problems. In Advances in Neural Information Processing Systems, volume 38, pages 83623--83675. Curran Associates, Inc., 2025

    2025

  22. [22]

    Optimism in the face of ambiguity principle for multi-armed bandits

    Mengmeng Li, Daniel Kuhn, and Bahar Ta s kesen. Optimism in the face of ambiguity principle for multi-armed bandits. arXiv preprint arXiv:2409.20440, 2024

    work page arXiv 2024

  23. [23]

    Importance weighting without importance weights: A n efficient algorithm for combinatorial semi-bandits

    Gergely Neu and G \'a bor Bart \'o k. Importance weighting without importance weights: A n efficient algorithm for combinatorial semi-bandits. Journal of Machine Learning Research, 17 0 (154): 0 1--21, 2016

    2016

  24. [24]

    Data-dependent bounds with T -optimal best-of-both-worlds guarantees in multi-armed bandits using stability-penalty matching

    Quan Nguyen, Shinji Ito, Junpei Komiyama, and Mehta Nishant. Data-dependent bounds with T -optimal best-of-both-worlds guarantees in multi-armed bandits using stability-penalty matching. In Conference on Learning Theory, pages 4386--4451. PMLR, 2025

    2025

  25. [25]

    NIST handbook of mathematical functions hardback and CD-ROM

    Frank WJ Olver, Daniel W Lozier, Ronald F Boisvert, and Charles W Clark. NIST handbook of mathematical functions hardback and CD-ROM . Cambridge university press, 2010

    2010

  26. [26]

    FPL analysis for adaptive bandits

    Jan Poland. FPL analysis for adaptive bandits. In International Symposium on Stochastic Algorithms, pages 58--69. Springer, 2005

    2005

  27. [27]

    Tsallis-INF for decoupled exploration and exploitation in multi-armed bandits

    Chlo \'e Rouyer and Yevgeny Seldin. Tsallis-INF for decoupled exploration and exploitation in multi-armed bandits. In Conference on Learning Theory, pages 3227--3249. PMLR, 2020

    2020

  28. [28]

    An improved parametrization and analysis of the EXP 3++ algorithm for stochastic and adversarial bandits

    Yevgeny Seldin and G \'a bor Lugosi. An improved parametrization and analysis of the EXP 3++ algorithm for stochastic and adversarial bandits. In Conference on Learning Theory, pages 1743--1759. PMLR, 2017

    2017

  29. [29]

    A simple and adaptive learning rate for FTRL in online learning with minimax regret of (T^ 2/3 ) and its application to best-of-both-worlds

    Taira Tsuchiya and Shinji Ito. A simple and adaptive learning rate for FTRL in online learning with minimax regret of (T^ 2/3 ) and its application to best-of-both-worlds. Advances in Neural Information Processing Systems, 37: 0 8477--8514, 2024

    2024

  30. [30]

    Further adaptive best-of-both-worlds algorithm for combinatorial semi-bandits

    Taira Tsuchiya, Shinji Ito, and Junya Honda. Further adaptive best-of-both-worlds algorithm for combinatorial semi-bandits. In International Conference on Artificial Intelligence and Statistics, pages 8117--8144. PMLR, 2023 a

    2023

  31. [31]

    Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds

    Taira Tsuchiya, Shinji Ito, and Junya Honda. Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds. Advances in Neural Information Processing Systems, pages 47406--47437, 2023 b

    2023

  32. [32]

    More adaptive algorithms for adversarial bandits

    Chen-Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference on Learning Theory, pages 1--29. PMLR, 2018

    2018

  33. [33]

    Follow-the-perturbed-leader nearly achieves best-of-both-worlds for the m-set semi-bandit problems

    Jingxin Zhan, Yuchen Xin, Chenjie Sun, and Zhihua Zhang. Follow-the-perturbed-leader nearly achieves best-of-both-worlds for the m-set semi-bandit problems. In Advances in Neural Information Processing Systems, 2025

    2025

  34. [34]

    Heavy-tailed linear bandits: Adversarial robustness, best-of-both-worlds, and beyond

    Canzhe Zhao, Shinji Ito, and Shuai Li. Heavy-tailed linear bandits: Adversarial robustness, best-of-both-worlds, and beyond. arXiv preprint arXiv:2508.13679, 2025

    work page arXiv 2025

  35. [35]

    Productive bandits: Importance weighting no more

    Julian Zimmert and Teodor Vanislavov Marinov. Productive bandits: Importance weighting no more. Advances in Neural Information Processing Systems, 37: 0 85360--85388, 2024

    2024

  36. [36]

    Tsallis- INF : A n optimal algorithm for stochastic and adversarial bandits

    Julian Zimmert and Yevgeny Seldin. Tsallis- INF : A n optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22 0 (28): 0 1--49, 2021

    2021

  37. [37]

    Beating stochastic and adversarial semi-bandits optimally and simultaneously

    Julian Zimmert, Haipeng Luo, and Chen-Yu Wei. Beating stochastic and adversarial semi-bandits optimally and simultaneously. In International Conference on Machine Learning, pages 7683--7692. PMLR, 2019

    2019