Community Exploration: From Offline Optimization to Online Learning
We introduce the community exploration problem that has many real-world applications such as online advertising. In the problem, an explorer allocates limited budget to explore communities so as to maximize the number of members he could meet. We provide a systematic study of the community exploration problem, from offline optimization to online learning. For the offline setting where the sizes of communities are known, we prove that the greedy methods for both of non-adaptive exploration and adaptive exploration are optimal. For the online setting where the sizes of communities are not known and need to be learned from the multi-round explorations, we propose an "upper confidence" like algorithm that achieves the logarithmic regret bounds. By combining the feedback from different rounds, we can achieve a constant regret bound.
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. If the agent can adapt its allocation on the fly (scenario 2), then a greedy adaptive strategy is shown to be optimal.  In the online setting, community sizes are unknown. Perhaps because tracking overall sets S_1,…,S_m of met members is costly (space & time complexity), authors consider the restricted case where only few parameters can be maintained across rounds. More precisely, they redefined the notion of round: a round is composed of K sub-rounds in which the agent performs a strategy k_1+...+k_m=K (restricted to scenario 1 or 2, depending on the setting), and updates parameters at the end of these K sub-rounds, to then go to the next round, with in memory only these parameters.  Authors provide CUCB-based algorithms, that call offline greedy algorithms, and prove a O(log(T)) bound on regret in the setting described above.  Quality  The submission appears to be technically correct. The offline part is interesting as an operational research problem, and proofs are well-written. I think this part represent the major contribution of the paper.  Clarity  For the online part, I regret that the setting was not clearly explained. We do not know what is allowed for the learning algorithm. I think this is an important step (particularly if one wants to compete with provided solutions) that has been largely neglected. Even if the setting can be considered as “implicitly defined” from the regret definition, no justification are given for the (unnatural) restriction considered (maybe the “complexity” argument I gave above could be a reason, but I don’t find it realistic).  The more natural online setting where collision with previous rounds can be used is only considered in the future work section. It would have been better to see it before, in order to contrast with the restriction considered.  Originality  There is a significant lack of related work. For instance, the setting described in [1] is clearly related and should appear in the paper. The online setting analysis is pretty classic.  Significance  Offline results can be considered as important, the optimality of greedy algorithm being not trivial. Provided application are also relevant.  I am not convinced for the online part. I don’t see a clear and well justified setting definition that support the notion of regret used in the paper.  [1] S. Bubeck, D. Ernst, and A. Garivier. Optimal discovery with probabilistic expert advice: finite time  analysis and macroscopic optimality. Journal of Machine Learning Research, 14:601–623, 2013.