論文の概要: Learning in Structured Stackelberg Games

• arxiv url: http://arxiv.org/abs/2504.09006v2
• Date: Mon, 04 Aug 2025 14:51:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-05 14:07:56.611626
• Title: Learning in Structured Stackelberg Games
• Title（参考訳）: 構造化スタックルバーグゲームにおける学習
• Authors: Maria-Florina Balcan, Kiriaki Fragkia, Keegan Harris,
• Abstract要約: 構造化されたStackelbergゲームについて検討し、両プレイヤーがプレイ時の世界の状況に関する文脈情報を観察する。 我々は、文脈情報とフォロワーのタイプの間に固定的な関係を仮定する。 本研究は,学習課題の難しさを特徴付けるものではないことを示唆する。
• 参考スコア（独自算出の注目度）: 20.392732735387238
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study structured Stackelberg games, in which both players (the leader and the follower) observe contextual information about the state of the world at time of play. The leader plays against one of a finite number of followers, but the follower's type is not known until after the game has ended. Importantly, we assume a fixed relationship between the contextual information and the follower's type, thereby allowing the leader to leverage this additional structure when deciding her strategy. Under this setting, we find that standard learning theoretic measures of complexity do not characterize the difficulty of the leader's learning task. Instead, we introduce a new notion of dimension, the Stackelberg-Littlestone dimension, which we show characterizes the instance-optimal regret of the leader in the online setting. Based on this, we also provide a provably optimal learning algorithm. We extend our results to the distributional setting, where we use two new notions of dimension, the $\gamma$-Stackelberg-Natarajan dimension and $\gamma$-Stackelberg-Graph dimension. We prove that these control the sample complexity lower and upper bounds respectively, and we design a simple, improper algorithm that achieves the upper bound.
• Abstract（参考訳）: 構造化されたStackelbergゲームについて検討し、プレイヤー(リーダーとフォロワー)がプレイ時の世界の状況に関する文脈情報を観察する。 リーダーは、限られた数のフォロワーの1人に対してプレーするが、ゲームの終了後までフォロワーのタイプは分かっていない。 重要なことは、コンテキスト情報とフォロワーのタイプの間に固定された関係を仮定することで、リーダーが戦略を決定する際に、この付加的な構造を活用できるということです。 この条件下では,複雑性の標準的な学習理論尺度は,リーダーの学習課題の難しさを特徴づけるものではない。 代わりに、新しい次元の概念であるStackelberg-Littlestoneディメンションを導入し、オンライン環境におけるリーダーのインスタンス最適化後悔を特徴づける。 これに基づいて、証明可能な最適学習アルゴリズムも提供する。 我々はその結果を分布的設定にまで拡張し、そこでは、$\gamma$-Stackelberg-Natarajan 次元と$\gamma$-Stackelberg-Graph 次元という2つの新しい次元の概念を使用する。 サンプルの複雑さをそれぞれ下界と上界を制御できることを証明し、上界を達成できる単純で不適切なアルゴリズムを設計する。

関連論文リスト

• Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information [57.287431079644705]
  そこで我々は,Stackelbergゲームにおけるオンライン学習の問題について,リーダーとフォロワーの列の側情報を用いて検討した。 我々は,リーダに対する学習アルゴリズムを提供し,盗聴フィードバックの下でO(T1/2)$後悔を達成する。
  論文  参考訳（メタデータ） (2025-01-31T22:40:57Z)
• 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)
• Online Learning in Stackelberg Games with an Omniscient Follower [83.42564921330896]
  オンライン学習の課題を2人のプレイヤーによる分散協調型Stackelbergゲームで検討する。 各ラウンドで、まずリーダーが行動を起こし、次にリーダーの動きを観察した後に行動を起こすフォロワーが続く。 報酬構造によっては、全能なフォロワーの存在が、サンプルの複雑さを大きく変える可能性があることを示す。
  論文  参考訳（メタデータ） (2023-01-27T03:35:10Z)
• Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization [39.51923275855131]
  本研究では,テスト時間における逆例に頑健な予測器の学習問題に対して,最小限の最適学習器を提案する。 特に、強い否定的な意味で、モンタッサー、ハネケ、スレブロによって提案された頑健な学習者の亜最適性を示す。
  論文  参考訳（メタデータ） (2022-09-15T15:32:42Z)
• Learning in Stackelberg Games with Non-myopic Agents [60.927889817803745]
  そこで本研究では,主役が非筋力的な長寿命エージェントと繰り返し対話するスタックルバーグゲームについて,エージェントの支払関数を知らずに検討する。 我々は、非ミオピックエージェントの存在下での学習を、ミオピックエージェントの存在下で堅牢な帯域最適化に還元する一般的なフレームワークを提供する。
  論文  参考訳（メタデータ） (2022-08-19T15:49:30Z)
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
  本研究では、半教師付きPACモデルにおいて、時間攻撃をテストするために、逆向きに頑健な予測器を学習する問題について検討する。 最悪の分布自由モデルにおいても,半教師付き頑健な学習には大きなメリットがあることが示されている。
  論文  参考訳（メタデータ） (2022-02-11T03:01:45Z)
• No-Regret Learning in Dynamic Stackelberg Games [31.001205916012307]
  Stackelbergゲームでは、リーダーがランダム化された戦略にコミットし、フォロワーがレスポンスでベスト戦略を選択する。 このゲームは、リーダーの報酬や利用可能な戦略に影響を与える基礎となる状態空間を持ち、リーダーとフォロワーの選択した戦略に依存するマルコフ的な方法で進化する。
  論文  参考訳（メタデータ） (2022-02-10T01:07:57Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。 特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。 以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
  論文  参考訳（メタデータ） (2022-02-08T16:39: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)
• When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning? [53.523017945443115]
  我々は,十分な精度のトレーニングアルゴリズムが,予測モデルにおいて,そのトレーニング例の大規模サブセットに関する情報を本質的にすべてエンコードしなければならない自然予測問題を記述する。 私たちの結果は、トレーニングアルゴリズムや学習に使用されるモデルのクラスに依存しません。
  論文  参考訳（メタデータ） (2020-12-11T15:25:14Z)
• Sample-efficient proper PAC learning with approximate differential privacy [51.09425023771246]
  近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。 この結果は Bun et al の質問に答えます。 (FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
  論文  参考訳（メタデータ） (2020-12-07T18:17:46Z)
• Optimally Deceiving a Learning Leader in Stackelberg Games [123.14187606686006]
  MLコミュニティの最近の結果は、リーダーがStackelbergゲームでコミットする最適な戦略を計算するために使用される学習アルゴリズムが、フォロワーによる操作に影響を受けやすいことを明らかにしている。 本稿は、リーダーとフォロワー間の学習相互作用に関する様々なシナリオにおいて、フォロワーが(最適に近い)ペイオフを計算することは、常に可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-11T16:18:21Z)
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? [108.94173231481355]
  長い地平線を計画する学習は、エピソード強化学習問題における中心的な課題である。 長地平線RLは、少なくともミニマックス感覚において、短地平線RLよりも困難ではないことを示す。
  論文  参考訳（メタデータ） (2020-05-01T17:56:38Z)

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

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