Stochastic Bandit Convex Optimization with Blocking Constraints

We study stochastic bandit convex optimization under blocking constraints. After an action is selected, all actions within distance $\epsilon$ become unavailable for the next $p-1$ rounds, where $p$ is the blocking period. Since repeatedly selecting a minimizer is, in general, infeasible, we measure regret against an offline benchmark defined by the infimum average loss over feasible cycles of $p$ actions. We show that the convexity of the loss function and the action set allows the search for this benchmark to be restricted to a ball of radius $2p\epsilon$ around a global minimizer. This motivates the design and analysis of an algorithm that first learns a point with low loss and then uses lower confidence bound (LCBs) to explore feasible cycles in its neighborhood. By grouping repeated queries and controlling transitions between cycles, our algorithm respects the blocking constraints and accounts for all exploration and transition costs. Under a geometric condition ensuring local feasibility, we establish a regret upper bound of $\tilde{O}(\sqrt{T}[1+(\epsilon \sqrt{T}{)}^{d/(d+2)}])$ and a minimax lower bound of $\Omega (\sqrt{T}[1+(\epsilon \sqrt{T}{)}^{(d-1)/(d+3)}])$, for fixed action space dimension $d\ge 2$ and blocking period $p>2$. The lower bound holds on the unit Euclidean ball with Gaussian noise. Both bounds recover the classical $\sqrt{T}$ regret when $\epsilon \sqrt{T}$ is small. For $p=2$, a sharper decomposition based on the direction between the two actions improves the upper bound to match the lower bound, establishing minimax optimal dependence on $T$ and $\epsilon$ up to logarithmic factors.