Fairness with Exponential Weights
This addresses fairness in machine learning by ensuring statistical parity in contextual bandits and classification, though it builds incrementally on existing Hedge/Exp4 methods.
The authors developed a meta-algorithm that converts any Hedge implementation into an efficient contextual bandit algorithm guaranteeing exact statistical parity on every trial, achieving the same asymptotic regret bound as running Exp4 independently for each protected characteristic.
Motivated by the need to remove discrimination in certain applications, we develop a meta-algorithm that can convert any efficient implementation of an instance of Hedge (or equivalently, an algorithm for discrete bayesian inference) into an efficient algorithm for the equivalent contextual bandit problem which guarantees exact statistical parity on every trial. Relative to any comparator with statistical parity, the resulting algorithm has the same asymptotic regret bound as running the corresponding instance of Exp4 for each protected characteristic independently. Given that our Hedge instance admits non-stationarity we can handle a varying distribution with which to enforce statistical parity with respect to, which is useful when the true population is unknown and needs to be estimated from the data received so far. Via online-to-batch conversion we can handle the equivalent batch classification problem with exact statistical parity, giving us results that we believe are novel and important in their own right.