論文の概要: Learning-based Optimal Admission Control in a Single Server Queuing System

• arxiv url: http://arxiv.org/abs/2212.11316v1
• Date: Wed, 21 Dec 2022 19:26:52 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-23 15:11:48.980368
• Title: Learning-based Optimal Admission Control in a Single Server Queuing System
• Title（参考訳）: 単一サーバキューシステムにおける学習型最適アドミッション制御
• Authors: Asaf Cohen, Vijay G. Subramanian, Yili Zhang
• Abstract要約: 我々は,M/M/1キューイングシステムにおける入場率を未知のサービス率で把握し,入場率を最大化する長期平均利益を考察する。 完全情報を含む全ての最適しきい値がゼロでない場合には,アルゴリズムが$O(1)$後悔することを示す。
• 参考スコア（独自算出の注目度）: 21.68301564207292
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a long-term average profit maximizing admission control problem in an M/M/1 queuing system with a known arrival rate but an unknown service rate. With a fixed reward collected upon service completion and a cost per unit of time enforced on customers waiting in the queue, a dispatcher decides upon arrivals whether to admit the arriving customer or not based on the full history of observations of the queue-length of the system. \cite[Econometrica]{Naor} showed that if all the parameters of the model are known, then it is optimal to use a static threshold policy - admit if the queue-length is less than a predetermined threshold and otherwise not. We propose a learning-based dispatching algorithm and characterize its regret with respect to optimal dispatch policies for the full information model of \cite{Naor}. We show that the algorithm achieves an $O(1)$ regret when all optimal thresholds with full information are non-zero, and achieves an $O(\ln^{3+\epsilon}(N))$ regret in the case that an optimal threshold with full information is $0$ (i.e., an optimal policy is to reject all arrivals), where $N$ is the number of arrivals and $\epsilon>0$.
• Abstract（参考訳）: 我々は,M/M/1待ち行列システムにおける入場率を未知のサービス率で最大化する長期平均利益を考える。 サービス完了時に定額の報酬と、待ち行列で待機している顧客に対して実施される時間単位当たりのコストにより、ディスペンサーは、システムの待ち行列の長さの観察の全履歴に基づいて、到着客を認めるか否かを判断する。 \cite[Econometrica]{Naor} は、もしモデルのすべてのパラメータが知られているなら、静的しきい値ポリシーを使うのが最適であることを示した。 本稿では, 学習に基づくディスパッチアルゴリズムを提案し, その後悔を, \cite{Naor} の全情報モデルに対する最適ディスパッチポリシーに関して特徴づける。 完全情報を持つ最適なしきい値がゼロでない場合に、そのアルゴリズムが$o(1)$の後悔を達成し、全情報を持つ最適なしきい値が$0$(すなわち、すべての到着を拒否する最適方針)である場合に$o(\ln^{3+\epsilon}(n))$の後悔を達成する。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
  サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。 近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。 ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
  論文  参考訳（メタデータ） (2023-09-21T21:51:55Z)
• Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space [0.0]
  離散時間可算状態空間マルコフ決定過程の族を最適に制御する問題について検討する。 動的サイズのエピソードを用いたトンプソンサンプリングに基づくアルゴリズムを提案する。 提案アルゴリズムは, 近似最適制御アルゴリズムの開発に応用可能であることを示す。
  論文  参考訳（メタデータ） (2023-06-05T03:57:16Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。 各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。 一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-23T09:03:24Z)
• Optimal Admission Control for Multiclass Queues with Time-Varying Arrival Rates via State Abstraction [16.99621896314678]
  我々は、意思決定者がランダムに到着したタスクを受け入れ、拒否する必要があるという、新しいキュー問題を考える。 目的は、処理されたタスクの総価格が有限の地平線上で最大になるように、どのタスクを受け入れるかを決定することである。 最適値関数は特定の構造を持ち、ハイブリッドMDPを正確に解くことができることを示す。
  論文  参考訳（メタデータ） (2022-03-14T12:38:13Z)
• Learning a Discrete Set of Optimal Allocation Rules in a Queueing System with Unknown Service Rate [1.4094389874355762]
  入場率とサービス率の不明なシステムの入場制御について検討する。 私たちのモデルでは、ジョブが到着するたびに、ディスペンサーがジョブを利用可能なサーバに割り当てるか、ブロックするかを決めます。 我々の目標は、ディスパッチの長期平均報酬を最大化するディスパッチポリシーを設計することです。
  論文  参考訳（メタデータ） (2022-02-04T22:39:03Z)
• Non-Parametric Stochastic Sequential Assignment With Random Arrival Times [3.871148938060281]
  ジョブがランダムに到着し、ランダムな値を仮定する問題を考える。 本稿では,NPSA(Non-Parametric Sequential Allocation)アルゴリズムを提案する。 NPSAアルゴリズムによって返される期待報酬は、M$が大きくなるにつれて、最適性に収束することを示す。
  論文  参考訳（メタデータ） (2021-06-09T09:41:38Z)
• Learning to Schedule [3.5408022972081685]
  本稿では,ジョブが生み出す累積保持コストを最小限に抑えるための学習・スケジューリングアルゴリズムを提案する。 各タイムスロットにおいて、サーバはシステムに残されているジョブのランダム保持コストを受信しながらジョブを処理できる。
  論文  参考訳（メタデータ） (2021-05-28T08:04:06Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Timely Communication in Federated Learning [65.1253801733098]
  我々は,パラメータサーバ(PS)が,クラウドサーバにクライアントデータを集中的に格納することなく,$n$クライアントを用いてグローバルモデルを訓練するグローバルラーニングフレームワークを検討する。 提案されたスキームでは、各イテレーションでPSは$m$のクライアントを待ち、現在のモデルを送信する。 各クライアントが経験する情報の平均年齢を見つけ、与えられた$n$の年齢最適値である$m$と$k$を数値的に特徴付ける。
  論文  参考訳（メタデータ） (2020-12-31T18:52:08Z)
• Toward Optimal Adversarial Policies in the Multiplicative Learning System with a Malicious Expert [87.12201611818698]
  専門家のアドバイスを組み合わせて真の結果を予測する学習システムについて考察する。 専門家の一人が悪意があり、システムに最大損失を課すことを目指していると推測されている。 誤予測を常に報告する単純な欲求ポリシーは、近似比が1+O(sqrtfracln NN)$で最適であることを示す。 悪意のある専門家がその判断を適応的に行うことができるオンライン環境では、最適のオンラインポリシーを$O(N3)$で動的プログラムを解くことで効率的に計算できることが示される。
  論文  参考訳（メタデータ） (2020-01-02T18:04:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。