論文の概要: Learning in Congestion Games with Bandit Feedback

• arxiv url: http://arxiv.org/abs/2206.01880v1
• Date: Sat, 4 Jun 2022 02:32:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-07 15:27:34.228865
• Title: Learning in Congestion Games with Bandit Feedback
• Title（参考訳）: バンドフィードバックによる混雑ゲームにおける学習
• Authors: Qiwen Cui, Zhihan Xiong, Maryam Fazel, Simon S. Du
• Abstract要約: 我々は、良質な理論構造と広い実世界の応用を持つゲームのクラスである混雑ゲームについて検討する。 まず,渋滞ゲームにおける不確実性原理に直面する楽観性に基づく集中型アルゴリズムを提案する。 次に,Frank-Wolfe法とG-Optimal設計を組み合わせた分散アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 45.4542525044623
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning Nash equilibria is a central problem in multi-agent systems. In this paper, we investigate congestion games, a class of games with benign theoretical structure and broad real-world applications. We first propose a centralized algorithm based on the optimism in the face of uncertainty principle for congestion games with (semi-)bandit feedback, and obtain finite-sample guarantees. Then we propose a decentralized algorithm via a novel combination of the Frank-Wolfe method and G-optimal design. By exploiting the structure of the congestion game, we show the sample complexity of both algorithms depends only polynomially on the number of players and the number of facilities, but not the size of the action set, which can be exponentially large in terms of the number of facilities. We further define a new problem class, Markov congestion games, which allows us to model the non-stationarity in congestion games. We propose a centralized algorithm for Markov congestion games, whose sample complexity again has only polynomial dependence on all relevant problem parameters, but not the size of the action set.
• Abstract（参考訳）: nash平衡の学習はマルチエージェントシステムにおける中心的な問題である。 本稿では,理論構造が良質なゲーム群と広い実世界のアプリケーション群であるゆがみゲームについて検討する。 まず,(半)帯域フィードバックによる混雑ゲームに対する不確実性原理に直面する楽観性に基づく集中型アルゴリズムを提案し,有限サンプル保証を得る。 次に,Frank-Wolfe法とG-Optimal設計を組み合わせた分散アルゴリズムを提案する。 混雑ゲームの構造を生かして, 両アルゴリズムのサンプル複雑性は, プレイヤー数と施設数に多項式的にのみ依存するが, 動作集合のサイズには依存せず, 施設数で指数関数的に大きいことを示す。 さらに,新しい問題クラスであるマルコフ混雑ゲームを定義し,混雑ゲームにおける非定常性をモデル化する。 本稿では,マルコフ混雑ゲームに対する一元的アルゴリズムを提案する。サンプル複雑性は,すべての関連する問題パラメータに多項式依存性のみを持つが,アクションセットのサイズには依存しない。

関連論文リスト

• Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
  エージェントが以前保持していた情報を忘れたとき、不完全なリコールの下で最適な意思決定を行う。 不完全なリコールを伴う広範囲形式のゲームフレームワークにおいて、マルチプレイヤー設定における平衡を求める際の計算複雑性を解析する。
  論文  参考訳（メタデータ） (2024-06-23T00:27:28Z)
• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  我々はNuPL-JPSROという,スキルの伝達学習の恩恵を受けるニューラル集団学習アルゴリズムを導入し,ゲームの粗相関(CCE)に収束する。 本研究は, 均衡収束型集団学習を大規模かつ汎用的に実施可能であることを示す。
  論文  参考訳（メタデータ） (2024-01-10T12:56:24Z)
• The Complexity of Optimizing Atomic Congestion [14.845310803203724]
  アトミック・渋滞ゲームは、ネットワーク設計、ルーティング、アルゴリズムゲーム理論において古典的なトピックである。 非常に単純なネットワークでも問題は非常に難解なままである。 我々は、この問題の(さらに難しい)min-max変種に対する分析を拡張して結論付ける。
  論文  参考訳（メタデータ） (2023-12-15T21:31:30Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。 遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
  論文  参考訳（メタデータ） (2022-10-30T22:58:22Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• 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)
• Algorithmic Information Design in Multi-Player Games: Possibility and Limits in Singleton Congestion [10.817873935576412]
  本稿では, 負の外部性を持つゲームにおいて, 共用信号と共用信号の両方のアルゴリズム情報設計を開始する。 公開信号とプライベート信号の両方に対して、資源の数が一定である場合に最適な情報設計を効率的に計算できることが示される。
  論文  参考訳（メタデータ） (2021-09-25T22:02:32Z)
• Signatured Deep Fictitious Play for Mean Field Games with Common Noise [0.0]
  平均場ゲーム(MFG)を共通のノイズで解くための既存のディープラーニング手法は、サンプリングされた共通のノイズパスを固定し、対応するMFGを解く。 そこで我々は,固定されていない共通雑音設定を用いてネストループ構造を回避できる新しい単一ループアルゴリズムを提案する。 提案アルゴリズムは,ニューラルネットワークのさらなるトレーニングを行うことなく,共通不確実性の変化が平均場平衡に与える影響を正確に把握することができる。
  論文  参考訳（メタデータ） (2021-06-06T23:09:46Z)

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

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