Exploration-free Algorithms for Multi-group Mean Estimation

We address the problem of multi-group mean estimation, which seeks to allocate a finite sampling budget across multiple groups to obtain uniformly accurate estimates of their means. Unlike classical multi-armed bandits, whose objective is to minimize regret by identifying and exploiting the best arm, the optimal allocation in this setting requires sampling every group on the order of $\Theta(T)$ times. This fundamental distinction makes exploration-free algorithms both natural and effective. Our work makes three contributions. First, we strengthen the existing results on subgaussian variance concentration using the Hanson-Wright inequality and identify a class of strictly subgaussian distributions that yield sharper guarantees. Second, we design exploration-free non-adaptive and adaptive algorithms, and we establish tighter regret bounds than the existing results. Third, we extend the framework to contextual bandit settings, an underexplored direction, and propose algorithms that leverage side information with provable guarantees. Overall, these results position exploration-free allocation as a principled and efficient approach to multi-group mean estimation, with potential applications in experimental design, personalization, and other domains requiring accurate multi-group inference.

Many real-world studies need accurate estimates for several groups at once, such as different patient populations, survey groups, customer segments, or treatment options in an experiment. A common challenge is deciding how many samples to collect from each group when the total budget is limited and the uncertainty within each group is not known in advance. This paper studies this allocation problem and shows that, unlike settings where the goal is to find only the best option, accurate estimation requires collecting data from every group. We use this structure to design simple procedures that do not need a separate trial-and-error stage: the data collected to understand each group’s uncertainty also directly contributes to the final estimates. We also extend the idea to settings where extra information about each individual or situation is available, such as in personalized recommendations or online experiments. Our results show that these methods can allocate samples efficiently while keeping estimates accurate across groups. This can help make surveys, experiments, and data-driven decisions more reliable for diverse populations.