Causal Logistic Bandits with Counterfactual Fairness Constraints

Introduction

Artificial intelligence (AI) models, using techniques from statistics and machine learning, are increasingly being used to make affect people's lives. In light of this, a plethora of formal fairness criteria have been proposed (Darlington, 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 fairness, including in settings such as classic and contextual bandits (Joseph et al., 2018), combinatorial bandits (Xu et al., 2020), bandits with long-term constraints (Liu et al., 2022), and reinforcement learning (Jabbari et al., 2017), just to name a few. Notably, rather than addressing fairness through the lens of specified attributes, these studies typically operationalize fairness 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 a higher selection probability to a less qualified decision than to a more 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.

In this paper, we focus on a problem structure wherein arms arrive in a 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 a sequence of decisions over a finite set of treatments which appears across a broad range of applications.

Our 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 a constrained causal logistic bandits problem where the online decision-making processes are characterized within a causal structure. We formalize a (non-linear) fairness constraint based on the counterfactual outcome effect that is a 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 a known safe decision subset (see Footnote 1).

• We provide an unified analysis for the confidence set construction, algorithm design, and performance guarantee, i.e., sublinear reward regret and sublinear cumulative constraint violations by leveraging the regret-toconfidence-set conversion and the primal-dual online 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 ρ (see Section 3.2), Slater's constant δ (see Assumption 3), decision-set-dependent term R Z (T ), generalized linear model (GLM). Problem dependent constant κ * , κ Z , κ, where 1/κ * < 1 ≪ κ Z ≪ κ when compared within the same decision and parameter spaces. † Requires prior knowledge (see Footnote 1) of a safe action/policy (i.e. satisfies the constraint ∆ π0 ≤ τ ) (per-round zero constraint violations with high probability).

Related Work

We next briefly discuss two lines of literature closely related to our work. See Appendix B for more discussion 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 governing relationships between the stochastic contexts (seen by the learner before making decisions) and the rewards. They assume all variables are discrete. Like us, they proposed 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 features in an online recommendation system). They make an assumption 1 about a fair policy; they provide high probabil-1 Pacchiano et al. (2021) (which Huang et al. (2022b)'s analysis is based on) requires explicit a priori knowledge of a feasible action/policy (Assumption 5) and states that it is "absolutely necessary" to do so for the problem they study (Remark 1). Huang et al. (2022b)'s Assumption 3 only requires the existence of a safe policy π0; π0 is not explicitly used in estimating rewards or estimating a ity guarantees that all actions are fair. We model fairness as a long-term constraint, for which we seek to bound cumulative violations, as it is unclear whether it is possible to certify policies as fair (feasible) before collecting data to estimate the reward parameter upon which the (non-linear) 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 structural 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 Table 1). In contrast, we model rewards parametrically (using a logistic model), depending on feature maps of the context and decision variables. This dramatically improves the dimensional dependence, though the fairness constraint becomes a mixture of logistic functions for which estimating confidence bounds (to estimate region of fair actions) is more challenging.

Among works on MAB with parametric rewards and unknown (stochastic) constraints, there are numerous works on logistic rewards without constraints and linear rewards with linear constraints (see Appendix B for discussion on those works). The only prior work that like us considered a non-linear (parametric) reward model with non-linear unset of feasible policies in the main paper. However, to the best of our knowledge it is unclear how the conservatively estimated sets of policies Φt (shown w.h.p. to be feasible for all rounds) that are used to select actions could be guaranteed to be non-empty in early rounds without a known safe policy π0 or additional assumptions. 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 κ (see Table 1), which can be arbitrarily large. They considered generalized linear constraints; like in our work, the constraints depend on the unknown parameter vector θ * in the reward function. However, they consider a priori knowledge of some feasible actions. At a high level, they explore the environment (improving their estimate of θ * ) 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.

Preliminaries

In this section, we introduce the basic notations and definitions used throughout the paper. We use capital letters to denote variables (e.g., Y ), lowercase letters (e.g., y) represent scalar values, bold lowercase letters (e.g., y) indicate vectors, and bold uppercase letters (e.g., Y) represent matrices. For a twice-differentiable function g, the notation ġ and g 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 dimension. For two realvalued 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 ∥z∥ A = √ z ⊺ Az. Finally, for two univariate real-valued functions f and g, we denote f = O(g) to indicate that g dominates f up to logarithmic factors; and for an event E ∈ Ω, we write 1{E} 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, V, F , P(u)⟩, where U is a set of exogenous (unobserved or latent) variables, V is a set of endogenous (observed) variables, F is a set of structural functions, and P(u) is a distribution over the latent variables. For the set of structural functions F , f Vi ∈ F decides values of an endogenous variable V i ∈ V taking as argument a combination of other variables. That is,

, where P a Vi denotes the parent set (explained below) of V i . Realizations of the set of latent variables U ∼ P(u) induce an observational distribution P(v) over V . An intervention on a variable

Each SCM is associated with a directed acyclic graph (DAG) G (e.g., see Figure 1), called the causal diagram, where nodes correspond to endogenous variables V, solid arrows represent arguments of each function f V . A bi-directed arrow between nodes V i and V j indicates an unobserved confounder affecting both V i and V j , i.e., U Vi ∩ U Vj ̸ = ∅. We will use the graphtheoretic family abbreviations, e.g., P a(V ) G stand for the set of parents of V in G. Two nodes X and Y are said to be d-separated by a third set Z in a DAG G denoted by (X ⊥ ⊥ Y |Z) 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), included in Appendix A with formal definitions for completeness.

A Theoretical Framework for Constrained

Causal Logistic Bandits

In this section, we formalize the constrained causal logistic bandits theoretical framework in the semantics of SCMs and MABs. We start by considering a recruitment example (see Appendix D.1 for more motivating examples), where 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. Variable A represents the specified attribute, W is a set of confounded features, and M is a set of intermediate features, D and Y represent the decision and outcome reward. The contextual information {w t , m t , a t } is accessible by the learner before making decisions. 2.1. Logistic bandits with structural causal model At every round t, the learner observes the contextual features {w t , m t , a t }, which are drawn from a stochastic distribution and then is presented a set of decisions D t that depend on the candidate's context. The learner chooses a decision d t ∈ D t and receives an outcome reward y t+1 ∈ {0, 1}. The learner's decision is based on previous round knowledge F t = (F 0 , {w t , m t , a t , d t , y t+1 } t-1 t=1

) and causal information, where F 0 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 features Z, specifically,

where the fixed but unknown parameters θ * belongs to R n , g(x) = (1 + e -x ) -1 is the standard logistic function, f is the mapping function that is known ahead of time to the learner, and the encoded feature vector f (Z) is in R n . Then the interventional distribution for the expected reward of do(d t ) and do(a t ) given the observed contextual features m t and w t is represented as (Plecko & Bareinboim, 2024):

where Z t is the feature consisting of the decision d t and the contexts {w t , m t , a t }, In this paper, we consider one specified attribute variable A, which in general is a parent of the decision and outcome variable in the causal graph (see Figure 1). Note that the specified attribute value at round t is a t and we denote the counterfactual value as a ′ t . 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 a ′ t for any decision d

t is the counterfactual feature for the interventions do(a ′ t ) and do(d). Notice that for this problem, we consider that the factual feature Z t and counterfactual feature Z a ′ t are both in the feature space Z. The derivation of Equation (2) and Equation (3) follows by the do-calculus rule (Pearl, 1995); readers can refer Appendix D.2 for a more detailed analysis. Therefore, the counterfactual fairness effect for decision d t is represented as:

Counterfactual fairness modeling via soft constraint

In this section, we discuss modeling fairness as part of the learner's decision making problem. Consider a stochastic bandit optimization with a soft constraint for our decisionmaking problem. In particular, at every round t ∈ [T ], the learner selects a decision d t to maximize the expected reward E[Y |do(d t ), do(a t ), w t , m t ] subject to a constraint on (violations to) counterfactual fairness (Equation (4)),

where τ is a predefined fairness threshold. In this work, the counterfactual fairness constraint by Equation (5) requires that the expected reward is similar regardless if the value of the specified attribute had been different. In addition, the learner only receives bandit feedback (the reward). The learner does not not observe feedback on constraint violations. Huang et al. (2022b) were the first to propose a counterfactual fairness constraint in a bandit framework. We note that their setting confines the learner to decisions from a safe action set (see Footnote 1). To the best of our knowledge, that setting requires strong assumptions on prior knowledge of a subset of safe actions that can be used even before rewards are estimated (the constraint (4) depends on the unknown reward parameter vector θ * ). Prior knowledge of safe actions can be mild in some settings, though we argue counterfactual fairness (a convex combination of logistic functions that depend on the unknown reward parameter vector θ * ) is more complex, thereby it is 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 a priori, we allow for instantaneous violations but bound the cumulative violations.

The goal of the learner is to maximize the cumulative expected outcome reward while minimizing the cumulative expected counterfactual fairness constraint violations throughout the learning process. Define the cumulative expected regret and cumulative expected counterfactual fairness constraint violations as

where

In this paper, we establish a stronger version of regret (Liu et al., 2021;Zhou & Ji, 2022), specifically, let π t be a probability distribution over the set of actions D t at round t, and let

We compare the received outcome reward with the following baseline optimization problem:

t is the optimal solution at step t. Thus, the stronger regret is defined as:

Note that the probability distribution π t could include some decisions that violate the constraint but on average the constraint is satisfied, while for a single action it must be a feasible one, therefore, R + (T ) ≥ R(T ).

Model assumptions and definition

To study our 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 n . 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 parameter vector θ, ∥θ∥ 2 ≤ S, ∀ θ ∈ Θ.

Assumption 2. The feature mapping function f : Z → R n is in a reproducing kernel Hilbert space (RKHS) with a bounded norm (i.e., a measure of smoothness), such that ∥f (Z)∥ 2 ≤ 1, ∀ Z ∈ Z.

Assumption 3 (Slater's Constraint Qualification). There is a constant δ > 0 such that there exists a feasible probability distribution π t,0 over decision set D t that satisfies

. Without loss of generality, we assume δ ≤ 1.

Notice that this is a mild assumption since it only requires that one could find a stochastic policy π t,0 under which the expected constraint violations will be strictly less than a negative value. Whereas for hard constraints (Amani et al., 2019;Khezeli & Bitar, 2020;Pacchiano et al., 2021), they typically assume that the non-empty initial safe decision set which is stronger than the assumption of existence for a Slater's constant δ about the learner's knowledge.

We next define a problem dependent quantity that impacts learnability.

Definition 1 (Problem Dependent Constantfoot_1 ).

We recall the other problem dependent constants discussed in Table 1:

Notice that such problem dependent constants are defined through the first order of logistic function, which quantifies the level of non-linearity of plausible expected reward signals with different scales. In particular, κ can be significantly large even for reasonable logistic bandits problems. Readers can refer Section 2 of (Faury et al., 2020) for a detailed discussion on the importance of this quantity.

Convex confidence set

For logistic bandit problems, a natural way to estimate the reward parameter θ * given F t is to use maximum-likelihood estimation. We build on the works for the unconstrained problem (Abeille et al., 2021;Lee et al., 2024). At every round t, a reward value y t+1 is sampled from a Bernoulli distribution with expected value (or success probability) g(f (Z t ) ⊺ θ * ). The unregularized cumulative logistic loss can be written as:

The loss L t (θ) is a strongly convex function of θ (Abeille et al., 2021;Lee et al., 2024). The reward parameter is estimated using maximum likelihood estimation (MLE), defined as θt = arg min ||θ||2≤S L t (θ). For α ∈ (0, 1], we use the confidence set:

where β t (α) = 10n log( St 4n + e) + 2((e -2) + S) log 1 α . Then the following proposition ensures that C t (α) is a confidence set for θ * with high probability: Proposition 1 (Theorem 1 in (Lee et al., 2024)).

The proof is provided in Appendix E. The proof uses the approach 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 O( nS 3 log(t)), while the above tightened loss-based confidence set results in O( (n + S) log(t)), leading to an overall improvement in the factor of S, especially when S is large, e.g., S ≥ |D t |.

Online learning algorithm

We consider a constrained stochastic causal logistic bandit over horizon T as described in Section 2.2. The objec-tive for the learner is to maximize the cumulative rewards while minimizing cumulative counterfactual fairness violations over time horizon T . To address the challenges on the unknown reward and the unknown counterfactual fairness constraint, we develop a Constrained Causal Logistic Bandits (CCLB) algorithm by leveraging the primal-dual optimization techniques.

The pseudo code for our CCLB algorithm is in Algorithm 1. At every round t, let the Lagrangian of the primal problem

and then the associated dual function is defined as q(ϕ) = max πt L D (π t , ϕ). Since both the reward and counterfactual fairness constraint depend on the unknown parameter θ * , we first estimate it through maximal likelihood estimation and construct a confidence set C t (α) using the observed histories, i.e., feature vectors and rewards. The greedy procedure 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 ( θt ) is obtained by maximizing the expected reward across the confidence set C t (α), however, we penalize the expected reward for the constraint violations when the greedy action (d t ) is picked by the learner over the decision domain D t . The dual update that minimizes q(ϕ) with respect to ϕ is by taking a projected gradient descent with 1/η being the step size. Note that the truncated parameter ρ is chosen to be larger than the optimal dual variable ϕ * , where can be achieved since the optimal dual variable is bounded under the Slater's constraint qualification, specifically, d), do(a t ), w t , m t ])/δ from Theorem 8.42 in (Beck, 2017).

Remark 1. We remark that the computational complexity of Algorithm 1 is the same as standard 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 optimization retains the character of the unconstrained case without constructing a prior safe subset designed for hard constraints as in (Amani et al., 2020). Additionally, the reward and counterfactual fairness constraint in our algorithm share the same unknown parameter θ * .

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 ρ ≥ 2/δ, and η = √ T /ρ. For 0 ≤ τ < 1, under the Slater's constraint qualification in Assumption 3 and regularity assumptions in Assumption 1 and 2, the CCLB algorithm achieves the following Algorithm 1 CCLB Algorithm 1: Input: Horizon T , truncated parameter ρ, step size η = √ T /ρ, and the initial dual value ϕ 1 = 0. 2: for t = 1, 2, 3, . . . , T do 3:

Use MLE to estimate the reward parameter and build a confidence set C t (α) from Equation (10),

Greedy procedure. Choose the optimistic reward parameter θt and select the greedy action d t :

Update the estimates of the dual variable:

Update the estimation and confidence set according to the new received reward y t+1 . 7: end for bounds simultaneously with probability at least 1 -α for any α ∈ (0, 1]:

Remark 2. We remark that: (1) the leading term of our regret O(ρnS √ T ) is similar to the bound O(nS T /κ * ) established in (Lee et al., 2024) as the logarithmic growth of T , which improves upon (Abeille et al., 2021) (OFULog-r) by a factor of S 3/2 and improves upon (Zhang & Sugiyama, 2024) by at least a factor of √ S. Though it acquires a multiplicative factor ρ, one could note that, at an extreme case, when the Slater's constant δ is optimized to 1/ log(T ), the leading term scales as O(n √ T ).

(2) Compared to the unconstrained case (Abeille et al., 2021;Zhang & Sugiyama, 2024;Lee et al., 2024), the regret bound R + (T ) exhibits an additional term ρ √ T , which roughly captures the impact of the unknown counterfactual fairness constraint, i.e., a convex combination of logistic functions, which is not logistic function any more. More specifically, the non-convex nature of the logistic mixture introduces a non-linear relationship between the constraint and the reward parameter, thereby resulting in a more complex estimated feasible region 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 κ (see Table 1). ( 4) If τ ≥ 1, the constraint violations bound V(T ) will be zero since the counterfactual fairness constraint is satisfied for all the decisions (see Equation 5) and our problem falls into the setting of logistic bandits without constraint.

See Appendix G for the full proof. We next highlight a few key parts of the proof.

Proof Sketch of Theorem 1. We first derive the following key decomposition of total regret and constraint violations that holds for any ϕ ∈ [0, ρ] : R

. 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 R 1 and R 2 , we apply the following proposition for logistic bandits regret: Proposition 2. With probability at least 1 -α for any α ∈ (0, 1], under the CCLB algorithm, we have:

The central idea to obtain the above regret (Proposition 2) is by applying Taylor expansion which tightly link estimation errors (e.g. between θ t and θ * ) to prediction errors (e.g. between g(f (Z t ) ⊺ θ t ) and g(f (Z t ) ⊺ θ * )), readers can refer Appendix F for more technical details. As for the logistic bandits regret based on the counterfactual feature vectors, i.e.,

, we observe that the counterfactual feature vector Z a ′ t and the factual feature vector Z t are both lie in the same feature space Z for our problem. Thus,

) exhibits the same asymptotic upper bound up to logarithmic factors as

Therefore, the regret upper bound R + (T ) can be obtained by choosing ϕ = 0.

Inspired by (Beck, 2017), we apply tools from constrained convex optimization to obtain the bound on constraint violations V(T ).

First, we define the the probability distribution π

where the policy π ′ t only puts probability mass (equal to 1) on decision d t chosen by the learner after the observation of contextual information at every round t. Then, we have,

t , by utilizing (Beck, 2017, Theorem 3.60), we obtain the upper bound on V(T ). ■

Improved regret and constraint violations bounds

In Section 3.3, our analysis demonstrates that the proposed CCLB algorithm (Algorithm 1) achieves both sublinear regret and sublinear constraint violations upper bounds. Another natural question to consider is whether the constraint violations bound can be further improved. It turns out that by introducing a tightness parameter ϵ in the dual update in Algorithm 1, for ϵ < δ,

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 before. Intuitively, with a tightness parameter ϵ > 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 τ -ϵ instead of τ ). Then, under this new hypothetical pessimistic constraint function, the primal problem is modified as:

be the optimal solution to this new constrained optimization problem, then we have the following relationship between policy π * t,ϵ and π * t : Proposition 3. Let policies π * t and π * t,ϵ be the optimal solutions for the constrained problem

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 π * t,ϵ as: R ϵ

We then state the following theoretical results for R ϵ + (T ) and V(T ): Theorem 2. Suppose ρ ≥ 2/δ, and η = √ T /ρ. For 0 ≤ τ < 1 and the user-chosen parameter ϵ ∈ [0, δ), under Slater's constraint qualification in Assumption 3 and regularity assumptions in Assumption 1 and 2, the CCLB algorithm with refined constraint condition (see Equation ( 11)) attains the following theoretical upper bounds with probability at least 1 -α for any α ∈ (0, 1] :

Remark 3. One could notice that (1) by introducing a tightness parameter ϵ in the dual update, the associated regret R ϵ + (T ) still achieves a comparable asymptotic upper bound as R + (T ) in Theorem 1; nevertheless, the constraint violations 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 of ϵT , thereby obtaining a 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 ϵ ∈ [0, δ) and Theorem 1 is ρ √ T (2ϵ + ϵ 2 ). For a problem-dependent (fixed) Slater's constraint qualification constant δ > 0, increasing ϵ only worsens the regret bound, as the learner is increasingly cautious (increasing in ϵ), selecting from a smaller set of actions than the learner would have with ϵ = 0. If δ is large, ρ shrinks towards 2 and so for a fixed tightness ϵ the regret bound reduces. Larger δ also allow for a bigger range of ϵ and thus more room for caution (and regret). Proposition 4. By conditions stated in Theorem 2, for the user-selected parameter

are the universal constants independent of n, S, T, κ Z , if n ≥ 2 and ϵ ′ < δ for sufficiently large T , then one could achieve a zero upper bound on the constraint violations when selecting ϵ ∈ (ϵ ′ , δ).

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 encourages exploration and adaptability to changing environments, which might lead to occasional violations of constraints. Conversely, strictly adhering to constraints may limit the algorithm's ability to adapt, potentially increasing regret.

Numerical Experiments

We next evaluate the empirical performance of our proposed methods on a synthetic data set. See Appendix H for additional experiments for different values of the constraint threshold τ and tightness parameter ϵ.

Data set description:foot_3 We generated the synthetic dataset from a structural causal model (modified an example from (Plecko & Bareinboim, 2024)), i.e.,

As defined in Figure 1, A denotes the sensitive attribute (binary valued), W is the confounded feature, M represents the intermediate feature, D ∈ D is the agent's decision, and Y is the outcome. At every round, we generate a set of 20 feature vectors {[A, W, M, D i ]} 20 i=1 along with their corresponding counterfactual feature vectors. We use rejection sampling over the sets to make sure that at least twelve of the feature vectors are feasible.

Algorithms:foot_4 We evaluate four different algorithms: GLM-UCB (Filippi et al., 2010) (unconstrained generalized linear bandits ), OFULog+ (Lee et al., 2024) (unconstrained logistic bandits ), CCLB (our method, causal logistic bandits with counterfactual fairness constraints, Algorithm 1), and ϵ-CCLB (our method with a user-chosen tightness parameter ϵ, Algorithm 2).

Metrics: We evaluated the algorithms using cumulative regret (6), cumulative constraint violations (7), and a penalized 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 θ), but we count the reward earned as being 0. In this way, constraint violations are allowed but are not (directly) profitable. This penalized form combines the two primary metrics for simpler analysis. penalized cumulative regret (Figure 2 (c))

, where rewards are only received for fair actions, there is a large gap between our method (CCLB) and the methods of OFULog+ and GLM-UCB, with the gap growing larger for longer horizons. This is expected since GLM-UCB and OFULog+ do not account for constraints. Both baselines have nearly linear 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 cumulative regret (unpenalized), OFULog+ performs better than our method (which seeks to satisfy the constraint).

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 ϵ-CCLB has a larger regret than CCLB (but less than GLM-UCB), the cumulative constraint violations of ϵ-CCLB are much smaller than CCLB, especially, its growth rate is nearly 0 from horizon T = 2, 000 to horizon T = 10, 000, which rarely violates the constraints.

Conclusion

This paper introduced a framework for logistic bandits with counterfactual fairness constraints built within a causal structure. The proposed approach attains satisfactory results, demonstrating sublinear growth in both regret and constraint violations by effectively balancing exploration and exploitation 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. (1) One important direction is to extend our method to work with unobserved confounders (i.e. W would be unobserved).

(2) Another interesting direction is to extend our model to handle distribution shifts over time.

(3) A third interesting direction would be to extend our work to handle budget constraints and consider a fairness notion defined by the resource assignment, potentially building on existing work in bandits with knapsacks (Tran-Thanh et al., 2012;Badanidiyuru et al., 2018;Nie et al., 2024).

Organization of the Appendix

• In Appendix A, we recall important notations and introduce some useful functions and results.

• In Appendix B, we provide additional related works for our problem.

• In Appendix C, we list some technical lemmas, needed for the analysis.

• In Appendix D, we provide motivation and proofs for the constrained causal logistic bandits framework.

• In Appendix E, we prove the convex confidence set.

• In Appendix F, we prove the logistic bandits regret upper bound.

• In Appendix G, we prove the total regret and constraint violations upper bounds, and the improved results.

• In Appendix H, we provide additional results for the numerical experiments.

A. Preliminaries

We first provide a formal definition for d-separation discussed in Section 1.3, Definition 2 (d-separation (Pearl, 2009)). A path p is said to be d-separated (or blocked) by a set of nodes Z if and only if (1) p contains a chain i → m → j or a fork i ← m → j such that the middle node m is in Z, (2) p contains an intervened fork (or collider) i → m ← j such that the middle node m is not in Z.

We then detail below some useful notations that have been used throughout the paper. Below

1}, θ * true reward parameter vector. Y reward variable. X t context vector including the specified attribute, the confounded features, and the intermediate features. f (Z t ) mapping feature vector. λ t regularization parameter. ϕ t dual variable. ρ truncated parameter. ϵ user-chosen tightness parameter. δ Slater's constant. α failure probability. C t (α) confidence set. B n p (1) n-dimensional ball of radius 1 under the ℓ p norm. || • || ℓ 2 norm.

We further recall and introduce the following functions and use it for the following analysis,

Where the regularized design matrices V t , H t (θ * ), G t (θ, θ * ), and α(f (Z τ ), θt , θ * ) are defined for the proof of logistic bandits regret upper bound in Appendix F. In particular, H t (θ * ) measures the local behavior of the logistic function through ġ f (Z τ ) ⊺ θ * .

B. Additional Related Works

Logistic bandits. The logistic bandits model represents a sequential decision-making framework that has attracted substantial attention within the parametric bandits literature (Li et al., 2010;Filippi et al., 2010;Li et al., 2017;Dong et al., 2019). In a recent work, Faury et al. (2020) proposed an optimistic algorithm based on a finer examination of the non-linearities of the reward function to study the prohibitive linear dependencies introduced by κ in the regret upper bound. Abeille et al. (2021) proved a minimax-optimal rate by deriving an Ω n T /κ * (T ) problem-dependent lower-bound, which implies that the non-linearity in logistic bandits can ease the exploration-exploitation trade-off in the long-term regime, i.e. κ * (T ) > 1. 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 is the multinomial logit contextual bandit problem (Agrawal et al., 2017;Oh & Iyengar, 2019;Zhang & Sugiyama, 2024;Lee et al., 2024), which generalizes the binary logistic bandit by allowing the learner to select a subset of arms. In particular, (Zhang & Sugiyama, 2024;Lee et al., 2024) also improve the logistic bandits on the regret guarantee (with respect to S) and computational complexity, respectively.

Fairness. The body of research in fair machine learning is expanding and encompasses a 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) Constrained MABs. There is a 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 et 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 kernelized 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.

C. Technical Lemmas

Lemma 1 ((Abeille et al., 2021) Lemma 11). Let {u τ } ∞ τ =1 be a sequence in R n such that ||u τ || ≤ B for all τ ∈ N, and let λ be a non-negative scalar. For t ≥ 1 define

The following inequality holds:

Proof. By definition of V t :

Where the second inequality follows by λ t ≥ λ t-1 ; the forth inequality comes from Matrix Determinant Lemma. Taking the log on both side of the equation and summing from t = 1 to T :

Where the second equality is by telescopic sum; and the last equality comes from Lemma 1. Therefore:

Where the second inequality comes from ||u t || 2 V -1 t ≤ B 2 /λ t ; and the third inequality follows by log(1

We then state some useful generalized self-concordance results from (Faury et al., 2020, Lemma 9) and (Abeille et al., 2021, Lemma 7). We provide a proof for the sake of completeness (we also use the properties from (Abeille et al., 2021, Lemma 8)).

Lemma 3 ((Faury et al., 2020) Lemma 9). Let g be a strictly increasing function such that |g| ≤ | ġ|, and let Z be any bounded interval of R. Then, for all z 1 , z 2 ∈ Z:

Proof. Since function g is strictly increasing, we have ġ > 0 for any z ∈ Z. Therefore:

where the first line follows from z 0 ∈ Z. Assume that z 2 ≥ z 1 , let v ≥ 0, and set z 0 = z 1 + v(z 2 -z 1 ), we then could easily get:

Where the second line follows by taking integral of v from 0 to 1 for both sides; and the last line is obtained by using exp(-x) ≤ (1 + x) -1 if x ≥ 0. We note that the same inequality can be proved when z 2 < z 1 by following the same steps. ■ Lemma 4 (Polynomial Inequality; (Abeille et al., 2021) Lemma 7). Let b, c ∈ R + , and u ∈ R. The following implication holds:

Then f is a strongly-convex function which roots are:

If u 2 ≤ bu + c, then f (u) < 0 and by convexity of f we obtain:

Where the last inequality is because √ x + y ≤ √ x + √ y, ∀x, y ≥ 0. ■

E. 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:

where:

Proposition 1. Let α ∈ (0, 1], then

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 L t (θ) -L t ( θt ) as the sum of (i) the regret of the online learning algorithm, (ii) a 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 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-geometric interpretation of the KL divergence.

Firstly, we denote ξ τ as a real-valued martingale difference noise where ξ τ = g(f (Z τ ) ⊺ θ * ) -y τ , thus for the logistic loss

, we have that the following equality holds for any θ:

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 θτ and taking a sum over time steps τ :

where in ( 23) we add and subtract ℓ τ ( θt ) and in ( 24) we rearrange terms. We further define and ζ 3 24), we then have

)} is the filtration for our bandit model, f (Z τ ) and θτ are F s-1 -measurable, and ξ τ is a martingale difference sequence w.r.t. F s-1 . Thus, we have that,

From (Beygelzimer et al., 2011, Theorem 1), we could apply Freedman's inequality to obtain the following result, Lemma 5. (Lee et al., 2024, Lemma 3). Let f (Z 1 ), ..., f (Z t ) be martingale difference sequence satisfying max τ |f (Z τ )| ≤ R a.s., and let F τ be the σ-field generated by (f (Z 1 ), ..., f (Z t ). Then for any α ∈ (0, 1) and any η ∈ [0, 1/R], the following holds with probability at least 1 -α:

Thus, for η ∈ [0, 1 2S ] to be chosen later, by invoking Lemma 5 for the martingale difference sequence f (Z 1 ), ..., f (Z t ), the following holds with probability at least 1 -α, ∀t ≥ 1:

Lower Bounding ζ 2 (t). From the standard result in information geometry (Amari, 2016;Brekelmans et al., 2020), we have the following result: Lemma 6. (Lee et al., 2024, Lemma 4). Let m(z) := log(1 + e z ) be the log-partition function for the Bernoulli distribution and g(z) = 1 1+e -z . Then, we have that

where

Notice that

Thus, we have the following lower bound on ζ 2 (t),

Where ( 28) follows by definition of ζ 2 ; (29) uses Lemma 6; (30) uses ( 27); (31) follows by change variables; (32) follows by (Abeille et al., 2021, Lemma 8); and (33) follows by Assumption 1 and 2.

Upper Bounding ζ 3 (t) (Lee et al., 2024, Theorem 2). From (Foster et al., 2018, Theorem 3), there exists an (improper learning) algorithm for online logistic regression with the following regret:

Though our selected decisions are more conservative compared with (Lee et al., 2024) (add a penalty term when selecting decisions to account for constraint violations), the estimation method to obtain θt (i.e., MLE) and the way to compute the optimistic estimate θt (i.e., θt = arg max θ∈Ct max d∈Dt E[Y |do(d), a t , w t , m t ]) are the same as (Lee et al., 2024). See the justification for using the improper learning algorithm in (Lee et al., 2024, Appendix B.2).

Combining Equation ( 25), ( 26), (33), and (34), with η =

which finishes the proof. ■

F. Logistic Regret Upper Bounds

In this section, we provide the proofs for logistic bandits regret upper bounds presented in Section 3.3. Some of the details follow from (Faury et al., 2020, Appendix B) and (Abeille et al., 2021, Appendix C). We first define the regret of logistic bandits, and use which to prove the regret and constraint violations upper bound in Appendix G for our problem:

where the (35) comes from the expected reward in (2); the (36) is by performing the Taylor Series Expansion of g(f (Z t ) ⊺ θt ) on f (Z t ) ⊺ θ * with a first order integral remainder. Then we rewrite the logistic regret R log as R log 1 and R log 2 , where,

We separately upper bound both terms. Firstly, we prove the following Lemma used throughout this section.

Lemma 7. With λ t = 1 4S 2 (2+2S) , for any θ ∈ C t (α), the following holds with probability at least 1 -α:

Proof. By proposition 1, we have that with probability at least 1 -α, L t (θ * ) -L t ( θt ) ≤ β t (α) 2 , we assume this event is true throughout this proof. Then, by second-order Taylor expansion of L t (θ) around θ * ,

As for the relationship between G t (θ, θ * ) and H t (θ * ), we have the following result:

Thus, we have that,

Where (37) follows by

, by Freedman's inequality (26), for any η ∈ [0, 1 2BS ], the following holds:

By (Vershynin,Corollary 4.2.13) and (Lee et al., 2024, Appendix C.4.4) the following holds with probability at least 1 -α:

Choose η = 1 2(e-2)(2+2S) < 1 2S , ϵ t = n t , and with Equation (37), we finally have:

Which finishes the proof. ■ F.1. The regret upper bound of R log 1 .

We start by examining R log 1 and show the following upper bounds:

Where ( 39) and ( 42) is by Cauchy-Schwarz inequality ( ġ f (Z t ) ⊺ θ * is non-negative); (40) comes from Lemma 7 and ( 41) is because γ T (α) = max t∈[T ] γ t (α); in (43), we define vector

, and obtain:

and (44) follows by Lemma 2.

We then take a look at the first order of the logistic function ġ(f (Z t ) ⊺ θ * ) and derive a upper bound for it by a first-order Taylor expansion:

Where ( 45) comes from the Taylor Expansion; (46) follows by changing variables; (47) is by taking the absolute value; ( 48) is because the optimistic estimate at step t, hence, f 50) follows by the self-concordance property of logistic function | ġ| ≥ |g| and ġ > 0; (51) follows by ( 16) and ( 52) is from the fundamental theorem of calculus; and (54)

Therefore, by ( 44) and ( 54), we intermediately obtain the following upper bound on R log 1 :

where ( 55) is because

F.2. The regret upper bounds of R log 2 .

In order to upper bound the logistic bandits regret R log in (36), we still need to upper bound R log 2 that includes the second order of logistic function:

Where ( 57) follows by changing variables; (58) is because g ≤ 1; (59) follows by Cauchy-Schwarz inequality; (60) comes from Lemma 7; (61) is by C T (α) = max t∈[T ] C t (α); as for (62), we note that

where the second line comes from Definition 1. Thus, and (63)follows by Lemma 2.

Then by the upper bounds on R log 1 in Equation ( 55) and R log 2 in Equation ( 63), we then finally upper bound the logistic bandits regret R log in Equation ( 36):

where (66) follows by Lemma 4; and (67) comes from (x + y) 2 ≤ 2x 2 + 2y 2 . To further simplify the logistic bandits regret R log , we write γ t (α) as:

To get an intuitive understanding on how γ t (α) behaves when t grows, we write γ T (α) as an asymptotic notation of T , i.e., γ T (α) = O(S n log(T )). Therefore, as for the R log , we obtain the following bounds:

which finishes the proof. ■

G.1. Proof of Theorem 1

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,

the r.h.s. is because the logistic function is less than 1. Now, we turn to establish a bound over R + (T ) + ϕV(T ). First, note that,

Where (69) holds since ϕ t ≥ 0 and E π * t (|∆(d t )| -τ ) ≤ 0; (71) holds by adding and subtracting

; and (72) comes from Lemma 8. We are then going to bound R 1 :

Where the second equality follows by adding and subtracting terms; the third inequality comes from the greedy action d t chosen at step t in Algorithm 1; the forth inequality comes from the optimistic estimate θt in Algorithm 1; and the fifth inequality is because ϕ t ≤ ρ; as for the result in the last line, we note that if ∆(d) ≥ 0 then ∆(d) ≥ 0, and by the counterfactual fairness effect (see Equation ( 4)), we have,

where the second line follows by optimistic estimation. On the another hand, if

, similarly, the second line follows by the optimistic estimate, here, we notice that, the factual feature Z t and the counterfactual feature Z a ′ t reside within the feature space Z, in which the boundness assumption (Assumption 1) and problem dependent constant (Definition 1) are defined by. Therefore, the logistic bandits regret of g(f (Z t ) θt ) -g(f (Z t )θ * ) has the same asymptotic upper bound up to logarithmic factors as g(f (Z a ′ t ) θt ) -g(f (Z a ′ t )θ * ) (see Equation ( 68)). We further bound R 2 . When ∆(d) ≥ 0:

Where the second equality follows by the counterfactual fairness effect (see Equation ( 4)); the forth inequality follows by the optimistic estimate.

When ∆(d) < 0, we have that:

Since the logistic bandits regret of g(f (Z t ) θt ) -g(f (Z t )θ * ) has the same asymptotic upper bound up to logarithmic factors as g(f

Thus, by Equation ( 73) and Equation ( 74), the upper bound on R + (T ) + ϕV(T ) for any ϕ ∈ [0, ρ] is the following:

Regret R + (T ). By setting ϕ = 0, then we obtain the upper bounds on the total regret guarantee with high probability:

where the second line is because the truncated parameter ρ ≥ 2/δ; and the last line is to write the regret upper bound in a logarithmic asymptotic notation.

Constraint violations. Next, to obtain a bound on V(T ), we employ tools from constrained convex optimization. First, we define probability distribution π ′ t by

Then we apply the following theorem from Theorem 3.60 in (Beck, 2017).

Theorem 3. Consider the following convex constrained problem f (π * ) = max π∈Π {f (π) : g(π) ≤ 0}, where both f and g are convex over the convex set Π in a vector space. Suppose f (π * ) is finite and there exists a slater point π 0 such that g(π 0 ) ≤ -δ, and a constant ρ ≥ 2ϕ * where ϕ * is the optimal dual variable, i.e., ϕ * = argmin ϕ≥0 (max π f (π) -ϕg(π)).

Assume that π ′ ∈ Π satisfies

for some ϵ > 0, then we have [g(π ′ )] + ≤ 2ϵ ρ .

Since

Then Equation ( 76) satisfies the conditions in Theorem 3 and we have that:

Where the second line follows by ϕ ∈ [0, ρ] and 1/ρ < 1. ■ Lemma 8. Under the dual update of ϕ t in Algorithm 1, we have the following for any ϕ ∈ [0, ρ]:

Proof. By the dual update of ϕ t in Algorithm 1:

Summing over T steps and multiplying both sides by η 2 :

Therefore:

where the second equality comes from telescopic sum; and the forth equality follows by ϕ 1 = 0 and η = √ T /ρ initialized in Algorithm 1; and the fifth inequality is because

Proposition 3 states the relationship between policy π * t and π * t,ϵ for the regret upper bounds, we provide a proof in the following. Proposition 3. Let policies π * t and π * t,ϵ be the optimal solution for constrained problem

Proof. The policies π * t and π * t,ϵ are defined as:

Let one policy π t,ϵ = (1 -ϵ δ )π * t + ϵ δ π t,0 , where π t,0 is the policy satisfies the Slater's constrained qualification, i.e.,

Therefore, π t,ϵ is a feasible solution of the baseline problem

Where the first inequality follows by that π * t,ϵ is the optimal solution while π t,ϵ is a feasible solution to E πt,ϵ [E[Y |do(d), do(a t ), w t , m t ]] : 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 ϵ, which serves to tighten the constraint. First, we decompose R ϵ + (T ) + ϕV ϵ (T ) as follows, where V ϵ (T ) = Causal Logistic Bandits with Counterfactual Fairness Constraint = T t=1 E π * t,ϵ E[Y |do(d), do(a t ), w t , m t ] -E[Y |do(d t ), do(a t ), w t , m t ] + ϕ[|∆(d t )| -τ + ϵ] ≤ T t=1 E π * t,ϵ E[Y |do(d), do(a t ), w t , m t ] -E[Y |do(d t ), do(a t ), w t , m t ] + ϕ[|∆(d t )| -τ + ϵ] -ϕ t E π * t,ϵ [|∆(d)| -τ + ϵ] = T t=1 E π * t,ϵ E[Y |do(d), do(a t ), w t , m t ] -ϕ t E π * t,ϵ [|∆(d)| -τ + ϵ] -E[ Y |do(d t ), do(a t ), w t , m t ] + ϕ t [| ∆(d t )| -τ + ϵ] R ϵ 1 + T t=1 E[ Y |do(d t ), do(a t ), w t , m t ] -E[Y |do(d t ), do(a t ), w t , m t ] + ϕ [|∆(d t )| -τ + ϵ] -[| ∆(d t )| -τ + ϵ] R ϵ 2 + T t=1 ϕ[| ∆(d t )| -τ + ϵ] -ϕ t [| ∆(d t )| -τ + ϵ] . R ϵ 3 Similar to the techniques in Section G.1, we can upper bound R ϵ 1 , R ϵ 2 , R ϵ 3 as follows: R ϵ 1 = T t=1 E π * t,ϵ E[Y |do(d), do(a t ), w t , m t ] -ϕ t E π * t,ϵ [|∆(d)| -τ + ϵ] -E[ Y |do(d t ), do(a t ), w t , m t ] + ϕ t [| ∆(d t )| -τ + ϵ] = ρ • O nS log(T ) √ T + n 2 S 2 (log(T )) 2 + n 2 S 2 κ Z (log(T )) 2 , R ϵ 2 = T t=1 E[ Y |do(d t ), do(a t ), w t , m t ] -E[Y |do(d t ), do(a t ), w t , m t ] + ϕ [|∆(d t Regret R ϵ + (T ). By setting ϕ = 0, we have:

Constraint violations. By applying (Beck, 2017, Theorem 3.60), we have:

To obtain a bound V(T ), we notice that:

Which finishes the proof. ■ Algorithm 2 ϵ-CCLB Algorithm 1: Input: Horizon T , truncated interval ρ, step size η = √ T /ρ, and the initial dual value ϕ 1 = 0, user-select parameter ϵ ∈ [0, δ). 2: for t = 1, 2, 3, . . . , T do 3:

Use MLE to estimate the reward parameter and build a confidence set C t (α) from Equation (10), C t (α) = θ ∈ Θ : L t (θ) -L t ( θt ) ≤ β t (α) 2 . we solve it when the right-hand-side is less than 0:

where Γ = C 1 nS log(T ) √ T + C 2 n 2 S 2 ((log(T ))) 2 + C 3 κ Z n 2 S 2 (log(T )) 2 + C 4 √ T . First, when T is large, the upper bound of ϵ have the following inequality:

Since it is larger than the Slater's constant, therefore ϵ < δ. Now we look at the lower bound of ϵ, If the lower bound ϵ ′ is less than the Slater's constant, then when the learner choose ϵ ∈ [ϵ ′ , δ), we could achieve zero cumulative constraint violations. ■