論文の概要: Playing Markov Games Without Observing Payoffs

• arxiv url: http://arxiv.org/abs/2509.00179v2
• Date: Sun, 07 Sep 2025 07:52:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-09 14:07:03.341556
• Title: Playing Markov Games Without Observing Payoffs
• Title（参考訳）: マルコフゲームは見つからずにプレイする
• Authors: Daniel Ablin, Alon Cohen,
• Abstract要約: 本稿では,ゼロサム対称マルコフゲームの新しいクラスを紹介し,形式化する。 報酬を観察しなくても、移行ダイナミクスを知っているプレイヤーが対戦相手と競争できることを示す。 我々の研究は、厳しい情報不利の下で堅牢な学習が可能となるゲームのクラスを広げる。
• 参考スコア（独自算出の注目度）: 5.120675183010349
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimization under uncertainty is a fundamental problem in learning and decision-making, particularly in multi-agent systems. Previously, Feldman, Kalai, and Tennenholtz [2010] demonstrated the ability to efficiently compete in repeated symmetric two-player matrix games without observing payoffs, as long as the opponents actions are observed. In this paper, we introduce and formalize a new class of zero-sum symmetric Markov games, which extends the notion of symmetry from matrix games to the Markovian setting. We show that even without observing payoffs, a player who knows the transition dynamics and observes only the opponents sequence of actions can still compete against an adversary who may have complete knowledge of the game. We formalize three distinct notions of symmetry in this setting and show that, under these conditions, the learning problem can be reduced to an instance of online learning, enabling the player to asymptotically match the return of the opponent despite lacking payoff observations. Our algorithms apply to both matrix and Markov games, and run in polynomial time with respect to the size of the game and the number of episodes. Our work broadens the class of games in which robust learning is possible under severe informational disadvantage and deepens the connection between online learning and adversarial game theory.
• Abstract（参考訳）: 不確実性の下での最適化は、学習と意思決定、特にマルチエージェントシステムにおける根本的な問題である。 従来,Feldman,Kalai,Tennenholtz [2010] は,対戦相手の動作が観察される限り,ペイオフを観察することなく,繰り返し対称な2人プレイヤ行列ゲームで効率的に競争する能力を示した。 本稿では,行列ゲームからマルコフ設定への対称性の概念を拡張したゼロサム対称マルコフゲームの導入と形式化を行う。 この結果から,移動力学を知っており,相手の行動列のみを観察するプレイヤーは,相変わらず,ゲームに詳しい相手と競うことができることがわかった。 これらの条件下では、学習問題をオンライン学習の事例に還元することができ、プレイヤーはペイオフの観察を欠いた相手の復帰を漸近的に一致させることができることを示す。 我々のアルゴリズムは行列ゲームとマルコフゲームの両方に適用され、ゲームのサイズとエピソード数に関して多項式時間で実行される。 本研究は,高度情報不利の下で頑健な学習が可能となるゲームの種類を広げ,オンライン学習と対戦型ゲーム理論との関係を深める。

関連論文リスト

• Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games [21.168085154982712]
  マルチプレイヤーゲームにおける平衡は、一意でも爆発的でもない。 本稿では,平等な共有という自然な目的に焦点をあてることで,これらの課題に対処するための最初の一歩を踏み出す。 我々は、様々な設定でほぼ同じシェアを確実に得る、非回帰学習にインスパイアされた、一連の効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-06-06T15:59: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)
• Is Learning in Games Good for the Learners? [14.781100349601587]
  2人のエージェント間の繰り返しのゲームプレイにおいて、報酬と後悔の間のトレードオフを考慮する。 このような平衡は、任意の相手に対する後悔の保証を維持するアルゴリズムのペアによって到達可能であることを示す。 また,ゲーム開始時において,未学習エージェントとの繰り返しプレイを通じて報酬-最適戦略を学習する問題についても検討する。
  論文  参考訳（メタデータ） (2023-05-31T02:10:27Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Online Learning in Unknown Markov Games [55.07327246187741]
  未知のマルコフゲームでオンライン学習を学ぶ。 後方視における最良の反応に対するサブ線形後悔の達成は統計的に困難であることを示す。 サブ線形$tildemathcalO(K2/3)$ regretを$K$のエピソード後に達成するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-28T14:52:15Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。 対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。 我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
  論文  参考訳（メタデータ） (2020-07-10T09:33:05Z)
• Matrix games with bandit feedback [33.637621576707076]
  本研究では,古典的ゼロサム行列ゲームのバージョンを,未知のペイオフ行列と帯域幅フィードバックを用いて検討する。 我々は、トンプソンがこの設定で破滅的に失敗し、既存のアルゴリズムと経験的な比較を行うことを示した。
  論文  参考訳（メタデータ） (2020-06-09T09:36:21Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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