論文の概要: Nonpreemptive Scheduling While Learning Context-Dependent Service Rates
- arxiv url: http://arxiv.org/abs/2609.37660v1
- Date: Tue, 29 Sep 2026 14:20:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-30 21:28:47.61656
- Title: Nonpreemptive Scheduling While Learning Context-Dependent Service Rates
- Title（参考訳）: コンテキスト依存型サービスレート学習における非プリエンプティブスケジューリング
- Abstract要約: 単一サーバシステムにおける非プリエンプティブなコンテキスト待ち行列帯域について検討する。
Learn--Clear--Planはシステムを推定し、結果のベルマン再帰を使って地平線に依存した決定を行う。
モデルを知らずに$widetildeO(sqrtd/T)$の追跡誤差を実現する推定SEPTアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.8984888893275712
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study nonpreemptive contextual queueing bandits in a single-server system. Each job is represented by a $d$-dimensional context vector; in each round, a job may arrive with its context drawn from an unknown distribution $\mathcal{D}$, and its departure probability is determined by a logistic model of that context vector with an unknown parameter $θ^*$. The server learns from service outcomes while deciding which waiting job to serve and whether to idle, aiming to minimize queue-length regret, the gap between its expected terminal queue length and the minimum achievable by an admissible policy. Once selected, a job must be served until completion, and we refer to this as the nonpreemptive setting. A central challenge is that, even with full model knowledge, the optimal policy cannot in general be characterized by a simple myopic rule, since the optimal action can change with the remaining horizon at the same queue state. Nevertheless, when the model and horizon are known, the optimal action can be obtained through a finite-horizon Bellman recursion. Motivated by this, we propose Learn--Clear--Plan (LCP), which estimates the system and uses the resulting Bellman recursion to make horizon-dependent decisions. LCP achieves $\widetilde{O}(\sqrt{d/T})$ queue-length regret, while a lower-bound construction gives $Ω(\min\{1/\sqrt{d},\sqrt{d/T}\})$ regret for every learning policy on some instance, establishing optimality up to polylogarithmic factors when $T\ge d^2$. When the horizon is unknown, no horizon-independent policy achieves vanishing regret against the finite-horizon optimum. We therefore use SEPT, the policy that serves a waiting job with the highest probability of departure, as a fixed reference, and suggest an estimated-SEPT algorithm that achieves a tracking error of $\widetilde{O}(\sqrt{d/t})$ without knowing the model.
- Abstract（参考訳）: 単一サーバシステムにおける非プリエンプティブなコンテキスト待ち行列帯域について検討する。
それぞれのジョブは$d$次元のコンテキストベクトルで表現され、各ラウンドにおいて、ジョブは未知の分布$\mathcal{D}$から引き出されたコンテキストに到達し、その離脱確率は未知のパラメータ$θ^*$でそのコンテキストベクトルのロジスティックモデルによって決定される。
サーバは、どの待機ジョブを提供するか、アイドルするかを判断しながら、サービス結果から学習し、待ち行列長の後悔、期待される終端待ち行列の長さと許容ポリシーで達成可能な最小限のギャップを最小化する。
一度選択すると、ジョブは完了まで提供されなければなりません。
中心的な課題は、完全なモデル知識があるとしても、最適ポリシーは一般に単純なミオピック規則によって特徴づけられないことである。
それでも、モデルと地平線が知られているとき、最適作用は有限水平ベルマン再帰によって得られる。
そこで我々は,Learning-Clear-Plan (LCP)を提案する。
LCP は $\widetilde{O}(\sqrt{d/T})$ queue-length regret を達成し、一方低次構成は $Ω(\min\{1/\sqrt{d},\sqrt{d/T}\})$ regret を与える。
地平線が未知の場合、地平線に依存しない政策は有限水平最適点に対する後悔を消し去ることはない。
したがって、SEPTは、出発確率が最も高い待ちジョブを固定基準として使用するポリシーであり、モデルを知らずに$\widetilde{O}(\sqrt{d/t})$の追跡誤差を達成する推定SEPTアルゴリズムを提案する。
関連論文リスト
- Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。
失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
論文 参考訳（メタデータ） (2026-07-22T07:42:19Z) - 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) - From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。
実現可能な最小二乗の設定において、新しい最上界を創出する。
我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
論文 参考訳（メタデータ） (2025-04-06T18:39:45Z) - Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
我々は,個別かつ不可逆な意思決定を対象とするオンライン学習と最適化の問題を定義した。
各期間において、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために分類モデルを更新する。
目的は,多数の施設を対象とする地平線を特徴とし,カバー対象を反映するチャンス制約の下で施設開口を最小化することである。
論文 参考訳（メタデータ） (2024-06-20T23:00:25Z) - Learning-based Optimal Admission Control in a Single Server Queuing
System [14.13429123941818]
我々は,M/M/1待ち行列システムにおける入場制御問題の長期平均利益を最大化することを検討する。
完全情報を含む全ての最適しきい値がゼロでない場合には,アルゴリズムが$O(1)$後悔することを示す。
論文 参考訳（メタデータ） (2022-12-21T19:26:52Z) - Provably Efficient Lifelong Reinforcement Learning with Linear Function
Approximation [41.460894569204065]
線形文脈マルコフ決定過程(MDP)の遺残条件における生涯強化学習(RL)について検討する。
本稿では, UCB Lifelong Value Distillation (UCBlvd) と呼ばれるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T06:53:28Z) - Dynamic Planning and Learning under Recovering Rewards [18.829837839926956]
我々は「純粋周期ポリシー」のクラスの性能保証を提案し、構築し、証明する。
私たちのフレームワークとポリシー設計は、他のオフライン計画およびオンライン学習アプリケーションに適応する可能性がある。
論文 参考訳（メタデータ） (2021-06-28T15:40:07Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Stochastic Shortest Path: Minimax, Parameter-Free and Towards
Horizon-Free Regret [144.6358229217845]
エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。
我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。
私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
論文 参考訳（メタデータ） (2021-04-22T17:20:48Z) - Minimax Regret for Stochastic Shortest Path [63.45407095296692]
我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。
この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。
本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
論文 参考訳（メタデータ） (2021-03-24T10:11:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。