論文の概要: Learning Algorithms for Minimizing Queue Length Regret
- arxiv url: http://arxiv.org/abs/2005.05206v2
- Date: Thu, 14 May 2020 13:26:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-04 20:10:57.684277
- Title: Learning Algorithms for Minimizing Queue Length Regret
- Title（参考訳）: 待ち行列の最小化のための学習アルゴリズム
- Authors: Thomas Stahlbuhk, Brooke Shrader and Eytan Modiano
- Abstract要約: パケットはランダムに送信機のキューに到着し、受信機に送信されるのを待ちます。
送信機の目的は、キュー内のパケット数を$T$のタイムスロットで最小化するために、最適なチャネルを素早く識別することである。
順序の最適値O(1)$キュー長の後悔を得られるキュー長ベースのポリシーのセットが存在することを示す。
- 参考スコア（独自算出の注目度）: 5.8010446129208155
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a system consisting of a single transmitter/receiver pair and $N$
channels over which they may communicate. Packets randomly arrive to the
transmitter's queue and wait to be successfully sent to the receiver. The
transmitter may attempt a frame transmission on one channel at a time, where
each frame includes a packet if one is in the queue. For each channel, an
attempted transmission is successful with an unknown probability. The
transmitter's objective is to quickly identify the best channel to minimize the
number of packets in the queue over $T$ time slots. To analyze system
performance, we introduce queue length regret, which is the expected difference
between the total queue length of a learning policy and a controller that knows
the rates, a priori. One approach to designing a transmission policy would be
to apply algorithms from the literature that solve the closely-related
stochastic multi-armed bandit problem. These policies would focus on maximizing
the number of successful frame transmissions over time. However, we show that
these methods have $\Omega(\log{T})$ queue length regret. On the other hand, we
show that there exists a set of queue-length based policies that can obtain
order optimal $O(1)$ queue length regret. We use our theoretical analysis to
devise heuristic methods that are shown to perform well in simulation.
- Abstract（参考訳）: 我々は,単一送信/受信器ペアと通信可能なn$チャネルからなるシステムについて検討する。
パケットはランダムに送信機のキューに到着し、受信機に送信されるのを待つ。
送信機は、1つのチャネル上のフレーム送信を試みることができ、キューに1つあれば各フレームにパケットが含まれる。
各チャネルに対して、試みられた送信は未知の確率で成功する。
送信機の目標は、$t$のタイムスロット上のキュー内のパケット数を最小化する最善のチャネルを迅速に特定することである。
システム性能を分析するために,学習方針の全キュー長と,そのレートを知っているコントローラ,すなわち優先順位との期待値の違いである待ち行列長の後悔を導入する。
伝達ポリシーを設計する1つのアプローチは、密接に関連する確率的多腕バンディット問題を解決する文学のアルゴリズムを適用することである。
これらのポリシーは、時間とともにフレーム転送の成功回数を最大化することに焦点を当てる。
しかし、これらのメソッドは、$\Omega(\log{T})$ queue length regretを持つことを示す。
一方で, 最適な$o(1)$ キュー長の後悔を得られるような, キュー長ベースのポリシー群が存在することを示す。
シミュレーションでうまく機能することを示すヒューリスティックな手法を考案するために理論解析を用いる。
関連論文リスト
- Queueing Matching Bandits with Preference Feedback [10.988222071035198]
我々は、一方のN$キューと他方のK$サーバからなるマルチクラス非対称キューシステムについて検討する。
各ジョブサーバ割り当てのサービスレートは未知であり、機能ベースのMNL(Multi-nomial Logit)関数によってモデル化される。
我々は,UCBとトンプソンサンプリングに基づくアルゴリズムを提案する。このアルゴリズムは,待ち時間の平均値が$O(minN,K/epsilon)$に制限されたシステム安定性を実現する。
論文 参考訳（メタデータ） (2024-10-14T02:29:06Z) - 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 Scheduling for Information Accuracy and Freshness in
Wireless Networks [0.0]
我々は、複数のソース、単一の通信チャネル、単一の監視ステーションからなるシステムを考える。
正確な測定の確率と、全てのソースが正常に送信される確率は、スケジューラに未知である。
論文 参考訳（メタデータ） (2023-10-24T10:31:34Z) - Revisiting Decentralized ProxSkip: Achieving Linear Speedup [50.28561300894826]
ProxSkipilonの既存の解析は限定凸設定であり、ProxSkipilonの強い線形速度を達成できない。
本稿では, ProxSkipilon が線形スピードアップを実現し,通信の確率に比例した通信オーバーヘッドを低減することができることを示す。
論文 参考訳（メタデータ） (2023-10-12T02:13:48Z) - Queue Scheduling with Adversarial Bandit Learning [20.606599586119835]
K$キューからなるワンホップ単一サーバキューシステムについて検討する。
我々のスケジューリング手法は,逆帯域学習とリアプノフドリフト最小化の革新的な組み合わせに基づいている。
ランダム化ポリシーのいくつかの(おそらく未知の)シーケンスで安定化可能なシステムを安定化できる2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-03T07:17:09Z) - Sequential Information Design: Learning to Persuade in the Dark [49.437419242582884]
本研究では,自己関心の受信者の行動に影響を及ぼそうとする情報発信者が直面する繰り返し情報設計問題について検討する。
各ラウンドにおいて、送信者は、シーケンシャル意思決定(SDM)問題におけるランダムイベントの実現を観察する。
これは、そのような情報をレシーバーに段階的に開示し、彼らが(望まれる)アクションレコメンデーションに従うように説得する方法の課題である。
論文 参考訳（メタデータ） (2022-09-08T17:08:12Z) - Learning While Scheduling in Multi-Server Systems with Unknown
Statistics: MaxWeight with Discounted UCB [18.898514227870926]
本稿では、複数のサーバと複数のタイプのジョブを持つマルチサーバシステムについて考察する。
目標は、処理時間の統計を知ることなく、サーバ上のジョブをスケジュールすることだ。
我々は,MaxWeightスケジューリングポリシと割引された高信頼度境界(UCB)を組み合わせることで,統計を同時に学習し,ジョブをサーバにスケジュールするアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-09-02T15:37:02Z) - Multi-Receiver Online Bayesian Persuasion [51.94795123103707]
本研究では,未知の逆選択型の受信者に対して,送信者が繰り返し対面するオンライン学習フレームワークについて検討する。
オフラインモデルの慣習として、外部性やバイナリアクションのないケースに重点を置いています。
本稿では,損失関数を有限個に制限したオンライン学習問題に対処する一般的なオンライン降下スキームを提案する。
論文 参考訳（メタデータ） (2021-06-11T16:05:31Z) - Better than the Best: Gradient-based Improper Reinforcement Learning for
Network Scheduling [60.48359567964899]
パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。
我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
論文 参考訳（メタデータ） (2021-05-01T10:18:34Z) - Aging Bandits: Regret Analysis and Order-Optimal Learning Algorithm for
Wireless Networks with Stochastic Arrivals [24.897224064639406]
信頼できないチャネルに時間感知情報を送信するソースを持つシングルホップ無線ネットワークを検討する。
学習アルゴリズムは1つのペア(ソース、チャネル)を選択し、選択されたソースは選択されたチャネルを介してパケットを送信しようとする。
学習アルゴリズムの目的は、ネットワーク内の年齢情報(AoI)を$ T$のタイムスロットで最小化することです。
論文 参考訳（メタデータ） (2020-12-16T00:58:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。