論文の概要: Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systems

• arxiv url: http://arxiv.org/abs/2402.01147v1
• Date: Fri, 2 Feb 2024 05:22:41 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-05 16:51:49.033795
• Title: Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systems
• Title（参考訳）: 不均一なキューシステムにおけるルーティングジョブの効率的な強化学習
• Authors: Neharika Jali, Guannan Qu, Weina Wang, Gauri Joshi
• Abstract要約: 我々は、中央キューに到着するジョブをヘテロジニアスサーバのシステムに効率的にルーティングする問題を考察する。 均質なシステムとは異なり、キュー長が一定のしきい値を超えた場合、ジョブを遅いサーバにルーティングするしきい値ポリシーは、ワンファストワンスローの2サーバシステムに最適であることが知られている。 本稿では,低次元ソフトしきい値パラメータ化を用いた効率的なポリシー勾配に基づくアルゴリズムであるACHQを提案する。
• 参考スコア（独自算出の注目度）: 23.973033446355167
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of efficiently routing jobs that arrive into a central queue to a system of heterogeneous servers. Unlike homogeneous systems, a threshold policy, that routes jobs to the slow server(s) when the queue length exceeds a certain threshold, is known to be optimal for the one-fast-one-slow two-server system. But an optimal policy for the multi-server system is unknown and non-trivial to find. While Reinforcement Learning (RL) has been recognized to have great potential for learning policies in such cases, our problem has an exponentially large state space size, rendering standard RL inefficient. In this work, we propose ACHQ, an efficient policy gradient based algorithm with a low dimensional soft threshold policy parameterization that leverages the underlying queueing structure. We provide stationary-point convergence guarantees for the general case and despite the low-dimensional parameterization prove that ACHQ converges to an approximate global optimum for the special case of two servers. Simulations demonstrate an improvement in expected response time of up to ~30% over the greedy policy that routes to the fastest available server.
• Abstract（参考訳）: 我々は、中央キューに到着するジョブを異種サーバシステムに効率的にルーティングする問題を考察する。 均質なシステムとは異なり、キューの長さが一定のしきい値を超えると遅いサーバにジョブをルーティングするしきい値ポリシーは、1つの高速な2つのサーバシステムにとって最適であることが知られている。 しかし、マルチサーバシステムに最適なポリシーは未知であり、見つからない。 強化学習(Reinforcement Learning, RL)はそのような場合, 学習方針に大きな可能性があることが認識されているが, この問題は指数関数的に大きな状態空間サイズを持ち, 標準のRLを非効率にする。 本研究では,待ち行列構造を利用した低次元ソフトしきい値ポリシパラメータ化を用いた,効率的なポリシー勾配に基づくアルゴリズムである achq を提案する。 一般の場合に対して定常点収束保証を提供し、低次元パラメータ化にもかかわらず、ACHQは2つのサーバの特別の場合の近似大域最適化に収束することを示す。 シミュレーションは、最も速く利用可能なサーバにルーティングされる欲望ポリシーよりも、最大30%程度の期待応答時間の改善を示している。

関連論文リスト

• FusionLLM: A Decentralized LLM Training System on Geo-distributed GPUs with Adaptive Compression [55.992528247880685]
  分散トレーニングは、システム設計と効率に関する重要な課題に直面します。 大規模深層ニューラルネットワーク(DNN)のトレーニング用に設計・実装された分散トレーニングシステムFusionLLMを提案する。 本システムと手法は,収束性を確保しつつ,ベースライン法と比較して1.45～9.39倍の高速化を実現可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-16T16:13:19Z)
• Queueing Matching Bandits with Preference Feedback [10.988222071035198]
  我々は、一方のN$キューと他方のK$サーバからなるマルチクラス非対称キューシステムについて検討する。 各ジョブサーバ割り当てのサービスレートは未知であり、機能ベースのMNL(Multi-nomial Logit)関数によってモデル化される。 我々は,UCBとトンプソンサンプリングに基づくアルゴリズムを提案する。このアルゴリズムは,待ち時間の平均値が$O(minN,K/epsilon)$に制限されたシステム安定性を実現する。
  論文  参考訳（メタデータ） (2024-10-14T02:29:06Z)
• Twin Sorting Dynamic Programming Assisted User Association and Wireless Bandwidth Allocation for Hierarchical Federated Learning [7.274131715810928]
  階層型フェデレーション学習システムにおけるユーザアソシエーションと無線帯域幅割り当てについて検討する。 エッジサーバが2つある場合に,グローバルな最適解を求めるTSDPアルゴリズムを設計する。 さらに,3つ以上のエッジサーバが存在する場合に,ユーザアソシエーションのためのTSDP支援アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-17T02:29:32Z)
• Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity [85.92481138826949]
  我々は,従来の集中型手法の時間的複雑さを確実に改善する新しい手法であるShadowheart SGDを開発した。 また、サーバからワーカーへのブロードキャストが無視できない双方向設定も検討し、対応する方法を開発した。
  論文  参考訳（メタデータ） (2024-02-07T12:15:56Z)
• Client Orchestration and Cost-Efficient Joint Optimization for NOMA-Enabled Hierarchical Federated Learning [55.49099125128281]
  半同期クラウドモデルアグリゲーションの下で非直交多重アクセス(NOMA)を実現するHFLシステムを提案する。 提案手法は,HFLの性能改善と総コスト削減に関するベンチマークよりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-11-03T13:34:44Z)
• Learning While Scheduling in Multi-Server Systems with Unknown Statistics: MaxWeight with Discounted UCB [18.898514227870926]
  本稿では、複数のサーバと複数のタイプのジョブを持つマルチサーバシステムについて考察する。 目標は、処理時間の統計を知ることなく、サーバ上のジョブをスケジュールすることだ。 我々は,MaxWeightスケジューリングポリシと割引された高信頼度境界(UCB)を組み合わせることで,統計を同時に学習し,ジョブをサーバにスケジュールするアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-09-02T15:37:02Z)
• Scheduling Servers with Stochastic Bilinear Rewards [7.519872646378837]
  システム最適化問題は、マルチクラス、マルチサーバキューシステムスケジューリングで発生する。 本稿では,報酬の限界コストを付加した重み付き比例フェアアロケーション基準に基づくスケジューリングアルゴリズムを提案する。 我々のアルゴリズムは,時間的地平線に関して,サブ線形後悔とサブ線形平均保持コスト(および待ち時間境界)を考慮し,待ち行列システムの安定性を保証する。
  論文  参考訳（メタデータ） (2021-12-13T00:37:20Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。 我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
  論文  参考訳（メタデータ） (2021-05-01T10:18:34Z)
• Tailored Learning-Based Scheduling for Kubernetes-Oriented Edge-Cloud System [54.588242387136376]
  エッジクラウドシステムのための学習ベースのスケジューリングフレームワークkaisを紹介する。 まず,分散した要求ディスパッチに対応するために,協調型マルチエージェントアクタ-クリティックアルゴリズムを設計する。 次に,多種多様なシステムスケールと構造について,グラフニューラルネットワークを用いてシステム状態情報を埋め込む。 第3に、リクエストディスパッチとサービスオーケストレーションを調和させる2段階のスケジューリングメカニズムを採用します。
  論文  参考訳（メタデータ） (2021-01-17T03:45:25Z)
• RL-QN: A Reinforcement Learning Framework for Optimal Control of Queueing Systems [8.611328447624677]
  モデルベース強化学習(RL)を用いて、待ち行列ネットワークの最適制御ポリシーを学習する。 しかし、従来のRLのアプローチでは、ネットワーク制御問題の非有界状態空間は扱えない。 我々は、状態空間の有限部分集合にモデルベースのRL法を適用するReinforcement Learning for Queueing Networks (RL-QN)と呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-14T22:12:27Z)
• Joint Parameter-and-Bandwidth Allocation for Improving the Efficiency of Partitioned Edge Learning [73.82875010696849]
  機械学習アルゴリズムは、人工知能(AI)モデルをトレーニングするために、ネットワークエッジにデプロイされる。 本稿では,パラメータ(計算負荷)割り当てと帯域幅割り当ての新しい共同設計に焦点を当てる。
  論文  参考訳（メタデータ） (2020-03-10T05:52:15Z)

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

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