論文の概要: Sparsified Linear Programming for Zero-Sum Equilibrium Finding
- arxiv url: http://arxiv.org/abs/2006.03451v2
- Date: Mon, 29 Jun 2020 22:23:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-25 04:28:46.434355
- Title: Sparsified Linear Programming for Zero-Sum Equilibrium Finding
- Title(参考訳): ゼロサム均衡探索のためのスパーシファイド線形計画法
- Authors: Brian Hu Zhang, Tuomas Sandholm
- Abstract要約: 我々は、この問題に対して全く異なるアプローチを示し、それは競争力があり、しばしば、以前の最先端技術よりも桁違いに優れている。
ポーカーエンドゲームの実験により、現代の線形プログラムソルバは、ゲーム固有のCFRの現代的な変種でさえも競合することを示した。
- 参考スコア(独自算出の注目度): 89.30539368124025
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Computational equilibrium finding in large zero-sum extensive-form
imperfect-information games has led to significant recent AI breakthroughs. The
fastest algorithms for the problem are new forms of counterfactual regret
minimization [Brown and Sandholm, 2019]. In this paper we present a totally
different approach to the problem, which is competitive and often orders of
magnitude better than the prior state of the art. The equilibrium-finding
problem can be formulated as a linear program (LP) [Koller et al., 1994], but
solving it as an LP has not been scalable due to the memory requirements of LP
solvers, which can often be quadratically worse than CFR-based algorithms. We
give an efficient practical algorithm that factors a large payoff matrix into a
product of two matrices that are typically dramatically sparser. This allows us
to express the equilibrium-finding problem as a linear program with size only a
logarithmic factor worse than CFR, and thus allows linear program solvers to
run on such games. With experiments on poker endgames, we demonstrate in
practice, for the first time, that modern linear program solvers are
competitive against even game-specific modern variants of CFR in solving large
extensive-form games, and can be used to compute exact solutions unlike
iterative algorithms like CFR.
- Abstract(参考訳): 大規模なゼロサム広角不完全情報ゲームにおける計算平衡発見は、近年のAIのブレークスルーに繋がった。
この問題の最も速いアルゴリズムは、新しい形の反事実的後悔の最小化(Brown and Sandholm, 2019)です。
本稿では,従来の技術よりも競争力が高く,しばしば桁違いに優れた問題に対して,まったく異なるアプローチを提案する。
平衡フィリング問題は線形プログラム (LP) [Koller et al., 1994] として定式化できるが、LPソルバのメモリ要求のため、LPとして解くにはスケーラビリティがない。
我々は、大きなペイオフ行列を2つの行列からなる積に分解する効率的な実用的アルゴリズムを与える。
これにより,cfrより小さい対数因子のみの大きさの線形プログラムとして平衡探索問題を表現することができ,そのようなゲーム上で線形プログラムソルバを動作させることができる。
ポーカーエンドゲームに関する実験により,本研究では,現代リニアプログラムソルバが,大規模展開型ゲームの解法において,ゲーム特有のcfrの現代的変種とさえ競合することを初めて実証し,cfrのような反復的アルゴリズムと異なり,厳密な解法を計算できることを示した。
関連論文リスト
- Truly No-Regret Learning in Constrained MDPs [66.28706907897285]
未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。
提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。
論文 参考訳(メタデータ) (2024-02-24T09:47:46Z) - An efficient, provably exact, practical algorithm for the 0-1 loss
linear classification problem [4.418462313508022]
インクリメンタルセル(ICE)は,0-1損失分類問題を正確に時間内に解くことができることを示す。
この長年の問題に対する、厳格に証明された実用的なアルゴリズムとしては、これが初めてだ。
論文 参考訳(メタデータ) (2023-06-21T15:41:34Z) - Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。
我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。
我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文 参考訳(メタデータ) (2023-03-22T03:28:12Z) - Differentiable Bilevel Programming for Stackelberg Congestion Games [53.99859235245136]
Stackelberg Congestion Game (SCG) は、リーダーが利得を最大化するための二段階のプログラムである。
本研究は,従来の手法と機械学習の最新の発展を融合した,微分可能プログラミングによるSCGにアプローチする。
論文 参考訳(メタデータ) (2022-09-15T21:32:23Z) - A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for
Nonconvex Functional Constrained Optimization [27.07082875330508]
制約のない不等式問題は、マルチクラスネイマンオラクルのような多くの機械学習問題をモデル化するために用いられる。
このような緩やかな規則性の条件下では、値損失の交互化と制約違反の低減のバランスをとることは困難である。
本稿では,新しい不等式制約問題アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-07-12T16:30:34Z) - Fast and Robust Non-Rigid Registration Using Accelerated
Majorization-Minimization [35.66014845211251]
非剛性登録は、ターゲット形状と整合する非剛性な方法でソース形状を変形させるが、コンピュータビジョンにおける古典的な問題である。
既存のメソッドは通常$ell_p$型ロバストノルムを使用してアライメントエラーを測定し、変形の滑らかさを規則化する。
本稿では、アライメントと正規化のためのグローバルなスムーズなロバストノルムに基づく、ロバストな非剛体登録のための定式化を提案する。
論文 参考訳(メタデータ) (2022-06-07T16:00:33Z) - High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
共分散行列の明示的な構成を避ける新しい推論手法を提案する。
本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。
いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
論文 参考訳(メタデータ) (2022-02-25T16:35:26Z) - Coordinate Linear Variance Reduction for Generalized Linear Programming [27.365677554732304]
この問題における線形構造は、効率的でスケーラブルな1次アルゴリズムの設計に利用できることを示す。
textscclvr はスペクトルノルムではなく、線形制約行列 (GLP) の最大行ノルムに依存する(GLP) に対して、より複雑な結果をもたらす。
論文 参考訳(メタデータ) (2021-11-02T18:57:23Z) - Covariance-Free Sparse Bayesian Learning [62.24008859844098]
共分散行列の明示的な反転を回避する新しいSBL推論アルゴリズムを導入する。
私たちの手法は、既存のベースラインよりも数千倍も高速です。
我々は,SBLが高次元信号回復問題に難なく対処できる新しいアルゴリズムについて紹介する。
論文 参考訳(メタデータ) (2021-05-21T16:20:07Z) - Symbolic Regression using Mixed-Integer Nonlinear Optimization [9.638685454900047]
シンボリック回帰(SR)問題は、機械学習において難しい問題である。
混合整数非線形最適化と明示列挙法を組み合わせたハイブリッドアルゴリズムを提案する。
我々のアルゴリズムは、いくつかの合成データセットに対して、最先端のSRソフトウェアと最近の物理学に触発されたAI Feynmanという手法で競合していることを示す。
論文 参考訳(メタデータ) (2020-06-11T20:53:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。