論文の概要: 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) アルゴリズムを拡張して、境界のない大きなフィードバック信号を処理します。
関連論文リスト
- Adversarial Network Optimization under Bandit Feedback: Maximizing Utility in Non-Stationary Multi-Hop Networks [35.78834550608041]
古典的なSNOアルゴリズムでは、ネットワーク条件は時間とともに定常である必要がある。
これらの問題に触発され、我々は帯域幅のフィードバックの下でAdversarial Network Optimization (ANO) を検討する。
提案するUMO2アルゴリズムは,ネットワークの安定性を保証し,また,「微妙に変化する」参照ポリシーの実用性に適合する。
論文 参考訳（メタデータ） (2024-08-29T02:18:28Z) - Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
実用的な分散システムでは、労働者は概して均質ではなく、非常に多様な処理時間を持つ。
本稿では、任意に遅い計算を扱うための新しい並列手法Freyaを提案する。
Freyaは従来の手法と比較して,複雑性の保証が大幅に向上していることを示す。
論文 参考訳（メタデータ） (2024-05-24T13:33:30Z) - 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 [7.519872646378837]
システム最適化問題は、マルチクラス、マルチサーバキューシステムスケジューリングで発生する。
本稿では,報酬の限界コストを付加した重み付き比例フェアアロケーション基準に基づくスケジューリングアルゴリズムを提案する。
我々のアルゴリズムは,時間的地平線に関して,サブ線形後悔とサブ線形平均保持コスト(および待ち時間境界)を考慮し,待ち行列システムの安定性を保証する。
論文 参考訳（メタデータ） (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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。