論文の概要: Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need

• arxiv url: http://arxiv.org/abs/2510.21312v1
• Date: Fri, 24 Oct 2025 10:15:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 06:57:23.411436
• Title: Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need
• Title（参考訳）: バンディットにおける社会福祉の再考:UCBは(まだ)必要なものすべて
• Authors: Dhruv Sarkar, Nishant Pandey, Sayak Ray Chowdhury,
• Abstract要約: 我々は,蓄積した報酬の幾何学的平均による評価を行うナッシュ後悔を紹介する。 実験では,初期均一探索フェーズに標準のアッパー信頼境界(UCB)アルゴリズムが適用され,ほぼ最適ナッシュの後悔が達成されることを示した。 我々はアルゴリズムを、$p$平均後悔(英語版)と呼ばれる幅広い公正度尺度に一般化し、すべての$p$値に対して(ほぼ)最適後悔境界を均一に証明する。
• 参考スコア（独自算出の注目度）: 9.443816944974419
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Regret in stochastic multi-armed bandits traditionally measures the difference between the highest reward and either the arithmetic mean of accumulated rewards or the final reward. These conventional metrics often fail to address fairness among agents receiving rewards, particularly in settings where rewards are distributed across a population, such as patients in clinical trials. To address this, a recent body of work has introduced Nash regret, which evaluates performance via the geometric mean of accumulated rewards, aligning with the Nash social welfare function known for satisfying fairness axioms. To minimize Nash regret, existing approaches require specialized algorithm designs and strong assumptions, such as multiplicative concentration inequalities and bounded, non-negative rewards, making them unsuitable for even Gaussian reward distributions. We demonstrate that an initial uniform exploration phase followed by a standard Upper Confidence Bound (UCB) algorithm achieves near-optimal Nash regret, while relying only on additive Hoeffding bounds, and naturally extending to sub-Gaussian rewards. Furthermore, we generalize the algorithm to a broad class of fairness metrics called the $p$-mean regret, proving (nearly) optimal regret bounds uniformly across all $p$ values. This is in contrast to prior work, which made extremely restrictive assumptions on the bandit instances and even then achieved suboptimal regret bounds.
• Abstract（参考訳）: 確率的な多重武装の包帯の規則は、伝統的に最高報酬と累積報酬の算術平均と最終報酬の差を測定する。 これらの指標は、特に臨床試験の患者のような集団に報酬が分配される環境では、報酬を受けるエージェント間の公平性に対処できないことが多い。 この問題に対処するため、近年のNash regretは、蓄積された報酬の幾何学的平均を通じてパフォーマンスを評価するもので、公正な公理を満たすことで知られているNash社会福祉機能と一致している。 ナッシュの後悔を最小限に抑えるために、既存のアプローチは特殊アルゴリズムの設計と、乗法的濃度の不等式や有界な非負の報酬のような強い仮定を必要とする。 我々は,初期一様探索フェーズに続いて,標準のアッパー信頼境界(UCB)アルゴリズムが,加法的ホエフィング境界のみに依存しながらほぼ最適なナッシュ後悔を達成し,自然にガウス以下の報酬に拡張できることを実証した。 さらに、このアルゴリズムを「$p$平均後悔」と呼ばれる幅広い公正度尺度に一般化し、(ほぼ)最適後悔境界を全ての$p$値に対して均一に証明する。 これは以前の研究とは対照的であり、バンディットの事例に対して極めて制限的な仮定をし、なおかつ過度に最適の後悔境界を達成した。

関連論文リスト

• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• Tracking Most Significant Shifts in Infinite-Armed Bandits [3.591122855617648]
  本研究では,貯水池分布からアクションの平均報酬をサンプリングする無限武装バンディット問題について検討する。 貯水池の正則性の全規則に対して, パラメータフリーな最適後悔境界を示す。 そこで我々は,無作為な除去の変種を用いることで,大きな変化の点におけるより厳密な後悔境界を適応的に達成できることを示した。
  論文  参考訳（メタデータ） (2025-01-31T19:00:21Z)
• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Zero-Inflated Bandits [11.60342504007264]
  そこでは,ゼロ膨らみ分布と呼ばれる古典的半パラメトリック分布を用いて報酬をモデル化する。 我々は、この特定の構造のためのアッパー信頼境界とトンプソンサンプリングフレームワークに基づくアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-12-25T03:13:21Z)
• Nash Regret Guarantees for Linear Bandits [12.494184403263338]
  我々は,Nashが$Oleft(sqrtfracdnuT log(T |X|)right)$を後悔するアルゴリズムを開発した。 さらに、アームの集合 X$ が必ずしも有限ではない線形バンドイットのインスタンスに対処すると、ナッシュ後悔の上限 $Oleft( fracdfrac54nufrac12sqrtT log(T)right)$ が得られる。
  論文  参考訳（メタデータ） (2023-10-03T12:58:10Z)
• STARC: A General Framework For Quantifying Differences Between Reward Functions [52.69620361363209]
  我々は、STARCメトリックと呼ばれるすべての報酬関数の空間上の擬計量のクラスを提供する。 以上の結果から,STARCは最悪の後悔に対して上界と下界の両方を誘導することがわかった。 また、以前の研究によって提案された報酬指標に関するいくつかの問題も特定します。
  論文  参考訳（メタデータ） (2023-09-26T20:31:19Z)
• Contextual bandits with concave rewards, and an application to fair ranking [108.48223948875685]
  CBCR (Contextual Bandits with Concave Rewards) に対する反省点のある最初のアルゴリズムを提案する。 我々は,スカラー・リワード問題に対するCBCRの後悔から,新たな縮小を導出した。 推薦の公正さによって動機づけられたCBCRの特別事例として,ランク付けと公正を意識した目的について述べる。
  論文  参考訳（メタデータ） (2022-10-18T16:11:55Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。 最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
  論文  参考訳（メタデータ） (2022-06-07T18:08:21Z)
• Fairness and Welfare Quantification for Regret in Multi-Armed Bandits [13.094997642327371]
  我々は後悔という概念を反逆主義者の視点で拡張する。 我々はナッシュの後悔について研究し、前兆不明の最適平均(腕の間)とアルゴリズムのパフォーマンスの違いとして定義する。
  論文  参考訳（メタデータ） (2022-05-27T12:12:56Z)
• Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning [56.23358327635815]
  リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
  論文  参考訳（メタデータ） (2020-06-22T16:06:25Z)

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

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