Follow-the-Regularized-Leader

Also known as FTRL

Follow-the-Regularized-Leader (FTRL) studies how to make a sequence of decisions by minimizing past losses together with a regularization term that shapes the learner’s behavior. Researchers use regularizers such as entropy and log-barrier functions, and develop optimistic, adaptive, and parameter-free variants related to Online Mirror Descent. Applications include online convex optimization, bandits, reinforcement learning in Markov decision processes, decentralized optimization, and learning in games, where performance is measured by regret or convergence to equilibrium. A central challenge is obtaining strong guarantees across different feedback and environment types while controlling stability, computational cost, and last-iterate behavior.

Latest papers

22 papers2 papers in the last four weeks, down 50% on the four weeks before. 0.0% of all new papers.

Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on $\ell_p$ Balls
Oct 26, 2026Jack J. MayoRegret Minimization Online Convex Optimization
Kurtos.ai Korteweg-de Vries Institute for Mathematics University of Amsterdam
Linear Last-Iterate Convergence Rates for Optimistic Learning in Harmonic Games
Oct 13, 2026John Lazarsfeld, Anas Barakat, Jacob Abernethy +4Last-Iterate Convergence Game Theory
Georgia Tech · SUTD · Google Research +2
Prediction with Expert Advice under Heavy-Tailed Losses
Oct 10, 2026Yuki Shibukawa, Shinji ItoMinimax Regret Heavy-Tailed Distributions
The University of Tokyo and RIKEN
Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader
Sep 8, 2026Ashkan Soleymani, Gabriele Farina, Patrick JailletGame Theory Gradient Descent
MIT
Constant regret in general games via higher-order optimism
Sep 3, 2026Omar Abbadi, Rida Laraki, Panayotis MertikopoulosFollow-the-Regularized-Leader Regret Minimization
Univ. Mohammed VI Polytechnic, CMSIS, MCGT, 11103 Rabat, Morocco · Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France
Constant Individual Regret in General Games
Aug 31, 2026Mingyang Liu, Gabriele Farina, Asuman OzdaglarGame Theory Follow-the-Regularized-Leader
LIDS, EECS, Massachusetts Institute of Technology
Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
Aug 31, 2026Yiyang Lu, Mohammad Pedramfar, Vaneet AggarwalSubmodular Optimization Follow-the-Regularized-Leader
Purdue University, West Lafayette, IN, USA · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada
Online Convex Optimization with Dueling Feedback
Aug 15, 2026Yiyang Lu, Hareshkumar Jadav, Mohammad Pedramfar +2Online Convex Optimization Follow-the-Regularized-Leader
Purdue University · IIT Indore · Mila - Quebec AI Institute/McGill University
What preferences can - and cannot - predict in multi-agent online learning
Aug 13, 2026Omar Abbadi, Rida Laraki, Panayotis MertikopoulosGame Theory Regret Minimization
Univ. Mohammed VI Polytechnic, CMSIS, Moroccan Center for Game Theory, 11103 Rabat, Morocco. · Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.
Dirichlet Follow-the-Leader Closes the Gap in Simultaneous Multiclass U-Calibration
Aug 7, 2026Pahan DewasurendraProbabilistic Forecasting Follow-the-Regularized-Leader
Johns Hopkins University
Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization
Aug 4, 2026Taira TsuchiyaFollow-the-Regularized-Leader Swap Regret
The University of Tokyo and RIKEN
Revisiting Decentralized Online Convex Optimization with Compressed Communication
Jul 2, 2026Hao Zhou, Xiaoyu Wang, Chang Yao +2Online Convex Optimization Follow-the-Regularized-Leader
School of Software Technology, Zhejiang University, Ningbo, China · State Key Laboratory of Blockchain and Data Security, Zhejiang University, Hangzhou, China
Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions
Jun 30, 2026Mingyi Li, Taira Tsuchiya, Kenji YamanishiRegret Minimization in RL Markov Decision Processes
Department of Mathematical Informatics, The University of Tokyo · Center for Advanced Intelligence Project, RIKEN
Capacity-Constrained Online Convex Optimization with Delayed Feedback
Jun 10, 2026Alexander Ryabchenko, Idan Attias, Daniel M. RoyOnline Convex Optimization Bandit Convex Optimization
Department of Statistical Sciences, University of Toronto; Vector Institute. · Institute for Data, Econometrics, Algorithms, and Learning (IDEAL), hosted by UIC and TTIC.
SEArch: Optimistic Policy Selection Between Scene Noise and Drift for UAV Radar Search
May 31, 2026Noor Khial, Naram Mhaisen, Loay Ismail +1Multi-Armed Bandits Non-Stationary Bandits
College of Engineering, Qatar University, Qatar · Faculty of Electrical Engineering, Mathematics, and Computer Science, Delft University of Technology, The Netherlands
No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics
Apr 6, 2026Yiheng Su, Emmanouil-Vasileios Vlatakis-GkaragkounisGame Theory Follow-the-Regularized-Leader
University of Wisconsin–Madison
A Controllability Perspective on Steering Follow-the-Regularized-Leader Learners in Games
Mar 28, 2026Heling Zhang, Siqi Du, Roy DongGame Theory Multi-Agent Control
Department of Electrical and Computer Engineering at Illinois Grainger Engineering, University of Illinois Urbana-Champaign. · Department of Industrial and Enterprise Systems Engineering at Illinois Grainger Engineering, University of Illinois Urbana-Champaign.
Efficient Uncoupled Learning Dynamics with $\tilde{O}\!\left(T^{-1/4}\right)$ Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback
Feb 24, 2026Arnab Maiti, Claire Jie Zhang, Kevin Jamieson +3Bandit Learning Last-Iterate Convergence
University of Washington · Amazon · University of California, Irvine
Data- and Variance-dependent Regret Bounds for Online Tabular MDPs
Feb 2, 2026Mingyi Li, Taira Tsuchiya, Kenji YamanishiRegret Minimization in RL Markov Decision Processes
Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan · RIKEN AIP, Tokyo, Japan
Self-Concordant Perturbations for Linear Bandits
Oct 28, 2025Lucas Lévy, Jean-Lou Valeau, Arya Akhavan +1Multi-Armed Bandits Follow-the-Perturbed-Leader
Ecole Polytechnique and University of Oxford · ENSAE Paris and University of Oxford · University of Oxford and Ecole Polytechnique +1
Best-of-Both Worlds for linear contextual bandits with paid observations
Oct 8, 2025Nathan Boyer, Dorian Baudry, Patrick RebeschiniMulti-Armed Bandits Follow-the-Regularized-Leader
ENS Paris-Saclay, France · Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France · Department of Statistics, University of Oxford
Online Learning: A Modern Introduction Using Convex Optimization
Dec 31, 2019Francesco OrabonaOnline Convex Optimization Follow-the-Regularized-Leader
KAUST

Oct 26, 2026J/K move · Enter open · S save

Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on $\ell_p$ Balls

Jack J. Mayo

Kurtos.ai Korteweg-de Vries Institute for Mathematics University of Amsterdam

Regret Minimization Online Convex Optimization Minimax Regret Follow-the-Regularized-Leader

Open paper AskPDF arXiv

We study full-information online linear optimisation on the unit

\ell_p

ball in

\mathbb{R}^d

, for fixed

2\le p<\infty

and losses of dual norm at most one. Let

Δ_T

denote the cumulative loss of the best fixed action above each round's minimum. A follow-the-regularised-leader (FTRL) algorithm attains, on every loss sequence and without knowing

T

Δ_T

, regret

O_p(1+\min\{Δ_T^{1-1/p},\, d^{1/2-1/p}\sqrt{Δ_T}\})

. Matching lower bounds show that this rate is minimax for each fixed

p

, and its constant

(2+o(1))p/\log p

is optimal as

p\to\infty

among guarantees uniform in

d

and

T

. The algorithm uses a bounded radial regulariser and switches at most once to its quadratic augmentation. On some paths where follow-the-leader (FTL) has regret one, its regret grows with

T

. A switching extension keeps the sharp constant and also guarantees

\mathrm{Reg}_T\le 2\,\mathrm{Reg}_T^{\mathrm{FTL}}

. For i.i.d. losses whose mean has no zero coordinates, we compute the exact

\log T

coefficient of the expected regret, which separates FTL's variance term from the bias of the regulariser.