## Abstract

The permutahedron is the convex polytope with vertex set consisting of the vectors (π(1),…, π(n)) for all permutations (bijections) π over {1,…, 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 π_{t} of the permutahedron and suffers an observed instantaneous loss of ∑_{i} ^{n}=1 π_{t}(i)s_{t}(i).We study the problem in two regimes. In the first regime, s_{t} is a point in the polytope dual to the permutahedron. Algorithm CombBand of Cesa-Bianchi et al (2009) guarantees a regret of O(n√T log n) after T steps. Unfortunately, CombBand requires at each step an n-by-n matrix permanent computation, a #P-hard problem. Approximating the permanent is possible in the impractical running time of O(n^{10}), with an additional heavy inverse-polynomial dependence on the sought accuracy. We provide an algorithm of slightly worse regret O(n^{3/2}√T) but with more realistic time complexity O(n^{3}) per step. The technical contribution is a bound on the variance of the Plackett-Luce noisy sorting process’s ‘pseudo loss’, obtained by establishing positive semi-definiteness of a family of 3-by-3 matrices of rational functions in exponents of 3 parameters.In the second regime, st is in the hypercube. For this case we present and analyze an algorithm based on Bubeck et al.’s (2012) OSMD approach with a novel projection and decomposition technique for the permutahedron. The algorithm is efficient and achieves a regret of O(n√T), but for a more restricted space of possible loss vectors.

Original language | English |
---|---|

Title of host publication | Algorithmic Learning Theory - 25th International Conference, ALT 2014, Proceedings |

Editors | Peter Auer, Alexander Clark, Thomas Zeugmann, Sandra Zilles |

Publisher | Springer Verlag |

Pages | 215-229 |

Number of pages | 15 |

ISBN (Electronic) | 9783319116617 |

DOIs | |

Publication status | Published - 2014 |

Event | 25th International Conference on Algorithmic Learning Theory, ALT 2014 - Bled, Slovenia Duration: Oct 8 2014 → Oct 10 2014 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 8776 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 25th International Conference on Algorithmic Learning Theory, ALT 2014 |
---|---|

Country/Territory | Slovenia |

City | Bled |

Period | 10/8/14 → 10/10/14 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)