論文の概要: Learning payoffs while routing in skill-based queues
- arxiv url: http://arxiv.org/abs/2412.10168v1
- Date: Fri, 13 Dec 2024 14:33:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-16 15:01:38.882830
- Title: Learning payoffs while routing in skill-based queues
- Title（参考訳）: スキルベースのキューにおけるルーティング中のペイオフ学習
- Authors: Sanne van Kempen, Jaron Sanders, Fiona Sloothaak, Maarten G. Wolf,
- Abstract要約: 我々は,全支払パラメータを適応的に学習し,全支払パラメータを最大化する機械学習アルゴリズムを構築した。
このアルゴリズムは,残差の下限を導出することにより,対数項に最適であることを示す。
- 参考スコア（独自算出の注目度）: 0.4077787659104315
- License:
- Abstract: Motivated by applications in service systems, we consider queueing systems where each customer must be handled by a server with the right skill set. We focus on optimizing the routing of customers to servers in order to maximize the total payoff of customer--server matches. In addition, customer--server dependent payoff parameters are assumed to be unknown a priori. We construct a machine learning algorithm that adaptively learns the payoff parameters while maximizing the total payoff and prove that it achieves polylogarithmic regret. Moreover, we show that the algorithm is asymptotically optimal up to logarithmic terms by deriving a regret lower bound. The algorithm leverages the basic feasible solutions of a static linear program as the action space. The regret analysis overcomes the complex interplay between queueing and learning by analyzing the convergence of the queue length process to its stationary behavior. We also demonstrate the performance of the algorithm numerically, and have included an experiment with time-varying parameters highlighting the potential of the algorithm in non-static environments.
- Abstract（参考訳）: サービスシステムにおけるアプリケーションによって動機付けられ、各顧客が適切なスキルセットを持つサーバによって処理されなければならないキューシステムについて検討する。
我々は,顧客-サーバ間マッチングの総支払額を最大化するために,顧客-サーバ間のルーティングを最適化することに注力する。
我々は,全支払パラメータを最大化しながら適応的に学習し,多言語的後悔を達成できる機械学習アルゴリズムを構築した。
さらに,このアルゴリズムは,残差下界を導出することにより,対数項まで漸近的に最適であることを示す。
このアルゴリズムは、静的線形プログラムの基本的な実現可能な解をアクション空間として活用する。
後悔解析は待ち行列と学習の間の複雑な相互作用を克服し、待ち行列のプロセスと定常動作の収束を解析する。
また,アルゴリズムの性能を数値的に示すとともに,非定常環境におけるアルゴリズムの可能性を示す時間変化パラメータを用いた実験も実施している。
関連論文リスト
- Efficient Methods for Non-stationary Online Learning [67.3300478545554]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
論文 参考訳（メタデータ） (2023-09-16T07:30:12Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。
我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。
これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
論文 参考訳（メタデータ） (2022-02-21T13:18:11Z) - Scheduling Servers with Stochastic Bilinear Rewards [7.519872646378837]
システム最適化問題は、マルチクラス、マルチサーバキューシステムスケジューリングで発生する。
本稿では,報酬の限界コストを付加した重み付き比例フェアアロケーション基準に基づくスケジューリングアルゴリズムを提案する。
我々のアルゴリズムは,時間的地平線に関して,サブ線形後悔とサブ線形平均保持コスト(および待ち時間境界)を考慮し,待ち行列システムの安定性を保証する。
論文 参考訳（メタデータ） (2021-12-13T00:37:20Z) - Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for
Mixable/Exp-Concave Losses [0.0]
動的環境における対数的静的後悔を伴う混合損失関数のオンライン最適化について検討する。
文献では,スイッチ1回あたりのほぼ対数的後悔を1時間あたりのポリノミカルな複雑さで達成できることが確認できた。
論文 参考訳（メタデータ） (2021-09-28T15:06:31Z) - 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) - Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。
私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
論文 参考訳（メタデータ） (2021-04-19T14:35:14Z) - An online learning approach to dynamic pricing and capacity sizing in
service systems [26.720986177499338]
本稿では,$GI/GI/1$キューにおいて,動的価格とキャパシティサイズの問題について検討する。
私たちのフレームワークは、GOLiQ(Gradient-based Online Learning in Queue)と呼ばれています。
論文 参考訳（メタデータ） (2020-09-07T07:17:20Z) - Joint Parameter-and-Bandwidth Allocation for Improving the Efficiency of
Partitioned Edge Learning [73.82875010696849]
機械学習アルゴリズムは、人工知能(AI)モデルをトレーニングするために、ネットワークエッジにデプロイされる。
本稿では,パラメータ(計算負荷)割り当てと帯域幅割り当ての新しい共同設計に焦点を当てる。
論文 参考訳（メタデータ） (2020-03-10T05:52:15Z) - Learning with Differentiable Perturbed Optimizers [54.351317101356614]
本稿では,操作を微分可能で局所的に一定ではない操作に変換する手法を提案する。
提案手法は摂動に依拠し,既存の解法とともに容易に利用することができる。
本稿では,この枠組みが,構造化予測において発達した損失の族とどのように結びつくかを示し,学習課題におけるそれらの使用に関する理論的保証を与える。
論文 参考訳（メタデータ） (2020-02-20T11:11:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。