論文の概要: 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(参考訳): 汎用的な協調型マルチエージェント・マルチアーム・バンディット・モデルでは,各エージェントが有限個のアームに面し,中央制御器を介して他のエージェントと通信することができる。
このモデルにおける各エージェントの最適なアームは、最も期待される混合報酬を持つアームであり、各アームの混合報酬は、各エージェント間の報酬の重み付け平均であり、エージェント間の通信が不可欠である。
このコラボレーティブモデルの下では、最善の腕識別のための最適に近いサンプル複合体が知られているが、最適後悔の問題は未解決である。
本研究では,この問題に対処し,この協調帯域モデルの下での最適後悔境界付きアルゴリズムを提案する。
さらに,期待される通信ラウンドの一定数しか必要としないことを示す。
関連論文リスト
- Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
我々は,多武装盗賊の文脈における平等的課題であるEgalMABについて検討する。
UCBベースのポリシーEgalUCBを設計・分析し、累積的後悔の上限を確立する。
論文 参考訳(メタデータ) (2024-10-08T09:49:47Z) - Best Arm Identification with Minimal Regret [55.831935724659175]
最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。
エージェントの目標は、所定の信頼度で最高の腕を特定することである。
二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
論文 参考訳(メタデータ) (2024-09-27T16:46:02Z) - Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。
課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。
我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
論文 参考訳(メタデータ) (2024-08-20T13:57:00Z) - 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) - Near-Optimal Collaborative Learning in Bandits [15.456561090871244]
本稿では,各エージェントが有限個のアームに対向する一般マルチエージェントバンディットモデルを提案する。
ツイストは、各エージェントの最適なアームは最大の混合報酬を持つアームであり、アームの混合報酬は全てのエージェントに対するこのアームの報酬の重み付けの和である。
純粋探索のための近似アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-05-31T21:11:47Z) - Max-Min Grouped Bandits [48.62520520818357]
マルチアームバンディット問題であるmax-min grouped banditsを導入する。
ゴールは、最悪の腕が最高の平均報酬を持つグループを見つけることです。
この問題はレコメンデーションシステムのようなアプリケーションには関心がある。
論文 参考訳(メタデータ) (2021-11-17T01:59:15Z) - 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 [20.259428328004738]
N$エージェントからなる分散マルチエージェントMulti Armed Bandit (MAB) のセットアップを検討する。
我々のモデルでは、エージェントは任意の連結グラフ上で、ペアワイズなゴシップスタイルの通信を通じてメッセージを交換することで協調する。
論文 参考訳(メタデータ) (2020-01-15T17:49:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。