6 papers
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…
Tree-based Focused Web Crawling with Reinforcement Learning
Andreas Kontogiannis, Dimitrios Kelesis, Vasilis Pollatos +2
A focused crawler aims at discovering as many web pages and web sites relevant to a target topic as possible, while avoiding irrelevant ones. Reinforcement Learning (RL) has been a…
On Corruption-Robustness in Performative Reinforcement Learning
Vasilis Pollatos, Debmalya Mandal, Goran Radanovic
In performative Reinforcement Learning (RL), an agent faces a policy-dependent environment: the reward and transition functions depend on the agent's policy. Prior work on performa…