論文の概要: 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$ターゲットで改善する。
この結果は、非ミオピックエージェントによる学習を超えた独立した関心である。
関連論文リスト
- Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents [16.514561132180134]
本研究では,エージェントが武器を弾くためのインセンティブを提案することで,主役が未知の環境と間接的に対話する繰り返しプリンシパル・エージェント・バンディットゲームについて検討する。
既存の作業の多くは、エージェントが報酬手段について十分な知識を持っていると仮定し、常に欲張りに振る舞うが、多くのオンラインマーケットプレースでは、エージェントは未知の環境を学び、時には探索する必要がある。
そこで我々は,報酬推定を反復的に更新する探索行動を持つ自己関心学習エージェントをモデル化し,推定報酬プラスインセンティブを最大化するアームを選択するか,一定の確率で任意に探索するアームを選択する。
論文 参考訳(メタデータ) (2024-12-20T20:04:50Z) - Strategic Classification With Externalities [11.36782598786846]
戦略分類問題の新しい変種を提案する。
実世界のアプリケーションによって動機づけられた我々のモデルは、あるエージェントの操作が他のエージェントに影響を与えることを決定的に許している。
特定の仮定の下では、このエージェント操作ゲームの純粋なナッシュ平衡はユニークであり、効率的に計算できることが示される。
論文 参考訳(メタデータ) (2024-10-10T15:28:04Z) - Toward Optimal LLM Alignments Using Two-Player Games [86.39338084862324]
本稿では,対戦相手と防御エージェントの反復的相互作用を含む2エージェントゲームのレンズによるアライメントについて検討する。
この反復的強化学習最適化がエージェントによって誘導されるゲームに対するナッシュ平衡に収束することを理論的に実証する。
安全シナリオにおける実験結果から、このような競争環境下での学習は、完全に訓練するエージェントだけでなく、敵エージェントと防御エージェントの両方に対する一般化能力の向上したポリシーにつながることが示されている。
論文 参考訳(メタデータ) (2024-06-16T15:24:50Z) - Impact of Decentralized Learning on Player Utilities in Stackelberg Games [57.08270857260131]
多くの2エージェントシステムでは、各エージェントは別々に学習し、2つのエージェントの報酬は完全に一致しない。
分散学習を用いたStackelbergゲームとしてこれらのシステムをモデル化し、標準後悔ベンチマークが少なくとも1人のプレイヤーにとって最悪の線形後悔をもたらすことを示す。
我々は,これらのベンチマークに関して,両プレイヤーにとってほぼ最適な$O(T2/3)を後悔するアルゴリズムを開発した。
論文 参考訳(メタデータ) (2024-02-29T23:38:28Z) - 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) - Disturbing Reinforcement Learning Agents with Corrupted Rewards [62.997667081978825]
強化学習アルゴリズムに対する報酬の摂動に基づく異なる攻撃戦略の効果を分析します。
敵対的な報酬をスムーズに作成することは学習者を誤解させることができ、低探査確率値を使用すると、学習した政策は報酬を腐敗させるのがより堅牢であることを示しています。
論文 参考訳(メタデータ) (2021-02-12T15:53:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。