論文の概要: Games played by Exponential Weights Algorithms
- arxiv url: http://arxiv.org/abs/2407.06676v1
- Date: Tue, 9 Jul 2024 08:49:51 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-10 18:46:17.657081
- Title: Games played by Exponential Weights Algorithms
- Title（参考訳）: 指数重みアルゴリズムによるゲーム
- Authors: Maurizio d'Andrea, Fabien Gensbittel, Jérôme Renault,
- Abstract要約: 各プレイヤーは、初期混合動作と固定学習率を特徴とする指数重み付けアルゴリズムを使用する。
厳密なナッシュ均衡が存在するときは常に、次の段階で厳密なナッシュ均衡を行う確率は、ほぼ確実に0または1に収束することを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the last-iterate convergence properties of the exponential weights algorithm with constant learning rates. We consider a repeated interaction in discrete time, where each player uses an exponential weights algorithm characterized by an initial mixed action and a fixed learning rate, so that the mixed action profile $p^t$ played at stage $t$ follows an homogeneous Markov chain. At first, we show that whenever a strict Nash equilibrium exists, the probability to play a strict Nash equilibrium at the next stage converges almost surely to 0 or 1. Secondly, we show that the limit of $p^t$, whenever it exists, belongs to the set of ``Nash Equilibria with Equalizing Payoffs''. Thirdly, we show that in strong coordination games, where the payoff of a player is positive on the diagonal and 0 elsewhere, $p^t$ converges almost surely to one of the strict Nash equilibria. We conclude with open questions.
- Abstract（参考訳）: 本稿では,指数重み付けアルゴリズムの学習速度を一定に抑えた最終項目収束特性について検討する。
そこで各プレイヤーは,初期混合作用と固定学習率を特徴とする指数重み付けアルゴリズムを用いて,ステージ$t$での混合動作プロファイル$p^t$が同質マルコフ連鎖に従うように,離散時間で繰り返し相互作用を考慮する。
まず、厳密なナッシュ均衡が存在するときは常に、次の段階で厳密なナッシュ均衡を行う確率は、ほぼ確実に0または1に収束することを示す。
第二に、$p^t$ の極限が存在すればいつでも ``Nash Equilibria with Equalizing Payoffs''' の集合に属することを示す。
第三に、強調整ゲームにおいて、プレイヤーのペイオフが対角線上で正であり、他の場所で0である場合、$p^t$はほぼ確実に厳しいナッシュ均衡の1つに収束することを示す。
オープンな質問で締めくくります。
関連論文リスト
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。
我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。
我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
論文 参考訳（メタデータ） (2024-06-15T13:26:17Z) - Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property [89.96815099996132]
単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。
我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
論文 参考訳（メタデータ） (2023-12-19T11:34:10Z) - 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) - Smooth Nash Equilibria: Algorithms and Complexity [38.08108978808664]
ナッシュ均衡の概念の根本的な欠点は、その計算的推論性である。
$sigma$-smooth Nash均衡では、プレイヤーは$sigma$-smooth戦略への最良の偏差よりも少なくとも高いユーティリティを達成する必要がある。
弱いと強い$sigma$-smooth Nash平衡は、Nash平衡よりも優れた計算特性を持つことを示す。
論文 参考訳（メタデータ） (2023-09-21T16:22:07Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳（メタデータ） (2023-01-19T11:36:50Z) - $O(T^{-1})$ Convergence of Optimistic-Follow-the-Regularized-Leader in
Two-Player Zero-Sum Markov Games [10.915751393257011]
O(T-1)$-approximate Nash equilibrium in $T$ for two-player zero-sum Markov games with full information。
これにより、Zhang et al (2022)に最近示されている$tildeO(T-5/6)$収束率が向上する。
論文 参考訳（メタデータ） (2022-09-26T05:35:44Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z) - Nash, Conley, and Computation: Impossibility and Incompleteness in Game
Dynamics [28.815822236291392]
ゲーム力学が$epsilon$-Nash平衡に収束できないことを示す。
また、$epsilon$-approximate Nash equilibriaに対してより強い結果を示す。
論文 参考訳（メタデータ） (2022-03-26T18:27:40Z) - Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。
我々はNash equilibria(NE)の解の概念に焦点をあてる。
このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
論文 参考訳（メタデータ） (2021-11-07T21:15:35Z) - Almost Optimal Algorithms for Two-player Markov Games with Linear
Function Approximation [92.99933928528797]
同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。
我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。
我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
論文 参考訳（メタデータ） (2021-02-15T09:09:16Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。