Tung Mai

Constant Swap Regret in General-Sum Games via Optimistic Transition Matrices

The Nelson-Nguyen Conjecture via Mean-to-Moments Concentration

An oblivious subspace embedding (OSE) is a distribution over matrices that approximately preserves the squared Euclidean norm of every vector in any fixed low-dimensional subspace. We prove the Nelson-Nguyen conjecture: for every $0<\delta<1$, there exists a distribution that gives an OSE with embedding dimension $O((d...

Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism

We give deterministic and uncoupled learning dynamics for finite multiplayer general-sum games under full-information feedback that achieve constant individual swap regret in self-play, independent of the horizon $T$. With $n$ players and at most $m$ actions each, every player's individual swap regret is $O(\sqrt n\,m\...