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

• arxiv url: http://arxiv.org/abs/2407.00575v1
• Date: Sun, 30 Jun 2024 03:33:42 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-04 02:36:46.461275
• Title: Learning to Control Unknown Strongly Monotone Games
• Title（参考訳）: 未知の強いモノトーンゲームを制御するための学習
• Authors: Siddharth Chandak, Ilai Bistritz, Nicholas Bambos,
• Abstract要約: 制御された係数をオンラインで調整し,線形制約を満たすためにゲームのNEをシフトする簡単なアルゴリズムを提案する。 我々は,2つの時間スケール近似に基づくアルゴリズムが,目的とする線形制約を満たすNEの集合に対する確率1との収束を保証することを証明した。 本稿では,NEにおけるグローバル2次コストの最適化と資源配分ゲームにおけるロードバランシングに,我々の手法を適用する方法を示す。
• 参考スコア（独自算出の注目度）: 16.327788209492805
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Consider $N$ players each with a $d$-dimensional action set. Each of the players' utility functions includes their 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 if each player runs gradient descent, the dynamics converge to a unique Nash equilibrium (NE). The NE is typically inefficient in terms of global performance. The resulting global performance of the system can be improved by imposing $K$-dimensional 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 their action sets. Obtaining this game structure information is infeasible in a large-scale network and violates the users' privacy. To overcome this, we propose a simple algorithm that learns to shift the NE of the game 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, which is based on two time-scale stochastic approximation, guarantees convergence with probability 1 to the set of NE that meet target linear constraints. We then provide a mean square convergence rate of $O(t^{-1/4})$ for our algorithm. This is the first such bound for two time-scale stochastic approximation where the slower time-scale is a fixed point iteration with a non-expansive mapping. We demonstrate how our scheme can be applied to optimizing a global quadratic cost at NE and load balancing in resource allocation games. We provide simulations of our algorithm for these scenarios.
• Abstract（参考訳）: それぞれ$d$-dimensionalアクションセットを持つ$N$プレーヤーを考えてみましょう。 プレイヤーの効用関数はそれぞれ、報酬関数と各次元に対する線形項を含み、管理者によって制御される係数を持つ。 ゲームは強い単調であると仮定するので、各プレイヤーが勾配降下を実行すると、ダイナミクスはユニークなナッシュ均衡(NE)に収束する。 NEは通常、グローバルパフォーマンスの点で非効率である。 システム全体の性能は、NEに$K$次元の線形制約を課すことで改善することができる。 したがって、我々はマネージャが NE に所望の制約を課す制御係数を選択することを望んでいます。 しかし、プレイヤーの報酬関数とアクションセットを知る必要がある。 このゲーム構造情報の取得は、大規模ネットワークでは不可能であり、ユーザのプライバシを侵害する。 そこで本研究では,制御された係数をオンラインに調整することで,ゲームのNEを線形制約に合わせるための簡単なアルゴリズムを提案する。 我々のアルゴリズムは線形制約違反をフィードバックとして要求するだけであり、報酬関数やアクションセットを知る必要はない。 我々は,2つの時間スケール確率近似に基づくアルゴリズムが,対象線形制約を満たすNEの集合への確率1との収束を保証することを証明した。 次に、アルゴリズムに対して平均2乗収束率を$O(t^{-1/4})$とする。 これは、2つの時間スケール確率近似に対する最初の境界であり、遅い時間スケールは非拡張写像を持つ固定点反復である。 本稿では,NEにおけるグローバル2次コストの最適化と資源配分ゲームにおけるロードバランシングに,我々の手法を適用する方法を示す。 これらのシナリオに対するアルゴリズムのシミュレーションを提供する。

関連論文リスト

• 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)
• 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)
• Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
  本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。 分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
  論文  参考訳（メタデータ） (2021-07-30T15:25:13Z)
• 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)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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