Efficient Online Linear Optimization with Approximation Algorithms
成果类型：
Article
署名作者：
Garber, Dan
署名单位：
Technion Israel Institute of Technology
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2020.1053
发表日期：
2021
页码：
204-220
关键词：
摘要：
We revisit the problem of online linear optimization in the case where the set of feasible actions is accessible through an approximated linear optimization oracle with a factor alpha multiplicative approximation guarantee. This setting in particular is interesting because it captures natural online extensions of well-studied offline linear optimization problems that are NP-hard yet admit efficient approximation algorithms. The goal here is to minimize the alpha-regret, which is the natural extension to this setting of the standard regret in online learning. We present new algorithms with significantly improved oracle complexity for both the full-information and bandit variants of the problem. Mainly, for both variants, we present alpha-regret bounds of O(T-1/3), were T is the number of prediction rounds, using only O(log T) calls to the approximation oracle per iteration, on average. These are the first results to obtain both the average oracle complexity of O(log T) (or even polylogarithmic in T) and alpha-regret bound O(T-c) for a constant c > 0 for both variants.
来源URL：