論文の概要: Optimal No-Regret Learning in General Games: Bounded Regret with Unbounded Step-Sizes via Clairvoyant MWU

• arxiv url: http://arxiv.org/abs/2111.14737v1
• Date: Mon, 29 Nov 2021 17:42:24 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-30 16:29:36.662123
• Title: Optimal No-Regret Learning in General Games: Bounded Regret with Unbounded Step-Sizes via Clairvoyant MWU
• Title（参考訳）: 一般ゲームにおける最適非回帰学習:クラリボイアンMWUによる非有界ステップサイズ境界
• Authors: Georgios Piliouras, Ryann Sim, Stratis Skoulakis
• Abstract要約: 一定のステップサイズで絶え間なく後悔するアルゴリズムを提案する。 ステップサイズが大きくなるにつれて,アルゴリズムの累積後悔は線形的に減少する。
• 参考スコア（独自算出の注目度）: 27.438327151960657
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we solve the problem of no-regret learning in general games. Specifically, we provide a simple and practical algorithm that achieves constant regret with fixed step-sizes. The cumulative regret of our algorithm provably decreases linearly as the step-size increases. Our findings depart from the prevailing paradigm that vanishing step-sizes are a prerequisite for low regret as championed by all state-of-the-art methods to date. We shift away from this paradigm by defining a novel algorithm that we call Clairvoyant Multiplicative Weights Updates (CMWU). CMWU is Multiplicative Weights Updates (MWU) equipped with a mental model (jointly shared across all agents) about the state of the system in its next period. Each agent records its mixed strategy, i.e., its belief about what it expects to play in the next period, in this shared mental model which is internally updated using MWU without any changes to the real-world behavior up until it equilibrates, thus marking its consistency with the next day's real-world outcome. It is then and only then that agents take action in the real-world, effectively doing so with the ``full knowledge" of the state of the system on the next day, i.e., they are clairvoyant. CMWU effectively acts as MWU with one day look-ahead, achieving bounded regret. At a technical level, we establish that self-consistent mental models exist for any choice of step-sizes and provide bounds on the step-size under which their uniqueness and linear-time computation are guaranteed via contraction mapping arguments. Our arguments extend well beyond normal-form games with little effort.
• Abstract（参考訳）: 本稿では,一般ゲームにおける非regret学習の課題を解決する。 具体的には,固定ステップサイズで一定の後悔を達成する,単純かつ実用的なアルゴリズムを提案する。 ステップサイズの増加に伴い,アルゴリズムの累積後悔は線形的に減少する。 我々の発見は、現在まですべての最先端の手法が支持しているように、ステップサイズを消滅させることが、低い後悔の前提条件である、という一般的なパラダイムから逸脱している。 我々は、Clairvoyant Multiplicative Weights Updates (CMWU)と呼ばれる新しいアルゴリズムを定義することで、このパラダイムから脱却する。 CMWUはMultiplelicative Weights Updates (MWU)であり、次の期間におけるシステムの状態に関するメンタルモデル(すべてのエージェント間で共同で共有される)を備えている。 それぞれのエージェントは、その混合戦略、すなわち、次の期間に何がプレーするかという信念を、実際の行動が均衡するまで変化することなくMWUを用いて内部的に更新されるこの共有精神モデルに記録し、次の日の現実的な結果と整合性を示す。 その時、エージェントが現実世界で行動し、翌日のシステムの状態の「完全な知識」を効果的に行うのは、その時である。 CMWUは事実上MWUとして機能し、一日の視線で後悔の種となる。 技術的レベルでは、ステップサイズの選択には自己整合性精神モデルが存在し、その特異性と線形時間計算が契約写像の引数によって保証されるステップサイズに境界が与えられる。 我々の議論は、ほとんど努力することなく、通常の形式のゲームにかなり及ばない。

関連論文リスト

• Lancet: Accelerating Mixture-of-Experts Training via Whole Graph Computation-Communication Overlapping [14.435637320909663]
  MoEテクニックは、DNNモデルパラメータのサイズを拡大する上で重要な役割を果たす。 既存の手法は、全てを専門家の計算でオーバーラップすることでこの問題を緩和しようとする。 本研究では,より広いトレーニンググラフレベルでのオーバーラップを考慮し,この課題の範囲を広げる。 コンパイラをベースとした最適化により,MoEモデルトレーニングを自動的に強化するシステムであるLancetにこれらの手法を実装した。
  論文  参考訳（メタデータ） (2024-04-30T10:17:21Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Regret Minimization and Convergence to Equilibria in General-sum Markov Games [57.568118148036376]
  汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。 我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
  論文  参考訳（メタデータ） (2022-07-28T16:27:59Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Consensus Multiplicative Weights Update: Learning to Learn using Projector-based Game Signatures [8.08640000394814]
  2つ目のアルゴリズムである textitConsensus MWU を導入し、局所収束を証明し、OMWU よりも高速で堅牢な収束を経験的に示す。 提案アルゴリズムは,新たな対象であるテクスチシプレックス・ヘシアンの重要性と,ゲームとベクトルの(固有)空間との相互作用を示す。
  論文  参考訳（メタデータ） (2021-06-04T17:26:54Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。 私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。 エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
  論文  参考訳（メタデータ） (2021-03-08T04:03:24Z)
• AdamP: Slowing Down the Slowdown for Momentum Optimizers on Scale-invariant Weights [53.8489656709356]
  正規化技術は現代の深層学習の恩恵である。 しかし、運動量を導入することで、スケール不変の重みに対する効果的なステップサイズが急速に小さくなることがしばしば見過ごされる。 本稿では,この2つの材料の組み合わせが,有効ステップサイズと準最適モデル性能の早期劣化につながることを検証した。
  論文  参考訳（メタデータ） (2020-06-15T08:35:15Z)
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
  本稿では,ゼロサムにおける乗算重み更新 (MWU) と最適乗算重み更新 (OMWU) のボリューム解析と協調ゲームについて述べる。 我々は、OMWUが、その既知の収束挙動の代替的な理解を提供するために、ボリュームを契約していることを示します。 我々はまた、コーディネートゲームを調べる際に役割が逆になるという意味で、自由ランチ型の定理も証明する: OMWU は指数関数的に高速に体積を拡大するが、MWU は契約する。
  論文  参考訳（メタデータ） (2020-05-28T13:47:09Z)

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

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