論文の概要: Queue Scheduling with Adversarial Bandit Learning
- arxiv url: http://arxiv.org/abs/2303.01745v1
- Date: Fri, 3 Mar 2023 07:17:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-06 16:03:05.259057
- Title: Queue Scheduling with Adversarial Bandit Learning
- Title(参考訳): 逆帯域学習によるキュースケジューリング
- Authors: Jiatai Huang, Leana Golubchik, Longbo Huang
- Abstract要約: K$キューからなるワンホップ単一サーバキューシステムについて検討する。
我々のスケジューリング手法は,逆帯域学習とリアプノフドリフト最小化の革新的な組み合わせに基づいている。
ランダム化ポリシーのいくつかの(おそらく未知の)シーケンスで安定化可能なシステムを安定化できる2つの新しいアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 20.606599586119835
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: In this paper, we study scheduling of a queueing system with zero knowledge
of instantaneous network conditions. We consider a one-hop single-server
queueing system consisting of $K$ queues, each with time-varying and
non-stationary arrival and service rates. Our scheduling approach builds on an
innovative combination of adversarial bandit learning and Lyapunov drift
minimization, without knowledge of the instantaneous network state (the arrival
and service rates) of each queue. We then present two novel algorithms
\texttt{SoftMW} (SoftMaxWeight) and \texttt{SSMW} (Sliding-window
SoftMaxWeight), both capable of stabilizing systems that can be stablized by
some (possibly unknown) sequence of randomized policies whose time-variation
satisfies a mild condition. We further generalize our results to the setting
where arrivals and departures only have bounded moments instead of being
deterministically bounded and propose \texttt{SoftMW+} and \texttt{SSMW+} that
are capable of stabilizing the system. As a building block of our new
algorithms, we also extend the classical \texttt{EXP3.S} (Auer et al., 2002)
algorithm for multi-armed bandits to handle unboundedly large feedback signals,
which can be of independent interest.
- Abstract(参考訳): 本稿では,瞬時ネットワーク条件の知識のない待ち行列システムのスケジューリングについて検討する。
我々は、1ホップのシングルサーバ待ち行列システムについて検討し、それぞれが時刻変動と非定常到着とサービスレートを持つ、$k$のキューからなる。
我々のスケジューリング手法は、各キューの瞬時ネットワーク状態(到着とサービス率)を知らずに、逆帯域学習とリアプノフドリフト最小化の革新的な組み合わせに基づいている。
次に、時間変化が穏やかな条件を満たすランダム化ポリシーのいくつかの(おそらく未知の)シーケンスで安定化可能なシステムを安定化できる2つの新しいアルゴリズムである「texttt{SoftMW} (SoftMaxWeight) と「texttt{SSMW} (Sliding-window SoftMaxWeight)」を提案する。
さらに、到着と出発が決定的に有界ではなく有界な瞬間のみを持つような設定に一般化し、システムの安定化が可能な \texttt{SoftMW+} と \texttt{SSMW+} を提案する。
新しいアルゴリズムの構成要素として、マルチアーム付きバンディットのための古典的な \texttt{exp3.s} (auer et al., 2002) アルゴリズムを拡張して、境界のない大きなフィードバック信号を処理します。
関連論文リスト
- Quantifying the Cost of Learning in Queueing Systems [4.784875233446591]
待ち行列における学習コスト (CLQ) はパラメータの不確実性に起因する平均待ち行列長の最大増加を定量化する新しい指標である。
本稿では,Lyapunov と Bandit 分析をブリッジし,幅広いアルゴリズムの保証を提供するCLQ の統一解析フレームワークを提案する。
論文 参考訳(メタデータ) (2023-08-15T14:50:12Z) - Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When
Partial Feedback Counts [53.579515853222986]
時間分割リワード(TP-MAB)を用いたマルチアーメッド・バンディット(Multi-Armed Bandit)について検討する。
この設定は、プル後の有限時間スパン上で報酬が拡張されるケースに対する遅延フィードバックバンディットの自然な拡張である。
本稿では,TP-UCB-FRとTP-UCB-EWの2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-06-01T15:56:59Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳(メタデータ) (2022-02-09T19:22:34Z) - Scheduling Servers with Stochastic Bilinear Rewards [3.5408022972081685]
本稿では,ジョブやサーバを表す特徴ベクトルの双線形モデルに従って,ジョブサーバの割り当てを報奨するマルチクラスマルチサーバキューシステムについて検討する。
本稿では,サーバへのジョブの動的割り当てとともに線形帯域幅アルゴリズムを用いたスケジューリングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-12-13T00:37:20Z) - STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal
Sample and Communication Complexities for Federated Learning [58.6792963686231]
フェデレートラーニング(FL)とは、複数のワーカノード(WN)がローカルデータを用いてジョイントモデルを構築するパラダイムを指す。
WNの最小更新方向、最初のミニバッチサイズ、ローカル更新頻度をどうやって選択するかは明らかになっていない。
局所的な更新頻度と局所的なミニサイズとの間にはトレードオフ曲線があることを示し、上記の複雑さを維持できることを示す。
論文 参考訳(メタデータ) (2021-06-19T06:13:45Z) - 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) - Learning Algorithms for Minimizing Queue Length Regret [5.8010446129208155]
パケットはランダムに送信機のキューに到着し、受信機に送信されるのを待ちます。
送信機の目的は、キュー内のパケット数を$T$のタイムスロットで最小化するために、最適なチャネルを素早く識別することである。
順序の最適値O(1)$キュー長の後悔を得られるキュー長ベースのポリシーのセットが存在することを示す。
論文 参考訳(メタデータ) (2020-05-11T15:50:56Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳(メタデータ) (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。