Best Arm Identification with Fairness Constraints on Subpopulations
This addresses fairness in decision-making for subpopulations, such as ethnic or age groups, but is incremental as it builds on standard best arm identification problems.
The paper tackles the problem of best arm identification with fairness constraints on subpopulations (BAICS), aiming to select the arm with the largest expected reward while ensuring fairness across groups, and proves a lower bound on sample complexity and designs an algorithm that matches it in order.
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.