論文の概要: Queueing Matching Bandits with Preference Feedback
- arxiv url: http://arxiv.org/abs/2410.10098v1
- Date: Mon, 14 Oct 2024 02:29:06 GMT
- ステータス: 処理完了
- システム内更新日: 2024-10-30 03:04:18.095824
- Title: Queueing Matching Bandits with Preference Feedback
- Title（参考訳）: 優先フィードバックによるマッチング帯域の待ち行列
- Authors: Jung-hun Kim, Min-hwan Oh,
- Abstract要約: 我々は、一方のN$キューと他方のK$サーバからなるマルチクラス非対称キューシステムについて検討する。
各ジョブサーバ割り当てのサービスレートは未知であり、機能ベースのMNL(Multi-nomial Logit)関数によってモデル化される。
我々は,UCBとトンプソンサンプリングに基づくアルゴリズムを提案する。このアルゴリズムは,待ち時間の平均値が$O(minN,K/epsilon)$に制限されたシステム安定性を実現する。
- 参考スコア（独自算出の注目度）: 10.988222071035198
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this study, we consider multi-class multi-server asymmetric queueing systems consisting of $N$ queues on one side and $K$ servers on the other side, where jobs randomly arrive in queues at each time. The service rate of each job-server assignment is unknown and modeled by a feature-based Multi-nomial Logit (MNL) function. At each time, a scheduler assigns jobs to servers, and each server stochastically serves at most one job based on its preferences over the assigned jobs. The primary goal of the algorithm is to stabilize the queues in the system while learning the service rates of servers. To achieve this goal, we propose algorithms based on UCB and Thompson Sampling, which achieve system stability with an average queue length bound of $O(\min\{N,K\}/\epsilon)$ for a large time horizon $T$, where $\epsilon$ is a traffic slackness of the system. Furthermore, the algorithms achieve sublinear regret bounds of $\tilde{O}(\min\{\sqrt{T} Q_{\max},T^{3/4}\})$, where $Q_{\max}$ represents the maximum queue length over agents and times. Lastly, we provide experimental results to demonstrate the performance of our algorithms.
- Abstract（参考訳）: 本研究では、一方のN$キューと他方のK$サーバからなるマルチクラスマルチサーバ非対称キューシステムについて考察する。
各ジョブサーバ割り当てのサービスレートは未知であり、機能ベースのMNL(Multi-nomial Logit)関数によってモデル化される。
スケジューラはサーバにジョブを割り当て、各サーバは割り当てられたジョブに対する好みに基づいて、少なくとも1つのジョブを確率的に処理する。
アルゴリズムの主な目標は、サーバのサービスレートを学習しながら、システムのキューを安定させることである。
この目的を達成するために,UCB と Thompson Sampling に基づくアルゴリズムを提案する。このアルゴリズムは平均キュー長$O(\min\{N,K\}/\epsilon)$でシステム安定性を実現する。
さらに、アルゴリズムは、$\tilde{O}(\min\{\sqrt{T} Q_{\max},T^{3/4}\})$のサブ線形後悔境界(sublinear regret bounds of $\tilde{O}(\min\{\sqrt{T} Q_{\max},T^{3/4}\})$。
最後に,提案アルゴリズムの性能を示す実験結果について述べる。
関連論文リスト
- Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。
遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
論文 参考訳（メタデータ） (2024-03-25T22:49:56Z) - Learning-Based Pricing and Matching for Two-Sided Queues [14.854050478428727]
複数のタイプの顧客とサーバを持つ動的システムについて検討する。
各キューの到着率は、未知の需要または供給機能に応じて価格によって決定される。
このシステムは、乗客やドライバーとの乗り合い市場のような、両側の市場をモデル化するのに使用することができる。
論文 参考訳（メタデータ） (2024-03-17T05:07:04Z) - Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systems [21.944723061337267]
我々は、中央キューに到着するジョブをヘテロジニアスサーバのシステムに効率的にルーティングする問題を考察する。
均質なシステムとは異なり、キュー長が一定のしきい値を超えた場合、ジョブを遅いサーバにルーティングするしきい値ポリシーは、ワンファストワンスローの2サーバシステムに最適であることが知られている。
本稿では,低次元ソフトしきい値パラメータ化を用いた効率的なポリシー勾配に基づくアルゴリズムであるACHQを提案する。
論文 参考訳（メタデータ） (2024-02-02T05:22:41Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - Learning While Scheduling in Multi-Server Systems with Unknown
Statistics: MaxWeight with Discounted UCB [18.898514227870926]
本稿では、複数のサーバと複数のタイプのジョブを持つマルチサーバシステムについて考察する。
目標は、処理時間の統計を知ることなく、サーバ上のジョブをスケジュールすることだ。
我々は,MaxWeightスケジューリングポリシと割引された高信頼度境界(UCB)を組み合わせることで,統計を同時に学習し,ジョブをサーバにスケジュールするアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-09-02T15:37:02Z) - A Simple and Provably Efficient Algorithm for Asynchronous Federated
Contextual Linear Bandits [77.09836892653176]
我々は,M$エージェントが相互に協力して,中央サーバの助けを借りて,グローバルなコンテキスト線形バンドイット問題を解決するためのフェデレーション付きコンテキスト線形バンドイットについて検討した。
すべてのエージェントが独立して動作し、ひとつのエージェントとサーバ間の通信が他のエージェントの通信をトリガーしない非同期設定を考える。
texttFedLinUCBの後悔は$tildeO(dsqrtsum_m=1M T_m)$で、通信の複雑さは$tildeO(dM)であることを示す。
論文 参考訳（メタデータ） (2022-07-07T06:16:19Z) - Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。
我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
論文 参考訳（メタデータ） (2022-03-29T15:27:13Z) - Scheduling Servers with Stochastic Bilinear Rewards [7.519872646378837]
システム最適化問題は、マルチクラス、マルチサーバキューシステムスケジューリングで発生する。
本稿では,報酬の限界コストを付加した重み付き比例フェアアロケーション基準に基づくスケジューリングアルゴリズムを提案する。
我々のアルゴリズムは,時間的地平線に関して,サブ線形後悔とサブ線形平均保持コスト(および待ち時間境界)を考慮し,待ち行列システムの安定性を保証する。
論文 参考訳（メタデータ） (2021-12-13T00:37:20Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Learning Algorithms for Minimizing Queue Length Regret [5.8010446129208155]
パケットはランダムに送信機のキューに到着し、受信機に送信されるのを待ちます。
送信機の目的は、キュー内のパケット数を$T$のタイムスロットで最小化するために、最適なチャネルを素早く識別することである。
順序の最適値O(1)$キュー長の後悔を得られるキュー長ベースのポリシーのセットが存在することを示す。
論文 参考訳（メタデータ） (2020-05-11T15:50:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。