論文の概要: 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)$ キュー長の後悔を得られるような, キュー長ベースのポリシー群が存在することを示す。
シミュレーションでうまく機能することを示すヒューリスティックな手法を考案するために理論解析を用いる。
関連論文リスト
- Learning-based Scheduling for Information Accuracy and Freshness in
Wireless Networks [0.0]
我々は、複数のソース、単一の通信チャネル、単一の監視ステーションからなるシステムを考える。
正確な測定の確率と、全てのソースが正常に送信される確率は、スケジューラに未知である。
論文 参考訳(メタデータ) (2023-10-24T10:31:34Z) - Queue Scheduling with Adversarial Bandit Learning [20.606599586119835]
K$キューからなるワンホップ単一サーバキューシステムについて検討する。
我々のスケジューリング手法は,逆帯域学習とリアプノフドリフト最小化の革新的な組み合わせに基づいている。
ランダム化ポリシーのいくつかの(おそらく未知の)シーケンスで安定化可能なシステムを安定化できる2つの新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-03T07:17:09Z) - Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
論文 参考訳(メタデータ) (2023-01-31T03:49:00Z) - 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) - 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) - 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) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。