A Unified Approach to Fair Online Learning via Blackwell Approachability
Year: 2021

Abstract:
We provide a setting and a general approach to fair online learning with stochastic sensitive and non-sensitive contexts. The setting is a repeated game between the Player and Nature, where at each stage both pick actions based on the contexts. Inspired by the notion of unawareness, we assume that the Player can only access the non-sensitive context before making a decision, while we discuss both cases of Nature accessing the sensitive contexts and Nature unaware of the sensitive contexts. Adapting Blackwell’s approachability theory to handle the case of an unknown contexts’ distribution, we provide a general necessary and sufficient condition for learning objectives to be compatible with some fairness constraints. This condition is instantiated on (group-wise) no-regret and (group-wise) calibration objectives, and on demographic parity as an additional constraint. When the objective is not compatible with the constraint, the provided framework permits to characterise the optimal trade-off between the two.

heading: 1 Introduction
text: Classically, the goal of the decision maker in sequential environment is purely performance driven — she wants to obtain as high reward as if she has had a complete information about the environment. In contrast, algorithmic fairness shifts the attention from the performance-driven behavior by taking into account additional ethical considerations. The latter is often formalized via the notion of fairness constraint [10, 26, 6] on the decision maker’s strategies. The goal of this work is to bring to light Blackwell’s approachability theory as a suitable theoretical formalism for fair online learning under group fairness constraints. The appealing feature of this theory is two-fold: first, it gives explicit criteria when learning is possible; second, if this criteria is met, it comes with an explicit strategy.
It is well known that Blackwell’s approachability theory may be used to characterize online learning problems that are tractable and to design strategies to solve them—for instance, for no-regret learning or calibration. Extensive references to such uses may be found in Cesa-Bianchi and Lugosi [5], Perchet [23] and Abernethy et al. [1]. Actually, as noted by the latter two references, no-regret learning, calibration, and approachability imply each other in some sense. The main first achievement of this article is to extend this use to online learning under fairness constraints. This idea, though natural and intuitive, requires some extensions to Blackwell’s approachability theory, like ignoring the target set and having to estimate it.
Related works in fair online learning. Several frameworks have been proposed to tackle various problems of fairness arising in online learning. Blum et al. [4] consider the problem of online prediction with experts and define fairness via (approximate) equality of average payoffs. HébertJohnson et al. [16], Gupta et al. [14] consider the problem of group-wise calibration. (In passing, we may note that Gupta et al. [14] consider some techniques with a flavor of approachability.) Bechavod et al. [2] consider the problem of online binary classification with partial feedback and
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
equal opportunity constraint [15]. We treat the above works as sources of inspiration; they all differ in the specific (sensitive and non-sensitive) information that the Player may or may not access before or after taking an action. We apply the general formalism of approachability theory to give new insights into online learning under fairness constraints, and approach this goal in a unified (and geometric) way. In particular, the generality of this formalism allows to derive (im)possibility results nearly effortlessly. But we also go beyond such a mere compatibility/incompatibility check between the learning objectives and fairness constraints, and note that approachability theory also gives a clear strategy for the study of trade-offs between incompatible learning objectives and fairness constraints, which often arise in batch setup [6].
Outline. We describe our approachability setting in Section 2 and provide some learning objectives (noregret and calibration) and fairness constraints (group-wise controls, demographic parity, equalized average payoffs) that fit our framework. A slight extension of the classical result of Blackwell [3] is required and discussed in Section 3. We then support the generality of our framework by deriving (im)possibility results for some objective–constraint pairs in Section 4. We also illustrate in Section 5 how this formalism can be used to derive optimal trade-offs (Pareto frontiers) between performance and fairness for incompatible objective–constraint pairs; as an example, we deal with group-wise calibration (studied by [16, 14]) under demographic parity constraint. For the sake of exposition, we deal in Sections 2–5 with stochastic sensitive contexts whose distribution is known; Section 6 explains how to overcome this and develops a theory of approachability relying on ignoring but estimating the target set.
Notation. The Euclidean norm is denoted by ‖ · ‖, while the `1 norm is denoted by ‖ · ‖1. Given a convex closed set C ⊂ Rd, we denote by ProjC(·) the projection operator onto C in Euclidean norm.

heading: 2 Fair online learning cast as an approachability problem
text: In this section, we propose a setting for fair online learning based on approachability—a theory introduced by Blackwell [3] (see also the more modern expositions by Perchet [25] or Mertens et al. [22]). More precisely, we consider the following repeated game between a Player and Nature, with stochastic contexts. The existence of these contexts is a (minor) variation on the classical statement of the approachability problem.
The Player and Nature have respective finite action sets A and B. The sets of sensitive and nonsensitive contexts are respectively denoted by S and X . The set X is a general Borel set, while S is a finite set with cardinality denoted by |S|. Typical choices are S = {0, 1} and X = Rm for some m ∈ N. A joint distribution Q on X × S is fixed and is unknown to the Player. Finally, a (bounded) Borel-measurable vector-valued payoff function m : A × B × X × S → Rd, as well as a closed target set C ⊆ Rd, are given and known by the Player. At each round t > 1 the pair of non-sensitive and sensitive contexts (xt, st) ∼ Q is generated independently from the past. The Player observes only the non-sensitive context xt; while Nature also observes xt, it may or may not observe the sensitive context st. Then, Nature and the Player simultaneously pick (possibly in a randomized fashion) bt ∈ B and at ∈ A, respectively. The Player finally accesses the obtained reward m(at, bt, xt, st) and the sensitive context st, while Nature has a more complete monitoring and may observe at and st. We introduce an observation operation G to indicate whether Nature observes xt only—i.e.,G(xt, st) = xt, the case of Nature’s unawareness—or whether Nature observes both contexts—i.e., G(xt, st) = (xt, st), the case of Nature’s awareness.
We consider the short-hand notation mt := m(at, bt, xt, st),
mT := 1
T T∑ t=1 m(at, bt, xt, st), and cT = ProjC ( mT ) = arg min v∈C ‖mT − v‖
for the instantaneous and average payoffs of the player, as well as the Euclidean projection of the latter onto the closed set C, respectively. The distance of mT to C thus equals dT := ‖mT − cT ‖. The game protocol is summarized on the next page.
We recall that the Player does not know the context distribution Q. Definition 1. A target set C is called m–approachable by the Player under the distribution Q if there exists a strategy of the Player such that, for all strategies of the Nature, mT → C a.s.
PROTOCOL 2.1
Parameters: Observation operator G for Nature; distribution Q on X × S For t = 1, 2, . . .
1. Contexts (xt, st) are sampled according to Q, independently from the past; 2. Simultaneously,
• Nature observes G(xt, st) and picks bt ∈ B; • the Player observes xt and picks an action at ∈ A;
3. The Player observes the reward m(at, bt, xt, st) and the sensitive context st, while Nature observes (at, bt, xt, st).
Aim: The Player wants to ensure that mT → C a.s., i.e., dT = ‖mT − cT ‖ → 0 a.s.
Remark 1 (Awareness for the Player). We are mostly interested in a Player unaware of the sensitive contexts st (Gajane and Pechenizkiy [13]). However, the setting above also covers the case of a Player aware of these contexts: simply consider the lifted non-sensitive contexts x′t = (xt, st).
We now describe payoff functions and target sets corresponding to online learning objectives or online fairness constraints. They may be combined together. For instance, vanilla calibration corresponds below to the mcal–approachability of a set Ccal, demographic parity, to the mDP–approachability of a set CDP, so that vanilla calibration under a demographic parity constraint translates into the (mcal,mDP)–approachability of the product set Ccal × CDP. We therefore consider each objective and each constraint as some elementary brick, to be combined with one or several other bricks. We recall that S is a finite set and will indicate the cases where we only consider S = {0, 1}. We discuss two objectives: no-regret and approximate calibration, as well as three fairness constraints: group-wise (per-group) control, demographic parity, and equal average payoffs.

heading: 2.1 Statement of the objectives
text: For the sake of a more compact exposition, we define the objectives in two forms: global objectives (the vanilla form of objectives) and group-wise objectives. We denote γs = P(st = s), so that (γs)s∈S corresponds to the marginal of Q on S.
Objective 1: (Vanilla and group-wise) no-regret. The definition is based on some payoff function r, possibly taking contexts into account: at each round t, the Player obtains the payoff r(at, bt, xt, st). The aim is to get, on average, almost as much payoff as the best constant action, all things equal. The vanilla (average) regret equals
RT = min a∈A
1
T T∑ t=1 ( r(at, bt, xt, st)− r(a, bt, xt, st) ) ,
while the group-wise (average) regret equals
Rgr,T = min s∈S min a′s∈A
1
T T∑ t=1 ( r(at, bt, xt, st)− r(a′s, bt, xt, st) ) I{st = s} .
The aim is that lim inf RT > 0 a.s. (no-regret) and lim inf Rgr,T > 0 a.s. (group-wise no-regret), respectively. We could replace the 1/T factor by a 1/(γsT ) factor in the definition of Rgr,T , as we will do for the CT calibration criterion, but given the wish of a non-negative limit, this is irrelevant. Denote by N = |A| the cardinality of A. No-regret corresponds to the mreg–approachability of( [0,+∞) )N , with the global payoff function mreg(a, b, x, s) = ( r(a, b, x, s) − r(a′, b, x, s) ) a′∈A. We also duplicate mreg into the group-wise payoff function
mgr-reg(a, b, x, s) = ( mreg(a, b, x, s) I{s′ = s} ) s′∈S .
Group-wise no-regret then corresponds to the mgr-reg–approachability of Cgr-reg = ( [0,+∞) )N |S| .
Objective 2: Approximate (vanilla or group-wise) calibration. Online calibration was first solved by Foster and Vohra [12] and Foster [11]; see the monograph by Cesa-Bianchi and Lugosi [5, Section 4.8] for references to other solutions and extensions. For simplicity, we focus on binary outcomes bt ∈ {0, 1} and ask the Player to provide at each round forecasts at in [0, 1], and even in a discretization of [0, 1] based on a fixed number N > 2 of points:
A = { a(k) := (k − 1/2)/N, k ∈ {1, . . . , N} } .
Each x ∈ [0, 1] can be approximated by some a(k) ∈ A with |x− a(k)| 6 1/(2N). At each round, the Player picks kt ∈ {1, . . . , N} and forecasts at = a(kt). The action set A can thus be identified with {1, . . . , N}. This problem is actually called 1/N–calibration or approximate calibration. The global (vanilla) form of the criterion reads
CT = N∑ k=1 ∣∣∣∣∣ 1T T∑ t=1 ( a(k) − bt ) I{kt = k} ∣∣∣∣∣ , while the approximate group-wise calibration criterion is defined as
Cgr,T = ∑ s∈S N∑ k=1 ∣∣∣∣∣ 1γsT T∑ t=1 ( a(k) − bt ) I{kt = k} I{st = s} ∣∣∣∣∣ . The aim is that lim supCT 6 1/N a.s. or lim supCgr,T 6 1/N , respectively. Note that unlike vanilla calibration, its group-wise version requires to be calibrated on each sensitive attribute s ∈ S. In particular, the classical 1/T factor is replaced by 1/(γsT ), the expected number of appearances of st = s for t = 1, . . . , T .
Mannor and Stoltz [18] and Abernethy et al. [1] rewrote the problem of approximate calibration as an approachability problem as follows: introduce the global payoff function
mcal(k, b) = ( (a(1) − b) I{k = 1}, . . . , (a(N) − b) I{k = N} ) ,
and duplicate it into the group-wise payoff function as follows: mgr-cal(k, b, s) = ( mcal(k, b) I{s = s′}/γs′ ) s′∈S .
The calibration criteria CT and Cgr,T can now be rewritten as the `1–norms of the average payoff vectors mcal,T and mgr-cal,T . Approximate vanilla calibration thus corresponds to the mcal– approachability of Ccal = { v ∈ RN : ‖v‖1 6 1/N } , while approximate group-wise calibration
corresponds to the mgr-cal–approachability of Cgr-cal = { v ∈ RN |S| : ‖v‖1 6 1/N } .
Note that non-sensitive contexts play no role in the calibration objectives, but the Player can (and must) leverage these non-sensitive contexts to possibly infer sensitive contexts when handling group-wise calibration.

heading: 2.2 Statement of the fairness constraints
text: Fairness constraint 1: Group-wise objectives. We already considered possibly group-wise objectives above and Section 4 will show that handling them is already a challenge in our setting where the Player is unaware of the sensitive contexts.
Fairness constraint 2: Demographic parity. We will consider it only in the setting of approximate calibration and further restrict our attention to the case of two groups: S = {0, 1}. The demographic parity criterion measures the difference between the average forecasts issued for the two groups:
DT = ∣∣∣∣∣ 1γ0T T∑ t=1 at I{st = 0} − 1 γ1T T∑ t=1 at I{st = 1} ∣∣∣∣∣ . Given the discretization used, the wish is that lim supDT 6 1/N . Abiding by a demographic parity constraint is equivalent to mDP–approaching CDP = { (u, v) ∈ R2 : |u− v| 6 1/N } , where
mDP(k, s) = ( a(k) I{s = 0}/γ0, a(k) I{s = 1}/γ1 ) .
Fairness constraint 3: Equalized average payoffs. This criterion is to be combined with a noregret criterion; in particular, a base payoff function r is considered. We restrict our attention to the case of two groups, S = {0, 1}, and measure the difference of average payoffs:
PT = ∣∣∣∣∣ 1γ0T T∑ t=1 r(at, bt, xt, st) I{st = 0} − 1 γ1T T∑ t=1 r(at, bt, xt, st) I{st = 1} ∣∣∣∣∣ . Ensuring lim supPT 6 ε corresponds to meq-pay–approaching Ceq-pay = { (u, v) ∈ R2 : |u− v| 6 ε } , where meq-pay(a, b, x, s) = ( r(a, b, x, 0) I{s = 0}/γ0, r(a, b, x, 1) I{s = 1}/γ1 ) . Remark 2. Note that in this general form, the equality of average payoffs encompasses the demographic parity constraint. Indeed, the latter is obtained by setting r(a, b, x, s) = a and ε = 1/N .

heading: 2.3 Summary table
text: The table below gives a summary of different criteria and associated pairs of payoff function and target set. We remark that some of the payoff functions depend on the marginals (γs)s∈S . Meanwhile, Protocol 2.1 assumes the perfect knowledge of the former. In Section 6 we will show how to bypass this issue, transferring all the unknown quantities into the target set and estimating it.
Criterion Vector payoff function Closed convex target set Calibration mcal(k, b) = ( (a(k ′) − b) I{k = k′} ) k′∈A Ccal = { v ∈ RN : ‖v‖1 6 1/N } Group-calibration mgr-cal(k, b, s) = ( mcal(k, b) I{s = s′}/γs′ ) s′∈S Cgr-cal = { v ∈ RN |S| : ‖v‖1 6 1/N
} No-regret mreg(a, b, x, s) = ( r(a, b, x, s)− r(a′, b, x, s) ) a′∈A Creg = ( [0,+∞)
)N Group-no-regret mgr-reg(a, b, x, s) = ( mreg(a, b, x, s) I{s′ = s} ) s′∈S Cgr-reg = ( [0,+∞)
)N |S| Demographic parity mDP(k, s) = ( a(k) I{s = 0}/γ0, a(k) I{s = 1}/γ1 ) CDP = { (u, v) ∈ R2 : |u− v| 6 1/N
} Equalized payoffs meq-pay(a, b, x, s) = ( r(a, b, x, s′) I{s = s′}/γs′ ) s′∈{0,1} Ceq-pay = { (u, v) ∈ R2 : |u− v| 6 ε }

heading: 3 Approachability theory adapted
text: We provide a rather straightforward extension of the approachability theory to deal with Protocol 2.1, namely, with the existence of stochastic contexts, drawn according to an unknown distribution Q. We want to characterize closed convex sets that are approachable.
Pure vs. mixed actions. To conclude the description of the setting, we provide more details on the randomized draws of the (pure) actions at+1 and bt+1 of the Player and Nature at round t+ 1. We denote by ht the information available to Player at the end of round t, and by Ht the full history of the first t rounds: ht = (mt′ , xt′ , st′)t′6t and Ht = (at′ , bt′ , xt′ , st′)t′6t. At the beginning of round t+ 1, the Player thus picks in a ht–measurable way a measurable family ( pxt+1 ) x∈X of probability distributions over A (i.e., a collection of distributions such that x ∈ X 7→ pxt+1 is Borel-measurable), and then draws at+1 independently at random according to the mixed action p xt+1 t+1 . Similarly, Nature
picks in a Ht–measurable way a measurable family ( q G(x,s) t+1 ) (x,s)∈X×S of probability distributions over B, and uses qG(xt+1,st+1)t+1 to draw bt+1.
Approachability strategy. We adapt the original strategy by Blackwell [3] by asuming the existence of and substituting a sequence of estimates Q̂t that are ht–adapted in place of the unknown distribution Q. We will assume that this sequence is convergent in the total variation distance in the sense of Assumption 1 below. To state the strategy, we extend linearly m: for all probability distributions p over A and q over B, for all (x, s) ∈ X × S,
m(p, q, x, s ) = ∑ a∈A ∑ b∈B p(a) q(b)m(a, b, x, s) .
Now, the Player uses an arbitrary measurable family of distributions (px1)x∈X for the first round, gets the estimate Q̂1, and then uses, for rounds t+ 1, where t > 1:
(pxt+1)x∈X ∈ arg min (px)x∈X max (qG(x,s))(x,s)∈X×S
〈 mt − ct, ∫ X×S m ( px, qG(x,s), x, s ) dQ̂t(x, s) 〉 , (1)
where the minimum and maximum are over all measurable families of probability distributions over A and B, respectively. The Player then gets access to ht+1 and may compute the estimate Q̂t+1 to be used at the next round.
Necessary and sufficient condition for approachability. We were able to work out such a condition under the assumption that Q can be estimated well enough, e.g., faster than at a 1/ ln3(T ) rate in total variation distance. We recall that the total variation distance between two probability distributions Q1 and Q2 on X × S equals (see, e.g., Devroye [8]):
TV(Q1,Q2) = sup E⊆X×S ∣∣Q1(E)−Q2(E)∣∣ = 1 2 ∫ X×S ∣∣g1(x, s)− g2(x, s)∣∣dµ(x, s) , where the supremum is over all Borel sets E of X × S, and where g1 and g2 denote densities of Q1 and Q2 with respect to a common dominating probability distribution µ. Assumption 1 (fast enough sequential estimation of Q). The sequence of (ht)–adapted estimators
(Q̂t) used is such that ∑+∞ t=1 1 t √ E [ TV2(Q̂t,Q) ] < +∞. The above assumption implies both 1T ∑T−1 t=1 √ E [ TV2(Q̂t,Q) ] and ∑ t>T+1 1 t √ E [ TV2(Q̂t,Q)
] converge to zero (with T ; see Appendix A for details). Assumption 1 is trivially satisfied in the case when Q is known, as it is sufficient to take Q̂t = Q. When both X and S are finite sets, we may use the empirical frequencies as estimators Q̂t; they satisfy E[TV2(Q̂t,Q)] = O(1/t); see, e.g., [7, Lemma 3]. The general case of an uncountable X , e.g., X = Rm requires results for density estimation in the L1 or L2 norms; such results rely typically on moving averages or kernel estimates and may be found, for instance, in the monographs by Devroye and Györfi [9] and Devroye [8] (see also Tsybakov [28]). Under mild conditions, the estimation takes place at a polynomial rate in total variation distance (e.g., a T−1/5 rate in dimension m = 1). Note that the needed rate of decrease for E [ TV2(Q̂t,Q) ] in Assumption 1 is extremely slow: a 1/ ln3(T ) rate would suffice.
Assumption 2 (boundedness). We assume that ‖m‖∞,2:= max a,b∈A×B sup (x,s)∈X×S ‖m(a, b, x, s)‖<+∞.
We may now state our main result; the distance of mT to C was denoted by dT in Protocol 2.1. Theorem 1. Assume that C is a closed convex set and that Assumptions 1 (fast enough sequential estimation of Q) and 2 (bounded reward function) are satisfied, then C is approachable if and only if
∀(qG(x,s))(x,s)∈X×{0,1} ∃(px)x∈X s.t. ∫ X×S m ( px, qG(x,s), x, s ) dQ(x, s) ∈ C . (2)
In this case, the strategy of Eq. (1) achieves the following rates for L2 and almost-sure convergences:
E [ d2T ] 6
√ K
T + 4‖m‖∞,2
:=∆T︷ ︸︸ ︷ 1
T T−1∑ t=1 √ E [ TV2(Q̂t,Q) ] and
P (
sup t>T dt > ε
) 6 3K
Tε2 + 16‖m‖∞,2 ε2
(√ K
T − 1 + 2 ( sup t>T ∆t )( ∆T+ ∑ t>T 1 t √ E [ TV2(Q̂t,Q) ])) where K < +∞ denotes the maximal distance to C of an element of the compact set m(A,B,X ,S).
The proof lies in Appendix A. The necessity part of the theorem actually relies on no assumption other than C being closed; it consists of showing that Nature has a stationary strategy such that there exists α > 0 with dT > α in the limit, i.e., the average payoff vectors mT remain α–away from C in the limit. This exactly indicates that the underlying fair online learning problem is not tractable: the underlying objectives and underlying fairness constraints cannot be simultaneously satisfied.

heading: 4 Working out some objective–constraint pairs: (im)possibility results
text: In this section we apply Theorem 1 to deal with some examples of objective–constraint pairs described in Sections 2.1 and 2.2. Some of them have been considered before in the literature (sometimes in the batch setup) using various tools [4, 16, 21, 14], as discussed in Section 1.
We keep the original criteria and obtain possiblity or impossibility results. This is a first step, meanwhile, Section 5 will explain how to go further and obtain a trade-off, if needed, between the objective and the fairness constraint.
Additional notation. We recall that γs = P(st = s) and denote by Qs the conditional distribution of xt given st=s, so that dQ(x, s) = γs dQs(x). We denote by supp(Qs) ⊆ X the support of Qs.
Example 1: Vanilla calibration under a demographic parity constraint—achievable. Consider the following payoff function and target set, obtained by simultaneously considering the objective of vanilla calibration and the constraint of demographic parity: m = (mcal,mDP) and C = Ccal × CDP. Defining ψ(u1, u2) := |u1 − u2|, the approachability condition (2) then reads as follows (where we introduce short-hand notation C and DP):
∀(qG(x,s))(x,s)∈X×{0,1} ∃(px)x∈X s.t.  C := ∥∥∥∥∥ ∫ X×{0,1} mcal ( px, qG(x,s) ) dQ(x, s) ∥∥∥∥∥ 1 6 1 N ; DP := ψ (∫ X×{0,1} mDP(p x, s) dQ(x, s) ) 6 1 N . (3) Recalling the notation Q0 and Q1 for the conditional distributions, we observe that
DP = ∣∣∣∣∣ ∫ X N∑ k=1 px(k) a(k) dQ0(x)− ∫ X N∑ k=1 px(k) a(k) dQ1(x) ∣∣∣∣∣ . We now show that the condition in Eq. (3) is satisfied. For any (qG(x,s)), we define the family (px) as the constant family ( dirac(QA) ) , where dirac(QA) denotes the Dirac mass supported on QA, the
closest point of A to Q := ∫ X×{0,1} q
G(x,s)(1) dQ(x, s). We have DP = 0 as px does not depend on x. Substituting the expression for mcal into the definition of C, we observe that for such a choice of (px)x∈X , we have
C = ∣∣∣∣∣ ∫ X×{0,1} ( QA − qG(x,s)(1) ) dQ(x, s) ∣∣∣∣∣ 6 12N + ∣∣∣∣∣ ∫ X×{0,1} ( Q− qG(x,s)(1) ) dQ(x, s)︸ ︷︷ ︸
=0 ∣∣∣∣∣ , where the inequality holds by taking the effect of discretization in A into account and by the very definition of Q. The condition of Eq. (3) is thus satisfied. Therefore, under Assumption 1 (the existence of fast enough sequential estimators of Q) and thanks to Theorem 1, the vanilla calibration and the demographic parity can be achieved simultaneously no matter the monitoring of the Nature. Example 2: Group-wise no-regret—mixed picture. Let the target set be Cgr-reg = ( [0,+∞)
)N |S| and the payoff function be mgr-reg, i.e., we consider the case of group-wise no-regret under no additional constraint. The approachability condition in Eq. (2) demands that
∀(qG(x,s)) ∃(px) s.t. ∫ X×S mgr-reg ( px, qG(x,s) ) dQ(x, s) ∈ ( [0,+∞) )N |S| , i.e., (4)
∀(a′, s), ∫ supp(Qs) ∑ a∈A px(a) (∑ b∈B qG(x,s)(b) ( r(a, b, x, s)− r(a′, b, x, s) )) dQs(x) > 0 .
No-regret seems a harmless challenge, and it is so when the sensitive context is directly observed by the Player, which we do not assume. (In this case, the Player may simply run several no-regret algorithms in parallel, one per sensitive group s.) In our context, the direct observation is emulated in some sense when the non-sensitive context x reveals the sensitive context s; this is the case, for instance, when the supports of the distributions Qs are pairwise disjoint. Note, however, that these distributions Qs are unknown to the Player and need to be learned. The second part of Proposition 1
shows that in this case, the group-wise no-regret may be controlled. We get a similar control in the case of irrelevant sensitive contexts, i.e., not affecting the payoffs and not used by Nature; see the first part of Proposition 1, which corresponds to the case of vanilla no-regret minimization. In both cases, the group-wise no-regret can be controlled under Assumption 1, thanks to Theorem 1. However, as we show by means of counter-examples, these are the only cases that may be favorably dealt with. Proposition 1. The condition of Eq. (4) holds when
• the sensitive context is irrelevant, i.e., the payoff function is such that r(a, b, x, s) = r(a, b, x) and Nature’s monitoring is G(x, s) = x;
• for all s 6= s′, it holds that supp(Qs) ∩ supp(Qs′) = ∅, no matter Nature’s monitoring G. Otherwise, the condition of Eq. (4) may not hold.
Proof. We mimic the classical proof of no-regret by approachability for the positive results. For the first positive result: for any (qx), we define ax ∈ arg maxa∈A ∑ b∈B q
x(b) r(a, b, x) and let (px) = ( dirac(ax) ) . For the second positive result: fix any (qG(x,s)); we define (px)x∈X point-wise as follows. For all s ∈ S, all x ∈ supp(Qs), we set px = dirac(ax), where we validly define ax ∈ arg maxa∈A ∑ b∈B q
G(x,s)(b) r(a, b, x, s) on the union of the supports of (Qs)s∈S , since they are pair-wise disjoint; we define the ax arbitrarily elsewhere.
Two counter-examples detailed in Appendix B back up the final part of the proposition: we show that Eq. (4) does not hold. In the first counter-example, the monitoring is G(x, s) = x, the payoff function depends on s, and the supports of (Qs)s∈S have non negligible intersection. In the second example, the monitoring is G(x, s) = (x, s), the payoff function does not depend on s, and the supports of (Qs)s∈S have non negligible intersection.
Example 3: (Vanilla) no-regret under the equalized average payoffs constraint. For the sake of space we deal with this example in Appendix B, obtaining similar conclusions as that of Blum et al. [4].

heading: 5 Group-wise calibration under a demographic parity constraint: trade-off
text: In this section, we consider the problem of group-wise calibration under the demographic parity constraint; in particular, S = {0, 1}. As we will see, except for special cases, the corresponding two error criteria cannot be simultaneously smaller than the desired 1/N in the limit. However, a (possibly optimal) trade-off may be set between the calibration error ε and the violation level δ of demographic parity. To that end, we introduce neighborhoods of the original target sets Cgr-cal and CDP:
Cεgr-cal = { v ∈ R2N : ‖v‖1 6 ε } and CδDP = { (u, v) ∈ R2 : |u− v| 6 δ } .
A pair (ε, δ) ∈ R+×R+ is said achievable when Cεgr-cal×CδDP is approachable with m = (mgr-cal,mDP). Theorem 1 provides a characterization of this approachability as well as an associated strategy; in particular, when (ε, δ) is achievable, this strategy ensures that the calibration error CT and the violation DT of demographic parity satisfy: lim supCT 6 ε a.s. and lim supDT 6 δ a.s.
The goal of this section is to identify all achievable pairs (ε, δ). We will do so by determining, for δ > 0 of interest, the smallest ε > 0 such that (ε, δ) is achievable1; we denote it by ε?(δ). The line( δ, ε?(δ) ) is a Pareto frontier.
Re-parametrization of the problem. Under Assumption 1 (the existence of fast enough sequential estimators of Q) and thanks to Theorem 1, the (mgr-cal,mDP)–approachability of Cεgr-cal × CδDP holds if and only if the condition of Eq. (2) is satisfied. The latter can be stated as follows:
∀(qG(x,s))(x,s)∈X×{0,1} ∃(px)x∈X s.t.  ∥∥∥∥∥ ∫ X×{0,1} mgr-cal ( px, qG(x,s) ) dQ(x, s) ∥∥∥∥∥ 1 6 ε ; ψ (∫ X×{0,1} mDP(p x, s) dQ(x, s) ) 6 δ ,
(5) 1Note that if (ε, δ) is achievable, then (ε′, δ′) with ε′ > ε and δ′ > δ is also achievable.
where we recall that ψ(u1, u2) = |u1 − u2|. Now, one can show (see comments after Lemma 3 of Appendix C) that the ψ( . . . ) term above is always smaller than TV(Q0,Q1). Thus, we can re-parameterize the problem and focus only on δτ = τ · TV(Q0,Q1), where τ ∈ [0, 1].
Computation of the Pareto frontier. The condition of Eq. (5) indicates that
ε?(δτ ) = max (qG(x,s)) min (px) ∥∥∥∥∥ ∫ X×{0,1} mgr-cal ( px, qG(x,s), s ) dQ(x, s) ∥∥∥∥∥ 1
s.t. ψ (∫ X×{0,1} mDP(p x, s) dQ(x, s) ) 6 τ · TV(Q0,Q1) . (6)
Propositions 2 and 3 below compute the values (up to the 1/N discretization error) of ε?(δτ ) in two scenarios, depending on whether Nature observes the sensitive contexts st. Proposition 2 (Nature awareness: G(x, s) = (x, s)). Under Assumption 1 and with the monitoring G(x, s) = (x, s) for Nature, the Pareto frontier ( ε?(δτ ), δτ ) τ∈[0,1] of achievable pairs satisfies
δτ = τ · TV(Q0,Q1) and 1− τ · TV(Q0,Q1) 6 ε?(δτ ) 6 1− τ · TV(Q0,Q1) + 1
N .
Proposition 3 (Nature unawareness: G(x, s) = x). Under Assumption 1 and with the monitoring G(x, s) = x for Nature, the Pareto frontier ( ε?(δτ ), δτ ) τ∈[0,1] of achievable pairs satisfies:
δτ = τ · TV(Q0,Q1) and (1− τ) · TV(Q0,Q1) 6 ε?(δτ ) 6 (1− τ) · TV(Q0,Q1) + 1
N .
The parameter τ ∈ [0, 1] is set by the user. We observe that in the case when the true label bt provided by the Nature can be directly influenced by the sensitive attribute st, Proposition 2 shows that approximate group-wise calibration with ε = 1/N is never possible, unless TV(Q0,Q1) = 1 (and τ = 1 is picked). The latter case corresponds to the situation when the supports of Q0 and Q1 are disjoint, hence allowing the Player to infer the sensitive context s from the non-sensitive one x, essentially reducing (up to unknown Q) the problem to the previously studied setup of Player’s awareness [16].
When the true label bt provided by the Nature is not directly influenced by the sensitive attribute st (it is influenced by st only via xt), Proposition 3 indicates that calibration is always possible by setting τ = 1, no matter the value of TV(Q0,Q1). Interestingly, this proposition also shows that if TV(Q0,Q1) = 0, i.e., the xt and the st are independent, then the Player is able to achieve calibration and satisfy the demographic parity constraint simultaneously.

heading: 6 Approachability of an unknown target set
text: A limitation of the calibration problems under demographic parity constraint discussed in Section 4 (Example 1) and Section 5 is that the unknown probabilities γ0 and γ1 enter the payoff functions mgr-cal and mDP. We already pointed out this issue in Section 2.3. Even worse, the trade-off claimed in Propositions 2 and 3 relies on the knowledge of the unknown TV(Q0,Q1), to set the values of the achievable pair (δ, ε) targeted; that is, the target set is unknown. To bypass the first limitation we transfer the unknown (γ0, γ1) to the target set, which makes the payoff function fully known to the Player. We will then be left with the problem of approaching an unknown target set only. For instance, in the context of Section 5, we can define m̃gr-cal(k, y, s) = (mcal(k, y) I{s = s′})s′=0,1 and m̃DP(k, s) = ( a(k) I{s = 0}, a(k) I{s = 1} ) ,
and set m̃ := (m̃gr-cal, m̃DP). Taking into account the definition of mcal, we note that m̃ does not depend on (γ0, γ1). Furthermore, by considering the closed convex target sets
C̃εgr-cal = { (v0,v1) ∈ R2N : ‖v0‖1γ0 + ‖v1‖1 γ1 6 ε } , C̃δDP = { (u, v) ∈ R2 : ∣∣ u γ0 − vγ1 ∣∣ 6 δ} , we remark that the (m̃gr-cal, m̃DP)–approachability of C̃εgr-cal × C̃δDP is equivalent to the (mgr-cal,mDP)– approachability of Cεgr-cal × CδDP. The unknown quantities appear only in the target set C̃εgr-cal × C̃δDP (and δ and ε count as unknown quantities given the trade-off exhibited), while the payoff m̃ is known beforehand. Thus, it is sufficient to consider the setup of Protocol 2.1 with an unknown target set C.
Approachability strategy for an unknown target set C. We still assume that the Player is able to build an ht–adapted sequence of estimates Q̂t. Additionally, we assume that for Tr := 2r, with r > 0, the Player can construct an hTr–adapted estimate Ĉr of C. We discuss this assumption at the end of this section. We define d(Ĉr, C) = supx∈Ĉr d(x, C). Assumption 3. There existB < +∞ and a summable non-increasing sequence (βr)r>0 such that for all r > 0, the sets Ĉr are convex closed, with ‖v − ProjĈr (v)‖ 6 B for all v ∈m(A,B,X , {0, 1}),
P ( C ⊂ Ĉr ) > 1− 1/(2Tr), and max { E [ d(Ĉr, C)2 ] , E [ d(C, Ĉr)2 ]} 6 β2r .
For all r > 0 and all t ∈ {Tr, . . . , Tr+1 − 1}, define ĉt := ProjĈr (mt). The idea of the approachability strategy is to use ĉt in place of ct in Eq. (1) and update the estimate Ĉr of the target C only at the end of rounds t = Tr. More precisely, the strategy of the Player is:
(pxt+1)x∈X ∈ arg min (px) max (qG(x,s))
〈 mt − ĉt, ∫ m ( px, qG(x,s), x, s ) dQ̂t(x, s) 〉 . (7)
Theorem 2. Under Assumption 3 and the assumptions of Theorem 1, a convex closed set C, unknown to the Player, is m–approachable if and only if Blackwell’s condition in Eq. (2) is satisfied. In this case, the strategy of Eq. (7) is an approachability strategy.
Appendix D.2 provides a proof of Theorem 2. But before we do so, we discuss in Appendix D.1 why and how the target set C may be estimated by sets Ĉr satisfying Assumption 3. The construction is idiosyncratic and strongly depends on the problem and exact setting considered (in particular, whether the set of non-sensitive contexts X is finite or not). We provide an illustration for the target set C = C̃εgr-cal × C̃δDP of Section 5, in the case of a finite set X .

heading: 7 Limitations of the current work and topics for future work
text: The anonymous reviewers of this article pointed out some limitations to or possible extensions of the current work, which we list now.
We only considered, for the sake of readability, the case of demographic parity with two groups. While the criterion of demographic parity easily extends to more groups, the extension of the trade-offs stated in Section 5 is less clear. It would probably involve the total variation distances TV(Qs,Qs ′ ) between each pair Qs and Qs ′ of marginal distributions, where s, s′ ∈ S, or the distances TV(Qs,Q).
The complexity of the generic approachability strategy of Section 3 is at least linear in the number of groups (if an approximate solution is used, and even polynomial in this number for an exact solution), see Mannor and Stoltz [18, Sections 3.3 and 3.4]. The convergence rates achieved in Theorem 1 involve total variation distances that would also probably depend in at least a linear fashion on the number of groups, unless some special structure is assumed. Both facts may be an issue for large numbers of groups. More generally, we only provide in this article a generic strategy, that is, a first approach to tackle a given fair online learning problem, but specific strategies may be more efficient and get better regret bounds, in particular for large numbers of groups. (For instance, for group-wise calibration, Gupta et al. [14] base a specific and computationally more efficient strategy on an exponential surrogate loss: this strategy enjoys a sample complexity only logarithmic in the number of groups.) The design of such specific strategies remains largely open.
As mentioned in the introduction, Bechavod et al. [2] consider the objective of online binary classification and an equal-opportunity fairness constraint, under some partial monitoring known as “apple tasting”. In this article we considered a bandit monitoring for the Player: she observes the reward obtained at each round. Partial monitoring, which was introduced by Rustichini [27], consists of only receiving feedback which is a (possibly) random function of the actions played by the Player and Nature. A theory of approachability under partial monitoring was initiated by Perchet [24], who stated a necessary and sufficient condition (see also Mannor et al. [19]); Mannor et al. [20] then exhibited a computationally more efficient strategy, with improved convergence rates, and Kwon and Perchet [17] finally obtained the optimal convergence rates. A question to investigate is therefore the extension of the results of this article from a bandit monitoring to a partial monitoring.
Acknowledgments and Disclosure of Funding
Evgenii Chzhen was fully funded by grant ANR-11-LABX-0056-LMH (Labex LMH, part of Programme d’investissements d’avenir). Christophe Giraud received partial support by grant ANR-19CHIA-0021-01 (“BiSCottE”, Agence Nationale de la Recherche). Gilles Stoltz has no direct funding to acknowledge.
Additional revenues for authors are: Evgenii Chzhen—none; Christophe Giraud—none; Gilles Stoltz—part time employment as an affiliate professor with HEC Paris.

Review summaries:
The paper looks at the online learning problem with different fairness objectives/constraints from the lens of Blackwell Approachability. Doing so allows one to see what fairness objectives (e.g. group-wise calibration/regret) with possibly additional fairness constraints (e.g. statistical parity) are compatible and immediately give an algorithm, if compatible.   Also, they have given a pretty tight characterization of the pareto frontier for group-wise calibration under demographic parity constraint.  Finally, they give how to try to approach a set where some of the parameters characterizing the set is unknown.

The paper studies an online setting formulated as a game between Player and Nature. On each round, a context is drawn stochastically, consisting of non-sensitive and sensitive parts. Player may only observe the non-sensitive part before making a decision, while both cases of Nature observing the entire context or only the non-sensitive part are discussed. After Nature’s decision, a reward based on the context and two decisions is given to Player. Using this formulation, the authors wish to unify previously suggested approaches to fair online learning, adapting Blackwell’s Approachability theory to handle unknown contexts’ distribution. The suggested framework assists them then in studying the compatibility of previously considered objectives [(vanilla/group-wise) no regret, (vanilla/group-wise) calibration] and fairness constraints (statistical parity, equalized average payoffs), where they provide a general sufficient and necessary condition for such compatibility, and study several specific instantiations. 

The paper presents a general Blackwell approachability based framework for online fair learning in the presence of stochastic (sensitive and non-sensitive) contexts. The framework allows to easily obtain both positive and negative fair learnability results. The authors work out their framework in the standard cases of no regret or calibrated online learning, paired with demographic parity constraints. They also present novel optimal tradeoffs between the  constraints in the case of group-calibrated learning subject to demographic parity. 

The authors aim to provide a framework, extended from Blackwell approachability, to study online learning with fairness constraints, in the presence of stochastic contexts. The authors assume that the distribution of contexts is unknown and needs to be estimated over time. They use the approachability framework to provide conditions under which certain learning objectives are compatible with certain definitions of fairness.