論文の概要: No-Regret Learning for Fair Multi-Agent Social Welfare Optimization

• arxiv url: http://arxiv.org/abs/2405.20678v1
• Date: Fri, 31 May 2024 08:21:11 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-03 15:07:03.112289
• Title: No-Regret Learning for Fair Multi-Agent Social Welfare Optimization
• Title（参考訳）: 公正なマルチエージェント社会福祉最適化のための非線形学習
• Authors: Mengxiao Zhang, Ramiro Deo-Campo Vuong, Haipeng Luo,
• Abstract要約: オンラインマルチエージェント・ナッシュ社会福祉(NSW)の課題について考察する。 アルゴリズムがサブ線形後悔を達成できないことを示す。 また,異なる武器に無関心なエージェントが1つ存在する場合,対数的後悔が可能であることも示している。
• 参考スコア（独自算出の注目度）: 35.44934658941197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of online multi-agent Nash social welfare (NSW) maximization. While previous works of Hossain et al. [2021], Jones et al. [2023] study similar problems in stochastic multi-agent multi-armed bandits and show that $\sqrt{T}$-regret is possible after $T$ rounds, their fairness measure is the product of all agents' rewards, instead of their NSW (that is, their geometric mean). Given the fundamental role of NSW in the fairness literature, it is more than natural to ask whether no-regret fair learning with NSW as the objective is possible. In this work, we provide a complete answer to this question in various settings. Specifically, in stochastic $N$-agent $K$-armed bandits, we develop an algorithm with $\widetilde{\mathcal{O}}\left(K^{\frac{2}{N}}T^{\frac{N-1}{N}}\right)$ regret and prove that the dependence on $T$ is tight, making it a sharp contrast to the $\sqrt{T}$-regret bounds of Hossain et al. [2021], Jones et al. [2023]. We then consider a more challenging version of the problem with adversarial rewards. Somewhat surprisingly, despite NSW being a concave function, we prove that no algorithm can achieve sublinear regret. To circumvent such negative results, we further consider a setting with full-information feedback and design two algorithms with $\sqrt{T}$-regret: the first one has no dependence on $N$ at all and is applicable to not just NSW but a broad class of welfare functions, while the second one has better dependence on $K$ and is preferable when $N$ is small. Finally, we also show that logarithmic regret is possible whenever there exists one agent who is indifferent about different arms.
• Abstract（参考訳）: オンラインマルチエージェント・ナッシュ社会福祉(NSW)の最大化の問題を考える。 Hossain et al [2021], Jones et al [2023] の以前の研究は、確率的マルチエージェント・マルチアーマー・バンドイットにおける同様の問題を研究し、$\sqrt{T}$-regret が$T$ラウンド後に可能であることを示す一方で、彼らの公正度尺度は NSW の代わりにすべてのエージェントの報酬の積である(つまり、幾何学的意味)。 フェアネス文学におけるNSWの基本的な役割を考えると、NSWを目的とする未学習のフェアラーニングが可能であるかどうかを問うことは当然である。 本研究では, 様々な状況において, この質問に対する完全な回答を提供する。 具体的には、$N$-agent $K$-armed bandits において、$\widetilde{\mathcal{O}}\left(K^{\frac{2}{N}}T^{\frac{N-1}{N}}\right)$ regret を用いてアルゴリズムを開発し、$T$への依存がきついことを証明し、Hossain et al [2021] の $\sqrt{T}$-regret bounds とは対照的である。 次に、敵の報酬に関する問題のより困難なバージョンを考えます。 意外なことに、NSWが凹凸関数であるにもかかわらず、アルゴリズムがサブ線形後悔を達成できないことが証明されている。 そのような否定的な結果を回避するために、我々はさらに、フル情報フィードバックと、$\sqrt{T}$-regretを持つ2つのアルゴリズムを設計することを考える: 1つはN$に全く依存せず、NSWだけでなく幅広い福祉機能にも適用可能であり、もう1つは$K$への依存がより良く、$N$が小さい場合には好適である。 最後に、異なる腕に無関心なエージェントが1つ存在する場合、対数的後悔が可能であることを示す。

関連論文リスト

• No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and NP-Hardness of Adversarial Full-Information Setting [23.188831772813103]
  オンラインM$natural$-concave関数問題について検討し,Murota と Shioura (1999) によるインタラクティブ版について検討した。 バンドイット設定では、$O(T-1/2)$-simple regretと$O(T2/3)$-regretアルゴリズムを、M$natural$-concave関数のノイズ値オーラクルに$T$倍のアクセスで提示する。 完全な情報フィードバックであっても,ラウンド毎に実行されたアルゴリズムは,任意の一定の$cに対して,O(T1-c)$後悔を達成できないことを証明しています。
  論文  参考訳（メタデータ） (2024-05-21T01:31:44Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret [7.059472280274009]
  従来の非効率アルゴリズムよりも後悔度が低い新しいアルゴリズムを提案する。 N$エージェント、$K$アーム、および$T$ラウンドの場合、我々のアプローチは、$tildeO(sqrtNKT + NK)$という残念な境界を持つ。 また、効率的なアルゴリズムを $tildeO(sqrtKT + N2K)$ regret で非効率なアプローチで補完する。
  論文  参考訳（メタデータ） (2022-09-23T19:15:43Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)
• Fairness and Welfare Quantification for Regret in Multi-Armed Bandits [13.094997642327371]
  我々は後悔という概念を反逆主義者の視点で拡張する。 我々はナッシュの後悔について研究し、前兆不明の最適平均(腕の間)とアルゴリズムのパフォーマンスの違いとして定義する。
  論文  参考訳（メタデータ） (2022-05-27T12:12:56Z)
• Non-stationary Bandits and Meta-Learning with a Small Set of Optimal Arms [30.024167992890916]
  そこで本研究では,学習者が200ドル(約1万2000円)の帯域幅のタスクに直面する決定について検討する。 敵は各タスクの最適なアームを、M$アームのより小さな(しかし未知の)サブセットで選択することを制約される。 境界は既知のもの(非定常的メタラーニング設定)、あるいは未知のもの(非定常的バンディット設定)である。
  論文  参考訳（メタデータ） (2022-02-25T22:28:01Z)
• 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)
• Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
  本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。 我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。 そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
  論文  参考訳（メタデータ） (2021-12-06T08:27:54Z)
• 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)

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

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