Online Learning with Sample Selection Bias

Personalized recommendation systems often face the challenge of making optimal decisions when user preferences are unknown, and outcomes are only observed if users engage with the platform (e.g., clicking a recommendation). In their paper, “Online Learning with Sample Selection Bias,” Singhvi and Singhvi study this problem in the context of sequential decision making, where the censoring of outcomes leads to selection bias. Ignoring this bias results in suboptimal recommendations and linear regret, even for well-performing existing learning algorithms. To address this, they propose the sample selection bandit (SSB) algorithm, which combines Heckman’s two-step estimator with the “optimism under uncertainty” principle. The authors also demonstrate that SSB achieves a near-optimal regret rate. Extensive numerical experiments using synthetic and real-world donation data confirm that SSB significantly outperforms existing algorithms, effectively addressing selection bias while improving recommendations and outcomes in practical settings.