論文の概要: Safe Search for Stackelberg Equilibria in Extensive-Form Games
- arxiv url: http://arxiv.org/abs/2102.01775v1
- Date: Tue, 2 Feb 2021 22:01:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-04 17:22:36.922834
- Title: Safe Search for Stackelberg Equilibria in Extensive-Form Games
- Title（参考訳）: 拡張型ゲームにおけるStackelberg平衡の安全な探索
- Authors: Chun Kai Ling, Noam Brown
- Abstract要約: スタックルバーグ均衡(Stackelberg equilibrium)は、2人プレイヤゲームにおいて、リーダーが従者に対するコミットメント権を持つ解概念である。
一般ゲームにおけるスタックルバーグ平衡の計算に探索を適用するための理論的に健全で実験的に有効な方法を提案する。
- 参考スコア（独自算出の注目度）: 24.557177222572786
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Stackelberg equilibrium is a solution concept in two-player games where the
leader has commitment rights over the follower. In recent years, it has become
a cornerstone of many security applications, including airport patrolling and
wildlife poaching prevention. Even though many of these settings are sequential
in nature, existing techniques pre-compute the entire solution ahead of time.
In this paper, we present a theoretically sound and empirically effective way
to apply search, which leverages extra online computation to improve a
solution, to the computation of Stackelberg equilibria in general-sum games.
Instead of the leader attempting to solve the full game upfront, an approximate
"blueprint" solution is first computed offline and is then improved online for
the particular subgames encountered in actual play. We prove that our search
technique is guaranteed to perform no worse than the pre-computed blueprint
strategy, and empirically demonstrate that it enables approximately solving
significantly larger games compared to purely offline methods. We also show
that our search operation may be cast as a smaller Stackelberg problem, making
our method complementary to existing algorithms based on strategy generation.
- Abstract（参考訳）: Stackelberg平衡(Stackelberg equilibrium)は、リーダーがフォロワーに対してコミットメント権を持つ2プレイヤーゲームにおけるソリューションコンセプトである。
近年では、空港のパトロールや野生動物の密猟防止など、多くのセキュリティアプリケーションの礎となっています。
これらの設定の多くは本質的にシーケンシャルですが、既存のテクニックは事前にソリューション全体を計算します。
本稿では,一般用ゲームにおける Stackelberg 平衡の計算に,オンライン計算を応用して解を改善する,理論的に健全かつ実証的に有効な探索手法を提案する。
リーダーがゲーム全体を前もって解決しようとする代わりに、近似的な"青写真"ソリューションが最初にオフラインで計算され、実際のプレイで遭遇した特定のサブゲームのためにオンラインで改善される。
提案手法は,事前計算したブループリント戦略に匹敵する性能が保証されていることを実証し,純粋にオフラインの手法に比べて大局的にゲームを解くことが可能であることを実証した。
また,我々の検索操作はより小さなStackelberg問題としてキャストされる可能性を示し,戦略生成に基づく既存のアルゴリズムを補完する手法を提案する。
関連論文リスト
- Who Plays First? Optimizing the Order of Play in Stackelberg Games with Many Robots [4.146913555716228]
Branch and Play (B&P) は、社会的に最適な遊びの順序とスタックルバーグ均衡に収束する効率的かつ正確なアルゴリズムである。
本稿では,B&Pによる航空交通管制,群れ形成,輸送車両の配車における実用性を実証する。
論文 参考訳（メタデータ） (2024-02-14T15:34:38Z) - Game Solving with Online Fine-Tuning [17.614045403579244]
本稿では,探索中のオンラインファインチューニングの適用について検討し,ゲーム問題解決のための最適設計計算を学習するための2つの方法を提案する。
実験の結果,オンラインファインチューニングを用いることで,ベースラインに比べて23.54%の時間しか利用できない7x7 Killall-Goの課題が解決できることがわかった。
論文 参考訳（メタデータ） (2023-11-13T09:09:52Z) - Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。
我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。
我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文 参考訳（メタデータ） (2023-03-22T03:28:12Z) - ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
連続的なアクションセットを持つゲームの近似的ナッシュ均衡を求める問題について検討する。
本稿では,戦略プロファイルに対するエクスプロイラビリティの近似を最小化する2つの新しい手法を提案する。
論文 参考訳（メタデータ） (2023-01-20T23:55:30Z) - Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks [83.28949556413717]
グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。
ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。
本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
論文 参考訳（メタデータ） (2022-11-29T05:16:41Z) - Robust No-Regret Learning in Min-Max Stackelberg Games [1.6500749121196987]
本研究は,Min-maxゲームにおける非regret学習の挙動について考察する。
非回帰力学がスタックルバーグ平衡に収束することを示す。
OMD のダイナミクスは,オンライン min-max Stackelberg ゲームの大規模なクラスでは堅牢であることを示す。
論文 参考訳（メタデータ） (2022-03-26T18:12:40Z) - No-Regret Learning in Dynamic Stackelberg Games [31.001205916012307]
Stackelbergゲームでは、リーダーがランダム化された戦略にコミットし、フォロワーがレスポンスでベスト戦略を選択する。
このゲームは、リーダーの報酬や利用可能な戦略に影響を与える基礎となる状態空間を持ち、リーダーとフォロワーの選択した戦略に依存するマルコフ的な方法で進化する。
論文 参考訳（メタデータ） (2022-02-10T01:07:57Z) - Can Reinforcement Learning Find Stackelberg-Nash Equilibria in
General-Sum Markov Games with Myopic Followers? [156.5760265539888]
我々は,マルチプレイヤーのジェネラルサムマルコフゲームについて,リーダーに指名されたプレイヤーとフォロワーに指名されたプレイヤーの1人を用いて研究した。
そのようなゲームに対して、我々のゴールは、政策対 $(pi*, nu*)$ であるスタックルバーグ・ナッシュ均衡 (SNE) を見つけることである。
オンラインとオフラインの両方でSNEを解くために,サンプル効率強化学習(RL)アルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-12-27T05:41:14Z) - Convex-Concave Min-Max Stackelberg Games [0.0]
コンベックス・コンケーブ min-max Stackelberg ゲームのクラスを解く2つの一階法を導入する。
私たちは我々の方法が時間内に収束していることを示します。
フィッシャー市場での競争均衡の計算は、min-max Stackelbergゲームも含む。
論文 参考訳（メタデータ） (2021-10-05T06:09:45Z) - Provable Fictitious Play for General Mean-Field Games [111.44976345867005]
静止平均場ゲームのための強化学習アルゴリズムを提案する。
目標は、ナッシュ均衡を構成する平均場状態と定常政策のペアを学ぶことである。
論文 参考訳（メタデータ） (2020-10-08T18:46:48Z) - Optimally Deceiving a Learning Leader in Stackelberg Games [123.14187606686006]
MLコミュニティの最近の結果は、リーダーがStackelbergゲームでコミットする最適な戦略を計算するために使用される学習アルゴリズムが、フォロワーによる操作に影響を受けやすいことを明らかにしている。
本稿は、リーダーとフォロワー間の学習相互作用に関する様々なシナリオにおいて、フォロワーが(最適に近い)ペイオフを計算することは、常に可能であることを示す。
論文 参考訳（メタデータ） (2020-06-11T16:18:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。