論文の概要: Approximate State Abstraction for Markov Games
- arxiv url: http://arxiv.org/abs/2412.15877v1
- Date: Fri, 20 Dec 2024 13:28:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-23 16:20:03.598782
- Title: Approximate State Abstraction for Markov Games
- Title（参考訳）: マルコフゲームのための近似状態抽象化
- Authors: Hiroki Ishibashi, Kenshi Abe, Atsushi Iwasaki,
- Abstract要約: 本稿では,2プレーヤゼロサムマルコフゲーム(TZMG)の状態抽象化を提案する。
2人のプレイヤーの報酬は環境とその行動を表す状態によって決定され、マルコフの決定プロセスに従って状態遷移が行われる。
TZMGでは、状態の数が増加するにつれて、計算平衡はより困難になる。
- 参考スコア（独自算出の注目度）: 9.23067612743827
- License:
- Abstract: This paper introduces state abstraction for two-player zero-sum Markov games (TZMGs), where the payoffs for the two players are determined by the state representing the environment and their respective actions, with state transitions following Markov decision processes. For example, in games like soccer, the value of actions changes according to the state of play, and thus such games should be described as Markov games. In TZMGs, as the number of states increases, computing equilibria becomes more difficult. Therefore, we consider state abstraction, which reduces the number of states by treating multiple different states as a single state. There is a substantial body of research on finding optimal policies for Markov decision processes using state abstraction. However, in the multi-player setting, the game with state abstraction may yield different equilibrium solutions from those of the ground game. To evaluate the equilibrium solutions of the game with state abstraction, we derived bounds on the duality gap, which represents the distance from the equilibrium solutions of the ground game. Finally, we demonstrate our state abstraction with Markov Soccer, compute equilibrium policies, and examine the results.
- Abstract（参考訳）: 本稿では,2人プレイヤゼロサムマルコフゲーム (TZMG) における状態抽象化について述べる。
例えば、サッカーのようなゲームでは、アクションの価値はプレーの状態に応じて変化するため、このようなゲームはマルコフゲームとして記述されるべきである。
TZMGでは、状態の数が増加するにつれて、計算平衡はより困難になる。
したがって、複数の異なる状態を単一の状態として扱うことにより、状態の数を削減できる状態抽象化を考える。
状態抽象化を用いたマルコフ決定プロセスの最適ポリシーの発見には、かなりの研究機関がある。
しかし、マルチプレイヤー設定では、状態抽象化を持つゲームは、グラウンドゲームと異なる平衡解をもたらす可能性がある。
状態抽象化によるゲームの平衡解を評価するために,ゲーム間の平衡解からの距離を表す双対性ギャップの境界を導出した。
最後に,マルコフサッカーによる状態抽象化,平衡ポリシの計算,結果の検証を行った。
関連論文リスト
- Strategy Game-Playing with Size-Constrained State Abstraction [44.99833362998488]
戦略ゲームは人工知能(AI)にとって難しい問題である
主な課題の1つは、ゲームコンポーネントの多様さによる巨大な検索スペースである。
状態抽象化は、検索ベースのゲームAIに適用され、大幅なパフォーマンス向上をもたらした。
論文 参考訳（メタデータ） (2024-08-12T14:50:18Z) - Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property [89.96815099996132]
単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。
我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
論文 参考訳（メタデータ） (2023-12-19T11:34:10Z) - Soft-Bellman Equilibrium in Affine Markov Games: Forward Solutions and
Inverse Learning [37.176741793213694]
我々は、アフィン・マルコフゲームと呼ばれるマルコフゲームのクラスを定式化し、アフィン報酬関数はプレイヤーの行動と一致する。
我々は,各プレイヤーが有理的に有理であり,ソフト・ベルマンポリシーを選択するような,新しい解の概念,ソフト・ベルマン均衡を導入する。
そこで我々は,プロジェクテッド・グラディエント・アルゴリズムを用いて,観測された状態-行動軌跡からプレイヤーの報酬パラメータを推定する逆ゲーム問題を解く。
論文 参考訳（メタデータ） (2023-03-31T22:50:47Z) - Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。
我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。
我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文 参考訳（メタデータ） (2023-03-22T03:28:12Z) - Decidability of fully quantum nonlocal games with noisy maximally
entangled states [5.076419064097734]
本稿では、雑音の多い最大絡み合った状態を持つ完全量子非局所ゲームの決定可能性について考察する。
我々は、プレイヤーが量子値に任意に近い確率で完全量子非局所ゲームに勝つために、雑音の多い最大絡み合った状態のコピーに計算可能な上限が存在することを証明した。
論文 参考訳（メタデータ） (2022-11-19T08:11:02Z) - Elastic Monte Carlo Tree Search with State Abstraction for Strategy Game
Playing [58.720142291102135]
戦略ビデオゲームは、複雑なゲーム要素によって引き起こされる検索スペースでAIエージェントに挑戦する。
状態抽象化は、状態空間の複雑さを低減する一般的なテクニックである。
我々は,状態抽象化を用いてストラテジーゲームをプレイするアルゴリズムであるElastic MCTSを提案する。
論文 参考訳（メタデータ） (2022-05-30T14:18:45Z) - SOCCER: An Information-Sparse Discourse State Tracking Collection in the
Sports Commentary Domain [7.119677737397071]
自然言語理解の追求において、物語全体の状態変化を追跡することに対する長年の関心が高まってきた。
本稿では,これらの特性を示す,シンプルで完全に観測可能なシステムに転換することを提案する。
そこで本研究では,異なるタイムスタンプでのゲーム解説文を前提として,ゲーム内イベントの発生を認識させるタスクの定式化を提案する。
論文 参考訳（メタデータ） (2021-06-03T16:21:13Z) - Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。
本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
論文 参考訳（メタデータ） (2021-02-23T05:11:07Z) - Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
私たちは、修正された振る舞いで達成できたことに対して、強いパフォーマンスを後見で保証するアルゴリズムを検討します。
我々は,学習の隠れた枠組みを,逐次的な意思決定の場で開発し,提唱する。
本稿では,それぞれの平衡の強さと弱さを文献に示す例を示す。
論文 参考訳（メタデータ） (2020-12-10T18:30:21Z) - Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
本稿では,ゼロサムにおける乗算重み更新 (MWU) と最適乗算重み更新 (OMWU) のボリューム解析と協調ゲームについて述べる。
我々は、OMWUが、その既知の収束挙動の代替的な理解を提供するために、ボリュームを契約していることを示します。
我々はまた、コーディネートゲームを調べる際に役割が逆になるという意味で、自由ランチ型の定理も証明する: OMWU は指数関数的に高速に体積を拡大するが、MWU は契約する。
論文 参考訳（メタデータ） (2020-05-28T13:47:09Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。