Timezone: »
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.
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
-
2022 Poster: Tiered Reinforcement Learning: Pessimism in the Face of Uncertainty and Constant Regret »
Jiawei Huang · Li Zhao · Tao Qin · Wei Chen · Nan Jiang · Tie-Yan Liu -
2023 Poster: Scalable Fair Influence Maximization »
Xiaobin Rui · Zhixiao Wang · Jiayu Zhao · Lichao Sun · Wei Chen -
2023 Poster: Online Corrupted User Detection and Regret Minimization »
Zhiyong Wang · Jize Xie · Tong Yu · Shuai Li · John C.S. Lui -
2023 Poster: Multi-Fidelity Multi-Armed Bandits Revisited »
Xuchuang Wang · Qingyun Wu · Wei Chen · John C.S. Lui -
2023 Poster: Block Broyden's Methods for Solving Nonlinear Equations »
Chengchang Liu · Cheng Chen · Luo Luo · John C.S. Lui -
2023 Poster: Online Clustering of Bandits with Misspecified User Models »
Zhiyong Wang · Jize Xie · Xutong Liu · Shuai Li · John C.S. Lui -
2023 Poster: Uncertainty-Aware Instance Reweighting for Off-Policy Learning »
Xiaoying Zhang · Junpu Chen · Hongning Wang · Hong Xie · Yang Liu · John C.S. Lui · Hang Li -
2022 Spotlight: Tiered Reinforcement Learning: Pessimism in the Face of Uncertainty and Constant Regret »
Jiawei Huang · Li Zhao · Tao Qin · Wei Chen · Nan Jiang · Tie-Yan Liu -
2022 Spotlight: Lightning Talks 4A-1 »
Jiawei Huang · Su Jia · Abdurakhmon Sadiev · Ruomin Huang · Yuanyu Wan · Denizalp Goktas · Jiechao Guan · Andrew Li · Wei-Wei Tu · Li Zhao · Amy Greenwald · Jiawei Huang · Dmitry Kovalev · Yong Liu · Wenjie Liu · Peter Richtarik · Lijun Zhang · Zhiwu Lu · R Ravi · Tao Qin · Wei Chen · Hu Ding · Nan Jiang · Tie-Yan Liu -
2022 Poster: Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms »
Xutong Liu · Jinhang Zuo · Siwei Wang · Carlee Joe-Wong · John C.S. Lui · Wei Chen -
2021 Poster: Combinatorial Pure Exploration with Bottleneck Reward Function »
Yihan Du · Yuko Kuroki · Wei Chen -
2021 Poster: The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle »
Fang Kong · Yueran Yang · Wei Chen · Shuai Li -
2021 Poster: Cooperative Stochastic Bandits with Asynchronous Agents and Constrained Feedback »
Lin Yang · Yu-Zhen Janice Chen · Stephen Pasteris · Mohammad Hajiesmaili · John C. S. Lui · Don Towsley -
2020 Poster: Adversarial Bandits with Corruptions »
Lin Yang · Mohammad Hajiesmaili · Mohammad Sadegh Talebi · John C. S. Lui · Wing Shing Wong -
2020 Poster: Online Influence Maximization under Linear Threshold Model »
Shuai Li · Fang Kong · Kejie Tang · Qizhi Li · Wei Chen -
2020 Poster: Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits »
Siwei Wang · Longbo Huang · John C. S. Lui -
2019 Poster: Adaptive Influence Maximization with Myopic Feedback »
Binghui Peng · Wei Chen -
2017 Poster: Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications »
Qinshi Wang · Wei Chen -
2017 Poster: Influence Maximization with $\varepsilon$-Almost Submodular Threshold Functions »
Qiang Li · Wei Chen · Institute of Computing Xiaoming Sun · Institute of Computing Jialin Zhang -
2016 Poster: Combinatorial Multi-Armed Bandit with General Reward Functions »
Wei Chen · Wei Hu · Fu Li · Jian Li · Yu Liu · Pinyan Lu -
2015 Poster: Stochastic Online Greedy Learning with Semi-bandit Feedbacks »
Tian Lin · Jian Li · Wei Chen -
2014 Poster: Combinatorial Pure Exploration of Multi-Armed Bandits »
Shouyuan Chen · Tian Lin · Irwin King · Michael R Lyu · Wei Chen -
2014 Oral: Combinatorial Pure Exploration of Multi-Armed Bandits »
Shouyuan Chen · Tian Lin · Irwin King · Michael R Lyu · Wei Chen