Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria

2021-05-27 · Gabriele Farina, Christian Kroer, Tuomas Sandholm

We study the application of iterative first-order methods to the problem of computing equilibria of large-scale two-player extensive-form games. First-order methods must typically be instantiated with a regularizer that serves as a distance-generating function for the decision sets of the players. For the case of two-player zero-sum games, the state-of-the-art theoretical convergence rate for Nash equilibrium is achieved by using the dilated entropy function. In this paper, we introduce a new entropy-based distance-generating function for two-player zero-sum games, and show that this function achieves significantly better strong convexity properties than the dilated entropy, while maintaining the same easily-implemented closed-form proximal mapping. Extensive numerical simulations show that these superior theoretical properties translate into better numerical performance as well. We then generalize our new entropy distance function, as well as general dilated distance functions, to the scaled extension operator. The scaled extension operator is a way to recursively construct convex sets, which generalizes the decision polytope of extensive-form games, as well as the convex polytopes corresponding to correlated and team equilibria. By instantiating first-order methods with our regularizers, we develop the first accelerated first-order methods for computing correlated equilibra and ex-ante coordinated team equilibria. Our methods have a guaranteed $1/T$ rate of convergence, along with linear-time proximal updates.

📄 PDF Abstract BibTeX arXiv:2105.12954

Code (0)

등록된 구현이 없습니다.

Tasks

Form

Unifying Framework for Fast Learning Rate of Non-Sparse Multiple Kernel Learning

2011-12-01 · NeurIPS 2011 12 · Taiji Suzuki

In this paper, we give a new generalization error bound of Multiple Kernel Learning (MKL) for a general class of regularizations. Our main target in this paper is dense type regularizations including ℓp-MKL that impose…

Vocal Bursts Type Prediction

Distributional Robustness and Regularization in Reinforcement Learning

2020-03-05 · Esther Derman, Shie Mannor

Distributionally Robust Optimization (DRO) has enabled to prove the equivalence between robustness and regularization in classification and regression, thus providing an analytical reason why regularization generalizes w…

Decision Making reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+1

FoCL: Feature-Oriented Continual Learning for Generative Models

2020-03-09 · Qicheng Lao, Mehrzad Mortazavi, Marzieh Tahaei, Francis Dutil 외

In this paper, we propose a general framework in continual learning for generative models: Feature-oriented Continual Learning (FoCL). Unlike previous works that aim to solve the catastrophic forgetting problem by introd…

Continual Learning Incremental Learning

Primal-Dual Sequential Subspace Optimization for Saddle-point Problems

2020-08-20 · Yoni Choukroun, Michael Zibulevsky, Pavel Kisilev

We introduce a new sequential subspace optimization method for large-scale saddle-point problems. It solves iteratively a sequence of auxiliary saddle-point problems in low-dimensional subspaces, spanned by directions de…

MPC-Inspired Neural Network Policies for Sequential Decision Making

2018-02-15 · Marcus Pereira, David D. Fan, Gabriel Nakajima An, Evangelos Theodorou

In this paper we investigate the use of MPC-inspired neural network policies for sequential decision making. We introduce an extension to the DAgger algorithm for training such policies and show how they have improved tr…

Decision Making Sequential Decision Making