論文の概要: Best Arm Identification with Fairness Constraints on Subpopulations
- arxiv url: http://arxiv.org/abs/2304.04091v1
- Date: Sat, 8 Apr 2023 19:41:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-11 17:47:38.579505
- Title: Best Arm Identification with Fairness Constraints on Subpopulations
- Title(参考訳): サブポピュレーションにおけるフェアネス制約のあるベストアーム識別
- Authors: Yuhang Wu, Zeyu Zheng, Tingyu Zhu
- Abstract要約: サブポピュレーション(BAICS)におけるフェアネス制約によるベストアーム識別の問題を定式化し,解析し,解決する。
BAICSの問題は、選択された腕が全てのサブ集団に公平でなければならないことである。
我々は、閉形式表現を用いて、標本複雑性の最も達成可能な下界を証明した。
- 参考スコア(独自算出の注目度): 11.349636358427485
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We formulate, analyze and solve the problem of best arm identification with
fairness constraints on subpopulations (BAICS). Standard best arm
identification problems aim at selecting an arm that has the largest expected
reward where the expectation is taken over the entire population. The BAICS
problem requires that an selected arm must be fair to all subpopulations (e.g.,
different ethnic groups, age groups, or customer types) by satisfying
constraints that the expected reward conditional on every subpopulation needs
to be larger than some thresholds. The BAICS problem aims at correctly
identify, with high confidence, the arm with the largest expected reward from
all arms that satisfy subpopulation constraints. We analyze the complexity of
the BAICS problem by proving a best achievable lower bound on the sample
complexity with closed-form representation. We then design an algorithm and
prove that the algorithm's sample complexity matches with the lower bound in
terms of order. A brief account of numerical experiments are conducted to
illustrate the theoretical findings.
- Abstract(参考訳): サブポピュレーション(BAICS)におけるフェアネス制約によるベストアーム識別の問題を定式化し,解析し,解決する。
標準の腕識別問題は、人口全体に予想される最大の報酬を持つ腕を選択することを目的としている。
BAICSの問題は、選択された腕が全てのサブ人口(例えば、異なる民族グループ、年齢グループ、または顧客タイプ)に対して公平でなければならないことを要求する。
BAICS問題は、人口制限を満たす全ての腕から期待される最大の報酬を持つ腕を、高い信頼性で正しく識別することを目的としている。
本研究では,閉形式表現を用いたサンプル複雑性において,最善の達成可能な下限を証明し,baics問題の複雑性を解析する。
次にアルゴリズムを設計し、そのアルゴリズムのサンプル複雑性が次数で下限と一致することを証明します。
理論的知見を説明するために, 数値実験の簡単な説明を行った。
関連論文リスト
- Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Optimal Multi-Distribution Learning [94.73322179348332]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では,$(d+k)/varepsilon2$の順に,サンプルの複雑さを伴って,$varepsilon$-optimal randomized hypothesisを生成するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-08T16:06:29Z) - Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a
Fixed Budget [10.470114319701576]
本研究は、腕を最も期待できる結果に識別する実験的な設計問題について検討する。
分散が知られているという仮定のもと、一般化ネマン割当(GNA)-経験的ベストアーム(EBA)戦略を提案する。
GNA-EBA戦略は、誤同定の確率が下界と一致するという意味で無限に最適であることを示す。
論文 参考訳(メタデータ) (2023-10-30T17:52:46Z) - Optimal Clustering with Bandit Feedback [84.04424523097168]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳(メタデータ) (2022-02-09T06:05:05Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳(メタデータ) (2021-11-14T21:49:58Z) - From Finite to Countable-Armed Bandits [8.099977107670918]
有限の型に属する数え切れないほど多くのアームを持つバンドイット問題を考える。
武器の集団のそれぞれの種類の割合を設定する型に一定の分布がある。
我々は,O(log n)分布依存的な累積後悔を任意の回数の再生後に達成する完全適応型オンライン学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-05-22T13:09:50Z) - Robust Outlier Arm Identification [16.21284542559277]
ロバスト・アウトリー・アーム識別(ROAI)の問題点について検討する。
目標は、期待される報酬が多数派から大きく逸脱した武器を特定することである。
我々は、期待される報酬の中央値と中央値の絶対偏差を用いて、外れ値のしきい値を算出する。
論文 参考訳(メタデータ) (2020-09-21T16:13:01Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳(メタデータ) (2020-06-29T14:25:51Z) - Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a
Differentially Private Scheme [16.1694012177079]
我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。
ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。
このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
論文 参考訳(メタデータ) (2020-06-11T20:23:43Z) - The Price of Incentivizing Exploration: A Characterization via Thompson
Sampling and Sample Complexity [83.81297078039836]
インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。
我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
論文 参考訳(メタデータ) (2020-02-03T04:58:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。