The formulation we consider here has some parallels with the classical multi-armed bandit (MAB) problem [1]}; specifically, the fixed budget best arm identification formulation [2]}. Indeed, one may interpret communities in our formulation as arms in an MAB problem. However, there are two crucial differences between the two formulations. The first difference lies in the stochastic behavior of the reward/observation sequence. In the classical MAB problem, each pull of an arm yields an i.i.d. reward drawn from an arm specific reward distribution. However, in the community mode detection problem, the sequence of collisions (or equivalently, the evolution of the number of distinct individuals seen) does not admit an i.i.d. description. (Indeed, whether or not a certain sample from a box results in a collision depends in a non-stationary manner on the history of observations from that box.) The second difference between the two formulations lies in the extent of sampling control on part of the agent. In the MAB setting, the agent can pull any arm it chooses at any sampling epoch. However, in our formulation, the agent cannot sample directly from a community of its choice; it must instead choose a box to sample from, limiting its ability to target specific communities to explore.
