Follow the perturbed approximate leader for solving semi-bandit combinatorial optimization

doi:10.1007/s11704-020-9519-9

	Follow the perturbed approximate leader for solving semi-bandit combinatorial optimization
	Yang, Feidiao 1,2; Chen, Wei 3; Zhang, Jialin 1,2; Sun, Xiaoming 1,2
	2021-10-01
发表期刊	FRONTIERS OF COMPUTER SCIENCE
ISSN	2095-2228
卷号	15 期号:5 页码:12
摘要	Combinatorial optimization in the face of uncertainty is a challenge in both operational research and machine learning. In this paper, we consider a special and important class called the adversarial online combinatorial optimization with semi-bandit feedback, in which a player makes combinatorial decisions and gets the corresponding feedback repeatedly. While existing algorithms focus on the regret guarantee or assume there exists an efficient offline oracle, it is still a challenge to solve this problem efficiently if the offline counterpart is NP-hard. In this paper, we propose a variant of the Follow-the-Perturbed-Leader (FPL) algorithm to solve this problem. Unlike the existing FPL approach, our method employs an approximation algorithm as an offline oracle and perturbs the collected data by adding nonnegative random variables. Our approach is simple and computationally efficient. Moreover, it can guarantee a sublinear (1 + epsilon)-scaled regret of order O(T23) for any small epsilon v> 0 for an important class of combinatorial optimization problems that admit an FPTAS (fully polynomial time approximation scheme), in which T is the number of rounds of the learning process. In addition to the theoretical analysis, we also conduct a series of experiments to demonstrate the performance of our algorithm.
关键词	online learning online combinatorial optimization semi-bandit follow-the-perturbed-leader
DOI	10.1007/s11704-020-9519-9
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61832003] ; National Natural Science Foundation of China[61761136014] ; National Natural Science Foundation of China[61872334] ; 973 Program of China[2016YFB1000201] ; K.C.Wong Education Foundation
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems ; Computer Science, Software Engineering ; Computer Science, Theory & Methods
WOS记录号	WOS:000688411700001
出版者	HIGHER EDUCATION PRESS
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/17121
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Sun, Xiaoming
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Beijing 100190, Peoples R China 3.Microsoft Res Asia, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Yang, Feidiao,Chen, Wei,Zhang, Jialin,et al. Follow the perturbed approximate leader for solving semi-bandit combinatorial optimization[J]. FRONTIERS OF COMPUTER SCIENCE,2021,15(5):12.
APA	Yang, Feidiao,Chen, Wei,Zhang, Jialin,&Sun, Xiaoming.(2021).Follow the perturbed approximate leader for solving semi-bandit combinatorial optimization.FRONTIERS OF COMPUTER SCIENCE,15(5),12.
MLA	Yang, Feidiao,et al."Follow the perturbed approximate leader for solving semi-bandit combinatorial optimization".FRONTIERS OF COMPUTER SCIENCE 15.5(2021):12.