Timezone: »
Poster
Efficient Pure Exploration in Adaptive Round Model
Tianyuan Jin · Jieming SHI · Xiaokui Xiao · Enhong Chen
Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #21
In the adaptive setting, many multi-armed bandit applications allow the learner to adaptively draw samples and adjust sampling strategy in rounds. In many real applications, not only the query complexity but also the round complexity need to be optimized. In this paper, we study both PAC and exact top-$k$ arm identification problems and design efficient algorithms considering both round complexity and query complexity. For PAC problem, we achieve optimal query complexity and use only $O(\log_{\frac{k}{\delta}}^*(n))$ rounds, which matches the lower bound of round complexity, while most of existing works need $\Theta(\log \frac{n}{k})$ rounds. For exact top-$k$ arm identification, we improve the round complexity factor from $\log n$ to $\log_{\frac{1}{\delta}}^*(n)$, and achieve near optimal query complexity. In experiments, our algorithms conduct far fewer rounds, and outperform state of the art by orders of magnitude with respect to query cost.
Author Information
Tianyuan Jin (University of Science and Technology of China)
Jieming SHI (NATIONAL UNIVERSITY OF SINGAPORE)
Xiaokui Xiao (National University of Singapore)
Enhong Chen (University of Science and Technology of China)
More from the Same Authors
-
2022 Poster: DARE: Disentanglement-Augmented Rationale Extraction »
Linan Yue · Qi Liu · Yichao Du · Yanqing An · Li Wang · Enhong Chen -
2022 Spotlight: Lightning Talks 5B-4 »
Yuezhi Yang · Zeyu Yang · Yong Lin · Yishi Xu · Linan Yue · Tao Yang · Weixin Chen · Qi Liu · Jiaqi Chen · Dongsheng Wang · Baoyuan Wu · Yuwang Wang · Hao Pan · Shengyu Zhu · Zhenwei Miao · Yan Lu · Lu Tan · Bo Chen · Yichao Du · Haoqian Wang · Wei Li · Yanqing An · Ruiying Lu · Peng Cui · Nanning Zheng · Li Wang · Zhibin Duan · Xiatian Zhu · Mingyuan Zhou · Enhong Chen · Li Zhang -
2022 Spotlight: DARE: Disentanglement-Augmented Rationale Extraction »
Linan Yue · Qi Liu · Yichao Du · Yanqing An · Li Wang · Enhong Chen -
2022 Poster: Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits »
Tianyuan Jin · Pan Xu · Xiaokui Xiao · Anima Anandkumar -
2022 Poster: Graph Convolution Network based Recommender Systems: Learning Guarantee and Item Mixture Powered Strategy »
Leyan Deng · Defu Lian · Chenwang Wu · Enhong Chen -
2022 Poster: MGNNI: Multiscale Graph Neural Networks with Implicit Layers »
Juncheng Liu · Bryan Hooi · Kenji Kawaguchi · Xiaokui Xiao -
2022 Poster: Cache-Augmented Inbatch Importance Resampling for Training Recommender Retriever »
Jin Chen · Defu Lian · Yucheng Li · Baoyun Wang · Kai Zheng · Enhong Chen -
2022 Poster: Recommender Forest for Efficient Retrieval »
Chao Feng · Wuchao Li · Defu Lian · Zheng Liu · Enhong Chen -
2021 Poster: EIGNN: Efficient Infinite-Depth Graph Neural Networks »
Juncheng Liu · Kenji Kawaguchi · Bryan Hooi · Yiwei Wang · Xiaokui Xiao -
2020 Poster: Semi-Supervised Neural Architecture Search »
Renqian Luo · Xu Tan · Rui Wang · Tao Qin · Enhong Chen · Tie-Yan Liu -
2020 Poster: Incorporating BERT into Parallel Sequence Decoding with Adapters »
Junliang Guo · Zhirui Zhang · Linli Xu · Hao-Ran Wei · Boxing Chen · Enhong Chen -
2020 Poster: Sampling-Decomposable Generative Adversarial Recommender »
Binbin Jin · Defu Lian · Zheng Liu · Qi Liu · Jianhui Ma · Xing Xie · Enhong Chen -
2018 Poster: Neural Architecture Optimization »
Renqian Luo · Fei Tian · Tao Qin · Enhong Chen · Tie-Yan Liu -
2012 Poster: Image Denoising and Inpainting with Deep Neural Networks »
Junyuan Xie · Linli Xu · Enhong Chen