論文の概要: Decentralized Learning in Online Queuing Systems
- arxiv url: http://arxiv.org/abs/2106.04228v1
- Date: Tue, 8 Jun 2021 10:10:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-09 16:06:27.569079
- Title: Decentralized Learning in Online Queuing Systems
- Title（参考訳）: オンラインキューシステムにおける分散学習
- Authors: Flore Sentenac and Etienne Boursier and Vianney Perchet
- Abstract要約: オンラインキューシステムは、パケットを異なるレートで受信するキューで構成されている。
集中型の場合、サービスレートと到着率の比率が1ドル以上である限り、蓄積パケットの数は制限されているままである。
本稿では,レート比が1ドル以上である限り,システムの安定性を保証する最初の学習分散型アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 27.18971095426405
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by packet routing in computer networks, online queuing systems are
composed of queues receiving packets at different rates. Repeatedly, they send
packets to servers, each of them treating only at most one packet at a time. In
the centralized case, the number of accumulated packets remains bounded (i.e.,
the system is \textit{stable}) as long as the ratio between service rates and
arrival rates is larger than $1$. In the decentralized case, individual
no-regret strategies ensures stability when this ratio is larger than $2$. Yet,
myopically minimizing regret disregards the long term effects due to the
carryover of packets to further rounds. On the other hand, minimizing long term
costs leads to stable Nash equilibria as soon as the ratio exceeds
$\frac{e}{e-1}$. Stability with decentralized learning strategies with a ratio
below $2$ was a major remaining question. We first argue that for ratios up to
$2$, cooperation is required for stability of learning strategies, as selfish
minimization of policy regret, a \textit{patient} notion of regret, might
indeed still be unstable in this case. We therefore consider cooperative queues
and propose the first learning decentralized algorithm guaranteeing stability
of the system as long as the ratio of rates is larger than $1$, thus reaching
performances comparable to centralized strategies.
- Abstract（参考訳）: コンピュータネットワークにおけるパケットルーティングにより、オンラインキューシステムは異なるレートでパケットを受け取るキューで構成されている。
繰り返し、彼らはパケットをサーバに送信し、それぞれが一度に1つのパケットだけを処理します。
集中型の場合、蓄積されたパケットの数は、サービスレートと到着率の比率が1ドル以上である限り(つまり、システムは \textit{stable} である)有界のままである。
分散化の場合、個別の非回帰戦略は、この比率が2ドルより大きい場合の安定性を保証する。
しかし、後悔の最小化は、パケットのさらなるラウンドへの輸送による長期的な影響を無視している。
一方、長期コストの最小化は、比が$\frac{e}{e-1}$を超えるとすぐに安定なナッシュ均衡をもたらす。
2ドル未満の分散学習戦略による安定性は、依然として大きな疑問であった。
私たちはまず,2ドルまでの比率に対して,政策後悔の自発的最小化,すなわちtextit{patient} という概念がいまだに不安定であるように,学習戦略の安定性には協力が必要である,と論じます。
そこで我々は協調待ち行列を考察し,レート比が1ドルを超える限りシステムの安定性を保証する最初の学習分散アルゴリズムを提案し,集中型戦略に匹敵する性能を達成する。
関連論文リスト
- On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
非凹面ゲームはゲーム理論と最適化に重大な課題をもたらす。
Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。
また,オンライングラディエントDescentは,非自明な状況下で効率よく$Phi$-equilibriaを近似できることを示した。
論文 参考訳（メタデータ） (2024-03-13T01:51:30Z) - Order-Optimal Regret in Distributed Kernel Bandits using Uniform
Sampling with Shared Randomness [9.731329071569018]
我々はN$エージェントが未知の報酬関数を協調的に最大化する分散カーネルの帯域を考える。
我々は,通信コストが$N$と$T$に比例する,最適な後悔順序を達成するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-02-20T17:49:10Z) - Simple Opinion Dynamics for No-Regret Learning [38.61048016579232]
分散GOSSIPモデルにおける協調的マルチエージェントバンディット設定について検討する。
この設定のために、メモリレスおよび時間に依存しないプロトコルのファミリーを導入・分析する。
定常的な報酬設定のために、これらの単純なプロトコルが世界の最高の振る舞いを示すことを初めて証明する。
論文 参考訳（メタデータ） (2023-06-14T17:59:15Z) - Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
論文 参考訳（メタデータ） (2023-01-31T03:49:00Z) - Decentralized model-free reinforcement learning in stochastic games with
average-reward objective [1.9852463786440127]
本アルゴリズムは,次数$T3/4$のサブ線形高確率後悔と次数$T2/3$のサブ線形高確率後悔を実現する。
本アルゴリズムは,従来の手法に比べて計算量が少なく,メモリスペースも少ない。
論文 参考訳（メタデータ） (2023-01-13T15:59:53Z) - Communication-Efficient Topologies for Decentralized Learning with
$O(1)$ Consensus Rate [35.698182247676414]
分散最適化は分散学習における新たなパラダイムであり、エージェントは中央サーバを使わずにピアツーピア通信によってネットワーク全体のソリューションを実現する。
エージェントの情報が混在する速度によって,ネットワーク全体のソリューションに到達するためのイテレーションの総数が影響を受けることを示す。
本稿では,(ほぼ)一定の等級とネットワークサイズに依存しないコンセンサス率を有する新しいトポロジであるEquiTopoを提案する。
論文 参考訳（メタデータ） (2022-10-14T15:02:01Z) - Quantization for decentralized learning under subspace constraints [61.59416703323886]
エージェントがサブスペース制約を最小化するために個々のコスト関数を持つ分散最適化問題を考察する。
本稿では,エージェントが確率化量子化器を用いて推定値を圧縮する適応分散型戦略を提案し,検討する。
この分析は、量子化ノイズのいくつかの一般的な条件下では、平均二乗誤差と平均ビットレートの両方で戦略が安定であることを示している。
論文 参考訳（メタデータ） (2022-09-16T09:38:38Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - Better than the Best: Gradient-based Improper Reinforcement Learning for
Network Scheduling [60.48359567964899]
パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。
我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
論文 参考訳（メタデータ） (2021-05-01T10:18:34Z) - Decentralized Multi-Agent Linear Bandits with Safety Constraints [31.67685495996986]
本研究では,N$エージェントのネットワークが協調して線形帯域最適化問題を解く分散線形帯域幅について検討する。
ネットワーク全体の累積的後悔を最小限に抑える完全分散アルゴリズム DLUCB を提案する。
私たちのアイデアは、より困難な、安全な盗賊の設定にもかかわらず、自然界に広まっています。
論文 参考訳（メタデータ） (2020-12-01T07:33:00Z) - Stochastic Shortest Path with Adversarially Changing Costs [57.90236104782219]
最短経路 (SSP) は計画と制御においてよく知られた問題である。
また, 時間とともにコストの逆変化を考慮に入れた逆SSPモデルを提案する。
我々は、この自然な逆SSPの設定を最初に検討し、それに対するサブ線形後悔を得る。
論文 参考訳（メタデータ） (2020-06-20T12:10:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。