Multinomial policies for large-scale bandit convex optimization on the simplex: algorithm design and performance analysis

Optimization over the simplex arises in a wide range of large-scale resource and workload allocation problems. We study an unknown convex objective through noisy one-point feedback and develop a multinomial-policy method that samples feasible allocations. A geometry-adapted stochastic mirror descent update learns the policy mean, while first-order comparisons connect its gradients to regret for the original objective even when the policy value is nonconvex. We prove sublinear regret with explicit dimension dependence for general convex objectives, sharper bounds under smoothness and, with additional structure, optimizer sparsity, and guarantees for boundary optima. Numerical experiments compare fixed-reference multinomial updates with simplex baselines.