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: $\tilde{O}(\sqrt{n}{m}^{1/4}{T}^{3/4}+\sqrt{d_{\max }mT})$ for convex losses and $\tilde{O}(n^{2/3}{m}^{1/3}{T}^{2/3}+d_{\max }m\log (eT/m))$ 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 \left(\sqrt{d(S_T+1)T}\right)$ and $\Omega (d(S_T+1))$ 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.