2025/08/06 by He, Chang, Jiang, Bo, Zhang, Shuzhong
#FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2508.04654
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).