Fugu-MT 論文翻訳(概要): Asymptotic Optimality for Decentralised Bandits

論文の概要: Asymptotic Optimality for Decentralised Bandits

arxiv url: http://arxiv.org/abs/2109.09427v1
Date: Mon, 20 Sep 2021 11:10:10 GMT
ステータス: 処理完了
システム内更新日: 2021-09-22 01:06:22.762055
Title: Asymptotic Optimality for Decentralised Bandits
Title（参考訳）: 分散バンディットの漸近的最適性
Authors: Conor Newton, Ayalvadi Ganesh and Henry W. J. Reeve
Abstract要約: 多数の武器で盗賊問題に協力するエージェントを多数検討する。目標は、コミュニケーション制約のある環境で各エージェントの後悔を最小限にすることである。
参考スコア（独自算出の注目度）: 7.057937612386993
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We consider a large number of agents collaborating on a multi-armed bandit problem with a large number of arms. The goal is to minimise the regret of each agent in a communication-constrained setting. We present a decentralised algorithm which builds upon and improves the Gossip-Insert-Eliminate method of Chawla et al. arxiv:2001.05452. We provide a theoretical analysis of the regret incurred which shows that our algorithm is asymptotically optimal. In fact, our regret guarantee matches the asymptotically optimal rate achievable in the full communication setting. Finally, we present empirical results which support our conclusions
Abstract（参考訳）: 我々は,複数腕のバンディット問題に対して多数のエージェントが協力し,多数の腕を持つエージェントについて検討する。目的は、コミュニケーションに制約のある設定で各エージェントの後悔を最小限にすることである。本稿では,Chawla et al. arxiv:2001.05452のGossip-Insert-Eliminate法に基づく分散アルゴリズムを提案する。我々は,本アルゴリズムが漸近的に最適であることを示す後悔を理論的に解析する。実際、我々の後悔の保証は、完全なコミュニケーション設定で達成可能な漸近的に最適なレートと一致します。最後に、結論を支持する経験的結果を示す。

関連論文リスト

Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
論文参考訳（メタデータ） (2024-06-05T08:02:40Z)
Multi-Armed Bandits with Abstention [62.749500564313834]
本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
論文参考訳（メタデータ） (2024-02-23T06:27:12Z)
On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits [7.23389716633927]
我々は,FTRLアルゴリズムが,下界を一定要素に整合した個々の後悔の上界を有することを示す。また、エッジ遅延パラメータによるスケーリングに関して、適切な正規化器を持つFTRLアルゴリズムが最適であることを示す。
論文参考訳（メタデータ） (2022-11-30T16:46:41Z)
Federated Best Arm Identification with Heterogeneous Clients [62.36929749450298]
中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。予測停止時間上の上限が乗算定数までの下限と一致するアルゴリズム(ほぼ最適アルゴリズムの場合)について示す。本稿では,指数時間瞬間に通信する新しいアルゴリズムを提案し,ほぼ最適であることを実証する。
論文参考訳（メタデータ） (2022-10-14T13:09:11Z)
Decentralized Multi-Armed Bandit Can Outperform Classic Upper Confidence Bound: A Homogeneous Case over Strongly Connected Graphs [9.84486119211443]
本稿では、複数のエージェントのネットワークが同じアームの集合に直面する均質な分散化されたマルチアームバンディット問題について検討する。隣接関係を有向グラフで記述したマルチエージェントネットワークに対して,完全分散上界信頼度(UCB)アルゴリズムを提案する。
論文参考訳（メタデータ） (2021-11-22T01:05:52Z)
An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文参考訳（メタデータ） (2020-10-23T09:12:47Z)
Bayesian Algorithms for Decentralized Stochastic Bandits [12.350564981588063]
我々は,ネットワーク上で接続された$K$アームと$N$エージェントを用いた分散協調型マルチエージェントマルチエージェントバンディット問題について検討した。我々のモデルでは、各アームの報酬分布は全てのエージェントで同じであり、報酬はエージェントや時間経過とともに独立して引き出される。目標は、ネットワーク全体の平均的な累積的後悔を最小限にすることである。
論文参考訳（メタデータ） (2020-10-20T19:14:20Z)
Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文参考訳（メタデータ） (2020-08-10T08:30:52Z)
Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文参考訳（メタデータ） (2020-06-29T14:25:51Z)

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