I participated today in the successful Ph.D. defense of Nikolas Patris, a student of my newly-tenured colleague Ioannis Panageas. Nikolas has been working on problems of learning Nash equilibria of games and more generally finding saddle points of smooth functions, a crossover area between theoretical computer science and machine learning. His results are theoretical but his papers on them are in machine learning conferences:

The main theme of his thesis and defense was that games can have a nice structure and still not be efficiently learnable. He started with a positive result from ICLR 2024: if the difference of the two payoff matrices of a two-player game has rank one, then the problem of finding an approximate equilibrium strategy can be reduced to a one-dimensional search over a parameterized family of zero-sum games, and approximately solved in very few iterations by an algorithm that alternates between trying to learn how to play one of these zero-sum games, and adjusting the parameter to find a game in the parameterized family that more accurately approximates the rank-one game the algorithm is really trying to solve. Rank zero is just the case of zero-sum games themselves, and for rank two it is already \(\mathsf{PPAD}\)-complete to find an equilibrium.

Next in the defense, he discussed exponential lower bounds for certain game-learning strategies. He started with cooperative games in which both players have equal payoffs; in these it is trivial to find the right strategy from a game matrix but it is still interesting to understand how quickly one can converge using simple iterative methods that do not know the matrix explicitly. He started with fictitious play in which each player chooses the move that would have the best average payoff against the previous move history. In work from NeurIPS 2023, using a game matrix containing a hidden spiral path of improving payoffs, he showed that this strategy takes factorial time to make each successive step along the path and therefore factorial time (in the number of game options) to converge to an approximately-optimal strategy. He summarized this idea, that averaging the entire past history produces a significant slowdown in convergence time, as “history creates inertia”. The same factorial slowdown also applies to “follow the regularized leader”, a family of learning algorithms with smoother dynamics that involve mixed rather than pure game strategies (ICML 2026).

In \(n\)-player games with two options per player, the slowdown is even worse. Here, the two-dimensional payoff matrix of a symmetric two-player game is replaced by a hypercube of payoffs (with equal payoffs to all players) with a dimension for the two choices of each player. Instead of a spiral path, Nikolas observed that a hidden path of improving payoffs could be realized using a solution to the “snake in the box problem”, asking for the longest induced path in a hypercube. Solutions to this problem, for an \(n\)-dimensional hypercube, have length \(\Omega(2^n)\), although the optimal constant of proportionality remains unknown. Plugging in the factorial slowdown for each step along the path, for both fictitious play and follow the regularized leader, gives a doubly exponential lower bound on the convergence time (ICML 2026). However, here the multidimensional payoff matrix has exponential size, so the slowdown is only singly exponential in the description complexity of the game instance. This motivates an interesting and unsolved variation of the snake-in-the-box problem: is it possible to find an exponentially long induced path in the hypercube so that determining whether a hypercube vertex is on the path, and if so how far along the path it lies, can be computed in polynomial time? If so it would give a concisely-represented multiplayer game with convergence time doubly exponential in the representation size.

Solution to the four-dimensional snake-in-the-box problem: a seven-vertex induced path in a 16-vertex hypercube graph

Even more generally, he considered follow the regularized leader as a method for finding saddle points of smooth functions and showed that, in this general context, it does not even reach stationarity.

Nikolas has still not settled on what to do next; he has a good postdoc offer but also has some conflicting geographic constraints. Regardless, he has produced a strong dissertation, and I was especially impressed at how clearly he explained these concepts that were in many cases not very familiar to me. Congratulations, Nikolas, and also, congratulations, Ioannis!

(Discuss on Mastodon)