Statistical Parity with Exponential Weights
Authors: Stephen Pasteris
Chris Hicks
Vasilios Mavroudis
Venue: NeurIPS 2025 poster ()
Keywords: bandits
statistical parity
fairness
privacy
Primary area: theory

Abstract: Statistical parity is one of the most foundational constraints in algorithmic fairness and privacy. In this paper, we show that statistical parity can be enforced efficiently in the adversarial contextual bandit setting while retaining strong performance guarantees. Specifically, we present a meta-algorithm that transforms any efficient implementation of Hedge (or, equivalently, any discrete Bayesian inference algorithm) into an efficient contextual bandit algorithm that guarantees exact statistical parity on every trial. Compared to any comparator that satisfies the same statistical parity constraint, the algorithm achieves the same asymptotic regret bound as running the equivalent instance of Exp4 for each group. We also address the scenario where the target parity distribution is unknown and must be estimated online. Finally, using online-to-batch conversion, we extend our approach to the batch classification setting.

Statistical Parity with Exponential Weights
Stephen Pasteris The Alan Turing Institute
Chris Hicks The Alan Turing Institute London UK
Vasilios Mavroudis
The Alan Turing Institute
London UK spasteris@turing.. ac.
London UK
wtw.cccwt.........ccccc thicks@turing.ac.u.
vmavroudiss@uuring.ce uk
Abstract
Statistical parity is one of the most foundational constraints in algorithmic fairness and privacy. this paper, we show that statistical parity can be enforced efficiently in the adversarial contextual bandit setting while retaining strong performance guarantees. Specifically, we present a meta-algorithm that transforms any efficient implementation of Hedge (or, equivalently, any discrete Bayesian inference algo- rithm) into an efficient contextual bandit algorithm that guarantees exact statistical parity every trial. Compared to any comparator that satisfies the same statis- tical parity constraint, the algorithm achieves the same asymptotic regret bound running the equivalent instance of Exp4 for each group. We also address the scenario where the target parity distribution is unknown and must be estimated online. Finally, using online-to-batch conversion, extend approach to the batch classification setting.
Introduction
Statistical parity [12 is foundational concept in algorithmic fairness and privacy. It imposes a constraint on how decisions should be distributed across individuals with different values of a protected characteristic. Formally, let C and V denote the sets of protected characteristics and non-protected features (known as contexts) respectively, and let be probability distribution over C x A policy mapping C x V to distributions over with respect to if and only if, when a pair (c, v) is drawn from and then an action is sampled from the policy, the selected action a independent of the protected characteristic c. That is, for all actions b and all protected characteristics d, d' E we have:
of actions said satisfy statistical parity
Pia- = b c = d = P(a = blc= d']
We now provide two illustrative examples motivating the enforcement of statistical parity. The first concerns stop-and-search procedures, in which law enforcement officers select individuals from the public to search for prohibited items. This practice has been the subject of substantial controversy due to evidence of racial bias with individuals from certain ethnic backgrounds being many times more likely to be stopped than others. In this setting, there are two possible actions: stop and do not stop, and the protected characteristic corresponds to individual's ethnicity. Enforcing statistical parity in this context ensures that the probability of being stopped is equal across all ethnic groups, thereby eliminating disparities attributable to racial bias.
The second example arises the context of cyber defence. Consider a computer system that must be protected using a defensive strategy, often referred to as a blue agent. The choice of blue agent depends on certain private attributes of the system, one of which is particularly sensitive. Through interaction with the system, external users may be able to infer which blue agent was selected, thereby gaining information about the underlying attributes. In this case, the actions correspond to chosen blue agents, and the protected characteristics are the possible values of the sensitive attribute. Enforcing statistical parity ensures that the selected blue agent is independent of the sensitive attribute, thereby preventing users from inferring anything about it.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In this paper, we primarily study the contextual bandit problem, where learning unfolds over a sequence of trials in an online setting. On each trial, the learner selects policy, then observes an instance from the set C x V, and samples an action according to the chosen policy. After the action taken, the learner receives the loss (or; equivalently, a reward) corresponding to that action on that trial. The goal is to minimise the total cumulative loss incurred over all trials. The algorithm's 's performance is measured via regret, defined as the difference between the expected cumulative loss of the algorithm and that of fixed comparator policy (or, in some cases, a sequence of comparator policies) in hindsight. We focus mainly on the adversarial setting, in which the only assumption is that the losses lie in [0, 1]. and there are restrictions on how instances or losses are generated. Additionally, we consider cases where the context space exhibits structure, introducing inductive biases to exploit this structure.
To the best of our knowledge, no prior work has successfully developed an efficient algorithm for the contextual bandit problem that ensures statistical parity in the selected policies, even in the simplified setting of finite, unstructured context space with i.i.d. instances and losses. This paper addresses that gap. We introduce SPEW (Statistical Parity with Exponential Weights), an efficient algorithm that achieves statistical parity while matching the asymptotic regret guarantees of the classic ExP4 algorithm (2]. Like EXP4, SPEW is meta-algorithm that leverages any efficient instantiation of HEDGE
13 adapted to the structure of the context space.
As an example, we analyse the regret bound of SPEW for when the contexts are the set of vertices of a tree (noting that graphs and finite metric spaces reduce to trees). In addition to guaranteving statistical parity with respect to given parity distribution, SPEW also extends to settings where the parity distribution is unknown and must be estimated from the data seen so far. Specifically, we show how to enforce statistical parity with respect to the empirical distribution of observed instances, as well as how to maintain statistical parity approximately when the context space is hierarchically clustered (such graphs or Euclidean spaces) and the instances are drawn i.i.d. from the parity distribution.
Beyond the contextual bandit setting, SPEW can also be applied to the batch classification problem under statistical parity constraints via standard online-to-baad bathhchh conversion techniques (9] We believe this yields novel results for the batch fairness and privacy literature. Moreover. the underlying methodology of SPEW is not necessarily limited to HEDGE-bused inplementations; it should extend naturally to other exponentiated gradient algorithms, and potentially even to broader classes of gradient-based methods. For instance, our approach should be able to adapt to the CBA A algorithm (7). enabling the incorporation of confidence-ratee expert advice, which further broadens the applicability of our framework.
We now explain why a direct modification of ExP4 to incorporate statistical parity constraints is problematic. ExP4 modifies the inputs to HEDGE: an algorithm that performs mirror descent over the probability simplex of experts (i.e. deterministic policies). In principle, one could attempt to incorporate statistical parity by adding the constraint directly into the mirror descent framework. This would require performing a relative entropy projection onto the constrained set. To compute such a projection, we construct the Lagrangian and differentiate it to obtain necessary conditions for optimality. While expressing the primal variables in terms of the Lagrange multipliers is straightfor- ward, solving for the multipliers themselves appears analytically intractable. Although the projection problem is convex and thus admits numerical solutions, known approximation methods are, as far as we are aware, computationally infeasible in this context due to the exponential size of the expert space. Even in the special case where there is no structure to the context set effectively removing the inductive bias and reducing the problem to polynomial dimension existing approximation methods remain considerably less efficient than our approach. In contrast, SPEW avoids these issues entirely by not modifying HEDGE itself but rather its inputs and outputs.
Much research has focused on designing efficient algorithms for online convex optimization that, unlike SPEW, allow constraint violations but ensure bounded cumulative constraint violation. No- tably, the work [ extends to the bandit setting and achieves a cumulative constraint violation of (TT3/4) (suppressing factors independent of T), albeit the cost of an additional multiplicative term of (241/11114) to the regret. The work [34] attains a tighter constraint violation bound of O(T1/2) (when the constraint set lacks an interior point, as for statistical parity) but their approach is incompatible with the bandit setting and incurs polynomial dependence on the problem dimension (which is exponential in our work) in both the regret and constraint violation bounds.
We provide a literature review in Appendix A
2

---

2
Notation
In this section we introduce the notation used in this paper. We define R be the of non non-negative real numbers. We define N to be the set of natural numbers excluding 0. Given E N we define:
[2] == {z' N | 2}
Given some finite set B we define As to be set of probability distributions over B. That is, As
the set of all p B + [0, 1] with:
Σ {()))= =1
ZEB
We call the set Ag a simplex. Given sets B and B' and a function with domain x B' we define, for all B, the function f(z, o) be the function that maps each x' E B' to f(2, z'). Given predicate we define [P] = 1 if P is true and [P] == 0 otherwise.
Problem Description
In this paper we consider the following problem, known as the contextual bandit problem. We have a set of contexts V which typically has some structure associated with it. For instance, V could be the set of vertices of graph or points in Euclidean space. When V is finite we define N == [V]. We also have finite sets C and A of protected characteristics and actions respectively. Let M == C and
K = A Define the set of policies as:
Q = { [0,
ECV, ((,
A-priori, our adversary chooses sequence:
((,, E,) [T]}
where for all [7] we have & e V and E [0, This sequence is not revealed to us. The problem proceeds in T trials where on trial the following happens.
1. We implicitly select a policy ni Q.
2. The pair (ct, vx) is revealed to us.
3. We draw an action a₂ from nī (C,, Vt. o).
4. The loss (at) is revealed to us.
Our aim is to minimise the cumulative loss:
Σ (a())
TE[T]
In this paper we consider the enforcement of statistical parity in our policy selections. Formally, policy π E Q has statistical parity with respect to probability distribution p E Δexv if and only if when a pair (c, v) is drawn from p and then an action is drawn from π (c, v, o) we have that:
Pla 6 = d = Pla = d']
for all b E A and d' E C. In other words, the selected action is independent of the protected characteristic e. Note that when P/c = d| 0 then we allow P/a = bl c = d) to be arbitrary in the above equation.
Given we have knowledge of a distribution e Acxv, our meta-algorithm SPEW will play in such a way that each policy xł has statistical parity with respect to p. We note that the contexts v selected by our adversary need not be drawn from p. Specifically, given any efficient implementation of an instance of the classic HEDGE algorithm, SPEW will convert it into efficient algorithm that will guarantee statistical parity whilst also guaranteeing that the bound on the difference (a.k.a. the regret) between its cumulative loss and that which would have been incurred by any constant policy with statistical parity is that of the equivalent instance of ExP4.
As we shall see, SPEW can also work when we have no knowledge of p, and instead must estimate it from the data seen so far. SPEW can also be applied to cases which we want to compare against dynamic policy sequence rather than constant policy.

---

The Algorithm
4.1 Hedge
Here we describe how an instance of HEDGE works. We have a finite set X' of virtual contexts which defined by the specific instance of HEDGE. On each trial we have non-empty set 9j X of the virtual contexts that are relevant for that trial, as well as function X V - Si that will map, on trial f. the given context U/ to a virtual context. These mathematical objects, which are defined by the specific instance of HEDGE, may be dependent on characteristic/contee pairs seen before trial t. In many cases we will have X V. g X and (v) for all E [T] and v E V. We also have learning rate i) > 0.
We define the of experts
H. := A
so that each expert associates an action with each virtual context. The inductive bias of the specific instance of HEDGE given by a probability distribution & E Ax over the experts. HEDGE implicitly maintains distribution v'' E Au initialised equal to d. HEDGE has the following two subroutines:
When run on trial the subroutine QUERY returns a function :: : x - [0, 1] defined by:
plz, a)
E[e(z)= (e) V(z,a) 9j A
eEW
When run on trial f the subroutine UPDATE takes, as input, a pair (x, E) E g x R and then, for all H. implicitly sets:
('(e) + d'(())xp(--i((((a))
and finally implicitly normalises Vr
Note that if HEDGE was explicitly then these subroutines would take exponential time. However, given a compatible inductive bias 0, algorithms for Bayesian inference (such as BELIEFPROPAGA- TION (29)) compute these subroutines efficiently. Such algorithms typically require only O(K) time for the UPDATE subroutine as the main computation is performed during QUERY.
SPEW maintains an instance of HEDGE (a.k.a. the base algorithm) for each protected characteristic. For simplicity, we assume each of these instances of HEDGE shares the same set and inductive bias I although this is not actually necessary. For each E C and i. E [T] define (e and (c, o) to be the mathematical objects 9 and X for the instance of HEDGE associated with protected characteristic In addition, let QUERY( [e) and UPDATE[[] be the subroutines QUERY and UPDATE for the instance of HEDGE associated with protected characteristic c.
4.2 Input and output
We now describe the input to SPEW, on each trial t E [T], and the properties of the action that it selects. To this we first define the virtual policy space:
= { [0, 10,1 ( ECx (((
and the target space:
D D: {u E [0, 1xxx E, u(c,o) E Ax}
Finally, for any target μ D, we define F(J) to be the set of all virtual policies P in which for all c, d' E and E A we have:
Σ
[((, (n(d,a)ne,,,,
NEN
xEX
On each trial E [T] the following happens:
1. A target 14 E 'D is created based on the characteristic/contex pairs seen far and the problem hand. This target has the property that for all (c, x)) C with x & Gx(c) we have pe(c, z) 0.

---

2. SPEW implicitly determines a virtual policy E F(j)). This virtual policy equates to the policy मं Q by mł (c, 0, Xe(c, v), e) for all (c, v) e V.
3. (Ct, v1) is revealed.
4. We define 2, := Xi(e,, v2).
5. SPEW samples the action az from the distribution Te(cs, Te, o). Note that this means that SPEW samples a from कं (ct, vt, o) required.
6. (at) is revealed.
We now describe how this process enforces statistical parity. Specifically, suppose we have distribution p Aexv. We assume, for simplicity, that for each there exists some X with p(c, x)) # O although it is trivial to modify the algorithm so that it does not require such an assumption. On any trial f, we can define pe by:
pelc,x) Evevlx((c.)) =xp(cc ((xx)
((,,)(
Note that for all (c, E C x X' with then have that the policy лद has statistical parity with respect p.
a & Ge(c) we have pe x)) = as required. Since ne E F(44
4.3 Pseudocode
We now give the pseudocode of SPEW. On any trial E [7) SPEW does the following.
Receive 14, It and Ct for E C do 0,) &- QUERY[C]
for a E A do wr(c,a) - (Usz),c
end for end for for (c, EC Ao
d,(c,a) + maxcec wilc, a)(c,a)
end for
Br + --Ees max.ea & (c,
for a E Aoo
va(aa) + (Eole,, 8, a))/(1 (3)
end for
he + 1-1- va(
for E A do
x/(a) + (aa + h./K
end for
Draw a from probability distribution of.
Receive (a(a) for a E A do (a)a) argmax w/ (c,
<a(a) + argmin (g(c, end for
for E C do
for E Ge(c) do for a E A do
a)) < [B 1][ x, (a. = +|c- [()))(())) [c= (((a)llu(e.z)
end for UPDATE(C[(2, te(c,
end for end for
5

---

4.4 Description
We now briefly describe the internal workings of SPEW on trial t. For a full description and analysis please see Appendix [ On high level, SPEW maintains virtual policy (which does not necessarily satisfy statistical parity) inside the instances of HEDGE. This virtual policy is computed by calling the QUERY subroutine of each instance of HEDGR. On trial 1, this virtual policy is mapped, in certain way, to the virtual policy Tt, which does satisfy statistical parity. & is then updated to f++1 by performing exponentiated gradient descent (on the expert probabilities) using unbiased estimate of the gradient a convex surrogate of the loss of I. in terms of &.. This exponentiated gradient descent update is performed by updating the instances of HEDGE (via the UPDATE subroutine) multiple times.
We now go into details. Given some E C, recall (from Section 4.1) that the instance of the HEDgE for protected characteristic e implicitly maintains a distribution in Ax. Let (, o) be the value of this distribution the start of trial I, so that 01 (c, d.
Define the virtual policy & E P by:
Eo(c, x, = Ele(x) = al,e,(c,e)
cEH
for all ac. C X A. We call the raw policy. For each C. SPEW needs only know (c,c, 2, o) for E Gi(c), which can compute by a call to QUERY[C].
Note that the raw policy does not necessarily belong to F(m)). The raw policy is converted into the virtual policy n, by the following procedure. Given (c, E C define:
ar(c, = Σ m((,,))
ZEG((c)
and:
d,(c,a) == max CEEl
( wr
wr(c,
Furthermore define:
Bi = Σ max de
CEC
aEA
For all (c, a) E C X' A define:
ve(c,2,0) Ee(c, + a)
1 3
Finally, define the virtual policy Ti by:
Te(c,2,a) = 2,
1 K
1 Σ (c,,,,)))
a'EA
for all (c, a) E x X' x A. In Appendix B we show that n. E F(ur) as required.
SPEW then samples the action a, from the distribution Te,
Now that we have shown how to choose the action ar, we will show how to update the HEDGE instances upon receipt of (az). We first define:
S Ex=xA
and given (g) a) S x C x A define:
ar(0,c,a) := Σ o)
xEG((O)
We define the function ye S R by:
(Φ) = [3, 1] Σ ((a)ole, Ir, a) +
max mr (,,,,,a)) aEC
min 5r (0, aEC

---

noting that SPEW never actually has knowledge of this function, as it is dependent on the entirety of 4. In Appendix [
we show that yt is convex and that:
(Er)
Σ
(e
Σ
Vi F(pe)
aEA
aEA
These properties mean that we can use Yt as convex surrogate for the expected loss in terms of the raw policy.
Since SPEW does know the entirety of & it does not know subgradient of y/ at & which is required for exponentiated gradient descent. Hence, we borrow the idea from ExP4, of constructing an unbiased estimate of such a subgradient. Specifically, we define the function X ESI0 by:
ee(as)
de(e, x, a) 31 s []](c x, a) = (ce, Fe, at] (e, Iz, T2,
[c argmax (c', ()))
[ce == argmin wrlc,, a))
where ties in the argmax and argmin are broken arbitrarily. In Appendix we prove that the expected value of ) over the draw of is equal to a subgradient of at &. Noting that, for each (c, e) E C H. & is dependent on (,, e). we then have that an unbiased estimate of the subgradient of (Er) with respect to (c,c, e) is equal to:
e)(c,))== = Σ (ee,2,,
ZEN
We now update the function 0e to d,41 via exponentiated gradient descent. Specifically, for all (c, e) E C x H. we have:
(x(c,e)exp(-ivx(cee)
S (c,e)) EVEn Oz(c, ed) iiu (c,ee)
This updated is implemented by simply running the function
UPDATE|c[(2, (c,,,,)))
for each E C and & E Ge(c).
4.5 Performance
In the following theorem we give the general performance guarantee of SPEW.
Theorem 4.1. Let: 7) == ÍTT For all e [T]. SPEW produces Te F(u)). In addition, for any virtual policy:
# E n F(u)
KE[T]
for any 3* :C H + [0, 1] with:
#(c,I,a) x, a) = Σ Il((z)
ECxxx
cE#
have:
#(ce, Fz, a)l((a)))))))) +0 ((n+ 1b 17 VKT)
E
Σ (((at)
Σ TE(T] aEA
[E(T]
where:
Φ: M> (c,e) In ((((ee)
O(e)
CEC
On each trial E [T] the time complexity of SPEW that of M calls to QUERY and Eoec (c)
calls UPDATE, The space complexity is that of maintaining M instances of HEDGE.
7

---

See Appendix B for the proof of this theorem. We note that for all applications the targets μ4, will be chosen such that Nerr F(1e) non-empty. We also note that for all virtual policies there exists 0" C x H [0, with:
(c) -[e())=aa])) (c,e) E(c.z,,)(CxXAA
eEN
EMer is required by the theorem. Relative any virtual policy म E Keery F(ue), the regret bound given by the theorem asymptotically identical that of running EXP4 independently for each protected characteristic.
Examples
Before we discuss the algorithm and the main result, we will give some example applications. The specific instances of SPEW that used obtain the results of this section, well their proofs, are given in Appendix D In the first example we assume that the distribution with which we must have statistical parity with respect is given a-priori, whilst in the final two examples is instead estimated from the data seen so far. Note that, in the theorems, the quantity:
Σ # Me (a)
is the expected loss incurred by playing policy सं E Q on trial t E [2]. Note also that = fNv KT
5.1 Trees with known distribution
In this problem we assume must maintain statistical parity with respect a distribution Acxy that is known to us a-priori. We also assume that we have knowledge of a tree with vertex set V. Let be the edge set of this tree. Several types of problem reduce this setting, including learning on graphs [14). learning on finite metric spaces (26) and learning on finite sets endowed with hierarchical clustering. For graphs, the tree created by sampling spanning tree uniformly at random. For metric spaces the tree is created by growing the tree context by context, linking each new context to it's nearest neighbour in the tree far. For heirarchical clusterings the context set altered to be the set of all clusters, which naturally has a tree structure.
Given policy ãे E Q define its complexity as:
( = Σ Σ
a(c,ua)) #(c, v, a.a)l
(u,))E (c.4)
Note that (#r is bounded above by twice the summation, over all C, of the number of edges (u, v) E & in which ((c, u, o) & #(c, v, o) (i.e. the cutsize).
We have the following performance guarantee.
Theorem 5.1. Suppose are given distribution p Aexv a-priori and run the appropriate instance of SPEW. Then all our generated policies मे have statistical parity with respect to and for any policy Q with statistical parity with respect p we have:
#(c,, a))((a)+++ + ((++
M M ((T) V(T INN)
E
(ar)
VKT
17
[E|T]
BE(T] aEAA
The per-trial time and space complexity O(MNK).
This theorem leads directly to theorems about learning on graphs and finite metric spaces via results from [10 (it is commonly used fact that the expected cutsize of uniformly sampled spanning tree of a labelled graph is equal to the effective resistance weighted cutsize of the graph) and [2] (see Theorem 3.6 therein) respectively.

---

5.2 Empirical statistical parity
We now turn to examples in which we are not given a distribution p a-priori. In this first example we utilise the methodology of [17] to enforce statistical parity with respect to the empirical distribution of the data seen so far. Note that for this to be meaningful the set V should not be too large (we will deal with very large and essentially infinite context sets in the next example). The set V could, for example, be created via a clustering of a larger context set. We do not exploit any structure to the contexts in this example.
For any trial > let Pt be the empirical distribution of the data seen so far. Formally, for all (c, v) E C x V, we have:
pr(c, u) u= 1-1 Σ
co=
sE(t-1]
Given any sequence of policies गे E Q", we define its complexity:
(+) = E E
(c,1(c, v, u,(c,
LEIT (CXX
With these definitions hand have the following result:
Theorem 5.2. There exists an instance of SPEW such that for all t > 1 we have that गं has statistical parity with respect to Pt and, for any sequence of policies π º in which, for all 1, Rg has statistical parity with respect to Pe. we have that:
V2, v1)10)) ((
MN + V(
E
Σ ((aa)) [E
VKT
BE[T] aEAA
The per-trial time and space complexity is O(MNK).
5.3 Approximate statistical parity for hierarchical clusterings with an unknown distribution
We now turn to maintaining approximate statistical parity when the context space is potentially massive and has a known hicrarchical clustering associated with it. Natural hierarchical clusterings can be derived for several types of structure, including graphs 15), Euclidean space 30) and finite metric spaces (25).
This example, which utilises the methodology of (26). does not assume a-priori knowledge of distribution p, but unlike the previous examples we assume here that there exists distribution p² E Acxv in which the pairs (ct, vz) are each drawn i.i.d. from p², This distribution is not known to us a-priori. We are given some e, 5 >> We say that a policy æ Q has e-approximate statistical parity with respect to p² if and only if, when pair (c, v) is drawn from p and then action is drawn from [(c, U, o). we have that:
IP(a- = b c = d'] - - S Pla blc d S Pla = b d') +
for all e and d. d' C. We are required to play such a way that, with probability at least 1 all our chosen policies ग. have e-approximate statistical parity with respect to '²
We assume that V is finite but potentially enormous. For instance, V could be the quantisation of a hypercube of Fuclidean space defined by all the points that the computer can handle (given its precision). We assume there is a known hierarchical clustering over V. That is, we have full binary tree in which each vertex is a subset of V. The root is the whole set V, the leaves are the singleton sets, and the children of each internal vertex/set partition that set. We note that there is no need to explicitly maintain the tree (which could be enormous). We define H to be the height of the hierarchical clustering, which typically a relatively small quantity (e.g. logarithmic in T).
Given a policy स E Q we define its complexity ( as follows. We first define a permitted clustering to be any partition of comprising of sets in the hierarchical clustering. For any protected characteristic e E C. we define gb(c, it) to be the minimum cardinality of any permitted clustering in which for each set l/ in that permitted clustering and for all u, l have iicc, u, o) = #(c, v. o).
We then define:
V (
Σ (C. m))
9

---

Finally, we say that probability distribution p Acxv is e-close to p if and only if every policy with statistical parity with respect to p has e-approximate statistical parity with respect p².
With these definitions hand we have the following result:
Theorem 5.3. There exists an instance of SPEW in which, with probability at least 8, there exists some p Aexv, v. which is e-close to p", such that all the generated policies nn have statistical parity with respect to p and, for any policy it with statistical parity with respect to we have:
T(a, ve, a)l(()++ ( ((() + (1+ HV(
E
Σ ((te) CE|T]
S <Σ>
VKT
BE[T]GEA
If the determination of whether context belongs to a given set of the hierarchical clustering takes ((1) time, and the hierarchical clustering needs be explicitly maintained to determine this, then the per-trial time and space complexity of SPEW is OKTT).
Note that unlike the previous examples, the time complexity is not dependent on the cardinality the context set. The algorithm can be easily modified to obtain exact statistical parity (without the pairs (ce, vx) necessarily being i.i.d)) when a distribution is known, as long as we can efficiently compute the probability masses of any set in the hierarchical clustering (for any given protected characteristic).
Batch Classification
Finally, describe how SPEW enforce statistical parity in the batch classification problem. Here there exists an unknown probability distribution ý E AexvX and we are given a sequence:
((c,, vt. bt [T])
of T i.i.d. samples from p. We are given a distribution E Δexv (which could be the empirical distribution of some unlabeled data). The aim is to construct policy Q which has statistical parity with respect to and has high accuracy:
Σ (c..
To solve this problem we first define, for all t E [T]. the loss function & by (a(a) := a + b.]
for all a and then, with the appropriate instance of HEDGE, run SPEW the sequence ((e,, Ve, 44) E (T]) to produce a sequence of policies (मī | E [7]) such that गद has statistical parity with respect p for all / [T]. Finally, we define the output policy:
Σ T LET2
We note that via HEDGE based doubling trick we can automatically tune the learning rate. Standard results on online-to-batch conversion [9] convert the regret bound given in Theorem 4. a bound on the expected accuracy. Specifically, the difference between the expected accuracy of the algorithm and that of any given policy स with statistical parity is equal to the bound on the regret divided by T. For trees this difference in expected accuracy is:
δ (V(M + I(N)
where V defined as in Section D.I
Acknowledgments
Research funded by the Defence Science and Technology Laboratory (Dstl) which an executive agency of the UK Ministry of Defence providing world class expertise and delivering cutting-edge science and technology for the benefit of the nation and allies. The research supports the Autonomous Resilient Cyber Defence (ARCD) project within the Dstl Cyber Defence Enhancement programme.
10

---

References
[1] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna M. Wallach. reductions approach to fair classification. ArXiv,
2018.
[2] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM J. Comput., 32:48-77, 2002.
[3] Yahav Bechavod, Christopher Jung, and Zhiwei Steven Wu. Metric-free individual fairness in online learning. ArXiv, abs/2002.05474, 2020.
[4] Yahav Bechavod. Katrina Ligett, Aaron Roth. Bo Waggoner, and Zhiwei Steven Wu. Equal opportunity online classification with partial feedback. ArXiv, 0bss/1902.0224,, 2019.
[5] Avrim Blum, Suriya Gunasekar, Thodoris Lykouris, and Nathan Srebro. On preserving non- discrimination when combining expert advice. In Neural Information Processing Systems, 2018.
[6] Toon Calders and Sicco Verwer. Three naive bayes approaches for discrimination-free classifi- cation. Data Mining and Knowledge Discovery, 21:277-292, 2010.
[7] Xuanyu Cao and K. Ray Liu. Online convex optimization with time-varying constraints and bandit feedback. IEEE Transactions Automatic Control, 64:2665-2000 26800, 2019.
[8] Matteo Castiglioni, A. Celli, Alberto Marchesi, Giulia Romano, and Nicola Gatti. A unifying framework for online optimization with long-term constraints. ArXiv, htbb///29.00454,, 2022.
[9] Nicolò Cesa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50:2050-2057, 2001.
[10) Nicolò Cesa-Bianchi, Claudio Gentile, Fabio Vitale, and Giovanni Zappella. Random spanning trees and the prediction of weighted graphs. International Conference on Machine Learning, 2010.
[11] Christophe Denis, Romuald Élie, Mohamed Hebiri, and Fran, Hu. Fairness guarantees in multi-class classification with demographic parity. J. Mach. Learn. Res., 15:130:1-130:4:: 2024.
[12] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel. Fairesss through awareness. ArXiv, abs/1 104.3913, 2011.
[13] Yoav Freund and Robert Schapire. theisicn- generalization of on-line learning and an application to boosting. In European Conference on Computational Learning Theory, 1997.
[14] Mark Herbster, Stephen Pasteris, Fabio Vitale, and Massimiliano Pontil. A gang of adversarial bandits. In Neural Information Processing Systems, 2021.
[15] Mark Herbster and James Robinson. Online prediction of switching graph labelings with cluster specialists. In Neural Information Processing Systems, 2018
[16] Mark Herbster and Manfred K. Warmuth. Tracking the best expert. Machine Learning, 32:151- 178, 1995.
[17] Mark Herbster and Manfred K. Warmuth. Tracking the best linear predictor. J. Mach. Learn. Res., 1:281-309, 2001.
[18] Wen Huang, Kevin Labille, Xintao Wu, Dongwon Lee, and Neil T. Hefferman. Achieving user-side fairness in contextual bandits. Human-Cene Centric Intelligent Systems, 2:81 - 94, 2020.
[19] Wen Huang, Kevin Labille, Xintao Wu, Dongwon Lee, and Neil T. Hefferman. Fairness-ae aware bandit-based recommendation. 2021 IEEE International Conference on Big Data (Big Data),
pages 1273-1278, 2021.
[20] Rodolphe Jenatton, Jim C. Huang, and C. Archambeau. Adaptive algorithms for online convex optimization with long-term constraints. ArXiv, 221.112,...772.22115.
11

---

[21] Matthew Joseph, Michael Kearns, Jamie Morgenstern, and Aaron Roth. Fairness in learning: Classic and contextual bandits. In Neural Information Processing Systems, 2016.
[22] Y. Liu, Goran Radanovic, Christos Dimitrakakis, Debmalya Mandal, and David C. Parkes. Calibrated fairness in bandits. ArXiv, abs/1 1000000..7,..... 2017.
[23] Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: online convex optimization with long term constraints. J. Mach. Learn. Res., 13:2503-2528, 2011.
[24] Michael J. Neely and Hao Yu. Online convex optimization with time-varying constraints. arXiv: Optimization and Control, 2017.
[25] Stephen Pasteris, Chris Hicks, and Vasilios Mavroudis. A hierarchical nearest neighbour approach to contextual bandits. ArXiv, abs/2312.00932. 2023.
[26] Stephen Pasteris, Chris Hicks, and Vasilios Mavroudis. Nearest neighbour with bandit feedback. NeurlPS, 2023.
[27] Stephen Pasteris, Alberto Rumi, Maximilian Thiessen, Shota Saito, Atsushi Miyauchi, Fabio Vitale, and Mark Herbster. Bandits with abstention under expert advice. ArXiv, abs/2402.1458. 2024.
[28] Vishakha Patil, Ganesh Ghalme, Vineet Jagadeesan Nair, and Y. Narahari. Achieving fairness in the stochastic multi-armed bandit problem. J. Mach. Learn. Res., 12:17::1117:31,
[29] Judea Pearl. Reverend bayes on inference engines: A distributed hierarchical approach. Proba- bilistic and Causal Inference, 1982.
[30] Vianney Perchet and Philippe Rigollet. The multi-armed bandit problem with covariates. ArXiv, 10.6044 2011.
[31] Subham Pokhriyal, Shweta Jain, Ganesh Ghalme, Swapnil Dhamal, and Sujit Gujar. Simultane- ously achieving group exposure fairness and within-group meritocracy stochastic bandits. ArXiv, abs/2402.055755, 2024.
[32] Candice Schumann, Zhi Lang, Nicholas Mattei, and John P. Dickerson. Group fairness in bandits with biased feedback. In Adaptive Agents and Multi-Agent Systems, 2019.
[33] Lequn Wang, Yiwei Bai, Wen Sun, and Thorsten Joachims. Fairness of exposure in stochastic bandits. In International Conference on Machine Learning, 2021.
[34] Hao Yu and Michael J. Necly. A low complexity algorithm with o(vT) regret and o(I) constraint violations for online convex optimization with long term constraints. J. Mach. Learn. Res., 21:1:1-1:24, 2020.
A Literature Review
Algorithmic fairness has been a topic of much study. Notable pioneering works include (6], which introduced statistical parity, and [12] which introduced the notion of individual fairness. Similar to our batch result, D considered the problem of constructing a randomised binary classifier, with statistical parity, which is convex combination of deterministic classifiers from some given hypothesis space. They solve the problem via a sequence of calls to a cost-sensitive classification oracle (for the particular hypothesis space) and give generalisation error in terms of the Rademacher complexity of the hypthesis space. The work [T]] considered finding the Bayes optimal classifier satisfying statistical parity approximately (with an arbitrary number of classes).
We now give a review of some of the research in the wide topic of achieving various forms of fairness in i.i.d. stochastic bandits. [32] considered the problem of eliminating societal bias when actions are partitioned into groups which are each subjected to societal bias. [19] considered, in the linear bandit setting, the problem of equalizing cumulative mean rewards across two protected groups of contexts. 31 considered the problem of, when actions are partitioned into groups, simulatenously achieving certain exposure for each group and ensuring that, within each group, each action is
12

---

chosen with probability proportional to its merit. 21 considered the problem of ensuring that a better action (one with lower mean loss) never has lower probability of being chosen than a worse action (one with higher mean loss), 33 considered the problem of choosing each action with a probability proportional to its merit, 22 considered the problem of treating similar actions similarly, and [28] considered the constraint of selecting each action at least pre-specified number of times. A form of fairness with respect to instances was studied in [18] which considered the constraint of equalising the cumulative mean loss of all protected groups (all instances that have some given protected characteristic) in stochastic linear bandits. We note that, whilst this constraint will be desired in some situations, it is very different from statistical parity. Possibly the closest such work to ours is 4 which considered the i.i.d. stochastic online binary classification problem (classifying contexts positive or negative) under the constraint that false negatives are equalised over two protected groups, under the assumption of the existence of an efficient oracle for empirical risk minimisation over a finite set of hypotheses. They specifically considered partial feedback setting where the true class is only revealed when the positive class is chosen. However, the fairness constraints are only approximated and the algorithm is relatively inefficient: taking a per-trial time that is polynomial in the number of trials (the exponent is not given in the paper).
Other works on fairness in online learning include the work [5] which deals with combining expert advice with experts that are each fair with respect to some metric, so that the resulting policy is fair with respect to that metric. This is very different problem to that studied in this paper: which utilises experts that do not satisfy statistical parity. Another notable work is [3] which considers the problem of enforcing individual fairness in online settings where metric is given but instead there exists an auditor which identifies pairs of users treated unfairly.
Finally, as described in the introduction (where we discussed the works g and 34 there has been much work on online learning subject to convex constraints (which are approximately satisfied the long run). This line of research was pioneered by [ and was extended to time-varying constraints in [24]. The work 7 considered both time-varying constraints and bandit feedback. The work 20 achieved bounds that can tradeoff between regret and constraint violation. The algorithm in 23 works by gradient descent/ascent on the Lagrangian, whilst our algorithm SPEW works in a fundamentally different way- - by mapping maintained policy (without statistical parity) to a policy with statistical parity and performing exponentiated gradient descent (on the maintained policy) with surrogate for the resulting loss in terms of the original policy.
B Algorithm and Analysis
Here we describe and analyse the mechanics of SPEW. All lemmas stated in this section are proved in Section C Since this section works entirely in the virtual context space we will refer to, in this section, virtual contexts and policies as contexts and policies respectively. We define I := C x X.
Let 17, म. & and o* be as in Theorem 4.1
Without loss of generality we can assume that:
S VT/K
otherwise our regret bound would be vacuous. Recall that SPEW takes as input an algorithm (a.k.a. the base algorithm) for implementing Hedge with inductive bias D. For the base algorithm we will choose the learning rate:
7 V KT
We will maintain M instances of this algorithm, one for each protected characteristic e E C. For each c E C let QUERY[C] and UPDATE[[] be the QUERY and UPDATE subroutines for the instance of the base algorithm associated with the protected characteristic c. Given some e E C, recall (from Section 4.I) that the instance of the base algorithm for protected characteristic implicitly maintains distribution in AH- Let 0e(c, o) be the value of this distribution at the start of trial f, so that 01 (c. a) D.
We now describe and analyse how SPEW behaves on trial f and, in doing so, will bound the instanta- neous regret:
Σ (To(C,) a) a)){(a
Tt.
aEA
13

---

B.1 Fundamental Definitions
We now make some fundamental definitions. We first define:
RxXXA
Given c,a) E x C A define:
wr(o, c, = E
m(c E (m(c,))(c
aESi(O)
and define:
(e( = max (r (o) c.
C'EC
Given @ E S define:
B((0)
max ( Σ
aeC
aEA
Finally, we define Z, be the set of all Φ E in which for all c, e' E and A we have:
wr(0, c, a) = (d a)
We note that F(w,) Pn Z..
B.2 Computing the Policy
Define the policy & E P by:
Ce x, a) = Ele(x) = (c,e)
CEH
for all (c, xxXXxx A. We call & the raw policy. For each C. SPEW needs only know (e n, o) for æ E Ge(c), which it can compute by call to QUERY[C]. We state the above equation as the following lemma:
Lemma B.1. For all (c) E C x X' x A we have:
E,c,,2,) a) [[((s)=old<(c44
EEH
We now describe the conversion of our raw policy & into our fair policy т.. We call this conversion process policy processing. First define, for all A and E C, the quantities:
5,(c, a) = 8,(E,,c,
3: : 3.(5))
We define function th E S such that for any (c, (,, C X x A we have:
ve(c, Ec(c, x, a) + a)
1 B,
The function vi, has the following properties:
Lemma B.2, We have that th2 Z, In addition we have, for all (c,x) I, that:
Σ aEAA
$1
and that the(c, x, 2 for all a E A.
The above lemma shows that the function th satisfies most of constraints. However, it is not necessarily in P as the functions (y x, o) may not lie on the simplex A In order to convert it into T. simply add, to each of the functions elrc,, o), some the uniform distribution. Specifically, for all (c, x, a) C x x A we define:
<,,, d,(c,z
1 K
1 -
11-
Σ (((....d))) a'EA
The following lemma, which follows from Lemma
B.2 confirms that n, does indeed lie in F(u)).
14

---

Lemma B.3. We have:
Ty F(p)
We now give two additional lemmas that are crucial to our analysis. The first lemma follows from Lemma B.2
Lemma B.4. For all (c, a, E x X x A we have:
(1 2, Be
Te x, (c,
The next lemma follows from lemmas B. and and B.4 Lemma B.5. For all (c, x) I we have:
Σ max(0,
E,(c,x,a)) s B
We have now derived all the properties of m. needed to proceed with the algorithm and analysis.
B.3 The Objective Function and its Pseudo-Gradient
Now that we have shown how to compute we turn to the update of the base algorithm instances the end of the trial. order to do this we need convex objective function y: : R which we note will never actually be known by Learner. Our objective function is defined such that for all we have:
(o) = [3 s 11 Σ (ela)o(e, a) + (c())
aEA
The reason we have chosen such an objective function due to the following two lemmas, where Lemma follows from Lemma B.5 We note that the appearance of [[3 1] in the definition of
y/ is to ensure another crucial lemma, which we shall present later.
Lemma B.6. We have:
Ve(()) 2 Σ
Te(e,, tt, xt, a)la(a)
aEA
Lemma B.7. We have:
Ve((T) (T)
Σ aEA
We will show that yt is indeed convex by showing that it has a sub-gradient at every point S. In order to give such a sub-gradient we first define, for all (Ø, a) E S A, the quantities:
te a) argmax (r,
Ri(6, a) argmin Wz(0, a)
where ties are broken arbitrarily. We then define 9e x C A such that for all (,,c,2, a) E S x C x X' x A we have:
(e c, a) == [8 1][(c, x>) (c. Ic= mlo ()) x) - Ic R2 (c.
The next lemma shows that for all á E S we have that g:( o, 0, is sub-gradient of yr at d.
Lemma B.8. For any é, S' E S we have:
ve(0) (o0) < ΣΣΣ
gol0, c, 2. a) (c
dEC xEC
Due to the fact that don't 't know the entire function l, can't compute the sub-gradient Ge(E, o, o) so instead, will borrow the technique, from ExP4, of using [a = (o.))a////((ee xt, az) unbiased estimator of (a). This gives the following function X that call the pseudo- gradient. de E S is defined such that for all (c, x, a) E x
X x A we have:
Ea(ax)
Xe(c, ((c, :1 < (c,
(ce, at)
ne. Te as) + [c (E, (c, - Ie = Ry(Ee, a)leeelc))r)
The following lemma states that X, is an unbiased estimator of the sub-gradien ge,E,, o,
15

---

Lemma B.9. For all (c, E C x X x A we have:
[[Aa(G x, a) & = ge C, C, 2,
Note that for the full-information online and batch classification versions of SPEW we can use true sub- -rab-gradient instead of X in order to give deterministic algorithm.
Lemmas B.6 B.7 B.8 and B.9 combine to give the following lemma.
Lemma B.10. We have:
E
ΣΣ CEE ZEX aEA
Σ
(E(c,
xf,, 2fG,,, & 2 rt
Now define V4 :C H + R such that for all (c, E EC x H. we have:
e((c,))== = [x(x,e
ZEN
Lemmas B.1 and combine to give us the following lemma.
Lemma B.11. We have:
E Σ
(Or(c,e)- - ((ce)))) D1
2 nr
LEEC EE
The reason that the term [B: S 1] appears in the definition of our objective function y/2 to ensure the following crucial property of the pseudo-gradient, which follows from Lemma B.4
Lemma B.12. We have:
E
ΣΣ ).(,,e))u(ce) 01
S8K
LEEC cE#
Finally have the following lemma:
Lemma B.13. For all (c,e) E x H we have:
(c(ce) 2-K
We have now derived all the properties in needed to progress to the next stage of the algorithm and analysis.
B.4 Hedge Update
To update we run, for each E C and x E Ge(c), the function:
(PDATE|c[[2, 2r(c, o))
We have the following lemma.
Lemma B.14. For all (c,e) H. we have:
(xCCce))pp(- e))
D4i(cG)) Even dz(c,
exp(-iuu (xxee(e))) e'))
We define the relative entropy B Au x AH + lK such that for all 3, E Ax we have:
3(e)
B(3 = Σ 3(e) In
3((e)
EEW
Lemma B.13 and Lemma B.14 give the following lemma.
16

---

Lemma B.15. For all E C we have:
((0",0((e,,)) B(O", (et1(c, 2
Σ
(((c,e)u((eee'
nCH
cCH
This lemma combines with lemmas B.11 and
B.12 give the following lemma.
Lemma B.16. We have:
E
Σ 1B(00,0 0.(c,))) - ,("", Dutilc o)))
02 2 fir -8ij2
LEC
This completes the description and analysis of trial L.
B.5
Regret Bound
To get the overall regret bound we take expectations on Lemma B.16 3..6and and sum over all & [2], which gives the following lemma.
Lemma B.17. We have:
Σ 1E|21
E(ra] (8n (8n- 4/n) (8n K/T
where:
① = ΣΣ 0³ (c, (c,
((c)
cEC EEH
C Proofs of Lemmas
We now prove, in order, all of the lemmas given in this Appendix B
C.1 Lemma B.1
This is immediately clear from the construction of & and the description of HEDGE given in Section
C.2 Lemma B.2
We first show that 3/e Ze. To show this consider some c and A. We have:
(1 + ()) = (1+
Σ (ll,z)(ilc.z..o))
TEx
milc (
TE
Σ [m(c,x) + de(c,a) Σ m(le,z) xE
TEN
WelEi, a) + (,(,,a)
Wr(En, a) + 5,(E,, c,a)
Wr(En, a) + max ws d' (E, CEc
= max wr (E,, ..a) d'Ec
Since this is independent of we have that E Z, as required.
17

---

We now show that, given (c, E I, we have ΣOEN V2(c, S 1. This is true since & E P and hence:
(1+ 3t)
Σ () = Σ
E( + Σ
de(c,a)
aEA
aEA
BEA
1+
Σ
aEA
3 1 + Σ
max (,,,,, C'EC
aEA
1 (E()
- (1 + Bt)
required.
The fact that (e x, a) 2 0 for all (c,x,a) EC X follows directly from the fact that, since & E P, we have that (c, a) and 8g and (, x., a) are all non-negative.
C.3 Lemma B.3
We first show that n. P. To show this consider any (c, I. By Lemma B.2 have that EeEA Velc, x. a) & and hence:
Σ v,l,,,,a') 2
E'EA
For all a A we have, by Lemma B.2 that de x, a) 2 and hence the above equation implies that:
1- Σ v1le.2,d)
Te(c,2,a)= = 1/ (c, =
2 0+0=0
K
a'EA
Finally note that:
Σ
Te a) Σ (c,
Σ
1 Σ
K
AEA
aEA
a'EA
Σ (c,2,a) +
( 1- (1-)
Σ
Walc,
aAA
a'EA
Since these equations hold for all (c,x) E I, we have shown that ne E P. Hence, all we now need to show is that N, Z₁. To show this, note that by Lemma B.2 we have that th: E Z,. Hence, there exists a function 2 : A + R such that for all (c,a) C x A we have:
Σ WEX
Em(crr))acca @. c, 2(a)
So for all (c, a) EC x A we have:
W C, a)
Σ ((Cx)))(GG2.a))
xEX
Σ [((.z)))(G,,,0)) + Σ Me(c,2r)
(1- Σ vr(c,,,a))
K
xEX
ZEN
a'EA
==(a) +
1
Σ
(i(e,))
Σ
K
ZEX
d'EAREX
1
1
=((a) +
z(d')
K
K
a'EAA
Since this is independent of we have स, Z, required. This completes the proof.
18

---

C.4 Lemma B.4
Choose any (c, a) E x X' x A. By Lemma B.2 we have EeEd Ve & so since (c a) and 3r and (r, I, a) are all non-negative, we have that:
ne(c,2,0) vr(c, +
1
E
K
d'Ed
1
2 v2(c,2,0) + K (1 1)
v)(C,2,0)
E((e,2, a) + de(c,, a)
1+ B₂
a)
1+ P1.
as required.
C.5 Lemma
B.5
Take any (c,z,a) E A. By Lemma B.4 we have:
(,),,2, 0 S (,,,,,,
1 + 3t
Since 3r and (e x, a) are non-negative we also have:
T,(,, (, 1 Br
mr(c, - Ei -((c,,,))$((
and hence we have shown that:
max Ti. (c,2,,, - (((c,,ra)) s ,,(,,,,)) ,,(,,2,
1+ Br
Now take any (c, I. By lemmas B.1 and B.3 we have that both and & are in P. Hence, by the above equation we have, since 3, 2 0, that:
Er(e,2ra)
Σ max (0, a)) -e(e, s Σ aEA
Te(e, x, a)
(1)
1 + Br
aEA
Te(c, a)
Σ Ee(e,2,a)
(2)
1 Br
1
+ B
Br
(4)
1 Br
$ 3
(5)
required.
19

---

C.6 Lemma B.6
We consider two cases. First consider the case that B, 1. In this case we have, since & and (a) S 1 for all a E A, that:
ve(Et) [Ba S 1] Σ ()) (E()
Be
Σ Te(c,,Z,,00
aEA
2 Σ
Te(c,, Le, (a)
aEA
Now consider the case that Br S 1. Since (((a) E [0, for all A, we have, by Lemma B.5 that:
Σ aEA aEA
((4))
Σ
((d))l(e,, Σ ()) Ee,
oEA
(a) max Te Ee(c,,
aEA
(e Te; (et,,,
$ B.
Hence, we have that:
(e(E)) = [3. = 11 Σ ((a)) 21, a) Bc(Ee)
aed
Σ (a) +
Σ (1) - Σ ((0))((c),211.0) a))
Σ 21))
acA
aad
aEA
- (())m)(
a
So in either case we have the result.
C.7 Lemma B.7
Since # E F(1) we have म, E Z, which implies that there exists a function 2: : - RR such that for all (c, a) EC x A we have (f, e, a) z(a). Hence, we have, for all (c, a) A, that:
( C, ()) = max as (5, é',,,,,) - #, e, a) =a)) =(a)
eec
Since (a) and (c,, a) are non-negetive for all E A, this implies that:
(=) [8 < Σ le(a) + (x)+)
Σ ((() + Σ
max (5, eEC
aed
Σ (())7(e,
required.
20

---

C.8 Lemma B.8
Take any A. Given 6 E E and d' C we have:
= Σ
(c,a)EZ
xEX
which implies that:
Σ (c==
max d'El
(6)
(C.t)E
Σ (G,))EZ
c== [(00 = min (0, .)
C'EC
Σ (C
I== & (0, (0) & m a)
(8)
e'cc
Σ Ic-
m ,c,))
CEc
(c,0)EZ
For all E A, equations
6 and
imply that:
Σ a(0,c,2,,)6(c.2..)
(Gæ)eT
Σ (Cæz)T
[ < [[[(c, x) = (c,, ((,,))]]((()))() + max mnx d. min (e
d'EC
d'eC
E
[8 < [[[(c, = (a,, (0. + max ctEl
max max (0 -
=
d'El
(c,z)EI
= [B < ([((())((e,,,, 2,, a) + max (0
etEC
This means that:
Σ Σ a(0.,,,,)000,0 Els, S 1[((a))(a, 21,0) (C,z)E
Σ
max ((
ceec
aEd
acd
[3 < 1]
(aa))le, a) (,(
aEA
(0)
(10)
Similarly, for all a E A, equations
( and imply that:
Σ 2, (AH)ET
Σ S = = (Ca))) + max
min@r(('
d'EC
dec
(G,a)EI
Σ [8, [][((,x)) (c, (() + max (c,+)EI
( ar((',ct,
etec
C'Ec
[B. < (1, + max (
o'EC
This means that:
Σ Σ () < Σle
[h S
(a)))))(,, + Σ max ma,
ceec
(Gx)EI
acd
DEA
= [3 < 1] Σ
((a)o' (c,,),,, a) 3((d')
aeA
= =v(o')
(11)
21

---

Equations 10 and 11 give us:
Σ
Σ ge c,
((, = Σ Σ
2100,2
Σ Σ 29 (c,a)EI
(C,z)EI aEA
2 (o( - (i(
as required.
C.9 Lemma B.9
In this proof we use, throughout, the property of linearity of expectation. Take any E A. Since It. Ct My and (a) are deterministic when conditioned & we have:
(at) La atl Te(Ce, te, ar)
(((a)
E
& = E
[a = ail
Te (e Zz, a)
((aa)
B[[a = a:] Ec]
Tece, 0)
(((a)
Pla = at Ee
m,(c,, 0)
4(aa)
Te (ct, a) Te(e,, Fr; 0)
= (a)
(12)
Which immediately gives the result.
C.10
Lemma B.10
By lemmas B.6 and B.7
we have:
rt me, (a)
Σ Fe, S ve ye (*)
(13)
and by lemmas
B.8 and B.9 and the linearity of expectation we have, since से is independent of &
that:
(E)E)) ve(A) < Σ
9i(Ei, -
(A
Σ
#(c,
(C.
Σ (C.))E
&t
(14)
Combining equations 13 and
[4] gives us the result.
C.11
Lemma B.11
By Lemma B.1 we have:
(((c,))u(c.e)= E Σ 0i(c.e) Σ x((c
nEC dE
aEC PEH
mEX
Σ Σ 0((c,e)
Σ
"lezz) = a]>x(c,2.a)
aEC CEH
aEA
Σ
Σ
Mele, a)
Σ
Oelc, ((c(()) a]
(EE
EEH
Σ
Σ
(CZ)EI
22

---

and by definition of e' we have:
ΣΣ
8' (c)))a(()) - (GGE)
E xe(e
CEC CEH
dEC CEH
ZEX
ΣΣ Σ
0' (c,
ΣΣ
[e(x) =d)))=])A(G,,;000
EEC EEH
*EN'
Σ
Σ
XL(G,, a)
Σ
((ce))](())) =
(az))TTEd
CEN
E
E
X(G.I,))fG..,a))
(aæ))I
so since & is derived solely from 02 (and deterministic objects) we have:
ΣΣ LEEC eEW
- - (cCe)uuce)) d. =E ΣΣΣ
Σ
(G)(c,2,)- ((xx,,)))(GG3,a) E:
LEEC FEX aEA
so Lemma 8.10 gives us the result.
C.12 Lemma B.12
Since (z + s 22 + 28 for all 2, & E R and since (2 < 2² + 8² for all 2, > 0, we have:
2)2
Σ xo(c:2;
ΣΣ ((ce))))))) ΣΣ o,(c,6)
EEH
aEC dEH
ΣΣ ee(c,e)
ΣΣ Σ
[e(x) [[e(x))=a\(((,zaa)
OEC eEH
2
2 Σ (,(c,e
ΣΣ [e(x) allB: < [][(c, = (ce, ax)]
(((es)
Te Te(C,, Wey at)
GEC CEC CEH
LEEt DEA
2
Or(c,e)
Σ
[e(x) a]le R (()(e)))))((())
SECEEN
KrEAt aEA1
2
0((c,e)
Σ
[e(z) = alle = Rd a)leec,,)
REC CEH
(15)
23

---

Note that:
ΣΣ o(lc,e)
Σ Σ
[e(x)) = al[c= = (et,, ()]
CEC eEH
ΣΣ 6)(c,)
ΣΣ
[e(x) a][ RE (c))
Σ EΣΣn [e(x)) a][c Re ())
CEC EEH
zEN' aEd
WEE DEA
e)(c,)
Σ Σ sEx' aEA
c Re (E: ())
Σ Me(e, v))
Ele(x)) = a]
CEC EEH
FEX
aEd
E e)(c))
Σ cc = Re(Es, a)l
Σ me(c,z)
Σ (e(c,,)) LEX
DEC CEH
AoEA
aeX
ΣΣ
De(c,e) e)
E(e= a))
OEC EEH
aEA
ΣΣ
[c RE(E,, a)l
Σ ee(c,e)
aEA CEC
oEHt
Σ> ΣIG
[c- = Re(E,, a)]
CEC
Σ1
aEA
K
(16)
Similarly we have:
ΣΣ Te(x) a][c KG(E, o)lle((, ?
ΣΣ ec(c,e)
K
(17)
aEC cEHl
wE aEA
Now note that, by Lemma B.4 we have, for all a E A that:
[3 S 1]
(Ce, Le, a)
Ei(c,, 12, a)
24

---

so by Lemma B.1 we have:
(((ee)
E
e,(c,e)
[(((()) a]]3 s [][(e, a) = (c, [,)]
02
Te Te( (c,
cEC
LEA
E
Σ er(c)re)
=c(lt)==allBB. (le(er) aBI[ S
E((ar)
11
Tt. (et, 2e, (t))
LCE
(((a)
Σ
Pl( a1 0c]
Σ De(ct,e) [[(xx)==a][4 al][ S 11
Te (Ct,
aEA
eEH
(a(a) Tr (1,
Σ aEA
Te F2, a)
Σ
ee(ce,e)
[Te(az) - al[3 < 1]
oEH
E
Σ
Se (()((x) al[[: S 1] (e(C,, Zz, a)
CEH
Σ De(c,, [e(xr)) =a al [3 - 1]
Te(e,, a),))
AEACEH
Σ (.(c,,))e(1r) =a]
(e Fe, a)
eEN
2 Eele, Fe, a)
Σ
REAA
2K
(18)
Taking expectations on Equation 115) and then substituting in equations (16). and (88) gives us the result.
C.13 Lemma B.13
Take any (c,e) E x H. Note first that for all (x, a) X' x A have:
Xe(e,z,)) a) 2 -Ic= a)le,cc)) 2 x)(c,))
so that:
vl(c,e) = Σ Xe(,,z,((x))
TE
),(,,2,a)
oEA
Σ m(c,x)
aEANEX
= Σ1
aEd
2 K
as required.
C.14
Lemma B.14
By the description of the UPDATE subroutine in Section ?? that our update procedure is equivalent to creating a function 0/ E RCCH defined such that for all (c,e) E H. we have:
81(c, = (c
II xEG:(c)
25

---

and then, for all C, normalising (f(c, o) to create (c, o). Note that for all (c,z) 2) E I with G((c) we have (y(c,,2 x) and (c, x) o (c,, that Xe x, a) for all A. This
implies that for all (c, e) E C H we have:
=((c,))= II exp(-iAi(c,z, (e(c,e) ( Σ EM(es)((s)) Ve(c, exx(()((((((())e)) FEx
so that:
Defc, e) exp(-fjui(c
04sl(,,))= EvEN (c 1upp--AMil (cp(-)u((c,e)))
as required.
C.15 Lemma B.15
Take any E C. Define:
Σ C((Ge))xp(-fiuccee
CEA
By Lemma B.14 we have:
(((,,,((,,,))) - -BO" 00010(0)))))) = Eor(c,e) In (c,e) e)
(c,ee
Di(c,e) - In
(cti(c,e)
eEW
(1t1(c,e)
Σ (c,e))
Oc(c,e)
CEW
cxp(-ffu(c,ee)
Σ EEH
0 (c,e))
2
-
E (G)e((()))) In(2) Σ (c,e)
oEH
" Σ 0" (c,e)((()))) In(2)
(19)
EEH
Since v S VT/K we have S 1/K so that, by Lemma B.13 we have, for that:
fmv(c,e) 2 -1
so, since exp(-2) I 1 - + 8 for all x 2 -1 and In(1 + 2) & for all 2 R, we have:
In(2) = In
Σ
e) exp((
DcH H
Σ - -
< In
NeeH
e.(c,e) Σ [dlcee)(- sf((c,,)
eEW
1+
Σ Velc, Uelc,e) + Pu((c,)83)
nEA
eE
= Σ
(cce)))()))))))) o Σ 0rlc,
(20)
EEH
eEH
Substituting Equation
20 into Equation
19 gives the result.
26

---

C.16 Lemma B.16
Immediate from summing the inequality Lemma B.15 over taking expectations (condi-
tioned on 1)) and substituting in the inequalities in lemmas B.11 and B.12
C.17
Lemma B.17
From Lemma B.16 we have, for all [2], that:
[ 8fj
E
EBBO ve(c,))) B(O", (c,1
and hence, by summing over all t E [T] and noting the linearity of expectation and the fact that the relative entropy is non-negative, have:
= E Eira] - K KT 1E|2
(B('', (((,,)) - - 01:1(e
BE[T]
E
(B(O', -(0, 10000,+++((00))
AEC
Σ
B(O", (((0)0((c,)))
CEC
Σ B(0", ,0)
that:
Σ Eird
Σ
B(O" 0) + 80KT
n
EETT]
AEC
noting that v // 11/VK KT, we have the result.
D Details of Examples
We now describe and analyse the instances of SPEW required to obtain the results in Section 5 We start with the following lemma:
Lemma D.1. Given a tree T with edge set E and any T A + [0, 1] with T(e, o) E f all E T, there exists a distribution A E AT such that:
a(v,a)= = Σ [e(v)= = ETxA
EEAT
and:
Σ (()) Σ [e(u) & e(v)]= - ΣΣ EEAT (NG))E
Σ (n.O)EE aEA
pT(,, a) (vv
Proof. We prove by induction on [T]. The inductive hypothesis clearly holds for [7| Now consider a tree T with > and let be a leaf of T. Assume that the inductive hypothesis holds for the tree T' created by removing from T. By now proving that the inductive hypothesis holds for T we will have completed the proof of the lemma.
Let X' be the neighbour of A. For all E A let {(a) == x a) and E'(a) T(X,)) a). Let S be the set of all a E A with {(a) & (a()). For all E let:
{(a)
r(a)
((())
27

---

for all a E A \ S let
q(a) = {(a) (7(a)
For all e E AT and a E Alet let r(e, a) be the function e' E A with e' e((A) = a and e'(u)= = =((v) for all T'. Let El be the edge set of T By the inductive hypothesis, let 0' AT be such that:
a(v,a)=
Σ
[e(v) (e) (
EEAT"
and:
Σ (e) Σ [e(u) # e(()]
Σ
Σ
((u,a) - T(e
2
EEAT"
(u,e)Ey
(u,v) aed
For all E AA) S and e E AT with e(X) = define:
0 == (ee)
For all a E S and e E AT with e(X) = a define:
8(7(e, == (e)
For all a S, d' E CA\ and E AT with e(X') = a define:
(()(e,d') = ((d') - ((()))((cc)
For all other e' E AT we define 0(e') == 0.
Note that for all v T' and a E A we have:
T(. a)
Σ Te(v) (c)
Σ Ie(u) aa Σ (()(e,d))) Σ [d((o)= =]](c')
rEAT!
EEAT!
a'EA
d'EAT
and for all E S we have:
a(),a) E(a)= =
= r(a)
Σ
[e(X') (e)
cEAT!
= Σ = =
Σ
[e((A) = alB(c')
rEAT"
d'EAT
and for all a E A \ S we have:
T(A a) E(a)
='(a)= + (E(a) - E'())
-aa + ((a)
Σ (E(a') - (a))))
d'EAYS
='((a) + ((a)
E(''(6) - E(d'))
a'ES
= E'(a) + ((a)
Σ
(1 - (1-r(d'))E'(c)
a'ES
x(),a) + a(a)
Σ (1-r(a'))
a'ES
Σ Ie(>) (e) + ((a)
(1- Σ =dj00())
EEAT"
a'ES
cEAT
Σ [e(X) a)) + Σ Σ
[e(>) al a'la(a)(1 ((a))))0(o)
TEAT"
a'ES CEA
Σ [e(A') a)0(T(e,a)) + Σ
(e() = d'(0()(e,a))
BEAT"
d'EStEAT'
Σ [d((A) aTO(d))
e'EAT
28

---

We have now shown that for all T and a E A we have:
T(o,))= = Σ [e(v)
[[(v)= = alf(e)
cEAT
as required.
For all e A define:
A(e) = E
[e(u) + e(())
(u,N)E
and for all E AT define:
A(e) = Σ
[e(u) + e(v)]
(u.D)EE
Note that for all E A\ S and e E AT with c(X) we have:
Σ
((((e =
= (c)cA((
d'EA
and for all a E and AT with e(X) = a we have:
Σ ((7(e, -(1((()))))))()()d)))))) [+
(((le
a'EA
a'EAIS
(M) Σ 0(r(e,d'))
d'EAYS
(Me) +)(1 r(a)(())) +
Hence, we have:
Σ 0())(())= = Σ (())A(e)+ + 1(1-r(p Σ
Ie(X) - (e)
C'EAT
cЕAТ"
aES
EEAT"
Σ (e)))(e) Σ (1-17) (1)-r())=(X(aa)
CEAT"
aES
E (c))((c)+ Σ (()))
EEAT
aES
Σ (e))((e)+ + E('(a) E(a))
EEAT"
aES
Σ (ee))(())
Σ
iT(, a) x(X.a))
cEAT"
REA
Σ
(( - π (
2
(U.))EE aEA
required.
D.I Trees with a known distribution
Here we define X' = V and Xelc, v) = v for all t E [T] and (c. EC V. We define & by:
(c)) = K
II (u.e)EÉ
(Ie(m)= ((n))=e())) (1- 1 [e(u) # c(v)] (K- 1)N)
1
Ve E 7
This instance of HEDGE can be implemented by belief propagation space complexity bounds.
229 which gives us the time and
29

---

For t E (T], we define the target μe by:
(c(c,)) = p(c,x)
V(cx)) ECX
Soexple,))
To analyse the regret, suppose we have policy म E Q which has statistical parity with respect to noting that:
E N F(m)).
rE[T]
By Lemma D.1
we have 0r C H [0, with:
F(c,2,a) = Σle(x) (c,e) (xxx
cEH
and:
Σ (c,e) EEN
Σ [e(u) # e(v)]
Σ
Σ
- cCEC
2
(u,0)EE
(N.)) aEA
We will now bound the term that appears Theorem 4.1 Juiing our choice of स and 0", which will give us the result. To do this note that for all H we have:
- II(((()) e [m(()) In(KN)
Σ
[e(u) e(v)]
(u,0)E
so that:
(((ce)
① ΣE
8 (c.c)
A(e)
AEC CEH
Σ <EC cEH
8 (c, (n(((e)
E0 In(K) Σ
0" (c,ce) + In(KN)
ΣΣ (c,ce)
Σ
Ie(u) & <(vi]]
GEC CEH
CEC CE7
(u,0)EE
=0 +n
Σ Σ Σ
((c, 2(c,v,a))
aEC (u.e)EE asA
(On(K)( In(K))
D.2 Empirical Statistical Parity
Here we take = V x [T] and define, for all E (T) and (c. C x V. xe(c, = (v. t) and:
G.(c) = ((v,t)
We then define 1 by:
II II (Ie(o,t)= e(u,t c((,tt)) (1- [e(o,t) * e(u,t+ 1)] "EV RE[T-1]
(ee)
K
(K 1)T
for all H. This instance of HEDGE is implemented by rumning the FIXEDSHARE algorithm of 16 for each context, which gives the time and space complexity.
For all / E [T], we define:
p((c,v)
Me(c, (v, = (t, Cxv
30

---

and:
prlc, (c,))) = V(c,u,)) ECXV (IT {tH
Note that if we have yet to see instances with particular protected characteristic E then (c, (u, undefined for all E V. is straightforward to modify the algorithm to handle such situations.
We now analyse the regret. Suppose we have a sequence of policies से E Q such that for all E [T] we have that n, has statistical parity with respect to Pr. Define the virtual policy H' E P such that:
Note that we have म' F(F()) as required.
Define the set H' = A By Lemma D.I (with T being a chain), for all (c, E EC x V we can construct distribution 0' (' u, o) Aw which:
(c,tt) El'(t) all0(cc, (c,
e'EH'
and:
Σ (',,),,e)) Σ I e' c'EW'
Σ Σ
(c,t)),) (e, 1),a)]
1E[T-1]
(E -EEAA aE
Now define, for all E C, the distribution (" o) E Au by:
O"
(c,e) II 0 (c,,,e(e,o)) Ve H VEV
Since for each expert e E H we have:
lIn(((e)) E Eo In(K)N + II(KT)
Σ
Σ
[e(u,t) + c(u,t 1)]
VEVIE(T-
31

---

we also have, for each E C, that:
(((e))
(c,e))l
(<l(e) d(e)
EEW
S Σ
(((e)))(((()
NEH
Σ (c,e)
In(K)N + I(KT)
Σ
Σ (e(u,t)
felestt)1
OEH
VE 1E
In(K)N In(KT) Σ (c,e)
Σ
+e(,,+)
eEH
DEVIE(T-)
-0
In(K)N (IT(TT) Σ
II
V'lc e(u,))
Σ
Σ
[e(u,t) 7 c(u,t +)]
cEH WEV
VEV LEVIE(T-. -1]
In(K)N + (IT)T ΣE
II (((,,,)(,,,))
Σ
[e(u,t) #e(,tt+1)
"EV uEY
:E(T-1)
0
In(K)N KI(KK) Σ
Σ
d'(,,e,eeu,
Σ
[e(e,t) * +elu,t+10 1)1
NEV e(v.o)EH'
1E
1n(KNN +n((T) Σ
E
(G,uee) Σ
[d((1) e' (1 1)
WEVE'EW"
1E(T-1]
In(K)N (I((T)
ΣE Σ
(c, - (',, (10,,,++))0))))
NEV LEVIET--1Jae
o +I(KT) Σ Σ
Σ
me(c,u.a) - (c1l(1151))
NEV DEVIEIT-11 AEA
so that:
('(CeE) O(e)
ΣΣ (c,e))n
E COMMN + ((+))
CEC CEH
We also have:
(())(,))) = Σ (l)o))==((((c,,,euuu.u.
Le(v,t) al (c,e)
e(v.o)EH'
cEW
for all (c. (, EC [ A.
Substituting into Theorem 4.1 gives the regret bound.
D.3 Approximate statistical parity for hierarchical clusterings with unknown distribution
Here we take X' to be the set of sets the tree T that is the hierarchical clustering. Let & the edge set of T. The functions Xt will be constructed online by the characteristic/contet sets seen far. We define 0 by:
(I<())= = c(x')] (1-17) + [e(x) # c((')) (K (1]]
(e) = K
II
Ve E H
(x,x))EE
Now define:
ē E/4H
= 18)22/8)/22
32

---

For each C we maintain dynamic (in that it grows over time) full binary subtree S(c) S T which contains the root. S(c) is initialised to contain the root (which is the set V) as a single vertex. Let L(()) be the set of leaves of ((c) so that L(c) is partition of V. On each trial & E [7] we define, for all (c, v) E C x V. Xe (c, v) to be the unique set in ((c) that contains v, and define Ge (c) to be the set ((c) at trial t. The instance of HEDGE for characteristic c is implemented by belief propagation over the tree (c) as in [26]. This gives us the time and space complexity bounds.
We now describe how S(c) grows and how the functions μr are defined. To do this we will define, for each c C, function jlc, o) S(c) - [o, 1] in which ja(e, V) 1. For each c E C, S(c) and ü[c, o) grow as follows. Whenever we have a non-singleton set in ) [(c) in which there have been trials f so far in which e, and z₁ y then we add the two children of y to S(c). Denoting the
two children by Z and Z' we let m be the number of trials in which = c and 22 E Z and then define:
Me, 2) mj/(c,))/n
2'c,2))== = (n mmm-m((c,))/
On each trial & we define [e(c, o) as follows. For x E Ge(c) we have pe x) = Me, x) and for X Ge(c) we have (e(c, == 0. This completes the description of the instance of SPEW.
We now analyse this instance of SPEW. First, for all (c,J)) E EC x X define:
(c, = Eney p¹ (c, Evev (c,
For all C let (c) be the tree S(c) trial T and let (c) be the set of leaves of (c)). We define the distribution P such that, for all E C, E (c) and E V, we have:
plc, v) = ji(c, ((c,))))( 10 (c,))
Note that by induction over time we always have:
Σ ((.)))) =1
yEA(e)
so that:
Σ p(c,u) = -
E
Σ
('(,))
(c.
DEC (ECI(C) NEY
= E E
M(G Ed((c,))
CEC VECt(C)
VEV
ΣΣ ('(c,)) E M(,)))
OEC VEV
VEC(())
(c(())
CEC VEV
=1
and hence p is a probability distribution as required.
We now show that with probability at least 1 - ô we have that is e-close to p². Let r be the root of T, which equal the set V. For any vertex x E T let f(x) be its parent and let <(x) and (xx) be its left and right children respectively, if they exist. For all c C and st(()) \ (r) define:
p(c,2)= == ji(c,2) x))
(c,
; p" (c(c,)) = (r f(x))
((c,x):=p(cc.))) p(c,
aace 1x))
Note that by the generation of ja(c, x) we have, direct from Hoeffding's inequality, that:
Pl P1 > E] 2exp( -222))
So since:
Eist(c) \ (r]1 ST
33

---

we have, by the union bound, that with probability at least 1 - 27 exp(-222n), which is no less than 1 6, we have:
1 S
for all e E C and æ E (c). So assume that this is the case. Now take any policy л E Q which has statistical parity with respect p². For all E C define:
((c) = Σe' (c,
NEV
For all (c,a) E CC A and y E (c) define:
(c,)),,) == (T())))(())
E (((o)))
vEY
(,) ((c)))((C)
Σ (l NEV
3(c. = == ("'(,,",', (c.))a) Yc,
and let hhc, )) be the height of in the tree (c). Note that by definition of μ (c, we have:
q" (c. V. S n² (c,
Σ (c, =
DEy
We take the inductive hypothesis that for all æ E (c) we have:
18(c,r,a) 2h(c,z)
and prove by induction on h(c, .2. The inductive immediately holds for h(c, 2) 0 by definition of Now suppose it holds when h(c, x) = h (for some h' E [H]) and consider with hic, h + Note that:
(c,,,,,))) x)(,,)) (n" (e, (()))
= =v'le, (c, (eco))))))))
and that:
a(c,,,a) 2),,z) (dcc
plc, =x =pcc #iselliiikchhhooooeeeoooooooooo -B(,,())
so, by defining:
= oecc::===e.ctttttttccccoooooo/od
we have:
a, == q',
= - p(c, <(x))( -ttp: +8C, + (
x
so that, by the inductive hypothesis and since h(c M(()))) have:
18(c, <(x)) (1)
(,(,,
s éq <(x), a) a) (c' (1(c)
(c)
28 |8 a)
< 2 + p(c. 4(z)) ((), (lcpp))))t))))))
2 + 2p(c, (()))M (0(c
2(1+1')
2h(c,r)ē
34

---

We have hence proved that the inductive hypothesis holds always. In particular it holds for z = r so that:
[3(c,r,)) - 2H = e/2
(21)
Since - = and r = this translates to:
1 ((c)
1 AdComaa s 6/2 Σ ((
((c)
Since ı has statistical parity with respect to p there exists some function n: A + [0, 1] such that:
Σ
(( k(a) V(c,a)
{(c)
DEY
which means:
<(a) -12) {(c)
[ k(a) + e/2
for all e E C. Hence, æ has e-approximate statistical parity with respect to p² This completes the proof that p is e-close to p²
We now show that each policy मi has statistical parity with respect to p. Take any c e and let (c) be the set [(c) trial t. Note that for all y E (c) we have:
iic, })
Σ plv))
((c)
VEY
so since for all Y' (c) \ (c) we have:
(lc,)) jlc. a())) ((c,
have by induction that for all y St (c):
jlc, y)
Σ p(t)
((c)
vEY
This means that for all a E A we have:
Σ (c,,a)
((c) NE
((c) NEV
E [xtommaxx(av)).
<(c) vEy
Σ Σ p(e)me(c,))a) <(c) yECi(C) vEY
Mlc. (.) yEC(())
Σ
Σ ((,,,)
xE9.(C)
so since we have n. E F(4) we have that π.. has statistical parity with respect to p.
We now prove the regret bound. Take any म E Ω with statistical parity with respect For all c C let ('(c) be the minimal cardinality permitted clustering such that for all sets y E ('(e) and u, E y we have 7(c, u, o) = #(c, o). Now we define #' E P as follows. First extend such that
for (c, )) E X we have:
1
p(c,y)
El( vEY
((c)
35

---

For any descendant 2 of some Y E (c) we define (c. 2, = [c,, u, o) for any V. For any that proper ancestor of some element of (c) we define 5' (c. x. o) that:
(c, x, a) ((x))() <(x), +
Note that by induction the height of x have:
((,,,,,)== jlc, s(x)) + f((,
Σ
((,,
REA
so that #' P as required. Given x T define (xx) to be the leaf descendants of x. By induction on the height of in T we have:
2,) ā(c, x'EV(o)
Σ
(e, a',)
so that, since the leaves the singleton sets, we have, for all y E X, that:
# (c, M(c)))((
plc u) Σ DE
Hence, on trial /. we have:
Σ (G2,,) 1 ((c) (ECI(O)
E Ellau)
Edce,)) ((c)
(EC.(C)
NEV
so since A has statistical parity with respect to we have that #' F(u).
Now that have shown that P E Nuerr F(u) we can apply the regret bound in Theorem 4.1 Note that for all e E C the number of edges (x, x²) in T in which i' a' o) * x', o) is at most (rb(c, #) 2. Hence, in Section D.I (noting that log([T]) & H), we have distribution
0" x j0, 1] with:
2', Ele(z) (c,e) Xxxxx
oEH
and:
( E (O(HI(())((t))
ΣΣ 8 (c REC EEH
M(e)
Noting also that we have at most (n) trials where F' It, o) # #(c,, Ut. o) we obtain, from Theorem 4.1 the regret bound.
36

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
Justification: The paper solves the given problem so we cannot see any limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
37

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: No experiments
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
38

---

Answer:
[NA]
Justification:
No experiments
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cpippi.ccppulli//uuuia wwwticccguie//eeieeeeeeii CoodeSubeiiie ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
39

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This paper has applications to fairness which is inherently a positive societal impact. We cannot foresee any negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
40

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We cannot foresee any risk of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: No assets used.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
41

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
42

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLM only used for writing assistance.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neur/e httpp////.e///ooeeeeeee///////// for what should or should not be described.
43


Reviews:
[{"review_id": "AfPr1Owgq2", "reviewer": "Reviewer_rm31", "summary": "In this paper, the authors propose an algorithm for contextual bandits that enjoys statistical parity. The proposed algorithm uses a Hedge algorithm subroutine for each protected attribute.", "questions": "No specific questions from my side, but I would appreciate an accessible (to say someone familiar with a textbook treatment of Hedge/Exp4) and intuitive explanation on how SPEW achieves statistical parity in the present context.", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper makes an interesting contribution, IMO. However, I think this articulation is too dense for a non-expert. I had a hard time trying to understand the basic idea of how the statistical parity is achieved by the algorithms.\n\nEven the examples in Section 3 are not covered in sufficient detail for a reader who has not encountered these problems before.\n\nOverall, I think this paper is an instance of there being too much material being packed into too little space.\n\nMinor suggestion: In the paragraph starting on Line 40 from the introduction, the authors describe the contextual bandit problem. It would help if the authors could also articulate what statistical parity means for this specific model (this is made clear later though).", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your review - here are our responses.\n\n\n> I had a hard time trying to understand the basic idea of how statistical parity is achieved by the algorithms.\n\nIn Appendix B we give a detailed overview of how and why the meta-algorithm SPEW works, although we admit this may not be as accessible as possible. In order to make things more accessible (and in the main body) we shall relegate the pseudocode (Section 5.3) to the appendix and replace it by a complete description of how and why SPEW works (using some of the extra page if necessary). This description will be made as accessible to the reader as possible and will complement Appendix B, which contains all the intermediate results.\n\n\n> Even the examples in Section 3 are not covered in sufficient detail…\n\nWe agree - this was due to space issues. We will use the extra page to expand section 3 in order to give more details and make things more accessible to the reader. Both graphs and metric spaces work via reduction to a (potentially random) tree (which is, to the best of our knowledge, the state of the art approach for adversarial bandits in graphs and metric spaces). Hence, in order to save space, we propose to unify sections 4.1 and 4.2 by giving the results for a tree in the main body, then briefly discuss the reductions to it, and defer the actual results for graphs and metric spaces to the appendix. Since the tree is a simpler object to describe, this will make things more accessible to the reader in the main body. In Section 4.4 we hope to have enough space to describe how Euclidean space can be hierarchically clustered (the clusters are hyper-cuboids and you keep splitting evenly across the longest axis)\n\n\n> Overall, I think this paper is an instance of there being too much material…\n\nYes we totally agree. We hope that the extra page and our intended changes described above will give the paper more room to breathe.\n\n\n> Minor suggestion: In the paragraph starting on Line 40…\n\nThanks for the suggestion - we will incorporate.\n\n\n> No specific questions from my side, but I would appreciate…\n\nAs described above, we will do this by relegating the pseudocode to the appendix."}, {"review_id": "vJqrPDRpxC", "reviewer": "Reviewer_FevA", "summary": "In this paper, the authors propose a meta-algorithm that can transform any efficient implementation of Hedge (or discrete Bayesian inference algorithm) into a contextual bandit algorithm that guarantees exact statistical parity on every trial.", "questions": "I am not familiar with the theory things about contextual bandits, so I only have some questions from the angle of fairness.\n1. As statistical fairness focus on the \"positive\" action, in the presented examples in Sec 4, can a \"positive\" action always exist and be clearly defined, especially when |A|>2?\n2. In the second example in Introduction, it says \"the choice of blue agent depends on certain private attributes of the system\" and \"enforcing statistical parity ensures that the selected blue agent is independent of the sensitive attribute\". In this sense, the correlation between the blue agent and private attributes is broken, which may hurt the model's performance (if any), as some useful features can no longer be utilized. How does the proposed method address this potential trade-off?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "***I have reviewed the paper with care, but evaluating the correctness of the theoretical analysis is beyond my current expertise. ***", "was_revised": true, "final_justification": "I am not very confident about the theoretical correctness. But this paper looks good and no reviewer is negative so far. I think this paper is ready to be accepted.", "rebuttal": "We thank you for your review - here are our responses.\n\n\n> As statistical parity focuses on the positive action\n\nThe formulation of statistical parity in terms of a “positive action” typically applies in settings with two actions so that $K=2$. In fact, for statistical parity there is nothing special about the positive action - if we flipped positive and negative we still have statistical parity. Our framework generalises the notion to any $K$ - the selected action is independent of the protected characteristic. There is another generalisation though - we could keep a positive action and the definition is that the probability that the positive action is selected is equal across all protected characteristics (which is a weaker constraint). We believe that it is this generalisation that you have in mind. We also believe that it should be straightforward to modify SPEW so that it satisfies this constraint and has the regret bound against any policy satisfying the constraint.\n\n\n> In the second example…\n\nThe constraint here is that we must select the blue agent in such a way that no information about the sensitive attribute is leaked. Since the blue agent must satisfy this constraint, performance will indeed be less than if it was allowed to leak information. However, aside from the regret term for learning, our algorithm randomly chooses the blue agents that perform (in expectation) the best given this constraint. We do indeed use all the features in order to do this. Interestingly, simply ignoring the sensitive attribute does not satisfy the constraint - as information can still leak due to the correlation of the sensitive attribute and the other attributes."}, {"review_id": "3XTNi6eIvp", "reviewer": "Reviewer_Fh2J", "summary": "The paper develops a novel algorithm for the contextual bandit setting, which is capable of producing no-regret policies that achieve guaranteed statistical parity with respect to protected attributes. The algorithmic proposal starts with Hedge (expressed in oracle-call format) and via reductions/tricks specific to the setting of obtaining statistical parity builds an algorithm entitled SPEW on top of it. The algorithm is then shown to provide regret bounds that have mild dependence on the dimensionality of the problem (rather than blow up when said dimension is exponential). \n\nThe algorithm's dimensionality properties are then showcased in several structured settings including: graphs with homophily; hierarchical settings; metric-induced settings. By way of straightforward extensions, it is furthermore observed that the proposed algorithm also gives a novel solution to the same problem even in the batch (offline i.i.d.) setting, as well as that an empirical-distribution variant of SPEW can be constructed that doesn't require full access to the underlying feature distribution (only to the observed samples).", "questions": "Please see the Weaknesses section above for a list of concrete items that in my view would significantly improve readability of the paper. \n\nSpecifically, the following points are of primary importance:\n\n--- A more careful discussion of related work such as on long-term constraints intersect fairness in online learning; in particular emphasizing technical details compared to methods achieving cumulative constraint violation regret bounds with different tradeoffs in the long-term literature.\n\n--- A clearer reorganized structure where SPEW comes first, before the examples; and please consider throwing both online to batch and also the empirical version of the algorithm into a dedicated section called Extensions, to separate from Examples.\n\n--- SPEW should be re-discussed with a substantial degree of insight into why the particular elements of the pseudocode were chosen as they are (included but not limited to the \\lambda); for this one, please keep in mind first-time readers!\n\nI expect that the authors will be able to provide a careful list of patches along those lines, as well as concrete and detailed chunks of text to be later included in the revised manuscript, in the rebuttal. If this is not performed, then, for full transparency, I may downgrade my current (advance) borderline-accept to borderline-reject.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The main strength of the method is that it fills a niche that to my knowledge has not yet been addressed in the fairness-in-bandits literature; in particular,\n\n--- It enforces fundamental statistical parity guarantees, which have not been accomplished for this task even in the i.i.d. offline scenario;\n\n--- Said statistical parity guarantees are obtained and satisfied in an exact way, without the corresponding O(\\sqrt{T}) or similar regret term corresponding to constraint violation;\n\n--- In contrast to some other related strands of research such as many of the long-term constraints papers, the present work operates under bandit rather than e.g. full information feedback regime;\n\n--- The provided worked-out examples (and the general guarantees) show that the algorithm successfully deals with a-priori exponentially-high-dimensional settings by being able to rely on certain kinds of structure in them (while this is a pervasive theme throughout many online bandits literatures, it has not been instantiated in such setting before, to my knowledge).\n\nFor the main weakness, I have to point out the composition and writing of this paper; it is far from clearly or lucidly written, and has required a lot of parsing effort that could have been saved with a different organization/writing. To give some concrete pointers:\n\n--- First, the main algorithm (SPEW) is relegated to the depths of the paper (after an entire array of example constructions), which I couldn't get behind. \n\n--- Second, and very importantly, the algorithm SPEW that's the main contribution of the paper is not described insightfully in the main paper, nor even in the appendix! For instance, a vague promise is made that the meaning of the concretely set variables \\lambda can be understood from the algorithm analysis, but even in the corresponding appendix this is explained in a very murky way! This opacity could have absolutely been avoided --- e.g. along the lines of explaining that we are looking for suitably upper- and lower-bounding surrogate losses, which, in turn, leads to a loss of a particular form whose subgradient is of the form... etc etc.\n\n--- Third, the comparisons to prior literature are brief and incomplete in ways that make them rushed/not as insightful as they should be in this set of circumstances. To be sure, some effort is made in the intro --- by asking the readers to imagine the process of forming the Lagrangian for the corresponding parity-constrained problem and solving it for the primal and dual variables, and pointing out that this is inefficient to do in the \"brute-force\" way. Such a point is best understood by someone with a background in long-term constraints; but then for such readers, the following couple sentences hinting at the differences from existing long-term works (that most of them don't achieve exact constraint satisfaction and many of them are not applicable to the bandit setting) are not discussed deeply enough to explain the technical nuances. (In fact, some long-term constraints setups emphasize (near-)exact constraint satisfaction in general settings, and some other such works do target bandit settings; and yet other long-term constraints papers have some degree of dimensionality-avoiding oracle efficiency to them.) Also, some essential fairness in online learning references have been missed, such as works on individual fairness online (like Bechavod et al, Metric-free individual fairness).  Moreover, down the line this leads to the proofs of the algorithm's analysis in which long-term constraints influences are not invoked when appropriate. E.g. surrogate loss constructing techniques, which this paper's analysis has an instance of, could/should be mentioned at the right point.", "was_revised": true, "final_justification": "I have carefully considered the authors' response to my review. I have also studied the other reviews and discussion. My overall assessment is that once the presentational aspects of this paper are improved, it will become an acceptable part of the conference. The contribution to the field of online fairness is there, though it fits into a substantial line of work on other notions of fairness and on long-term constraints, so there is no overwhelming technical novelty that would sway me towards a higher score. These aspects form the basis of my borderline assessment in this case. (The other reviews, in my opinion, are somewhat too optimistic in terms of assigned scores to the paper, given its current less-readable state and relatively streamlined techniques; however, the contribution seems appropriate for NeurIPS and valid so far as I checked, so I would not wish to argue for rejection.)", "rebuttal": "We thank you for your detailed review and helpful suggestions. We are committed to improving the paper along the lines you’ve proposed. You mentioned that you would like to see specific chunks of text for the revised version, but we weren’t sure which parts you had in mind. If you could clarify what additional text you’d like to see, we would be happy to draft and share it during the discussion period. We have, however, included one chunk of important text.\n\nWe believe that, with your suggestions in mind, the paper can be presented in a much clearer and more effective way. We are fully committed to revising the presentation accordingly and would be grateful for any additional guidance on what you would like to see in the revised version.\n\n\n> First, the main algorithm (SPEW) is relegated to the depths of the paper.\n\nWe chose to showcase the results of the paper early in the main body, which is why the examples appear first and the details of how and why SPEW works are deferred to the appendix. That said, we agree that this is not optimal. We propose the following modifications. We will cut the pseudocode section from the main body and relegate it to the appendix. With the addition of the extra page we will write a detailed description of how and why the algorithm works. We will place this description before the examples section. The description will contain the full algorithm with all the equations involved.\n\n\n> Secondly, and very importantly…\n\nPlease see the above for details of how we will introduce an accessible description of the algorithm into the main body. We propose to start the description with this (draft) chunk of text…\n\n“Before presenting the technical details, we begin with a high-level overview of the main steps in SPEW.  SPEW operates with any implementation of Hedge that satisfies the inductive bias. A separate instance of this Hedge implementation is maintained for each protected characteristic.\n\nAt the start of trial $t$ each virtual context is revealed in turn to each Hedge instance, which gives us a distribution over the actions for each virtual-context/protected-characteristic pair. This forms a (virtual) policy that we refer to as the “raw” policy. In general, however, the raw policy will not satisfy statistical parity.\n\nThe final policy $\\pi_t$ is obtained by applying a procedure we call “policy processing” to the raw policy (details to follow). We will define a convex function $y_t$, of the raw policy, which upper bounds the expected loss of $\\pi_t$ (evaluated at the context $x_t$). Importantly, for any policy that satisfies statistical parity, $y_t$ evaluated at that policy lower bounds its expected loss (evaluated at the context $x_t$). These properties allow us to use $y_t$ as a surrogate for the expected final loss incurred by the raw policy.\n\nThe update step proceeds by computing an unbiased estimator of the gradient of $y_t$ evaluated at the raw policy. This unbiased estimator gives us, for each virtual-context/protected-characteristic pair, a vector over the actions (which replaces the loss vector in a Hedge update). Hence, for each protected characteristic, the corresponding instance of Hedge is updated once for each virtual context.”\n\nAfter this chunk of text we shall go into the details of the policy processing step, followed by the definition of $y_t$ and the unbiased estimator of its gradient. We hope to have enough room to write all the lemmas in Appendix B as equations in order to give the reader a feel of how the result is proved. We will make sure that we make the description as accessible to readers as possible.\n\n\n> Third, the comparisons to priori literature…\n\nWe commit ourselves to doing a far more comprehensive review of the related literature, which will be placed in the appendix. \n\nWhen it comes to the literature on long-term constraints we do note that we briefly described the results of the papers [4] and [23] which, to the best of our knowledge, are state of the art. The paper [4] does indeed use an oracle to handle the high dimensional bandit problem efficiently. However, the statistical parity is violated and the regret is far worse than SPEW. We note that for [23] the regret is $O(\\sqrt{T})$ and not $O(1)$ as the constraint set has empty interior (which we will explain in the paper). [23] is actually irrelevant as it is not designed for bandit or high dimensional problems. We will make a dedicated section in the appendix that will give a comprehensive discussion of long-term constraint algorithms and how they work, highlighting the differences between these works and ours. We will make sure we cite many works in this appendix section. We will also mention any ties between our work and long-term constraint works, like the use of a surrogate loss as you mentioned.\n\nWe will give a full review of fairness in the batch setting. We will also include discussions on individual fairness and we thank you for the citation here.\n\nIf there are specific papers that you believe should be cited we would be very grateful for your suggestions.\n\n\n> Specifically, the following points are of primary importance...\n\nPlease see above. We shall be implementing all your suggestions fully.\n\n\n> and please consider throwing both online-to-batch...\n\nThank you for the suggestion. Our intention was to present the two unknown-distribution algorithms (the \"empirical statistical parity\" and the hierarchical decomposition) as direct instances of SPEW, which is why we placed them in the examples section. That said, we’re open to restructuring if you feel that it would improve clarity."}, {"review_id": "8ziLpNKcZy", "reviewer": "Reviewer_t2Fz", "summary": "The main contribution of this paper is developing a meta-algorithm called SPEW that translates an implementation of the HEDGE/EXP4 into a scheme that (i) ensures statistical parity, and (ii) achieves the same regret as EXP4 against the best parity-achieving policy in hindsight. The authors instantiate this general strategy for various examples, such as for graph valued contexts, finite metric spaces, statistical parity w.r.t. the empirical distribution, and for approximate statistical parity for hierarchical clustering. \nFinally, the authors conclude by discussing how SPEW can be applied to a fair classification problem via a online-to-batch conversion.", "questions": "**Q1:** Can you discuss about the possibility of constructing SPEW-like meta-algorithms for other notions of fairness, such as equalized odds for example. \n\n**Q2:** In Line 68 it is mentioned that the underlying methodology of SPEW can be generalized beyond HEDGE-based implementations. Can you expand upon this a bit.  \n\n**Q3:** Since both the time and space complexity of SPEW in each trial grows linearly with $M$, can you discuss potential ways of dealing with continuous or finite-but-large class of protected characteristics? What additional assumptions might we need to make? \n\n---\n### Minor Questions/Comments \n\nLine 23: The notation used in the display here is a bit confusing: if I understand correctly, a, c, v are random variables, and b, d, d' refer to realizations? \n\nLines 446, 659, 740: Broken cross-references.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths \n\n* I think the main strength of the paper is that proposed idea of a wrapper around HEDGE algorithm is conceptually quite simple and elegant. Yet, this scheme seems to be applicable quite broadly to structured and unstructured problems, with known or unknown distribution $\\rho$. \n\nWeaknesses \n\n* One minor issue could be the fact that the reduction is tied to a very specific notion of fairness (i.e., statistical parity), and it doesn't seem obvious to extend it to other notions of fairness. \n\n* The paper only consists of theoretical results, and there is no empirical evaluation of practical issues like the effect of constant factors, the speed of convergence, any trade-offs between fairness and performance, scalability etc.", "was_revised": true, "final_justification": "I enjoyed reading this paper, as well as following the discussion with other reviewers and the authors. The authors have clarified my concerns, and I will keep my score and recommend accept.", "rebuttal": "We thank you for your review - here are our responses.\n\n\n> One minor issue could be the fact that the reduction…\n\nWe believe that the main idea behind SPEW -  a “policy processing” step (which takes the output of Hedge for each virtual-context/protected-characteristic pair and maps it to a constrained policy) followed by taking an unbiased estimate of the gradient of a surrogate convex loss, splitting it up into effective loss vectors, and feeding it back into Hedge, should be applicable to other fairness notions. In particular, we believe (but are not 100 percent sure that) it should be applicable to the constraint of selecting each action with a specific (or bounded) overall probability, which is crucial for applications such as inclusive hiring for jobs. However, we do believe that to get regret bounds here the context selection by Nature must be i.i.d. stochastic (as opposed to the fully adversarial Nature of SPEW).\n\n\n> The paper only consists of theoretical results…\n\nWe felt that since this is, to the best of our knowledge, the first paper to enforce statistical parity in the bandit setting, there is no basis for comparison in experiments. We do note that in the appendix we analyse the constant factor in the regret and it is very small - only $\\sqrt{8}$ when the learning rate is optimally tuned. As for trade-offs between fairness and performance, this paper is focused on achieving statistical parity exactly (if the parity distribution is known). We leave it to follow-up work to widen the constraint set allowing for approximate statistical parity with a regret bound against any comparator in the widened set.\n\n\n> Q1 Can you discuss the possibility…\n\nPlease see above where we give an example of another fairness application that we believe the underlying concepts can be applied to. Let us think more about other notions of fairness and we’ll get back to you in the discussion phase.\n\n\n> In Line 68…\n\nWe would like to clarify that this statement (or rather, the existence of theoretical bounds) is conjecture, which is why we use the word “should”. An intuition is that SPEW works by taking the outputs of Hedge and performing a “policy processing” step, and then using the (unbiased estimator of the) derivative of the surrogate convex function in mirror descent. One should be able to replace Hedge (i.e. mirror descent on the simplex) by an algorithm that still performs something similar to mirror descent (with (unnormalised) KL divergence) but not over the simplex - such as the CBA algorithm of [18]. For CBA we have a set of predictors that each assign a confidence-rated prediction to each context and the regret bound would be with respect to any linear combination of predictors that satisfies statistical parity (the existence of such linear combinations can be enforced by adding specialists that are awake only on a particular context).\n\nWe also believe that, when we have full information feedback, SPEW could be applied to a contextualised version of the recent ReSeT algorithm of “Online Convex Optimisation: the Optimal Switching Regret for every Segmentation Simultaneously”. This would allow us to adapt to non-stationarity whilst having inductive biases and will also sharpen the regret when there is no inductive bias. The application should be achieved by choosing the base (static) algorithm for ReSeT to be SPEW. By constructing the propagating actions of ReSeT one will end up with a convex combination of policies with statistical parity - which is itself a policy with statistical parity.\n\nWe will think through the details of the proofs of CBA and ReSeT to check that there is nothing that gets in the way and get back to you in the discussion phase.\n\nHowever, there is an exponential weight algorithm in which it is certainly not straightforward (and may well be impossible) to analyse the application of the SPEW methodology to - and that is the specialist algorithm of “Using and Combining Predictors that Specialise”. It may be possible to get theoretical results here but there is an issue in that we must update all specialists on each trial rather than just the awake ones (which causes issues as we are no longer using mirror descent). We shall discuss specialists as an open problem in the revised version.\n\n\n> Since both the time and space complexity…\n\nHaving continuous (or an extremely large number of) protected characteristics is a hard one. All we can think of at this point is to discretise the protected characteristics. However, this would only give you approximate statistical parity and the approximation would depend on how smoothly the marginal parity distribution changed with the protected characteristic. However, we will think more on this problem and if we think of anything else we will let you know in the discussion period.\n\n\n> Line 23: The notation used in…\n\nYes exactly. Thanks for giving us a description to add to the paper.\n\n\n> Broken cross-references.\n\nThank you - we will fix these."}]

Author rebuttal:

Meta-review: The paper studies contextual bandits, where part of the context encodes a sensitive attribute. They provide regret bounds that satisfy statistical parity in this setting. 

+ The algorithm and setting is different from existing work in group fairness in bandits, and the results seem better i.e. [1] only obtains $T^{2/3}$. I don't think there has been work in this exact setting.

- However, contrary to the authors' claims, this is not the first paper in the area, as there have been papers on *group fairness* in bandits, which is one type of statistical parity, but not in the adversarial setting. The authors and reviewers seem to have completely missed this.  
[1] Group Fairness in Bandit Arm Selection
[2] Group fairness in bandits with Biased Feedback
[3] Fairness-aware Bandit-based Recommendation
[4] Simultaneously Achieving Group Exposure Fairness and Within-Group Meritocracy in Stochastic Bandits
- The structure of the paper could be somewhat improved.

Most of the reviewers didn't seem to have a good grasp of the theory, so I take their evaluation with a grain of salt.
Decision: Accept (poster)