Bandit Online Optimization Over the Permutahedron

Nir Ailon, Kohei Hatano, Eiji Takimoto

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 band…