論文の概要: Robust Multi-Agent Bandits Over Undirected Graphs

• arxiv url: http://arxiv.org/abs/2203.00076v1
• Date: Mon, 28 Feb 2022 20:21:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-02 13:43:57.006362
• Title: Robust Multi-Agent Bandits Over Undirected Graphs
• Title（参考訳）: 非向グラフ上のロバストマルチエージェントバンディット
• Authors: Daniel Vial, Sanjay Shakkottai, R. Srikant
• Abstract要約: 我々は、正直なエージェントがネットワーク上で協力し、後悔を最小限に抑えるマルチエージェント・マルチアーム・バンディット・セッティングを考える。 完全なグラフのケース以上に状況が悪くなることを示す。 我々は,$i$-thエージェントが任意の連結および無向グラフ上で$O(d_textmal(i) + K/n) log(T)/Delta)$を後悔する新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 26.26185074977412
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a multi-agent multi-armed bandit setting in which $n$ honest agents collaborate over a network to minimize regret but $m$ malicious agents can disrupt learning arbitrarily. Assuming the network is the complete graph, existing algorithms incur $O( (m + K/n) \log (T) / \Delta )$ regret in this setting, where $K$ is the number of arms and $\Delta$ is the arm gap. For $m \ll K$, this improves over the single-agent baseline regret of $O(K\log(T)/\Delta)$. In this work, we show the situation is murkier beyond the case of a complete graph. In particular, we prove that if the state-of-the-art algorithm is used on the undirected line graph, honest agents can suffer (nearly) linear regret until time is doubly exponential in $K$ and $n$. In light of this negative result, we propose a new algorithm for which the $i$-th agent has regret $O( ( d_{\text{mal}}(i) + K/n) \log(T)/\Delta)$ on any connected and undirected graph, where $d_{\text{mal}}(i)$ is the number of $i$'s neighbors who are malicious. Thus, we generalize existing regret bounds beyond the complete graph (where $d_{\text{mal}}(i) = m$), and show the effect of malicious agents is entirely local (in the sense that only the $d_{\text{mal}}(i)$ malicious agents directly connected to $i$ affect its long-term regret).
• Abstract（参考訳）: マルチエージェントのマルチアームバンディット設定では、$n$の正直なエージェントがネットワーク上で協力して後悔を最小限に抑えるが、$m$の悪意のあるエージェントは、任意の学習を妨害することができる。 ネットワークが完全なグラフであると仮定すると、既存のアルゴリズムは$O( (m + K/n) \log (T) / \Delta )$ regret in this set, where $K$ is the number of arms and $\Delta$ is the arm gap。 m \ll K$の場合、これは$O(K\log(T)/\Delta)$の単一エージェントベースラインの後悔よりも改善される。 本稿では,完全グラフの場合よりも状況が乱雑であることを示す。 特に、最先端のアルゴリズムが無向線グラフで使われている場合、正直なエージェントは(ほぼ)線形後悔に苦しみ、時間が2倍の指数関数的に$k$と$n$となる。 この負の結果を踏まえて、$i$-th エージェントは任意の連結かつ無向グラフに対して $o((d_{\text{mal}}(i) + k/n) \log(t)/\delta)$ を後悔し、$d_{\text{mal}}(i)$ は悪意のある$i$ の隣人の数である。 したがって、既存の後悔の限度を完全なグラフを超えて一般化し(ここでは$d_{\text{mal}}(i) = m$)、悪意あるエージェントの効果が完全に局所的であることを示す($d_{\text{mal}}(i)$ 悪質なエージェントが$i$に直接接続された場合のみ、その長期的な後悔に影響する)。

関連論文リスト

• On Interpolating Experts and Multi-Armed Bandits [1.9497955504539408]
  我々は、$mathbfm$-MABに対して厳密なミニマックス後悔境界を証明し、その純粋な探索バージョンである$mathbfm$-BAIに対して最適なPACアルゴリズムを設計する。 その結果、フィードバックグラフのいくつかのファミリに対して、厳密なミニマックス後悔境界を得た。
  論文  参考訳（メタデータ） (2023-07-14T10:38:30Z)
• Fair Multi-Agent Bandits [14.614647884175657]
  残念な$Oleft(N3 log fracBDelta f(log T) log T right)$, where $f(t)$ は infinity に $t$ で分岐する任意の関数である。 これにより、オーダー$O(f(log T) log T )$と同じ上限を持つ前の結果を大幅に改善するが、エージェントの数に指数関数的に依存する。
  論文  参考訳（メタデータ） (2023-06-07T15:05:53Z)
• Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
  ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。 複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
  論文  参考訳（メタデータ） (2023-06-05T15:35:00Z)
• UniRank: Unimodal Bandit Algorithm for Online Ranking [0.0]
  We create a algorithm with a expected regret matching $O(fracLlog(L)Deltalog(T))$ with $2L$ player, $T$ and a least reward gap $Delta$。 いくつかの実験結果は、これらの理論的な結果が実際に裏付けられていることを示している。
  論文  参考訳（メタデータ） (2022-08-02T15:01:33Z)
• Unimodal Mono-Partite Matching in a Bandit Setting [0.0]
  We create a algorithm with a expected regret matching $O(fracLlog(L)Deltalog(T))$ with $2L$ player, $T$ and a least reward gap $Delta$。 いくつかの実験結果は、これらの理論的な結果が実際に裏付けられていることを示している。
  論文  参考訳（メタデータ） (2022-08-02T14:55:50Z)
• Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
  我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。 我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2022-03-29T15:27:13Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
  シャッフルモデルにおけるマルチアームバンディット(MAB)問題に対して,$(varepsilon,delta)$-differentially privateアルゴリズムを提案する。 我々の上限は、集中モデルにおいて最もよく知られたアルゴリズムの後悔とほぼ一致し、局所モデルにおいて最もよく知られたアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2021-06-05T14:11:01Z)
• Communication Efficient Parallel Reinforcement Learning [34.77250498401055]
  我々は、$m$エージェントが$s$状態と$a$アクションを持つ$m$同一および独立環境と相互作用する問題を考える。 我々はエージェントが不適切なコミュニケーションラウンドで後悔を最小限に抑えるアルゴリズムを見つけることを目的としている。
  論文  参考訳（メタデータ） (2021-02-22T02:46:36Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。