Timezone: »
The optimization of combinatorial black-box functions is pervasive in computer science and engineering. However, the combinatorial explosion of the search space and lack of natural ordering pose significant challenges for current techniques from a theoretical and practical perspective, and require new algorithmic ideas. In this paper, we propose to adapt the recent advances in tree searches and partitioning techniques to design and analyze novel black-box combinatorial solvers. A first contribution is the analysis of a first tree-search algorithm called Optimistic Lipschitz Tree Search (OLTS) which assumes the Lipschitz constant of the function to be known. Linear convergence rates are provided for this algorithm under specific conditions, improving upon the logarithmic rates of baselines. An adaptive version, called Optimistic Combinatorial Tree Search (OCTS), is then introduced for the more realistic setup where we do not have any information on the Lipschitz constant of the function. Similar theoretical guarantees are shown to hold for OCTS and a numerical assessment is provided to illustrate the potential of tree searches with respect to state-of-the-art methods over typical benchmarks.
Author Information
Cedric Malherbe (Huawei Noah's Ark Lab)
Antoine Grosnit (Huawei Technologies Ltd.)
Rasul Tutunov (Massachusetts Institute of Technology)
Haitham Bou Ammar (Huawei R&D UK)
Jun Wang (UCL)
More from the Same Authors
-
2022 Poster: Multiagent Q-learning with Sub-Team Coordination »
Wenhan Huang · Kai Li · Kun Shao · Tianze Zhou · Matthew Taylor · Jun Luo · Dongge Wang · Hangyu Mao · Jianye Hao · Jun Wang · Xiaotie Deng -
2022 Poster: M2N: Mesh Movement Networks for PDE Solvers »
Wenbin Song · Mingrui Zhang · Joseph G Wallwork · Junpeng Gao · Zheng Tian · Fanglei Sun · Matthew Piggott · Junqing Chen · Zuoqiang Shi · Xiang Chen · Jun Wang -
2022 : Contextual Transformer for Offline Meta Reinforcement Learning »
Runji Lin · Ye Li · Xidong Feng · Zhaowei Zhang · XIAN HONG WU FUNG · Haifeng Zhang · Jun Wang · Yali Du · Yaodong Yang -
2022 : Meta-learning of Black-box Solvers Using Deep Reinforcement Learning »
Cedric Malherbe · Aladin Virmaux · Ludovic Dos Santos · Sofian Chaybouti -
2023 : Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training »
Xidong Feng · Ziyu Wan · Muning Wen · Ying Wen · Weinan Zhang · Jun Wang -
2023 : Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training »
Xidong Feng · Ziyu Wan · Muning Wen · Ying Wen · Weinan Zhang · Jun Wang -
2023 Competition: The Robot Air Hockey Challenge: Robust, Reliable, and Safe Learning Techniques for Real-world Robotics »
Puze Liu · Jonas Günster · Niklas Funk · Dong Chen · Haitham Bou Ammar · Davide Tateo · Ziyuan Liu · Jan Peters -
2023 Poster: Lending Interaction Wings to Recommender Systems with Conversational Agents »
Jiarui Jin · Xianyu Chen · Fanghua Ye · Mengyue Yang · Yue Feng · Weinan Zhang · Yong Yu · Jun Wang -
2023 Poster: End-to-End Meta-Bayesian Optimisation with Transformer Neural Processes »
Alexandre Maraval · Matthieu Zimmer · Antoine Grosnit · Haitham Bou Ammar -
2023 Poster: Invariant Learning via Probability of Sufficient and Necessary Causes »
Mengyue Yang · Yonggang Zhang · Zhen Fang · Yali Du · Furui Liu · Jean-Francois Ton · Jianhong Wang · Jun Wang -
2023 Poster: An Efficient End-to-End Training Approach for Zero-Shot Human-AI Coordination »
Xue Yan · Jiaxian Guo · Xingzhou Lou · Jun Wang · Haifeng Zhang · Yali Du -
2023 Poster: Interpretable Reward Redistribution in Reinforcement Learning: A Causal Approach »
Yudi Zhang · Yali Du · Biwei Huang · Ziyan Wang · Jun Wang · Meng Fang · Mykola Pechenizkiy -
2023 Poster: Online PCA in Converging Self-consistent Field Equations »
Xihan Li · Xiang Chen · Rasul Tutunov · Haitham Bou Ammar · Lei Wang · Jun Wang -
2023 Poster: Framework and Benchmarks for Combinatorial and Mixed-variable Bayesian Optimization »
Kamil Dreczkowski · Antoine Grosnit · Haitham Bou Ammar -
2023 Poster: ChessGPT: Bridging Policy Learning and Language Modeling »
Xidong Feng · Yicheng Luo · Ziyan Wang · Hongrui Tang · Mengyue Yang · Kun Shao · David Mguni · Yali Du · Jun Wang -
2022 Spotlight: Lightning Talks 5A-3 »
Minting Pan · Xiang Chen · Wenhan Huang · Can Chang · Zhecheng Yuan · Jianzhun Shao · Yushi Cao · Peihao Chen · Ke Xue · Zhengrong Xue · Zhiqiang Lou · Xiangming Zhu · Lei Li · Zhiming Li · Kai Li · Jiacheng Xu · Dongyu Ji · Ni Mu · Kun Shao · Tianpei Yang · Kunyang Lin · Ningyu Zhang · Yunbo Wang · Lei Yuan · Bo Yuan · Hongchang Zhang · Jiajun Wu · Tianze Zhou · Xueqian Wang · Ling Pan · Yuhang Jiang · Xiaokang Yang · Xiaozhuan Liang · Hao Zhang · Weiwen Hu · Miqing Li · YAN ZHENG · Matthew Taylor · Huazhe Xu · Shumin Deng · Chao Qian · YI WU · Shuncheng He · Wenbing Huang · Chuanqi Tan · Zongzhang Zhang · Yang Gao · Jun Luo · Yi Li · Xiangyang Ji · Thomas Li · Mingkui Tan · Fei Huang · Yang Yu · Huazhe Xu · Dongge Wang · Jianye Hao · Chuang Gan · Yang Liu · Luo Si · Hangyu Mao · Huajun Chen · Jianye Hao · Jun Wang · Xiaotie Deng -
2022 Spotlight: Multiagent Q-learning with Sub-Team Coordination »
Wenhan Huang · Kai Li · Kun Shao · Tianze Zhou · Matthew Taylor · Jun Luo · Dongge Wang · Hangyu Mao · Jianye Hao · Jun Wang · Xiaotie Deng -
2022 Spotlight: Optimistic Tree Searches for Combinatorial Black-Box Optimization »
Cedric Malherbe · Antoine Grosnit · Rasul Tutunov · Haitham Bou Ammar · Jun Wang -
2022 Poster: Enhancing Safe Exploration Using Safety State Augmentation »
Aivar Sootla · Alexander Cowen-Rivers · Jun Wang · Haitham Bou Ammar -
2022 Poster: Multi-Agent Reinforcement Learning is a Sequence Modeling Problem »
Muning Wen · Jakub Kuba · Runji Lin · Weinan Zhang · Ying Wen · Jun Wang · Yaodong Yang -
2022 Poster: A Theoretical Understanding of Gradient Bias in Meta-Reinforcement Learning »
Bo Liu · Xidong Feng · Jie Ren · Luo Mai · Rui Zhu · Haifeng Zhang · Jun Wang · Yaodong Yang -
2020 Poster: Robustness Analysis of Non-Convex Stochastic Gradient Descent using Biased Expectations »
Kevin Scaman · Cedric Malherbe