Showing 2026Show all
3 papers · 1 filter
cs.LG2026
Tracking the Best Strategy in an Extensive-Form Game
Stephen Pasteris, Rahul Savani, Theodore Turocy
We consider the extensive-form bandit problem where on each trial the learner plays an extensive-form game against an oblivious adversary. We focus on the notion of switching regre…
cs.CR2026
Differential Privacy in the Extensive-Form Bandit Problem
Stephen Pasteris, Rahul Savani, Theodore Turocy
We consider the extensive-form bandit problem, where on each trial the learner (a user coordinated by a server) plays an extensive-form game against an oblivious adversary, observi…
cs.CC2026
The Complexity of Sparse Win-Lose Bimatrix Games
Eleni Batziou, John Fearnley, Abheek Ghosh +1
We prove that computing an -approximate Nash equilibrium of a win-lose bimatrix game with constant sparsity is PPAD-hard for inverse-polynomial . Our result holds for 3-spars…