論文の概要: Regret Minimization in Stackelberg Games with Side Information
- arxiv url: http://arxiv.org/abs/2402.08576v2
- Date: Thu, 22 Feb 2024 19:20:51 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-26 17:06:59.073160
- Title: Regret Minimization in Stackelberg Games with Side Information
- Title(参考訳): サイド情報付きスタックルバーグゲームにおけるレグレト最小化
- Authors: Keegan Harris, Zhiwei Steven Wu, Maria-Florina Balcan
- Abstract要約: Stackelbergゲーム (Stackelberg game) は、リーダーが(混合)戦略にコミットし、フォロワーがベスト対応する2人プレイのゲームである。
本研究は, リーダが全敵的設定で優れたパフォーマンス(後悔によって測られる)を達成することは不可能であることを示す。
- 参考スコア(独自算出の注目度): 50.270531339600495
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In its most basic form, a Stackelberg game is a two-player game in which a
leader commits to a (mixed) strategy, and a follower best-responds. Stackelberg
games are perhaps one of the biggest success stories of algorithmic game theory
over the last decade, as algorithms for playing in Stackelberg games have been
deployed in many real-world domains including airport security, anti-poaching
efforts, and cyber-crime prevention. However, these algorithms often fail to
take into consideration the additional information available to each player
(e.g. traffic patterns, weather conditions, network congestion), a salient
feature of reality which may significantly affect both players' optimal
strategies. We formalize such settings as Stackelberg games with side
information, in which both players observe an external context before playing.
The leader then commits to a (possibly context-dependent) strategy, and the
follower best-responds to both the leader's strategy and the context. We focus
on the online setting in which a sequence of followers arrive over time, and
the context may change from round-to-round. In sharp contrast to the
non-contextual version, we show that it is impossible for the leader to achieve
good performance (measured by regret) in the full adversarial setting (i.e.,
when both the context and the follower are chosen by an adversary). However, it
turns out that a little bit of randomness goes a long way. Motivated by our
impossibility result, we show that no-regret learning is possible in two
natural relaxations: the setting in which the sequence of followers is chosen
stochastically and the sequence of contexts is adversarial, and the setting in
which the sequence of contexts is stochastic and the sequence of followers is
chosen by an adversary.
- Abstract(参考訳): 最も基本的な形式では、スタックルバーグゲームは、リーダーが(混合された)戦略にコミットし、追随者が最善を尽くす2人プレイヤゲームである。
Stackelbergゲームは、おそらく過去10年間でアルゴリズムゲーム理論の最大の成功例の1つであり、Stackelbergゲームでプレイするアルゴリズムは、空港のセキュリティ、反ポーチ活動、サイバー犯罪防止など、多くの現実世界の領域に展開されている。
しかしながら、これらのアルゴリズムは、それぞれのプレイヤーに利用可能な追加情報(例えば、交通パターン、気象条件、ネットワークの混雑など)を考慮するのに失敗することが多い。
両プレーヤーがプレー前に外部コンテキストを観察する,サイド情報付きStackelbergゲームのような設定を形式化する。
リーダーは(おそらくコンテキスト依存の)戦略にコミットし、従者はリーダーの戦略とコンテキストの両方に最善の責任を負う。
我々は、時間とともにフォロワーのシーケンスが到着するオンライン設定に注目し、状況が丸ごと変化する可能性がある。
文脈的でないバージョンとは対照的に、リーダーが完全な敵設定(つまり、文脈と従者の両方が敵によって選択された場合)において優れたパフォーマンス(後悔によって測定される)を達成することは不可能であることを示している。
しかし、多少のランダム性は長い道のりを歩むことが判明した。
その結果,2つの自然リラクゼーションでは,従者のシーケンスが確率的に選択され,文脈のシーケンスが逆行する設定と,文脈のシーケンスが確率的に選択され,従者のシーケンスが敵によって選択される設定の2つの自然リラクゼーションにおいて,リグレット学習が不可能であることが示された。
関連論文リスト
- 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) - Adversarial Training as Stackelberg Game: An Unrolled Optimization
Approach [91.74682538906691]
逆行訓練はディープラーニングモデルの一般化性能を向上させることが示されている。
Stackelbergゲームとして, 対人トレーニングを定式化するStackelberg Adversarial Training (SALT)を提案する。
論文 参考訳(メタデータ) (2021-04-11T00:44:57Z) - Safe Search for Stackelberg Equilibria in Extensive-Form Games [24.557177222572786]
スタックルバーグ均衡(Stackelberg equilibrium)は、2人プレイヤゲームにおいて、リーダーが従者に対するコミットメント権を持つ解概念である。
一般ゲームにおけるスタックルバーグ平衡の計算に探索を適用するための理論的に健全で実験的に有効な方法を提案する。
論文 参考訳(メタデータ) (2021-02-02T22:01:19Z) - Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies
in Extensive-Form Zero-Sum Games [123.76716667704625]
我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。
この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。
各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
論文 参考訳(メタデータ) (2020-09-21T17:51:57Z) - Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。
対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。
我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
論文 参考訳(メタデータ) (2020-07-10T09:33:05Z) - Optimally Deceiving a Learning Leader in Stackelberg Games [123.14187606686006]
MLコミュニティの最近の結果は、リーダーがStackelbergゲームでコミットする最適な戦略を計算するために使用される学習アルゴリズムが、フォロワーによる操作に影響を受けやすいことを明らかにしている。
本稿は、リーダーとフォロワー間の学習相互作用に関する様々なシナリオにおいて、フォロワーが(最適に近い)ペイオフを計算することは、常に可能であることを示す。
論文 参考訳(メタデータ) (2020-06-11T16:18:21Z) - Model-free Reinforcement Learning for Stochastic Stackelberg Security
Games [7.470839530834359]
リーダーとフォロワーの2人のプレイヤーによる連続的なStackelbergゲームについて検討する。
フォロワーはシステムの状態にアクセスでき、リーダーはアクセスしない。
本稿では,MDPのモデルをシミュレートして,スタックルバーグ均衡政策を学習する予測サーサに基づくRLアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-05-24T22:34:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。