Bandit Convex Optimization

Follow this topic Ask about this topic

Momentum

1 paper in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 10

All topics

Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret
Sep 11, 2026Xuan LiThompson Sampling Bandit Convex Optimization
University of New South Wales, Sydney, Australia
Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions
Jul 22, 2026Zhanyuan Cai, Emre Sahinoglu, Shahin ShahrampourOnline Convex Optimization Riemannian Optimization
Department of Mechanical & Industrial Engineering at Northeastern University, Boston, MA 02115, USA
The Price of Hidden Curvature: An $\widetildeΩ (d^{5/4} \sqrt{T})$ Lower Bound for Bandit Convex Optimization
Jul 21, 2026Nived RajaramanOnline Convex Optimization Minimax Regret
Microsoft Research
Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses
Jun 18, 2026Zhuoyu Cheng, Kohei Hatano, Eiji TakimotoOnline Convex Optimization Bandit Convex Optimization
Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan · RIKEN AIP, Japan · Department of Informatics, Kyushu University, Japan
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.
Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization
Jun 6, 2026Wentao Zhang, Yutong Zhang, Wentao MoOnline Convex Optimization Bandit Convex Optimization
Tsinghua Shenzhen International Graduate School, Tsinghua University, China · College of Mathematics, Sichuan University, China
Bandit Convex Optimization with Gradient Prediction Adaptivity
May 21, 2026Shuche Wang, Adarsh Barik, Vincent Y. F. TanOnline Convex Optimization Dynamic Regret Minimization
Department of Mathematics, National University of Singapore, Singapore · Department of Computer Science and Engineering, Indian Institute of Technology Delhi, India · Department of Electrical and Computer Engineering, National University of Singapore, Singapore
Harnessing Unimodality in Semiparametric Contextual Pricing via Oracle Price Map Learning
May 14, 2026Yingying Fan, Yuxuan Han, Jinchi Lv +2Bandit Convex Optimization Dynamic Pricing
Data Sciences and Operations Department, University of Southern California, Los Angeles, California 90089, USA · Stern School of Business, New York University, New York, NY 10003, USA
In-Context Learning for Data-Driven Censored Inventory Control
May 14, 2026Sohom Mukherjee, Anh-Duy Pham, Richard Pibernik +1Inventory Control Bandit Convex Optimization
Julius-Maximilians-Universität Würzburg · National University of Singapore Zaragoza Logistics Center
Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations
Feb 4, 2026Hang Yu, Yu-Hu Yan, Peng ZhaoOnline Convex Optimization Dynamic Regret Minimization
State Key Laboratory for Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China

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

University of New South Wales, Sydney, Australia

Thompson Sampling Bandit Convex Optimization

Open paper AskPDF arXiv

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.

Momentum

Related topics

Latest papers 10