  We investigate bandit convex optimization (BCO) with delayed feedback, where
only the loss value of the action is revealed under an arbitrary delay. Let
$n,T,\bar{d}$ denote the dimensionality, time horizon, and average delay,
respectively. Previous studies have achieved an
$O(\sqrt{n}T^{3/4}+(n\bar{d})^{1/3}T^{2/3})$ regret bound for this problem,
whose delay-independent part matches the regret of the classical non-delayed
bandit gradient descent algorithm. However, there is a large gap between its
delay-dependent part, i.e., $O((n\bar{d})^{1/3}T^{2/3})$, and an existing
$\Omega(\sqrt{\bar{d}T})$ lower bound. In this paper, we illustrate that this
gap can be filled in the worst case, where $\bar{d}$ is very close to the
maximum delay $d$. Specifically, we first develop a novel algorithm, and prove
that it enjoys a regret bound of $O(\sqrt{n}T^{3/4}+\sqrt{dT})$ in general.
Compared with the previous result, our regret bound is better for
$d=O((n\bar{d})^{2/3}T^{1/3})$, and the delay-dependent part is tight in the
worst case. The primary idea is to decouple the joint effect of the delays and
the bandit feedback on the regret by carefully incorporating the delayed bandit
feedback with a blocking update mechanism. Furthermore, we show that the
proposed algorithm can improve the regret bound to
$O((nT)^{2/3}\log^{1/3}T+d\log T)$ for strongly convex functions. Finally, if
the action sets are unconstrained, we demonstrate that it can be simply
extended to achieve an $O(n\sqrt{T\log T}+d\log T)$ regret bound for strongly
convex and smooth functions.
