Bayesian Learning to Select Fair Classifiers

Saatvik Kher; Hyungrok Do; Judy Zhong; Padhraic Smyth

cs.LGOct 14, 2026

Bayesian Learning to Select Fair Classifiers

Authors: Saatvik Kher, Hyungrok Do, Judy Zhong, Padhraic Smyth

Organizations: University of California, Irvine · New York University · Weill Cornell Medicine

Abstract

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.

Figures & tables

Dataset	Type of Arms ( $N$ )	$C$	Sensitive Attribute ( $M$ )	$\pi_{\min}$
Bank	ML classifiers (18)	2	Marital Status (2)	0.396
Adult	ML classifiers (18)	2	Race (2)	0.146
Credit	ML classifiers (18)	2	Sex (2)	0.392
ACSIncome	ML classifiers (18)	2	Race (5)	0.036
Toxicity	LLMs (56)	2	Race (2)	0.500
Bios	LLMs (16)	28	Gender (2)	0.461

Table 1: Datasets:

N

arms,

C

classes and

M

subgroups

(a) Accuracy ( $\lambda=0$ )
Algorithm	Twitter	Bank	Adult	Credit	Toxicity	Bios	ACSIncome
Round-Robin	4.141	3.494	3.521	3.155	16.73	17.80	7.115
UCB1	1.924	0.819	1.544	0.975	4.930	3.344	2.476
Bayes-UCB	0.864	0.563	0.679	0.615	2.229	0.669	0.845
$\epsilon$ -Greedy (0)	1.200	0.836	2.505	1.109	4.151	8.327	5.255
$\epsilon$ -Greedy (0.1)	0.915	0.634	0.552	0.530	2.406	2.236	1.001

Table 2: Regret per example (%) after

T=50

k rounds for each algorithm (rows) and dataset (columns), for (a) accuracy (

\lambda=0

) and (b) fairness (

\lambda=\infty

), averaged over 10,000 runs (the endpoints of the curves in Figure 1 ). Minimum regret bolded.

Figure 1: Trade-off between accuracy regret (x-axis) and fairness regret (y-axis) after

T=50

k rounds, as average regret per example (%) over 10,000 runs. Each point on a curve is one value of

\lambda

, from

\lambda=0

(all weight on accuracy) to

\lambda=\infty

(all weight on fairness). Datasets (a)–(e) are binary, (f) is multi-class and (g) is multi-subgroup. Grey crosses are the individual arms and the dotted line is the oracle frontier. Round-Robin does not depend on

\lambda

and is omitted from (b), (d) and (e), where it is off-scale.

Algorithm	Twitter	Bank	Adult	Credit	Toxicity	Bios	ACSIncome
Round-Robin	0	0	0	0	0	0	0
UCB1	0	0	0	0	0	0	0
Bayes-UCB	0	0	0	0	0	0	18
$\epsilon$ -Greedy (0)	0	0	0	0	0	0	0
$\epsilon$ -Greedy (0.1)	0	0	0	3	0	38	0
TS	100	100	100	97	100	62	82

Table 3: % of

\lambda

values at which each algorithm has the lowest average cumulative regret after

T=50

k rounds.

Appendix figures & tables28 assets

Supplementary material from the paper’s appendix.

Appendix

Arm	Accuracy	DP gap	% Missing
Arm 0	75.1	6.4	39.4
Arm 1	79.5	5.2	37.5
Arm 2 ∗	81.5	6.2	45.8
Arm 3 ∗	76.5	1.2	45.4
Arm 4 ∗	83.0	12.6	39.8
Arm 5	80.4	11.5	34.2

Appendix

Table 4: The 10 arms of Twitter: accuracy, DP gap and share of tweets without a prediction (%). ∗ : optimal for some

\lambda

Figure 2: Twitter: regret per example (%) against the round

t

at three values of

\lambda

(a)–(c), and after

T=50

k rounds against

\lambda

(d).

Arm	Accuracy	DP gap
GBM ∗	91.90	2.52
RF	91.26	1.75
LR	91.10	1.77
Tree-d3	90.94	2.63
GBM+S	91.74	2.24
GBM-OP1	91.67	2.16

Appendix

Table 5: The 18 arms of Bank: accuracy and DP gap (%) on the stream population. ∗ : optimal for some

\lambda

. Arms are described in Appendix B.1.1 .

Figure 3: Bank: regret per example (%) against the round

t

at three values of

\lambda

(a)–(c), and after

T=50

k rounds against

\lambda

(d).

Arm	Accuracy	DP gap
GBM	87.47	9.46
RF	86.54	7.45
LR	85.43	9.15
Tree-d3	84.62	6.23
GBM+S ∗	87.49	9.92
GBM-OP1 ∗	87.33	8.09

Appendix

Table 6: The 18 arms of Adult: accuracy and DP gap (%) on the stream population. ∗ : optimal for some

\lambda

. Arms are described in Appendix B.1.1 .

Figure 4: Adult: regret per example (%) against the round

t

at three values of

\lambda

(a)–(c), and after

T=50

k rounds against

\lambda

(d).

Arm	Accuracy	DP gap
GBM	81.84	0.93
RF	81.57	0.87
LR	80.90	1.03
Tree-d3	81.73	0.94
GBM+S	81.88	0.72
GBM-OP1 ∗	81.88	0.72

Appendix

Table 7: The 18 arms of Credit: accuracy and DP gap (%) on the stream population. ∗ : optimal for some

\lambda

. Arms are described in Appendix B.1.1 .

Figure 5: Credit: regret per example (%) against the round

t

at three values of

\lambda

(a)–(c), and after

T=50

k rounds against

\lambda

(d).

Arm	Accuracy	DP gap
together_opt-66b	29.5	0.2
cohere_medium-20220720	29.7	1.0
together_opt-175b	30.9	2.1
together_gpt-neox-20b	31.2	1.3
together_gpt-j-6b	32.1	2.1
openai_davinci	34.9	11.4

Appendix

Table 8: The 56 LLMs of Toxicity: accuracy and DP gap (%). ∗ : optimal for some

\lambda

Figure 6: Toxicity: regret per example (%) against the round

t

at three values of

\lambda

(a)–(c), and after

T=50

k rounds against

\lambda

(d).

Arm	Accuracy	TV gap
SmolLM2-360M	13.9	24.3
SmolLM2-1.7B ∗	28.7	13.3
Qwen2.5-0.5B	47.1	28.3
Gemma3-1B	49.9	22.3
Qwen2.5-1.5B	53.0	25.7
OLMo2-7B	56.8	28.7

Appendix

Table 9: The 16 arms of Bios: accuracy and TV gap (%) on the stream population. ∗ : optimal for some

\lambda

Figure 7: Bios: regret per example (%) against the round

t

at three values of

\lambda

(a)–(c), and after

T=50

k rounds against

\lambda

(d).

Arm	Accuracy	DP gap (max–min)
GBM ∗	82.22	35.33
RF	79.32	33.02
LR	81.84	36.06
Tree-d3	74.65	31.81
GBM+S	82.20	40.51
GBM-OP1	80.50	30.29

Appendix

Table 10: The 18 arms of ACSIncome: accuracy and DP gap (%) on the stream population. ∗ : optimal for some

\lambda

. Arms are described in Appendix B.1.1 .

Figure 8: ACSIncome: regret per example (%) against the round

t

at three values of

\lambda

(a)–(c), and after

T=50

k rounds against

\lambda

(d).

Figure 13: Trade-off between accuracy and fairness regret after

T=2{,}500

rounds, as in Figure 1 .

Figure 14: Trade-off between accuracy and fairness regret after

T=5{,}000

rounds, as in Figure 1 .

Figure 15: Trade-off between accuracy and fairness regret after

T=10{,}000

rounds, as in Figure 1 .

Arm	Accuracy	DP gap	$U_{a}$	$c_{a}$	$U_{a}$
			No cost	With cost
XGBoost	73.99	6.60	67.38	1	66.38
RandomForest	75.11	6.88	68.23	5	63.23
LogisticRegression	68.13	8.38	59.75	1	58.75
DecisionStump	61.67	0.36	61.31	1	60.31
Biased	50.57	69.88	-19.31	1	-20.31

Appendix

Table 13: Coupon arms: accuracy, DP gap and utility

U_{a}

\lambda=1

(%), without and with costs

c_{a}

. Bold: best arm.

Figure 16: Share of rounds in which TS selects each arm over rounds 25k–50k, averaged over 10,000 runs.

Figure 17: Trade-off between accuracy and fairness regret after

T=50

k rounds with geometric label delays of mean

\mathbb{E}[L_{t}]

(columns), using Algorithm 1 . Round-Robin does not use feedback and is taken from the runs without delay; it is omitted where it is off-scale.

Figure 18: ACSIncome-5C: regret per example (%) against the round

t

at three values of

\lambda

(a)–(c), and after

T=50

k rounds against

\lambda

(d), as in Appendix B.1 .

Figure 20: Trade-off between Brier-score regret (x-axis) and fairness regret (y-axis) on Adult with risk-score arms after

T=50

k rounds, as average regret per example (%) over 10,000 runs. Each point on a curve is one value of

\lambda

. Grey crosses are the individual arms and the dotted line is the oracle frontier.

Figure 21: Regret per example after

T=50

k rounds (

\lambda=2

) against

1/\pi_{\min}

, averaged over 10,000 runs. (a)–(g) Datasets of Appendix B.1 ; (h) synthetic instance.

Figure 22: Percentage of

\lambda

values at which TS has a lower mean regret than Bayes-UCB,

\epsilon

-Greedy (0) and

\epsilon

-Greedy (0.1), for 30 random subsets of 3 and of 5 arms (one point per subset; 400 runs,

T=50{,}000

). Filled points: the subset contains a biased arm. Bars: medians.

Figure 23: Trade-off between accuracy and fairness regret after

T=50{,}000

rounds with three frontier arms (GBM, GBM-OP4, GBM-OP6), as in Figure 1 . Means over 10,000 runs.

Group Fairness

Group fairness measures and reduces disparities in how algorithms predict, rank, allocate resources, and make decisions for different groups.

See all 140 papers

Towards Provably Fair Machine Learning: Bayesian Approaches For Consistent and Transparent Predictions
Jun 10, 2026Owen O'Neill, Fintan CostelloSelective Prediction Bayesian Inference
University College Dublin, Ireland
Bayesian Online Model Selection
Feb 20, 2026Aida Afshar, Yuke Zhang, Aldo PacchianoMarkovian Bandits Model Selection
Boston University · Broad Institute of MIT and Harvard
FairBED: Incorporating Fairness into Bayesian Experimental Design
Jun 22, 2026Marcel Hedman, Emily Alger, Brieuc Lehmann +2Algorithmic Fairness Bayesian Experimental Design
Department of Statistics, University of Oxford · Department of Statistical Science, University College London

Jun 10, 2026J/K move · Enter open · S save

Towards Provably Fair Machine Learning: Bayesian Approaches For Consistent and Transparent Predictions

Owen O'Neill, Fintan Costello

University College Dublin, Ireland

Selective Prediction Bayesian Inference Algorithmic Fairness Group Fairness Intersectional Fairness

Open paper AskPDF arXiv

ML classifiers deployed in high-stakes domains produce predictions whose quality varies systematically across subgroups. For granular subgroups defined by intersections of multiple features, predictions are often inconsistent with the observed data: the model's outputs contradict the evidence available for that subgroup. This problem is exacerbated by regularisation, which improves aggregate performance by collapsing small subgroups into larger groups, disproportionately affecting demographic minorities. We define two requirements for consistent prediction: determinism (identical individuals receive identical predictions) and statistical consistency (we cannot reject, at significance level alpha, the hypothesis that the predictions for a subgroup were drawn from the Bayesian optimal target distribution inferred for that subgroup). From these requirements we derive the Fair Bayesian classifier, which enforces both across every group and subgroup simultaneously and abstains whenever no consistent deterministic prediction is possible. On three benchmark datasets (Adult, COMPAS, and Bank Marketing), standard classifiers produce statistically inconsistent predictions for a substantial proportion of subgroups. Our classifier achieves zero consistency error by construction while exceeding baseline accuracy and multicalibration on every dataset tested. Statistical consistency provides a principled foundation for prediction quality with direct implications for algorithmic fairness. Minority demographics are disproportionately concentrated in small subgroups, precisely where frequentist inference is least reliable; addressing this inference problem is therefore a necessary step toward fair ML. By enforcing Bayesian consistency at the finest resolution the data supports, the our classifier demonstrates that exhaustive subgroup fairness with principled abstention is achievable in practice.

Abstract

Group Fairness

Explore similar work

Towards Provably Fair Machine Learning: Bayesian Approaches For Consistent and Transparent Predictions

Bayesian Online Model Selection

FairBED: Incorporating Fairness into Bayesian Experimental Design