論文の概要: On the Impossibility of Convergence of Mixed Strategies with No Regret Learning

• arxiv url: http://arxiv.org/abs/2012.02125v1
• Date: Thu, 3 Dec 2020 18:02:40 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-23 14:45:59.387626
• Title: On the Impossibility of Convergence of Mixed Strategies with No Regret Learning
• Title（参考訳）: 回帰学習を伴わない混合戦略の収束不可能性について
• Authors: Vidya Muthukumar, Soham Phade, Anant Sahai
• Abstract要約: 最適無後悔学習戦略の一般クラスから得られる混合戦略の収束特性について検討する。 各ステップに設定された情報を相手の実演の実証平均とする戦略のクラスを考察する。
• 参考スコア（独自算出の注目度）: 10.515544361834241
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study convergence properties of the mixed strategies that result from a general class of optimal no regret learning strategies in a repeated game setting where the stage game is any 2 by 2 competitive game (i.e. game for which all the Nash equilibria (NE) of the game are completely mixed). We consider the class of strategies whose information set at each step is the empirical average of the opponent's realized play (and the step number), that we call mean based strategies. We first show that there does not exist any optimal no regret, mean based strategy for player 1 that would result in the convergence of her mixed strategies (in probability) against an opponent that plays his Nash equilibrium mixed strategy at each step. Next, we show that this last iterate divergence necessarily occurs if player 2 uses any adaptive strategy with a minimal randomness property. This property is satisfied, for example, by any fixed sequence of mixed strategies for player 2 that converges to NE. We conjecture that this property holds when both players use optimal no regret learning strategies against each other, leading to the divergence of the mixed strategies with a positive probability. Finally, we show that variants of mean based strategies using recency bias, which have yielded last iterate convergence in deterministic min max optimization, continue to lead to this last iterate divergence. This demonstrates a crucial difference in outcomes between using the opponent's mixtures and realizations to make strategy updates.
• Abstract（参考訳）: ステージゲームが2対2の競争ゲーム(すなわち2対2の競争ゲーム)の繰り返しゲーム設定において、最適無後悔学習戦略の一般的なクラスから生じる混合戦略の収束性について検討する。 ゲームのすべてのナッシュ平衡(ne)が完全に混合されるゲーム。 我々は,各ステップに設定された情報を,平均ベース戦略と呼ぶ対戦相手の達成したプレイ(およびステップ番号)の経験平均とする戦略の類型を考える。 まず,各ステップでナッシュ平衡混合戦略を行う相手に対して,その混合戦略が(確率的に)収束する結果となるプレイヤー1に対して,最適無後悔,平均ベース戦略が存在しないことを示す。 次に、プレイヤー2が最小のランダム性特性を持つ任意の適応戦略を使用する場合、この最後の反復的発散が必然的に起こることを示す。 この性質は例えば、NEに収束するプレイヤー2の混合戦略の任意の固定列によって満たされる。 この性質は、双方のプレイヤーが互いに最適な無後悔学習戦略を使うときに成り立ち、混合戦略が正の確率で分岐することにつながると推測する。 最後に,決定論的min max最適化における最後の反復収束を導いた,連続バイアスを用いた平均ベース戦略の変種が,この反復的分岐に繋がることを示す。 これは、相手のミキシングと、戦略を更新するために実現することの間の結果に重大な違いを示す。

関連論文リスト

• Paths to Equilibrium in Games [6.812247730094933]
  我々は、強化学習におけるポリシー更新に触発されたペアワイズ制約を満たす戦略の列について研究する。 我々の分析は、戦略的な更新を劣化させる報酬が、満足のいく道に沿って均衡に進むための鍵である、という直感的な洞察を明らかにした。
  論文  参考訳（メタデータ） (2024-03-26T19:58:39Z)
• All by Myself: Learning Individualized Competitive Behaviour with a Contrastive Reinforcement Learning optimization [57.615269148301515]
  競争ゲームのシナリオでは、エージェントのセットは、彼らの目標を最大化し、敵の目標を同時に最小化する決定を学習する必要があります。 本稿では,競争ゲームの表現を学習し,特定の相手の戦略をどうマップするか,それらを破壊するかを学習する3つのニューラルネットワーク層からなる新しいモデルを提案する。 我々の実験は、オフライン、オンライン、競争特化モデル、特に同じ対戦相手と複数回対戦した場合に、我々のモデルがより良いパフォーマンスを達成することを示した。
  論文  参考訳（メタデータ） (2023-10-02T08:11:07Z)
• ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
  連続的なアクションセットを持つゲームの近似的ナッシュ均衡を求める問題について検討する。 本稿では,戦略プロファイルに対するエクスプロイラビリティの近似を最小化する2つの新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-01-20T23:55:30Z)
• Opponent Modeling in Multiplayer Imperfect-Information Games [1.024113475677323]
  マルチプレイヤー不完全情報ゲームにおける対戦相手モデルへのアプローチを提案する。 我々は,3人プレイヤのクーンポーカーにおいて,種々の実敵と正確なナッシュ均衡戦略に対する実験を行う。 我々のアルゴリズムは、正確なナッシュ均衡戦略を含む全てのエージェントを著しく上回る。
  論文  参考訳（メタデータ） (2022-12-12T16:48:53Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。 ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。 本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
  論文  参考訳（メタデータ） (2022-11-29T05:16:41Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。 我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。 提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
  論文  参考訳（メタデータ） (2022-07-25T18:29:16Z)
• Mixed Strategies for Security Games with General Defending Requirements [37.02840909260615]
  Stackelbergのセキュリティゲームはディフェンダーとアタッカーの間で行われ、ディフェンダーは複数のターゲットに限られたリソースを割り当てる必要がある。 そこで本研究では,ごく少数の戦略のみを用いる混合戦略を計算し,効率的な近似パチングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-04-26T08:56:39Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。 対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。 我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
  論文  参考訳（メタデータ） (2020-07-10T09:33:05Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  ゲームプレイを通じて,ゲームの記述を明示せず,託宣のみにアクセス可能な,重要で一般的なゲーム解決環境について検討する。 限られたデュレーション学習フェーズにおいて、アルゴリズムは両方のプレイヤーのアクションを制御し、ゲームを学習し、それをうまくプレイする方法を学習する。 私たちのモチベーションは、クエリされた戦略プロファイルの支払いを評価するのにコストがかかる状況において、利用可能性の低い戦略を迅速に学習することにあります。
  論文  参考訳（メタデータ） (2020-02-24T20:30:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。