On-device research index

arXiv research

A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.

168,695 papers · 148 categories

Trend · papers per month

count % of corpus

18 results for “FTPL”

A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for

m

-Set Semi-Bandit Problemcs.LG

This paper improves FTPL algorithm for semi-bandit problems with best-of-both-worlds guarantees.

problem Optimizing regret in adversarial and stochastic

m

-set semi-bandit problems.

method Extending FTPL with geometric resampling (GR) to

m

-set semi-bandits and analyzing its performance.

result FTPL with Fréchet and Pareto distributions achieves

O(\sqrt{mdT})

regret in adversarial setting and logarithmic regret in stochastic setting.

semi-bandit problem Follow-the-Perturbed-Leader regret minimization best-of-both-worlds geometric resampling

2026-03-12abs ↗pdf ↗

Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problemscs.LG

Paper analyzes FTPL's effectiveness in combinatorial semi-bandit problems.

problem Optimizing FTPL policy in combinatorial semi-bandit problems.

method Geometric resampling (GR) and conditional geometric resampling (CGR) for FTPL in semi-bandit setting.

result FTPL achieves optimal regret bounds in both Fréchet and Pareto distributions.

Follow-the-Perturbed-Leader Combinatorial Semi-Bandit Regret Analysis Geometric Resampling Conditional Geometric Resampling

2025-06-14abs ↗pdf ↗

Follow-the-Perturbed-Leader with Fréchet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worldsstat.ML

Paper optimizes FTPL for adversarial and stochastic bandits with specific tail distributions.

problem Optimizing Follow-the-Perturbed-Leader (FTPL) policy for bandit problems.

method Analyzes FTPL with Fréchet-type tail distributions in adversarial and stochastic settings.

result FTPL with certain Fréchet-type tail distributions achieves

\mathcal{O}(\sqrt{KT})

regrets in adversarial bandits.

Follow-the-Perturbed-Leader Bandits Fréchet distribution Adversarial Stochastic

2024-03-08abs ↗pdf ↗

Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problemsstat.ML

Advances FTPL results for bandit problems with unbounded perturbations.

problem Improving analytical foundations of FTPL in bandit problems.

method Revisiting classical FTRL-FTPL duality for unbounded perturbations.

result Establishes Best-of-Both-Worlds (BOBW) results for FTPL under a broad family of asymmetric unbounded perturbations.

Bandit Problems Follow-the-Perturbed-Leader Unbounded Perturbations Best-of-Both-Worlds Frechet-type Perturbations

2025-08-26abs ↗pdf ↗

Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leaderstat.ML

Adaptive learning rates improve FTPL's BOBW guarantees in bandit problems.

problem Improving Follow-the-Perturbed-Leader's BOBW guarantees in bandit problems.

method Introducing surrogate probability functions to compute adaptive learning rates without exact probabilities.

result BOBW guarantees for FTPL with Pareto perturbations for any

α>1

Follow-the-Perturbed-Leader BOBW guarantees adaptive learning rates surrogate probability bandit problems

2026-06-04abs ↗pdf ↗

Optimism in the Face of Ambiguity Principle for Multi-Armed Banditscs.LG

New algorithm optimizes multi-armed bandits with low computational cost.

problem Optimizing multi-armed bandits with low computational cost.

method Proposes a new FTPL algorithm with optimistic principle for ambiguity.

result Unified regret analysis and low computational costs.

multi-armed bandits optimism in ambiguity Follow-The-Perturbed-Leader Follow-The-Regularized-Leader regret analysis

2024-09-30abs ↗pdf ↗

Online Non-Convex Learning: Following the Perturbed Leader is Optimalcs.LG

We study the problem of online learning with non-convex losses, where the learner has access to an offline optimization oracle. We show that the classical Follow the Perturbed Leader (FTPL) algorithm achieves optimal regret rate of $O(T^{-1/2})$ in this setting. This improves upon the previous best-known regret rate of…

2019-03-19abs ↗pdf ↗

Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcs.LG

FTPL method shows near-optimal regret bounds for AMDPs with bandit feedback.

problem Minimizing regret in AMDPs with adversarial losses and bandit feedback.

method Follow-the-Perturbed-Leader (FTPL) method for AMDPs.

result FTPL achieves near-optimal regret bounds for AMDPs with bandit feedback.

Adversarial Markov Decision Processes Bandit Feedback Follow-the-Perturbed-Leader Regret Minimization Online Learning

2022-05-26abs ↗pdf ↗

Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicalitystat.ML

FTPL policy achieves best-of-both-worlds regret in decoupled bandits with reduced computational cost.

problem Decoupled multi-armed bandit problem with observed and unobserved losses.

method Follow-the-Perturbed-Leader (FTPL) policy that avoids convex optimization and resampling.

result Achieves constant regret in stochastic regime and optimal

O(\sqrt{KT})

regret in adversarial regime.

Follow-the-Perturbed-Leader Decoupled Bandits Best-of-Both-Worlds Stochastic Regime Adversarial Regime

2025-10-14abs ↗pdf ↗

Self-Concordant Perturbations for Linear Banditsstat.ML

Unified algorithm for linear bandits with improved regret bound.

problem Adversarial linear bandits with improved regret.

method Self-concordant perturbations in FTPL framework.

result Regret bound of

\mathcal{O}(d\sqrt{n \ln n})

for hypercube and

\ell_2

ball.

linear bandits self-concordant perturbations FTPL regret bound adversarial setting

2025-10-28abs ↗pdf ↗

Beyond the Hazard Rate: More Perturbation Algorithms for Adversarial Multi-armed Banditscs.LG

Recent work on follow the perturbed leader (FTPL) algorithms for the adversarial multi-armed bandit problem has highlighted the role of the hazard rate of the distribution generating the perturbations. Assuming that the hazard rate is bounded, it is possible to provide regret analyses for a variety of FTPL algorithms f…

2017-02-17abs ↗pdf ↗

Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for Smooth Minimax Gamescs.LG

Improved FTPL algorithm reduces regret in predictable minimax games.

problem Online learning and minimax games with predictable loss sequences.

method Optimistic modification of FTPL with dual regularization view.

result Tighter regret bounds for predictable sequences,

O(T^{-1/2})

accuracy.

Follow the Perturbed Leader Optimism Minimax Games Regret Minimization Parallel Algorithms

2020-06-13abs ↗pdf ↗

Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problemscs.LG

FTPL with Fréchet perturbation achieves near optimal regret bounds for m-set semi-bandit problems.

problem Optimizing regret bounds for m-set semi-bandit problems in adversarial and stochastic settings.

method Follow-the-Perturbed-Leader (FTPL) with Fréchet perturbation.

result Achieves near optimal regret bounds of

\mathcal{O}(\sqrt{nm}(\sqrt{d\log(d)}+m^{5/6}))

in adversarial setting and logarithmic regret in stochastic setting.

semi-bandit Follow-the-Perturbed-Leader Fréchet perturbation regret bounds m-set semi-bandit

2025-04-09abs ↗pdf ↗

An Efficient Algorithm for Cooperative Semi-Banditscs.LG

Coop-FTPL algorithm minimizes network regret in semi-bandit settings.

problem Online combinatorial optimization with semi-bandit feedback on a network of agents.

method Cooperative Follow The Perturbed Leader (Coop-FTPL) algorithm with new loss estimation procedure.

result Expected regret of Coop-FTPL is of order Q mkT log(k)(kα1 /Q + m), with a state-of-the-art computational complexity of T^3/2.

Cooperative Semi-Bandits Online Optimization Follow The Perturbed Leader Network Regret Semi-Bandit Feedback

2020-10-05abs ↗pdf ↗

Toward Simultaneously Optimal Regret in U-Calibrationstat.ML

New algorithm reduces prediction errors across various loss functions.

problem Online forecasting algorithms' inability to adapt to different loss functions.

method Design of a novel Follow-the-Perturbed-Leader (FTPL) algorithm with self-concordant noise.

result Simultaneously achieves

ilde O(\sqrt{T})

regret for bounded proper losses and

O(\log T)

regret for bounded smooth proper losses.

U-calibration online forecasting regret minimization Follow-the-Perturbed-Leader self-concordant noise

2026-06-16abs ↗pdf ↗

Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimizationmath.OC

New methods improve online matrix optimization with reduced computational cost.

problem Online matrix optimization with operator norm constraints.

method Gradient-based prediction scheme with smoothed potentials for nuclear norm.

result Adaptive matrix optimizers match Shampoo's regret up to a constant factor.

online optimization matrix variables operator norm nuclear norm smoothed potentials

2026-02-09abs ↗pdf ↗

Exponential Weights on the Hypercube in Polynomial Timestat.ML

We study a general online linear optimization problem(OLO). At each round, a subset of objects from a fixed universe of $n$ objects is chosen, and a linear cost associated with the chosen subset is incurred. To measure the performance of our algorithms, we use the notion of regret which is the difference between the to…

2018-06-12abs ↗pdf ↗

Individually Fair Learning with One-Sided Feedbackcs.LG

Online learning with one-sided feedback aims to maximize accuracy while ensuring fairness.

problem Maximizing accuracy in online learning with limited feedback and ensuring fairness.

method Extending the framework of Bechavod et al. (2020) to incorporate dynamic panels of auditors, reducing the problem to a contextual combinatorial semi-bandit, and leveraging Exp2 and Context-Semi-Bandit-FTPL algorithms.

result Multi-criteria no regret guarantees for accuracy and fairness are provided.

online learning one-sided feedback individual fairness contextual combinatorial semi-bandit multi-criteria no regret

2022-06-09abs ↗pdf ↗