論文の概要: Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent

• arxiv url: http://arxiv.org/abs/2510.22471v1
• Date: Sun, 26 Oct 2025 01:09:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 17:41:21.966518
• Title: Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent
• Title（参考訳）: 学習エージェントとの繰り返し相互作用による局所スタックルバーグ平衡の学習
• Authors: Nivasini Ananthakrishnan, Yuval Dagan, Kunhe Yang,
• Abstract要約: そこで我々は,エプシロン近似局所スタックルバーグ平衡を求めるアルゴリズムを提案する。 特に、アルゴリズムのランタイムはエージェントのアクション空間のサイズであるが、1/epsilonでは指数関数的である。
• 参考スコア（独自算出の注目度）: 14.992657154680215
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Motivated by the question of how a principal can maximize its utility in repeated interactions with a learning agent, we study repeated games between an principal and an agent employing a mean-based learning algorithm. Prior work has shown that computing or even approximating the global Stackelberg value in similar settings can require an exponential number of rounds in the size of the agent's action space, making it computationally intractable. In contrast, we shift focus to the computation of local Stackelberg equilibria and introduce an algorithm that, within the smoothed analysis framework, constitutes a Polynomial Time Approximation Scheme (PTAS) for finding an epsilon-approximate local Stackelberg equilibrium. Notably, the algorithm's runtime is polynomial in the size of the agent's action space yet exponential in (1/epsilon) - a dependency we prove to be unavoidable.
• Abstract（参考訳）: 学習エージェントとの繰り返しの相互作用において,プリンシパルが有効性を最大化できるかという質問に触発され,平均学習アルゴリズムを用いて,プリンシパルとエージェントの繰り返しゲームについて検討した。 以前の研究は、計算や、同様の設定でグローバルなStackelberg値を近似することさえも、エージェントのアクション空間のサイズで指数関数的なラウンド数を必要とすることを示しており、計算的に難解である。 対照的に、我々は局所的なスタックルバーグ平衡の計算に焦点を移し、スムーズな解析フレームワークの中で、エプシロン近似な局所スタックルバーグ平衡を求めるためのポリノミアル時間近似スキーム(PTAS)を構成するアルゴリズムを導入する。 特に、アルゴリズムのランタイムは、エージェントの作用空間が 1/エプシロン) で指数的であるほどの大きさの多項式である。

関連論文リスト

• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  ハーフスペースの交叉学習は計算学習理論における中心的な問題である。 たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。 本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-11-13T00:28:24Z)
• A Communication-Efficient Decentralized Actor-Critic Algorithm [5.138643040049347]
  本研究では,各エージェントがポリシーと値関数の局所的な更新を行う分散アクタ批判学習フレームワークを開発する。 このローカルトレーニング戦略は、ネットワーク間の協調を維持しながら、通信負担を大幅に削減する。
  論文  参考訳（メタデータ） (2025-10-22T03:15:52Z)
• Scaling Large Language Model-based Multi-Agent Collaboration [72.8998796426346]
  近年の大規模言語モデル駆動型自律エージェントのブレークスルーにより、複数エージェントのコラボレーションが集団的推論を通じて各個人を上回ることが判明している。 本研究は、協調剤の連続的な添加が同様の利益をもたらすかどうかを考察する。
  論文  参考訳（メタデータ） (2024-06-11T11:02:04Z)
• RL in Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Model [15.596599935486534]
  シミュレータへの局所アクセスを伴う粗相関平衡(CCE)を学習するための新しいアルゴリズムLin-Confident-FTRLを導入する。 状態空間のサイズに対数的依存がある限り、Lin-Confident-FTRLは証明可能な最適精度で$O(epsilon-2)$で$epsilon$-CCEを学ぶ。 本分析は,単一エージェントのローカルプランニング文献における仮想ポリシー境界を一般化する。
  論文  参考訳（メタデータ） (2024-03-18T07:54:11Z)
• Understanding Augmentation-based Self-Supervised Representation Learning via RKHS Approximation and Regression [53.15502562048627]
  最近の研究は、自己教師付き学習とグラフラプラシアン作用素のトップ固有空間の近似との関係を構築している。 この研究は、増強に基づく事前訓練の統計的分析に発展する。
  論文  参考訳（メタデータ） (2023-06-01T15:18:55Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Learning in Stackelberg Games with Non-myopic Agents [60.927889817803745]
  そこで本研究では,主役が非筋力的な長寿命エージェントと繰り返し対話するスタックルバーグゲームについて,エージェントの支払関数を知らずに検討する。 我々は、非ミオピックエージェントの存在下での学習を、ミオピックエージェントの存在下で堅牢な帯域最適化に還元する一般的なフレームワークを提供する。
  論文  参考訳（メタデータ） (2022-08-19T15:49:30Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。 このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
  論文  参考訳（メタデータ） (2022-06-01T23:26:51Z)
• Decentralized Cooperative Multi-Agent Reinforcement Learning with Exploration [35.75029940279768]
  マルコフチーム(Markov team)において、最も基本的な協調環境でマルチエージェント強化学習を研究する。 本稿では,各エージェントが独立してステージベースのVラーニングスタイルのアルゴリズムを実行するアルゴリズムを提案する。 エージェントは、少なくとも$proptowidetildeO (1/epsilon4)$ episodesにおいて、$epsilon$-approximate Nash平衡ポリシーを学ぶことができる。
  論文  参考訳（メタデータ） (2021-10-12T02:45:12Z)
• Dimension-Free Rates for Natural Policy Gradient in Multi-Agent Reinforcement Learning [22.310861786709538]
  協調型マルチエージェント強化学習のためのスケーラブルなアルゴリズムを提案する。 このアルゴリズムは,次元自由な統計量と計算量とで,グローバルな最適ポリシーに収束することを示す。
  論文  参考訳（メタデータ） (2021-09-23T23:38:15Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Multi-Agent Reinforcement Learning in Stochastic Networked Systems [30.78949372661673]
  エージェントネットワークにおけるマルチエージェント強化学習(MARL)について検討する。 目的は、世界的報酬を最大化する局所的な政策を見つけることである。
  論文  参考訳（メタデータ） (2020-06-11T16:08:16Z)

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

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