論文の概要: 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つの自然リラクゼーションにおいて,リグレット学習が不可能であることが示された。
関連論文リスト
- Neural Operators Can Play Dynamic Stackelberg Games [9.058593115274336]
ダイナミック・スタックバーグゲーム(Dynamic Stackelberg game)は、リーダーが最初に行動する2人プレイのゲームで、フォロワーはリーダーの戦略に対する反応戦略を選択する。
本稿では,textitfollowerのベストレスポンス演算子を,textitattentionに基づくニューラル演算子によって概ね実装できることを示し,この問題に対処する。
追従者が最適応答演算子を使用するスタックルバーグゲームの価値は、元のスタックルバーグゲームの価値を近似することを示す。
論文 参考訳（メタデータ） (2024-11-14T18:12:06Z) - Decentralized Online Learning in General-Sum Stackelberg Games [2.8659922790025463]
プレイヤーが分散的かつ戦略的に行動する一般のStackelbergゲームにおいて,オンライン学習問題を研究する。
我々は、フォロワーにとって、リーダーの行動にミオプティカルに最も反応することが、限られた情報設定にとって最良の戦略であることを示す。
後者の設定では、フォロワーに対する新たな操作戦略を設計し、最良の応答戦略に対して本質的な優位性を示す。
論文 参考訳（メタデータ） (2024-05-06T04:35:01Z) - When Should a Leader Act Suboptimally? The Role of Inferability in Repeated Stackelberg Games [28.856644679990357]
我々は、リーダーとフォロワーが繰り返し対話する観察結果を用いて、Stackelbergゲームを用いて、推論可能性の問題をモデル化する。
様々なゲーム設定において、不確実性ギャップは、リーダーの戦略の相互作用数とセマンティレベルの関数によって上限づけられていることが示される。
リーダーの準最適戦略が大きな不確実性ギャップに悩まされるような一連のゲームを特定する。
論文 参考訳（メタデータ） (2023-09-30T19:08:05Z) - Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks [83.28949556413717]
グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。
ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。
本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
論文 参考訳（メタデータ） (2022-11-29T05:16:41Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳（メタデータ） (2022-07-25T18:29:16Z) - Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret
Learning in Markov Games [95.10091348976779]
我々はマルコフゲームにおいて、非定常的でおそらく敵対的な相手と遊べる単一のエージェントを制御する分散ポリシー学習について研究する。
我々は、新しいアルゴリズム、アンダーラインデ集中型アンダーラインハイプラインRpolicy munderlineIrror deunderlineScent (DORIS)を提案する。
DORISは、一般的な関数近似の文脈で$sqrtK$-regretを達成する。
論文 参考訳（メタデータ） (2022-06-03T14:18:05Z) - No-Regret Learning in Dynamic Stackelberg Games [31.001205916012307]
Stackelbergゲームでは、リーダーがランダム化された戦略にコミットし、フォロワーがレスポンスでベスト戦略を選択する。
このゲームは、リーダーの報酬や利用可能な戦略に影響を与える基礎となる状態空間を持ち、リーダーとフォロワーの選択した戦略に依存するマルコフ的な方法で進化する。
論文 参考訳（メタデータ） (2022-02-10T01:07:57Z) - Adversarial Training as Stackelberg Game: An Unrolled Optimization
Approach [91.74682538906691]
逆行訓練はディープラーニングモデルの一般化性能を向上させることが示されている。
Stackelbergゲームとして, 対人トレーニングを定式化するStackelberg Adversarial Training (SALT)を提案する。
論文 参考訳（メタデータ） (2021-04-11T00:44:57Z) - Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。
対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。
我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
論文 参考訳（メタデータ） (2020-07-10T09:33:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。