論文の概要: Learning in Structured Stackelberg Games

• arxiv url: http://arxiv.org/abs/2504.09006v1
• Date: Fri, 11 Apr 2025 23:14:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-15 16:49:24.620376
• Title: Learning in Structured Stackelberg Games
• Title（参考訳）: 構造化スタックルバーグゲームにおける学習
• Authors: Maria-Florina Balcan, Kiriaki Fragkia, Keegan Harris,
• Abstract要約: プレイヤー(リーダーとフォロワー)がプレイ時の世界の状況を観察する構造化されたスタックルバーグゲームについて検討する。 この情報は、彼女の戦略を決定する際にリーダーが使用するフォロワーに関する情報を含むかもしれない。 リーダが学習するために使用するコンテキストからフォローアタイプへのマッピングセットがあまりに複雑ではない場合に限り、非回帰学習が可能であることを示しています。
• 参考スコア（独自算出の注目度）: 20.392732735387238
• License:
• Abstract: We study structured Stackelberg games, in which both players (the leader and the follower) observe information about the state of the world at time of play. Importantly, this information may contain information about the follower, which the leader may use when deciding her strategy. Under this setting, we show that no-regret learning is possible if and only if the set of mappings from contexts to follower types that the leader uses to learn is not ``too complex''. Specifically, we find that standard learning theoretic measures of complexity do not characterize learnability in our setting and we give a new dimension which does, which we term the Stackelberg-Littlestone dimension. In the distributional setting, we give analogous results by showing that standard complexity measures do not characterize the sample complexity of learning, but a new dimension called the Stackelberg-Natarajan dimension does. We then show that an appropriate empirical risk minimization procedure achieves the corresponding sample complexity.
• Abstract（参考訳）: 構造化されたStackelbergゲームについて検討し、プレイヤー(リーダーとフォロワー)がプレイ時の世界の状況に関する情報を観察する。 重要なことは、この情報は、彼女の戦略を決定するときに、リーダーが使用するフォロワーに関する情報を含むかもしれない。 この設定の下では,リーダが学習に使用するコンテキストから従者タイプへのマッピングセットが‘あまりにも複雑’ではない場合に限り,非回帰学習が可能であることを示す。 具体的には、複雑性の標準的な学習理論測度は、我々の設定における学習可能性を特徴づけるものではなく、新しい次元を与え、それをスタックルバーグ・リトルストーン次元と呼ぶ。 分布設定において、標準的な複雑性測度は学習のサンプルの複雑さを特徴づけるものではなく、スタックルベルグ・ナタラジャン次元と呼ばれる新しい次元を特徴付けることを示した。 次に、適切な経験的リスク最小化手法により、対応するサンプルの複雑さが達成されることを示す。

関連論文リスト

• 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)
• 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)
• 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)
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? [108.94173231481355]
  長い地平線を計画する学習は、エピソード強化学習問題における中心的な課題である。 長地平線RLは、少なくともミニマックス感覚において、短地平線RLよりも困難ではないことを示す。
  論文  参考訳（メタデータ） (2020-05-01T17:56:38Z)

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

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