論文の概要: Nash Equilibria via Stochastic Eigendecomposition
- arxiv url: http://arxiv.org/abs/2411.02308v1
- Date: Mon, 04 Nov 2024 17:32:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-05 21:27:20.073250
- Title: Nash Equilibria via Stochastic Eigendecomposition
- Title（参考訳）: 確率的固有分解によるナッシュ平衡
- Authors: Ian Gemp,
- Abstract要約: ナッシュ均衡は、パラメータへの純粋呼び出し、値分解とパワーの反復的変動によって近似できることを示す。
一般のゲームにおけるすべての平衡を、容易に利用できる線形代数ツールのみを用いて解くことを証明する擬符号と実験を提供する。
- 参考スコア（独自算出の注目度）: 4.190518009892366
- License:
- Abstract: This work proposes a novel set of techniques for approximating a Nash equilibrium in a finite, normal-form game. It achieves this by constructing a new reformulation as solving a parameterized system of multivariate polynomials with tunable complexity. In doing so, it forges an itinerant loop from game theory to machine learning and back. We show a Nash equilibrium can be approximated with purely calls to stochastic, iterative variants of singular value decomposition and power iteration, with implications for biological plausibility. We provide pseudocode and experiments demonstrating solving for all equilibria of a general-sum game using only these readily available linear algebra tools.
- Abstract（参考訳）: 本研究は,有限な正規形式ゲームにおいてナッシュ均衡を近似する新しい手法を提案する。
これは、チューナブルな複雑性を持つ多変量多項式のパラメータ化系を解くものとして、新しい再構成を構築することで実現される。
そうすることで、ゲーム理論から機械学習、バックまで、反復的なループをフォージします。
ナッシュ均衡は、純粋に確率的かつ反復的な特異値分解とパワー反復の変動を、生物学的な可算性に含めることで近似できることを示す。
我々は、これらの容易に利用可能な線形代数ツールのみを用いて、一般サムゲームの全平衡の解決を実証する擬符号と実験を提供する。
関連論文リスト
- Last-Iterate Convergence of Payoff-Based Independent Learning in Zero-Sum Stochastic Games [31.554420227087043]
両プレイヤー間のペイオフベース、収束、合理的、対称な学習ダイナミクスを開発する。
行列ゲーム設定では、結果はナッシュ分布を見つけるために$O(epsilon-1)$の複雑さを意味する。
ゲーム設定では、結果はナッシュ平衡を求めるために$O(epsilon-8)$の複雑さをも意味している。
論文 参考訳（メタデータ） (2024-09-02T20:07:25Z) - Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale Algorithm Under Weak Reachability [11.793922711718645]
我々は,ゼロサムゲームにおいて,プレイヤーが情報のみを閲覧し,相手の行動や支払いを行うような分散学習を検討する。
従来の研究は、強い到達可能性仮定の下で二重時間スケールのアルゴリズムを用いて、この設定でナッシュ均衡に収束することを示した。
我々の貢献は合理的で収束したアルゴリズムであり、Tsallis-Entropy regularization を値イテレーションに基づくアルゴリズムで利用している。
論文 参考訳（メタデータ） (2023-12-13T09:31:30Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳（メタデータ） (2023-01-19T11:36:50Z) - Learning Two-Player Mixture Markov Games: Kernel Function Approximation
and Correlated Equilibrium [157.0902680672422]
非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。
双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-10T14:21:54Z) - A Stochastic Halpern Iteration with Variance Reduction for Stochastic
Monotone Inclusion Problems [17.597000481404883]
機械学習アプリケーションで広く見られるモノトーン包摂問題について検討する。
我々のアルゴリズムは、$mathcalO(frac1epsilon3)$演算子の評価で演算子に$epsilon$ノルムを得る。
論文 参考訳（メタデータ） (2022-03-17T16:48:57Z) - A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。
提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
論文 参考訳（メタデータ） (2021-10-07T17:51:10Z) - Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
有限$n$-playerの正規形式ゲームに対して,Nash平衡を近似的に計算するための一般的なメタ学習手法を提案する。
ゲーム毎のナッシュ均衡をスクラッチから近似あるいは学習する既存の解とは異なり、メタソルバはゲームユーティリティ行列からジョイント戦略プロファイルへの写像を直接構築する。
論文 参考訳（メタデータ） (2021-08-17T07:06:46Z) - Better Regularization for Sequential Decision Spaces: Fast Convergence
Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
大規模2プレーヤワイドフォームゲームの計算平衡問題に対する反復的な一階法の適用について検討する。
正則化器を用いて一階法をインスタンス化することにより、相関平衡と元アンティー座標のチーム平衡を計算するための最初の加速一階法を開発する。
論文 参考訳（メタデータ） (2021-05-27T06:10:24Z) - Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。
本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
論文 参考訳（メタデータ） (2021-02-23T05:11:07Z) - Competitive Mirror Descent [67.31015611281225]
制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。
本稿では, 競合ミラー降下法(CMD)を提案する。
特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-06-17T22:11:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。