Locally-Additive Regret for Delayed Non-stationary Bandit Convex Optimization

We study bandit convex optimization (BCO) when feedback is adversarially delayed and the comparator sequence is also adversarially non-stationary. This setting arises in online advertising, recommender systems, and adaptive dosing, but existing algorithms either absorb one of the two axes into a black-box global penalty or pay a worst-case cost that ignores the local interaction between delay and drift. We propose Oracle-DARS-DBCO, a delay-aware blocking algorithm whose block length $K$ and one-point smoothing radius $\delta$ satisfy the single identity $K\delta^{2}\asymp n^{2}$. This identity cancels the multiplicative coupling between delay deviation and one-point estimator variance, so the regret of each segment is paid only on that segment. We prove matching upper and lower bounds on the expected dynamic regret: $\widetilde{O}\bigl(\sqrt{n}\,m^{1/4}T^{3/4}+\sqrt{d_{\max}\,mT}\bigr)$ for convex losses and $\widetilde{O}\bigl(n^{2/3}m^{1/3}T^{2/3}+d_{\max}\,m\log(eT/m)\bigr)$ for $\alpha$-strongly convex losses, where $m=S_{T}+1$ is the number of stationary segments and $d_{\max}$ is the worst-case delay. The matching Rademacher-sign lower bounds $\Omega\bigl(\sqrt{d(S_{T}+1)\,T}\bigr)$ and $\Omega\bigl(d(S_{T}+1)\bigr)$ show that the delay price is segment-local. On fourteen scaling experiments, the fitted log--log exponents agree with the predicted ones within $0.04$, and Oracle-DARS-DBCO reduces regret by up to $9.17\times$ relative to the strongest non-restarting baseline on a piecewise-stationary benchmark.