Source-linked AI summary
Online Learning with an Unknown Fairness Metric
Stephen Gillen, Christopher Jung, Michael Kearns, Aaron Roth
TL;DR
The paper studies online linear contextual bandits when reward optimization must coexist with strong individual fairness constraints defined by an unknown similarity metric. It learns the metric from weak violation-only feedback and achieves logarithmically many fairness violations together with an optimal O(sqrt(T)) regret bound to the best fair policy. The framework initiates fair sequential decision making when payoff and fairness are separate and potentially in tension.
Problem
Online learning must balance reward optimization with individual fairness constraints based on an unknown metric that may differ from the notion of merit.
Method
The algorithm learns an unknown Mahalanobis distance from fairness-oracle feedback identifying violations while solving an adversarial linear contextual bandit problem.
Results
The algorithm achieves logarithmically many fairness violations in T and an optimal O(sqrt(T)) regret bound to the best fair policy.
Takeaways & Limitations
The framework shows that optimal fair decisions can be efficiently learned even without direct knowledge of the fairness metric.
Takeaways & Limitations
The analysis uses weak feedback that does not quantify fairness violations, and allows singular matrices even though they do not define metrics.
Abstract
from arXiv · showhide
We consider the problem of online learning in the linear contextual bandits setting, but in which there are also strong individual fairness constraints governed by an unknown similarity metric. These constraints demand that we select similar actions or individuals with approximately equal probability (arXiv:1104.3913), which may be at odds with optimizing reward, thus modeling settings where profit and social policy are in tension. We assume we learn about an unknown Mahalanobis similarity metric from only weak feedback that identifies fairness violations, but does not quantify their extent. This is intended to represent the interventions of a regulator who "knows unfairness when he sees it" but nevertheless cannot enunciate a quantitative fairness metric over individuals. Our main result is an algorithm in the adversarial context setting that has a number of fairness violations that depends only logarithmically on $T$, while obtaining an optimal $O(\sqrt{T})$ regret bound to the best fair policy.
1 Introduction
This paper studies online linear contextual bandits with an unknown Mahalanobis fairness metric, where fairness feedback identifies violations without quantifying their extent. It develops an efficient approach that balances fairness and reward under adversarial contexts.
- Motivation: The paper addresses individual fairness constraints that may conflict with the merit or reward objective, motivating a separate fairness metric.Individual fairness requires similar individuals to be treated similarly, while the desired notion of merit may differ from or oppose the fairness criterion.
- Problem setting: The learner observes arbitrary d-dimensional contexts for k actions and seeks low regret while satisfying fairness constraints based on an unknown distance function.After choosing according to a distribution, it receives feedback identifying violated context pairs; Mahalanobis distances are the target class.
- Approach: The main result is an efficient algorithm that learns under Mahalanobis fairness constraints from weak violation feedback while competing with the best fair policy.The fairness oracle reports whether observed actions were fair or unfair, without explicitly providing the metric.
- Results: Fairness violations grow only logarithmically with T while regret remains O(sqrt(T)) to the best fair policy in adversarial contexts.Setting ε = O(1/T) yields a logarithmic bound on violations exceeding 1/T, while other regret–fairness tradeoffs are possible.
- Techniques: The approach resolves the tension between mistake-based metric learning and optimistic reward maximization by reconciling progress on fairness violations with low regret.Halving-style methods favor version-space reduction, whereas optimistic choices can lie on the version-space boundary and fail to reduce it substantially.
- Approach: The method combines a linear-programming reduction for learning the unknown metric with machinery for the complete contextual-bandit problem.The simpler known-objective problem is reduced to a weak-feedback linear-learning algorithm before extending the construction to the full setting.
2 Model and Preliminaries
The model combines linear contextual bandits with per-round individual fairness constraints defined by an unknown Mahalanobis distance and learned through violation-only feedback. It seeks low regret relative to the best perfectly fair policy while limiting significant fairness violations against adversarial contexts and distances.
- 2.1 Linear Contextual Bandits: The learner observes k d-dimensional contexts each round, selects one action from a randomized distribution, and receives only that action's stochastic reward.Expected rewards are linear in the contexts, with an unknown coefficient vector; unchosen-action rewards are unobserved.
- 2.2 Fairness Constraints and Feedback: Fairness requires similar contexts to receive similar action probabilities, with fairness defined pairwise within each round rather than across rounds.The fairness definition is a specialization of Dwork et al.'s individual fairness notion and is parameterized by a distance function.
- 2.2 Fairness Constraints and Feedback: The fairness oracle returns which context pairs violate the constraint after observing the learner's action distribution, but does not quantify violation magnitudes.The learner has no initial knowledge of the distance function and receives oracle feedback after choosing its distribution and action.
- 2.2 Fairness Constraints and Feedback: Fairness loss counts pairs that are more than ε-unfair, and the target guarantee bounds this loss with probability 1 in the worst case over rewards, contexts, and allowable distances.The model therefore limits significant violations rather than requiring avoidance of arbitrarily small violations under adversarial contexts.
- 2.3 Regret to the Best Fair Policy: Regret is measured against the per-round distribution maximizing expected reward subject to the true fairness constraints, with high-probability bounds required in the worst case.The benchmark assumes advance knowledge of the true reward parameter and distance function; the distance family is restricted to Mahalanobis distances, including possibly rank-deficient cases.
3 Warmup: The Known Objective Case
The known-objective warmup learns an unknown Mahalanobis fairness metric from weak violation feedback while optimizing a known linear reward objective. A linear-programming reduction with pairwise DistanceEstimator copies achieves logarithmic regret and fairness violations in T.
- The warmup simultaneously achieves logarithmic regret and a logarithmic number of fairness violations when the objective is known and the distance is unknown.
- 3.3 The Algorithm: At each round, the algorithm solves LP(¯r_t, ˆd_t) and samples from the resulting distribution, using estimated pairwise distances in place of the unknown metric.
- 3.2 The Distance Estimator: The unknown Mahalanobis distance becomes a linear estimation problem because squared distances are linear functions of the entries of G = A⊤A.
- 3.3 The Algorithm: Because feedback is available only when fairness constraints are violated or tight, inactive estimators roll back, while mistakes, fairness violations, and regret are charged to estimator mistake bounds.
- 3.3 The Algorithm: When every tight constraint has an accurate distance estimate, per-round regret is small; otherwise a large estimation error can be charged to a DistanceEstimator mistake bound.
- 3.2 The Distance Estimator: The method instantiates one DistanceEstimator(ε^2) copy for each action pair and converts weak feedback into pair-specific distance estimates.
- 3.3 The Algorithm: Setting ε = O(1/(k^3T)) yields regret O(d^2 log(||A⊤A||_F · dkT)), with the proof separating inaccurate-estimate rounds from rounds whose regret is at most εk^3.
4 The Full Algorithm
The full algorithm jointly learns the unknown reward parameter and Mahalanobis distance estimates, then selects fairness-constrained optimistic action distributions. Its regret analysis combines confidence-width bounds with martingale concentration, while fairness loss inherits the distance-estimation guarantee.
- 4 The Full Algorithm: The algorithm combines ridge-regression confidence bounds for unknown rewards with DistanceEstimator-based estimates of the unknown fairness distances.It forms optimistic reward estimates and chooses π_t = π(ˆr_t, ˆd_t).
- 4 The Full Algorithm: The action distribution is computed by applying the fairness-constrained optimization rule to optimistic rewards and estimated distances.The algorithm maintains ˆr_t and ˆd_t and selects actions according to π(ˆr_t, ˆd_t).
- 4 The Full Algorithm: The regret proof decomposes regret into confidence-width terms and controls expected widths through realized widths using martingale concentration.Abbasi-Yadkori et al.'s theorem bounds widths for selected arms, while Azuma-Hoeffding relates realized and expected quantities.
- 4 The Full Algorithm: Theorem 3 provides a high-probability time-horizon regret bound by combining the selected-arm confidence-width result with the concentration lemmas.The supplied passages identify the theorem and its dependence on Lemmas 6 and 8, with λ = 1.
- 4 The Full Algorithm: The fairness-loss guarantee remains the same as in the known-objective case because the distance-estimation procedure is unchanged.Theorem 4 applies to any sequence of contexts and any Mahalanobis distance d(x1,x2) = ||Ax1 − Ax2||2.
5 Conclusion and Future Directions
The paper initiates fair sequential decision making when payoff and fairness are separate and potentially in tension. It shows that optimal fair decisions can be efficiently learned without direct knowledge of the fairness metric, while identifying broader feedback models as future directions.
- 5 Conclusion and Future Directions: The framework efficiently learns optimal fair decisions without direct knowledge of the fairness metric when payoff and fairness may be in tension.The conclusion characterizes this as a stylized setting for fair sequential decision making.
- 5 Conclusion and Future Directions: Future work could relax the fairness feedback assumptions, including partial violation feedback, uninformative violation signals, inconsistent feedback, and approximately Mahalanobis distances.The conclusion also highlights closing the gap between individual and group fairness as an open direction.
A Generalization to Multiple Actions
The framework extends to selecting up to k actions per round by replacing the simplex constraint with a hypercube constraint and benchmarking against the best fair multi-action policy. Fairness loss remains unchanged, while regret scales by a factor of k because daily reward and regret can increase accordingly.
- A Generalization to Multiple Actions: The multiple-action extension allows the algorithm to select as many as k actions per round, increasing the maximum reward per day from 1 to k.The benchmark becomes the best fair policy that can make up to k selections per round.
- A Generalization to Multiple Actions: The regret bound scales by a factor of k because rounds with unbounded per-round regret can incur regret up to k rather than 1.The confidence-width martingale differences are also bounded by k instead of 1 in this extension.
- A Generalization to Multiple Actions: The modified linear program replaces the simplex constraint that action probabilities sum to 1 with a hypercube constraint limiting each probability to at most 1.The regret benchmark is defined with respect to this modified program.
- A Generalization to Multiple Actions: The fairness-loss bound is unchanged in the multiple-action setting because its analysis does not depend on rewards.The policy is defined as before, except relative to the modified linear program.