Eshwar Ram Arunachaleswaran

A big congratulations and thank you to all my co-authors. Especially @ncollina.bsky.social with whom I've worked in this area for over 4 years, and Jon, who took us under his wing and reoriented us to a geometric view of algorithms

Ecstatic and deeply honored by this award. I've had great fun thinking about algorithms as strategies for repeated games over the past few years and hope that this highlight will push more researchers to come up with exciting directions in this field! Come to our talk on Monday to learn more!

*simplices

We prove minimizing profile swap-regret is necessary & sufficient for non-manipulability and gets NR +PO. Bonus: if all agents minimize it, the dynamics can reach profiles that cannot be realized as Correlated Equilibria by traditional mediators—unlike normal-form games!

Pareto-Optimal Algorithms for Learning in Games We study the problem of characterizing optimal learning algorithms for playing repeated games against an adversary with unknown payoffs. In this problem, the first player (called the learner) commits ...

Our fix? Profile Swap-Regret, a further coarsening of polytope swap-regret, leveraging a geometric view of algorithms (link). Admits an efficient algorithm with O(√T) convergence! arxiv.org/abs/2402.09549

Strategizing against Learners in Bayesian Games We study repeated two-player games where one of the players, the learner, employs a no-regret learning strategy, while the other, the optimizer, is a rational utility maximizer. We consider general Ba...

Another idea: Polytope Swap-Regret—a coarser notion based on favorable decompositions of the learner’s action - with non-manipulability + √T convergence but no known efficient algorithms
arxiv.org/abs/2205.08562

One approach treats polytope games (for eg: Bayesian games, extensive form games) as high-dimensional normal-form games → exponential blowup resulting in a tradeoff between per-round efficiency and convergence rate (O(T/log T) convergence for efficient algorithms)

In normal-form games, No-Swap-Regret (NSR) algorithms ensure no-regret, non-manipulability, & Pareto-optimality. But extending these guarantees to polytopes (instead of simplexes) is tricky

Punchline: We design an efficient no-regret algorithm for games with arbitrary polytopal actions—that is simultaneously non-manipulable, Pareto-optimal, and converging at O(√T·Poly(d)), where d is the action space dimension

Swap Regret and Correlated Equilibria Beyond Normal-Form Games Swap regret is a notion that has proven itself to be central to the study of general-sum normal-form games, with swap-regret minimization leading to convergence to the set of correlated equilibria and...

What should swap-regret mean beyond normal-form games? We have a new paper (@ncollina.bsky.social, Mehryar Mohri, Yishay Mansour, Jon Schneider, Balu Sivan) tackling this question and providing a definitive answer! (thread)

arxiv.org/abs/2502.20229

Check out our new paper, on optimal algorithmic commitments against a distribution of opponents!