論文の概要: Improved Algorithms for Nash Welfare in Linear Bandits
- arxiv url: http://arxiv.org/abs/2601.22969v1
- Date: Fri, 30 Jan 2026 13:32:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-02 18:28:15.470816
- Title: Improved Algorithms for Nash Welfare in Linear Bandits
- Title（参考訳）: リニアバンドにおけるナッシュ福祉のアルゴリズムの改良
- Authors: Dhruv Sarkar, Nishant Pandey, Sayak Ray Chowdhury,
- Abstract要約: 線形包帯において,次数最適ナッシュ残差を生じる新しい解析ツールを導入する。
本稿では,任意の線形帯域戦略上のメタアルゴリズムとして機能する汎用アルゴリズムフレームワークであるFairLinBanditを提案する。
- 参考スコア（独自算出の注目度）: 9.443816944974419
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Nash regret has recently emerged as a principled fairness-aware performance metric for stochastic multi-armed bandits, motivated by the Nash Social Welfare objective. Although this notion has been extended to linear bandits, existing results suffer from suboptimality in ambient dimension $d$, stemming from proof techniques that rely on restrictive concentration inequalities. In this work, we resolve this open problem by introducing new analytical tools that yield an order-optimal Nash regret bound in linear bandits. Beyond Nash regret, we initiate the study of $p$-means regret in linear bandits, a unifying framework that interpolates between fairness and utility objectives and strictly generalizes Nash regret. We propose a generic algorithmic framework, FairLinBandit, that works as a meta-algorithm on top of any linear bandit strategy. We instantiate this framework using two bandit algorithms: Phased Elimination and Upper Confidence Bound, and prove that both achieve sublinear $p$-means regret for the entire range of $p$. Extensive experiments on linear bandit instances generated from real-world datasets demonstrate that our methods consistently outperform the existing state-of-the-art baseline.
- Abstract（参考訳）: ナッシュの後悔は最近、ナッシュ社会福祉の目的に動機づけられた、確率的マルチ武器の盗賊に対する原則的公正を意識したパフォーマンス指標として登場した。
この概念は線形包帯に拡張されているが、既存の結果は、制限的な濃度の不等式に依存する証明技術から生じる、周囲次元$d$の亜最適性に悩まされている。
本研究では, 線形包帯において, 次数最適ナッシュ残差を生じる新たな解析ツールを導入することにより, この問題を解消する。
これは、公正性と実用目的を補間し、ナッシュの後悔を厳密に一般化する統一的な枠組みである。
本稿では,任意の線形帯域戦略上のメタアルゴリズムとして機能する汎用アルゴリズムフレームワークであるFairLinBanditを提案する。
我々はこのフレームワークを2つの帯域幅アルゴリズムを用いてインスタンス化する: フェーズド・エミネーションとアッパー・信頼境界。
実世界のデータセットから生成された線形バンディットインスタンスに関する大規模な実験は、我々の手法が既存の最先端のベースラインを一貫して上回っていることを示している。
関連論文リスト
- Optimal and Practical Batched Linear Bandit Algorithm [8.087699764574788]
本稿では, 線形バンドイット問題(バッチ化線形バンドイット)について, 限定適応性の下で検討する。
我々は,腕の除去と正規化G-最適設計を統合した新しいバッチアルゴリズムBLAEを提案する。
BLAEは、全てのレジームにおける証明可能なミニマックス最適性と、バッチ化された線形帯域における実用上の優位性を組み合わせた最初のアルゴリズムである。
論文 参考訳（メタデータ） (2025-07-11T09:29:28Z) - Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。
UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。
我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
論文 参考訳（メタデータ） (2024-05-24T04:11:58Z) - 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) - 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) - PopArt: Efficient Sparse Regression and Experimental Design for Optimal
Sparse Linear Bandits [29.097522376094624]
そこで我々はPopArtと呼ばれる単純で効率的なスパース線形推定法を提案する。
我々は, 粗い線形バンディットアルゴリズムを導出し, 美術品の状態に対する後悔の上界の改善を享受する。
論文 参考訳（メタデータ） (2022-10-25T19:13:20Z) - Fairness and Welfare Quantification for Regret in Multi-Armed Bandits [13.094997642327371]
我々は後悔という概念を反逆主義者の視点で拡張する。
我々はナッシュの後悔について研究し、前兆不明の最適平均(腕の間)とアルゴリズムのパフォーマンスの違いとして定義する。
論文 参考訳（メタデータ） (2022-05-27T12:12:56Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-28T08:25:26Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-13T16:35:30Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。