Learning under Endogenous Selection Bias

Deployed classifiers often determine which outcomes become available for future training, creating endogenous selection bias. For example, a pretrial decision system observes whether defendants reoffend or fail to appear in court only for those released, while a lender observes repayment outcomes only for approved applicants. We study this phenomenon in binary classification, where a learner receives a batch of i.i.d. examples in each round and observes labels only for positive predictions. We first show that empirical risk minimization (ERM) on the observed labeled data can fail through self-confirming traps and self-reinforcing mistakes under noisy feedback. We then augment ERM with random exploration and show that, after accounting for initialization, its cumulative excess loss grows sublinearly in both the batch size and the number of rounds, in both realizable and agnostic settings. However, arbitrary exploratory decisions may be infeasible in high-stakes applications. We therefore also develop proper exploration algorithms that implement a single classifier from a prescribed hypothesis class in each round. These algorithms attain comparable guarantees, up to logarithmic factors and an additional cost linear in the batch size, which we show can be unavoidable under fixed initialization.