Bayesian Learning to Select Fair Classifiers
The paper tackles online selection of prediction agents—such as classifiers, LLMs, or human experts—that must balance accuracy and subgroup fairness in a sequential streaming setting where evaluating every agent on every example is impractical. It formulates the problem as a Bayesian multi-armed bandit where utility combines accuracy, a fairness-gap penalty weighted by $\lambda$, and a query cost, then applies Thompson Sampling with conjugate Beta posteriors for both overall accuracy and per-subgroup prediction rates. This matters because fairness-aware sequential selection introduces new statistical dependence between accuracy and subgroup estimates that standard MAB analyses do not handle, and because many real-world deployments must learn while operating.
The paper makes a timely, technically solid contribution to fair online model selection, supported by new regret bounds and unusually broad empirical validation across tabular classifiers, LLMs, and human experts. The authors correctly isolate how the smallest subgroup proportion $\pi_{\min}$ and fairness weight $\lambda$ inflate regret. However, the theoretical guarantees rely on two strong population assumptions—fixed interiority and an information-dominance condition—that are difficult to verify in practice, and the bounds contain an unusual $(\log T)^{7/2}$ anti-concentration term whose tightness is unclear and unsupported by a lower bound.
The utility decomposition $U_a(\lambda) := \rho_a - \lambda g_a - c_a$ is clean and interpretable, and the regret bounds elegantly separate the statistical cost of fairness estimation from accuracy estimation. Specifically, the fairness term scales with $\lambda / \sqrt{\pi_{\min}}$, quantifying the exploration burden imposed by rare subgroups. The empirical evaluation spans 18 tabular classifiers, 56 LLMs, and 10 human-expert arms over seven datasets, showing that Thompson Sampling is competitive or dominant in the vast majority of scenarios.
The core theoretical results require two population-level assumptions on the optimal arm—fixed interiority with margin $\kappa_0 = 1/100$ and an information-dominance inequality (Equation 7)—that are strong and not obviously satisfied by pretrained classifiers deployed in practice. If these conditions fail, the anti-concentration argument that bounds selections of suboptimal arms could collapse. The regret bound also carries a polylogarithmic anti-concentration cost $(\log T)^{7/2}$ that the authors admit may not be tight. Empirically, TS is not uniformly best: on ACSIncome, Bayes-UCB wins when two arms have nearly equal utility, and on Bios, $\epsilon$-Greedy outperforms TS at large $\lambda$ because the flat Dirichlet prior inflates sampled fairness gaps for rarely selected arms, causing under-exploration.
The evidence broadly supports the main claims: Thompson Sampling achieves the lowest regret in 12 of 14 endpoint settings and at nearly all $\lambda$ values on most datasets (Tables 2 and 3). The baseline choices—Round-Robin, UCB1, Bayes-UCB, and $\epsilon$-Greedy—are natural and fair, and the authors transparently report the few cases where TS is not best, noting that no MAB method is provably dominant across all problems. The theoretical decomposition into accuracy regret, fairness-estimation regret, and anti-concentration cost is conceptually useful, although the practical relevance of the additional anti-concentration term is left somewhat ambiguous.
The algorithm is conceptually straightforward to implement—maintaining Beta posteriors per arm for accuracy and per arm-subgroup pair for fairness—but the authors currently only promise to release code and datasets on GitHub for the final version. Hyperparameters are largely standard (uninformative $\mathrm{Beta}(1,1)$ or $\mathrm{Dirichlet}(1, \dots, 1)$ priors), though full details of the 18 tabular classifiers and deliberately biased models are relegated to the appendix. Reproducing the LLM and human-expert arms requires API access or specific Mechanical Turk annotations, which raises practical barriers. The experimental protocol is otherwise well-specified: results are averaged over 10,000 runs on streams of length $T = 50{,}000$ sampled with replacement from held-out test data.
Evaluations of classifiers (AI or human or agents) often assume a batch setting in which every agent produces labels on every example in a test set, which can be expensive or impractical in many contexts. This motivates online policies that adaptively select agents to query as examples arrive and update policies as outcomes are observed. We study the problem of selecting, in an online stream, the agent that best balances (i) predictive performance and (ii) subgroup fairness of a sensitive attribute, and that allows for delayed observations of true class labels. We formulate this as a Bayesian multi-armed bandit problem using Thompson Sampling, explicitly balancing accuracy and fairness. We conduct empirical evaluations on real-world datasets spanning problems involving tabular classifiers, large language models, and human labelers, demonstrating substantial reductions in regret relative to baselines. Our theoretical contributions include guarantees on the performance of the selected agent that incorporate both the accuracy and fairness aspects of the problem.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.