論文の概要: Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm
- arxiv url: http://arxiv.org/abs/2610.06006v1
- Date: Mon, 05 Oct 2026 09:02:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-09 19:33:02.681196
- Title: Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm
- Title（参考訳）: コンテキスト依存型サービスレート下でのジョブスケジューリングにおける学習: 任意のレート-最適アルゴリズム
- Abstract要約: 我々は、学習者が未知のサービスレートを学習しながらジョブをスケジュールするコンテキスト待ち行列の帯域について研究する。
WISE(Widest Interval Selection with Elimination)を提案する。
- 参考スコア（独自算出の注目度）: 1.0098114696565863
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study contextual queueing bandits, where a learner schedules jobs while learning unknown service rates modeled by logistic functions of job-server features. Performance is measured by queue length regret, the expected excess queue length at round $t$ relative to an oracle that knows the service rates. Existing decaying-regret guarantees either have a suboptimal decay rate or require a known fixed horizon. They also assume context-wise slack and a strictly positive minimum eigenvalue of the feature covariance. In this paper, we propose WISE (Widest Interval Selection with Elimination), achieving rate-optimal $\widetilde{\mathcal O}(t^{-1/2})$ queue length regret at every sufficiently large time without knowing the horizon. We assume capacity slack, meaning that expected incoming workload under best-server service is below service capacity, and impose no covariance lower bound. Our analysis uses a workload potential measuring the expected service attempts needed by waiting jobs on their best servers. Its drift on nonempty rounds combines a negative term ensured by capacity slack with errors from suboptimal service choices. Then an elliptical potential count bounds how often WISE selects wide confidence intervals, thereby limiting the number of rounds with large service errors. We also sharpen the arrival-rate dependence of an existing lower bound and make its dependence on feature dimension and server count explicit. We prove another lower bound that quantifies the increase in regret as the normalized capacity slack decreases; to our knowledge, this is the first such lower bound for CQB. Simulations show small regret even when context-wise slack fails.
- Abstract（参考訳）: 本研究では、学習者がジョブサーバの機能のロジスティック関数によってモデル化された未知のサービスレートを学習しながら、ジョブをスケジュールするコンテキスト待ち行列の帯域について検討する。
パフォーマンスは、サービスレートを知っているオラクルと比較して、期待される過剰なキューの長さである、キューの長さの後悔によって測定されます。
既存の崩壊-回帰保証は、最適下崩壊率を持つか、既知の固定地平線を必要とする。
彼らはまた、コンテキストワイズスラックと、特徴共分散の厳密な正の最小固有値も仮定する。
本稿では,WiSE(Widest Interval Selection with Elimination)を提案する。
私たちは、キャパシティの欠如を前提としています。つまり、最高のサーバサービス下での着信ワークロードは、サービスキャパシティ以下であり、共分散の低いバウンダリを課すことはありません。
私たちの分析では、最高のサーバでジョブを待機するために必要なサービスの試行を計測するワークロードの可能性を使用します。
空でないラウンドでのドリフトは、キャパシティスラックによって保証される負の項と、最適以下のサービス選択からのエラーを結びつける。
そして、楕円ポテンシャルカウントは、WISEが広範囲の信頼区間を選択する頻度を制限し、大きなサービスエラーを伴うラウンドの数を制限する。
また、既存の下界の到着速度依存を鋭くし、特徴量やサーバ数への依存を明確にする。
我々は、正規化されたキャパシティスラックが減少するにつれて、後悔の増加を定量化する別の下限を証明している。
シミュレーションは、文脈的にスラックが失敗しても、わずかな後悔を示している。
関連論文リスト
- Nonpreemptive Scheduling While Learning Context-Dependent Service Rates [0.8984888893275712]
単一サーバシステムにおける非プリエンプティブなコンテキスト待ち行列帯域について検討する。
Learn--Clear--Planはシステムを推定し、結果のベルマン再帰を使って地平線に依存した決定を行う。
モデルを知らずに$widetildeO(sqrtd/T)$の追跡誤差を実現する推定SEPTアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-09-29T14:20:41Z) - Capacity-Constrained Online Convex Optimization with Delayed Feedback [58.59385794080679]
容量制約下での遅延オンライン凸最適化(OCO)について検討した。
1次フィードバックの場合、容量$C = (log T)$ sufficesで標準遅延OCOレートを対数係数まで回復できることがわかった。
包帯フィードバックの場合、後悔率は$(1 + _textmax/C)$で変調される。
論文 参考訳（メタデータ） (2026-06-10T06:37:06Z) - Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret [1.0098114696565863]
待ち時間後悔は、学習者の待ち時間とオラクルの待ち時間の間に期待される差として定義される。
本稿では,この値を$widetildemathcalO(T-1/2)$に改善する。
論文 参考訳（メタデータ） (2026-06-08T15:51:25Z) - Queue Length Regret Bounds for Contextual Queueing Bandits [0.8984888893275712]
我々は、未知のサービスレートを同時に学習しながら、スケジューリングのための新しいコンテキスト対応フレームワークであるコンテキストキュー帯域を導入します。
我々のアルゴリズムであるCQB-$varepsilon$は、$widetildemathcalO(T-1/4)$の残念な上限を達成する。
また,2番目のアルゴリズムであるCQB-Optは,逆選択された文脈の設定も考慮し,その場合の残差上限は$mathcalO(log2 T)$である。
論文 参考訳（メタデータ） (2026-01-27T07:40:23Z) - Intra-request branch orchestration for efficient LLM reasoning [52.68946975865865]
大規模言語モデル(LLM)は、複雑なタスクの正確性を改善するために、推論時推論アルゴリズムにますます依存している。
それまでの作業は、トークンの使用を減らすことを中心に、多くの場合、正確さを犠牲にしつつ、他のレイテンシ要因を見越すことに重点を置いていた。
本稿では,LLMサービスシステムであるDUCHESSについて,予測によって導かれるリクエスト内ブランチオーケストレーションにより,精度を犠牲にすることなく,コストとレイテンシを低減できるシステムを提案する。
論文 参考訳（メタデータ） (2025-09-29T15:52:08Z) - Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs [60.7808741738461]
我々は,遅れたフィードバックのために,過去のラウンドを同時に追跡できる回数を制限する,斬新な「透明さ」の下で,難解な遅延を伴うオンライン学習について研究する。
我々のアルゴリズムは、全てのキャパシティレベルにおいてミニマックスの後悔を達成し、性能は最適以下のキャパシティで優雅に低下する。
論文 参考訳（メタデータ） (2025-03-25T17:20:39Z) - Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
我々は,個別かつ不可逆な意思決定を対象とするオンライン学習と最適化の問題を定義した。
各期間において、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために分類モデルを更新する。
目的は,多数の施設を対象とする地平線を特徴とし,カバー対象を反映するチャンス制約の下で施設開口を最小化することである。
論文 参考訳（メタデータ） (2024-06-20T23:00:25Z) - Learning While Scheduling in Multi-Server Systems with Unknown
Statistics: MaxWeight with Discounted UCB [18.898514227870926]
本稿では、複数のサーバと複数のタイプのジョブを持つマルチサーバシステムについて考察する。
目標は、処理時間の統計を知ることなく、サーバ上のジョブをスケジュールすることだ。
我々は,MaxWeightスケジューリングポリシと割引された高信頼度境界(UCB)を組み合わせることで,統計を同時に学習し,ジョブをサーバにスケジュールするアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-09-02T15:37:02Z) - Learning to Schedule in Parallel-Server Queues with Stochastic Bilinear Rewards [7.519872646378837]
本稿では,ジョブサーバの割り当てが不確実なマルチクラス並列サーバシステムにおけるスケジューリングの問題について考察する。
我々の目標は、時間軸上でのジョブサーバ割り当ての累積報酬を最大化することで、後悔を最小限に抑えることです。
提案アルゴリズムは,サブリニア・リセット・バウンドとサブリニア平均保持コストを実現する。
論文 参考訳（メタデータ） (2021-12-13T00:37:20Z) - Hierarchical Reinforcement Learning as a Model of Human Task
Interleaving [60.95424607008241]
我々は、強化学習によって駆動される監督制御の階層モデルを開発する。
このモデルは、タスクインターリービングの既知の経験的効果を再現する。
その結果、階層的RLがタスクインターリービングのもっともらしいモデルとして支持された。
論文 参考訳（メタデータ） (2020-01-04T17:53:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。