Efficient Online Linear Optimization with Approximation Algorithms

摘要

We revisit the problem of extit{online linear optimization} in case the setof feasible actions is accessible through an approximated linear optimizationoracle with a factor $lpha$ multiplicative approximation guarantee. Thissetting is in particular interesting since it captures natural onlineextensions of well-studied extit{offline} linear optimization problems whichare NP-hard, yet admit efficient approximation algorithms. The goal here is tominimize the $lpha$extit{-regret} which is the natural extension of thestandard extit{regret} in extit{online learning} to this setting. We present new algorithms with significantly improved oracle complexity forboth the full information and bandit variants of the problem. Mainly, for bothvariants, we present $lpha$-regret bounds of $O(T^{-1/3})$, were $T$ is thenumber of prediction rounds, using only $O(log{T})$ calls to the approximationoracle per iteration, on average. These are the first results to obtain bothaverage oracle complexity of $O(log{T})$ (or even poly-logarithmic in $T$) and$lpha$-regret bound $O(T^{-c})$ for a constant $c>0$, for both variants.