論文の概要: Scheduling Servers with Stochastic Bilinear Rewards

• arxiv url: http://arxiv.org/abs/2112.06362v1
• Date: Mon, 13 Dec 2021 00:37:20 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-14 19:30:53.635460
• Title: Scheduling Servers with Stochastic Bilinear Rewards
• Title（参考訳）: 確率的バイリニア報酬を用いたスケジューリングサーバ
• Authors: Jung-hun Kim and Milan Vojnovic
• Abstract要約: 本稿では,ジョブやサーバを表す特徴ベクトルの双線形モデルに従って,ジョブサーバの割り当てを報奨するマルチクラスマルチサーバキューシステムについて検討する。 本稿では,サーバへのジョブの動的割り当てとともに線形帯域幅アルゴリズムを用いたスケジューリングアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 3.5408022972081685
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we study a multi-class, multi-server queueing system with stochastic rewards of job-server assignments following a bilinear model in feature vectors representing jobs and servers. Our goal is regret minimization against an oracle policy that has a complete information about system parameters. We propose a scheduling algorithm that uses a linear bandit algorithm along with dynamic allocation of jobs to servers. For the baseline setting, in which mean job service times are identical for all jobs, we show that our algorithm has a sub-linear regret, as well as a sub-linear bound on the mean queue length, in the horizon time. We further show that similar bounds hold under more general assumptions, allowing for non-identical mean job service times for different job classes and a time-varying set of server classes. We also show that better regret and mean queue length bounds can be guaranteed by an algorithm having access to traffic intensities of job classes. We present results of numerical experiments demonstrating how regret and mean queue length of our algorithms depend on various system parameters and compare their performance against a previously proposed algorithm using synthetic randomly generated data and a real-world cluster computing data trace.
• Abstract（参考訳）: 本稿では,ジョブとサーバを表わす特徴ベクトルの双線形モデルに従って,ジョブサーバ割り当ての確率的報奨を伴うマルチクラスマルチサーバキューシステムについて検討する。 私たちの目標は、システムパラメータに関する完全な情報を持つoracleポリシーに対する後悔の最小化です。 本稿では,サーバへのジョブの動的割り当てとともに線形帯域幅アルゴリズムを用いたスケジューリングアルゴリズムを提案する。 平均ジョブサービス時間が全ジョブに対して同一であるベースライン設定に対して,本アルゴリズムでは,平均待ち行列長に対して水平時間内にバウンドするサブリニアリットと,サブリニアリットを持つことを示す。 さらに、同様の境界がより一般的な仮定の下で保持されていることも示しており、異なるジョブクラスやサーバクラスの時間的変動に対して、非identical平均ジョブサービス時間を可能にする。 また,ジョブクラスのトラフィック強度にアルゴリズムがアクセスすることで,後悔や平均キュー長の境界が保証されることを示した。 本稿では,アルゴリズムの残差と平均待ち時間長が様々なシステムパラメータに依存することを示す数値実験の結果を,合成ランダムに生成されたデータと実世界のクラスタ計算データトレースを用いて提案したアルゴリズムと比較した。

関連論文リスト

• Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systems [21.944723061337267]
  我々は、中央キューに到着するジョブをヘテロジニアスサーバのシステムに効率的にルーティングする問題を考察する。 均質なシステムとは異なり、キュー長が一定のしきい値を超えた場合、ジョブを遅いサーバにルーティングするしきい値ポリシーは、ワンファストワンスローの2サーバシステムに最適であることが知られている。 本稿では,低次元ソフトしきい値パラメータ化を用いた効率的なポリシー勾配に基づくアルゴリズムであるACHQを提案する。
  論文  参考訳（メタデータ） (2024-02-02T05:22:41Z)
• Online Optimization for Randomized Network Resource Allocation with Long-Term Constraints [0.610240618821149]
  簡単な通信網における最適オンラインリソース予約問題について検討する。 そこで我々は,オンラインサドルポイントアルゴリズムを提案し,関連するK-ベンチマークの後悔に対する上限を提示する。
  論文  参考訳（メタデータ） (2023-05-24T20:47:17Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Optimal Admission Control for Multiclass Queues with Time-Varying Arrival Rates via State Abstraction [16.99621896314678]
  我々は、意思決定者がランダムに到着したタスクを受け入れ、拒否する必要があるという、新しいキュー問題を考える。 目的は、処理されたタスクの総価格が有限の地平線上で最大になるように、どのタスクを受け入れるかを決定することである。 最適値関数は特定の構造を持ち、ハイブリッドMDPを正確に解くことができることを示す。
  論文  参考訳（メタデータ） (2022-03-14T12:38:13Z)
• Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty [87.81197574939355]
  最適化問題と学習問題の両方について検討する。 我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。 より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
  論文  参考訳（メタデータ） (2022-01-18T17:24:20Z)
• Learning to Schedule [3.5408022972081685]
  本稿では,ジョブが生み出す累積保持コストを最小限に抑えるための学習・スケジューリングアルゴリズムを提案する。 各タイムスロットにおいて、サーバはシステムに残されているジョブのランダム保持コストを受信しながらジョブを処理できる。
  論文  参考訳（メタデータ） (2021-05-28T08:04:06Z)
• 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)
• Policy Gradient for Continuing Tasks in Non-stationary Markov Decision Processes [112.38662246621969]
  強化学習は、マルコフ決定プロセスにおいて期待される累積報酬を最大化するポリシーを見つけることの問題を考える。 我々は、ポリシーを更新するために上昇方向として使用する値関数の偏りのないナビゲーション勾配を計算する。 ポリシー勾配型アルゴリズムの大きな欠点は、定常性の仮定が課せられない限り、それらがエピソジックなタスクに限定されていることである。
  論文  参考訳（メタデータ） (2020-10-16T15:15:42Z)
• An Online Algorithm for Computation Offloading in Non-Stationary Environments [12.843328612860244]
  計算タスクをアウトソーシングするユーザ機器に複数のサーバが利用可能なタスクオフロードシナリオにおいて,レイテンシの問題を考慮する。 無線リンクの時間的動的性質と計算資源の可用性を考慮し、サーバ選択をマルチアームバンディット(MAB)問題としてモデル化する。 本研究では,不確実性に直面した楽観主義の原理に基づく新しいオンライン学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T07:00:47Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)

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

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