論文の概要: Learning in Stackelberg Games with Non-myopic Agents
- arxiv url: http://arxiv.org/abs/2208.09407v1
- Date: Fri, 19 Aug 2022 15:49:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-22 17:45:31.090770
- Title: Learning in Stackelberg Games with Non-myopic Agents
- Title（参考訳）: 非筋覚エージェントを用いたstackelbergゲームにおける学習
- Authors: Nika Haghtalab, Thodoris Lykouris, Sloan Nietert, Alex Wei
- Abstract要約: 主成分が長寿命の非ミオピックエージェントと繰り返し相互作用するスタックルバーグゲームについて検討する。
Stackelbergゲームでの学習は、エージェントがミオピックであるときによく理解されているが、非ミオピックエージェントはさらなる合併症を引き起こす。
我々は、非ミオピックエージェントの存在下での学習を、ミオピックエージェントの存在下で堅牢な帯域最適化に還元する一般的なフレームワークを提供する。
- 参考スコア（独自算出の注目度）: 14.727571071020446
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study Stackelberg games where a principal repeatedly interacts with a
long-lived, non-myopic agent, without knowing the agent's payoff function.
Although learning in Stackelberg games is well-understood when the agent is
myopic, non-myopic agents pose additional complications. In particular,
non-myopic agents may strategically select actions that are inferior in the
present to mislead the principal's learning algorithm and obtain better
outcomes in the future.
We provide a general framework that reduces learning in presence of
non-myopic agents to robust bandit optimization in the presence of myopic
agents. Through the design and analysis of minimally reactive bandit
algorithms, our reduction trades off the statistical efficiency of the
principal's learning algorithm against its effectiveness in inducing
near-best-responses. We apply this framework to Stackelberg security games
(SSGs), pricing with unknown demand curve, strategic classification, and
general finite Stackelberg games. In each setting, we characterize the type and
impact of misspecifications present in near-best-responses and develop a
learning algorithm robust to such misspecifications.
Along the way, we improve the query complexity of learning in SSGs with $n$
targets from the state-of-the-art $O(n^3)$ to a near-optimal $\widetilde{O}(n)$
by uncovering a fundamental structural property of such games. This result is
of independent interest beyond learning with non-myopic agents.
- Abstract（参考訳）: そこで本研究では,校長がエージェントの報酬関数を知らずに長生きする非筋覚剤と繰り返し対話する,stackelbergゲームについて検討する。
スタッケルバーグゲームでの学習は、エージェントがミオライクであるときによく理解されているが、非ミオライクエージェントは追加の合併症を引き起こす。
特に、非筋覚剤は、現在より劣っている行動を戦略的に選択して、校長の学習アルゴリズムを誤解させ、将来より良い結果を得ることができる。
我々は、非ミオピックエージェントの存在下での学習を、ミオピックエージェントの存在下で堅牢な帯域最適化に還元する一般的なフレームワークを提供する。
最小反応性バンディットアルゴリズムの設計と解析を通じて,本手法は主学習アルゴリズムの統計的効率と,その近親感誘導効果とをトレードオフする。
このフレームワークをStackelbergセキュリティゲーム(SSG)に適用し、要求曲線の未知の価格、戦略分類、一般有限なStackelbergゲームに適用する。
各設定において、最寄りの応答に存在する誤特定の種類と影響を特徴付け、そのような誤特定に頑健な学習アルゴリズムを開発する。
その過程で、ssgsにおける学習のクエリの複雑さを、最先端の$o(n^3)$から準最適の$\widetilde{o}(n)$まで、そのようなゲームの基本的な構造的性質を明らかにすることによって、n$ターゲットで改善する。
この結果は、非ミオピックエージェントによる学習を超えた独立した関心である。
関連論文リスト
- Paths to Equilibrium in Normal-Form Games [6.812247730094933]
マルチエージェント強化学習(MARL)では、エージェントは時間をかけて繰り返し対話し、新たなデータが到着するにつれて戦略を再検討する。
本稿では,強化学習における政策更新に触発された一対の制約を満たす戦略の列について検討する。
論文 参考訳（メタデータ） (2024-03-26T19:58:39Z) - Impact of Decentralized Learning on Player Utilities in Stackelberg Games [57.08270857260131]
多くの2エージェントシステムでは、各エージェントは別々に学習し、2つのエージェントの報酬は完全に一致しない。
分散学習を用いたStackelbergゲームとしてこれらのシステムをモデル化し、標準後悔ベンチマークが少なくとも1人のプレイヤーにとって最悪の線形後悔をもたらすことを示す。
我々は,これらのベンチマークに関して,両プレイヤーにとってほぼ最適な$O(T2/3)を後悔するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-02-29T23:38:28Z) - Generalized Principal-Agent Problem with a Learning Agent [6.2458948163267785]
一般的な主要エージェント問題は、エージェントがプリンシパルのコミット戦略に最もよく反応する経済問題である。
エージェントが平均に基づく学習アルゴリズムを使用する場合、プリンシパルは非学習モデルよりもはるかに優れていることを示す。
論文 参考訳（メタデータ） (2024-02-15T05:30:47Z) - MERMAIDE: Learning to Align Learners using Model-Based Meta-Learning [62.065503126104126]
本研究では,先見のつかない学習エージェントの報酬を効率よく効果的に介入し,望ましい結果を導き出す方法について検討する。
これはオークションや課税のような現実世界の多くの設定に関係しており、プリンシパルは学習行動や実際の人々の報酬を知らないかもしれない。
モデルに基づくメタ学習フレームワークであるMERMAIDEを導入し,配布外エージェントに迅速に適応できるプリンシパルを訓練する。
論文 参考訳（メタデータ） (2023-04-10T15:44:50Z) - Learning to Incentivize Information Acquisition: Proper Scoring Rules
Meet Principal-Agent Model [64.94131130042275]
インセンティブ付き情報取得問題について検討し、主治官がエージェントを雇って代理情報を収集する。
UCBアルゴリズムをモデルに適合させる,実証可能なサンプル効率の良いアルゴリズムを設計する。
本アルゴリズムは,主役の最適利益に対する微妙な推定手順と,所望のエージェントの行動にインセンティブを与える保守的な補正手法を特徴とする。
論文 参考訳（メタデータ） (2023-03-15T13:40:16Z) - Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。
我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。
先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
論文 参考訳（メタデータ） (2022-06-17T12:58:58Z) - Disturbing Reinforcement Learning Agents with Corrupted Rewards [62.997667081978825]
強化学習アルゴリズムに対する報酬の摂動に基づく異なる攻撃戦略の効果を分析します。
敵対的な報酬をスムーズに作成することは学習者を誤解させることができ、低探査確率値を使用すると、学習した政策は報酬を腐敗させるのがより堅牢であることを示しています。
論文 参考訳（メタデータ） (2021-02-12T15:53:48Z) - Optimally Deceiving a Learning Leader in Stackelberg Games [123.14187606686006]
MLコミュニティの最近の結果は、リーダーがStackelbergゲームでコミットする最適な戦略を計算するために使用される学習アルゴリズムが、フォロワーによる操作に影響を受けやすいことを明らかにしている。
本稿は、リーダーとフォロワー間の学習相互作用に関する様々なシナリオにおいて、フォロワーが(最適に近い)ペイオフを計算することは、常に可能であることを示す。
論文 参考訳（メタデータ） (2020-06-11T16:18:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。