論文の概要: Safe Subgame Resolving for Extensive Form Correlated Equilibrium
- arxiv url: http://arxiv.org/abs/2212.14317v1
- Date: Thu, 29 Dec 2022 14:20:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 17:24:06.988228
- Title: Safe Subgame Resolving for Extensive Form Correlated Equilibrium
- Title（参考訳）: 広範な形態相関平衡に対する安全なサブゲーム解法
- Authors: Chun Kai Ling, Fei Fang
- Abstract要約: 相関平衡(Correlated Equilibrium)は、ナッシュ平衡(NE)よりも一般的な解概念であり、社会福祉の改善につながる。
テキストサブゲーム解決は,ゼロサムゲームにおけるNEの発見に極めて成功した手法であり,一般サム EFCE の解法である。
サブゲーム解決は、テキストトン方式で相関計画を洗練させる: ゲーム全体を前もって解決するのではなく、実際のプレイで到達したサブゲームにおける戦略のためにのみ解決する。
- 参考スコア（独自算出の注目度）: 47.155175336085364
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Correlated Equilibrium is a solution concept that is more general than Nash
Equilibrium (NE) and can lead to outcomes with better social welfare. However,
its natural extension to the sequential setting, the \textit{Extensive Form
Correlated Equilibrium} (EFCE), requires a quadratic amount of space to solve,
even in restricted settings without randomness in nature. To alleviate these
concerns, we apply \textit{subgame resolving}, a technique extremely successful
in finding NE in zero-sum games to solving general-sum EFCEs. Subgame resolving
refines a correlation plan in an \textit{online} manner: instead of solving for
the full game upfront, it only solves for strategies in subgames that are
reached in actual play, resulting in significant computational gains. In this
paper, we (i) lay out the foundations to quantify the quality of a refined
strategy, in terms of the \textit{social welfare} and \textit{exploitability}
of correlation plans, (ii) show that EFCEs possess a sufficient amount of
independence between subgames to perform resolving efficiently, and (iii)
provide two algorithms for resolving, one using linear programming and the
other based on regret minimization. Both methods guarantee \textit{safety},
i.e., they will never be counterproductive. Our methods are the first time an
online method has been applied to the correlated, general-sum setting.
- Abstract（参考訳）: 相関平衡(Correlated Equilibrium)は、ナッシュ平衡(NE)よりも一般的な解概念であり、社会福祉の改善につながる。
しかし、シーケンシャルな設定への自然な拡張である「textit{Extensive Form Correlated Equilibrium} (EFCE)」は、自然にランダム性のない制限された設定であっても、解くのに2次空間を必要とする。
これらの問題を緩和するために、ゼロサムゲームにおけるNEの発見に極めて成功したテクニックである \textit{subgame resolving} を適用し、一般サム EFCE を解く。
サブゲーム解決は、ゲーム全体を前もって解決するのではなく、実際のプレイで到達したサブゲームにおける戦略のためにのみ解決し、計算上の大きな利益をもたらす。
本稿では,
(i)相関計画の \textit{social welfare} と \textit{exploitability} という観点から、洗練された戦略の品質を定量化する基礎を整備する。
(二)EFCEが効率よく解決を行うためのサブゲーム間で十分な量の独立性を持っていること、及び
(iii)線形プログラミングによる解法と後悔の最小化に基づく解法という2つのアルゴリズムを提供する。
どちらのメソッドも \textit{safety} を保証する。
本手法は,オンライン手法が相関した汎用設定に適用された初めての方法である。
関連論文リスト
- Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。
特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
論文 参考訳（メタデータ） (2024-11-04T00:34:56Z) - A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints [7.9047096855236125]
不等式制約を伴う非滑らかな複合最適化は、統計学習とデータ科学において重要である。
textbfOBCDは、これらの課題に対処するための、実現可能な小さな計算フットプリント手法である。
我々はtextbfOBCD がブロック$k$定常点に収束することを証明する。
論文 参考訳（メタデータ） (2023-04-07T13:44:59Z) - Offline Learning in Markov Games with General Function Approximation [22.2472618685325]
マルコフゲームにおけるオフラインマルチエージェント強化学習(RL)について検討する。
マルコフゲームにおけるサンプル効率のよいオフライン学習のための最初のフレームワークを提供する。
論文 参考訳（メタデータ） (2023-02-06T05:22:27Z) - Function Approximation for Solving Stackelberg Equilibrium in Large
Perfect Information Games [115.77438739169155]
汎用ゲームにおける状態値関数の一般化であるtextitEnforceable Payoff Frontier (EPF) の学習を提案する。
Stackelbergの設定にFAを適用する最初の方法です。
論文 参考訳（メタデータ） (2022-12-29T19:05:50Z) - HSVI can solve zero-sum Partially Observable Stochastic Games [7.293053431456775]
2-player 0-sum不完全なゲームを解くための最先端の手法は、線形プログラミングや動的後悔の最小化に依存している。
本稿では,線形プログラミングや反復的手法に依存した手法を補完する,有望なアプローチの新たなファミリーを提案する。
論文 参考訳（メタデータ） (2022-10-26T11:41:57Z) - Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
ワイドフォームゲームにおいて,様々な種類の最適平衡を求める問題について検討する。
これら3つの概念のすべてに最適な平衡を計算するための新しいアルゴリズムを導入する。
論文 参考訳（メタデータ） (2022-03-14T15:21:18Z) - Model-Free Online Learning in Unknown Sequential Decision Making
Problems and Games [114.90723492840499]
大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。
私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。
エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
論文 参考訳（メタデータ） (2021-03-08T04:03:24Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。