A Unified Approach to Fair Online Learning via Blackwell Approachability
Authors: Evgenii E Chzhen
Christophe Giraud
Gilles Stoltz
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: online learning
fairness
Blackwell approachability
calibration

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.

A Unified Approach to Fair Online Learning via Blackwell Approachability
Evgenii Chzhen
Christophe Giraud
Gilless Stoltz
Université Paris-Saclay, CNRS, Laboratoire de mathématiques d' d'Orsay, 91405, Orsay, France fevgenii. Levgemii.chzhen, christophe, giraud, gilles. stoltz} Suniverrite-parii-aane fr
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, the non-sensitive context before making 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.
assume that the Player can only access
Introduction
Classically, the goal of the decision maker in sequential environment is purely performance driven she wants to obtain as high reward as she has had a complete information about the environment. In contrast, algorithmic fairness shifts the attention from the performance-driver behavior by taking into account additional ethical considerations. The latter often formalized via the notion faimess constraint [10, 26 66 the decision maker's strategies. The goal of this work is to bring to light Blackwell's s approachability theory as 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 [3 and Abernethy et al. [. Actually, as noted by the latter two references, no-regret learning, calibration, and approachability imply each other in 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.
sense. The main first achievement
Related works in fair online learning. Several frameworks have been proposed to tackle various problems of fairness arising online learning. Blum al. 4 consider the problem of online prediction with experts and define fairness via (approximate) equality of average payoffs. Hébert- Johnson et al. [6], Gupta et al. [14] consider the problem of group-wise calibration. (In passing, we may note that Gupta et al. [4] 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 (NcurIPS 2021).

---

equal opportunity constraint [1]]. We treat the above works as sources of inspiration; they all differ in the specific (sensitive and non 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 unified (and geometric) way. In particular, the generality of this formalism allows to derive (im)possibilitty results nearly effortlessly. But we also go beyond such a mere compatibiityiicoomatibbbl learning objectives and fairness constraints, and note that approachability theory also gives clear strategy for the study trade-offs between incompatible learning objectives and fairness constraints, which often arise in batch setup [6].
check between the
Outline. We describe our approachability setting in Section provide some learning objectives (no- regret and calibration) and fairesss constraints (group-wisc controls, demographic parity, equalized average payoffs) that our framework. 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-constral how this formalism can be used to derive optimal trade-off's (Pareto frontiers) between performance and fairness for incompatible objective-constrainl pairs; as an example, we deal with group-wise calibration (studied by [6 [4]) under demographic parity constraint. For the sake of exposition, we deal in Sections 5 with stochastic sensitive contexts whose distribution is known; Section 6 explains how to overcome this and develops theory of approachability relying ignoring but estimating the target set.
pairs in Section [ We also illustrate in Section
Notation. The Euclidean norm is denoted by || while the & norm is denoted by . |1- Given convex closed set C C Rdd we denote by (-oje()) the projection operator onto C' in Euclidean norm.
2 Fair online learning cast as an approachability problem
In this section, we propose a setting for fair online learning based on approachability- theory introduced by Blackwell [3] (see also the more modern expositions by Perchet [25] 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 non- sensitive contexts are respectively denoted by S and X. The set is general Borel set, while a finite set with cardinality denoted by (S). Typical choices are S = {0, 1} and X' = I for some m E N. joint distribution Q on X' x S is fixed and unknown to the Player. Finally, a (bounded) vector-valued payoff function m A x B x X x S + IRd, as well as closed target set C C ddd are given and known by the Player.
At each round / > 1 the pair of non-sensitive and sensitive contexts (1), ~ Q is generated independently from the past. The Player observes only the non sensitive context 2;; while Nature also observes Zt, it may or may not observe the sensitive context Then, Nature and the Player simultancously pick (possibly
randomized fashion) b, B and a A, respectively. The Player finally accesses the obtained reward m((a, ae, It, s,) and the sensitive context s,, while Nature has a more complete monitoring and may observe 0t and 8t. We introduce an observation operation G to indicate whether Nature observes only only-i.e., G( st) Iı, the case of Nature's 's unawareness -or whether Nature observes both contexts i.e. G( 8t) (æx, the case of Nature's awareness.
We consider the short-hand notation m, == m(ar, br, 8t),
T m(a, by, Ze, st), and Cr Proje (mz)
m&
arg min || vll vEC
for the instantaneous and average payoffs of the player, well as the Euclidean projection of the latter onto the closed set C, respectively. The distance of my to C thus equals dr == || - -r ll- The game protocol is summarized the next page.
We recall that the Player does not know the context distribution Q
Definition 1. A target set C is called m- 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, myr -> C a.s.
2

---

PROTOCOL 2.1
Parameters: Observation operator for Nature; distribution Q on x
For t 1.
1. Contexts (z,, are sampled according to Q, independently from the past;
2. Simultancously,
Nature observes G( se) and picks b2 B;
the Player observes zı and picks action a A;
3. The Player observes the reward maaa, be, 2t, 8t) and the sensitive context 8t. while Nature observes (at, b, Zt. St).
Aim: The Player wants to ensure that my + C a.s., i.., dr = m - črl - 0 a.s.
Remark (Awareness for the Player). We mostly interested in Player unaware of the sensitive contexts &t (Gajane and Pechenizkiy (I3]). However, the setting above also covers the case of a Player aware of these contexts: simply consider the lifted non-sensitive contexts 24 = 8t).
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 approoohhhyyllll of set Ces.. demographic parity, to the ahe-aaproachabilit of set Cop, that vanilla calibration under a demographic parity constraint translates into the (Mai, -aprocchpcahh of the product set Cea x Cnp. We therefore consider each objective and elementary brick, be combined with
each constraint that S is finite set and will indicate the cases where we only consider S {0, 1}.
several other bricks. We recall
We discuss two objectives: no-regret and approximate calibration, well as three faimess constraints:
group-wise (per-group) control, demographic parity, and equal average payoffs.
2.1 Statement of the objectives
For the sake of more compact exposition, we define the objectives in two forms: global objectives (the vanilla form of objectives) and group-wise objectives. We denote 7s- (( 8), so that (7s)ses corresponds to the marginal of Q on S.
Objective 1: (Vanilla and group-wise) no-regret. The definition is based on some payoff func- tion r. possibly taking contexts into account: at each round t, the Player obtains the payoff r(a, Te,
The aim is to get, on average, almost as much payoff as the best constant action, all things equal. The vanilla (average) regret equals
st). st).
Rr = a T
Σ
r(a, by, se,
t=1
while the group-wise (average) regret equals
T by, b., st) br - r(a,. b,, Fz, st)) =}.
R min min SES of EAA
1=1
The aim is that lim inf Ry > a.s. (no-regret) and lim inf Ry. > a.s. (group-wist wise no-regret), respectively. We could replace the 1/T factor by 1/(7,T) factor in the definition of Rg,r. will do for the Of 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 may approachability of b, 2, - r(a', b, x, 8) W'A (lo, +oo)) N with the global payoff function myy (a, b, x, s) = (r(a,
We also duplicate m.g. into the group-wise payoff function
Magrey (a, b, x, 8) (may x. s) =])
Group-wise no-regret then corresponds to the m appronccapooiiii of Currey (10, +00) Mis

---

Objective 2:
Approximate (vanilla or group-wise) calibration. Online calibration was first solved by Foster and Vohra [[2] and Foster [TT]: 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 by E (0. 1} and ask the Player to provide at each round forecasts ae [0, 1]. and even in discretization of (0, 1] based on fixed number N > 2 of points:
A (a == (k: - 1/2)/N, E (1,..,,,,
Each [0, 1] can be approximated by some (* E A with x a!*) & 1 1/(2N). At each round, the Player picks E (1...., N) and forecasts a (kR), The action set A can thus be identified with (1.
This problem is actually called 1 1/N /N-cciiibraiion or approximate calibration. The global (vanilla)
form of the criterion reads
N
T (a bτ) Like = k}
CT
Σ
Σ
k=
while the approximate group-wise calibration criterion is defined as
N
CHrr
Σ t=1
(k) - b.) Ifke Iss s}
ToT
SES
k=1
The aim is that lim sup Cr & 1/N a.s. or lim sup Ca.T < 1/N, respectively, Note that unlike vanilla calibration, its group-wise version requires be calibrated on each sensitive attribute s E S. In particular, the classical 1 I/ factor is replaced by 1/), the expected number of appearances of 8; 8 for = I.
Mannor and Stoltz [18] and Abernethy et al. [ rewrote the problem of approximate calibration as an approachability problem as follows: introduce the global payoff function
maa (k: ((a!)) b) T(E: 1},
(a! b) [[ N)),
and duplicate it into the group-wise payoff function as follows:
Myseu (k., b, b) (m (k. b) I[s = s11/wo)) SES'
The calibration criteria Cr and Cg.T off vectors 7 and m- Approximate vanilla calibration thus corresponds to the m approachability of Cul = {u E R. ||]|| < 1/N]. while approximate group-wise calibration corresponds to the m. approcccityy of Cgr-sal
be rewritten the fo-morms of the average pay-
E I- ||]|| 1/N]].
Note that non 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.
2.2 Statement of the fairness constraints
Fairness constraint 1: Group-wise objectives. We already considered possibly group-wise objec- tives above and Section 4 will show that handling them already challenge in our setting where the Player is unaware of the sensitive contexts.
Fairness constraint 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:
1
Dr
ToT Σ a.lls =}
Σ
a I[s = 13
71 t=1
Given the discretization used, the wish is that lim Dr & 1/N. Abiding by a demographic parity constraint is equivalent to apprapppon Cup = (u, v) E R²: |u ol < 1/N), where
mpr s) =(a (k) 1(s 03/700 a (k) I1s 1)/r1).

---

Fairness constraint 3: Equalized average payoff's. This criterion is to be combined with a no- regret criterion; particular, base payoff function considered. We restrict our attention the case of two groups, S = {0, 1), and measure the difference of average payoffs:
T
Pr
r(ar, Tr, Tz, or, 18+ = - 7I Σ r(a,, be, Ir, 81) 180 = -0
To? t=1
Ensuring lim sup Pr & corresponds to Mappy -aprrocchnn Cuppay = {(u, () E =² lu ul & {E). where
Mayppyy (a, b, 8) = (r(a, b, 0) I/s 03/m0, r(a,b,a 1) 11/-m).
Remark 2. Note that in this general form, the equality of average payoff's encompasses the demo- graphic parity constraint. Indeed, the latter obtained by setting r(a, ((,,,, and L/N.
2.3 Summary table
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 (% sEsss Meanwhile, Protocol 2.1 assumes the perfect knowledge of the former. In Section we will show how bypass this issue, transferring all the unknown quantities into the target set and estimating it.
Criterion
Vector payoff function
Closed convex target set
Calibration
malk, b) = ((att) 1) I[k = k() KTrred
Cu (w E RN |oll & 1/N3
Group-calibration
mg-ailh (k,b,)),)) 8) = (mai(k.
x) )/>w)) (
C (v e RM181 ||el| & 1/N)
No-regret
May (a, b,) - (r(a,b, r(a', 2,, s)) dee mgrong (a, b, 8) (,,
Cug (10, 1x))
Cyong ((0, (11++20)) M
Group-no-regret
Demographic parity
mar(k: s) = 1{s= 00/20 11s=|11
Cop {u, B² ||- 1//N
Equalized payoffs
Maspoy (a, b, a., 8) = (r(a, a,, 11ss= re(0.1)
Cuppy = ((, E R2 |/
3
Approachability theory adapted
We provide 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 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 a&+1 and b of the Player and Nature at round t + 1. We denote by he the information available Player at the end of round t, and by He the full history of the first rounds: h, (mr, Ir, se ge and H, = (a. by, Ze sy )e' gt. At the beginning of round + 1, the Player thus picks in meassuuuable way a measurable family (pī+1) nex of probability distributions over A (i.e., a collection of distributions such that E X' + P 1 is measl-mmasura and then draws dr+11 independently at random according to the mixed action 1 Similarly, Nature G(z,a))
picks in a me-seasurllle way a measurable family (qi-1 (a.))exxx of probability distributions G(#4+1,943)) to draw by-1. over B, and uses dr+1
Approachability strategy. We adapt the original strategy by Blackwell 3 by asuming the exis- tence of and substituting sequence of estimates Q that are hy-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 [ below. To state the strategy, we extend linearly m: for all probability distributions p over A and q over B, for all (z, 8) E X
m(p. q, 2.
ΣΣ p(a) q(b) m(a,b,x,5) aEA
Now, the Player uses an arbitrary measurable family of distributions (pi)xex for the first round, gets the estimate Q1, and then uses, for rounds + 1, where >
1 E arg min (xx) (l. Xxx
max
m&; E, /
m(p", "ap.gGGaan G(a,s) x. (2, (1)
xxs
5

---

where the minimum and maximum are over all measurable families of probability distributions over A and 1, respectively. The Player then gets access to h4+1 and may compute the estimate Q++1 to be used at the next round.
Necessary and sufficient condition for approachability. We were able to work out such con- dition under the assumption that Q can be estimated well enough, e.g., faster than at a 1/ In (T) rate in total variation distance. We recall that the total variation distance between two probability distributions Qi and Q2 on X' x S equals (see, e.g.. Devroye {]:
1
TV(Q1, Q2)
sup xCXXS
Qi(E) - Q2(E)
(1( 92(2, s) du(z,s). xxs
where the supremum is over all Borel sets E' of X' x S, and where 91 and g2 denote densities of Q₁ and Q2 with respect to a common dominating probability distribution μ. Assumption 1 (fast enough sequential estimation of Q). The sequence of -adaped estimators (Q:) used is such that Ete 1 E (TV Q)] +00.
The above assumption implies both + E E E Q)] and Eirr+i iv E TTV Q) converge to zero (with T: see Appendix A for details). Assumption i trivially satisfied in the case when Q is known, as it is sufficient take Q, = Q. When both X and S are finite sets, we may use the empirical frequencies estimators Q they satisfy E[TV² Q)] O(1/t); see, e.g.. [7 Lemma 3]. The general case of an uncountable X, e.g., X' = R= requires results for density estimation in the T,¹ or T,2 norms; such results rely typically on moving averages or kernel estimates and may be found, for instance, in the monographs by Devroye and Györf [9] and Devroye [ (see also Tsybakov (28). Under mild conditions, the estimation takes place at a polynomial rate total variation distance (e.g., T
1/5 rate in dimension m 1). Note that the needed rate of decrease for
E [[TV Q)] in Assumption is extremely slow: a 1/Inn In (T) rate would suffice.
Assumption 2 (boundedness). We assume that ||m o0.2 B
sup
|m(a, b, s)]<<
We may now state our main result; the distance of my to C was denoted by dr in Protocol 2.
Theorem 1. Assume that C is a closed convex set and that Assumptions (fast enough sequential estimation of Q) and (bounded reward function) are satisfied, then C is approuchable if and only if
Je m(p", .q Gla.s) s) (Q(z, EC. (2)
b(q G(2,6) (x,s)xXxx (0.1) 3(p")xEe
JxxS
In this case, the strategy of Eq. ① achieves the following rates for L and almost-sure convergences:
K T
E[cl < V
+
4||m
20.2
[TV2 (Q.,
Q1]
and
P supd, 26 1TT
3K TEa
16 16|[m||
00.2
K T
sup D, ) AT+ E V (111)) o11)
where K < too denotes the maximal distance to C of an element of the compact set m 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; consists of showing that Nature has a stationary strategy such that there exists a > 0 with dr 2 a in the limit, i.e., the average payoff vectors my remain a-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 simultancously satisfied.
Working out some objective-constraitt pairs: (im)possibility results
In this section we apply Theorem to deal with some examples of objective-constraint constraint pairs described in Sections 2.T and 2.2 Some of them have been considered before in the literature (sometimes the batch setup) using various tools 4 16 14), as discussed in Section I

---

We keep the original criteria and obtain possiblity or impossibility results. This is first step, meanwhile, Section will explain how to go further and obtain trade-off, if needed, between the objective and the fairness constraint.
Additional notation. We recall that 7ss ((2 = 8) and denote by Q the conditional distribution of It given s; so that dQ(z, s) = dQ (z). We denote by QQ") S X the support of Q*
Example 1: Vanilla calibration under a demographic parity constraint- sider the following payoff function and target set, obtained by simultaneously considering the objective of vanilla calibration and the constraint of demographic parity: m (maa. mpr) and = x CDp.
Con-
Defining (w1, (2) (11 u2l. the approachability condition introduce short-hand notation C and DP):
2 then reads follows (where
Vex Mea (p" a ((z,)) dQ(x, 8)
< N
v(g ((s.)) (x,0)xx((001 3(p")x(e 2zE s.t.
= $ (Vex morlp" dQ(2,))
N
(3)
Recalling the notation Q and Q' for the conditional distributions, we observe that
f De*()) dQ
Σ (k) (x)
DP
x
We now show that the condition in Eq. is satisfied. For any (q we define the family (p") as the constant family (dirac(QAA). where (Qra)(Q.A) denotes the Dirac mass supported on Q.A. the closest point of A to Q Jxx 10.1; (l (1) dQ s). We have DP 0 p does not depend Substituting the expression for maa into the definition of C, observe that for such choice of )xEx, we have
c c= - (QA- ((x)) s)
V (Q- 2N
1
( (l.)) (Q(z,s)
<
where the inequality holds by taking the effect of discretization A into account and by the very definition of Q. The condition of Eq. (3) is thus satisfied. Therefore, under Assumption (the existence of fast enough sequential estimators of Q) and thanks Theorem [ the vanilla calibration and the demographic parity can be achieved simultaneously matter the monitoring of the Nature.
Example 2: Group-wise no-regret-mixxd picture. Let the target set be Carreg = ([0, +oo)) ||S| and the payoff function be mg i.e., we consider the case of group-win wise no-regret under additional constraint. The approachability condition in Eq. (2 demands that
V(g G(a.o)) 3(p*) s.l.
mygm G(a,e)) dQ(x,s) ((0++0o)) NiSI
i.e., (4)
((a',s),
Ep'(a)
(() (r(a,b, ( dQ*(x) 0.
Supp((Q") aEA
hEB
No-regret seems 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 parallel, one per sensitive group s.) our context, the direct observation emulated in some sense when the non-sensitive context reveals the sensitive context 8; this is the case, for instance, when the supports of the distributions Q" are pairwise disjoint. Note, however, that these distributions Q* are unknown to the Player and need to be learned. The second part of Proposition ]
7

---

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 payoff's and not used by Nature: see the first part of Proposition [ which corresponds to the case of vanilla no-regret minimization. In both cases, the group-wise no-regret can be controlled under Assumption I thanks to Theorem TT 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. A holds when
the sensitive context is irrelevant, i.e., the payofffunction function is such that r(a, b, x, r(a, b,
and Nature's 's monitoring is G(z, 8) = 2;
* for all + s', it holds that supp Q²) n suspp( (Qx) = 0, no matter Nature's 's monitoring G. Otherwise, the condition of Eq. 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 (q"), we define a² arg max EsEB qº (b) ba)) and let (p") = (dirac(a*)) )). For the second positive result: fix any (qC(),))); we define (p" "x=) point-wise as follows. For all 8 E S, all E supp(Q"), we set p" dirac(a"), where we validly define a" E arg max4e,4 EbEs (C(x,))(b) r(a, b, x, 8) on the union of the supports of (Q*)ses, since they are pair-wise disjoint; we define the a" 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(z, s) = x, the payoff function depends on s, and the supports of (Q") ses have non negligible intersection. In the second example, the monitoring is G(z, s) = (zz s), the payoff function does not depend on s, and the supports of (Q") .Es have non negligible intersection.
Example 3: (Vanilla) no-regret under the equalized average payoll's constraint. For the sake of space we deal with this example in Appendix B. obtaining similar conclusions that of Blum et al.
5 Group-wise calibration under a demographic parity constraint: trade-off
In this section, we consider the problem of group-wise calibration under the demographic parity constraint; in particular, S = 10. 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, (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 Cyreat and Cre:
Cyrcal { TVEPP R2N; ||0||| <c} and C = {u, v) E R² |u v| < <
X A pair 0) E R. x R. is said achievable when x is approachable with Theorem
(m mpe). D provides a characterization of this approachability as well as an associated strategy; in particular, when (E, 8) is achievable, this strategy ensures that the calibration error Cr and the violation Dr of demographic parity satisfy: lim lim Cr & a.s. and lim sup Dr & 5 a.s.
The goal of this section is to identify all achievable pairs (c, We will do so by determining, for 8 > 0 of interest, the smallest > such that (e, is achievable we denote it by e* s6)). The line (6, 8* (0)) is Pareto frontier.
Re- pa--aaerrrizaiinn of the problem. Under Assumption (the existence fast enough sequential estimators of Q) and thanks to Theorem 1. the (mag-cal: p -approachability of Ca x Cpp holds if and only the condition of Eq. (2) is satisfied. The latter can be stated as follows:
ma (D" .9 G(r,)) dQ(xz
<
(e.))xxx1))) 3(p") s.t.
(Vertan mor(p", ())ppp"s(((a)))) <0,
(5)
'Note that if (c,8) is achievable, then (e', 86) with e' ' and 8' 3 8 also achievable.
8

---

where we recall that (bu1, u2) lu1 u2/- Now, one can show (see comments after Lemma of Appendix C that the v(...) term above is always smaller than TV" Q'). Thus, we can re-parameterize the problem and focus only on 6, TVQQ,, Q²), where E [0, 1).
Computation of the Pareto frontier.
The condition of Eq. indicates that
W Mgrcal"", g(l dQ(x,
(6,)) = max ((o))))
min (p=)
(6)
s.t. (Fortoss mpe .) dQ
< TT- Q!).
Propositions 2 and 3 below compute the values (up to the I/N discretization error) of of (ō,, ) in two scenarios, depending whether Nature observes the sensitive contexts 8t.
Proposition 2 (Nature awareness: G(z, s) (x) Under Assumption [and with the monitoring G(z, s) (z, s) for Nature, the Pareto frontier (e"(),), ),) of achievable pairs satisfies
8, = r. TV(QQ) ( and -- TV(Q", ( & <6,) < - TV(Q", .Q') + N
Proposition 3 (Nature unawareness: G(x, = x). Under Assumption 7 Mand with the monitoring G(x,, 8) - for Nature, the Pureto fromtierr (s* (ō+), 8r) rEjo11) of acchivabble pairs satisfies:
6, = T TV(Q", Q!) and (1-7)- TV(Q", Q²) & (6,) < -V(Q),
The parameter [0, 1] is by the user.
We observe that in the case when the true label b, 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", the situation when the supports of Q and Q' 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].
= 1 (and t = 1 is picked). The latter case corresponds to
When the true label provided by the Nature not directly influenced by the sensitive attribute (it is influenced by only via xz), Proposition 3 indicates that calibration is always possible by setting т 1, no matter the value of (V(Q", Q)). Interestingly, this proposition also shows that if (VQ Q+) = 0, i.e., the 2 and the 8, are independent, then the Player is able to achieve calibration and satisfy the demographic parity constraint simultancously.
Approachability of an unknown target set
limitation of the calibration problems under demographic parity constraint discussed in Section (Example and Section 5 is that the unknown probabilities inn and 71 enter the payoff functions mgra and mpp- We already pointed out this issue in Section 2.3 Even worse, the trade-off claimed in Propositions 2 and relies on the knowledge of the unknown TV Q*), to set the values of the achievable pair (0,s) targeted; that is, the target set is unknown. To bypass the first limitation we transfer the unknown (Yo, 71) 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
migrcal (k, y, 8) = (k: y) 11 = s') s'})==0, and mo s) = (a I1fs = 0}, a (b) L1s = 13)
and set i == (m grahl Mor). Taking into account the definition of maai we note that m does not depend on (vo. 71). Furthermore, by considering the closed convex target sets
grccll (vo.
v1) (1)) RR
||vo
<E).
C. = { {u,,)) e R
1 -=-- 1-1
<
70
71
we remark that the (Mareas mpr) approachability of Čr.... x Co. is equivalent to the (mar mpp approachability of Ca x Cg. The unknown quantities appear only the target set greal
č= x Cp. (and
5 and & count as unknown quantities given the trade-off exhibited), while the payoff m known beforchand. Thus, it is sufficient to consider the setup of Protoco] 2.1 with unknown target set C.

---

Approachability strategy for an unknown target set C. We still assume that the Player is able to build an hy-adapted sequence of estimates Qt- Additionally, we assume that for T, == 2", with r > O, the Player can construct an lt,, -adapted estimate é, of C. We discuss this assumption at the end of this section. We define d(Cr, C)) suP,cč, d(s,C) C)-
Assumption 3. There exist B < too and a summable non-increasing sequence (3+)r20 such that for all r > 0, the sets Cr are convex closed, with || Proje, (v)]l < B for all v E m(A, U,A, X, , fo. 1}),
P(C C C.) (- 1/(TT),,, and max [[d(Cr, B [[d(C, < B2
For all r > 0 and all t E {Tr: Te+1 - 1), define é, := Proje, m,.)) The idea of the approacha-
bility strategy is to use è, in place e in Eq. ① and update the estimate C, of the target only at the end of rounds t = T,.. More precisely, the strategy of the Player is:
mh 1o--e θt, / m(p" .q ((lz,)) x. (1,,
(pix))EEx E arg min max (D*) (g(lsi))
Theorem 2. Under Assumption 3 and the assumptions of Theoreml 7 convex closed set C. unknown to the Player, is mn-approachable if and only if Blackwell's 's condition in Eq. (2) is satisfied. this case, the strategy of Eq. 7 is an approachability strategy.
Appendix providess a proof of Theorem 2 But before we do so, we discuss in Appendix D.I
why and how the target set C may be estimated by sets &, satisfying Assumption 3 The construction is idiosyneratic 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 grecal x Cpp of Section in the case of a finite set X.
Limitations of the current work and topics for future work
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(Q", Q²)) between each pair Q* and Q of marginal distributions, where s, E S, or the distances TV(Q", 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 [ involve total variation distances that would also probably depend in 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 generic strategy, that is, a first approach to tackle given fair online learning problem, but specific strategies may be more efficient and get better regret bounds, particular for large numbers of groups. (For instance, for group-wis wise calibration, Gupta et al. [14] base 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. consider the objective of online binary classifi- cation 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 277,, consists of only receiving feedback which a (possibly) random function of the actions played by the Player and Nature. A theory of approachability under partial monitoring was initiated by Perchet [2]], who stated a necessary and sufficient condition (see also Mannor et al. (99); 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 therefore the extension of the results of this article from bandit monitoring to a partial monitoring.
10

---

Acknowledgments and Disclosure of Funding
Evgenii Chzhen was fully funded by grant ANR-I ANR-II-LANE 1-L-------------LM (Labex LMH, part of Pro- gramme d' d'investissements d' d'avenir). Christophe Giraud received partial support by grant ANR-19- CHIA-0021-01 ("BiSCouE", Agence Nationale de la Recherche). Gilles Stoltz has no direct funding to acknowledge.
Additional revenues for authors Evgenii Chzhen none; Christophe Giraud none; Gilles
Stoltz part time employment as an affiliate professor with HEC Paris.
References
[1] Abernethy, Bartlett, and E. Hazan. Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory, volume PMLR 19, pages 27-46, 2011.
[2] Y. Bechavod, K. Ligett, A. Roth, B. Waggoner, and S. Wu. Equal opportunity in online classification with partial feedback. In Advances in Neural Information Processing Systems, volume 32, 2019.
[3] D. Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1):1-8, 1956.
[4] A. Blum, Gunasekar, T. Lykouris, and N. Srebro. On preserving non donddiccrimnnaooon when combining expert advice. In Advances in Neural Information Processing Systems, volume 31, 2018.
[5] N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[6] A. Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big Data, 5(2):153-163, 2017.
[7] L. Devroye. The equivalence of weak, strong and complete convergence in L1 for kernel density estimates. The Annals of Statistics, 11(3):896-900 1983.
[8] L. Devroye. A Course in Density Estimation. Birkhääser, 1987.
[9] L. Devroye and L. Györfi. Nonparametric Density Estimation: The L View. Wiley, 1985.
[10] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel. Fairness through awareness.
In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 214-220 226, 2012.
[11] D. Foster. proof of calibration via Blackwell's approachability theorem. Games and Economic Behavior, 29:73-78. 78, 1999.
[12] D. Foster and R. Vohra. Asymptotic calibration. Biometrika, 85:379-390. 1998.
[13] P. Gajane and M. Pechenizkiy, On formalizing fairness in prediction with machine learning, 2017. Preprint, arXiv:1710.03184.
[14] V. Gupta, C. Jung, G. Noarov, M. Pai, and A. Roth. Online multivalid learning: Means, moments, and prediction intervals, 2021. Preprint, arXiv:2101.01 011399..
[15] M. Hardt, E. Price, and N. Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems, volume 29, 2016.
[16] U. Hébert-Johnson, M. Kim, O. Reingold, and G. Rothblum. Multicalibration: Calibration for the (computationally-dennii on Machine Learning, volume PMLR 80, pages 1939-1948, 2018.
masses. In Proceedings of the 35th International Conference
[17] J. Kwon and V. Perchet. Online learning and Blackwell approachability with partial monitoring: Optimal convergence rates. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume PMLR 54, pages 604-613, 2017.
11

---

[18] S. Mannor and G. Stoltz. A geometric proof of calibration. Mathematics of Operations Research, 35(4):721-77, 2010.
[19] Mannor, V. Perchet, and G. Stoltz. A primal condition for approachability with partial monitoring. Journal of Dynamics and Games, 1(3):447-469, 2013.
[20] S. Mannor, V. Perchet, and G. Stoltz. Set-valued approachability and online learning with partial monitoring. Journal of Machine Learning Research, 15(1):324733255, 2014.
[21] N. Martinez, M. Bertran, and G. Sapiro. Minimax Pareto fairness: multi objective perspective. In Proceedings of the 37th International Conference on Machine Learning, volume PMLR 119, pages 6755-6764, 2020.
[22] J.-F. Mertens, S. Sorin, and Z. Shmuel. Repeated Games. Cambridge University Press, 2015.
[23] V. Perchet. Approachability, calibration and regret in games with partial observations. PhD thesis, Université Pierre et Marie Curie Paris VI, 2010.
[24] V. Perchet. Approachability of convex sets in games with partial monitoring. Journal of Optimization Theory and Applications, 149(3):665 677, 2011.
[25] V. Perchet. Approachability. regret and calibration: Implications and equivalences. Journal of Dynamics & Games, 1()):881-254 2014.
[26] G. Pleiss, M. Raghavan, F. Wu, J. Kleinberg, and K. Weinberger. On faireess and calibration. In Advances in Neural Information Processing Systems, volume 30, pages 5680-5689, 2017.
[27] A. Rustichini. Minimizing regret: The general case. Games and Economic Behavior, 29(1): 224-243, 1999.
[28] A. Tsybakov. Introduction Nonparametric Estimation. Springer, 2008
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Fairness results exhibited should only have positive impacts
(d) Have you read the ethics review guidelines and ensured that your paper conforms to
them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "cIfT-YRFeQ", "reviewer": "Reviewer_yF4A", "summary": "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. \n\nAlso, they have given a pretty tight characterization of the pareto frontier for group-wise calibration under demographic parity constraint.\n\nFinally, they give how to try to approach a set where some of the parameters characterizing the set is unknown.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n\n-The connection between Blackwell approachability and online learning has been made before. However, this paper also considers various fairness objectives, more specifically group-wise calibration/regret, and fairness constraints such as statistical parity and equalized average payoffs. It is novel to use the Blackwell approachability result to see the compatibility of different objectives and constraints.\n\nQuality/clarity:\n\n-Notations developed here are pretty precise (some comments on notations below though), and the paper is mostly written clearly. However, there are some parts where some of the details are not clear (e.g. comment below on estimating the unknown set in section 5). Also, it would be helpful to have the contribution of this paper more expounded upon especially in relations to the other related work. For instance, it has been known how to leverage blackwell approachability to derive online calibration, and Gupta et al shows using techniques similar to blackwell approachability how to achieve online multicalibration (groupwise calibration). These kinds of discussions seem to be missing.  \n\nSignificance:\n\n-The framework (looking at online learning problem via Blackwell Approachability) is significant in that even for any new fairness objectives/constraints in the online learning setting, one can immediately see whether it's compatible and and immediately get an algorithm, if compatible.\n\nQuestion:\n\n-In terms of the impossibility results, the original Blackwell approachability provides that the set is approachable if and only if the condition that resembles best response condition (i.e. no matter what the the other player plays, you can land in the set) is met. Using this idea, the paper, for instance, shows that the set that corresponds to group-wise no-regret is not approachable. But shouldn't the final statement be regarding online learnability — that is, doesn't one need to show that if a set is not Blackwell-approachable, then the corresponding learning problem isn't possible? It seems like one would need to invoke the equivalence result of \"Blackwell Approachability and No-Regret Learning are Equivalent\" by Abernethy et al? \n\n-In section 6, it's not clear to me how \\hat{C}_r is constructed to estimate the unknown set C. \n\nMinor questions/Comments/Suggestions:\n\n-section 2.1, objective 1: N is never defined; I'm assuming it should be N = |A| I think? \n\n-I think the dependence on |S| here will be linear. I wonder whether it's be possible to achieve logarithmic dependence on |S| using the trick in Gupta (using the exponential surrogate loss). \n\n-In Theorem 1, d^2_T hasn't been defined. I'm assuming it's min_{v \\in C} ||m_T - v|| the rate of convergence toward the set you are trying to approach to?\n\n____________________________________________________________________________________________\nThanks for answering my questions. I recommend acceptance! ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It would be helpful to have even just a few sentences regarding the limitation of this framework. For instance, as mentioned above, in the case of possibly exponentially many groups, will the sample complexity/time complexity of the algorithm still be polynomial? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "LAvd_ooFola", "reviewer": "Reviewer_eMwY", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The connection between Blackwell approachability and group notions of fairness (rather than just calibration) seems relatively novel.\n- Using this connection, the authors are able to study several group notions of fairness and to figure out whether online learning with said fairness constraints is possible, based on checking whether the approachability condition (2) holds. Of particular interest is the fact that the authors are able to provide new (to the best of my knowledge) results on the trade-off that is achievable between group-wise calibration and demographic parity. \n- The authors provide rates of convergence based on the Blackwell approachability framework.\n- They extend their results to the case where the set to approach is unknown, and show how to use this extension to provide convergence results even when some of the priors on the probability of being in each group is unknown to the learner. \n\nWeaknesses:\n- It is a bit hard from reading the paper to figure out what are the authors’ contributions versus what is new. My understanding is that the connection between Blackwell approachability and no-regret learning was previously known, but that does not seem obvious from reading the paper. Note that I am also not sure about the technical novelty of the paper, since I am not an expert on Blackwell approachability.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper should have a positive impact as it aims to provide a framework and algorithms for online learning with fairness constraints. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4"}, "extra_text": {}}, {"review_id": "L-GjSvkA91m", "reviewer": "Reviewer_gm2z", "summary": "The paper presents a general Blackwell approachability based framework for online fair learning in the presence of stochastic (sensitive and non-sensitive)\ncontexts. The framework allows to easily obtain both positive and negative fair learnability results. The authors work out their framework in the standard\ncases of no regret or calibrated online learning, paired with demographic parity constraints. They also present novel optimal tradeoffs between the \nconstraints in the case of group-calibrated learning subject to demographic parity.\n", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I believe that this paper is an important and timely contribution to the literature of online fair learning. It successfully adapts Blackwell \napproachability to handle the case of both sensitive and non-sensitive stochastic contexts coming from a fixed but unknown distribution.\nIt is important that, subject to a technical assumption, the framework developed by the authors provides \"if and only if\" learnability results, as well as\nthat it gives explicit rates in the learnable case. Further, while the main assumption (fast sequential estimation of the contextual distribution) may\nappear technical, it is easily satisfied in most important online fairness settings studied in the literature, and thus poses virtually no problem \nin terms of the generality of the \"if and only if\" results. \n\nFrom my perspective, the identification of Pareto frontiers for group calibration under \nthe parity constraint is a crucial contribution of this paper. (I would like to point out, in conjunction with this, that while considering the case \nS = {0, 1} is a good choice presentation-wise, but it does not immediately appear clear to me how Propositions 2 and 3 regarding the Pareto optimal curve \nmight look like for more general sets S.)\n\nThe proofs are involved, and might be amenable to a more compact exposition. That said, the authors do a good job with helping the reader keep track of\nthe various assumptions made at various junctures in the proofs.\n\nSome minor corrections:\n-The display below line 91, the second regret term should be r(a, b_t, x_t, s_t), not r(a'_s, b_t, x_t, s_t).\n-Line 144, I believe it should say \"perfect knowledge of the former\", not \"the latter\" (the former being the payoff functions, which are \nexposed to the learner as per line 55).\n-Line 162, I suggest adding the word \"below\" after \"Assumption 1\", as the assumption has not been defined yet.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "DAe2mQN6P9H", "reviewer": "Reviewer_oHXk", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think that the unified approach provided by the authors makes a nice contribution, as it allows a clean, elegant abstraction and understanding of multiple previously studied objectives and constraints. The suggested framework allows lifting and minimizing implementational details we have seen in previous work (for example, the authors give a condition which directly applies to the convergence rate of the empirical distribution estimate to the true underlying distribution, as opposed to, for example, a VC-bound), which abstracts these parts away, allowing to focus on the objectives and constraints in a cleaner way. \n\nEstablishing this unified approach is in my opinion the main contribution of the paper. I do not think the specific compatibility/incompatibility results that were shown were very surprising. However, I do believe the paper gives a very formal analysis of the cases and additional assumptions and their implication on the compatibility, or rather the resulting trade-offs.\n\nThe paper is well-written and presentation (translation of the objectives and constraints, adaptation of Blackwell’s theory, specific instantiations) was done in a coherent, easy to read, manner.\n\nComments/Questions to authors:\n1. The authors refer (line 26) to Bechavod et al. 2019, as one example of an online setting with a fairness constraint. However, the problem studied in that paper is of one-sided feedback (also known as \"apple tasting\"). I am aware of at least one generalization of Blackwell’s approachability theory to handle such partial monitoring (Kwon & Perchet 2017). I think this is relevant to state in the paper, as many settings where fairness is a concern tend to take this form of feedback.\n2. (Line 269) How is \\tau computed/estimated? \n3. There is no discussion regarding the limitations of the suggested framework and results. Can you elaborate on these?\n\nFixes:\n1.\t(Line 26) Bechavod et al. study a partial feedback setting, not a delayed feedback one.\n2.\t(Line 91) In the second term, a_s’ -> a.\n3.\t(Line 142) “criterion” -> “criteria”.\n\nThe submission appears to be technically sound, although I have only glanced at the details in the appendix.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no discussion regarding limitations of the suggested framework and results. Please include one.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thanks for the strong submission! The reviewers unanimously enjoyed the paper. 
Decision: Accept (Spotlight)