Fugu-MT 論文翻訳(概要): On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits

論文の概要: On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits

arxiv url: http://arxiv.org/abs/2211.17154v1
Date: Wed, 30 Nov 2022 16:46:41 GMT
ステータス: 処理完了
システム内更新日: 2022-12-01 16:39:42.281413
Title: On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits
Title（参考訳）: 後悔・最適協調的非stastic multi-armed banditsについて
Authors: Jialin Yi and Milan Vojnovic
Abstract要約: 我々は,FTRLアルゴリズムが,下界を一定要素に整合した個々の後悔の上界を有することを示す。また、エッジ遅延パラメータによるスケーリングに関して、適切な正規化器を持つFTRLアルゴリズムが最適であることを示す。
参考スコア（独自算出の注目度）: 4.721069729610892
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: We consider the nonstochastic multi-agent multi-armed bandit problem with agents collaborating via a communication network with delays. We show a lower bound for individual regret of all agents. We show that with suitable regularizers and communication protocols, a collaborative multi-agent \emph{follow-the-regularized-leader} (FTRL) algorithm has an individual regret upper bound that matches the lower bound up to a constant factor when the number of arms is large enough relative to degrees of agents in the communication graph. We also show that an FTRL algorithm with a suitable regularizer is regret optimal with respect to the scaling with the edge-delay parameter. We present numerical experiments validating our theoretical results and demonstrate cases when our algorithms outperform previously proposed algorithms.
Abstract（参考訳）: 我々は,遅延を伴う通信ネットワークを介して協調するエージェントによる,非確率的マルチエージェントマルチアームバンディット問題を考える。すべてのエージェントに対する個人の後悔に対する限界は低い。適切な正規化器と通信プロトコルを用いて、協調的マルチエージェント \emph{follow-the-regularized-leader} (FTRL) アルゴリズムは、通信グラフ内のエージェントの次数に対して腕の数が十分大きい場合に、下限の値に一致する個々の後悔上限を持つことを示す。また、エッジ遅延パラメータによるスケーリングに関して、適切な正規化器を持つFTRLアルゴリズムが最適であることを示す。提案手法が提案するアルゴリズムを上回った場合を数値実験で検証し,実例を示す。

関連論文リスト

DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
論文参考訳（メタデータ） (2024-03-25T22:49:56Z)
Multi-Armed Bandits with Abstention [62.749500564313834]
本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
論文参考訳（メタデータ） (2024-02-23T06:27:12Z)
Pure Exploration under Mediators' Feedback [63.56002444692792]
マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
論文参考訳（メタデータ） (2023-08-29T18:18:21Z)
On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
論文参考訳（メタデータ） (2023-05-01T06:46:22Z)
On-Demand Communication for Asynchronous Multi-Agent Bandits [43.3383282058292]
ODCはオンデマンド通信プロトコルであり、経験的なプル時間に基づいて各エージェントの通信を調整します。 ODCは、エージェントのプル時間が非常に均一であり、その通信の複雑さはエージェントの実証的なプル時間に依存する。
論文参考訳（メタデータ） (2023-02-15T03:32:33Z)
Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文参考訳（メタデータ） (2022-02-09T06:05:05Z)
Asymptotic Optimality for Decentralised Bandits [7.057937612386993]
多数の武器で盗賊問題に協力するエージェントを多数検討する。目標は、コミュニケーション制約のある環境で各エージェントの後悔を最小限にすることである。
論文参考訳（メタデータ） (2021-09-20T11:10:10Z)
Distributed Online Learning for Joint Regret with Communication Constraints [17.080853582489073]
コミュニケーションの制約との共同後悔のための分散オンライン学習環境を検討する。すべてのエージェントのサブセットは、グラフ内の隣人に$b$-bitメッセージを送信することができる。アルゴリズムのコンパレータ適応特性を利用して、最適なパーティションの集合から最適なパーティションを学習する。
論文参考訳（メタデータ） (2021-02-15T12:48:33Z)
Kernel Methods for Cooperative Multi-Agent Contextual Bandits [15.609414012418043]
協調的マルチエージェント意思決定は、遅延のあるネットワーク上で通信しながら、学習問題を協調的に解決するエージェントのグループを含む。エージェントが得られる報酬は、関連するカーネル再生ヒルベルト空間(RKHS)におけるコンテキストのイメージの任意の線形関数である。我々は, 年齢ごとの後悔に対して, ほぼ最適境界を与えるアルゴリズムであるtextscCoop- KernelUCBを提案する。
論文参考訳（メタデータ） (2020-08-14T07:37:44Z)
Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文参考訳（メタデータ） (2020-08-10T08:30:52Z)
The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits [20.259428328004738]
N$エージェントからなる分散マルチエージェントMulti Armed Bandit (MAB) のセットアップを検討する。我々のモデルでは、エージェントは任意の連結グラフ上で、ペアワイズなゴシップスタイルの通信を通じてメッセージを交換することで協調する。
論文参考訳（メタデータ） (2020-01-15T17:49:29Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。