Timezone: »

 
Poster
Community Exploration: From Offline Optimization to Online Learning
Xiaowei Chen · Weiran Huang · Wei Chen · John C. S. Lui

Thu Dec 06 02:00 PM -- 04:00 PM (PST) @ Room 517 AB #153
in Thu Poster Session B »

We introduce the community exploration problem that has various 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.

Keywords: Bandit Algorithms · Adaptive Data Analysis
[ Paper]  [ Poster] 

Author Information

Xiaowei Chen (The Chinese University of Hong Kong)
Weiran Huang (Huawei Noah's Ark Lab)
Wei Chen (Microsoft Research)
John C. S. Lui (The Chinese University of Hong Kong)

More from the Same Authors