Reviews: Community Exploration: From Offline Optimization to Online Learning

Summary In the submission, authors explore a new "community exploration problem", both in an offline and online setting: An agent choose at each round t \in [K] one community among C_1,…,C_m. Then, a member is uniformly sampled (with replacement) from the chosen community. The goal for the agent is to maximize the overall number of distinct members sampled. In the offline setting, the agent knows each community size. If the allocation strategy k_1 ... k_m K has to be given before the beginning of the game (scenario 1), then a greedy non-adaptive strategy is shown to be optimal.