Reviews: Equal Opportunity in Online Classification with Partial Feedback

This paper studies the problem of online classification with partial feedback under the new constraint that the policy satisfies a fairness (equality of false positives) constraint at each round. The paper leverages careful modification of a number of technical tools to prove the O(sqrt(T)) regret with gamma O(T (-1/4)) fairness rate. In particular, they reduce the partial feedback setting to a contextual bandits problem, construct an approximate "fair oracle" using a modification of the reductions approach to fair classification, and then modify ILOVETOCONBANDITS to use this approximate oracle. The relevant inspiration is clearly cited, and the main contribution is combining these tools to effectively handle the fairness constraint in the online learning problem. The proposed algorithm is intuitive: accept everyone in the early rounds to gather data and use this data to determine which classifiers satisfy the constrain.