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

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).