論文の概要: 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問題の複雑性を解析する。 次にアルゴリズムを設計し、そのアルゴリズムのサンプル複雑性が次数で下限と一致することを証明します。 理論的知見を説明するために, 数値実験の簡単な説明を行った。

関連論文リスト

• An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration [3.9901365062418312]
  我々は、K$$armed banditフレームワークにおける最適な腕識別問題を考察する。 エージェントは1つのアームではなく、各タイムスロットでアームのサブセットをプレイすることができる。 我々は、$log K$グループを構築し、最適なアームの存在を検出するための確率比テストを実行するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-03T15:10:08Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。 最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。 本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
  論文  参考訳（メタデータ） (2025-01-23T12:28:09Z)
• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。 我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Representative Arm Identification: A fixed confidence approach to identify cluster representatives [7.459521930846415]
  マルチアームバンディット(MAB)フレームワークにおける代表腕識別問題について検討する。 RAI問題は、最高の腕や、上位の$K$から$M$を識別するなど、いくつかのよく研究されたMAB問題としてカバーされている。 本稿では,信頼区間の概念に基づく2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-26T11:47:52Z)
• Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget [6.22018632187078]
  固定予算の制約付きベスト・ミックスアーム識別(CBMAI)問題を導入する。 目標は、与えられた学習予算$N$で、期待されるコストの制約によって期待される報酬を最大化する最高の混合アームを見つけることである。 我々は、(最良の混合アームの支持の)誤識別に関する理論上の上限を提供し、予算$N$で指数関数的に崩壊することを示す。
  論文  参考訳（メタデータ） (2024-05-23T22:35:11Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、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)
• Robust Outlier Arm Identification [16.21284542559277]
  ロバスト・アウトリー・アーム識別(ROAI)の問題点について検討する。 目標は、期待される報酬が多数派から大きく逸脱した武器を特定することである。 我々は、期待される報酬の中央値と中央値の絶対偏差を用いて、外れ値のしきい値を算出する。
  論文  参考訳（メタデータ） (2020-09-21T16:13:01Z)

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

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