The minimax regret conjecture for stochastic bandit convex optimization

Let $d$ be the dimension, let $\calA$ denote the action space, and let $\mathfrak R_T^\star(d;\calA)$ be the minimax expected regret after $T$ rounds in stochastic bandit convex optimization. The two action spaces under consideration are the unconstrained space $\calA=\bbR^d$ and the Euclidean unit ball $\calA=\bbB_2^d$. Here $\widetilde{\Theta}$ suppresses polylogarithmic factors and $a\wedge b=\min\{a,b\}$. Minimax regret conjecture. In both the unconstrained setting and the Euclidean-ball setting,

$$\mathfrak R_T^\star(d;\calA)=\widetilde{\Theta}\bigl(d^{3/2}\sqrt{T}\wedge T\bigr).$$

The conjecture refines an earlier conjecture of Bubeck, Eldan, and Lee. The best-known upper bounds have leading term $\widetilde{\mathcal{O}}(d^{3/2}\sqrt{T})$ in both settings, while the paper's construction gives a larger lower-bound exponent only for a different regime and does not establish the conjectured minimax rate.