論文の概要: Settling the Communication Complexity for Distributed Offline Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2202.04862v1
• Date: Thu, 10 Feb 2022 06:27:07 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-11 14:49:01.808172
• Title: Settling the Communication Complexity for Distributed Offline Reinforcement Learning
• Title（参考訳）: 分散オフライン強化学習におけるコミュニケーションの複雑さの解消
• Authors: Juliusz Krysztof Ziomek, Jun Wang, Yaodong Yang
• Abstract要約: オフライン強化学習(RL)において,複数の分散マシンが協調して問題解決を行う新たな環境について検討する。 各マシンが送信できる情報の総数(ビット数)には予算の制約がある。 文脈的包帯における値関数の予測と, エピソード的および非エピソード的MDPの双方に対して, ミニマックスリスクに対する情報理論的下限を確立する。
• 参考スコア（独自算出の注目度）: 10.315054389907031
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a novel setting in offline reinforcement learning (RL) where a number of distributed machines jointly cooperate to solve the problem but only one single round of communication is allowed and there is a budget constraint on the total number of information (in terms of bits) that each machine can send out. For value function prediction in contextual bandits, and both episodic and non-episodic MDPs, we establish information-theoretic lower bounds on the minimax risk for distributed statistical estimators; this reveals the minimum amount of communication required by any offline RL algorithms. Specifically, for contextual bandits, we show that the number of bits must scale at least as $\Omega(AC)$ to match the centralised minimax optimal rate, where $A$ is the number of actions and $C$ is the context dimension; meanwhile, we reach similar results in the MDP settings. Furthermore, we develop learning algorithms based on least-squares estimates and Monte-Carlo return estimates and provide a sharp analysis showing that they can achieve optimal risk up to logarithmic factors. Additionally, we also show that temporal difference is unable to efficiently utilise information from all available devices under the single-round communication setting due to the initial bias of this method. To our best knowledge, this paper presents the first minimax lower bounds for distributed offline RL problems.
• Abstract（参考訳）: 本研究では,複数の分散マシンが協調して問題解決を行うオフライン強化学習(rl)において,1ラウンドの通信のみを許可し,各マシンが送信可能な情報の総数(ビット単位)に予算制約を設ける新しい設定について検討する。 文脈的帯域における値関数の予測と、エピソディックおよび非エピソディックMDPの双方に対して、分散統計推定器のミニマックスリスクに関する情報理論の下限を確立し、任意のオフラインRLアルゴリズムで必要となる最小の通信量を明らかにする。 具体的には、コンテキスト・バンディットに対して、ビット数を最小化されたminimaxの最適レートに合わせるために少なくとも$\omega(ac)$でスケールしなければならないことを示し、ここで$a$はアクション数、$c$はコンテキスト次元である。 さらに,最小二乗推定とモンテカルロ回帰推定に基づく学習アルゴリズムを開発し,対数要因による最適リスクを達成することができることを示す鋭利な分析を行う。 また,本手法の初期バイアスにより,単一ラウンド通信環境下で利用可能なすべてのデバイスからの情報の有効利用が不可能であることを示す。 本稿では,分散オフラインRL問題に対する最初のミニマックス低境界について述べる。

関連論文リスト

• Minimax and Communication-Efficient Distributed Best Subset Selection with Oracle Property [0.358439716487063]
  大規模データの爆発はシングルマシンシステムの処理能力を上回っている。 分散推論への伝統的なアプローチは、高次元データセットにおいて真の疎性を達成するのにしばしば苦労する。 そこで本稿では,これらの問題に対処する2段階分散ベストサブセット選択アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-30T13:22:08Z)
• Provably Efficient CVaR RL in Low-rank MDPs [58.58570425202862]
  リスクに敏感な強化学習(RL)について検討する。 本稿では, CVaR RLにおける探索, 搾取, 表現学習の相互作用のバランスをとるための, 新たなアッパー信頼境界(UCB)ボーナス駆動アルゴリズムを提案する。 提案アルゴリズムは,各エピソードの長さが$H$,アクション空間が$A$,表現の次元が$d$であるような,エプシロン$最適CVaRのサンプル複雑性を実現する。
  論文  参考訳（メタデータ） (2023-11-20T17:44:40Z)
• Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
  本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。 疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。 後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
  論文  参考訳（メタデータ） (2023-05-30T16:05:44Z)
• The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learning [43.9624940128166]
  本稿では,分散強化学習(DistRL)の利点を,低損失領域のレンズを通して説明する。 オンラインRLでは,最大推定値を用いて信頼度を推定するDistRLアルゴリズムを提案する。 オフラインRLでは、悲観的なDistRLは、オフライン設定に新しく、かつ、悪い単一政治カバレッジに対してより堅牢な小さなPACバウンダリを享受していることが示される。
  論文  参考訳（メタデータ） (2023-05-25T04:19:43Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  エージェントがサブスペース制約を最小化するために個々のコスト関数を持つ分散最適化問題を考察する。 本稿では,エージェントが確率化量子化器を用いて推定値を圧縮する適応分散型戦略を提案し,検討する。 この分析は、量子化ノイズのいくつかの一般的な条件下では、平均二乗誤差と平均ビットレートの両方で戦略が安定であることを示している。
  論文  参考訳（メタデータ） (2022-09-16T09:38:38Z)
• Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost [48.288452411283444]
  そこでは,$N$エージェントが協調して,$d$次元の特徴を持つ線形帯域最適化問題を解く。 本稿では,LinUCBアルゴリズムの分散バッチ除去版であるDisBE-LUCBを提案する。 我々は、DisBE-LUCBの通信コストがわずか$tildemathcalO(dN)$であり、その後悔は少なくとも$tildemathcalO(dN)$であることを示す。
  論文  参考訳（メタデータ） (2022-05-26T05:56:23Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• Sparse Normal Means Estimation with Sublinear Communication [13.257075075199781]
  通信制約のある分散環境における正規平均推定の問題点を考察する。 信号対雑音比(SNR)がわずかに高くなると、$mu$のサポートはより少ない通信で正確に回復できることを示す。
  論文  参考訳（メタデータ） (2021-02-05T08:52:25Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。 通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。 分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。 分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
  論文  参考訳（メタデータ） (2020-10-02T10:41:59Z)

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

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