論文の概要: Minimizing Queue Length Regret for Arbitrarily Varying Channels
- arxiv url: http://arxiv.org/abs/2501.13551v1
- Date: Thu, 23 Jan 2025 10:54:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-24 15:55:02.743455
- Title: Minimizing Queue Length Regret for Arbitrarily Varying Channels
- Title（参考訳）: 任意可変チャネルにおける待ち時間レギュレータの最小化
- Authors: G Krishnakumar, Abhishek Sinha,
- Abstract要約: 任意に変化する無線チャネルをN$で備えた単一送受信機対のオンラインチャネルスケジューリング問題を考える。
チャネルの送信速度は非定常的であり、不可避な敵によって制御される可能性がある。
本稿では,この設定における待ち行列長の最小化のために,弱適応型マルチアーマッド帯域幅(MAB)アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 9.091372562683311
- License:
- Abstract: We consider an online channel scheduling problem for a single transmitter-receiver pair equipped with $N$ arbitrarily varying wireless channels. The transmission rates of the channels might be non-stationary and could be controlled by an oblivious adversary. At every slot, incoming data arrives at an infinite-capacity data queue located at the transmitter. A scheduler, which is oblivious to the current channel rates, selects one of the $N$ channels for transmission. At the end of the slot, the scheduler only gets to know the transmission rate of the selected channel. The objective is to minimize the queue length regret, defined as the difference between the queue length at some time $T$ achieved by an online policy and the queue length obtained by always transmitting over the single best channel in hindsight. We propose a weakly adaptive Multi-Armed Bandit (MAB) algorithm for minimizing the queue length regret in this setup. Unlike previous works, we do not make any stability assumptions about the queue or the arrival process. Hence, our result holds even when the queueing process is unstable. Our main observation is that the queue length regret can be upper bounded by the regret of a MAB policy that competes against the best channel in hindsight uniformly over all sub-intervals of $[T]$. As a technical contribution of independent interest, we then propose a weakly adaptive adversarial MAB policy which achieves $\tilde{O}(\sqrt{N}T^{\frac{3}{4}})$ regret with high probability, implying the same bound for queue length regret.
- Abstract（参考訳）: 任意に変化する無線チャネルをN$で備えた単一送受信機対のオンラインチャネルスケジューリング問題を考える。
チャネルの送信速度は非定常的であり、不可避な敵によって制御される可能性がある。
各スロットで、受信したデータは送信側にある無限容量のデータキューに届く。
スケジューラは、現在のチャネルレートとは無関係であり、送信用の$N$チャネルの1つを選択する。
スロットの最後には、スケジューラは選択したチャンネルの送信率のみを知る。
目的は、オンラインポリシーによって達成された待ち行列長と、後から常に1つのベストチャネルを渡して得られる待ち行列長との差として定義される待ち行列長の最小化である。
本稿では,この設定における待ち行列長の最小化のために,弱適応型マルチアーマッド帯域幅(MAB)アルゴリズムを提案する。
以前の作業とは異なり、キューや到着プロセスに関する安定性の仮定は行いません。
したがって、キュー処理が不安定である場合でも、結果が持続する。
我々の主な観察は、待ち行列長の後悔は、[T]$のすべてのサブインターバルに対して一様に最高のチャネルと競合するMABポリシーの後悔によって上限づけられるということです。
独立利害関係の技術的貢献として、我々は、高い確率で$\tilde{O}(\sqrt{N}T^{\frac{3}{4}})の後悔を達成し、待ち行列長の後悔に対する同じ境界を示唆する弱適応的逆MABポリシーを提案する。
関連論文リスト
- Queueing Matching Bandits with Preference Feedback [10.988222071035198]
我々は、一方のN$キューと他方のK$サーバからなるマルチクラス非対称キューシステムについて検討する。
各ジョブサーバ割り当てのサービスレートは未知であり、機能ベースのMNL(Multi-nomial Logit)関数によってモデル化される。
我々は,UCBとトンプソンサンプリングに基づくアルゴリズムを提案する。このアルゴリズムは,待ち時間の平均値が$O(minN,K/epsilon)$に制限されたシステム安定性を実現する。
論文 参考訳（メタデータ） (2024-10-14T02:29:06Z) - Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。
我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
論文 参考訳（メタデータ） (2024-02-19T03:08:02Z) - Queue Scheduling with Adversarial Bandit Learning [20.606599586119835]
K$キューからなるワンホップ単一サーバキューシステムについて検討する。
我々のスケジューリング手法は,逆帯域学習とリアプノフドリフト最小化の革新的な組み合わせに基づいている。
ランダム化ポリシーのいくつかの(おそらく未知の)シーケンスで安定化可能なシステムを安定化できる2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-03T07:17:09Z) - Soft Masking for Cost-Constrained Channel Pruning [17.138115344464513]
構造化チャネルプルーニングは、現代のハードウェア上での畳み込みニューラルネットワーク(CNN)の推論時間を著しく加速することが示されている。
最近の研究は、トレーニング中にこれらのチャネルを永久的にゼロにしており、最終的な精度を著しく損なうことが観察されている。
本稿では,コスト制約付きチャネル・プルーニング(SMCP)のためのソフト・マスキングを提案する。
論文 参考訳（メタデータ） (2022-11-04T01:28:45Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Multi-Receiver Online Bayesian Persuasion [51.94795123103707]
本研究では,未知の逆選択型の受信者に対して,送信者が繰り返し対面するオンライン学習フレームワークについて検討する。
オフラインモデルの慣習として、外部性やバイナリアクションのないケースに重点を置いています。
本稿では,損失関数を有限個に制限したオンライン学習問題に対処する一般的なオンライン降下スキームを提案する。
論文 参考訳（メタデータ） (2021-06-11T16:05:31Z) - Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions [54.25616645675032]
アルゴリズムが受信したフィードバックにランダムな遅延を伴うマルチアーマッド・バンドイット(MAB)問題について検討する。
報酬非依存の遅延設定は、報酬非依存の遅延設定と、報酬非依存の遅延設定に依存する可能性がある。
私たちの主な貢献は、それぞれの設定でほぼ最適に後悔するアルゴリズムです。
論文 参考訳（メタデータ） (2021-06-04T12:26:06Z) - Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。
最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
論文 参考訳（メタデータ） (2021-01-31T16:17:56Z) - Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。
我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
論文 参考訳（メタデータ） (2020-10-12T20:53:52Z) - Harnessing Wireless Channels for Scalable and Privacy-Preserving
Federated Learning [56.94644428312295]
無線接続は、フェデレートラーニング(FL)の実現に有効である
Channel randomnessperturbs 各ワーカはモデル更新をインバージョンし、複数のワーカはバンド幅に大きな干渉を発生させる。
A-FADMMでは、すべてのワーカーがモデル更新をアナログ送信を介して単一のチャンネルを使用してパラメータサーバにアップロードする。
これは通信帯域幅を節約するだけでなく、各ワーカーの正確なモデル更新軌跡を任意の盗聴者から隠蔽する。
論文 参考訳（メタデータ） (2020-07-03T16:31:15Z) - Learning Algorithms for Minimizing Queue Length Regret [5.8010446129208155]
パケットはランダムに送信機のキューに到着し、受信機に送信されるのを待ちます。
送信機の目的は、キュー内のパケット数を$T$のタイムスロットで最小化するために、最適なチャネルを素早く識別することである。
順序の最適値O(1)$キュー長の後悔を得られるキュー長ベースのポリシーのセットが存在することを示す。
論文 参考訳（メタデータ） (2020-05-11T15:50:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。