論文の概要: Stability and Learning in Strategic Queuing Systems
- arxiv url: http://arxiv.org/abs/2003.07009v1
- Date: Mon, 16 Mar 2020 03:59:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-23 04:08:32.984443
- Title: Stability and Learning in Strategic Queuing Systems
- Title（参考訳）: 戦略的キューシステムにおける安定性と学習
- Authors: Jason Gaitonde, Eva Tardos
- Abstract要約: ゲームモデリングキューイングシステムのコンテキストにおける現象について検討する。
ルータはサーバと競合し、サービスを取得しないパケットは将来のラウンドで再送される。
本稿では,キューイングシステムにおける自己学習の効果を初めて研究する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bounding the price of anarchy, which quantifies the damage to social welfare
due to selfish behavior of the participants, has been an important area of
research. In this paper, we study this phenomenon in the context of a game
modeling queuing systems: routers compete for servers, where packets that do
not get service will be resent at future rounds, resulting in a system where
the number of packets at each round depends on the success of the routers in
the previous rounds. We model this as an (infinitely) repeated game, where the
system holds a state (number of packets held by each queue) that arises from
the results of the previous round. We assume that routers satisfy the no-regret
condition, e.g. they use learning strategies to identify the server where their
packets get the best service.
Classical work on repeated games makes the strong assumption that the
subsequent rounds of the repeated games are independent (beyond the influence
on learning from past history). The carryover effect caused by packets
remaining in this system makes learning in our context result in a highly
dependent random process. We analyze this random process and find that if the
capacity of the servers is high enough to allow a centralized and knowledgeable
scheduler to get all packets served even with double the packet arrival rate,
and queues use no-regret learning algorithms, then the expected number of
packets in the queues will remain bounded throughout time, assuming older
packets have priority. This paper is the first to study the effect of selfish
learning in a queuing system, where the learners compete for resources, but
rounds are not all independent: the number of packets to be routed at each
round depends on the success of the routers in the previous rounds.
- Abstract（参考訳）: 参加者の利己的な行動による社会福祉への損害を定量化する無政府主義の価格設定は重要な研究分野である。
本稿では,この現象をゲームモデリングキューシステムという文脈で考察する: ルータはサーバと競合し,サービスを受けないパケットは今後のラウンドで再送され,各ラウンドにおけるパケットの数が前ラウンドでのルータの成功に依存するシステムとなる。
我々はこれを(無限に)繰り返しゲームとしてモデル化し、システムが前のラウンドの結果から生じる状態(各キューが保持するパケット数)を保持する。
ルータは、例えば、学習戦略を使って、パケットが最適なサービスを得るサーバを特定するなど、非レグレット条件を満たすと仮定する。
繰り返しゲームに関する古典的な研究は、後続のラウンドが(過去の歴史からの学習の影響に加えて)独立である、という強い仮定を下している。
このシステムに残されているパケットによって引き起こされるキャリーオーバー効果は、我々のコンテキストでの学習を高度に依存するランダムプロセスへと導く。
このランダムなプロセスを分析し、もしサーバのキャパシティが高くて、中央集権的で知識のあるスケジューラがパケット到着率の2倍でも全てのパケットを配信でき、キューが非Regret学習アルゴリズムを使用していれば、古いパケットが優先されていると仮定して、待ち行列内のパケットの数は時間とともに制限される。
本稿では,学習者がリソースを競うキューシステムにおいて,自己学習の効果を初めて研究した。しかしラウンドは必ずしも独立ではない。各ラウンドにおいてルーティングされるパケット数は,前ラウンドにおけるルータの成功に依存する。
関連論文リスト
- Full Stage Learning to Rank: A Unified Framework for Multi-Stage Systems [40.199257203898846]
我々は,多段階システム,すなわちGPRP(Generalized Probability Ranking Principle)のための改良されたランキング原理を提案する。
GPRPは、システムパイプラインの各ステージにおける選択バイアスと、ユーザの基本的な関心の両方を強調している。
我々の中核的な考え方は、まず次の段階における選択バイアスを推定し、次に下流モジュールの選択バイアスに最もよく適合するランキングモデルを学ぶことである。
論文 参考訳（メタデータ） (2024-05-08T06:35:04Z) - Distributed No-Regret Learning for Multi-Stage Systems with End-to-End Bandit Feedback [7.8539454948826375]
本稿では,エンド・ツー・エンドの帯域フィードバックを用いたマルチステージシステムについて検討する。
各ジョブは、結果を生成する前に、異なるエージェントによって管理される複数のステージを通過する必要があります。
本研究の目的は,敵対的環境におけるサブ線形後悔を実現するために,分散オンライン学習アルゴリズムを開発することである。
論文 参考訳（メタデータ） (2024-04-06T05:34:12Z) - Impact of Decentralized Learning on Player Utilities in Stackelberg Games [57.08270857260131]
多くの2エージェントシステムでは、各エージェントは別々に学習し、2つのエージェントの報酬は完全に一致しない。
分散学習を用いたStackelbergゲームとしてこれらのシステムをモデル化し、標準後悔ベンチマークが少なくとも1人のプレイヤーにとって最悪の線形後悔をもたらすことを示す。
我々は,これらのベンチマークに関して,両プレイヤーにとってほぼ最適な$O(T2/3)を後悔するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-02-29T23:38:28Z) - A Study of Forward-Forward Algorithm for Self-Supervised Learning [65.268245109828]
本研究では,自己指導型表現学習におけるフォワードとバックプロパゲーションのパフォーマンスについて検討する。
我々の主な発見は、フォワードフォワードアルゴリズムが(自己教師付き)トレーニング中にバックプロパゲーションに相容れないように機能するのに対し、転送性能は研究されたすべての設定において著しく遅れていることである。
論文 参考訳（メタデータ） (2023-09-21T10:14:53Z) - Learning While Scheduling in Multi-Server Systems with Unknown
Statistics: MaxWeight with Discounted UCB [18.898514227870926]
本稿では、複数のサーバと複数のタイプのジョブを持つマルチサーバシステムについて考察する。
目標は、処理時間の統計を知ることなく、サーバ上のジョブをスケジュールすることだ。
我々は,MaxWeightスケジューリングポリシと割引された高信頼度境界(UCB)を組み合わせることで,統計を同時に学習し,ジョブをサーバにスケジュールするアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-09-02T15:37:02Z) - No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。
提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。
本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
論文 参考訳（メタデータ） (2022-01-30T06:10:04Z) - Decentralized Learning in Online Queuing Systems [27.18971095426405]
オンラインキューシステムは、パケットを異なるレートで受信するキューで構成されている。
集中型の場合、サービスレートと到着率の比率が1ドル以上である限り、蓄積パケットの数は制限されているままである。
本稿では,レート比が1ドル以上である限り,システムの安定性を保証する最初の学習分散型アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-08T10:10:21Z) - Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。
対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。
我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
論文 参考訳（メタデータ） (2020-07-10T09:33:05Z) - Learning from Learners: Adapting Reinforcement Learning Agents to be
Competitive in a Card Game [71.24825724518847]
本稿では,競争力のあるマルチプレイヤーカードゲームの現実的な実装を学習・プレイするために,一般的な強化学習アルゴリズムをどのように適用できるかについて検討する。
本研究は,学習エージェントに対して,エージェントが競争力を持つことの学習方法を評価するための特定のトレーニングと検証ルーチンを提案し,それらが相互の演奏スタイルにどのように適応するかを説明する。
論文 参考訳（メタデータ） (2020-04-08T14:11:05Z) - Predictive Bandits [68.8204255655161]
我々は,予測的盗賊と呼ばれる,新たな盗賊問題を紹介し,研究する。
各ラウンドで、意思決定者はまず、特定の武器の報酬に関する情報を集めるかどうかを決定する。
意思決定者は、ラウンドで実際にプレイされる腕を選択する。
論文 参考訳（メタデータ） (2020-04-02T17:12:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。