論文の概要: 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のような反復的アルゴリズムと異なり,厳密な解法を計算できることを示した。
関連論文リスト
- Infrequent Resolving Algorithm for Online Linear Programming [3.247415064064425]
既存のオンライン線形プログラミング(OLP)アルゴリズムは、LPベースアルゴリズムとLPフリーアルゴリズムの2つのカテゴリに分類される。
本稿では,LPを時間的水平線上でのO(loglog T)$倍だけ解きながら,常に後悔するアルゴリズムを提案する。
我々のアルゴリズムは、LPの$O(loglog T)$ timesと$Oleft(T(1/2+epsilon)Mright)$ regretを、LPの$M$ timesを解くことで、絶え間ない後悔を保証できる。
論文 参考訳（メタデータ） (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) - Differentiable Bilevel Programming for Stackelberg Congestion Games [47.60156422249365]
Stackelberg Congestion Game (SCG) において、リーダーは、群集が集まる平衡状態を予測し、操作することで、自身の利益を最大化することを目的としている。
本稿では,従来の手法と機械学習における最新の微分可能プログラミング技術を組み合わせることで,この計算課題に挑戦する。
本稿では,SCGの局所探索アルゴリズムを2つ提案する。第1に,微分可能プログラミングを用いてILDをアンロールすることで導関数を求める勾配降下アルゴリズムを提案する。
第二のアルゴリズムは、フォロワーの進化軌道を短くすることでツイストを加える。
論文 参考訳（メタデータ） (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) - 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) - Boosting Data Reduction for the Maximum Weight Independent Set Problem
Using Increasing Transformations [59.84561168501493]
最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。
驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。
提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
論文 参考訳（メタデータ） (2020-08-12T08:52:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。