Dynamic Regret Bounds

Follow this topic Ask about this topic

Recent momentum

-50%

3 papers in the last 28 days · 0.1% of indexed attention

Twelve weeks of publication activity for this topic as it is defined today.

Weekly history

Recent digests

What was published in this topic, kept on the site without email delivery.

Period ending 2026-09-14

2 new papers

A weekly snapshot of new work published in Dynamic Regret Bounds.

46 papers

Latest in Dynamic Regret Bounds

Open your feed →

Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret
Sep 11, 2026Xuan LiThompson Sampling Dynamic Regret Bounds
Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
Sep 9, 2026Hao Li, Jie Xu, Zheng XieDynamic Regret Bounds Meta-Learning
No-Regret Bayesian Optimization with Finite-Library Input-Warped Kernels
Sep 2, 2026Edvin Ketabati Augustinsson, Robert A. BridgesBayesian Optimization Gaussian Process
Online Learning of Scale Parameters in Score-Driven Filters
Aug 10, 2026Fabrizio Lillo, Giulia Livieri, Gianluca PalmariMirror Descent Dynamic Regret Bounds
RASP-QAOA: Resource-Aware Per-Instance Selection for Exact QAOA Simulation
Aug 6, 2026Chih-Chung HsuQuantum Approximate Optimization Algorithm Cost-Aware
Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs
Jul 31, 2026Emmanuel Vazquez, Sébastien PetitReproducing Kernel Hilbert Spaces Dynamic Regret Bounds
Real-Time Hard Peak Age-of-Information Safety with No-Regret Learning
Jul 30, 2026Wentao Zhang, Wentao MoDeadlines Internet Of Thing
Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization
Jul 28, 2026Wentao ZhangConvex Optimization Dynamic Regret Bounds
Optimizing Regret
Jul 21, 2026Irene AldridgeDynamic Regret Bounds Regret
Evaluating Epistemic Uncertainty: Beyond OOD Detection and Active Learning
Jul 16, 2026Jakub Paplhám, Willem Waegeman, Eyke Hüllermeier +1Epistemic Uncertainty Artificial Intelligence Act Epistemic Injustice
When Is Delegated Play Truthful? Within-Range Regret and the Trilemma of Aligned Delegation
Jul 15, 2026Taksch DubeHonesty Progressive Disclosure
Robust Bayesian Decision Making under Adversarial Uncertainty
Jul 9, 2026Haripriya Harikumar, Sammie Katt, Yasir Zubayr Barlas +1Bayesian Experimental Design Bayesian Inference Approaches
How Many Initial Points Does Bayesian Optimization Need?
Jul 5, 2026Mujin Cheon, James Odgers, Dong-Yeun Koh +1Bayesian Optimization Thompson Sampling
Decision-Aware Training for Sample-Based Generative Models
Jul 1, 2026Kornelius Raeth, Nicole LudwigGenerative Models Score Function
Selective Ensemble Based on Preference-Directed Multi-Objective Bandits
Jun 20, 2026Lanjihong Ma, Zhen-Yu Zhang, Masashi Sugiyama +1Pareto Frontier Dynamic Regret Bounds
On the Variance of Temporal Difference Learning and its Reduction Using Control Variates
Jun 18, 2026Hsiao-Ru Pan, Bernhard SchölkopfTemporal Difference Variance Reduction
A Solver-Free Training Method for Predict-then-Optimize
Jun 17, 2026Beichen Wan, Mo LiuPredictive Performance Surrogate Gradient
Wasserstein Policy Learning for Distributional Outcomes
Jun 17, 2026Yiyan Huang, Cheuk Hang Leung, Qi Wu +1Optimal Policies Causal Inferences
Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization
Jun 6, 2026Wentao Zhang, Yutong Zhang, Wentao MoConvex Optimization Dynamic Regret Bounds
Online Learning with Gradient-Variation Interval Regret
Jun 2, 2026Yan-Feng Xie, Shuche Wang, Peng Zhao +1Learning-Augmented Algorithms Dynamic Regret Bounds
Optimal-Point Variance Reduction For Bayesian Optimization With Regret Guarantee
May 31, 2026Shion TakenoBayesian Optimization Variance Reduction
Variance-sensitive Thompson sampling for generalised linear bandits, revisited
May 29, 2026Tom Perneczky, Marc Abeille, David JanzThompson Sampling Dynamic Regret Bounds
Annealed Softmax Greedy in Many-Armed Bayesian Bandits
May 29, 2026William Overman, Mohsen BayatiDynamic Regret Bounds Verifiable Rewards
Information-Directed Offline-to-Online Reinforcement Learning
May 28, 2026Keru ChenOffline Safe Reinforcement Learning Dynamic Regret Bounds
Agile Online Model Selection: Resolving Adaptation Lag via Safeguarded Large Learning Rates
May 26, 2026Kei Takemura, Ryuta Matsuno, Keita SakumaLearning Rates Dynamic Regret Bounds
Goal-driven Bayesian Optimal Experimental Design for Robust Decision-Making Under Model Uncertainty
May 25, 2026Jinwoo Go, Xiaoning Qian, Byung-Jun YoonBayesian Experimental Design Bayesian Inference Approaches
Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
May 25, 2026Joongkyu Lee, Min-hwan OhMirror Descent Generalized Linear Bandit
Evolving Robustness--Exploration Trade-off in Online Reinforcement Learning via Quantile Bayesian Risk MDPs
May 23, 2026Meichen Song, Yuhao Wang, Enlu ZhouDynamic Regret Bounds Markov Decision Processes
Regret-Based $(ε,δ)$ -optimal Stopping Criteria for Bayesian OptimizationRegret-Based (ε,δ)-optimal Stopping Criteria for Bayesian Optimization
May 21, 2026Haowei Wang, Jingyi Wang, Qiyu WeiOptimal Stopping Bayesian Optimization
Decision-Aware Proximal Bridge Learning for Optimal Treatment Selection
May 16, 2026Tomàs Garriga, Alejandro Almodóvar, Axel Brando +3Causal Inferences Treatment
In-Context Learning for Data-Driven Censored Inventory Control
May 14, 2026Sohom Mukherjee, Anh-Duy Pham, Richard Pibernik +1Monotonic Inventory Estimation Dynamic Regret Bounds
Safe Bayesian Optimization for Uncertain Correlation Matrices in Linear Models of Co-Regionalization
May 13, 2026Jannis Lübsen, Annika EichlerBayesian Optimization Gaussian Process
Kernel-based guarantees for nonlinear parametric models in Bayesian optimization
May 13, 2026Rafael OliveiraBayesian Optimization Dynamic Regret Bounds
Online Sharp-Calibrated Bayesian Optimization
May 11, 2026Marshal Arijona Sinaga, Julien Martinelli, Teemu Turpeinen +1Bayesian Optimization Dynamic Regret Bounds
PFN-TS: Thompson Sampling for Contextual Bandits via Prior-Data Fitted Networks
May 11, 2026Yan Shuo Tan, Kenyon Ng, Ruizhe Deng +3Thompson Sampling Tabular Prior-Data Fitted Network
The Value of Mechanistic Priors in Sequential Decision Making
May 11, 2026Itai Shufaro, Gal Benor, Shie MannorSequential Decision Making Dynamic Regret Bounds
Asymptotically Log-Optimal Bayes-Assisted Confidence Sequences for Bounded Means
May 8, 2026Valentin Kilian, Stefano Cortinovis, François CaronConfidence Intervals Bayesian Inference Approaches
Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time
May 8, 2026Kalana Kalupahana, Francesco Emanuele Stradi, Matteo Castiglioni +1Dynamic Regret Bounds Prices
Data-dependent Exploration for Online Reinforcement Learning from Human Feedback
May 6, 2026Zhen-Yu Zhang, Yuting Tang, Jiandong Zhang +2Reinforcement Learning From Human Feedback Dynamic Regret Bounds
QUIVER: Cost-Aware Adaptive Preference Querying in Surrogate-Assisted Evolutionary Multi-Objective Optimization
May 5, 2026Florian A. D. BurnatMulti-Objective Evolutionary Algorithm Multi-Objective Optimization
DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees
Apr 17, 2026Argyrios Gerogiannis, Yu-Han Huang, Venugopal V. VeeravalliModel-Free Reinforcement Learning Finite-Horizon Episodic Markov Decision Processes
Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces
Mar 9, 2026Hamish Flynn, Joe Watson, Ingmar Posner +1Dynamic Regret Bounds Gaussian Process
Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Bounds
Mar 2, 2026Shuhei Sugiura, Ichiro Takeuchi, Shion TakenoBayesian Optimization Gaussian Process
Improved Algorithms for Nash Welfare in Linear Bandits
Jan 30, 2026Dhruv Sarkar, Nishant Pandey, Sayak Ray ChowdhuryDynamic Regret Bounds Fairness-Aware Learning
Prior Diffusiveness and Regret in the Linear-Gaussian Bandit
Jan 5, 2026Yifan Zhu, John C. Duchi, Benjamin Van RoyThompson Sampling Dynamic Regret Bounds
Active Exploration via Autoregressive Generation of Missing Data
May 29, 2024Tiffany Tianhui Cai, Hongseok Namkoong, Daniel Russo +1Stochastic Exploration Dynamic Regret Bounds

Sep 11, 2026 · cs.LGJ/K move · Enter open · S save

Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret

Xuan Li

Bakhtiari, Lattimore and Szepesv'ari (COLT 2025) proved that Thompson sampling (TS) has Bayesian regret

\tilde O(d^{5/2}\sqrt n)

for bandit convex optimisation with convex \emph{monotone} ridge losses

f(x)=\ell(\ip{x}{\theta})

, and asked whether monotonicity of the link is necessary. We give a qualitative negative answer. For every prior on

[0,1]

-valued,

1

-Lipschitz convex ridge losses with an arbitrary convex, possibly non-monotone, link, and for any fixed measurable selection of minimisers, exact-posterior TS has Bayesian regret

O\big((d+1)^4\sqrt{dn}\,\log(e+nd\max\{1,\diam K\})\big)=\tilde O(d^{9/2}\sqrt n)

. The monotone proof relies on a single-removal John-ellipsoid dichotomy; we show by an explicit twelve-point configuration that this dichotomy fails for non-monotone links, and replace it by an

O(d^2)

cardinality bound for ``uninformative'' configurations. The bound uses a Boolean rounding argument: a

0

1

matrix within

1/(4r)

in max-norm of a rank-

r

matrix has rank at most

2r-1

. We construct

d(d+1)

uninformative losses, showing that the cardinality bound is tight up to constants in the large-diameter-to-gap regime, and give a self-contained information-ratio-to-regret transfer that is uniform over fixed measurable selections. Whether the

d^{5/2}

dependence of the monotone case can be retained remains open.

Thompson Sampling Dynamic Regret Bounds Monotonicity Convex Loss

Open paper Ask about it PDF

Recent momentum

Neighbouring directions

Recent digests

2 new papers

Latest in Dynamic Regret Bounds