Solving Optimization Problems with Blackwell Approachability

• 成果类型: Article; Early Access
• 署名作者: Grand-Clement, Julien; Kroer, Christian
• 署名单位: Columbia University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2023.1376
• 发表日期: 2023
• 关键词: markov decision-processes; robust; CONVERGENCE; regret; Poker

摘要

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+ (CBA+), a new parameter- and scale-free regret minimizer for general convex compact sets. CBA+ is based on Blackwell approachability and attains O( T ) regret. We show how to efficiently instantiate CBA+ for many decision sets of interest, including the simplex, lp norm balls, and ellipsoidal confidence regions in the simplex. Based on CBA+, we introduce SP-CBA+, 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-CBA+ on several standard saddle-point problems from the optimization and operations research literature, including matrix games, extensiveform games, distributionally robust logistic regression, and Markov decision processes. In each setting, SP-CBA+ achieves state-of-the-art numerical performance and outperforms classical methods, without the need for any choice of step sizes or other algorithmic parameters.