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 + ( CB A + ), a new parameter- and scale-free regret minimizer for general convex compact sets. CB A + is based on Blackwell approachability and attains O ( T ) regret. We show how to efficiently instantiate CB A + for many decision sets of interest, including the simplex, ℓ p norm balls, and ellipsoidal confidence regions in the simplex. Based on CB A + , we introduce SP-CB A + , a new parameter-free algorithm for solving convex-concave saddle-point problems achieving a O ( 1 / T ) ergodic convergence rate. In our simulations, we demonstrate the wide applicability of SP-CB A + 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, SP-CB A + achieves state-of-the-art numerical performance and outperforms classical methods, without the need for any choice of step sizes or other algorithmic parameters.