論文の概要: Grouped Satisficing Paths in Pure Strategy Games: a Topological Perspective

• arxiv url: http://arxiv.org/abs/2509.23157v1
• Date: Sat, 27 Sep 2025 07:07:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-30 22:32:19.074721
• Title: Grouped Satisficing Paths in Pure Strategy Games: a Topological Perspective
• Title（参考訳）: 純粋戦略ゲームにおけるグループ満足パス : トポロジカルな視点
• Authors: Yanqing Fu, Chao Huang, Chenrun Wang, Zhuping Wang,
• Abstract要約: MARLアルゴリズムで広く採用されている原則は「ウィンステイ、負けシフト」であり、エージェントが最高の応答を達成すれば現在の戦略を維持することを指示する。 本稿では,そのような特性に対して十分な条件を確立し,任意の有限状態マルコフゲーム,および任意の$N$-playerゲームが有限長充足パスの存在を保証することを示す。
• 参考スコア（独自算出の注目度）: 15.76917401735207
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In game theory and multi-agent reinforcement learning (MARL), each agent selects a strategy, interacts with the environment and other agents, and subsequently updates its strategy based on the received payoff. This process generates a sequence of joint strategies $(s^t)_{t \geq 0}$, where $s^t$ represents the strategy profile of all agents at time step $t$. A widely adopted principle in MARL algorithms is "win-stay, lose-shift", which dictates that an agent retains its current strategy if it achieves the best response. This principle exhibits a fixed-point property when the joint strategy has become an equilibrium. The sequence of joint strategies under this principle is referred to as a satisficing path, a concept first introduced in [40] and explored in the context of $N$-player games in [39]. A fundamental question arises regarding this principle: Under what conditions does every initial joint strategy $s$ admit a finite-length satisficing path $(s^t)_{0 \leq t \leq T}$ where $s^0=s$ and $s^T$ is an equilibrium? This paper establishes a sufficient condition for such a property, and demonstrates that any finite-state Markov game, as well as any $N$-player game, guarantees the existence of a finite-length satisficing path from an arbitrary initial strategy to some equilibrium. These results provide a stronger theoretical foundation for the design of MARL algorithms.
• Abstract（参考訳）: ゲーム理論とマルチエージェント強化学習(MARL)では、各エージェントが戦略を選択し、環境や他のエージェントと相互作用し、その後、受信した支払いに基づいて戦略を更新する。 このプロセスは一連のジョイント戦略$(s^t)_{t \geq 0}$を生成し、ここでは、s^t$は時間ステップ$t$における全てのエージェントの戦略プロファイルを表す。 MARLアルゴリズムで広く採用されている原則は「ウィンステイ、負けシフト」であり、エージェントが最高の応答を達成すれば現在の戦略を維持することを指示する。 この原理は、ジョイント戦略が平衡になったときの固定点特性を示す。 この原理の下でのジョイント戦略のシーケンスは、[40] で最初に導入され、[39] で$N$-player ゲームという文脈で探求された概念である、満足なパスと呼ばれる。 すべての初期合同戦略$s$は有限長の充足パス$(s^t)_{0 \leq t \leq T}$で、$s^0=s$と$s^T$は平衡か? 本稿は、そのような性質に対して十分な条件を確立し、任意の有限状態マルコフゲーム、および任意の$N$-playerゲームが、任意の初期戦略からある平衡への有限長の満足パスの存在を保証することを示す。 これらの結果は、MARLアルゴリズムの設計に強力な理論的基盤を提供する。

関連論文リスト

• Paths to Equilibrium in Games [6.812247730094933]
  我々は、強化学習におけるポリシー更新に触発されたペアワイズ制約を満たす戦略の列について研究する。 我々の分析は、戦略的な更新を劣化させる報酬が、満足のいく道に沿って均衡に進むための鍵である、という直感的な洞察を明らかにした。
  論文  参考訳（メタデータ） (2024-03-26T19:58:39Z)
• Hierarchical Strategies for Cooperative Multi-Agent Reinforcement Learning [0.0]
  本稿では,新たな情報理論目標と軌道予測モデルを組み合わせた2段階階層アーキテクチャを提案する。 提案手法は,超硬度SCIIシナリオを解く最初のMARLアルゴリズムとして,我々の知る限り,この技術の新たな状態を確立するものであることを示す。 メソッドのビデオと簡単な概要は、https://sites.google.com/view/hier-strats-marl/home.comで公開されている。
  論文  参考訳（メタデータ） (2022-12-14T18:27:58Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。 我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。 先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
  論文  参考訳（メタデータ） (2022-06-17T12:58:58Z)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。 このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
  論文  参考訳（メタデータ） (2022-06-06T14:23:13Z)
• Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus [48.34563955829649]
  本稿では,共同戦略の信頼区間を構築する戦略的な集中原理を提案する。 2人のプレイヤーによるゼロサムマルコフゲームの場合、戦略的なボーナスの凸性を利用して効率的なアルゴリズムを提案する。 すべてのアルゴリズムは、指定済みの戦略クラスである$Pi$を入力として取り、最良の戦略に近い戦略を$Pi$で出力することができる。
  論文  参考訳（メタデータ） (2022-06-01T00:18:15Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  ゲームプレイを通じて,ゲームの記述を明示せず,託宣のみにアクセス可能な,重要で一般的なゲーム解決環境について検討する。 限られたデュレーション学習フェーズにおいて、アルゴリズムは両方のプレイヤーのアクションを制御し、ゲームを学習し、それをうまくプレイする方法を学習する。 私たちのモチベーションは、クエリされた戦略プロファイルの支払いを評価するのにコストがかかる状況において、利用可能性の低い戦略を迅速に学習することにあります。
  論文  参考訳（メタデータ） (2020-02-24T20:30:38Z)

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

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