Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving

Abstract

We develop new parameter-free and scale-free algorithms for solving convex-concave saddle-point problems. Our results are based on a new simple regret minimizer, the Conic Blackwell Algorithm${}^{+}$ (CBA${}^{+}$), which attains $O(1/\sqrt{T})$ average regret. Intuitively, our approach generalizes to other decision sets of interest ideas from the Counterfactual Regret minimization (CFR${}^{+}$) algorithm, which has very strong practical performance for solving sequential games on simplexes. We show how to implement CBA${}^{+}$ for the simplex, ${\ell }_p$ norm balls, and ellipsoidal confidence regions in the simplex, and we present numerical experiments for solving matrix games and distributionally robust optimization problems. Our empirical results show that CBA${}^{+}$ is a simple algorithm that outperforms state-of-the-art methods on synthetic data and real data instances, without the need for any choice of step sizes or other algorithmic parameters.

References in corpus (11)

• DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker
• Online Learning with Predictable Sequences
• Fast Convergence of Regularized Learning in Games
• Online Learning: A Modern Introduction Using Convex Optimization
• Efficiently Solving MDPs with Stochastic Mirror Descent
• Solving Large Sequential Games with the Excessive Gap Technique
• Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions
• Regret Circuits: Composability of Regret Minimizers
• Increasing Iterate Averaging for Solving Saddle-Point Problems
• First-Order Methods for Wasserstein Distributionally Robust MDP
• An Online Convex Optimization Approach to Blackwell's Approachability