論文の概要: Fairness and Welfare Quantification for Regret in Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2205.13930v1
- Date: Fri, 27 May 2022 12:12:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-30 15:23:00.900643
- Title: Fairness and Welfare Quantification for Regret in Multi-Armed Bandits
- Title（参考訳）: マルチアーメッドバンドにおけるレグレットの公平性と福祉的定量化
- Authors: Siddharth Barman, Arindam Khan, Arnab Maiti and Ayush Sawarni
- Abstract要約: 我々は後悔という概念を反逆主義者の視点で拡張する。
我々はナッシュの後悔について研究し、前兆不明の最適平均(腕の間)とアルゴリズムのパフォーマンスの違いとして定義する。
- 参考スコア（独自算出の注目度）: 13.094997642327371
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We extend the notion of regret with a welfarist perspective. Focussing on the
classic multi-armed bandit (MAB) framework, the current work quantifies the
performance of bandit algorithms by applying a fundamental welfare function,
namely the Nash social welfare (NSW) function. This corresponds to equating
algorithm's performance to the geometric mean of its expected rewards and leads
us to the study of Nash regret, defined as the difference between the -- a
priori unknown -- optimal mean (among the arms) and the algorithm's
performance. Since NSW is known to satisfy fairness axioms, our approach
complements the utilitarian considerations of average (cumulative) regret,
wherein the algorithm is evaluated via the arithmetic mean of its expected
rewards.
This work develops an algorithm that, given the horizon of play $T$, achieves
a Nash regret of $O \left( \sqrt{\frac{{k \log T}}{T}} \right)$, here $k$
denotes the number of arms in the MAB instance. Since, for any algorithm, the
Nash regret is at least as much as its average regret (the AM-GM inequality),
the known lower bound on average regret holds for Nash regret as well.
Therefore, our Nash regret guarantee is essentially tight. In addition, we
develop an anytime algorithm with a Nash regret guarantee of $O \left(
\sqrt{\frac{{k\log T}}{T}} \log T \right)$.
- Abstract（参考訳）: 我々は後悔の概念をウェルファリスト的な視点で拡張する。
本研究は,従来のマルチアーム・バンディット(MAB)フレームワークに着目し,基本的な福祉機能,すなわちナッシュ社会福祉(NSW)機能を適用して,バンディットアルゴリズムの性能を定量化する。
これはアルゴリズムのパフォーマンスを期待される報酬の幾何学的平均と同等にすることに対応し、nash regretの研究へと繋がる。
NSWは公平性の公理を満たすことが知られているため、提案手法は平均的(累積的な)後悔の実用的考察を補完し、アルゴリズムは期待される報酬の算術平均を通して評価される。
この研究は、play $t$の地平線を考えると、mabインスタンスのアームの数を表す$o \left( \sqrt{\frac{k \log t}}{t}} \right)$というnashの後悔を達成するアルゴリズムを開発した。
どんなアルゴリズムでも、ナッシュの後悔はその平均的な後悔(am-gmの不等式)と同じであるので、ナッシュの後悔に対する平均的な後悔の上限は、ナッシュの後悔にも当てはまる。
したがって、ナッシュの後悔の保証は本質的にきつい。
さらに、nashの後悔を保証したanytimeアルゴリズムを、$o \left( \sqrt{\frac{k\log t}}{t}} \log t \right)$で開発する。
関連論文リスト
- No-Regret Learning for Fair Multi-Agent Social Welfare Optimization [35.44934658941197]
オンラインマルチエージェント・ナッシュ社会福祉(NSW)の課題について考察する。
アルゴリズムがサブ線形後悔を達成できないことを示す。
また,異なる武器に無関心なエージェントが1つ存在する場合,対数的後悔が可能であることも示している。
論文 参考訳（メタデータ） (2024-05-31T08:21:11Z) - Incentive-compatible Bandits: Importance Weighting No More [14.344759978208957]
本稿では,包括的フィードバックによるインセンティブ適合型オンライン学習の課題について検討する。
この研究では、最初のインセンティブに適合するアルゴリズムを提案し、$O(sqrtKT)$ regret bounds を楽しむ。
論文 参考訳（メタデータ） (2024-05-10T13:57:13Z) - 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) - Learning Two-Player Mixture Markov Games: Kernel Function Approximation
and Correlated Equilibrium [157.0902680672422]
非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。
双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-10T14:21:54Z) - Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。
本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。
提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
論文 参考訳（メタデータ） (2021-11-09T09:00:02Z) - Optimal Order Simple Regret for Gaussian Process Bandits [6.84224661918159]
純粋な探索アルゴリズムは既存の境界よりもかなり厳密であることを示す。
この後悔は、カーネル上の低い境界が知られている場合に、対数的に最適であることを示す。
論文 参考訳（メタデータ） (2021-08-20T16:49:32Z) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。