論文の概要: No-Regret Learning in Dynamic Stackelberg Games

• arxiv url: http://arxiv.org/abs/2202.04786v1
• Date: Thu, 10 Feb 2022 01:07:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-11 17:01:45.767835
• Title: No-Regret Learning in Dynamic Stackelberg Games
• Title（参考訳）: 動的スタックルバーグゲームにおける非回帰学習
• Authors: Niklas Lauffer, Mahsa Ghasemi, Abolfazl Hashemi, Yagiz Savas, and Ufuk Topcu
• Abstract要約: Stackelbergゲームでは、リーダーがランダム化された戦略にコミットし、フォロワーがレスポンスでベスト戦略を選択する。 このゲームは、リーダーの報酬や利用可能な戦略に影響を与える基礎となる状態空間を持ち、リーダーとフォロワーの選択した戦略に依存するマルコフ的な方法で進化する。
• 参考スコア（独自算出の注目度）: 31.001205916012307
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In a Stackelberg game, a leader commits to a randomized strategy, and a follower chooses their best strategy in response. We consider an extension of a standard Stackelberg game, called a discrete-time dynamic Stackelberg game, that has an underlying state space that affects the leader's rewards and available strategies and evolves in a Markovian manner depending on both the leader and follower's selected strategies. Although standard Stackelberg games have been utilized to improve scheduling in security domains, their deployment is often limited by requiring complete information of the follower's utility function. In contrast, we consider scenarios where the follower's utility function is unknown to the leader; however, it can be linearly parameterized. Our objective then is to provide an algorithm that prescribes a randomized strategy to the leader at each step of the game based on observations of how the follower responded in previous steps. We design a no-regret learning algorithm that, with high probability, achieves a regret bound (when compared to the best policy in hindsight) which is sublinear in the number of time steps; the degree of sublinearity depends on the number of features representing the follower's utility function. The regret of the proposed learning algorithm is independent of the size of the state space and polynomial in the rest of the parameters of the game. We show that the proposed learning algorithm outperforms existing model-free reinforcement learning approaches.
• Abstract（参考訳）: Stackelbergゲームでは、リーダーがランダム化された戦略にコミットし、フォロワーがレスポンスでベスト戦略を選択する。 我々は、離散時間動的スタックルバーグゲームと呼ばれる標準的なスタックルバーグゲームの拡張を考える。これは、リーダーの報酬と利用可能な戦略に影響を与える基礎的な状態空間を持ち、リーダーと従者の選択した戦略の両方に応じてマルコフ的手法で進化する。 標準的なstackelbergゲームはセキュリティドメインのスケジューリングを改善するために利用されてきたが、その配置は、従者のユーティリティ機能の完全な情報を必要とすることで制限されることが多い。 対照的に、従者の効用関数がリーダーに知られていないシナリオを考えるが、線形にパラメータ化できる。 本研究の目的は, ゲームの各ステップにおいて, 従者が前ステップでどう反応するかの観察に基づいて, ランダム化戦略をリーダーに規定するアルゴリズムを提供することである。 高確率で、時間ステップ数でサブ線形である後悔境界(後述の最良のポリシーと比較した場合)を達成できる非回帰学習アルゴリズムを設計し、そのサブ線形性の度合いは、フォロワーの効用関数を表す特徴数に依存する。 提案された学習アルゴリズムの後悔は、ゲームの他のパラメータにおける状態空間と多項式の大きさに依存しない。 提案した学習アルゴリズムは,既存のモデルレス強化学習手法よりも優れていることを示す。

関連論文リスト

• Neural Operators Can Play Dynamic Stackelberg Games [9.058593115274336]
  ダイナミック・スタックバーグゲーム(Dynamic Stackelberg game)は、リーダーが最初に行動する2人プレイのゲームで、フォロワーはリーダーの戦略に対する反応戦略を選択する。 本稿では,textitfollowerのベストレスポンス演算子を,textitattentionに基づくニューラル演算子によって概ね実装できることを示し,この問題に対処する。 追従者が最適応答演算子を使用するスタックルバーグゲームの価値は、元のスタックルバーグゲームの価値を近似することを示す。
  論文  参考訳（メタデータ） (2024-11-14T18:12:06Z)
• 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)
• Follower Agnostic Methods for Stackelberg Games [14.143502615941648]
  我々は,複数のフォロワーを対象とするオンラインStackelbergゲームにおいて,フォロワーに依存しない方法で効率よく解決するアルゴリズムを提案する。 私たちのアプローチは、リーダがフォロワーのユーティリティ機能や戦略空間について知識を持っていない場合でも機能します。
  論文  参考訳（メタデータ） (2023-02-02T21:21:14Z)
• Learning in Stackelberg Games with Non-myopic Agents [60.927889817803745]
  そこで本研究では,主役が非筋力的な長寿命エージェントと繰り返し対話するスタックルバーグゲームについて,エージェントの支払関数を知らずに検討する。 我々は、非ミオピックエージェントの存在下での学習を、ミオピックエージェントの存在下で堅牢な帯域最適化に還元する一般的なフレームワークを提供する。
  論文  参考訳（メタデータ） (2022-08-19T15:49:30Z)
• Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers? [156.5760265539888]
  我々は,マルチプレイヤーのジェネラルサムマルコフゲームについて,リーダーに指名されたプレイヤーとフォロワーに指名されたプレイヤーの1人を用いて研究した。 そのようなゲームに対して、我々のゴールは、政策対 $(pi*, nu*)$ であるスタックルバーグ・ナッシュ均衡 (SNE) を見つけることである。 オンラインとオフラインの両方でSNEを解くために,サンプル効率強化学習(RL)アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-12-27T05:41:14Z)
• Who Leads and Who Follows in Strategic Classification? [82.44386576129295]
  戦略分類における役割の順序は、決定者とエージェントが互いの行動に適応する相対周波数によって決定される。 更新頻度を自由に選択できる意思決定者は,いずれの順番でスタックルバーグ均衡に収束する学習力学を誘導できることを示す。
  論文  参考訳（メタデータ） (2021-06-23T16:48:46Z)
• Adversarial Training as Stackelberg Game: An Unrolled Optimization Approach [91.74682538906691]
  逆行訓練はディープラーニングモデルの一般化性能を向上させることが示されている。 Stackelbergゲームとして, 対人トレーニングを定式化するStackelberg Adversarial Training (SALT)を提案する。
  論文  参考訳（メタデータ） (2021-04-11T00:44:57Z)
• Optimally Deceiving a Learning Leader in Stackelberg Games [123.14187606686006]
  MLコミュニティの最近の結果は、リーダーがStackelbergゲームでコミットする最適な戦略を計算するために使用される学習アルゴリズムが、フォロワーによる操作に影響を受けやすいことを明らかにしている。 本稿は、リーダーとフォロワー間の学習相互作用に関する様々なシナリオにおいて、フォロワーが(最適に近い)ペイオフを計算することは、常に可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-11T16:18:21Z)
• Model-free Reinforcement Learning for Stochastic Stackelberg Security Games [7.470839530834359]
  リーダーとフォロワーの2人のプレイヤーによる連続的なStackelbergゲームについて検討する。 フォロワーはシステムの状態にアクセスでき、リーダーはアクセスしない。 本稿では,MDPのモデルをシミュレートして,スタックルバーグ均衡政策を学習する予測サーサに基づくRLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-24T22:34:20Z)

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

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