Causal Logistic Bandits with Counterfactual Fairness Constraints
Authors: Jiajun Chen
Jin Tian
Christopher John Quinn
Venue: ICML 2025 poster (2025)
Keywords: bandits
causality
fairness
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: We analyze logistic bandits regret with a long-term constraint for counterfactual fairness.

Abstract: Artificial intelligence will play a significant role in decision making in numerous aspects of society. Numerous fairness criteria have been proposed in the machine learning community, but there remains limited investigation into fairness as defined through specified attributes  in a sequential decision-making framework.  In this paper, we focus on causal logistic bandit problems where the learner seeks to make fair decisions, under a notion of fairness that accounts for counterfactual reasoning.  We propose and analyze an algorithm by leveraging primal-dual optimization for constrained causal logistic bandits where the non-linear constraints are a priori unknown and must be learned in time.  We obtain sub-linear regret guarantees with leading term similar to that for  unconstrained logistic bandits (Lee et al., 2024)  while guaranteeing sub-linear constraint violations.   We show how to achieve zero cumulative constraint violations with a small increase in the regret bound.

Causal Logistic Bandits with Counterfactual Fairness Constraints
Jiajun Chen Jin Tian 2
Christopher John Quinn'
Abstract
long-term constraints (Liu et al., 2022), and reinforcement learning (Jabbari et al., 2017), just name a few. Notably, rather than addressing fairness through the lens of specified attributes, these studies typically operationalize fairess in a different manner by defining it with respect to one-step rewards and introducing a notion of meritocratic fairness (Joseph et al., 2018). An algorithm should never assign higher selection probability to less qualified decision than to qualified one, i.e., arms with higher empirical rewards should be picked more frequently than those with lower empirical rewards, which is distinguishable from the fairness criteria based on specified attribute.
Artificial intelligence will play significant role in decision making in numerous aspects of soci- ety. Numerous faimess criteria have been pro- posed in the machine learning community, but there remains limited investigation into fairness as defined through specified attributes in a sequen- tial decision- maainn framework. In this paper, we focus on causal logistic bandit problems where the learner seeks make fair decisions, under notion of fairness that accounts for counterfac- tual reasoning. We propose and analyze an al- gorithm by leveraging primal-dual optimization for constrained causal logistic bandits where the non-linear constraints are a priori unknown and must be learned in time. We obtain sub-linear regret guarantees with leading term similar to that for unconstrained logistic bandits (Lee et al., 2024) while guaranteeing sub-linead constraint violations. We show how to achieve zero cumula- tive constraint violations with small increase in the regret bound.
In this paper, we focus on a problem structure wherein arms arrive in sequential and stochastic manner from an underlying fixed distribution and decisions are made in an online fashion by the agent. The objective of the agent is to optimize cumulative rewards while achieving fairness counterfactually with respect to specified attributes, i.e. the outcome would not have been substantially different if the specified attributes had different values. In general, this type of task belongs to the setting of dynamic treatment regimes (Murphy, 2003; Lavori & Dawson, 2008; Zhang, 2020) for finding sequence of decisions over finite set of treatments which appears across broad range of applications.
1. Introduction
Artificial intelligence (AI) models, using techniques from statistics and machine learning, are increasingly being used to make decisions that affect people's lives. In light of this, plethora of formal fairness criteria have been proposed (Dar- lington, 1971; Dwork et al., 2012; Hardt et al., 2016; Zhang et al., 2016; Kusner et al., 2017; Zafar et al., 2017; Nabi & Shpitser, 2018; Chiappa, 2019; Chouldechova & Roth, 2020; Imai Jiang, 2023; Plecko Bareinboim, 2024). There has been growing interest in the sequential decision- making community for accounting for fairess, including in settings such as classic and contextual bandits (Joseph et al., 2018), combinatorial bandits (Xu et al., 2020), bandits with
1.1. Contributions
In light of the above, the goal of this paper is to analyze the foundations of online causal fair decision-making, More specially, our contributions are as follows:
We formulate constrained causal logistic bandits prob- lem where the online decision-making processes are characterized within causal structure. We formalize a (non-lincar) fairness constraint based on the counterfac- tual outcome effect that is priori unknown and must be learned in time. To the best of our knowledge, this is the first work to study constrained logistic bandits without known safe decision subset (see Footnote 1).
DDepartment of Computer Science, Iowa State University. Ames. IA, USA MMhhaedd bin Zayed University of Artificial Intelligence, Abu Dhabi, UAE. Correspondence Christopher John Quinn wejquinn@iastatc...m @dd
We provide an unified analysis for the confidence set construction, algorithm design, and performance guar- antee, i.e., sublinear reward regret and sublinear cumu- lative constraint violations by leveraging the regret-to- confidence-sed conversion and the primal-dual online
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
Table 1:
Comparison of reward model, constraint types, frequentist regret guarantees, and cumulative violations upper bounds for select related works. Notation: horizon T, the dimension for arm feature vector n. bounded bandit parameter S, truncated parameter p (see Section 3.2), Slater's constant 6 (see Assumption 3), seeeeeeenssttdeeeddeettt term Rz (T), generalized linear model (GLM). Problem dependent constant K,, R2, K. where VI/K, < 1 < R2 & R when compared within the same decision and parameter spaces. Requires prior knowledge (see Footnote 1) of safe action or policy ( per-round zero constraint violations with high probability).
Algorithm
Model
Constraint
Regret
Violation
Safe UCB-GLM
GLM
GLM
Ô (KNVT)
0
(Amani et al., 2020)
OFULog-r
Logistic
No
T Ö(n 1 V k.(2)
+ minfnn "omffn"S*x2 R2 (T)))
(Abeille et al., 2021)
F-UCB
Causal
Linear
o V
0
(Huang et al., 2022b)
MAB
OFULog+ (lee et al., 2024)
Logistic
No
{ms V
T m.(T) + min mmin R2 (2(()))
CCLB
Causal
Mixture
ÖppSVT + pm² FZ PVT)
Ö(nSTT + n=s + vT)
Theorem
logistic
logistics
CCLB
Causal
Mixture
(pnSvt + pn? pm? S2x + PVT(1 +)))
Proposition 4
logistic
logistics
optimization. We show that the leading term of our regret, ((pnSVT), is significantly better than regret bounds for related works handling constraints and is similar the bound for the unconstrained problem (Lee et al., 2024) (see Remark 3). Furthermore, by in- troducing user-chosen parameter, one can trade off the regret slightly to achieve zero cumulative constraint violations.
ity guarantees that all actions are fair. We model fairness as long-term constraint, for which we seek to bound cumula- tive violations, as it is unclear whether it is possible certify policies as fair (feasible) before collecting data estimate the reward parameter upon which the non-lineer) constraint depends. Unlike our work, they considered that all variables except the reward are discrete-valued with non-parametric (thus more flexible) distributions. They proposed simpler empirical estimation methods for rewards, for which the counterfactual constraints became linear. While the struc- tural causal model was discrete- valued but non-parametric. their regret bound in turn depended on [W], the number of realizations of the set of parent variables of the reward, which is exponential in the size of the parent set (see Ta- ble 1). In contrast, we model rewards parametrically (using a logistic model), depending on feature maps of the con- text and decision variables. This dramatically improves the dimensional dependence, though the fairness constraint be- comes mixture of logistic functions for which estimating confidence bounds (to estimate region of fair actions) is more challenging.
1.2. Related works
We next briefly discuss two lines of literature closely related to our work. See Appendix B for more discussions on additional works.
Firstly, in terms of formulating causal fairness within a multi-armed bandit setting, the closest related work is (Huang et al., 2022b). Like us, they considered a stochastic, contextual MAB problem with a (known) causal graph gov- erning relationships between the stochastic contexts (seen by the learner before making decisions) and the rewards. They assume all variables are discrete. Like us, they pro- posed characterizing fairness with counterfactual fairness (Kusner et al., 2017; Wu et al., 2019; Chiappa, 2019) w.r.t. specified attributes in the context (e.g. specified user fea- tures in an online recommendation system). They make an assumption about fair policy; they provide high probabil-
Among works on MAB with parametric rewards and un- known (stochastic) constraints, there are numerous works on logistic rewards without constraints and linear rewards with linear constraints (see Appendix B for discussions on those works). The only prior work that like us considered non-linear (parametric) reward model with non-linear un-
Pacchiano et al. (2021) (which Huang et al. (2022b)'s analy- sis is based on) requires explicit priori knowledge of feasible action/policy (Assumption 5) and states that it "absolutely neces- sary" to do so for the problem they study (Remark 1). Huang et al. (2022h)'s Assumption 3 only requires the existence of safe policy To; mo is not explicitly used estimating rewards or estimating
set of feasible policies in the main paper. However, to the best of our knowledge it is unclear how the conservatively estimated sets of policies & (shown w.h.p. be feasible for all rounds) that are used to select actions could be guaranteed to be non-empty in carly rounds without a known safe policy To or additional assumptions.
2

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
known (stochastic) constraints is (Amani et al., 2020). They considered generalized linear rewards where the generalized function is assumed to be twice-differentiable and Lipschitz constant of which logistic rewards is a sub-class. We note that in terms of regret bound alone, their bound specialized to logistic rewards is linearly dependent on the worst case parameter K (see Table I), which can be arbitrarily large. They considered generalized linear constraints; like in our work, the constraints depend on the unknown parameter vector 0. in the reward function. However, they consider priori knowledge of some feasible actions. At high level, they explore the environment (improving their estimate of 9.) using those feasible actions and are able to get high probability guarantees of per-round feasibility. We do not assume such prior knowledge. We instead bound long-term constraint violations.
observed confounder affecting both and j. i. U,nü, + 0. We will use the graph-theoretic family abbreviations, e.g.. Pa(V)g stand for the set of parents of V in G. We omit the subscript G when it is obvious. A path from a node X to a node Y in g is a sequence of edges which does not include a particular node more than once. Two nodes X and Y are said to be d-separated by a third set Z in a DAG G denoted by (X TT 2|2)g if and only if Z blocks all paths from every node in X to every node in Y. The criterion of blockage follows (Pearl, 2009, Def. 1.2.3) and is included in Appendix A with formal definitions for completeness.
2. A Theoretical Framework for Constrained Causal Logistic Bandits
In this section, we formalize the theoretical framework of constrained causal logistic bandits in the semantics of SCMs and MABs. We start by considering a recruitment exam- ple (see Appendix C for more motivating examples), where applicants arrive sequentially and stochastically from an underlying fixed distribution, and the hiring decisions made by employer are based some peciision-maing strate- gies to optimize organizational productivity and efficiency while achieving individual fairness for each applicant. The decision making process is characterized by the extended Standard Fairness Model (SFM) (Zhang & Bareinboim, 2018; Plecko & Bareinboim, 2024). See Figure 1 for a graphical model of the SFM. The variable A represents the specified attribute, W is set of confounded features, and M is set of intermediate features, D and Y represent the decision and outcome reward. Contextual information X, = (wa, my, 0t is accessible by the learner before mak- ing decisions.
1.3. Preliminaries
In this section, we introduce the basic notations and defini- tions used throughout the paper. For a wiice-differentiable function g. the notation ý and ğ denote the first and second derivative of function g respectively. For a random variable Z. let Z represent the domain of Z and |Z| the latter's s car- dinality. For two real-valued symmetric matrices A and B, the notation A > B indicates that A - B is positive semi- definite, and when A is positive definite, we denote A-norm for a vector z as ||=|AA- VzTAz. Finally, for two univari- ate real-valued functions f and g. we denote f f= =(g) to indicate that g dominates f up to logarithmic factors; and for an event E Ω we write 1 } the indicator function of E.
We adopt the language of Structural Causal Models (SCMs) (Pearl, 2009, Ch. 7). An SCM M is a tuple (U, F.F,P(()). where U is a set of exogenous (unobserved or latent) vari- ables, V is a set of endogenous (observed) variables, F is a set of structural functions, and IP(u) is a distribution over
2.1. Logistic bandits with structural causal model
At every round I, the learner observes the contextual fea- tures X, = {w,, m, ar). which are drawn from a stochastic distribution and then is presented set of decisions D that de- pend on the candidate's 's context. The learner chooses a deci- sion d, E D and receives an outcome reward yt-1 {0, 1}. The learner's 's decision is based on previous round knowl- edge F, = (Fo, { [We, my, Gz. de, Vt+1 H==) and causal in- formation, where Fo represents any prior knowledge. In our problem, we assume that the outcome variable Y has a generalized linear relationship (Filippi et al., 2010; Li et al., 2017) with the feature Z, specifically.
the latent variables. For the set of structural functions J, fi F decides values of an endogenous variable i e V taking as argument a combination of other variables. That is, i + f((Pa, U.), S V, U, S U, where Pa; denotes the parent set (explained below) of i. Realizations of the set of latent variables U ~ PP( induce an observational distribution P(e) over V. An intervention on a variable i V. denoted by do = <)² is operation where value of is set to constant regardless of the structural function (Ji : i VJ. Each SCM is associated with directed acyelic graph (DAG) G (c.g., see Figure 1). called the causal diagram, where nodes correspond to endogenous variables i E V, solid arrows represent arguments of each function ft- bi-directed arrow between nodes i and j indicates an un-
E E || TZf
(1)
where the fixed but unknown parameters 0. belong to IR". g(x) = (1 + + is the standard logistic function, f is the mapping function known ahead of time to the learner, and the encoded feature vector f(Z) is in R". Then the interventional distribution for the expected reward of do(d.)
'When the variable being intervened on is clear from context, we write do(c) for short notation.
3

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
and do(a,) given the observed contextual features my and
W
wy is represented (Plecko & Bareinboim, 2024):
B| do(de)) do(az) wi, my] g(f().) (2)
where Za, is the feature consisting of the decision de and the contexts X, = (w,, me; ae). In this paper; we consider one specified attribute variable A, which in general is parent of the decision and outcome variable in the causal graph (see Figure 1). Note that the specified attribute value at round is ae and we denote the counterfactual value as af. Both the decision and (hypothetical) counterfactual intervention on the specified attribute value are atomic interventions (Correa & Bareinboim, 2020). Thus, the expected reward for the counterfactual feature df for any decision d, D is
A
D
M
Figure Extended Standard Fairness Model (SFM). Vari- able A denotes the specified attribute, W is a set of con- founded features, M is set of intermediate features, D is the decision, and Y is the outcome. Let X { M, A} denote contextual information the learner has available to make the decision, and let Z = { M, A, D) denote vari- ables the reward distribution may depend on.
[ (de), do(a)); W2, me] = g )
where Z'd, the counterfactual feature for interventions do(a)) and do(d)). Notice that for our problem, we consider that the factual feature Za, and counterfactual feature Z/2 are both in the feature space Z. The identification of (2) and (3) follows by the do-calculus rule (Pearl, 1995), which expresses the do intervention as the functions of observed data. Readers can refer Appendix C for a more detailed analysis. Therefore, the counterfactual fairness effect for decision d, is represented as:
specified attribute had been different. In addition, the learner only receives bandit feedback (the reward). The learner does not observe feedback constraint violations.
Huang et al. (2022b) were the first to propose a counterfac- tual fairness constraint in a bandit framework. We note that their setting confines the learner to decisions from safe action set (see Footnote 1). To the best of our knowledge, that setting requires strong assumptions on prior knowledge of subset of safe actions that can be used even before rewards are estimated (the constraint (4) depends on the unknown reward parameter vector 0.). Prior knowledge of safe actions can be mild in some settings, though we argue counterfactual faimess (a convex combination of logistic functions that depend on the unknown reward parameter vector 0.) is more complex, thereby less obvious for us to construct a prior safe decision without knowing any information about the reward distribution. Therefore, for the setting we consider, since no safe actions might known priori, we allow for instantaneous violations but bound the cumulative violations.
De. g(S(Za)) o(.(Z))
(4)
Remark The above counterfactual fairness measure the conditional average treatment effect (CATE) (Pearl, 2009; Imbens & Rubin, 2015) compared to the total effect, direct effect, or indirect effect (Pearl, 2001). The causul fairness notation proposed in ( (Kusner et al., 2017) is the average effect of treatment on the treated (ETT), while both CATE and ETT could be decomposed as (conditional) path- specific effect, i... (conditional) counterfactual direct effect, indirect effect, and spurious effect (Zhang & Bareinboim, 2018; Plecko & Bareinboim, 2024).
2.2. Counterfactual fairnesss modeling via soft constraint
In this section, we discuss modeling fairness as part of the learner's diecision-making problem. Consider stochastic bandit optimization with a soft constraint for our decision- making problem. In particular, at every round t E [T), the learner selects a decision de to maximize the expected re- ward [do()d(d)))) X,] subject to a constraint on (violations to) counterfactual fairness (4),
The goal of the learner is to maximize the cumulative ex- pected outcome reward while minimize the cumulative ex- pected counterfactual faimess constraint violations through- out the learning process. Define the cumulative expected regret and cumulative expected counterfactual faimess con- straint violations as
a (X,) < T
(5)
R(T) Σ -LLF2,)))
(6)
where 7 is a predefined fairness threshold. In this work, the counterfactual faimness constraint by (5) requires that the expected reward is similar regardless if the value of the
V(T) Σ
||Ad, (Xt)) - 7/4
(7)
4

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
where dj = arg max (xP: TO, and [+ m 0}. In this paper, we establish a stronger ver- sion of regret (Liu et al., 2021; Zhou & Ji, 2022), specifically, let क E II be probability distribution over the set of actions D, and let (
We recall the problem dependent constants discussed in Ta- ble I: k. = 1.)) Kz maxzez g( and K maxzez 1/ā(f clearly, vI/K. < < Kg < K. Notice that such problem dependent con- stants are defined through the first order of logistic function, which quantifies the level of non-linearity of plausible ex- pected reward signals with different scales. In particular, k can be significantly large even for reasonable logistic ban- dits problems. Readers can refer Section 2 of (Faury et al., 2020) for a detailed discussion on the importance of this quantity.
= EeED T0. and (T,, [x()) - 7) = Edep -EEpplAd(X) (d). We compare the received reward with the (baseline) expected reward for x" and x² is the optimal solution of the optimiza- tion problem: m ( ((a)) (Za)) : {xt [Xa()
r) S O}. Thus, the stronger regret is defined as:
T (T) = ( - (O.)) (8)
t=1
3. Methods for Constrained Causal Logistic Bandits
Note that the probability distribution Te could include some decisions that violate the constraint but on average the con- straint is satisfied, while for a single action it must be a feasible one, therefore, R+ (T) 2 R(T).
We next design an online algorithm for the constrained causal logistic bandits problem. We will then develop an unified analysis of regret and constraint violations with rig- orous performance guarantees for our decision making strat- egy. Before proposing the algorithm, we first construct a convex confidence set for the reward parameter 0., using a regret-to- contf-dccon set conversion (Foster et al., 2018; Lee et al., 2024).
2.3. Model assumptions and definition
To study the constrained causal logistic bandits problem, we make the following standard assumptions (Yu et al., 2017; Efroni et al., 2020; Zhou & Ji, 2022). Let denote a compact set in R". Let Z denote the feature space domain.
Assumption 1 (Bounded Bandit Parameter). There is a known bound S on the norm of the (unknown) reward pa- rameter vector 0, ||0||2 S S. V 0 E @.
3.1. Convex confidence set
For logistic bandit problems, a natural way to estimate the reward parameter 0. given F, is to use moximum--lkellhonn estimation. We build on the works for the unconstrained problem (Abeille et al., 2021; Lee et al., 2024). At every round 4, a reward value 3/++1 is sampled from Bernoulli distribution with expected value (or success probability) gf o(f(Za, TO.). The unregularized cumulative logistic loss can be written as:
Assumption 2. The feature mapping function f Z + R" is in a reproducing kernel Hilbert space (RKHS) with a bounded norm (i.c., a measure of smoothness). such that [[(())]22 < 1, A Z 2.
Assumption 3 (Slater's Constraint Qualification). There is a constant 5 > 0 such that there exists a feasible prob- ability distribution mo over decision set DD that satisfies (wo (X,) - -]) I -5, V E (T). Without loss of generality, we assume
(.
yr+i logg (( Σ T=1
1.
(1 - 0r+1) log(1 (00)))(()9(((( =(((2))0)) (10)
Notice that this is a mild assumption since it only requires that one could find a stochastic policy mg under which the expected constraint violations will be strietly less than negative value. Whereas for hard constraints (Amani al., 2019; Khezeli & Bitar, 2020; Pacchiano et al., 2021), they typically assume the non-empty known safe decision set which is stronger than the assumption of existence for a Slater's constant 5 about the learner's 's knowledge.
The loss (,) is a strongly convex function of 0 (Abeille et al., 2021; Lee et al., 2024). The reward parameter estimated using maximum likelihood estimation (MLE), defined as 02 = arg m Le()). For E (0, 1], we use the confidence set:
Ca = {0 E θ (,())) s
= B((a))3
(11)
We next define a problem dependent quantity that impacts learnability.
where Be(ax) = / 1010 log( +e)+ + 2( -) 2) + S) log a
Definition (Problem Dependent Constant ) Kz (0.)
Then the following proposition ensures that (a
max (Z)TT)
confidence set for 0. with high probability:
ZEZ
Proposition (Theorem in (Lee et al., 2024)).
"e will drop the dependency 0, when there no ambigu- ity.
TPVV 2 1, 0. CC(()) 2 - a
5

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
The proof is provided in Appendix D. The proof uses the ap- proach from the online logistic regression regret guarantee of (Foster et al., 2018) without running the online learning algorithm explicitly. We notice that the radius of the convex confidence set in (Abeille et al., 2021, Lemma 1) is around (a(a) = O( n53 log(t)), while the above tightened loss- based confidence set results in O(ynlonn log(())) + S), lead- ing to an overall improvement in the factor of S, especially when S is large, e.g., S 2/1 D
Algorithm 1 CCLB Algorithm
1: Input: Horizon T, truncated parameter P. step size
n VT/p, and the initial dual value á1 0.
for 1. 1,2.3......
., T do
The learner observes the contextual information
X₁ ((t, Wh, m.
Update the estimated reward parameter Oz.
5: Build confidence set Ca(a) from (11),
Ca(a) = fo 6 (L)) =
3.2. Online learning algorithm
Greedy procedure. Choose the optimistic reward parameter de and select the greedy action d;
We consider a constrained stochastic causal logistic bandit over horizon T as described in Section 2.2. The objec- tive for the learner to maximize the cumulative rewards while minimizing cumulative counterfactual fairness vio- lations over time horizon T. To address the challenges the unknown reward and the unknown counterfactual fair- ness constraint, we develop a Constrained Causal Logistic Bandits (CCLB) algorithm by leveraging the primal-dual optimization techniques.
0. arg max max ((f(Z))))) eec,
(12)
de = arg max (f( - @e (( - 7). (13)
deD
7: Update the estimates of the dual variable:
0141 = projjo.pl [ + 1/n(1 a/ (14)
The pseudo code for our CCLB algorithm is in Algorithm At every round t. let the Lagrangian of the primal prob- lem max, ( [( Φ) (T. (ff.)
8: Received a random reward y/+1-
9 (T, (Z.) TO.)) (T, (T,) 2 0} be and then the associated dual function is defined as (()) max, ()),)). Since both the reward and counterfactual fairness constraint depend on the unknown parameter 0,, we first estimate through maximal likelihood estimation and construct a confidence set (a) using the observed histories, i.e., feature vectors and rewards. The greedy pro- cedure is based on the principle of optimism in the face of uncertainty (OFU) (Auer et al., 2002; 2008; Osband & Van Roy, 2014), where the optimistic estimate (6:) is obtained by maximizing the expected reward across the confidence set Ca(a), however, we penalize the expected reward for the constraint violations when the greedy ac- tion (d₂) is picked by the learner over the decision do- main DD The dual update that minimizes q()) with re- spect to é is by taking projected gradient descent with 1/n being the step size. Note that the truncated param- eter is chosen to be larger than the optimal dual vari- able d... And the optimal dual variable Φz is bounded un- der the Slater's constraint qualification, specifically, d. I (Za) (mo.. (f (Za)TO=)) /8, Vd E D from Theorem 8.42 in (Beck, 2017).
end for
constraints as in (Amani et al., 2020). Additionally, the reward and counterfuctual fairness constraint in our algo- rithm share the same unknown parameter 8..
3.3. Regret and constraint violations bounds
In this section, we provide the theoretic upper bounds for both regret and constraint violations of Algorithm 1 and explain the main idea behind the proof of Theorem 1.
Theorem 1. Suppose p 2 2/5, and n /p For O < < 1, under the Slater's constraint qualification in Assumption 3 and regularity assumptions in Assump- tion I and 2, the CCLB algorithm achieves the following bounds simultaneously with probability at least 1 - a for any a E (0,
R4(T) = -0mSmSTT pn2 pn²S² + PVT).
V(T) = +nnSVT+n2S222 VVT)
+ +
((T",,
of "f
Where both R_ (T) and VT)) hides dependencies on log 1 a Remark 3. We remark that: (1) the leading term of our regret O (pnSV/) is similar to the bound O(nS /T/R., established in (Lee el al., 2024) as the logurithmic growth of T. which improves upon (Abeille et al., 2021) (OFULog-r) by a factor of S3/2 and improves upon (Zhang & Sugiyama, 2024) by at least a factor of v/S Though it acquires a mul- tiplicative factor p. one could note that, at an extreme case,
Remark 2. We remark that the computational complex- ity (O(t) per-round) of Algorithm 1 is the same stan- dard algorithms for unconstrained logistic bandits problems (Abeille et al., 2021; Lee et al., 2024), since the dual update is executed via a single-step projection, and the primal op- timization retains the character of the unconstrained case without constructing a prior safe subset designed for hard
6

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
when the Slater's constant 6 is optimized to 1/ (Tg((T,, ). the leading term scales as (nv/T). (2) Compared to the un- construined case (Abeille et al., 2021; Zhang & Sugiyama, 2024; Lee et al., 2024), the regret bound (T)) exhibits an additional term pv'T, which roughly captures the impact of the unknown counterfactull fairness constraint, i.e., convex combination of logistic funcctons, which is not lo- gistic function any more. More specifically, the non-convex nature of the logistic mixture introduces a non-linear rela- tionship between the constraint and the reward parumeter, thereby resulting in more complex estimated feasible re- gion of safe decisions at every round. (3) Compared to the constrained generalized linear bandits (Amani et al., 2020), our regret bound shows a big improvement on the worst case constant K (see Table 1). (4) If 2 1, the constraint violations bound (T) will be zero since the counterfactual fairness constraint is satisfied for all the decisions (see (5)) and our problem falls into the setting of logistic bandits without constraint.
i.e., Ei=ig(((Z,) (0)) - - TO,), we observe that the counterfactual feature vector Zyz and the factual feature vector Zo, are both lie in the same feature space Z for our problem. Thus, Ei= ((f(2z,)) exhibits the same asymptotic upper bound up to logarithmic factors as Ex=1 (ll((,((Zaa)) R₂ are bounded.
g g( TT+)
s([(Za, )0.). thus R, and
Therefore, the regret upper bound R+ (T) can be obtained by choosing & = O. Inspired by (Beck, 2017), we ap- ply tools from constrained convex optimization to obtain the bound on constraint violations V(T). First, we define the the probability distribution n' by (T', (Za,)) T..) and (T', (a,())x())) -) = |Sx, (X+)) - where the policy x' only puts probability mass (equal to 1) decision de chosen by the learner after the observation of contextual information at every round t. Then, we have,
R4 (T)++VV() = Σ (TT o(f(Za)
See Appendix F for the full proof. We next highlight a few key parts of the proof.
(r'=9(f(Za) + + (x', [a(x)) - -7)
Proof Sketch of Theorem 1. We first derive the following key decomposition of total regret and constraint violations that holds for any & E [0 (T) + @V(T) S R1 + R2= + TT, where
Since (TT (T'')(((Z.)TOO.) is convex over n², both (T) and (अ'. [X,)) - 7) are convex over n', by utilizing (Beck, 2017, Theorem 3.60), we obtain the upper bound on the cumulative constraint violations:
T
R1 S
(dl- - (T' g(f.(((TTTT) - T(f())
| (x)I- s 2(R1 + R
+ vTp..
P.
1=1
T
Σ (o(f(zu)) ( +
R2=
Which finishes the proof.
(0U - -( (Ta))
3.4. Improved regret and constraint violations bounds
In Section 3.3, our analysis demonstrates that the proposed CCLB algorithm (Algorithm 1) achieves both sublinear re- gret and sublinear constraint violations upper bounds. An- other natural question to consider is whether the constraint violations bound can be further improved. turns out that by introducing a tightness parameter c in the dual update in Algorithm 1, for < 6,
This is attained by employing a dual variable update and necessary algebraic operations. Note that this bound will serve as the cornerstone for the subsequent analysis of both the regret and constraint violations. To further bound R1 and R2, we apply the following proposition for logistic bandits regret:
Proposition 2. With probability at least - a for any (0, 1), under the CCLB algorithm, we have:
d++1 = Pr [de + 1/nn(Aa, (X.) - - +)] (15)
one can achieve a bounded and in some cases even zero constraint violations by trading the regret slightly while still preserving the same asymptotic order of regret as be- fore. Intuitively, with tightness parameter e > 0 in the constraint, the learner will be more cautious in selecting actions by effectively working with a stricter constraint (e.g. with fairness threshold 7 - e instead of T). Then, under this new hypothetical pessimistic constraint function, the primal problem is modified as: max, ( (TT, (Za) (n,, A (X.)) 7 + <) s 0). Let क. be the optimal solution
Σ o(f(Za)) g(f(Za)) Ö n22skz))
The central idea to obtain the above regret (Proposition 2) is by applying Taylor expansion which tightly links estimation errors (c.g. between O2 and 0,) to prediction errors (c.g. between (f TT,) and T..) readers can refer Appendix E for more technical details. As for the logistic bandits regret based on the counterfactual feature vectors,
7

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
to this new constrained optimization problem, then we have the following relationship between policy x² and x²: Proposition 3. Let policies πt" and n. be the optimal solu-
v T 11T----/(TT--Goo000000-0-------0
/2C, - 1, where C1, C2 C2, are the universal constants independent of n. S, T, Kiz, if n. Z 2 and e' < 8 then one could achieve a zero upper bound on the cumulative constraint violations when selecting e E (6',6).
rions for the constrained problem max (/ (() T
a (X)) - r) S 0} and maxx, ((mes 9 (Za) T0.)) (X.)) T) S 0}. For E < 8, we have,
Note that this user-chosen parameter trades off between the upper bounds of the regret and constraint violations (Jenatton et al., 2016). Minimizing regret often encour- ages exploration and adaptability to changing environments, which might lead to occasional violations of constraints. Conversely, strictly adhering to constraints may limit the algorithm's 's ability adapt, potentially increasing regret.
T
C S 8
Σ ((I(ZZ) t=1
Σ (. 1=1
To further investigate how the user-chosen parameter will impact the regret and constraint violations upper bounds, we define the regret associated with the policy m² as: R$, (T) = Ei= (TT g (f(()))00)
g(f T..), while the constraint violations remain defined by V(T) =
4. Numerical Experiments
Ei [| (X.)l
-x)]-=]_a. - retical results for R2, (T) and V(T):
We then state the following theo-
We next evaluate the empirical performance of our proposed methods on a synthetic data set. See Appendix H for ad- ditional experiments for different values of the constraint threshold and tightness parameter c.
Theorem 2. Suppose p 2 2/6, and 1 = VTip For 0 T<T<L 1 and the user-chosen parameter e E [0, 8), under Slater's s constraint qualification in Assumption and regu- larity ussumptions in Assumption and 2, the CCLB algo- rithm with refined constraint condition (see Equation (15)) attains the following theoretical upper bounds with proba- bility at least 1 a for any [0.1]:
Data set description: We generated the synthetic dataset from structural causal model (modified an example from (Plecko & Bareinboim, 2024)), i.e.,
A t UAW,
W <- N(O, 1 - 2 EAK),
(T) ō (pnSSV + pm kz + pVT()+)))).
M C [N( WW1/2+ + |Uwrl/3) if
V(T)= onnVV + m2 V1+
$
(N WW/3 + |UMl/2)
if
D. + N(O0, [|x (MD))
1 20,
D - (Di, D2,...,D20f
Again, both RE((T and V(T) hides dependencies on log ! Remark 4, One could notice that (1) by introducing a tight- ness parameter e in the dual update, the associated regret RS, (T) still achieves a comparable asymptotic upper bound as (T) in Theorem I; nevertheless, the constraint viola- tions V(T) upper bound exhibits an éT reduction compared to the result in Theorem 1. Consequently, by selecting appropriately, one can offset the other terms through the subtraction CT, thereby obtaining constant upper bound (with respect to the horizon T' on the constraint violations. (2) The difference in regret bounds between Theorem 2 with a user selected E (0,8) and Theorem is (2 + 2). For a problem- dependnt (fxxd) Slater's constraint qualifi- cation constant 5 > 0, increasing only worsens the regret bound, as the learner is increasingly cautious (increasing in c), selecting from smaller set of actions than the learner would have with e = O. If 5 is large, p shrinks lowards 2 and so for a fixed tightness the regret bound reduces. Larger ō also allow for a bigger range of e and thus more room for caution (and regret).
Y + 1(Uy + 3DDD fw> 0),
P(U) = (UAw ~ Bern(0.5), UM, Uy ~ 1).
As defined in Figure 1, A denotes the sensitive attribute (binary valued), W is the confounded feature, M represents the intermediate feature, D E D is the agent's decision, and Y is the outcome. At every round, we generate set of 20 feature vectors ([A, W, M, D: along with their corre- sponding counterfactual feature vectors. We use rejection sampling over the sets to make sure that at least twelve of the feature vectors are feasible.
Algorithms: We evaluate four different algorithms: GLM- UCB (Filippi al., 2010) (unconstrained generalized linear bandits ), OFULog+ (Lee et al., 2024) (unconstrained lo- gistic bandits ), CCLB (our method, causal logistic bandits
"The source code is available at https: https:////tthuboooom jehen- sereenreseaaee research/ CCLB.
'Another potential baseline is (Huang et al., 2022b), which also studied counterfactual faimesss in the causal bandits framework, though for different causal graph. Their code was available at the time of this work.
Proposition 4. By conditions stated in Theo- rem 2, for the user-selected parameter e' = (VT-
8

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
3000
GLM-UCB
OFULog
500
OFULog
2500
OFULog
Cumuletive regret
CCLB
CCLB
Pena leee cunuulative
CCLB
600
Cumulative canstraint
eps-CCLB
2000
300
1500
400
200
1000
200
100
500
2000
4000
6000 Horizon
8000
10000
2000
4000
6000
8000
10000
0
2000
4000
6000
8000
10000
Horizon
Horizon
(b)
Figure 2: Plots for different algorithms GLM-UCB, OFULog+, CCLB (r = 0.2), and c-CCLB (e = 0.14, 0.2) on (a)
cumulative regret; (b) cumulative constraint violations; (c) penalized cumulative regret.
with counterfactual fairness constraints, Algorithm 1), and c- CCLB (our method with user-chosen tightness parameter 6, Algorithm 2).
rarely violates the constraints.
5. Conclusion
We evaluated the algorithms using cumulative regret (6), cumulative constraint violations (7), and penal- ized form of cumulative regret for different horizons. For the penalized cumulative regret, when the action picked by the learner violates the counterfactual fairness constraint, the learner still observes the reward value (i.e. the learner can improve the reward parameter estimate f), but we count the reward earned being 0. In this way, constraint violations allowed but are not (directly) profitable. This penalized form combines the two primary metrics for simpler analysis.
Metrics:
This paper introduced framework for logistic bandits with counterfactual fairness constraints built within a causal struc- ture. The proposed approach attains satisfactory results, demonstrating sublinear growth both regret and constraint violations by effectively balancing exploration and exploita- tion within the environment via primal-dual optimization. By introducing a user-chosen parameter, one can trade the upper bounds between regret and constraint violations to achieve zero cumulative constraint violations.
Several promising directions emerge for future research. (I) One important direction is to extend our method to work with unobserved confounders (i.e. W would unobserved). (2) Another interesting direction is to extend our model to handle distribution shifts over time. (3) A third interesting direction would be extend our work handle budget constraints and consider fairness notion defined by the resource assignment, potentially building on existing work in bandits with knapsacks (Tran-Thanh et al., 2012; Badani- diyuru et al., 2018; 18 Nie et al., 2024).
The results are plotted in Figure 2. Beginning with penalized cumulative regret (Figure 2 (c)), where rewards are only received for fair actions, there large gap tween our method (CCLB) and the methods of OFULog+ and GLM-UCB, with the gap growing larger for longer hori- zons. This is expected since GLM-UCB and OFULog+ do not account for constraints. Both baselines have nearly lin- car penalized cumulative regret across horizons used. OFU- Log+ does because it frequently violates constraints, and thus large cumulative constraint violations, despite learning good actions (for the unconstrained problem). For cumula- tive regret (unpenalized), OFULog+ performs better than method (which seeks to satisfy the constraint).
Results:
Acknowledgments
We thank Wen Huang for discussion. This material is based upon work supported by the National Science Foundation under Award No. 2321786.
GLM-UCB performs poorly at identifying good actions within the horizons (Figure 2 (a)). GLM-UCB's regret bound has a linear dependence on the λ (see Table 1). GLM- UCB is also designed for a more general class of reward functions. Though e-CCLB has larger cumulative regret and (slightly) larger cumulative constraint violations than CCLB (but less than GLM-UCB), the penalized regret of c-CCLB are smaller than CCLB when T goes larger (Fig- ure 2 (c)), especially, the growth rate of e-CLLB is nearly from horizon T 6, 000 to horizon = 10, 000, which
Impact Statement
This paper presents work whose goal is to advance the field of machine learning. The results in this paper may have implications bringing together strong practical results in causality and decision-making Such integration is antici- pated to contribute to the development trustworthy AI.
9

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
References
Chiappa, S. Path-specific counterfactual fairesss. In Pro-
ceedings of the AAAI Conference on Artificial Intelli- gence, volume 33, pp. 7801-7808, 2019.
Abeille, M., Faury, L.,, and Calauzènes, C. Instance-wiss minimax-oppiiman algorithms for logistic bandits. In Inter- national Conference on Artificial Intelligence and Statis- fics, pp. 3691-3699. PMLR, 2021.
Chouldechova, A. and Roth, A. A snapshot of the frontiers of fairess in machine learning. Communications of the ACM, 63(5);82-89 2020.
Agrawal, S. and Devanur, N. Linear contextual bandits with knapsacks. Advances in Neural Information Processing Systems, 29, 2016.
Correa, J. and Bareinboim, E. A calculus for stochastic interventions: Causal effect identification and surrogate experiments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 10093-10100, 2020.
Agrawal, S., Avadhanula, V., Goyal, V., and Zeevi, A. Thompson sampling for the MNL-bandit. In Conference on Learning Theory, pp. 76-78. PMLR, 2017.
Darlington, R. B. Another look at "cultural faimess". Jour- nat of Educational Measurement, 8(2):71-82, 1971. ISSN 00220655, 17453984. URL http:/ /wtp///wwww..... jstor.
Amani, S., Alizadeh, M., and Thrampoulidis, C. Linear stochastic bandits under safety constraints. Advances in Neural Information Processing Systems, 32, 2019.
1143999.
Amani, S., Alizadeh, M., and Thrampoulidis, C. General- ized linear bandits with safety constraints. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3562-3566. IEEE, 2020.
Ding, D., Wei, X., Yang, Z., Wang, Z., and Jovanovic, M. Provably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2021.
Dong, S., Ma, T., and Van Roy, B. On the performance of thompson sampling on logistic bandits. In Conference on Learning Theory, pp. 1158-1160 1100. PMLR, 2019.
Amari, S.-i. Information Geometry and Its Applications. Springer Publishing Company, Incorporated, 1st edition, 2016. ISBN 4431559779.
Dwork, C.,, Hardt, M., Pitassi, T., Reingold, O., and Zemel, Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 214 224,22666222 2012.
Auer, P., Cesa-Bianchi, N., and Fischer, P. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., 47(2-3):35-255,, May 2002. ISSN 0885-6125, doi: 10.
1023/A:10136889744352. URL https: :ttess://dooo/// aeg..oor///o.ooooo.oo....oo.oo.. 10. 1tt1122/A:111335100
Efroni, Y., Mannor, S., and Pirotta, M. Exploration- exploitation in constrained MDPs. arXiv preprint arXiv:2003.02189 2020.
Auer, P., Jaksch, T., and Ortner, R. Near-optimal regret bounds for reinforcement learning. Advances in Neural Information Processing Systems, 21, 2008.
Faury, L., Abeille, M., Calauzènes, C., and Fercoq, O. Im- proved optimistic algorithms for logistic bandits. In In- ternational Conference on Machine Learning, pp. 3052- 3060. PMLR, 2020.
Badanidiyuru, A., Kleinberg, R., and Slivkins, A. Bandits with knapsacks. J. ACM, 65(3), March 2018. ISSN 0004- 5411. doi: 10. 10.1145/3164539. URL https:://ol:
Faury, L., Abeille, M., Jun, K.-S., and Calauzènes, C. Jointly efficient and optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pp. 546-580. PMLR, 2022.
Beck, A. First-Order Methods in Optimization. SIAM- Society for Industrial and Applied Mathematics, Philadel- phia, PA, USA, 2017. ISBN 161 1974984.
Filippi, S., Cappe, O., Garivier, A., and Szepesvári, C. Para- metric bandits: The generalized linear case. Advances in Neural Information Processing Systems, 23, 2010.
Beygelzimer, A., Langford, J., Li, L.., Reyzin, L.., and Schapire, R. Contextual bandit algorithms with super- vised learning guarantees. In Proceedings of the Four- teenth International Conference on Artificial Intellignce and Statistics, pp. 19-26. JMLR Workshop and Confer- ence Proceedings, 2011.
Foster, D. J., Kale. S., Luo, H., Mohri, M., and Sridharan, K. Logistic regression: The importance of being improper. In Conference on Learning Theory, pp. 167-208. PMLR, 2018
Brekelmans, R., Masrani, V., Wood, F., Steeg, G. V., and Galstyan, A. All in the exponential family: Bregman duality in thermodynamic variational inference. arXiv preprint Xrxi:2207..000 00642, 2020.
Hardt, M., Price, E.,, and Srebro, N. Equality of opportunity in supervised learning. Advances in Neural Information Processing Systems, 29, 2016.
10

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
Hu, Y. and Zhang, L. Achieving long-term fairness in se- quential decision making. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 9549-955 2022.
Lee, J., Yun, S.-Y., and Jun, K.-S. Improved regret bounds of (multinomial) logistic bandits via regnet-to-confidence set conversion. In International Conference Artificial Intelligence and Statistics, pp. 4474 4482. PMLR. 2024.
Hu, Y., Wu, Y., and Zhang, L. Long-term fair decision making through deep generative models. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 22114-22122 2024.
Li, L., Chu, W. Langford, J., and Schapire, R. E. A cartextual-bandiee approach to personalized news arti- cle recommendation. In Proceedings of the 19th Inter- national Conference on World Wide Web, pp. 661-670, 2010.
Huang, W., Labille, K., Wu, X., Lee, D., and Heffernan, N. Achieving user-side fairness in contextual bandits. Caaman-Centril Intelligent Systems, 2(3):81 2022a.
Li, L., Lu, Y., and Zhou, D. Provably optimal algorithms for generalized linear contextual bandits. In Interna- tional Conference on Machine Learning, pp. 2071-2080. PMLR, 2017.
Huang, W., Zhang, L., and Wu, X. Achieving counterfac- tual fairness for causal bandit. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6952-6959, 2022b.
Liu, Q. Xu, W., Wang, S., and Fang. Z. Combinatorial bandits with linear constraints: Beyond knapsacks and fairness. Advances in Neural Information Processing Systems, 35:2997-3010, 2022.
Imai, K. and Jiang, 7. Principal Fairness for Human and Algorithmic Decision-Making Statistical Science, 38 (2)3317 - 322, 2023. doi: 10.1214/22-STS872 URL https: //tp::////.../ org/ 10. 10w111222222222
Liu, X., Li, B., Shi, P., and Ying, L. An efficient pessimistic- optimistic algorithm for stochastic linear bandits with general constraints. Advances in Neural Information Processing Systems, 34:24075-24086, 2021.
Imbens, G. W. and Rubin, B. Causal Inference for Statis- tics, Social, and Biomedical Sciences: An Introduction.
Cambridge University Press, 2015.
Murphy, S. A. Optimal dynamic treatment regimes. Jour- nal of the Royal Statistical Sociery Series B: Statistical Methodology, 65(2)33313355 2003.
Jabbari, S., Joseph, M., Kearns, M., Morgenstern, J., and Roth, A. Fairness in reinforcement learning. In Interna- fional Conference on Machine Learning, pp. 1617-1626. PMLR. 2017.
Nabi, R. and Shpitser, I. Fair inference on outcomes. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 32, 2018
Jenatton, R., Huang. J., and Archambeau, C. Adaptive algorithms for online convex optimization with long-term constraints. In International Conference Machine Learning, pp. 402 402-411.20 A11..MMR. PMLR, 2016.
Nic, G., Zhu, Y., Nadew, Y. Y., Basu, S., Pavan, A., and Quinn, C. Size-constrained k-submodular maximiza- tion in near-lines time. Uncertainty in Artificial Intel- ligence, pp. 1545-1554, PMLR, 2023.
Joseph, M., Kearns, M., Morgenstern, J., Neel, S., and Roth, A. Meritocratic fairness for infinite and contextual bandits. In Proceedings of the 2018 AAAI/ACM Conference on Al, Ethics, and Society, pp. 158-163, 2018
Nic, G., Aggarwal, V., and Quinn, C. J. Gradient methods for online dr-submodular maximization with stochastic long-ten tengtterm constraints. Advances in Neural Information Processing Systems, 2024.
Khezeli, K. and Bitar, F. Safe linear stochastic bandits. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 34, pp. 10202-10209, 2020.
Oh, M.-h. and Iyengar, G. Thompson sampling for multi- nomial logit contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
Krause, A. and Guestrin, C. Near-optimal observation se-
lection using submodular functions. In Proceedings of the AAA/ Conference on Artificial Intelligence, volume 7, pp. 1650-1654, 2007.
Osband, I. and Van Roy, B. Near-optimal reinforcement learning in factored MDPs. Advances in Neural Informa- tion Processing Systems, 27, 2014.
Kusner, M. J., Loftus, J., Russell, C., and Silva, R. Coun- terfactual fairness. Advances in Neural Information Pro- cessing Systems, 30, 2017.
Pacchiano, A., Ghavamzadeh, M., Bartlett, P., and Jiang, H. Stochastic bandits with linear constraints. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 2827-2835 PMLR, 2021.
Lavori, P. W. and Dawson, R. Adaptive treatment strategies in chronic disease. Annu. Rev. Med., 59(1):443-44 453, 2008.

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
Pearl, J. Causal diagrams for empirical research. Biometrika, 82(4):669 688, 1995. ISSN 00063444, 14643510. URL http:// http:://www. jstor. www.ooo.orrroteeeeeeeeeeeoooeooe wttp//taaleeee/e33332
Zhang, Designing optimal dynamic treatment regimes: causal reinforcement learning approach. In International Conference on Machine Learning, pp. 11012-11022. PMLR, 2020.
Pearl, J. Direct and indirect effects. UAT'01, pp. 411-400, San Francisco, CA, USA, 2001. Morgan Kaufmann Pub- lishers Inc. ISBN 1558608001.
Zhang, J. and Bareinboim, E. Fairness in decision- making- the causal explanation formula. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Pearl, J. Causality: Models, Reasoning and Inference. Cam- bridge University Press, USA, 2nd edition, 2009. ISBN 052189560X.
Zhang, L., Wu, Y., and Wu, X. A causal framework for dis- covering and removing direct and indirect discrimination. arXiv preprint arXiv: 1et16/111.000..0 2016.
Plecko, D. and Bareinboim, E. Causal fairness for outcome control. Advances in Neural Information Processing Sys- tems,
2023.
Zhang, Y.-J. and Sugiyama, M. Online (multinomial) logis- tic bandit: Improved regret and constant computation cost. Advances in Neural Information Processing Systems, 36, 2024.
Plecko, D. and Bareinboim, E. Causal faimess analysis. Foundations and Trends in Machine Learning. Vol. 17, No. 3, pp 1-238. DOI: 10.1561/2200000006 2024.
Zhou, X. and Ji, B. On kernelized multi-armed bandits with constraints. Advances in Neural Information Processing Systems, 35:14-26, 2022.
Plecko, D. and Bareinboim, E. Fairness-accuray trade-offs: A causal perspective. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 39, pp. 26344- 26353, 2025.
Tran-Thanh, L.,, Chapman, A., Rogers, A., and Jennings, N. Knapsack based optimal policies for budget-limited multi multi-armed bandits. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 26, pp. 1134-1140, 2012.
Vershynin, R. High-Diman Digh--Dimessioall Probability: An In- troduction with Applications in Data Science. Cam- bridge University Press. ISBN 978-1-108-4151944 doi: 10.1017/9781 108231196.
Wu, H., Srikant, R., Liu, X., and Jiang, C. Algorithms with logarithmic or sublinear regret for constrained contextual bandits. Advances in Neural Information Processing Systems, 28, 2015.
Wu, Y., Zhang, L., and Wu, X. Counterfactual fairesss: Unidentification, bound and algorithm. In Proceedings of the Twenty-Fight International Joint Conference on Artificial Intelligence, 2019.
Xu, H., Liu, Y., Lau, W. C., and Li, R. Combinatorial multi-armed bandits with concave rewards and fairness constraints. In IJCAI, pp. 2554-2560, 2020.
Yu, H., Neely, M., and Wei, X. Online convex optimization with stochastic constraints. Advances in Neural Informa- tion Processing Systems, 30, 2017.
Zafar, M. B., Valera, I., Gomez Rodriguez, M., and Gum- madi, K. P. Fairness beyond disparate treatment & dis- parate impact: Learning classification without disparate mistreatment. In Proceedings of the 26th International Conference on World Wide Web, pp. 1171-1180 2017.
12

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
Contents
Introduction
1.1 Contributions
1.2 Related works
1.3 Preliminaries
2 A Theoretical Framework for Constrained Causal Logistic Bandits
2.1
Logistic bandits with structural causal model
2.2 Counterfactual fairness modeling via soft constraint
2.3 Model assumptions and definition
5
3 Methods for Constrained Causal Logistic Bandits
3.1 Convex confidence set
5
3.2 Online learning algorithm....
3.3 Regret and constraint violations bounds
3.4
Improved regret and constraint violations bounds
Numerical Experiments
8
Conclusion
Preliminaries
14
Additional Related Works
14
Causal Logistic Bandits Framework
15
Confidence Sets
16
Logistic Error Upper Bound
18
Regret and Constraint Violations Upper Bounds
23
F.1 Proof of Theorem
23
F2 Proof of Proposition 3
26
F3 Proof of Theorem
27
F.4 Proof of Proposition
28
Technical Lemmas
29
Additional Experiments
30
13

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
A. Preliminaries
first provide formal definition for d-separation discussed in Section 1.3,
Definition 2 (d-separation (Pearl, 2009)), A path is said to be d-separated (or blocked) by a set of nodes Z if and only if (1) contains chain + m + or fork i + m + j such that the middle node m is in Z, (2) contains an intervened fork (or collider) > m + such that the middle node m is not in
We then detail below some useful notations that have been used throughout the paper.
The set of all the decisions.
0.
true reward parameter vector (RR)).
Y
reward variable {0, 1}.
X
context vector including the specified attribute, the confounded features, and the intermediate features. mapping feature vector (IR").
f(Za,)
d
regularization parameter.
Φi
dual variable.
p
truncated parameter. user-chosen tightness parameter.
e
8
Slater's constant.
failure probability.
C((a)
confidence set. n-dimensional ball of radius under the @ norm.
(1)
11-11
2 norm.
11-
H H-weighted Euclidean norm (H is a symmetric positive definite matrix). Bernoulli distribution with parameter p.
Bern(p)
We further recall and introduce the following functions and use for the following analysis,
(X,) = g(f(Zu.) - g(f((2)))
(16)
[-1
Ve Σ f(Za.) f(Za.) + Achn
(17)
H.(0.) Σ (0.(
AeIn
(18)
G.(0,0.) Σ [" (1- (1-))) s(Za) -0.) du f(Za,) f(Za.) + X (19)
Juz
[ (( + ( 0.)) de
w w(F(Za),,0,..)
(20)
Where the regularized design matrices V,, (,)),,, G, and w (f((a,)) ). 0..00.. 0.) are defined for the proof of logistic bandits regret upper bound in Appendix E. In particular, (0.))) measures the local behavior of the logistic function through g (T..).)TO...
),0(,
B. Additional Related Works
Logistic bandits. The logistic bandits model represents sequential decision-making framework that has attracted substantial attention within the parametric bandits literature (Li al., 2010; Filippi al., 2010; Li et al., 2017; Dong et al., 2019). In recent work, Faury al. (2020) proposed an optimistic algorithm based on finer examination of the non-linearities the reward function study the prohibitive linear dependencies introduced by in the regret upper bound. Abeille al. (2021) proved a minimax-optimal rate by deriving an ((n/TT/K.(T) problem-dependent lower-bound, which implies that the non-linearity in logistic bandits can ease the Faury et al. (2022) addressed the issue of computational tractability while preserving statistical efficiency by designing a new convex confidence set. Additionally, another line of research the multinomial logit contextual bandit problem (Agrawal al., 2017; Oh Iyengar, 2019; Zhang Sugiyama, 2024; Lee et al., 2024), which generalizes the binary logistic bandit
trade-off' in the long-term regime, i.c. K. (T') > 1.
14

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
by allowing the learner select subset of arms. In partieular, (Zhang & Sugiyama, 2024; Lee al., 2024) also improve the logistic bandits on the regret guarantee (with respect S) and computational complexity, respectively.
Fairness. The body of research in fair machine learning is expanding and encompasses variety of contexts. Within this field, three distinct tasks can be identified: (1) the detection and quantification of biases in currently deployed policies; (2) the development of fair predictive models for outcomes; and (3) the formulation of fair decision-making policies. Our work falls under the setting of online outcome control (task (3)) that explores fairness through a causal lens (Huang et al., 2022a;b; Plecko & Bareinboim, 2023; 2025). Unlike us, Plecko & Bareinboim (2023; 2025) explored the fairness through the path-specific counterfactual effect in an offline setting along with budget constraint. As for the online setting, Hu & Zhang (2022) studied achieving long-term faimess within Markov Decision Process (MDP) framework, in which they quantified long-term fairness by evaluating the path-specific effects in a causal graph under interventions sensitive attributes and predicted decisions. More recently, Hu et al. (2024) studied long-term fair decision makinng through deep generative models.
Constrained MABs. There is large body of work on bandits with different types of constraints, including knapsack bandits (Wu et al., 2015; Agrawal & Devanur, 2016), submodular maximization (Krause & Guestrin, 2007; Nie et al., 2023), bandits with hard safety constraints (Amani al., 2019; Pacchiano et al., 2021), and bandits with cumulative soft constraints (Liu et al., 2021; Zhou & Ji, 2022). Among them, the bandit setting with cumulative soft constraints is most closely related to ours in that the goal is also to minimize the cumulative constraint violation. In particular, Zhou & Ji (2022) considered a general unknown reward function and a general unknown constraint function in kemnliied bandits via primal-dual optimization. More broadly, this type of constrained problem has also been studied in the reinforcement learning (RL) setting (Efroni et al., 2020; Ding et al., 2021) where constraints are managed through convex optimization methods.
W
W
A
A
D
M
M
(a)
(b)
Figure 3: (a) A causal diagram representing Gp: (b) another causal diagram representing 9D,A-
C. Causal Logistic Bandits Framework
Here, we provide another example to motivate our constrained causal logistic bandits problem.
Online Recommendation System (Huang al., 2022b). Customers arrive sequentially according an underlying stochastic distribution, and an online ceriiiinnmmaingg model selects and recommends specific item to each incoming individual based on a predefined strategy. In this context, each arm represents distinct item content piece available for recommendation to user. The reward is determined by the user's interaction with the recommended item, such as whether the user clicks on it or not. The fairness constraint mandates that customers with similar profiles receive similar rewards, irrespective of their specific attributes and the particular items being recommended.
Next, we provide proofs for (2) and (3), which follow by the do-calculus rule (Pearl, 1995).
Y| do(a)) wt m.] E| [de, at, We, mz]
(21)
= E|Y|Za!
(22)
((((Za))TO...
(23)
where (21) follows by (D, A IL YJW, M) (see Figure 3b); (22) follows by denoting Za, as the features from de, We, m,
15

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
and az; and (23) follows by the logistic reward assumption (()). As for (3), E [[]]do())), do(a)), we; ma] [[ dy Wt, me]
(24)
[
(25)
g(f(Za,)
(26)
where (24) follows by (D,A TL YIW,M)en. gn (see Figure 3b); (25) follows by denoting Zá as the features from de, Wi, my and ai; and (26) the last equality follows by the logistic reward assumption, similar as above.
D. Confidence Sets
In this section, we provide proofs for the construction of the improved convex confidence set for the estimated bandit parameter presented in Section 3.1. We borrow the techniques from (Lee et al., 2024, Section 3) to obtain the results.
Recall the convex confidence set definition:
C,(a) = {8 0 s =
where:
+ +e)+ + +2(((e 2) 8) log _ a 2n
St
B((a)=
10n log( log(
Proposition Let a E (0, 11, then
P(Vt 2 0. E C((a)) 2 a-a.
Proof. The proof unfolds through three principal technical components similar with (Lee et al., 2024). First, we invoke decomposition identities for the logistic loss, expressing (0) (0.) as the sum of (i) the regret of the online learning algorithm, (ii) martingale difference sequence, and (iii) a collection of KL-divergence terms. Second, in controlling the martingale sum, we derive and apply an anytime variant of Freedman's 's inequality tailored to martingales. Third, to bound the Kl.-divergence contribution, we fuse the self-concordant analysis of Abeille et al. (2021) with an information-geoment interpretation of the KL divergence.
Firstly, we denote & as a real-valued martingale difference noise where y- = (Za.) + f., thus for the logistic loss &, (0) Vr log g (Za))
(1 y. log (1 g TT)) we have that the following equality holds for any 0: & (0.) = (0) + (Ja,)), 0 0.) - KL. L. (Berr((( T..)) Bern(g(J
)T))))
The equality follows from the first order Taylor expansion with an integral remainder (see (Lee et al., 2024, Appendix C.4.1) for more details). Setting to be the optimistic estimate 0, and taking a sum over time steps T:
0 Σ (0.) - (.(()) (B0))))e(())KK((BBmm(((l KT, Bem S-
+7fnrn/nifiaaaaaaa//////mm///1/1 0.)
Σ ((,)) +..00)+)+000 --0)))0--000000))--------------- -.0000)0--0(((/(((144)))))))) Bern((/((2))) + (,)()),)) -0)
(27)
= Σ (()))) (.(0.) - KL(Bem(g(f(zu.)T..) (enn -o,) 0.)+ + Σ l (,,0) - e, (,(
7=1
(28)
where in (27) we add and subtract (,,) and in (28) rearrange terms. We further define (i(() = Σt=1 Er(( 1,
0.), (t) E'= (TerBee (7a,, TT,)), Bern(g(] TT,.), and (s(t)= Σi=1 er (0-)) - (-(0,) Using (28),
we then have
1
(, - (.)))
Σ (0. ec(0)) = (i(() (())))())++()))))
(29)
16

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
Upper Bounding (1). Recall that J, = ((S(Za, (Z ,.,.... f(Za, Nr: (1)3 is the filtration for bandit model, f(Za,) and 0, are Fr ------uaaaaallee and Êr is martingale difference sequence w.r.t Fr-1- Thus, we have that,
(( -1 -.. (f(Za.). -8) =(
(30)
= (f(Za.), - 0.) g(f( (11=)((22.)T8..)
(31)
(32)
Where (30) follows by the measurability of (f(Za,), 0- - 0.) w.r.t Fr-1: (31) is because B[G)) = Var(y=) =
g(((Za,)O0.(( (T.))) Also,
(f 0.-1 - (.11 - -
$ (f(Za.), 1K((Za)),.))
(33)
1 2S.
(34)
Where (33) is by triangle inequality and |6r S 1. From (Beygelzimer et al., 2011, Theorem 1), we could apply Freedman's ss inequality to obtain the following result,
Lemma (Lee el al., 2024, Lemma 3). Let ...... Z be martingale difference sequence satisfying max, |7+1 S R a.s., and let F, be the a-fiedd generated by Zi..., .., Zr. Then for any (0, 1) and any 1i E [0, L/B), the the following holds with probability least a:
Zr s (e - 2)n Σ 1IZ
log a
1
Thus, for E [0, 28 to be chosen later, by invoking Lemma for the martingale difference sequence Zi.... Zz, the following holds with probability at least a. 2
1
(t) (c 2)n Σ 3l112..)T8.)f((2.).eee. -0,)
log
(35)
Lower Bounding (t). From the standard result in information geometry (Amari, 2016; Brekelmans et al., 2020), we have the following result:
Lemma 2. (Lee et al., 2024, Lemma 4). Let m(2) == log(1 + ) be the log-partition function for the Bernoulli distribution and g(2) Ts Then, we have that
KL (Ber Bern(g((2))) = Dm 22),
where Dm (21, 22) is the Bregman Divergence defined as (m, =2)= = = m(=)(21 - 2) dz.
Notice that
(m1, // (>=)(21 - -2) de 1 (log(1 +c²) =) 1/ 0(z)(21 22.
(2)
(36)
Thus, we have the following lower bound on (2(t),
(a(t) = Σ KL (L Bern(g(z1)))
(37)
Σ Dm
(38)
/ ((a))) 2) dz
[(Za.)
Σ
(39)
1l20))10
17

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
((...))..-01)) f.u- (1- f (1- + (1- v)).) du
(40)
(f(Za.),0.-) -0,, -0,)² ((((2a,)TO))
(41)
2+ 1f(Za, (T( 0,)l
(I(Za,).0. - -0,² ((f(Za.)
IV
(42)
2$
Where (37) follows by definition of <2: (38) uses Lemma 2; (39) uses (36); (40) follows by change of variables; (41) follows by Lemma 6; and (42) follows by Assumptions 1 and 2.
Upper Bounding (t (Lee al., 2024, Theorem 2). From (Foster al., 2018, Theorem 3), there exists an (improper
learning) algorithm for online logistic regression with the following regret:
(t S 10n log (e+
St 2n
(43)
Though our selected decisions are more conservative than those of (Lee et al., 2024) (we add penalty term when selecting decisions to account for constraint violations), the estimation method to obtain fg (i.e., MLE) and the way to compute the optimistic estimate O, (i.e., 0, arg mäXegc, maxde 9([(Z))TO) are the same as (Lee et al., 2024). See more justifications for using the improper learning algorithm in (Lee et al., 2024, Appendix B.2).
Combining Equation (29), (35), (42), and (43),
(0) (..) (t() -x((t) + (t())
$ (e- - 2)n Σ 3lF((u. 0.)²
1
log +
(f(Za)). 0_ -0,22
((S(Za,) TT.)
1 a
2 25
+ 10n log (e+
St
2n
St
1
< 10n log(
+ +) + 2((e 22) + S) log
(44)
2n
Where (44) follows by 17 2(e-2)+25
<
1 which finishes the proof.
E. Logistic Error Upper Bound
In this section, we provide the proof' for error in mean reward from an action de based on optimistic 0, instead of 8*. Some of the details follow from (Faury et al., 2020, Appendix B) and (Abeille et al., 2021, Appendix C).
Riog Σ
E (do(d)), Wi: mi] B[Y [do(d)), we, mi]
T
-
(45)
T
T +
(( ((w)([(Za)) u) du
[o(((Za)TO.) ((2a)) -0)
((2,)To.
(46)
term (a)
term (b)
where the (45) comes from the expected reward in (2); the (46) is by performing the Taylor Series Expansion of on Té, with a first order integral remainder. Then we rewrite the logistic regret Rlog as term (a) and term (b), where,
T
term (a)
Σ
(.. 0.) -0.)
18

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
T
term (b) = Σ
[
(())(f(Za))T, - -u) du
t=1
We separately upper bound both terms. Firstly, we prove the following Lemma (Lee et al., 2024, Lemma 6) used throughout this section.
Lemma 3. With d = 15-(2425) " ((2-2) and & = for any E C.(a),, the following holds with probability at
least 1 - az
||0 0.1171.00.) S s)(a)²
where = 25) B:(a)3 2(2 (5) - 2) =/ + log bSt n
+ ( (45 + -)6r) + +1)n| 2.
Proof. By Proposition have that with probability least a, Lo.) (..)) Bc(aa) assume this event is true throughout this proof. Then,
(0) (.(0.) VL. 0.) / -0)00 + =0))-0))) 0.)de
(47)
C,(0.) (2.0)) 0.) + +1 0. 0.I1,.(000))-x111
(48)
L.(0.)++ (Z.0))) 10 0. O.I... - Ae110 - 0.112
Where (47) is by the second-order Taylor expansion of (.))) around 0.; (48) comes from Jn v) 21 v 0.) (.))dr = v) 1
+ v(0 -..)) (Za, ( ( ) du = G,, - XeIn-
As for the relationship between G,(0, 0.) (19) and H.)0.) (18), we have the following result:
1-1
G,(0,0.)
Σ
(1 v)g s(za, ((a,) - -01) du s(Za,) ) S(Za,) + Aehn
1-1
2
f(Za,) f(Za,) + A.T
(49)
+ If( T(Za.)
1=1
Σ à (f(Za.)
AeIn
(50)
2 28
H,(0.).
2+ 2S
Where (49) follows by Lemma 6; (50) follows by Assumptions I and 2. Thus, we have that,
||0 1..1l1,,
- (2+ 25) 0x 122,,
(51)
(2+28) - L.(0.) VC,(0.)T(O 0) xel00 02112) S (2 (2+22)(C.(0)) - L.((.) + VL.( 0) + Arl 0.1 s (2 + (5))((((()))) + +2 VL. 0) +1.
(52)
(53)
Where (51) is by semi-definite order monotonicity; (53) follows by X = TS*(2+25}* and (52) comes from 0,
arg min sollass (f). Since (,(a) / log( St 2n
+ e) + 2((e - 2) + 5) log 1 we then go to bound (B.) which is done via a new concentration-tyyn type argument. Let (2.5) be a dimensional ball of radius 25 and an arbitrary E B, (2S). Firstly,
V., Σ (o(f(Za,) - Σ (z,(Za)
19

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
As (za Tol < 28 and Bl(G. (1)),,) = =(0((2) TT) from (34) and (32), by Freedman's inequality (35), for any 1/ E [0, z the following holds:
+ + log - 2 1- a
P
Sil(,,)) (2) Σ "1.12,,))0,)((22,,)))))
"f
By (Vershynin, Corollary 4.2.13) and (Lee al., 2024, Appendix C.4.4) the following holds with probability at least 1 at
1
1
55
( - 2) (45n + ne=) + 1 eat.
(O. - 0) < (e- - 2)nl10. - -11 + - log + log
1) a
4
By (53), we finally have:
25 |10 - 0- (0.,)) 2 1 (2 22n [3((a)+ + log
1
1
n
log + ( (e--2) 2)
5S
(45 + mes) + +1)ead +
+
"
4
< 22 25) (c(aa) + +2(22 + 25) - 2)( log
1
+ log
5St
+
(e - 2)
(4St) + nes) + +1)mg
+ 2.
4
(54)
Where (54) follows by 17 2(c- (2)
<
28. 4 7. Which finishes the proof.
1
We start by examining term (a) and show the following upper bounds:
T
term (a)
((f((a))TO.) ((2
((Z 0.) -0))
(55)
(((Zz,)TO.) [ff(Za)lla, 0x 0.l1m.(0.)
(56)
T
g(f(Za,) [I((aa))l,, 1(0.) 7e(a)
(57)
I (a))
g(f(Za.) [lf(Za)) HI (00))
(58)
S (r(a)
T(..
3(F(Za)TO.) 111 (0.))
(59)
T
S (r(a)
Σ T(.(
||ell
(60)
x 2nr(a)
o(f(Za) V no (>r +
(61)
Where (56) and (59) is by the Cauchy-Schward inequality (Z.. To.) is non-negative); (57) comes from Lemma 3 and (58) is because rr(a)= = max Te(a);; in (60), we define vector u, = (T(f(Za,)TO.) f(Za,) and matrix V, Dr Ue of + deln, and obtain:
((((Z))TO.) [15(Z)))) (1(()))) (0.) =10 (l f(za))) ( = -1ueelfs
and (61) follows by Lemma 8.
20

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
We then take look at the first order of the logistic function ((S(Za)))) TO.) and derive upper bound for it by a first-order Taylor expansion:
T
((.( E TT..
((u) du
(62)
(l((Za)TT.)) + Σ [f 3 + (
Bi)) do) ((Zz) - -0.) (63)
=
t=1
(L) + Σ [ V=D
(1Z2 8))))d)
du 5 I(Za, - -6a)
(64)
T
[ 9 (1ZZ -0)) du) [(Za) -a)
Σ
)(f(Z)))
v=
(65)
T
Σ ((((Za)
Σ
5 (122))
du) ( ((0 0.)
+
v=0
1=1
(66)
T
1 (1122)60+0 0.)) do I(za)
((((Z))
Σ
(0. -0.))) (67)
Σ )(((Z.) + (T((2a))T.)) - ((12aa)0o.)
(68)
= Σ ((((Z.))To,) + Riog 1=1
(69)
S T + Riog.
(70)
Where (62) comes from the Taylor Expansion; (63) follows by changing variables; (64) is by taking the absolute value; (65) is because the optimistic estimate at step t, hence, fZaa, T 2 (Za,)TO, (67) follows by the cecoodnnced
property of logistic function [ف] 2 [ö] and و > O; and (68) is from the fundamental theorem of calculus; and (70) follows by T(f 1.
Therefore, by (61) and (70), we intermediately obtain the following upper bound on term (a):
term (a) < 2 n log (AT
T m) /T + Riog
s 27r(a) n log (Ar
n )
T
(VT+ / RROS).
(71)
where (71) is because /T + Riog S SV + Rlog for T > 0, Riog > 0.
In order to upper bound the logistic bandits regret Riog in (46), we still need upper bound term (b) that includes the second order of logistic function:
T
term (b)
=
Σ
(Z)))(Z - -u) du)
(72)
T
=
Σ
(1 (1- -r)r ((zz, + 1(Za,) (00--00)) 0.)) dr] (I(ZZ)) -0,)) 0.))
(73)
v==
T
(0. ²
(74)
2
21

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
2 [. (e.,), - 0.1121.0.)
(75)
2 (l.((Za)) (0.))
(76)
T
$ (()(
Σ
(Z, ) 117
(77)
T
< 2
(7) Kz Σ (Zaz)))lve
(78)
t=1
s 2n (a) Kz log (AT + m
(79)
Where (73) follows by changing variables; (74) is because ğ S 1; (75) follows by Cauchy-Schwart inequality; (76) comes from Lemma 3; (77) is by (a)) = max (a):: as for (78), we note that
t-1
H(().) = Σ 3 (F(z..)0O.) f(Za)) + dchn 7=1
s(Za,) /T A
(80)
1
Vi(O.).
KZ
I v Raz Vi (0.); and the last inequality (79) follows by Lemma 8. Then by the upper bounds on term (a) in (71) and term (b) in (79), we then finally upper bound the logistic bandits regret Riog in (46):
where (80) follows by Definition 1, thus,
Rlog- term (a) + term (b)
< 2yr (2) log (AT + ) (VT (R10)) + 2n (a) xz log (Xr + 7
This is second-order polynomial equation in / Rlog, by Lemma 5, we have
7) RRug & 2yr (a) log (xr + m) + VeTur(a)/ n log (>r + nt) + 2n 77((a) kz log (Xr + T)
))
Using (xr + y)² < 2x² + 2y²,, we obtain:
I Riog& < (a) log (xr + 1) + 4rr(a)) log Ar + 2) VT + 4 nz log (AT +
n
To further simplify the logistic bandits regret Riog. we write 7/ ((x) as:
(a = o(sy log (e + 2n
St
5St
= (5 log(t))
+ log
Therefore, as for the Ring, we obtain the following bounds:
4) + ( Riog & (m) log (Ar + n
(Ar I) I)VT + 4n) rez log (xr T n
n
o (nSSlo((T)VT + n = =²
n²
(81)
which finishes the proof.
22

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
F. Regret and Constraint Violations Upper Bounds
In this section, we provide proofs for upper bounds of both reward regret and constraint violations. Our proof' build on the greedy procedure in Algorithm 1 and standard convex optimization analysis.
F.I Proof of Theorem
We first prove the regret upper bound. Under Slater's constraint qualification in Assumption 3, we have the boundedness of the optimal dual solution by standard convex optimization analysis from (Beck, 2017, Theorem 8.42), where,
S vh (T",9([(Z))00.)) - (To (To.
8
the r.h.s. is because the logistic function is less than 1. Now, we turn establish bound over R+ + ΦV(T). Firstly,
(T) + +V(T)- =
Σ
(5 g -
((4 7)
(82)
t=1
T
- (11 - -T) (,("T, ( -
(83)
(fT' - or (AXx)) - (0(F(2))00)- (Xx)) (xxol- -T) +
term (1)
Σ
+ (14,,, -(U()))))))
-113a, (X.)) (x))
term (2)
Σ
(()), -x) 6e. (Xx) - -)]
(84)
term (3)
(ff.9((Z))TO))) - (T (xxr) 7)) - -(9(F(2))T6)) a. -)) +
term (1)
o(f(Za)T0.) - o(f(Zz))T.) + @ (X,a - .( (X,) (x) + VTp.
(85)
term (2)
where (83) holds since di and (T AA (Xt) - -) 1 0: (84) holds by adding and subtracting
(() Σr (d (X+) - r), Σn Ad. (Xi) - r): and (85) follows by upper bounding term (3)
from Lemma 4.
We are then going to bound term (1):
T
(x" (f7,g(((Z,))))) - -1 -)) - - -T))
term (1)
(x', o(((Z))TO)) 6. - (T" ((A.(()()))) -T) (1Ax(x)) - -T)) +
(M" (77.)(((Z T0.) c.. (x,((),)
-))) --)))>>>)) (Zaa )TO) + Φe (1 (X,) -
(86)
23

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
T
- + Σ Φe (m", ((Aa(x)))
Φe (x", (05,(1))))))))) - -T) - ((1aa(X) - -7))
(87)
t=1
- -)- -())(())) -))
(88)
S P Σ (x" ((,) - 7) ((Isa(x)) - -)))
(89)
= p. o log (T) + n² (log(())) + n2 (log(T)))
(90)
Where (86) follows by adding and subtracting terms; (87) comes from the greedy action de (see (13)) chosen at step in
Algorithm I; (88) comes from the optimistic estimate 0, (see (12)) in Algorithm 1; and (89) is because &e S pp as for the result in (90), we note that if (X,, 2 0 then (x(), 2 O, and by the counterfactual faimess effect (see (4)), we have,
(Aa(x))- 7) (14,(X,)) -) olf(Zz)T T() olf(Za) + olf(Zz)
S { - (Za)))))
(91)
where (91) follows by selecting optimistic reward parameter at every round (see (12)) in Algorithm I, thus f(Z)) S T8, On the another hand, if (X,) < 0 then Ax(X,) < 0,
(Aa((x)--) )
-)= = T( o(((ZaT + (((( - o((())))..) - -)
- -0(f()))8)))(((())T)))
(92)
Again, (92) follows by selecting optimistic reward parameter at every round (see (12)) in Algorithm 1, thus f(. <
f T0. Here, notice that, the factual feature Zd, and the counterfactual feature Z/a reside within the feature space 2, in which the boundness assumption (Assumption 1) and problem dependent constant (Definition 1) are defined by. Therefore, the logistic bandits regret of gff )0,) g(f(Za,)))) )0.) has the same asymptotic upper bound up to logarithmic factors as g(S(Zz,)0)) 0.)) s([(Z,,)))))))) )0.) (see (81)).
We further bound term (2). When ia(X)) 2
term (2)=
- -0((2a)) + +0 (1Aa,
-)) -7) (x)a (X:Il
+ (o( = Σ g(F(Za)To.) - ( - - - -
(93)
< Σ -(J((()))) + (o(o)))))((((((()) -
(94)
Where (93) follows by the counterfactual fairness effect (see (4)); and (94) follows by (12) in Algorithm
When ix())) O. we have that:
term (2) Σ
- -00T))))))))( + + (1Aa, -) - -
(X.Il -(A
= Σ - -T. -4 - - (001122)600-9((22u))
-
(95)
- +
(96)
24

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
Similarly with above, (95) follows by the counterfactual fairness effect (see (4)); and (96) follows by (12) in Algorithm
Since the logistic bandits regret of o(f(Za, (Z.)).) g(f has the same asymptotic upper bound up to logarithmic factors (Z )0.) (( )o.) (see discussions (90)), thus combining (94) and (96),
+ (log(T)) + 5 Kz (log(T))) term (2) v (1 + Φ) 0 (
(97)
Thus, by (90) and (97), the upper bound on R+ (T) + (T) for any & E [0, /] the following:
(log (+ = (1+ (1) S (z20(())))) (n
+
p p (=O0nlog(T))TT n (log(T)) n² x² + O(vTT).
Regret R+ By setting o = then we obtain the upper bounds on the total regret guarantee with high probability:
(T) = (o + 1) = s² (log(T))²) ((vVT)
o ( +
+ pVT)
(98)
+ S kz) + + PVT).
(99)
where (98) is because the truncated parameter p 2 2/6; and (99) is write the regret upper bound in logarithmic asymptotic notation.
Constraint violations. Next, to obtain bound on V(T)), we employ tools from constrained convex optimization. First, we define probability distribution Ti by
(T', or.. ((f( and (za)) 7) |0d, (Xx)) -T, T,
Thus, we could rewrite (T) + (V( in (82) as:
(T) + (V Σ (T" (m".g(ff g(f((Z) - (F. +1A((( m)
(100)
Then we apply the following theorem from Theorem 3.60 in (Beck, 2017).
Theorem Consider the following convex constrained problem f(TT) = max {f(m) g(T) S 0}, where both f and 9 are convex over the convex set II in a vector space. Suppose f finite and there exists a slater point To such that g(mo)= S -5, and constant p 2 26. where &. is the optimal dual variable, i.e,, th argmin (max, [(x) (g(())) Assume that x' 11 satisfies
- -(x)) plg(T))1 S
for some 0, then we have 19( < 2t D.
Since ΣT ( T(. is convex over {m Et ( Te.)) and ET (Aa())) 7) are convex
over t=/1= Then (100) satisfies the conditions in Theorem 3 and we have that:
T
V(T) = Σ (Xi)1 1=1
( (nSSlo(T)VTT- n²
S (log(T)) +n2 n² (log(())) + vT)
(101)
ö(nSVT + n² 5" kz + VT).
(102)
Where (101) follows by & E p) and 1/p //= 1: and (102) writes the bound up to polylogarithmic factors.
25

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
Lemma 4. Under the dual update of th in Algorithm 1, we have the following for any & E [O.
T Σ
T
( (d
1 -
(01- -
-0)++
+
Σ
(1)Aa 4 (Xx)l - --)?
2n
[=1
t=1
Proof. By the dual update of de in Algorithm
(6t+1 -)²² = (Ø: + (1 (Xx) - -T) - -))²
1
(103)
1
(ò: x)² + ( (1Suh (X+)l - +)) 2((r - - Rd. (Xx)) - -])
(104)
11
2 (Øt 2)( (xi) - 7) + (1 (Xi) - -))²
= (6: 3)² + r
(105)
17
Where (103) follows by (14); both (104) and (105) write the technical terms. Summing over T steps and multiplying both sides by 2:
T
T
T
T
2 (de+1 0)²² =
1
0e
6)²
+
Σ
(or
()
- 7)+ +
Σ
(1) (1 (X+) - 7))
(106)
2
2n
1=1
Therefore:
T
T 1
( (0)(((a. -)) = Σ
7 2
(ot - x)2²
(di+) x)² + Σ
(().d d, (x.) 7))
(107)
2
21j
1=1
1=1
t=1
(01 3)² N/4
1
(OT+) 6) + Σ 21
(15 (Xx) - 7))²
(108)
T
$
1 (01 6)² +
Σ
1
(1 de (Xt)) - -))²
(109)
21)
1=1
VT 8²
PVT
(113a, (Xi) -))
(110)
2p
2
VTP
PVT
(111)
2
2
O()Tp).
Where (107) follows by (106); (108) comes from telescopic sum; (109) is because 4(0T+1 +)² > 0; (110) follows by
61 = 0 and 77 = VT initialzzed in Algorithm 1; and (111) is because [نa (X,)) E [0, 1]. o E pl. and 0 S T S 1.
F.2. Proof of Proposition 3
Proposition 3 states the relationship between policy n. and म. for the regret upper bounds, we provide a proof in the following.
Proposition 3. Let policies nt and ग5 be the optimal solution for constrained problem max, (( ((f( (,. (x(x))) - T) s 0} and max+ ((T,
(x,,Ax((,) - T + c) S 0), we have,
T
o(( s ET
(TT (T,o(((Z)))())
8
Proof. The policies nt" and n. are defined as:
xx = *
max((TT (uex(((T,(((Z2,TTO)) (r. s 00
26

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
- (ax(((
(T. 53.
Let one policy ne = (1 )) + To. where mg the policy satisfies the Slater's constrained qualification, i.e.,
(To, [a(),) -T) - -à V E [2]. Note that
(Te)l - (1 -1- - IA(x) - r) + (mo. (aallaa()) 7) 0+ 8 (-0)) 1 -c
Therefore, ne feasible solution of the baseline problem (Te.)(((Za))O.) (T.. (xx())) T + t) s 0. Thus,
n ((((())))0.))
Σ
The Tl.
T
Tt' .9.9( off Σ
Tee ((f(a)
(112)
(T" (m( - -11 (5 , (f(( of
(113)
Σ { (1 (f (mo: g (f(
eT 5
(114)
Where (112) follows by that π. is the optimal solution while π. is a feasible solution to ( ((f( (Te, Aa(X)) +e) e) & 0; (113) is from (1 )x + Too and (1 14) comes from g(f((z) E j0,
Algorithm 2 c CCLB Algorithm
Input: Horizon T, truncated interval p. step size 1) = vT/p, and the initial dual value Φ1 O, user-select parameter
< 80.
2: for = =0==,, 1,2,3..... T do
3: The learner observes the contextual information X, = {ac, Wh, m
4: Update the estimated reward parameter Ó,.
5: Build confidence set (ox) from (11).
C.(a) = -00 B(())
(115)
6: Greedy procedure. Choose the optimistic reward parameter and select the greedy action:
0, arg m g(f((a)
(116)
dj arg max g(f(Za) 6: (()()))))) deD
(117)
7: Update the dual variable:
Φ++1 Proj 1ipr) [de + 1/v(I - + -X
s)]
(118)
8: Received random reward J6+1-
9: end for
F.3. Proof of Theorem 2
In this section, we establish upper bounds on both regret and constraint violation for the revised constraint condition (see Algorithm 2). This is achieved by introducing a slackness variable e, which serves to tighten the constraint. First, we decompose R$ (T) + ΦV (T) as follows, where (T) = ΣT1 a (X.) - E.
+V))+ = Σ ( ((( g(S(2a.) + (X.)) +e]
(119)
27

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
- +)
-z))) - ( -) - -(((2a)TT.) + -x+
term (I-e)
- + Φ (1Idd, (Xx) - (xx))())))()
term (2-t)
Σ (X,] - - - (X:)
- -
(120)
term (3-E)
Where (119) holds since Φ; 2 0 and (T" (X.)l + <) S 0; and (120) follows by adding and subtracting technical terms. Similar the techniques Section F.1, we can upper bound term (1-e), term (2-r), term (3-c) according to (90), (97),
and Lemma 4 following:
term (I-e) = Eoe o(fia((())))))) - 11k - - + c) -((f(())) + (x - T + +c]
p. = @ log nS
+ ( n2 ks (log (T))
T
term (2-e) = Σ (1((2 - + /6 (1 (Xi) (Xi) - + c) (x)I
1=1
(1+ d) (1+ 2 5 (z(o((()))
T
term (3-e)
Σ
- -
O(p(1 (e((1+))VVT)
Thus, we have R++()))) + (TT = (p+ Φ)
Regret R$ (T). By setting Φ = 0, we have:
R4 (T) = ( (nns x
(mmSVT m² kz + PV + +
Constraint violations. By applying (Beck, 2017, Theorem 3.60), we have VTTT) = to obtain bound V(T),, notice that:
V(T) = VT()) - Σe= Ö(nSVT+ + -T+
Which finishes the proof.
E.4. Proof of Proposition
(VT
Proposition By conditions stated in Theorem 2, for the user-selected parameter
VT 4CT(VT Cinlog(T) + (C2 + (2 v1/T) /2Ca 1, where C₁, C2, Ca, Ca are the universal con-
28

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
stants independent of n, S. T, Kiz, if 2 and e' < 6, then one could achieve zero upper bound the constraint violations when select E ())
Proof. To show the result in cumulative zero constraint violations, we write it as the following where C1, C2, C3, Ca are the kiz, universal constants which independent of n, Kiz and E (0,
V(T) < CinS log()))T Can (log( + CaKz n² we solve it when the right- side is less than 0:
T - 2C4VT V - 2C. 4C4VTT
T T-204 2CvV + (T <
(T-22c.vTT 2C 4CAVTI
2CAVT
2C
where r CanSSSSloge (T) + C2n2 S2n2222 ((lg( + CzKz n² 5 +CTT)) CvVT. First, The upper bound of have the following inequality:
VT
T 2C2VV + VT -CCVV) 4CvTT
5 <
(121)
2C4
2CIVT
Where (121) is because C = p while T the lower bound f,
>
(typically we choose p < 100 for the numerical experiments). Now we look at
2CaVT V (T- (C-22CTV)2222 é
+ CzKz n² ( + +CVTTT
2C4VT
T T-2CIVT T 1T-4c, 4c, TVV CCnSoogTT + + Cskz ((((()(()((()
2C4vT
VT T 4c, (GnSoog))) (C2 + (2rg))
2C4
If the lower bound e' is less than the Slater's constant, then when the learner choose E [e', we could achieve zero cumulative constraint violations.
G. Technical Lemmas
Lemma ((Abeille et al., 2021) Lemma 7). Let be Rt, and R. The following implication holds:
w² bu buutc = u uSb+ b Vc.
Lemma 6 ((Abellee et al., 2021) Lemma 8). Let be a strictly increasing function such that [ S (g), and let 2 be any bounded interval R.. RR. Then, for all 21, 22 E Z:
[ (1- (1-v)a(21 + e022 - -z1) do 2 + 121 22
9(2)
Lemma (Abeille et al., 2021) Lemma 11), Let {ur be a sequence IR" such that ||u/|| < B for all 5 E N, and let A be non-negative scalar. Fort t 2 1 define V = > ue ut + -dnn The following inequality holds:
tr (r((V))
< (A+ (t 1)B²
det(V)) <
TI
Lemma (Abeillee et al., 2021) Lemma 12). Let {ur 1 be sequence in TR. such that || |l & B all E N. Further
let {Ar 10 be an non-decreasing sequence in Rt s.t. \ = 1. Fort 2 1 define V, = Et=l u. + X,In- Then:
|u 1p. S 2n(1 + BT) log (AT + TB²
29

---

Causal Logistic Bandits with Counterfactual Fairness Constraint
H. Additional Experiments
this section, we provide additional evaluations for the e-CCLB and CCLB algorithms when selecting different tightness parameter e (Figure 4) and counterfactual fairness threshold 7 (Figure 5), respectively.
Figure 4. Increasing the user-chosen tightness parameter c, the cumulative regret increases well, but the cumulative constraint violations decreases (the learner becomes more conservative). When we pick the equals (both are 0.16), we observe that incurs high cumulative constraint violations (Figure 4 (b)) since (x", |xx(X.) + + 0 therefore there does not exist feasible decisions (notice that < S)
Figure 5. As the counterfactual fairness threshold J increases, the feasible region is larger (more of the actions are feasible), which means the fixed comparator could be better but at the same time easier to avoid violating constraints (since more actions are feasible the first place when [D] is fixed), thus reduce the cumulative constraint violations (see Figure 5 (b), the cumulative constraint violations are nearly 0 when every round. The dual variable de will increase as well, which renders the learner penalizes fairness constraint (thus more conservative), therefore decrease the cumulative constraint violations (see Figure (b), the cumulative constraint violations are relative small when T 0.06).
0.86). On the other hand, when is small, i.e., A (X,)l almost the counterfactual
1750
eps=0
Cumulative constraimt violations
eps=0
1500
eps=0.05
eps-0.05
Penalized cumulative regret
3000
eps-0.05
Cumulative regret
ops-0.1
ops-0.1
ops-0.1
1250
eps=0.16
2500
eps=0.16
1000
2000
750
1500
500
1000
100
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Horizon
Horizon
Horizon
(a)
(b)
Figure 4: Plots for the e-CCLB (r=0.16) algorithm when selecting different on (a) cumulative regret; (b) cumulative constraint violations; (c) penalized cumulative regret.
150
tau-0.16
tau=0.06
Cumulative constraint violations
250
tau=0.06
Penalized curuulative regret
1400
1200
tau=0.16
Cumulative regret
200
tau=0.46
tau-0.46
tau-0,86
tau-0.80
1000
tau=0.86
100
350
800
75
50
400
0
2000
4000
2000
4000
6000
10000
Harizon
Horizon
Hortzon
(b)
Figure 5: Plots for CCLB algorithm when selecting different counterfactual fairness threshold on (a) Cumulative regret; (b) Cumulative constraint violations; (c) Penalized cumulative regret.
30


Reviews:
[{"review_id": "QHvlCK1fZz", "reviewer": "Reviewer_Ye1T", "summary": "The paper introduces a new problem formulation: Constrained Causal Logistic Bandits (CCLB), which addresses online decision-making under counterfactual farness constraints. This paper proposes an algorithm utilizing primal-dual optimization for constrained causal logistic bandits with non-linear constraints and priori unknown. Further, they propose the regret bound $\\mathcal{R}_+(T)$ as well as the fairness constraint violation bound $\\mathcal{V}(T)$ in section 3.3. In section 3.4, the paper further shows the fairnes constraint bound could be further improved by introducing tightness variable $\\epsilon$ in the dual update.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your time and feedback. Below, we address the main comments provided in the review.\n\n### _**Weaknesses**_ \n\n> _1. My primary concern is the lack of empirical validation._\n\nWe will add empirical results using a synthetic dataset, evaluating both cumulative regret and constraint violations over multiple horizons. See the discussion for Reviewer y2yQ’s comments (Weakness 1) for the empirical results and discussion.\n\n> _2. Another concern is the assumption on the causal graph, without unobserved confounders, the problem might not be generalize in real-world systems where unobserved confounders are usually expected._\n\nCounterfactual fairness is an important fairness criterion. Since we cannot actually intervene on the sensitive attribute (race, gender, etc.), instead we must estimate hypothetical interventions from the data we collect. In general, in the presence of unobserved confounders (i.e. if W is not/partly observed), counterfactuals might not be identifiable. To be clear, it is not simply a limitation of our method or analyses, but a more fundamental challenge regarding counterfactuals and causality more broadly. \n\nFor problems with unobserved confounders, there is active research on bounding counterfactual queries, such as [1]. An important future direction is to extend our method to work with those.   Thus, even for the broader family of problems that have unobserved confounders, we view our current work as an important step. \n\n[1]. Junzhe Zhang, Jin Tian, and Elias Bareinboim. Partial counterfactual identification from observational and experimental data. In International Conference on Machine Learning, pages 26548–26558. PMLR, 2022.\n\n### _**Comments or Suggestions**_\n\n> _1. Readers need to guess how $Z$ is related to other variable like $A ,W, M, X $._\n\nThank you for pointing this out. We will revise Figure 1's caption to be: \n\nExtended Standard Fairness Model (SFM).  $A$ denotes the sensitive attribute, $W$ is a set of confounded features, $M$ is a set of intermediate features, $D$ is the decision, and $Y$ is the outcome. Let $X=(W,M,A)$ denote contextual information the learner has available to make the decision, and let $Z=(W,M,A,D)$ denote variables the reward distribution may depend on. In the main text we will also define $ Z_t$ in terms of its components $Z_t=(w_t, m_t, a_t,d_t)$.\n\n### _**Questions**_\n\n> _1. Can you introduce more about the tightness variable $\\epsilon$. To be specific, why this variable could help improve the constraint violation bound intuitively?_\n\nWe will revise the text in Section 3.4 line 404 to include more intuition for how $\\epsilon>0$ improves the constraint bound: \n\n\"... same asymptotic order of regret as before. Intuitively, with a  tightness variable $\\epsilon>0$ in the constraint, the learner will be more cautious in selecting actions by effectively working with a stricter constraint (e.g. with fairness threshold $\\tau-\\epsilon$ instead of $\\tau$). Then, under this new hypothetical ...\"\n\n> _2. Is it possible to extend this model to handling distribution shift over time?_\n\nThat is a good question. \n\nFor MAB problems without constraints, there is work on black-box adaptations to convert stationary MAB methods to non-stationary ones. One well known method is “Non-stationary Reinforcement Learning without Prior Knowledge: an Optimal Black-box Approach”, however as recently pointed out in “Is Prior-Free Black-Box Non-Stationary Reinforcement Learning Feasible?”, the former one is not order optimal in some settings. The authors of the latter paper recently proposed a blackbox method to convert algorithms from stationary MAB to piece-wise stationary MAB “Detection Is All You Need: A Feasible Optimal Prior-Free Black-Box Approach For Piecewise Stationary Bandits”. Since they do not consider long-term constraint so we cannot apply their method directly, but it is a promising direction to explore.\n\nAn alternative route is to specially adapt a method, for which there are several results without long term constraints, e.g., ”Revisiting weighted strategy for non-stationary parametric bandits” and some results with constraints, e.g., ”Non-stationary bandits with knapsacks”. Both of these two works propose interesting methods which might help us extend our current model to non-stationary environment. The former one analyzes non-stationarity in logistic bandits using a weighted strategy and the latter one studied knapsack (long-term) constraints in an nonstationary environment using sliding-window strategy.", "claims_and_evidence": "The paper claims to propose an algorithm in solving CCLB, and provide the theoretical bound on it. The claims is supported by math proofs.", "methods_and_evaluation_criteria": "N.A.", "theoretical_claims": "The proofs are correct.", "experimental_designs_or_analyses": "N.A.", "relation_to_broader_scientific_literature": "The paper proposes a constrained causal logistic bandits (CCLB). The fomulation and online setting is interesting both theoretically and meaningful for the real-world applications.", "essential_references_not_discussed": "I am not aware of any such references that should have discussed.", "other_strengths_and_weaknesses": "## Strengths\nThe paper is well written and easy to follow. The proposed methods and theoretical bound is solid. Theoretical contribution is new and creative.\n\n## Weaknesses\nMy primary concern is the lack of empirical validation. Though this paper is purely theoretical, simulation on synthetic or semi-synthetic dataset is expected. For instance, the comparison on the unfair counterpart as well as the convergence behaviour would significanly strength the paper claims. \n\nAnother concern is the assumption on the causal graph, without unobserved confounders, the problem might not be generalize in real-world systems where unobserved confounders are usually expected.", "other_comments_or_suggestions": "While the paper is generally well written, I have one suggestion. In the graph, there does not have $Z$ as a causal variable, but you directly introduce $Z$ in page 4. Readers need to guess how $Z$ is related to other variable like $A,W,M,X$.", "questions_for_authors": "Can you introduce more about the tightness variable $\\epsilon$. To be specific, why this variable could help improve the constraint violation bound intuitively?\n\nIs it possible to extend this model to handling distribution shift over time? Especially in online MAB type of algorithm, the distribution might change over time.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DSbDHSMy0Y", "reviewer": "Reviewer_Qhcc", "summary": "This paper forwards an online decision-making framework constrained using counterfactual fairness constraints. The paper considers a sequential decision-making setup where a set of applicants arrive at each time step. The goal is to make labeling decisions that maximize the cumulative outcome reward associated with decisions across all time steps while minimizing the cumulative fairness violations of the decisions. The fairness criterion that the paper focuses on is counterfactual fairness which quantifies bias/unfairness of any set of decisions as the change in expected outcome reward when the protected attribute takes a counterfactual value. \n\nFor this constrained setup, the paper formulates an online learning algorithm that employs the primal-dual paradigm. They obtain sublinear guarantees in the horizon for the cumulative reward regret and for the cumulative constraint violations using this method.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your detailed and constructive suggestions on our submission. We address the main comments provided as following.\n\n### _**Claims and Evidence**_\n\n> _1. Intuitively, if I understand correctly, the larger the $\\delta$ value the easier it likely is to find a \"fair\" policy, and the smaller will be the reward regret._\n\nThat is correct, $\\delta\\in(0,\\tau)$ means there are strictly feasible actions, whose counterfactual fairness for that context is strictly smaller than the threshold $\\tau$. The larger of a margin $\\delta>0$ for a problem, intuitively the easier it will be to identify some fair actions (though they could have low rewards).  \n\nWe note that larger $\\delta$  only reduces regret bounds (e.g. only simplifies learning) to a certain extent. Even with large $\\delta$, the best fair actions (in terms of expected reward) could still be on the boundary (i.e. for many contexts $X_t$, we could have the optimal action satisfy $|\\Delta(d_t^*,X_t)|=\\tau$). Regarding how larger $\\delta$  manifests in improving regret bounds, for binary rewards, we have fairness thresholds $\\tau\\in (0,1)$ (since counterfactual fairness violations are absolute differences of expected rewards, which are binary valued), so $\\delta < \\tau < 1$, so larger $\\delta$ only shrinks the minimum $\\rho$ in the regret bounds towards a factor of $2$ (i.e. not towards $0$).  \n\n> _2. substituting $\\epsilon$ by the upper bound of $\\delta / 2$ leads to a direct proportional dependence of regret on $\\delta$, which doesn't seem right._ \n\nSorry for the confusion regarding those terms and the discussion on the regret formula. Larger $\\epsilon$ means the learner is increasingly cautious, effectively working with a stricter fairness constraint $|\\Delta(d,X)|\\leq \\tau-\\epsilon$. Large $\\delta\\in(0,1]$ means there is more cautiousness possible (bigger range for $\\epsilon$). The more cautious the learner is (larger $\\epsilon$) the more the learner might miss out (in a worst-case) on higher reward actions among the larger (in $\\delta$) set of fair actions.  \n\nAfter Theorem 2, we will add an extra remark before the  current Remark 4 to clarify this point:\n\n_Remark 4. The difference in regret bounds between Theorem 2 with an user chosen $\\epsilon\\in [0,\\delta / 2]$ and Theorem 1 is $\\rho \\sqrt{T} (2\\epsilon + \\epsilon^2)$. For a problem-dependent (fixed) Slater's constraint qualification constant $\\delta>0$, increasing $\\epsilon$ only worsens the regret bound, as the learner is increasingly cautious (increasing in $\\epsilon$), selecting from a smaller set of actions than the learner would have with $\\epsilon=0$. If $\\delta$ is large, $\\rho$ shrinks towards 2 and so for a fixed tightness $\\epsilon$ the regret bound reduces.  Larger $\\delta$ also allow for a bigger range of $\\epsilon$ and thus more room for caution (and regret)._    \n\n### _**Questions**_\n\n> _1. How does the regret bound in Theorem 2 change with $\\delta$?_\n\nSee Claims and Evidence 1 (above).\n\n> _2. Does the sensitive attribute intervention in the counterfactual fairness metric only change the sensitive attribute value (keeping everything else unchanged)? If so, is that realistic in the applications relevant to this paper?_\n\nThe (hypothetical) intervention $do(a_{t}^{\\prime})$ on the sensitive attribute does change the distribution of other variables as well, namely descendants of $A$ in the structural causal model. The structural causal models for the intermediate features $M$, outcome $Y$, and potentially confounders $W$, depend on the sensitive attribute value, so as the sensitive attribute  that is intervened on their (estimated and exact) conditional distributions change. \n\nFor example, in our synthetic dataset experiment (see the discussion for Reviewer y2yQ's comments for the results and discussion), \nwe create a structural causal model (including exogenous variables, endogenous variables, and structural causal equations), \nwhere the causal relationships are described by the extended standard fairness model, more specifically, for the causal mechanism between the sensitive attribute $A$ (binary), the intermediate variable $M$, and the confounded variable $W$ is represented as:\n\\begin{align} \n    M &\\leftarrow  \\mathcal{N}(0, |W| / 2 + |U_{M}| / 3 )\\ \\text{if } A = 1; \n\\end{align} \n\\begin{align}\nM &\\leftarrow  \\mathcal{N}(0, |W| / 3 + |U_{M}| / 2 )\\ \\text{if } A = 0,\n\\end{align}\n\nwhere $U_{M}$ is the exogenous feature for $M$, $\\mathcal{N}$ is the norm distribution.", "claims_and_evidence": "Overall, the paper provides a useful framework for fair sequential decision-making that can maximize cumulative reward while minimizing counterfactual violations, with provable guarantees. Despite the rigidity of online decision-making setups, the algorithm proposed to solve the constrained problem does seem to be practical. The main claim of sublinear reward regret and sublinear cumulative constraint violation in Theorem 1 looks correct. \n\nHowever, the claims made regarding the follow-up improved regret bounds in Section 3.4 are a bit unclear to me. In particular, the paper introduces a tightness parameter for the fairness constraint $\\epsilon$ whose value can be set in a manner that allows one to upper bound the cumulative constraint violations by zero. However, this comes with tradeoffs in reward regret. The third term in the regret bound has an additional dependence on $\\delta$ which could use some more explanation.\n\nSpecifically, $\\delta$ (as defined in Assumption 3) is based on the assumption there exists a policy that achieves  \"negative\" expected constraint violations. Intuitively, if I understand correctly, the larger the $\\delta$ value the easier it likely is to find a \"fair\" policy, and the smaller will be the reward regret. So the inverse dependence on $\\delta$ in Theorem 1 makes sense. However, the opposite seems to be true in Theorem 2, where substituting $\\epsilon$ by the upper bound of $\\delta/2$ leads to a direct proportional dependence of regret on $\\delta$, which doesn't seem right. Would be good to know if I am missing something here or whether this relationship between regret and $\\delta$ is to be expected for the case of zero-bounded constraint violation setting.", "methods_and_evaluation_criteria": "The methodology used to solve the constrained bandit problem makes sense.\n\nRegarding the chosen fairness criteria, the assumptions on the counterfactuals can be further expanded. The authors define \n$\\mathbf{Z}_t$ as the feature set at time $t$. \n\nAnd $\\mathbf{Z}_{a'_t}$ is used to denote the counterfactual feature set. The paper claims that both are in the feature space $\\mathcal{Z}$, but it doesn't specify the impact of the sensitive attribute intervention on other features.\n\nIn particular, does the intervention imply that only the sensitive attribute changes in the counterfactual without any changes to the other attributes in the feature set (or their underlying distribution)? If so, that doesn't seem realistic about how sensitive attributes work in real-world settings. For instance, gender influences other intermediate features used for making the final decision, e.g., \"soft skills\" or \"prior experience\" in interview settings. An appropriate counterfactual with respect to gender should ideally track (stochastically) the changes in the distributions of other related features as well.", "theoretical_claims": "Theoretical claims seem mostly correct. I am curious about the $\\delta$ dependence in Theorem 2 which I have noted above.", "experimental_designs_or_analyses": "No experimental analyses.", "relation_to_broader_scientific_literature": "The paper contributes to the broad literature on algorithmic fairness methods, especially targeting the setting of online decision-making. With regard to fairness, the paper chooses to focus on causal formulations of fairness to identify and tackle causal relationships between sensitive attributes and decisions that can potentially lead to discriminatory outcomes.", "essential_references_not_discussed": "All main references are discussed.", "other_strengths_and_weaknesses": "Overall, the paper is well-written. Theoretical claims are sufficiently explained and discussed without an overreliance on technical details. I also appreciated the inclusion of Remarks 3 and 4 as they help flesh out the implications of the performance guarantees and their relation to bounds established in prior related works. \nAs a mostly theoretical paper, the authors do a good job of grounding the results in the context of the problem statement and providing intuitive explanations for their theorems and propositions.", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "I have noted the questions on the two points I discussed above.\n\n1. How does the regret bound in Theorem 2 change with $\\delta$?\n2. Does the sensitive attribute intervention in the counterfactual fairness metric only change the sensitive attribute value (keeping everything else unchanged)? If so, is that realistic in the applications relevant to this paper?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dt0tmv3saP", "reviewer": "Reviewer_4qVC", "summary": "This paper studies the problem of imposing counterfactual fairness constraints in causal logistic bandit problems. The authors propose an algorithm that leverages primal-dual optimization for constrained causal logistic bandits, where the non-linear constraints are a priori unknown and must be learned over time. The authors theoretically demonstrate that their algorithm achieves sublinear regret and constraint violations. Notably, they also provide a user-chosen parameter to control the trade-off between regret and the degree of constraint violation (fairness).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your time and feedback. Below, we address the main comments provided in the review.\n\n### _**Weaknesses**_\n\n> _1. The paper could benefit from extensive numerical studies._\n\nWe have done some empirical experiments using a synthetic dataset, evaluating both cumulative regret and constraint violations over multiple horizons.  See the discussion for Reviewer y2yQ's comments (Weakness 1) for the results and discussion.\n\n### _**Questions**_\n\n>  _1. Could you please explain the limitations of proposed algorithm?_\n\nThere are a few limitations of our proposed algorithm\n- Unobserved confounding: We assume that there are no unobserved confounders for the outcome $Y$ (i.e. we observe (possibly multi-variate) context features $W$ and intermediate features $M$).  See the discussion with Reviewer Ye1T for Weakness 2 regarding possible future extensions for settings with unobserved confounders.\n- Stationarity:  See the discussion with Reviewer Ye1T for Question 2 for discussion about extending to non-stationary environments.\n- Budget constraints: Another direction for improvement is to also consider global resource constraints, where different actions may incur different costs and there is a total budget the learner must adhere to.\n\n> _2. Could you provide details on how_ $ \\Delta(d, X_{t}) $ _can be estimated in practice?_\n\nTo estimate $\\Delta(d, X_{t})$, at each round, we need to estimate the confidence set  $ C_{t} (\\alpha) $  of reward parameter and choose the optimistic parameter $\\theta_{t}^\\sim$ within the confidence set (see step 3 and step 4 in Algorithm 1 in line 279), in which has the highest expected reward for decision $d$. Specifically,\n    \\begin{align} \n        \\hat{\\Delta}(d, X_{t}) = g (f (Z_{t})^\\top \\theta_{t}^\\sim ) - g (f (Z_{a_{t}^{\\prime}})^\\top \\theta_{t}^\\sim ),\n    \\end{align} \n\nwhere $g$ is standard logistic function, $f (Z_{t})$ and $  f (Z_{a_{t}^{\\prime}}) $ are the factual and counterfactual feature vectors, specifically, $Z_{t} = (a_{t}, w_{t}, m_{t}, d_{t}), Z_{a_{t}^{\\prime}} = (a_{t}^{\\prime}, w_{t}^{\\prime}, m_{t}^{\\prime}, d_{t})$ ($m_{t} $ and $m_{t}^{\\prime}$ are the sampled intermediate feature from its distribution; $w_{t}^{\\prime}$ is also the sampled confounded feature from its counterfactual distribution; $a_{t}^{\\prime}$ is the counterfactual sensitive attribute), both $Z_{t}$ and $Z_{a_{t}^{\\prime}}$ are known for the learner.", "claims_and_evidence": "Claims made in the paper are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods make sense for solving the problem.", "theoretical_claims": "I didn't check the correctness of any proofs for theoretical claims in detail.", "experimental_designs_or_analyses": "There is no numerical experiments in this paper. The theoretical analyses are sound to me.", "relation_to_broader_scientific_literature": "This paper is closely related to literature on causal logistic bandit and counterfactual fairness.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n\n    1. The proposed algorithm is well-analyzed, and the authors provide rigorous theoretical analyses and performance guarantees.\n\n    2. The paper address the gap between incoperating CF constraint into causal logistic bandits.\n\nWeakness\n\n    1. The paper could benefit from extensive numerical studies.", "other_comments_or_suggestions": "The paper's contribution would be enhanced by including numerical experimentation that demonstrates the validity of the proposed algorithm and the sublinear regret and constraint violation guarantee.", "questions_for_authors": "1. Could you please explain the limitations of proposed algorithm?\n\n2 Could you provide details on how $\\Delta(d,X_t)$ can be estimated in practice?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lTydHyXNk5", "reviewer": "Reviewer_y2yQ", "summary": "This paper introduces a framework for causal logistic bandits with counterfactual fairness constraints, addressing sequential decision-making under fairness requirements and offering theoretical guarantees and practical algorithms for balancing performance and fairness.\n\n## update after rebuttal\nThe authors added experimental analysis of the proposed method. However, the baselines compared are a bit old. Even without experiments, I agree this is a good paper. As a result, I decided to keep my high score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful feedback. Below, we address the main comments provided in the review.\n\n### _**Claim and Evidence**_\n\n> _1. \"performance guarantee\" This paper has only theoretical effectiveness analysis, no experimental validation of performance._\n\nWe will add empirical results using a synthetic dataset, evaluating both cumulative regret and constraint violations over multiple horizons. See below for details.\n\n### _**Weaknesses**_\n\n> _1. The paper’s theoretical contributions are not supported by empirical results (e.g., simulations or real-world experiments)._\n\nWe will add experiments using a synthetic dataset.  Plots of the  empirical results (penalized cumulative regret, cumulative regret, and cumulative constraint violations) can be accessed through the following link:\n\nhttps://anonymous.4open.science/r/constrained-causal-logistic-bandits-EA00\n\n- **Data set description**  We use a synthetic structural causal model (modified from an example from [1], i.e.,\n\\begin{align}\n    A \\leftarrow U_{A},\n\\end{align}\n\\begin{align}\n    W \\leftarrow \\mathcal{N}(0, \\max ( |U_{W}|, |A| )),\n\\end{align}\n\\begin{align} \n    M \\leftarrow  \\mathcal{N}(0, |W| / 2 + |U_{M}| / 3 )\\ \\text{if } A = 1; M \\leftarrow  \\mathcal{N}(0, |W| / 3 + |U_{M}| / 2 )\\ \\text{if } A = 0,\n\\end{align} \n\\begin{align}\n   D_t \\leftarrow \\mathcal{N} (0, \\max (|W|, |M| )),\n\\end{align}\n\\begin{align}\n    Y \\leftarrow 1 (  U_{Y} + \\frac{1}{3}MD - \\frac{1}{5} W  > 0),\n\\end{align}\n\\begin{align}\n    U_{A} \\in \\{0,1 \\}, P(U_{A} =1) = 0.5; U_{W}, U_{M}, U_{Y} \\sim \\mathcal{N}(0,1),\n\\end{align}\n\n     where $A$ denotes the sensitive attribute (binary), $W$ is the confounded feature, $M$ represents intermediate feature, $\\mathcal{D}_t$ is the decision set, and $Y$ is the outcome. At every round, we generate a set of 20 random feature vectors that form the (time varying discrete) decision set, along with their corresponding counterfactual feature vectors.\n\n- **Baselines** We evaluate three different algorithms: GLM-UCB [1] (generalized linear bandits without constraint), OFULog-r [2] (logistic bandits without constraint), and CCLB (our method, causal logistic bandits with constraint, with a modified constraint set (see note below)). The code for \"Achieving counterfactual fairness for causal bandit\" is not publicly available.  We reached out to the authors requesting a copy of their code and followed up, but have not received it. \n\n-    **Metrics** We use cumulative regret, cumulative constraint violations, and a penalized form of cumulative regret, where if the learner chooses an unfair action, the learner observes the value (i.e. the learner can improve the reward parameter estimate $\\hat{\\theta}$) but we penalize the learner by counting the reward as being 0. In this way, constraint violations are allowed but are not profitable.\n\n-    **Results** Beginning with penalized cumulative regret, where rewards are only received for fair actions, there is a large gap between our method (CCLB) and the baselines, with the gap growing larger for longer horizons. Both baselines appear to have linear penalized cumulative regret across horizons used.  This is expected since the baselines do not account for constraints. Their cumulative constraint violations also appears to be linear.\n\n- **Confidence set** The confidence set $\\mathcal{C}_t(\\alpha)$ in Algorithm 1 is non-convex. We propose an additional variant of our algorithm using a convex confidence set (based on [2]), improving our algorithm's complexity though with slightly worse regret and constraint violation bounds. Our proofs for the convex set are largely the same as our current proofs.  We use this variant for experiments.\n\n[1]. Sarah Filippi, Olivier Cappe, Aur´elien Garivier, and Csaba Szepesv´ari. Parametric bandits: The generalized linear case. Advances in neural information processing systems, 23, 2010.\n\n[2]. Marc Abeille, Louis Faury, and Cl´ement Calauz`enes. Instance-wise minimax-optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 3691–3699. PMLR, 2021.\n\n> _2. Simplifying key ideas could improve accessibility._\n\nThat is a good suggestion.  Where possible  in the main text (respecting space limitations) alongside definitions we will explain quantities and operations work with a running example of hiring (mentioned in the introduction) or online recommendation (mentioned in Appendix C.1.). Alternatively, we will expand Appendix C.1. to discuss how definitions, operations, and properties would be instantiated for applications to give readers stronger intuition.\n\n### _**Comments or Suggestions**_\n\n> _1. Including a description of the meaning of each variable in Figure 1 can help to understand the counterfactual fairness problem considered._\n\nWe will revise Figure 1's caption as discussed with Reviewer Ye1T for Comments or Suggestions 1.", "claims_and_evidence": "Line 99-101: \"We provide a unified analysis for the estimation method, algorithm design, and **performance guarantee**.\" This paper has only theoretical effectiveness analysis, no experimental validation of performance.", "methods_and_evaluation_criteria": "The proposed methods in the paper are theoretically well-aligned with the problem of causal fair decision-making in sequential settings. However, this paper has only theoretical bounds and no empirical validation.", "theoretical_claims": "I have checked the theoretical claims in this paper. I think the proofs are correct under the stated assumptions.", "experimental_designs_or_analyses": "There is no experimental verification in this paper.", "relation_to_broader_scientific_literature": "The key contributions of the paper intersect with multiple strands of the scientific literature, addressing gaps in causal inference, fairness in machine learning, and sequential decision-making.\n\nSpecifically, the framework of this paper is built on counterfactual fairness [1], with a logistic bandits formulation [2].\n\n\n[1] Kusner, Matt J., et al. \"Counterfactual fairness.\" Advances in neural information processing systems 30 (2017).\n\n[2] Abeille, Marc, Louis Faury, and Clément Calauzènes. \"Instance-wise minimax-optimal algorithms for logistic bandits.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "**Strengths:**\n1. This paper introduces a novel integration of causal inference and counterfactual fairness into a logistic bandit framework. \n2. The proposed algorithm learns fairness constraints online without prior safe policies assumption.\n3. This paper establishes sublinear regret and constraint violation bounds for causal logistic bandits with counterfactual fairness.\n\n**Weaknesses:**\n1. The paper’s theoretical contributions are not supported by empirical results (e.g., simulations or real-world experiments). This limits its practical credibility, as theoretical bounds may be not sharp with complex causal structures. \n2. While the theoretical sections are rigorous, the mathematical density may challenge readers unfamiliar with advanced bandit theory or causal inference. Simplifying key ideas could improve accessibility.", "other_comments_or_suggestions": "Including a description of the meaning of each variable in Figure 1 can help to understand the counterfactual fairness problem considered.", "questions_for_authors": "No.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper focuses on the following bandit setting: the learner seeks to make online fair decisions, where the feedback can be encoded by a logistic function, and the fairness requires a certain counterfactual reasoning. The objective is to maximize the cumulative reward while minimizing the cumulative fairness violations over time. The paper leverages a primal-dual formulation for solving the constrained optimization problem where the constraints are nonlinear and have to be learned over time. The paper theoretically analyzes the regret in outcome rewards and in fairness violations. Improvements are discussed too. 

This paper is a technically solid contribution to the community of causal fairness and online decision making.
Decision: Accept (poster)