# Non-Stationary Bandit Convex Optimization: An Optimal Algorithm with Two-Point Feedback

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Aug 2025.

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

- [Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations](https://mlsanity.com/paper/2602.04761/) (2026)
- [Bandit Convex Optimization with Gradient Prediction Adaptivity](https://mlsanity.com/paper/2605.22191/) (2026)
- [Small Gradient Norm Regret for Online Convex Optimization](https://mlsanity.com/paper/2601.13519/) (2026)

## Abstract (arXiv)

This paper studies bandit convex optimization in non-stationary environments with two-point feedback, using dynamic regret as the performance measure. We propose an algorithm based on bandit mirror descent that extends naturally to non-Euclidean settings. Let T be the total number of iterations and PT,p the path variation with respect to the ℓp-norm. In Euclidean space, our algorithm matches the optimal regret bound O(√dT(1+PT,2)), improving upon citetzhao2021bandit by a factor of O(√d). Beyond Euclidean settings, our algorithm achieves an upper bound of O(√dlog(d)Tlog(T)(1 + PT,1)) on the simplex, which is nearly optimal up to log factors. For the cross-polytope, the bound reduces to O(√dlog(d)T(1+PT,p)) for some p = 1 + 1/log(d).