# Sequential Community Mode Estimation

arXiv: https://arxiv.org/abs/2111.08535 · HTML: https://mlsanity.com/paper/2111.08535/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 24 references that are in the map.
- First posted on arXiv 16 Nov 2021.

## Builds on (most cited first, 7 of 7)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Optimal Best Markovian Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1912.00636/) (2019)
- [Data Amplification: Instance-Optimal Property Estimation](https://mlsanity.com/paper/1903.01432/) (2019)
- [Sequential Mode Estimation with Oracle Queries](https://mlsanity.com/paper/1911.08197/) (2019)
- [Unified Sample-Optimal Property Estimation in Near-Linear Time](https://mlsanity.com/paper/1911.03105/) (2019)
- [Community Exploration: From Offline Optimization to Online Learning](https://mlsanity.com/paper/1811.05134/) (2018)

## Built on by (most cited first, 1 of 1)

- [Best Arm Identification in Bandits with Limited Precision Sampling](https://mlsanity.com/paper/2305.06082/) (2023)

## Abstract (arXiv)

We consider a population, partitioned into a set of communities, and study the problem of identifying the largest community within the population via sequential, random sampling of individuals. There are multiple sampling domains, referred to as boxes, which also partition the population. Each box may consist of individuals of different communities, and each community may in turn be spread across multiple boxes. The learning agent can, at any time, sample (with replacement) a random individual from any chosen box; when this is done, the agent learns the community the sampled individual belongs to, and also whether or not this individual has been sampled before. The goal of the agent is to minimize the probability of mis-identifying the largest community in a fixed budget setting, by optimizing both the sampling strategy as well as the decision rule. We propose and analyse novel algorithms for this problem, and also establish information theoretic lower bounds on the probability of error under any algorithm. In several cases of interest, the exponential decay rates of the probability of error under our algorithms are shown to be optimal up to constant factors. The proposed algorithms are further validated via simulations on real-world datasets.