Fair Classification with Partial Feedback: An Exploration-Based Data Collection Approach

The evolution of machine learning in high-stakes domains has highlighted issues of bias and fairness, especially under limited feedback conditions. Early efforts like Fairlearn and Adversarial Debiasing addressed bias correction but often assumed full data access. Recent research in active learning and fairness optimization introduced methods combining exploration and exploitation, yet these often rely on strong assumptions or incur high costs. In real-world scenarios such as credit scoring, only positive outcomes (e.g., loan repayment) are observed, leading to biased datasets that propagate unfairness. This paper builds on these foundations, proposing a theoretically grounded exploration framework that ensures fairness and convergence under partial feedback.

The core challenge is that in many applications, outcome labels are only available for samples positively classified in the past. This leads to a biased data distribution, as negatively classified samples remain unlabeled, causing the model to overfit to observed data and propagate biases. Such partial feedback environments hinder the ability to learn fair and accurate classifiers, especially when dealing with protected groups. The difficulty lies in balancing data collection—actively sampling unobserved samples—without incurring excessive false positives or utility loss. Addressing this requires a systematic approach that guarantees exploration, fairness, and utility simultaneously.

The paper introduces a novel iterative framework that combines explicit exploration strategies with FDR constraints, ensuring bounded false positives and comprehensive subgroup exploration. Key innovations include:

• �� Defining 'exploitation' regions based on outcome observation frequency, training classifiers with reweighted distributions to mitigate bias.
• �� Employing exploration strategies (g_clf and g_fair) to sample from underrepresented groups, promoting fairness.
• �� Theoretical guarantees that classifiers improve iteratively, satisfy FDR constraints, and converge to the optimal classifier.
• �� Integrating fairness mechanisms directly into exploration and exploitation phases, reducing disparities across protected groups.

This approach advances beyond prior work by providing formal guarantees and practical algorithms for fair classification under partial feedback.

• �� Initialization: Define 'exploitation' regions where outcome labels are sufficiently observed, based on a weight threshold.
• �� Training: Use reweighted distribution ηw, combining observed data and prior probabilities, to train classifiers that maximize utility while satisfying FDR constraints.
• �� Prediction: Classifiers predict labels for samples in the 'exploitation' region.
• �� Exploration: Samples from the 'exploration' region are selected via strategies g_clf or g_fair, with sampling probabilities proportional to their importance or fairness adjustments.
• �� Label collection: Observe true labels for positively predicted samples, update the 'exploitation' region based on accumulated observations.
• �� Iteration: Repeat the process, gradually expanding the 'exploitation' region, improving classifier performance, and ensuring fairness across groups.

Experiments used Adult Income and German Credit datasets, comparing the proposed method against baseline classifiers. Metrics included true positive rate (TPR), false discovery rate (FDR), and overall accuracy. Multiple FDR thresholds (e.g., 0.05, 0.1) were tested across several iterations. Ablation studies evaluated the impact of different exploration strategies (g_clf vs g_fair), exploration proportions, and fairness constraints. Hyperparameters such as exploration rate and classifier complexity were tuned via cross-validation, ensuring robustness. Results demonstrated consistent TPR improvements, bias reduction, and convergence toward offline optimal performance.

Results showed that the exploration framework increased TPR for all groups by an average of 5.2%, with bias disparities reduced by over 20%. FDR constraints were maintained below the preset thresholds across all iterations. The classifiers progressively approached the performance of the offline optimal model, with an overall accuracy gain of about 8%. The fairness-aware exploration strategy g_fair further reduced group disparities, especially benefiting marginalized subpopulations. These outcomes validate the effectiveness of combining exploration with fairness constraints in limited feedback environments.

This approach is directly applicable to credit scoring, healthcare diagnostics, and criminal justice, where outcome labels are limited and fairness is critical. It enables institutions to systematically explore underrepresented groups, improve decision fairness, and meet regulatory constraints like FDR limits. Its iterative nature allows continuous improvement, making it suitable for deployment in dynamic, real-world settings. Future extensions could incorporate deep neural networks and multi-class scenarios, broadening its industry impact.

The framework assumes initial classifiers satisfy certain FDR bounds, which may not hold in highly biased or poorly initialized models. Its efficiency diminishes in extremely high-dimensional or severely imbalanced data. Computational costs increase with data size and model complexity, necessitating further optimization. Additionally, the approach relies on accurate estimates of outcome probabilities, which may be challenging in practice. Addressing these limitations will be key for scaling to large, complex applications.