論文の概要: 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のような反復的アルゴリズムと異なり,厳密な解法を計算できることを示した。
関連論文リスト
- Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation [52.16923999754027]
そこで我々は,Stackelbergの大規模相関平衡の計算アルゴリズムを提案する。
また,大域的相関平衡を近似計算するアルゴリズムも提案する。
ほぼ最適なEFCEのアルゴリズムは、私たちの知る限り、3つのデシラタを同時に達成した最初のアルゴリズムである。
論文 参考訳（メタデータ） (2024-12-22T09:12:05Z) - Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
大規模言語モデルのテスト時間計算のための2つの原理的アルゴリズムを提案する。
理論的には、1つのアルゴリズムの故障確率は、そのテスト時間計算が大きくなるにつれて指数関数的に減衰する。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - Infrequent Resolving Algorithm for Online Linear Programming [3.247415064064425]
既存のオンライン線形プログラミング(OLP)アルゴリズムは、LPベースアルゴリズムとLPフリーアルゴリズムの2つのカテゴリに分類される。
本稿では,LPを数個の時間点で解き,他の時間点で1次計算を行うアルゴリズムを提案する。
我々の研究は、販売ラインの開始と終了の両方で解決する価値を強調し、パフォーマンスの保証を証明するための新しいフレームワークを提供します。
論文 参考訳（メタデータ） (2024-08-01T11:09:01Z) - Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
未知の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) - A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization [35.003192679045675]
制約のない不等式問題は、マルチクラスネイマンオラクルのような多くの機械学習問題をモデル化するために用いられる。
このような緩やかな規則性の条件下では、値損失の交互化と制約違反の低減のバランスをとることは困難である。
本稿では,新しい不等式制約問題アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-12T16:30:34Z) - Covariance-Free Sparse Bayesian Learning [62.24008859844098]
共分散行列の明示的な反転を回避する新しいSBL推論アルゴリズムを導入する。
私たちの手法は、既存のベースラインよりも数千倍も高速です。
我々は,SBLが高次元信号回復問題に難なく対処できる新しいアルゴリズムについて紹介する。
論文 参考訳（メタデータ） (2021-05-21T16:20:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。