5 papers
The Complexity of Computing Coarse Correlated Equilibria in Markov Games with a Single Controller
Gabriele Farina, Andreas Kontogiannis, Ioannis Panageas +1
We study the complexity of computing stationary Markov coarse correlated equilibria (CCE) in discounted single-controller stochastic (Markov) games [PR81, FV97], a fundamental subc…
Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback
Anas Barakat, Andreas Kontogiannis, Vasilis Pollatos +2
We study adversarial online learning with hidden-convex losses, i.e., nonconvex losses that become convex after a nonlinear reparameterization. Ghai, Lu and Hazan (2022) proved tha…
The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos
While first-order stationary points (FOSPs) are the traditional targets of non-convex optimization, they often correspond to undesirable strict saddle points. To circumvent this, a…
Efficient Swap Regret Minimization in Combinatorial Bandits
Andreas Kontogiannis, Vasilis Pollatos, Panayotis Mertikopoulos +1
This paper addresses the problem of designing efficient no-swap regret algorithms for combinatorial bandits, where the number of actions is exponentially large in the dimension…
Efficient Kernelized Learning in Polyhedral Games Beyond Full-Information: From Colonel Blotto to Congestion Games
Andreas Kontogiannis, Vasilis Pollatos, Gabriele Farina +2
We examine the problem of efficiently learning coarse correlated equilibria (CCE) in polyhedral games, that is, normal-form games with an exponentially large number of actions per…