論文の概要: Optimal Regret Bounds for Collaborative Learning in Bandits
- arxiv url: http://arxiv.org/abs/2312.09674v1
- Date: Fri, 15 Dec 2023 10:36:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-18 16:13:51.557220
- Title: Optimal Regret Bounds for Collaborative Learning in Bandits
- Title(参考訳): バンディットにおける協調学習のための最適後悔限度
- Authors: Amitis Shidani and Sattar Vakili
- Abstract要約: 一般的な協調型マルチエージェント・マルチアーム・バンディット・モデルにおける後悔について考察する。
このモデルの下では、順序最適後悔境界を持つ最初のアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 10.76667043339504
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider regret minimization in a general collaborative multi-agent
multi-armed bandit model, in which each agent faces a finite set of arms and
may communicate with other agents through a central controller. The optimal arm
for each agent in this model is the arm with the largest expected mixed reward,
where the mixed reward of each arm is a weighted average of its rewards across
all agents, making communication among agents crucial. While near-optimal
sample complexities for best arm identification are known under this
collaborative model, the question of optimal regret remains open. In this work,
we address this problem and propose the first algorithm with order optimal
regret bounds under this collaborative bandit model. Furthermore, we show that
only a small constant number of expected communication rounds is needed.
- Abstract(参考訳): 汎用的な協調型マルチエージェント・マルチアーム・バンディット・モデルでは,各エージェントが有限個のアームに面し,中央制御器を介して他のエージェントと通信することができる。
このモデルにおける各エージェントの最適なアームは、最も期待される混合報酬を持つアームであり、各アームの混合報酬は、各エージェント間の報酬の重み付け平均であり、エージェント間の通信が不可欠である。
このコラボレーティブモデルの下では、最善の腕識別のための最適に近いサンプル複合体が知られているが、最適後悔の問題は未解決である。
本研究では,この問題に対処し,この協調帯域モデルの下での最適後悔境界付きアルゴリズムを提案する。
さらに,期待される通信ラウンドの一定数しか必要としないことを示す。
関連論文リスト
- Byzantine-Resilient Decentralized Multi-Armed Bandits [25.499420566469098]
エージェント間の情報混合ステップを不整合および極端な値の切り離しで融合するアルゴリズムを開発する。
このフレームワークは、コンピュータネットワークの攻撃者をモデル化したり、攻撃的なコンテンツをレコメンデーターシステムに攻撃したり、金融市場のマニピュレータとして利用することができる。
論文 参考訳(メタデータ) (2023-10-11T09:09:50Z) - 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) - Near-Optimal Collaborative Learning in Bandits [15.456561090871244]
本稿では,各エージェントが有限個のアームに対向する一般マルチエージェントバンディットモデルを提案する。
ツイストは、各エージェントの最適なアームは最大の混合報酬を持つアームであり、アームの混合報酬は全てのエージェントに対するこのアームの報酬の重み付けの和である。
純粋探索のための近似アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-05-31T21:11:47Z) - Best Arm Identification under Additive Transfer Bandits [49.69203462561861]
提案手法は, 未知であるにもかかわらず, ソースとターゲットMABインスタンスの間には, 付加的な関係があることが知られている。
本稿では,LUCBスタイルのアルゴリズムを理論的に解析し,高い確率で$epsilon$-optimal target armを同定する。
論文 参考訳(メタデータ) (2021-12-08T02:20:18Z) - Max-Min Grouped Bandits [48.62520520818357]
マルチアームバンディット問題であるmax-min grouped banditsを導入する。
ゴールは、最悪の腕が最高の平均報酬を持つグループを見つけることです。
この問題はレコメンデーションシステムのようなアプリケーションには関心がある。
論文 参考訳(メタデータ) (2021-11-17T01:59:15Z) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳(メタデータ) (2021-01-21T10:35:09Z) - Robust Multi-Agent Multi-Armed Bandits [26.26185074977412]
最近の研究によると、$Kの武器を持った盗賊の独立した事例に直面しているエージェントが、後悔を減らすために協力できることが示されている。
我々は、悪質なエージェントの振る舞いを仮定することなく、$m$が$K$よりも小さいと仮定すると、このアルゴリズムに対するコラボレーションは本当に後悔を減らせることを示した。
論文 参考訳(メタデータ) (2020-07-07T22:27:30Z) - Tight Lower Bounds for Combinatorial Multi-Armed Bandits [72.56064196252498]
Combinatorial Multi-Armed Bandit 問題は、エージェントが各ラウンドで一組の腕を選択する、シーケンシャルな意思決定問題である。
最近提案されたGini重み付き滑らか度パラメータが単調報酬関数の下限を決定することを示す。
論文 参考訳(メタデータ) (2020-02-13T08:53:43Z) - The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits [19.457336747088593]
N$エージェントからなる分散マルチエージェントMulti Armed Bandit (MAB) のセットアップを検討する。
我々のモデルでは、エージェントは任意の連結グラフ上で、ペアワイズなゴシップスタイルの通信を通じてメッセージを交換することで協調する。
論文 参考訳(メタデータ) (2020-01-15T17:49:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。