論文の概要: Follower Agnostic Methods for Stackelberg Games
- arxiv url: http://arxiv.org/abs/2302.01421v3
- Date: Wed, 27 Mar 2024 00:38:33 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-28 23:31:58.772785
- Title: Follower Agnostic Methods for Stackelberg Games
- Title(参考訳): Stackelberg ゲームにおけるより低速なアグノスティック手法
- Authors: Chinmay Maheshwari, James Cheng, S. Shankar Sasty, Lillian Ratliff, Eric Mazumdar,
- Abstract要約: 我々は,複数のフォロワーを対象とするオンラインStackelbergゲームにおいて,フォロワーに依存しない方法で効率よく解決するアルゴリズムを提案する。
私たちのアプローチは、リーダがフォロワーのユーティリティ機能や戦略空間について知識を持っていない場合でも機能します。
- 参考スコア(独自算出の注目度): 14.143502615941648
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we present an efficient algorithm to solve online Stackelberg games, featuring multiple followers, in a follower-agnostic manner. Unlike previous works, our approach works even when leader has no knowledge about the followers' utility functions or strategy space. Our algorithm introduces a unique gradient estimator, leveraging specially designed strategies to probe followers. In a departure from traditional assumptions of optimal play, we model followers' responses using a convergent adaptation rule, allowing for realistic and dynamic interactions. The leader constructs the gradient estimator solely based on observations of followers' actions. We provide both non-asymptotic convergence rates to stationary points of the leader's objective and demonstrate asymptotic convergence to a \emph{local Stackelberg equilibrium}. To validate the effectiveness of our algorithm, we use this algorithm to solve the problem of incentive design on a large-scale transportation network, showcasing its robustness even when the leader lacks access to followers' demand.
- Abstract(参考訳): 本稿では,複数のフォロワーを対象とするオンラインStackelbergゲームにおいて,フォロワーに依存しない方法で効率よく解決するアルゴリズムを提案する。
従来の作業とは異なり、私たちのアプローチは、リーダがフォロワーのユーティリティ機能や戦略空間について知識を持っていない場合でも機能します。
アルゴリズムは、特別な設計の戦略を利用してフォロワーを探索する独自の勾配推定器を導入する。
最適な遊びの伝統的な仮定から離れて、収束適応規則を用いてフォロワーの反応をモデル化し、現実的でダイナミックな相互作用を可能にする。
リーダーは、フォロワーの行動の観察のみに基づいて勾配推定器を構築する。
我々は、リーダーの目的の定常点に非漸近収束率を提供し、また \emph{local Stackelberg equilibrium} への漸近収束を示す。
提案アルゴリズムの有効性を検証するため,大規模交通ネットワークにおけるインセンティブ設計の問題を解決するため,リーダがフォロワーの要求に応えていない場合でも,その堅牢性を示す。
関連論文リスト
- Actions Speak What You Want: Provably Sample-Efficient Reinforcement
Learning of the Quantal Stackelberg Equilibrium from Strategic Feedbacks [94.07688076435818]
本研究では,量子スタックルバーグ平衡(QSE)学習のための強化学習を,リーダ・フォロワー構造を持つエピソディックマルコフゲームで研究する。
このアルゴリズムは, (i) 最大推定による量子応答モデル学習と (ii) リーダーの意思決定問題を解決するためのモデルフリーまたはモデルベースRLに基づく。
論文 参考訳(メタデータ) (2023-07-26T10:24:17Z) - Computing the optimal distributionally-robust strategy to commit to [32.1464237233989]
分布的に不安定なスタックルバーグ均衡は、常に幅広い不確実性モデルにわたって存在することを示す。
そこで我々は,分散ロバストな強いスタックルバーグ均衡を計算するための2つのアルゴリズムを提案する。
実験は,従来のStackelbergゲーム上でのアルゴリズムのトラクタビリティを裏付けるものである。
論文 参考訳(メタデータ) (2022-09-15T23:20:26Z) - Large-Scale Sequential Learning for Recommender and Engineering Systems [91.3755431537592]
本稿では,現在の状況に適応してパーソナライズされたランキングを提供する自動アルゴリズムの設計に焦点を当てる。
前者はSAROSと呼ばれる新しいアルゴリズムを提案し,インタラクションの順序を学習するためのフィードバックの種類を考慮に入れている。
提案手法は, 電力網の故障検出に対する初期アプローチと比較して, 統計的に有意な結果を示す。
論文 参考訳(メタデータ) (2022-05-13T21:09:41Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳(メタデータ) (2022-05-06T03:37:00Z) - No-Regret Learning in Dynamic Stackelberg Games [31.001205916012307]
Stackelbergゲームでは、リーダーがランダム化された戦略にコミットし、フォロワーがレスポンスでベスト戦略を選択する。
このゲームは、リーダーの報酬や利用可能な戦略に影響を与える基礎となる状態空間を持ち、リーダーとフォロワーの選択した戦略に依存するマルコフ的な方法で進化する。
論文 参考訳(メタデータ) (2022-02-10T01:07:57Z) - Bayesian Graph Contrastive Learning [55.36652660268726]
本稿では,ランダムな拡張がエンコーダにつながることを示すグラフコントラスト学習手法の新たな視点を提案する。
提案手法は,各ノードを決定論的ベクトルに埋め込む既存の手法とは対照的に,各ノードを潜在空間の分布で表現する。
いくつかのベンチマークデータセットにおける既存の最先端手法と比較して,性能が大幅に向上したことを示す。
論文 参考訳(メタデータ) (2021-12-15T01:45:32Z) - Stackelberg Actor-Critic: Game-Theoretic Reinforcement Learning
Algorithms [13.649494534428745]
アクター批判に基づく強化学習アルゴリズムにおけるアクターと批評家の階層的相互作用は、ゲーム理論の解釈に自然に結びつく。
そこで我々は,従来の個人勾配ではなく,その目的の全体微分をリーダプレイヤーが追従する,Stackelbergアクタ批判アルゴリズムのメタフレームワークを提案する。
OpenAIのジム環境での実験では、Stackelbergのアクター批判アルゴリズムは常に、少なくとも同じようにパフォーマンスし、標準的なアクター批判アルゴリズムよりもはるかに優れていることが示されている。
論文 参考訳(メタデータ) (2021-09-25T06:18:41Z) - Policy Gradient for Continuing Tasks in Non-stationary Markov Decision
Processes [112.38662246621969]
強化学習は、マルコフ決定プロセスにおいて期待される累積報酬を最大化するポリシーを見つけることの問題を考える。
我々は、ポリシーを更新するために上昇方向として使用する値関数の偏りのないナビゲーション勾配を計算する。
ポリシー勾配型アルゴリズムの大きな欠点は、定常性の仮定が課せられない限り、それらがエピソジックなタスクに限定されていることである。
論文 参考訳(メタデータ) (2020-10-16T15:15:42Z) - Optimally Deceiving a Learning Leader in Stackelberg Games [123.14187606686006]
MLコミュニティの最近の結果は、リーダーがStackelbergゲームでコミットする最適な戦略を計算するために使用される学習アルゴリズムが、フォロワーによる操作に影響を受けやすいことを明らかにしている。
本稿は、リーダーとフォロワー間の学習相互作用に関する様々なシナリオにおいて、フォロワーが(最適に近い)ペイオフを計算することは、常に可能であることを示す。
論文 参考訳(メタデータ) (2020-06-11T16:18:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。