Fugu-MT 論文翻訳(概要): Optimal Fair Multi-Agent Bandits

論文の概要: Optimal Fair Multi-Agent Bandits

arxiv url: http://arxiv.org/abs/2306.04498v1
Date: Wed, 7 Jun 2023 15:05:53 GMT
ステータス: 処理完了
システム内更新日: 2023-06-08 13:52:00.534235
Title: Optimal Fair Multi-Agent Bandits
Title（参考訳）: 最適フェアマルチエージェントバンド
Authors: Amir Leshem
Abstract要約: We provide a algorithm with regret $Oleft(N3 log N log T right)$ (suming bounded rewards, with unknown bounds) これは、$O(log T loglog T)$を後悔し、エージェントの数に指数関数的依存した以前の結果を大幅に改善する。
参考スコア（独自算出の注目度）: 22.722051730901452
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper, we study the problem of fair multi-agent multi-arm bandit learning when agents do not communicate with each other, except collision information, provided to agents accessing the same arm simultaneously. We provide an algorithm with regret $O\left(N^3 \log N \log T \right)$ (assuming bounded rewards, with unknown bound). This significantly improves previous results which had regret of order $O(\log T \log\log T)$ and exponential dependence on the number of agents. The result is attained by using a distributed auction algorithm to learn the sample-optimal matching, a new type of exploitation phase whose length is derived from the observed samples, and a novel order-statistics-based regret analysis. Simulation results present the dependence of the regret on $\log T$.
Abstract（参考訳）: 本稿では,同一のアームに同時にアクセスするエージェントに対して提供される衝突情報を除いて,エージェント同士が通信しない場合の,公平なマルチエージェントマルチアームバンディット学習の問題について検討する。後悔した$o\left(n^3 \log n \log t \right)$のアルゴリズムを提供する。これは、o(\log t \log \log t)$の順序とエージェント数への指数依存を後悔した以前の結果を大幅に改善する。その結果、分散オークションアルゴリズムを用いてサンプル-最適マッチング、観察されたサンプルから長さが導出される新しいタイプの搾取フェーズ、新しいオーダー統計に基づく後悔分析が得られた。シミュレーションの結果は、$\log T$に対する後悔の依存性を示す。

関連論文リスト

Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文参考訳（メタデータ） (2024-05-09T17:40:09Z)
Refined Sample Complexity for Markov Games with Independent Linear Function Approximation [49.5660193419984]
マルコフゲーム(MG)はマルチエージェント強化学習(MARL)の重要なモデルである本稿では、WangらによるAVLPRフレームワークを改良し(2023年)、最適部分ギャップの悲観的推定を設計する。マルチエージェントの呪いに取り組み、最適な$O(T-1/2)収束率を達成し、同時に$textpoly(A_max)$依存性を避ける最初のアルゴリズムを与える。
論文参考訳（メタデータ） (2024-02-11T01:51:15Z)
Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis [5.02063914741425]
Zhang, Johansson, Li が導入したグラフバンディット問題のマルチエージェント拡張として,マルチエージェントグラフバンディット問題を定式化する。上信頼境界(UCB)に基づく学習アルゴリズムであるMulti-G-UCBを提案し、T$のステップに対する期待された後悔が$O(gamma Nlog(T)[sqrtKT + DK])$で束縛されていることを証明した。
論文参考訳（メタデータ） (2024-01-18T21:36:17Z)
Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs [11.024467775280193]
マルチエージェントマルチアーム・バンドイット(MAMAB)問題について検討し,$m$エージェントを$rho$オーバーラップするグループに分解する。そこで本稿では,MATS の効率的な変種として$epsilon$-exploring Multi-Agent Thompson Sampling (epsilon$-MATS) アルゴリズムを提案する。我々は、$epsilon$-MATSが、時間地平線と局所アームサイズの両方においてサブ線形である最悪の頻繁な後悔境界を達成することを証明した。
論文参考訳（メタデータ） (2023-12-24T21:41:01Z)
Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
論文参考訳（メタデータ） (2023-11-22T06:06:54Z)
Robust Multi-Agent Bandits Over Undirected Graphs [26.26185074977412]
我々は、正直なエージェントがネットワーク上で協力し、後悔を最小限に抑えるマルチエージェント・マルチアーム・バンディット・セッティングを考える。完全なグラフのケース以上に状況が悪くなることを示す。我々は,$i$-thエージェントが任意の連結および無向グラフ上で$O(d_textmal(i) + K/n) log(T)/Delta)$を後悔する新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-02-28T20:21:55Z)
Distributed Bandits with Heterogeneous Agents [38.90376765616447]
本稿では、M$エージェントが協力して$K$武器の盗賊問題を解くマルチエージェントの盗賊設定に取り組む。本稿では,ucbo と AAE の2つの学習アルゴリズムを提案する。 Oleft(sum_i:tildeDelta_i>0 log T/tildeDelta_iright)$, $tildeDelta_i$は報酬平均の最小部分最適差である。
論文参考訳（メタデータ） (2022-01-23T20:04:15Z)
Mixability made efficient: Fast online multiclass logistic regression [68.8204255655161]
我々は、混合性は最適な後悔を伴うアルゴリズムを得るための強力なツールであることを示した。結果として得られる手法は、しばしば計算の複雑さに悩まされ、実用性が低下した。
論文参考訳（メタデータ） (2021-10-08T08:22:05Z)
Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
シャッフルモデルにおけるマルチアームバンディット(MAB)問題に対して,$(varepsilon,delta)$-differentially privateアルゴリズムを提案する。我々の上限は、集中モデルにおいて最もよく知られたアルゴリズムの後悔とほぼ一致し、局所モデルにおいて最もよく知られたアルゴリズムを著しく上回っている。
論文参考訳（メタデータ） (2021-06-05T14:11:01Z)
Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文参考訳（メタデータ） (2020-10-22T19:14:37Z)

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