Improved Bounds for Online Learning Over the Permutahedron and Other Ranking Polytopes

Consider the following game: There is a fixed set V of n items. At each step an adversary chooses a score function st: V 7 → [0, 1], a learner out-puts a ranking of V, and then st is revealed. The learner’s loss is the sum over v ∈ V, of st(v) times v’s position (0th, 1st, 2nd,...) in the rank-ing. This problem captures, for example, on-line systems that iteratively present ranked lists of items to users, who then respond by choosing one (or more) sought items. The loss measures the users ’ burden, which increases the further the sought items are from the top. It also captures a version of online rank aggregation. We present an algorithm of expected regret O(n OPT + n2), where OPT is the loss of the best (single) ranking in hindsight. This im-proves the previously best known algorithm of Suehiro et. al (2012) by saving a factor of Ω( log n). We also reduce the per-step run-ning time fromO(n2) toO(n log n). We provide matching lower bounds.