論文の概要: An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret

• arxiv url: http://arxiv.org/abs/2209.11817v1
• Date: Fri, 23 Sep 2022 19:15:43 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-27 17:53:43.967866
• Title: An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret
• Title（参考訳）: 低レギュレントなマルチエージェントマルチArmed Banditの効率的なアルゴリズム
• Authors: Matthew Jones, Huy L\^e Nguyen, Thy Nguyen
• Abstract要約: 従来の非効率アルゴリズムよりも後悔度が低い新しいアルゴリズムを提案する。 N$エージェント、$K$アーム、および$T$ラウンドの場合、我々のアプローチは、$tildeO(sqrtNKT + NK)$という残念な境界を持つ。 また、効率的なアルゴリズムを $tildeO(sqrtKT + N2K)$ regret で非効率なアプローチで補完する。
• 参考スコア（独自算出の注目度）: 7.059472280274009
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently a multi-agent variant of the classical multi-armed bandit was proposed to tackle fairness issues in online learning. Inspired by a long line of work in social choice and economics, the goal is to optimize the Nash social welfare instead of the total utility. Unfortunately previous algorithms either are not efficient or achieve sub-optimal regret in terms of the number of rounds $T$. We propose a new efficient algorithm with lower regret than even previous inefficient ones. For $N$ agents, $K$ arms, and $T$ rounds, our approach has a regret bound of $\tilde{O}(\sqrt{NKT} + NK)$. This is an improvement to the previous approach, which has regret bound of $\tilde{O}( \min(NK, \sqrt{N} K^{3/2})\sqrt{T})$. We also complement our efficient algorithm with an inefficient approach with $\tilde{O}(\sqrt{KT} + N^2K)$ regret. The experimental findings confirm the effectiveness of our efficient algorithm compared to the previous approaches.
• Abstract（参考訳）: 近年,オンライン学習における公平性問題に取り組むために,古典的多腕バンディットのマルチエージェント版が提案されている。 社会的選択と経済学における長い仕事に着想を得て、目標は全効用ではなくナッシュ社会福祉を最適化することである。 残念なことに、以前のアルゴリズムは効率的でないか、ラウンド数で$T$の準最適後悔を達成するかのいずれかである。 従来の非効率アルゴリズムよりも後悔度が低い新しいアルゴリズムを提案する。 N$エージェント、$K$アーム、および$T$ラウンドの場合、我々のアプローチは、$\tilde{O}(\sqrt{NKT} + NK)$の後悔の束を持つ。 これは以前のアプローチの改善であり、$\tilde{O}( \min(NK, \sqrt{N} K^{3/2})\sqrt{T})$を後悔する。 また、効率的なアルゴリズムを $\tilde{O}(\sqrt{KT} + N^2K)$ regret で非効率なアプローチで補完する。 実験の結果,従来の手法と比較し,効率的なアルゴリズムの有効性を確認した。

関連論文リスト

• Achieving Tractable Minimax Optimal Regret in Average Reward MDPs [19.663336027878408]
  我々は,$widetildemathrmO(sqrtmathrmsp(h*) S A T)$のミニマックス最適後悔を伴う最初の抽出可能なアルゴリズムを提案する。 注目すべきは、我々のアルゴリズムは$mathrmsp(h*)$に関する事前情報を必要としないことである。
  論文  参考訳（メタデータ） (2024-06-03T11:53:44Z)
• Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback [30.337826346496385]
  線形マルコフ決定過程におけるオンライン強化学習について,敵対的損失と帯域幅フィードバックを用いて検討した。 既存の手法と比較して、後悔性能を向上させるアルゴリズムを2つ導入する。
  論文  参考訳（メタデータ） (2023-10-17T19:43:37Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem [13.69077222007053]
  従来のマルチアームバンディット問題(英語版)のバリエーションである$K$のデュエルリングバンディット問題(英語版)について検討し、フィードバックをペア比較の形で得られる。 我々は、$O(K2log(K)) + O(Klog(T))$ in $O(log(T))$ rounds を後悔する。 実世界の様々なデータセットに対する計算実験において、$O(log(T))$ラウンドを用いたアルゴリズムが完全に同じ性能を達成することが観察された。
  論文  参考訳（メタデータ） (2022-09-25T00:23:55Z)
• 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)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards [59.559028338399855]
  我々は,行動セットと敵意の報酬を伴って睡眠中の盗賊の問題を考察する。 本稿では,EXP3にインスパイアされた新しい計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-14T00:41:26Z)

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

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