Timezone: »

 
Oral
Multi-layered Network Exploration via Random Walks: From Offline Optimization to Online Learning
Xutong Liu · Jinhang Zuo · Xiaowei Chen · Wei Chen · John C. S. Lui

Wed Jul 21 07:00 PM -- 07:20 PM (PDT) @
in Bandits 4 »
Multi-layered network exploration (MuLaNE) problem is an important problem abstracted from many applications. In MuLaNE, there are multiple network layers where each node has an importance weight and each layer is explored by a random walk. The MuLaNE task is to allocate total random walk budget $B$ into each network layer so that the total weights of the unique nodes visited by random walks are maximized. We systematically study this problem from offline optimization to online learning. For the offline optimization setting where the network structure and node weights are known, we provide greedy based constant-ratio approximation algorithms for overlapping networks, and greedy or dynamic-programming based optimal solutions for non-overlapping networks. For the online learning setting, neither the network structure nor the node weights are known initially. We adapt the combinatorial multi-armed bandit framework and design algorithms to learn random walk related parameters and node weights while optimizing the budget allocation in multiple rounds, and prove that they achieve logarithmic regret bounds. Finally, we conduct experiments on a real-world social network dataset to validate our theoretical results.
Keywords: Bandits · Convex Optimization · Optimization · Reinforcement Learning and Planning

Author Information

Xutong Liu (The Chinese University of Hong Kong)
Jinhang Zuo (Carnegie Mellon University)
Xiaowei Chen (Bytedance)
Wei Chen (Microsoft)
John C. S. Lui (The Chinese University of Hong Kong)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors