Online Decision-Making in General Combinatorial Spaces
We study online combinatorial decision problems, where one must make sequential decisions in some combinatorial space without knowing in advance the cost of decisions on each trial; the goal is to minimize the total regret over some sequence of trials relative to the best fixed decision in hindsight. Such problems have been studied mostly in settings where decisions are represented by Boolean vectors and costs are linear in this representation. Here we study a general setting where costs may be linear in any suitable low-dimensional vector representation of elements of the decision space. We give a general algorithm for such problems that we call low-dimensional online mirror descent (LDOMD); the algorithm generalizes both the Component Hedge algorithm of Koolen et al. (2010), and a recent algorithm of Suehiro et al. (2012). Our study offers a unification and generalization of previous work, and emphasizes the role of the convex polytope arising from the vector representation of the decision space; while Boolean representations lead to 0-1 polytopes, more general vector representations lead to more general polytopes. We study several examples of both types of polytopes. Finally, we demonstrate the benefit of having a general framework for such problems via an application to an online transportation problem; the associated transportation polytopes generalize the Birkhoff polytope of doubly stochastic matrices, and the resulting algorithm generalizes the PermELearn algorithm of Helmbold and Warmuth (2009).
The paper considers online learning of combinatorial decision problems.A new method LDOMD is introduced, which generalizes the Component Hedgealgorithm of Koolen et al. [14] for 0/1-polytopes and the method ofSuehiro et al. [15] for polytopes associated with submodular functions.In Theorem 3, a general regret bound is established for LDOMD, which isclaimed to be optimal for 0/1-polytopes. Some new polytopes areconsidered, but, with the possible exception of the transportationpolytope, they appear to be minor generalizations of the polytopes of[14] and [15]. Thus, the main contribution of the paper appears to be aunification of the results of [14] and [15].*** Changes after author response ***[Deleted claim that Thm 3 is suboptimal, which was incorrect, as theauthors pointed out in their response.]The provided unification is satisfying, but does not seem to lead tomany new applications. The exception might be the transportationpolytope, which the authors argue is "truly novel and non-trivial".On the whole, I would judge the paper as borderline. I am not sure thatthe transportation polytope is technically a very large step forward,but it does appear practically important. This tips the balance towardsaccept.*** End of changes after author response ***Other remarks:Since both [14] and [15] give bounds in terms of L* instead of T, itshould be discussed that the weakening to T is still sufficientlyinteresting.Sections 3.1,3.2: It seems unfair to apply Hedge to the whole class cal{C}          instead of only the subset with ||phi(c)||_1 <= m, which would          give a better bound that would be easier to compare to the          bound for LDOMD.line 196: although true, it is actually not so easy to see that F is          1/m-strongly convex, and, since x^1 is not explicitly          specified, it is also not that obvious that B_F(phi(c),x^1) <= m log(d/m).