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
刊名	FRONTIERS OF COMPUTER SCIENCE
	2021-10-01
卷号	15 期号:5 页码:12
关键词	online learning online combinatorial optimization semi-bandit follow-the-perturbed-leader
ISSN号	2095-2228
DOI	10.1007/s11704-020-9519-9
英文摘要	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.
资助项目	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
语种	英语
出版者	HIGHER EDUCATION PRESS
WOS记录号	WOS:000688411700001
内容类型	期刊论文
源URL	[http://119.78.100.204/handle/2XEOYT63/17120]
专题	中国科学院计算技术研究所
通讯作者	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.