論文の概要: Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and
Value
- arxiv url: http://arxiv.org/abs/2311.00582v1
- Date: Wed, 1 Nov 2023 15:27:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-02 13:03:34.141255
- Title: Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and
Value
- Title(参考訳): ナッシュ平衡と値を達成するためにマルコフゲームを最小限に修正する
- Authors: Young Wu, Jeremy McMahan, Yiding Chen, Yudong Chen, Xiaojin Zhu,
Qiaomin Xie
- Abstract要約: 本稿では,ゲームデザイナや悪意ある相手がゼロサムマルコフゲームの報酬関数を変更するゲーム修正問題について検討する。
我々は、あるゲームのユニークな平衡としてインストールできるポリシープロファイルの集合を特徴づける。
- 参考スコア(独自算出の注目度): 16.606082870373704
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the game modification problem, where a benevolent game designer or a
malevolent adversary modifies the reward function of a zero-sum Markov game so
that a target deterministic or stochastic policy profile becomes the unique
Markov perfect Nash equilibrium and has a value within a target range, in a way
that minimizes the modification cost. We characterize the set of policy
profiles that can be installed as the unique equilibrium of some game, and
establish sufficient and necessary conditions for successful installation. We
propose an efficient algorithm, which solves a convex optimization problem with
linear constraints and then performs random perturbation, to obtain a
modification plan with a near-optimal cost.
- Abstract(参考訳): 本研究は,ゼロサムマルコフゲームの報奨機能を好意的ゲームデザイナーまたは好意的敵が修正することにより,目標決定論的又は確率的ポリシープロファイルがユニークなマルコフ完全ナッシュ均衡となり,目標範囲内での値を有するように修正コストを最小化するゲーム修正問題について検討する。
我々は,あるゲームのユニークな均衡としてインストール可能な一連のポリシープロファイルを特徴付け,インストール成功に必要な十分かつ必要な条件を確立する。
線形制約で凸最適化問題を解き、次にランダムな摂動を行い、ほぼ最適コストで修正計画を得る効率的なアルゴリズムを提案する。
関連論文リスト
- Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property [89.96815099996132]
単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。
我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
論文 参考訳(メタデータ) (2023-12-19T11:34:10Z) - Model-Free Algorithm with Improved Sample Efficiency for Zero-Sum Markov
Games [71.0315408565146]
モデルフリーのステージベースQ-ラーニングアルゴリズムはモデルベースアルゴリズムと同じ$H$依存の最適性を享受できることを示す。
本アルゴリズムは,楽観的値関数と悲観的値関数のペアとして参照値関数を更新するキーとなる新しい設計を特徴とする。
論文 参考訳(メタデータ) (2023-08-17T08:34:58Z) - Provably Efficient Generalized Lagrangian Policy Optimization for Safe
Multi-Agent Reinforcement Learning [105.7510838453122]
制約付きマルコフゲームを用いたオンライン安全なマルチエージェント強化学習について検討する。
我々は,このラグランジアン問題を解くための高信頼強化学習アルゴリズムを開発した。
提案アルゴリズムは,オンラインミラー降下によるミニマックス決定主元変数と,投影勾配ステップによる双対変数を更新する。
論文 参考訳(メタデータ) (2023-05-31T22:09:24Z) - Soft-Bellman Equilibrium in Affine Markov Games: Forward Solutions and
Inverse Learning [37.176741793213694]
我々は、アフィン・マルコフゲームと呼ばれるマルコフゲームのクラスを定式化し、アフィン報酬関数はプレイヤーの行動と一致する。
我々は,各プレイヤーが有理的に有理であり,ソフト・ベルマンポリシーを選択するような,新しい解の概念,ソフト・ベルマン均衡を導入する。
そこで我々は,プロジェクテッド・グラディエント・アルゴリズムを用いて,観測された状態-行動軌跡からプレイヤーの報酬パラメータを推定する逆ゲーム問題を解く。
論文 参考訳(メタデータ) (2023-03-31T22:50:47Z) - Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
ゼロサムマルコフゲームにおいて、2人のプレイヤーが望ましいナッシュ均衡、すなわち仲裁を誘導する報酬を摂動する方法を研究する。
低いレベルでは、与えられた報酬関数の下でのナッシュ均衡の解決が必要であり、それによって全体的な問題をエンドツーエンドで最適化することが難しくなる。
上層階の勾配フィードバックを提供するナッシュ平衡を微分するバックプロパゲーション方式を提案する。
論文 参考訳(メタデータ) (2023-02-20T16:05:04Z) - Offline Learning in Markov Games with General Function Approximation [22.2472618685325]
マルコフゲームにおけるオフラインマルチエージェント強化学習(RL)について検討する。
マルコフゲームにおけるサンプル効率のよいオフライン学習のための最初のフレームワークを提供する。
論文 参考訳(メタデータ) (2023-02-06T05:22:27Z) - Efficiently Computing Nash Equilibria in Adversarial Team Markov Games [19.717850955051837]
我々は,同じプレイヤーが対戦相手と競合するゲームのクラスを紹介する。
この設定により、ゼロサムマルコフゲームの可能性ゲームの統一処理が可能になる。
我々の主な貢献は、対戦チームマルコフゲームにおける固定的な$epsilon$-approximate Nash平衡を計算するための最初のアルゴリズムである。
論文 参考訳(メタデータ) (2022-08-03T16:41:01Z) - Inducing Equilibria via Incentives: Simultaneous Design-and-Play Finds
Global Optima [114.31577038081026]
本稿では,デザイナーとエージェントの問題を同時に1ループで解くための効率的な手法を提案する。
設計者は平衡問題を何度も解決しないが、エージェントに対するインセンティブの全体的な影響を予測できる。
このアルゴリズムは,幅広い種類のゲームに対して,サブ線形速度で大域的最適値に収束することを示す。
論文 参考訳(メタデータ) (2021-10-04T06:53:59Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳(メタデータ) (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。