論文の概要: 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 で非効率なアプローチで補完する。
実験の結果,従来の手法と比較し,効率的なアルゴリズムの有効性を確認した。
関連論文リスト
- Efficient and Optimal Policy Gradient Algorithm for Corrupted Multi-armed Bandits [29.845787788972594]
我々はSAMBAが最先端の$O(Klog T/Delta) + O(C/Delta)$ regret upper boundを達成することを示す。
また,SAMBAの有効性を実証するためにシミュレーションを行った。
論文 参考訳（メタデータ） (2025-02-19T23:16:18Z) - p-Mean Regret for Stochastic Bandits [52.828710025519996]
単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。
我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
論文 参考訳（メタデータ） (2024-12-14T08:38:26Z) - 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) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary
Dueling Bandits [27.279654173896372]
我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。
これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
論文 参考訳（メタデータ） (2021-11-06T16:46:55Z) - 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) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。