論文の概要: Price of Fairness in Bandits: A Tight Minimax Characterization

• arxiv url: http://arxiv.org/abs/2607.13402v1
• Date: Wed, 15 Jul 2026 02:58:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-16 16:39:12.627282
• Title: Price of Fairness in Bandits: A Tight Minimax Characterization
• Title（参考訳）: バンドの公正さの価格:極小評価
• Authors: Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray Chowdhury,
• Abstract要約: 盗賊問題では、標準的な後悔を最小化するアルゴリズムが探索を償却コストとして扱い、初期の参加者は不公平な前衛の損失に晒される。 最近の研究は、一般化された$p$-meanを通じて、ラウンドごとの期待される報酬のシーケンスを評価することで、この問題に対処している。 アルゴリズムに依存しない下界$(sqrtkmax(1,q)/T)$; for $q>1$, this shows that $kq/2$ is a information-theoretically unavoidable。
• 参考スコア（独自算出の注目度）: 9.360852329235477
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In bandit problems, standard regret-minimizing algorithms treat exploration as an amortized cost, which can expose early participants to unfair ex-ante losses in settings such as clinical trials. Recent work addresses this by evaluating the sequence of per-round expected rewards through the generalized $p$-mean, interpolating between utilitarian welfare ($p=1$), Nash welfare ($p\to0$), and Rawlsian fairness ($p\to-\infty$). Although tight guarantees are known for $p\ge0$, the strictly fair regime $q=-p>0$ remains unresolved because negative-power means are dominated by the smallest per-round rewards. For $σ$-sub-Gaussian rewards with nonnegative means, the best prior algorithm relied on uniform early exploration and achieved regret $O(k^{(q+1)/2}/\sqrt{T})$, while the only general lower bound was the classical $Ω(σ\sqrt{k/T})$. Thus it was unclear whether the extra dependence on $k$ was intrinsic to strict fairness or an artifact of uniform exploration. We close this gap by identifying the exact polynomial price of strict fairness. Using a needle-in-haystack construction, we prove an algorithm-independent lower bound $Ω(σ\sqrt{k^{\max(1,q)}/T})$; for $q>1$, this shows that the penalty $k^{q/2}$ is information-theoretically unavoidable. We then introduce \textsf{UCB-HARE} (Harmonic Anchored Rank Exploration), which replaces uniform exploration with an inverse-weighted harmonic rank schedule protected by a certified positive-mean anchor. Its regret is $\widetilde{O}(σ\sqrt{k^{\max(1,q)}/T})$, matching the lower bound up to logarithmic factors. Experiments on synthetic instances confirm that \textsf{UCB-HARE} improves over uniform-exploration baselines, with gains increasing as $q$ grows.
• Abstract（参考訳）: バンドイット問題では、標準的な後悔最小化アルゴリズムが探索を償却コストとして扱うため、早期の参加者は臨床試験のような設定において不当な前衛的な損失を被る可能性がある。 最近の研究は、一般化された$p$-mean、実用的福祉(p=1$)、ナッシュ福祉(p\to0$)、ラウルシアン公正(p\to-\infty$)の補間を通じて、ラウンドごとの報酬のシーケンスを評価することでこの問題に対処している。 厳密な保証は$p\ge0$で知られているが、厳密な公正な規則である$q=-p>0$は、負のパワー平均がラウンド当たりの報酬で支配されるため未解決のままである。 非負の手段を持つ$σ$-sub-ガウスの報酬に対して、最良の事前アルゴリズムは、一様の初期探索に頼り、後悔した$O(k^{(q+1)/2}/\sqrt{T})$を達成したが、唯一の一般的な下限は古典的な$Ω(σ\sqrt{k/T})$である。 したがって、$k$への追加依存が厳密な公正性に固有のものなのか、一様探査の人工物なのかは定かではない。 厳密な公正性の多項式価格を正確に同定することで、このギャップを埋める。 ニードル・イン・ヘイスタック構造を用いて、アルゴリズムに依存しない下界の$Ω(σ\sqrt{k^{\max(1,q)}/T})$; for $q>1$, this show that the penalty $k^{q/2}$ is a information-theoretically unavoidable。 次に、一様探索を正平均アンカーで保護された逆重み付き高調波ランクスケジュールに置き換える「textsf{UCB-HARE} (Harmonic Anchored Rank Exploration)」を導入する。 その後悔は$\widetilde{O}(σ\sqrt{k^{\max(1,q)}/T})$である。 合成インスタンスの実験では、 \textsf{UCB-HARE} が一様探索ベースラインよりも改善し、$q$が成長するにつれて上昇することを確認した。

関連論文リスト

• p-Mean Regret for Stochastic Bandits [52.828710025519996]
  単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。 我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
  論文  参考訳（メタデータ） (2024-12-14T08:38:26Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。 我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
  論文  参考訳（メタデータ） (2023-04-25T09:31:20Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning [40.990467706237396]
  タスクに依存しない強化学習のための効率的なアルゴリズムを提案する。 このアルゴリズムは1/epsilon cdot (H3SA / rho + H4 S2 A) の$widetildemathcalOのみを探索する。 情報理論上、この境界は$rho Theta (1/(HS))$と$H>1$に対してほぼ厳密であることを示す。
  論文  参考訳（メタデータ） (2021-08-11T20:42:46Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs [35.988644745703645]
  我々は、リニアバンディットをヘビーテールのペイオフで分析し、そこではペイオフは1+epsilon$のモーメントしか持たない。 本稿では,$widetildeO(dfrac12Tfrac11+epsilon)$のサブ線形後悔境界を満足する2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-28T13:01:38Z)

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

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