論文の概要: Learning to Control Unknown Strongly Monotone Games

• arxiv url: http://arxiv.org/abs/2407.00575v2
• Date: Sat, 11 Jan 2025 12:27:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-14 14:20:38.838022
• Title: Learning to Control Unknown Strongly Monotone Games
• Title（参考訳）: 未知の強いモノトーンゲームを制御するための学習
• Authors: Siddharth Chandak, Ilai Bistritz, Nicholas Bambos,
• Abstract要約: 制御係数をオンラインで調整することで,線形制約を満たすためにNEをシフトするアルゴリズムを提案する。 我々のアルゴリズムは線形制約違反をフィードバックとして要求するだけであり、報酬関数やアクションセットを知る必要はない。
• 参考スコア（独自算出の注目度）: 16.327788209492805
• License:
• Abstract: Consider a game where the players' utility functions include a reward function and a linear term for each dimension, with coefficients that are controlled by the manager. We assume that the game is strongly monotone, so gradient play converges to a unique Nash equilibrium (NE). The NE is typically globally inefficient. The global performance at NE can be improved by imposing linear constraints on the NE. We therefore want the manager to pick the controlled coefficients that impose the desired constraint on the NE. However, this requires knowing the players' reward functions and action sets. Obtaining this game information is infeasible in a large-scale network and violates user privacy. To overcome this, we propose a simple algorithm that learns to shift the NE to meet the linear constraints by adjusting the controlled coefficients online. Our algorithm only requires the linear constraints violation as feedback and does not need to know the reward functions or the action sets. We prove that our algorithm converges with probability 1 to the set of NE that satisfy target linear constraints. We then prove an L2 convergence rate of near-$O(t^{-1/4})$.
• Abstract（参考訳）: プレイヤーの効用関数が各次元に対する報酬関数と線形項を含み、管理者が制御する係数を持つゲームを考える。 ゲームは強い単調であると仮定するので、勾配プレイは固有のナッシュ均衡(NE)に収束する。 通常、NEは非効率である。 NEのグローバルパフォーマンスは、NEに線形制約を課すことで改善できる。 したがって、我々はマネージャが NE に所望の制約を課す制御係数を選択することを望んでいます。 しかし、プレイヤーの報酬機能やアクションセットを知る必要がある。 このゲーム情報の取得は、大規模なネットワークでは不可能であり、ユーザのプライバシを侵害する。 そこで本研究では,制御係数をオンラインで調整することで,線形制約を満たすためにNEをシフトする簡単なアルゴリズムを提案する。 我々のアルゴリズムは線形制約違反をフィードバックとして要求するだけであり、報酬関数やアクションセットを知る必要はない。 目的とする線形制約を満たす NE の集合に確率 1 に収束することを示す。 次に、L2 の収束速度を約$O(t^{-1/4})$とする。

関連論文リスト

• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。 本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
  論文  参考訳（メタデータ） (2023-10-21T18:38:13Z)
• Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning [105.7510838453122]
  制約付きマルコフゲームを用いたオンライン安全なマルチエージェント強化学習について検討する。 我々は,このラグランジアン問題を解くための高信頼強化学習アルゴリズムを開発した。 提案アルゴリズムは,オンラインミラー降下によるミニマックス決定主元変数と,投影勾配ステップによる双対変数を更新する。
  論文  参考訳（メタデータ） (2023-05-31T22:09:24Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• 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)
• Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
  本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。 我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。 そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
  論文  参考訳（メタデータ） (2021-12-06T08:27:54Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。 我々はNash equilibria(NE)の解の概念に焦点をあてる。 このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
  論文  参考訳（メタデータ） (2021-11-07T21:15:35Z)
• Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall [34.73929457960903]
  本研究では,不完全情報ゲーム(IIG)におけるナッシュ均衡(NE)学習の問題について,自己学習を通して検討する。 Inlicit Exploration Online Mirror Descent (IXOMD)アルゴリズムを提案する。 IXOMD は 1/sqrtT$ の NE への収束率に縛られる確率の高いモデルのないアルゴリズムである。
  論文  参考訳（メタデータ） (2021-06-11T09:51:29Z)
• Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation [92.99933928528797]
  同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。 我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。 我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
  論文  参考訳（メタデータ） (2021-02-15T09:09:16Z)
• Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent [40.99558326586079]
  非コンケーブゼロサムゲームクラスは、ゼロサムゲームを隠す機能を持つ。 我々は「隠れた」凸凹ゲームのフォン・ノイマン平衡への収束を証明する。 我々の保証は非ローカルであり、これは我々が知る限り、非コンケーブゲームにおける第一種の結果である。
  論文  参考訳（メタデータ） (2021-01-13T18:13:49Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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