論文の概要: Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agents
- arxiv url: http://arxiv.org/abs/2410.22908v1
- Date: Wed, 30 Oct 2024 11:05:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-31 14:28:48.416652
- Title: Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agents
- Title（参考訳）: フェデレートUCBVI:不均一剤によるコミュニケーション効率の良いフェデレーションレギュレット最小化
- Authors: Safwan Labbi, Daniil Tiapkin, Lorenzo Mancini, Paul Mangold, Eric Moulines,
- Abstract要約: We present the Federated upper Confidence bound Value Iteration algorithm (textttFed-UCBVI$)
textttFed-UCBVI$ の後悔は $tildemathcalO(sqrtH3 |mathcalS| |mathcalA| T / M)$ としてスケールすることを証明する。
既存の強化学習アプローチとは異なり、$textttFed-UCBVI$の通信複雑性は、その数によってわずかに増加する。
- 参考スコア（独自算出の注目度）: 13.391318494060975
- License:
- Abstract: In this paper, we present the Federated Upper Confidence Bound Value Iteration algorithm ($\texttt{Fed-UCBVI}$), a novel extension of the $\texttt{UCBVI}$ algorithm (Azar et al., 2017) tailored for the federated learning framework. We prove that the regret of $\texttt{Fed-UCBVI}$ scales as $\tilde{\mathcal{O}}(\sqrt{H^3 |\mathcal{S}| |\mathcal{A}| T / M})$, with a small additional term due to heterogeneity, where $|\mathcal{S}|$ is the number of states, $|\mathcal{A}|$ is the number of actions, $H$ is the episode length, $M$ is the number of agents, and $T$ is the number of episodes. Notably, in the single-agent setting, this upper bound matches the minimax lower bound up to polylogarithmic factors, while in the multi-agent scenario, $\texttt{Fed-UCBVI}$ has linear speed-up. To conduct our analysis, we introduce a new measure of heterogeneity, which may hold independent theoretical interest. Furthermore, we show that, unlike existing federated reinforcement learning approaches, $\texttt{Fed-UCBVI}$'s communication complexity only marginally increases with the number of agents.
- Abstract（参考訳）: 本稿では、フェデレートされた学習フレームワークに適した$\texttt{Fed-UCBVI}$アルゴリズム(Azar et al , 2017)の新たな拡張であるフェデレートされたアッパー信頼境界値反復アルゴリズム(\textt{Fed-UCBVI}$)を提案する。
我々は、$\texttt{Fed-UCBVI}$の後悔が$\tilde{\mathcal{O}}(\sqrt{H^3 |\mathcal{S}| |\mathcal{A}| T / M})$であることを示す。
特にシングルエージェント設定では、この上限は最小値の下限をポリ対数的因子に一致させるが、マルチエージェントシナリオでは$\texttt{Fed-UCBVI}$は線形スピードアップを持つ。
解析を行うために、独立理論的な関心を抱く可能性のある不均一性の新しい尺度を導入する。
さらに,既存の強化学習手法とは異なり,$\texttt{Fed-UCBVI}$の通信複雑性はエージェント数によってわずかに増加する。
関連論文リスト
- Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
近似の性能をMonge-Kantorovich $p$-costで定量化する。
次に、ソボレフ予算の制約の下で、機能的$mathscrJ_p(f)$を最小化するものとして問題を再構築する。
論文 参考訳（メタデータ） (2024-09-25T01:30:16Z) - Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - On the Minimax Regret for Online Learning with Feedback Graphs [5.721380617450645]
強く観察可能な無向フィードバックグラフを用いて,オンライン学習を後悔する上で,上層と下層の境界を改善した。
改良された上界$mathcalObigl(sqrtalpha T(ln K)/(lnalpha)bigr)$ hold for any $alpha$ and the lower bounds for bandits and experts。
論文 参考訳（メタデータ） (2023-05-24T17:40:57Z) - Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
論文 参考訳（メタデータ） (2023-02-27T16:34:21Z) - Layered State Discovery for Incremental Autonomous Exploration [106.37656068276901]
Layered Autonomous Exploration (LAE) は、$tildemathcalO(LSrightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightar row_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)のサンプル複雑性を達成するAXの新しいアルゴリズムである。
論文 参考訳（メタデータ） (2023-02-07T22:58:12Z) - A Simple and Provably Efficient Algorithm for Asynchronous Federated
Contextual Linear Bandits [77.09836892653176]
我々は,M$エージェントが相互に協力して,中央サーバの助けを借りて,グローバルなコンテキスト線形バンドイット問題を解決するためのフェデレーション付きコンテキスト線形バンドイットについて検討した。
すべてのエージェントが独立して動作し、ひとつのエージェントとサーバ間の通信が他のエージェントの通信をトリガーしない非同期設定を考える。
texttFedLinUCBの後悔は$tildeO(dsqrtsum_m=1M T_m)$で、通信の複雑さは$tildeO(dM)であることを示す。
論文 参考訳（メタデータ） (2022-07-07T06:16:19Z) - On Convergence of Gradient Descent Ascent: A Tight Local Analysis [30.206431787797776]
GDA(Gradient Descent Ascent)法は、GAN(Generative Adversarial Network)における最小最適化のためのアルゴリズムである。
段差比eta_mathbfx$/eta_mathbfx=Theta(kappa2)によるGDAの収束を証明する。
我々はさらに収束保証を GDA および Extra-gradient Method (EG) に拡張する。
論文 参考訳（メタデータ） (2022-07-03T05:04:46Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。