Causal Logistic Bandits with Counterfactual Fairness Constraints

Thank you for the thoughtful feedback. Below, we address the main comments provided in the review.

Claim and Evidence

1. "performance guarantee" This paper has only theoretical effectiveness analysis, no experimental validation of performance.

We will add empirical results using a synthetic dataset, evaluating both cumulative regret and constraint violations over multiple horizons. See below for details.

Weaknesses

1. The paper’s theoretical contributions are not supported by empirical results (e.g., simulations or real-world experiments).

We 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:

https://anonymous.4open.science/r/constrained-causal-logistic-bandits-EA00

• Data set description We use a synthetic structural causal model (modified from an example from [1], i.e.,

$

A \leftarrow U_{A},

$

$

W \leftarrow \mathcal{N}(0, \max ( |U_{W}|, |A| )),

$

$

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,

$

$

D_t \leftarrow \mathcal{N} (0, \max (|W|, |M| )),

$

$

Y \leftarrow 1 (  U_{Y} + \frac{1}{3}MD - \frac{1}{5} W  > 0),

$

$

U_{A} \in \{0,1 \}, P(U_{A} =1) = 0.5; U_{W}, U_{M}, U_{Y} \sim \mathcal{N}(0,1),

$

 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.

• 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.

• 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.

• 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.

• 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.

[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.

[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.

2. Simplifying key ideas could improve accessibility.

That 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.

Comments or Suggestions

1. Including a description of the meaning of each variable in Figure 1 can help to understand the counterfactual fairness problem considered.

We will revise Figure 1's caption as discussed with Reviewer Ye1T for Comments or Suggestions 1.

We appreciate your time and feedback. Below, we address the main comments provided in the review.

Weaknesses

1. The paper could benefit from extensive numerical studies.

We 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.

Questions

1. Could you please explain the limitations of proposed algorithm?

There are a few limitations of our proposed algorithm

• 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.
• Stationarity: See the discussion with Reviewer Ye1T for Question 2 for discussion about extending to non-stationary environments.
• 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.

2. Could you provide details on how $\Delta(d, X_{t})$ can be estimated in practice?

To 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,

$

    \hat{\Delta}(d, X_{t}) = g (f (Z_{t})^\top \theta_{t}^\sim ) - g (f (Z_{a_{t}^{\prime}})^\top \theta_{t}^\sim ),

$

where $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.

We are grateful for your detailed and constructive suggestions on our submission. We address the main comments provided as following.

Claims and Evidence

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.

That 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).

We 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$).

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.

Sorry 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.

After Theorem 2, we will add an extra remark before the current Remark 4 to clarify this point:

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).

Questions

1. How does the regret bound in Theorem 2 change with $\delta$?

See Claims and Evidence 1 (above).

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?

The (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.

For example, in our synthetic dataset experiment (see the discussion for Reviewer y2yQ's comments for the results and discussion), we create a structural causal model (including exogenous variables, endogenous variables, and structural causal equations), where 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:

$

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,

$

where $U_{M}$ is the exogenous feature for $M$, $\mathcal{N}$ is the norm distribution.

We appreciate your time and feedback. Below, we address the main comments provided in the review.

Weaknesses

1. My primary concern is the lack of empirical validation.

We 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.

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.

Counterfactual 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.

For 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.

[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.

Comments or Suggestions

1. Readers need to guess how $Z$ is related to other variable like $A ,W, M, X$.

Thank you for pointing this out. We will revise Figure 1's caption to be:

Extended 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)$.

Questions

1. Can you introduce more about the tightness variable $\epsilon$. To be specific, why this variable could help improve the constraint violation bound intuitively?

We will revise the text in Section 3.4 line 404 to include more intuition for how $\epsilon>0$ improves the constraint bound:

"... 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 ..."

2. Is it possible to extend this model to handling distribution shift over time?

That is a good question.

For 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.

An 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.