Regret Minimization

Follow this topic Ask about this topic

Momentum

12 papers in the last four weeks, up 71% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 81

All topics

Optimal Regret for Single Index Bandits
May 10, 2026Devdan Dey, Sujoy Bhore, Avishek GhoshMulti-Armed Bandits Single-Index Models
Department of Computer Science and Engineering, Indian Institute of Technology Bombay.
Tight Generalization Bounds for Noiseless Inverse Optimization
May 9, 2026Pouria Fatemi, Hoomaan Maskan, Suvrit Sra +1Parameter Estimation Learning to Optimize
Technical University of Munich, Germany · Uppsala University, Sweden · University of Toronto, Canada
Online Nonstochastic Prediction: Logarithmic Regret via Predictive Online Least Squares
May 6, 2026Chih-Fan Pai, Yang ZhengRecursive Least Squares Regret Minimization
Department of Electrical and Computer Engineering, UC San Diego
Trading off rewards and errors in multi-armed bandits
May 1, 2026Akram Erraqabi, Alessandro Lazaric, Michal Valko +2Multi-Armed Bandits Exploration-Exploitation Tradeoff
Inria SequeL · CMU · EnLearn
A Note on How to Remove the $\ln\ln T$ Term from the Squint Bound
Apr 29, 2026Francesco OrabonaRegret Minimization Online Learning
King Abdullah University of Science and Technology (KAUST) · Thuwal, 23955-6900, Kingdom of Saudi Arabia
Prior-Agnostic Robust Forecast Aggregation
Apr 27, 2026Zhi Chen, Cheng Peng, Wei TangMinimax Regret Probabilistic Forecasting
Chinese University of Hong Kong
Cover meets Robbins while Betting on Bounded Data: $\ln n$ Regret and Almost Sure $\ln\ln n$ Regret
Apr 22, 2026Shubhada Agrawal, Aaditya RamdasRegret Minimization
Indian Institute of Science · Carnegie Mellon University
An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to $Φ$ -Regret Minimization
Apr 21, 2026Gabriele Farina, Juan Carlos PerdomoModel Calibration Regret Minimization
MIT EECS · New York University
Demystifying the unreasonable effectiveness of online alignment methods
Apr 19, 2026Enoch Hyunwook KangLLM Alignment Direct Preference Optimization
Foster School of Business University of Washington
Adaptive multi-fidelity optimization with fast learning rates
Apr 17, 2026Come Fiegel, Victor Gabillon, Michal ValkoMulti-Fidelity Optimization Black-Box Optimization
´Ecole Normale Sup´erieure, Paris · Huawei R&D, UK · Inria Lille
Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound
Mar 6, 2026Hangyi ZhaoMinimax Regret Regret Minimization
Small Gradient Norm Regret for Online Convex Optimization
Jan 20, 2026Wenzhi Gao, Chang He, Madeleine UdellOnline Convex Optimization Sequential Decision Making
ICME, Stanford University · SIME, Shanghai University of Finance and Economics · Department of Management Science and Engineering, Stanford University
Prior Diffusiveness and Regret in the Linear-Gaussian Bandit
Jan 5, 2026Yifan Zhu, John C. Duchi, Benjamin Van RoyThompson Sampling Multi-Armed Bandits
Department of Electrical Engineering, Stanford University, California, United States.
No-Regret Gaussian Process Optimization of Time-Varying Functions
Nov 29, 2025Eliabelle Mauduit, Eloïse Berthier, Andrea SimonettoMulti-Armed Bandits Bayesian Optimization
Unit´e de Math´ematiques Appliqu´ees ENSTA, Institut Polytechnique de Paris Palaiseau, France · U2IS ENSTA, Institut Polytechnique de Paris Palaiseau, France
Direct Regret Optimization in Bayesian Optimization
Jul 9, 2025Fengxue Zhang, Yuxin ChenBayesian Optimization Learning to Optimize
Department of Computer Science University of Chicago Chicago, IL 60637
Infrequent Resolving Algorithm for Online Linear Programming
Aug 1, 2024Guokai Li, Zizhuo Wang, Jingwei ZhangSequential Decision Making Regret Minimization
School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, 518172, P.R. China
Online Linear Programming with Batching
Aug 1, 2024Haoran Xu, Peter W. Glynn, Yinyu YeSequential Decision Making Regret Minimization
Department of Management Science and Engineering, Stanford University
Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents
Jun 5, 2023Nika Haghtalab, Chara Podimata, Kunhe YangImperfect-Information Games Game Theory
University of California, Berkeley · Massachusetts Institute of Technology
Hierarchical Deep Counterfactual Regret Minimization
May 27, 2023Jiayu Chen, Xudong Wu, Zhekai Wang +1Imperfect-Information Games Hierarchical RL
The University of Hong Kong Hong Kong SAR · Peking University Beijing, China, 100871 · Purdue University2025 West Lafayette, IN 47907
Robust Budget Pacing with a Single Sample
Feb 3, 2023Santiago Balseiro, Rachitesh Kumar, Vahab Mirrokni +2Sample Complexity Online Advertising
DRO, Columbia Business School, New York, NY, USA · Google Research, New York, NY, USA · IEOR, Columbia University, New York, NY, USA
Satisficing Regret Minimization in Bandits: Constant Rate and Light-Tailed Distribution
Date pendingQing Feng, Tianyi Ma, Ruihao ZhuMulti-Armed Bandits Regret Minimization
School of Operations Research and Information Engineering, Cornell University · SC Johnson College of Business, Cornell University

May 10, 2026, stat.MLJ/K move · Enter open · S save

Optimal Regret for Single Index Bandits

Devdan Dey, Sujoy Bhore, Avishek Ghosh

Department of Computer Science and Engineering, Indian Institute of Technology Bombay.

Multi-Armed Bandits Single-Index Models Minimax Regret Regret Minimization Contextual Bandits

Open paper AskPDF arXiv

We study the

\textit{single-index bandit}

problem, where rewards depend on an unknown one-dimensional projection of high-dimensional contexts through an unknown reward function. This model extends linear and generalized linear bandits to a nonparametric setting, and is particularly relevant when the reward function is not known in advance. While optimal regret guarantees are known for monotone reward functions, the general non-monotone case remains poorly understood, with the best known bound being

\tilde{\mathcal{O}}(T^{3/4})

(under standard boundedness and Lipschitz assumptions on the reward function [Kang et al., 2025]). We close this gap by establishing the optimal regret for general single-index bandits. We propose a simple two-phase algorithm, namely, Zoomed Single Index Bandit with Upper Confidence Bound (

\texttt{ZoomSIB-UCB}

), that first estimates the projection direction via a normalized Stein estimator, and then reduces the problem to a one-dimensional bandit using discretization and finally use UCB. This approach achieves a regret of

\tilde{\mathcal{O}}(T^{2/3})

, and improves significantly upon prior work without any additional assumptions. We also prove a matching minimax lower bound of

\tildeΩ(T^{2/3})

, showing that the upper bound is essentially tight. Our upper and lower bounds together provide a sharp characterization of the regret in single-index bandits. Moreover, the empirical results further demonstrate the effectiveness and robustness of our approach.

Momentum

Related topics

Latest papers 81