論文の概要: Online Learning in Stackelberg Games with an Omniscient Follower
- arxiv url: http://arxiv.org/abs/2301.11518v1
- Date: Fri, 27 Jan 2023 03:35:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-30 16:32:05.604840
- Title: Online Learning in Stackelberg Games with an Omniscient Follower
- Title(参考訳): Omniscient FollowerによるStackelbergゲームにおけるオンライン学習
- Authors: Geng Zhao, Banghua Zhu, Jiantao Jiao, Michael I. Jordan
- Abstract要約: オンライン学習の課題を2人のプレイヤーによる分散協調型Stackelbergゲームで検討する。
各ラウンドで、まずリーダーが行動を起こし、次にリーダーの動きを観察した後に行動を起こすフォロワーが続く。
報酬構造によっては、全能なフォロワーの存在が、サンプルの複雑さを大きく変える可能性があることを示す。
- 参考スコア(独自算出の注目度): 83.42564921330896
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of online learning in a two-player decentralized
cooperative Stackelberg game. In each round, the leader first takes an action,
followed by the follower who takes their action after observing the leader's
move. The goal of the leader is to learn to minimize the cumulative regret
based on the history of interactions. Differing from the traditional
formulation of repeated Stackelberg games, we assume the follower is
omniscient, with full knowledge of the true reward, and that they always
best-respond to the leader's actions. We analyze the sample complexity of
regret minimization in this repeated Stackelberg game. We show that depending
on the reward structure, the existence of the omniscient follower may change
the sample complexity drastically, from constant to exponential, even for
linear cooperative Stackelberg games. This poses unique challenges for the
learning process of the leader and the subsequent regret analysis.
- Abstract(参考訳): オンライン学習の課題を2人のプレイヤーによる分散協調型Stackelbergゲームで検討する。
各ラウンドにおいて、リーダーはまず行動を起こし、続いてリーダーの動きを観察した後に行動を起こす従者が続く。
リーダーの目標は、対話の歴史に基づいて累積的な後悔を最小限に抑えることを学ぶことです。
繰り返し行われるスタックルバーグのゲームの伝統的な定式化から逸脱し、従者は全能であり、真の報酬を十分に知っており、常にリーダーの行動に最もよく対応していると仮定する。
この反復スタッケルバーグゲームにおける後悔の最小化のサンプル複雑性を分析した。
報酬構造により,全科学的従者の存在は,線形協調スタッケルバーグゲームにおいても,サンプル複雑性を定数から指数関数へと劇的に変化させる可能性がある。
これはリーダーの学習プロセスとその後の後悔の分析に特有の課題をもたらす。
関連論文リスト
- Regret Minimization in Stackelberg Games with Side Information [50.270531339600495]
Stackelbergゲーム (Stackelberg game) は、リーダーが(混合)戦略にコミットし、フォロワーがベスト対応する2人プレイのゲームである。
本研究は, リーダが全敵的設定で優れたパフォーマンス(後悔によって測られる)を達成することは不可能であることを示す。
論文 参考訳(メタデータ) (2024-02-13T16:24:57Z) - 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) - Uncoupled Learning of Differential Stackelberg Equilibria with
Commitments [36.08560307852286]
我々は,各プレイヤーの学習更新が相手の行動の観察にのみ依存する未結合の学習過程を示す。
この過程は, 従来と類似した条件下で局所的なスタックルバーグ平衡に収束することが証明された。
論文 参考訳(メタデータ) (2023-02-07T12:46:54Z) - Learning Correlated Stackelberg Equilibrium in General-Sum
Multi-Leader-Single-Follower Games [16.810700878778007]
本研究では、非対称な役割を持つプレイヤーをリーダーとフォロワーに分けることができる階層型マルチプレイヤーゲーム構造について検討する。
特に、複数のリーダーと1人のフォロワーがいるStackelbergのゲームシナリオに焦点を当てています。
我々は、CSE(Correlated Stackelberg Equilibrium)と呼ばれるMLSFゲームのための新しい非対称平衡概念を提案する。
論文 参考訳(メタデータ) (2022-10-22T15:05:44Z) - No-Regret Learning in Dynamic Stackelberg Games [31.001205916012307]
Stackelbergゲームでは、リーダーがランダム化された戦略にコミットし、フォロワーがレスポンスでベスト戦略を選択する。
このゲームは、リーダーの報酬や利用可能な戦略に影響を与える基礎となる状態空間を持ち、リーダーとフォロワーの選択した戦略に依存するマルコフ的な方法で進化する。
論文 参考訳(メタデータ) (2022-02-10T01:07:57Z) - Adversarial Training as Stackelberg Game: An Unrolled Optimization
Approach [91.74682538906691]
逆行訓練はディープラーニングモデルの一般化性能を向上させることが示されている。
Stackelbergゲームとして, 対人トレーニングを定式化するStackelberg Adversarial Training (SALT)を提案する。
論文 参考訳(メタデータ) (2021-04-11T00:44:57Z) - Online Learning in Unknown Markov Games [55.07327246187741]
未知のマルコフゲームでオンライン学習を学ぶ。
後方視における最良の反応に対するサブ線形後悔の達成は統計的に困難であることを示す。
サブ線形$tildemathcalO(K2/3)$ regretを$K$のエピソード後に達成するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-10-28T14:52:15Z) - Optimally Deceiving a Learning Leader in Stackelberg Games [123.14187606686006]
MLコミュニティの最近の結果は、リーダーがStackelbergゲームでコミットする最適な戦略を計算するために使用される学習アルゴリズムが、フォロワーによる操作に影響を受けやすいことを明らかにしている。
本稿は、リーダーとフォロワー間の学習相互作用に関する様々なシナリオにおいて、フォロワーが(最適に近い)ペイオフを計算することは、常に可能であることを示す。
論文 参考訳(メタデータ) (2020-06-11T16:18:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。