11 papers
The Complexity of Computing Nash Equilibria in Colonel Blotto Games
Vasilis Pollatos, Andreas Kontogiannis
We study the complexity of Nash equilibrium computation in discrete Colonel Blotto games. For two-player general-sum Colonel Blotto with monotonic piecewise-constant battlefield pa…
Finding a Positive Index Nash Equilibrium is PPADS-Complete
Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos +1
Every nondegenerate bimatrix game has a Nash equilibrium of Shapley index +1, since all equilibria are isolated, have index +1 or -1, and their indices sum to +1. We prove that the…
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
The complexity of finding second-order stationary points (SOSPs) in constrained settings has remained unclear and has been highlighted as an open question by the works of Hollender…
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…
Enhancing Cooperative Multi-Agent Reinforcement Learning with State Modelling and Adversarial Exploration
Andreas Kontogiannis, Konstantinos Papathanasiou, Yi Shen +3
Learning to cooperate in distributed partially observable environments with no communication abilities poses significant challenges for multi-agent deep reinforcement learning (MAR…
An Extended Benchmarking of Multi-Agent Reinforcement Learning Algorithms in Complex Fully Cooperative Tasks
George Papadopoulos, Andreas Kontogiannis, Foteini Papadopoulou +3
Multi-Agent Reinforcement Learning (MARL) has recently emerged as a significant area of research. However, MARL evaluation often lacks systematic diversity, hindering a comprehensi…
XDQN: Inherently Interpretable DQN through Mimicking
Andreas Kontogiannis, George Vouros
Although deep reinforcement learning (DRL) methods have been successfully applied in challenging tasks, their application in real-world operational settings is challenged by method…
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…