Parameter-Free Online Learning

Follow this topic Ask about this topic

Latest papers

11 papers2 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits
Nov 2, 2026Jongyeong Lee, Chansoo KimMulti-Armed Bandits Parameter-Free Online Learning
Korea Institute of Science and Technology · University of Science and Technology
Conic-Lifting for Learning-rate-free Convex Optimization
Oct 29, 2026Julien Grand-Clément, Joon Kwon, Francesco OrabonaParameter-Free Online Learning Online Convex Optimization
ISOM Department, HEC Paris, 78350, Jouy-en-Josas, France · INRAE & Université Paris–Saclay, 91120, Palaiseau, France · King Abdullah University of Science and Technology (KAUST), 23955–6900, Thuwal, Kingdom of Saudi Arabia
Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
Oct 7, 2026Sasha Voitovych, Adam Block, Alexander Rakhlin +1Follow-the-Perturbed-Leader Parameter-Free Online Learning
MIT · Columbia University · Georgia Tech
Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise
Sep 30, 2026Vaneet AggarwalParameter-Free Online Learning Online Convex Optimization
Purdue University, West Lafayette, IN, USA
Parameter-Free Dynamic Regret under Heavy-Tailed Noise
Jul 29, 2026Vaneet AggarwalHeavy-Tailed Noise Dynamic Regret Minimization
Purdue University
Parameter-Free and Group Conditional Online Conformal Prediction
May 29, 2026Beepul Bharti, Ambar Pal, Jacopo Teneggi +1Uncertainty Quantification Group-Conditional Conformal Prediction
1Johns Hopkins University · 2Amazon Responsible AI
Decentralized Parameter-Free Online Learning with Compressed Gossip
May 27, 2026Tomas Ortega, Hamid JafarkhaniOnline Convex Optimization Decentralized Learning
Center for Pervasive Communications & Computing and EECS Department, University of California, Irvine, Irvine, CA 92697 USA
A Note on How to Remove the $\ln\ln T$ Term from the Squint Bound
Apr 29, 2026Francesco OrabonaRegret Minimization Parameter-Free Online Learning
King Abdullah University of Science and Technology (KAUST) · Thuwal, 23955-6900, Kingdom of Saudi Arabia
Gradient-Variation Regret Bounds for Unconstrained Online Learning
Apr 13, 2026Yuheng Zhao, Andrew Jacobsen, Nicolò Cesa-Bianchi +1Parameter-Free Online Learning Online Convex Optimization
Università degli Studi di Milano & Politecnico di Milano
A Short Note on a Variant of the Squint Algorithm
Mar 3, 2026Haipeng LuoParameter-Free Online Learning Regret Minimization
University of Southern California
Online Learning: A Modern Introduction Using Convex Optimization
Dec 31, 2019Francesco OrabonaOnline Convex Optimization Follow-the-Regularized-Leader
KAUST

Nov 2, 2026J/K move · Enter open · S save

A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits

Jongyeong Lee, Chansoo Kim

Korea Institute of Science and Technology · University of Science and Technology

Multi-Armed Bandits Parameter-Free Online Learning

Open paper AskPDF arXiv

We study online channel scheduling for a single queue served by

K

channels under bandit feedback. We propose a simple best-of-both-worlds policy that explores when the queue is empty. During busy periods, it selects the empirical best channel while the prescribed conditions hold and, if any condition is violated, switches to a robust bandit policy to clear the queue. For arbitrary arrivals and services determined by an oblivious adversary, our policy achieves

\tilde{\mathcal{O}}(\sqrt{K L_T})

worst-case queue length regret with high probability, where

L_T

is the longest busy-period length. This result improves the previous

T^{3/4}

dependence and matches the worst-case lower bound up to logarithmic factors. Under bounded i.i.d. stochastic models with a unique best stabilizing channel, we show that the cumulative queue length regret converges to a finite problem-dependent constant, and further establish the logarithmic expected worst-case queue length regret bound.