論文の概要: Taming the Exponential Action Set: Sublinear Regret and Fast Convergence
to Nash Equilibrium in Online Congestion Games
- arxiv url: http://arxiv.org/abs/2306.13673v1
- Date: Mon, 19 Jun 2023 03:03:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-02 13:47:30.260602
- Title: Taming the Exponential Action Set: Sublinear Regret and Fast Convergence
to Nash Equilibrium in Online Congestion Games
- Title（参考訳）: 指数関数的アクションセットの改ざん:オンライン混雑ゲームにおけるサブリニアな後悔とナッシュ均衡への高速収束
- Authors: Jing Dong, Jingyu Wu, Siwei Wang, Baoxiang Wang, Wei Chen
- Abstract要約: そこでは,エージェントが繰り返しゲームに参加し,ランダムにフィードバックを観察する,混雑ゲームのオンライン定式化について検討する。
古典指数重み法を適用した分散アルゴリズムであるCongestEXPを提案する。
我々は、CongestEXPが各プレイヤーに対して$O(kFsqrtT)$という後悔の上限に達していることを示す。
- 参考スコア（独自算出の注目度）: 29.384748500302678
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The congestion game is a powerful model that encompasses a range of
engineering systems such as traffic networks and resource allocation. It
describes the behavior of a group of agents who share a common set of $F$
facilities and take actions as subsets with $k$ facilities. In this work, we
study the online formulation of congestion games, where agents participate in
the game repeatedly and observe feedback with randomness. We propose
CongestEXP, a decentralized algorithm that applies the classic exponential
weights method. By maintaining weights on the facility level, the regret bound
of CongestEXP avoids the exponential dependence on the size of possible
facility sets, i.e., $\binom{F}{k} \approx F^k$, and scales only linearly with
$F$. Specifically, we show that CongestEXP attains a regret upper bound of
$O(kF\sqrt{T})$ for every individual player, where $T$ is the time horizon. On
the other hand, exploiting the exponential growth of weights enables CongestEXP
to achieve a fast convergence rate. If a strict Nash equilibrium exists, we
show that CongestEXP can converge to the strict Nash policy almost
exponentially fast in $O(F\exp(-t^{1-\alpha}))$, where $t$ is the number of
iterations and $\alpha \in (1/2, 1)$.
- Abstract（参考訳）: 渋滞ゲームは、トラフィックネットワークやリソース割り当てといった幅広いエンジニアリングシステムを含む強力なモデルである。
これは、$F$施設の共通セットを共有し、$k$施設のサブセットとしてアクションを行うエージェントのグループの振る舞いを記述する。
そこで本研究では,エージェントが繰り返しゲームに参加し,ランダムにフィードバックを観察する,混雑ゲームのオンライン定式化について検討する。
古典的指数重み法を適用した分散アルゴリズムであるcongestexpを提案する。
施設レベルでの重みを維持することで、コンジェストEXPの後悔境界は、可能な施設集合、すなわち$\binom{F}{k} \approx F^k$への指数的依存を回避し、$F$でのみ線形にスケールする。
具体的には、CongestEXPが各プレイヤーに対して$O(kF\sqrt{T})$という後悔の上限に達していることを示す。
一方、重みの指数的成長を利用すると、congestexpは高速な収束率を達成できる。
厳密なナッシュ均衡が存在するなら、CongestEXP が $O(F\exp(-t^{1-\alpha})$ においてほぼ指数関数的に高速なナッシュポリシーに収束できることを示し、$t$ は反復数であり、$\alpha \in (1/2, 1)$ である。
関連論文リスト
- Games played by Exponential Weights Algorithms [0.0]
各プレイヤーは、初期混合動作と固定学習率を特徴とする指数重み付けアルゴリズムを使用する。
厳密なナッシュ均衡が存在するときは常に、次の段階で厳密なナッシュ均衡を行う確率は、ほぼ確実に0または1に収束することを示す。
論文 参考訳（メタデータ） (2024-07-09T08:49:51Z) - MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Games [5.778024594615575]
本稿では,シーケンシャルゲームのナッシュ平衡計算のためのオンライン平均場強化学習アルゴリズムを提案する。
MFOMLは、ナッシュ平衡を実証的に解くための、最初の完全近似マルチエージェント強化学習アルゴリズムである。
副生成物として、モノトーン平均場ゲームの近似計算のための最初のトラクタブル大域収束計算も得られる。
論文 参考訳（メタデータ） (2024-05-01T02:19:31Z) - Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with
General Utilities [12.104551746465932]
安全マルチエージェント強化学習について検討し、エージェントはそれぞれの安全制約を満たしつつ、局所的な目的の総和をまとめて最大化しようとする。
我々のアルゴリズムは、$mathcalOleft(T-2/3right)$のレートで1次定常点(FOSP)に収束する。
サンプルベースの設定では、高い確率で、我々のアルゴリズムは、$epsilon$-FOSPを達成するために$widetildemathcalOleft(epsilon-3.5right)$サンプルが必要です。
論文 参考訳（メタデータ） (2023-05-27T20:08:35Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳（メタデータ） (2023-01-19T11:36:50Z) - The Sample Complexity of Online Contract Design [120.9833763323407]
オンライン環境での隠れアクションの主エージェント問題について検討する。
各ラウンドにおいて、主席は、各結果に基づいてエージェントへの支払いを指定する契約を投稿する。
エージェントは、自身のユーティリティを最大化する戦略的な行動選択を行うが、プリンシパルによって直接観察できない。
論文 参考訳（メタデータ） (2022-11-10T17:59:42Z) - Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a
Generative Model [50.38446482252857]
2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。
我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。
我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
論文 参考訳（メタデータ） (2022-08-22T17:24:55Z) - Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。
我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。
先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
論文 参考訳（メタデータ） (2022-06-17T12:58:58Z) - Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。
我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
論文 参考訳（メタデータ） (2022-03-29T15:27:13Z) - Learning Stationary Nash Equilibrium Policies in $n$-Player Stochastic
Games with Independent Chains [2.132096006921048]
我々は、プレイヤーがペイオフ機能を介して結合されている間、内部の状態/行動空間を持つ、$n$プレイヤゲームのクラスを考える。
このクラスのゲームに対して、報奨関数を仮定せずに定常ナッシュ(NE)ポリシーを見つけることは、対話可能であることを示す。
我々は,2重平均化と2重ミラー降下に基づくアルゴリズムを開発し,これを$epsilon$-NEポリシーの集合に収束させる。
論文 参考訳（メタデータ） (2022-01-28T16:27:21Z) - When Can We Learn General-Sum Markov Games with a Large Number of
Players Sample-Efficiently? [10.397170312149067]
本稿では,m$-player General-sum Markovゲームの設定において,学習目標がより優れたサンプル複雑性を許容するものについて検討する。
まず,$epsilon$-Coarse Correlated Equilibrium (CCE)を$widetildemathcalO(H5Smax_ile m A_i / epsilon2)$ episodesで学習するアルゴリズムを設計する。
第二に、マルコフポテンシャルゲームの重要な特別な場合を考え、$widet内で$epsilon$-approximate Nash平衡を学ぶアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-10-08T15:06:22Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。