# Second Order Methods for Bandit Optimization and Control

arXiv: https://arxiv.org/abs/2402.08929 · HTML: https://mlsanity.com/paper/2402.08929/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 38 references that are in the map.
- First posted on arXiv 14 Feb 2024.

## Builds on (most cited first, 6 of 6)

- [Black-Box Control for Linear Dynamical Systems](https://mlsanity.com/paper/2007.06650/) (2020)
- [Jointly Efficient and Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2201.01985/) (2022)
- [Logistic Regression: Tight Bounds for Stochastic and Online Optimization](https://mlsanity.com/paper/1405.3843/) (2014)
- [Introduction to Online Control](https://mlsanity.com/paper/2211.09619/) (2022)
- [A Second-Order Method for Stochastic Bandit Convex Optimisation](https://mlsanity.com/paper/2302.05371/) (2023)
- [Optimal Rates for Bandit Nonstochastic Control](https://mlsanity.com/paper/2305.15352/) (2023)

## Built on by (most cited first, 5 of 5)

- [Tight Rates for Bandit Control Beyond Quadratics](https://mlsanity.com/paper/2410.00993/) (2024)
- [Non-stationary Bandit Convex Optimization: A Comprehensive Study](https://mlsanity.com/paper/2506.02980/) (2025)
- [A Regularized Online Newton Method for Stochastic Convex Bandits with Linear Vanishing Noise](https://mlsanity.com/paper/2501.11127/) (2025)
- [Trading Vector Data in Vector Databases](https://mlsanity.com/paper/2511.07139/) (2025)
- [A Spectral Filtering Approach to Regret Analysis of Distributed Online Control for Linear Dynamical Systems](https://mlsanity.com/paper/2608.02375/) (2026)

## Abstract (arXiv)

Bandit convex optimization (BCO) is a general framework for online decision making under uncertainty. While tight regret bounds for general convex losses have been established, existing algorithms achieving these bounds have prohibitive computational costs for high dimensional data. In this paper, we propose a simple and practical BCO algorithm inspired by the online Newton step algorithm. We show that our algorithm achieves optimal (in terms of horizon) regret bounds for a large class of convex functions that we call kappa-convex. This class contains a wide range of practically relevant loss functions including linear, quadratic, and generalized linear models. In addition to optimal regret, this method is the most efficient known algorithm for several well-studied applications including bandit logistic regression. Furthermore, we investigate the adaptation of our second-order bandit algorithm to online convex optimization with memory. We show that for loss functions with a certain affine structure, the extended algorithm attains optimal regret. This leads to an algorithm with optimal regret for bandit LQR/LQG problems under a fully adversarial noise model, thereby resolving an open question posed in citepgradu2020non and citepsun2023optimal. Finally, we show that the more general problem of BCO with (non-affine) memory is harder. We derive a tildeOmega(T2/3) regret lower bound, even under the assumption of smooth and quadratic losses.