Solving Optimization Problems with Blackwell Approachability

In this paper, we propose a new algorithm for solving convex-concave saddle-point problems using regret minimization in the repeated game framework. To do so, we introduce the Conic Blackwell Algorithm⁺ ($\mathsf{\text{CB}}{\mathsf{A}}^{\mathsf{+}}$), a new parameter- and scale-free regret minimizer for general convex compact sets. $\mathsf{\text{CB}}{\mathsf{A}}^{\mathsf{+}}$ is based on Blackwell approachability and attains $O(\sqrt{T})$ regret. We show how to efficiently instantiate $\mathsf{\text{CB}}{\mathsf{A}}^{\mathsf{+}}$ for many decision sets of interest, including the simplex, ${\mathcal{\ell }}_p$ norm balls, and ellipsoidal confidence regions in the simplex. Based on $\mathsf{\text{CB}}{\mathsf{A}}^{\mathsf{+}}$, we introduce $\mathsf{SP-CB}{\mathsf{A}}^{\mathsf{+}}$, a new parameter-free algorithm for solving convex-concave saddle-point problems achieving a $O(1/\sqrt{T})$ ergodic convergence rate. In our simulations, we demonstrate the wide applicability of $\mathsf{SP-CB}{\mathsf{A}}^{\mathsf{+}}$ on several standard saddle-point problems from the optimization and operations research literature, including matrix games, extensive-form games, distributionally robust logistic regression, and Markov decision processes. In each setting, $\mathsf{SP-CB}{\mathsf{A}}^{\mathsf{+}}$ achieves state-of-the-art numerical performance and outperforms classical methods, without the need for any choice of step sizes or other algorithmic parameters.

Funding: J. Grand-Clément is supported by the Agence Nationale de la Recherche [Grant 11-LABX-0047] and by Hi! Paris. C. Kroer is supported by the Office of Naval Research [Grant N00014-22-1-2530] and by the National Science Foundation [Grant IIS-2147361].