AI summaryⓘ
The authors study a problem where you have several groups (or arms) and want to decide how to split a limited number of tests among them to reduce the worst uncertainty in estimating their means. They create a new way to understand the minimum possible error any strategy must have, breaking it down into three parts: the total budget of samples, how unevenly uncertainty is spread across groups, and a special complexity measure they call Variance Local Curvature (VLC). For smooth problems, VLC relates to well-known statistical information measures. Their results nearly match the best known strategies except in cases where uncertainty varies a lot between groups, and they introduce new mathematical tools to prove these findings.
multi-armed banditsactive learningmean estimationminimax lower boundheteroscedasticityvariance local curvature (VLC)Fisher informationrandom matrix theorysampling allocationuncertainty quantification
Authors
Abdellah Aznag, Rachel Cummings, Adam N. Elmachtoub
Abstract
We study a \emph{max-risk} objective for active learning in a multi-group mean estimation $d$-armed bandits: a learner adaptively allocates a budget of $T$ samples across $d$ groups to minimize the worst-case uncertainty index $\max_{k\in[d]}σ_k^2/n_k$, where $σ_k$ is the standard deviation of the distribution of arm $d$, and $n_k$ is the number of times arm $d$ is sampled. We develop a local minimax framework and prove the first general lower bound for this objective, valid for any finite-variance hypothesis class. The bound separates difficulty into three orthogonal factors: a \emph{budget} term, a \emph{heteroscedasticity} index measuring how unevenly the uncertainty is spread across arms, and a model-dependent complexity measure, the \emph{Variance Local Curvature} ($\mathrm{VLC}$), which captures how much information a local change of variance creates inside the hypothesis class. For smooth classes, the $\mathrm{VLC}$ is a reparametrization of a variance--Fisher information, with closed-form values for common families. Benchmarking against the strongest available upper bound shows near-optimality up to logarithmic factors in broad regimes, and pinpoints a systematic gap in highly heterogeneous instances. Our proof introduces two key ingredients: a loss-induced $\ell_1$ geometry on the decision space, and a representation-based instance generator that reduces hard-instance construction to an explicit random matrix calculation.