The Oracle Complexity of Simplex-based Matrix Games

Guy Kornowski, Ohad Shamir

We study the problem of solving matrix games of the form ${\min }_{\mathbf{p}\in \hat{I}”}{\max }_{\mathbf{w}\in \mathcal{W}}{\mathbf{p}}^{\top }A\mathbf{w}$, where $A$ is a matrix and $\hat{I}”$ is the…