Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Bandit Online Optimization Over the Permutahedron   The permutahedron is the convex polytope with vertex set consisting of the
vectors $(\pi(1),\dots, \pi(n))$ for all permutations (bijections) $\pi$ over
$\{1,\dots, n\}$. We study a bandit game in which, at each step $t$, an
adversary chooses a hidden weight weight vector $s_t$, a player chooses a
vertex $\pi_t$ of the permutahedron and suffers an observed loss of
$\sum_{i=1}^n \pi(i) s_t(i)$.
  A previous algorithm CombBand of Cesa-Bianchi et al (2009) guarantees a
regret of $O(n\sqrt{T \log n})$ for a time horizon of $T$. Unfortunately,
CombBand requires at each step an $n$-by-$n$ matrix permanent approximation to
within improved accuracy as $T$ grows, resulting in a total running time that
is super linear in $T$, making it impractical for large time horizons.
  We provide an algorithm of regret $O(n^{3/2}\sqrt{T})$ with total time
complexity $O(n^3T)$. The ideas are a combination of CombBand and a recent
algorithm by Ailon (2013) for online optimization over the permutahedron in the
full information setting. The technical core is a bound on the variance of the
Plackett-Luce noisy sorting process's "pseudo loss". The bound is obtained by
establishing positive semi-definiteness of a family of 3-by-3 matrices
generated from rational functions of exponentials of 3 parameters.

36
The categories of this paper are: cmp-lg
5
The categories of this paper are: gr-qc
12
The categories of this paper are: nucl-th
19
The categories of this paper are: eess
31
The categories of this paper are: ao-sci
11
The categories of this paper are: hep-lat
13
The categories of this paper are: quant-ph
17
The categories of this paper are: q-fin
15
The categories of this paper are: nucl-ex
7
The categories of this paper are: hep-th
22
The categories of this paper are: chao-dyn
10
The categories of this paper are: q-bio
26
The categories of this paper are: bayes-an
8
The categories of this paper are: hep-ex
24
The categories of this paper are: dg-ga
16
The categories of this paper are: stat