Scalar Limits and Geometric Recovery in Softmax Gradient Bandits

Softmax gradient bandits can converge to the best arm, but convergence alone does not determine the cumulative reward lost during learning. This leaves open whether adaptive learning rates and reward baselines can achieve square-root worst-case regret, or whether the update structure must change. The analysis addresses this question for bounded, independent and identically distributed rewards with a unique best arm. The analysis identifies a coupling in the mean update: a common scalar rescales corrective and competing drift terms together, while the baseline cancels from the conditional mean. Beyond this local mechanism, matching lower and upper polynomial exponents characterize the entire bounded scalar class, including history- and horizon-dependent learning rates and common baselines with nonnegative steps. For each fixed number of arms $K\ge 3$, its minimax regret is of order $T^{1-1/K}$ up to logarithmic factors, uniformly over an explicit neighborhood of biased initial logits. To change this coupling, an explicit diagonal update reweights coordinates while preserving softmax sampling and single-reward feedback. It achieves square-root worst-case regret up to logarithmic factors and polylogarithmic fixed-gap regret from every fixed finite initialization, without gap or horizon inputs. These guarantees establish a polynomial separation on the common initialization domain: changing coordinate weights achieves a regret exponent unavailable through bounded scalar tuning alone.