7 papers
Equilibrium Computation in Extensive-Form Games with Stochastic Action Sets
Thomas Schwarz, Ryann Sim, Chun Kai Ling
Extensive-form games (EFGs) are a standard model for sequential decision-making in games. A fundamental and typically implicit assumption in EFGs is that players always have access…
Solving Imperfect-Recall Games via Sum-of-Squares Optimization
Rui Zheng, Ryann Sim, Antonios Varvitsiotis
Extensive-form games (EFGs) provide a powerful framework for modeling sequential decision making, capturing strategic interaction under imperfect information, chance events, and te…
Computing Equilibria in Games with Stochastic Action Sets
Thomas Schwarz, Jiaru Li, Ryann Sim +1
The study of learning in games typically assumes that each player always has access to all of their actions. However, in many practical scenarios, players' available actions might…
Optimism Without Regularization: Constant Regret in Zero-Sum Games
John Lazarsfeld, Georgios Piliouras, Ryann Sim +1
This paper studies the optimistic variant of Fictitious Play for learning in two-player zero-sum games. While it is known that Optimistic FTRL -- a regularized algorithm with a bou…
Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies
Vincent Leon, Iosif Sakos, Ryann Sim +1
Concavity and its refinements underpin tractability in multiplayer games, where players independently choose actions to maximize their own payoffs which depend on other players' ac…
Fast and Furious Symmetric Learning in Zero-Sum Games: Gradient Descent as Fictitious Play
John Lazarsfeld, Georgios Piliouras, Ryann Sim +1
This paper investigates the sublinear regret guarantees of two non-no-regret algorithms in zero-sum games: Fictitious Play, and Online Gradient Descent with constant stepsizes. In…