論文の概要: Regret Minimization in Stackelberg Games with Side Information

• arxiv url: http://arxiv.org/abs/2402.08576v3
• Date: Thu, 23 May 2024 14:39:31 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-25 06:50:03.322627
• Title: Regret Minimization in Stackelberg Games with Side Information
• Title（参考訳）: サイド情報付きスタックルバーグゲームにおけるレグレト最小化
• Authors: Keegan Harris, Zhiwei Steven Wu, Maria-Florina Balcan,
• Abstract要約: 両プレイヤーがプレー前に外部コンテキストを観察するサイド情報付きStackelbergゲームを定式化する。 リーダーは(コンテキストに依存した)戦略をコミットし、フォロワーはリーダーの戦略とコンテキストの両方に最もよく対応します。 非コンテクストバージョンとは対照的に、完全な対向的な設定では、リーダが優れたパフォーマンス(後悔によって測定される)を達成することは不可能であることを示す。
• 参考スコア（独自算出の注目度）: 44.72865997906019
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Algorithms for playing in Stackelberg games have been deployed in 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 commits to a (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. 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（参考訳）: Stackelbergのゲームでプレイするためのアルゴリズムは、空港のセキュリティ、密猟防止、サイバー犯罪防止など、現実世界のドメインに展開されている。 しかし、これらのアルゴリズムは、それぞれのプレイヤーに利用可能な追加情報(例えば、交通パターン、気象条件、ネットワークの混雑など)を考慮するのに失敗することが多く、両者の最適な戦略に大きな影響を与える可能性がある。 両プレーヤーがプレー前に外部コンテキストを観察する,サイド情報付きStackelbergゲームのような設定を形式化する。 リーダーは(コンテキストに依存した)戦略をコミットし、フォロワーはリーダーの戦略とコンテキストの両方に最もよく対応します。 我々は、フォロワーの連続が時間とともに到着するオンライン設定に焦点を当て、そのコンテキストがラウンド・ツー・ラウンドで変化する可能性がある。 非コンテクストバージョンとは対照的に、完全な対向的な設定では、リーダが優れたパフォーマンス(後悔によって測定される)を達成することは不可能であることを示す。 この結果から,従属者の列が確率的に選択され,文脈の列が逆となるような設定と,文脈の列が確率的であり,従属者の列が敵対者によって選択されるような設定の2つの自然な緩和において,非回帰学習が可能であることが示唆された。

関連論文リスト

• Decentralized Online Learning in General-Sum Stackelberg Games [2.8659922790025463]
  プレイヤーが分散的かつ戦略的に行動する一般のStackelbergゲームにおいて,オンライン学習問題を研究する。 我々は、フォロワーにとって、リーダーの行動にミオプティカルに最も反応することが、限られた情報設定にとって最良の戦略であることを示す。 後者の設定では、フォロワーに対する新たな操作戦略を設計し、最良の応答戦略に対して本質的な優位性を示す。
  論文  参考訳（メタデータ） (2024-05-06T04:35:01Z)
• Bayesian Opponent Modeling in Multiplayer Imperfect-Information Games [1.4502611532302037]
  マルチプレイヤー不完全情報ゲームにおける対戦相手モデルへのアプローチを提案する。 我々は,3人プレイヤのクーンポーカーにおいて,種々の実敵と正確なナッシュ均衡戦略に対する実験を行う。 我々のアルゴリズムは、正確なナッシュ均衡戦略を含む全てのエージェントを著しく上回る。
  論文  参考訳（メタデータ） (2022-12-12T16:48:53Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。