- Rating
- 3
- Confidence
- 4(+1)
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies causal logistic bandits with counterfactual fairness constraints, where the learner only observes factual rewards. The authors first show that without sufficient coverage, it may not be possible to achieve sublinear regret and fairness violations. They then introduce an information measure and derive matching upper and lower bounds with a rate. The paper also proposes fixed and adaptive explore-then-exploit algorithms, with the adaptive version not requiring prior knowledge of . The authors evaluate their methods on synthetic and structural causal model experiments, where they generally perform better than the baselines in terms of fairness violations and penalized regret.
Critical strengths
I think the main strength of this paper is its theoretical contribution, especially the matching upper and lower bounds for the joint loss from regret and fairness violations. I find the lower-bound results particularly interesting because they show why learning under counterfactual fairness constraints is inherently difficult. The authors show that without sufficient coverage, achieving sublinear joint loss may not be possible. Even with sufficient coverage, identifying fair actions can require costly exploration, leading to an unavoidable rate in the worst case. Another strength is that the paper uses a weaker coverage assumption than prior work, allowing the results to apply to a broader range of problem instances. I also like the adaptive algorithm, which achieves the same leading theoretical rate, up to logarithmic factors, without needing to know the information scale in advance. Overall, I think these are meaningful contributions and provide a good case for acceptance.
Critical weaknesses
My main concern is the difference between the theory and the experiments. In Section 5, the algorithms require a minimum exploration length and use a confidence radius coefficient of . However, Appendix A.1 states that the experiments start with 100 exploration rounds and use a much smaller coefficient of 0.01. I wonder how much it affects the reported results. I also noticed that the baselines use different confidence coefficients. It would be helpful to explain how these values were chosen and whether the results would remain similar under different settings.
I also have a few questions about the theoretical assumptions. The paper assumes that both factual and counterfactual feature maps are known, which might be difficult in real applications. The authors show that some form of coverage is necessary, but I wonder whether the pooled covariance matrix really needs to be full rank. Could coverage only in the directions relevant to rewards and fairness be enough? Also, Theorem 4.2 requires and . Although Theorem 4.1 covers a smaller setting, it would be interesting to know whether the general lower bound, including its dependence on dimension and the number of actions, can be extended to smaller settings. I think discussing these points would help clarify the scope of the results.
Questions for authors
I have some questions for Authors
-
In Section 5, the theoretical analysis requires a minimum exploration length and uses a confidence radius coefficient of . However, Appendix A.1 states that the experiments start with 100 exploration rounds and use a coefficient of 0.01. Could the authors explain why these values were chosen? Would the algorithms show similar regret and fairness violation results with larger confidence radii and exploration lengths?
-
I noticed that the proposed methods and baselines use different confidence coefficients in Appendix A.1. Were these values tuned separately for each method or taken from the original implementations? Could the authors clarify whether the main experimental conclusions remain similar under different parameter settings?
-
In Section 3.1, the authors show that some form of coverage is necessary to guarantee learning, while Assumption 3.1 requires the pooled factual covariance matrix to be full rank. Is this full-rank condition necessary, or is it mainly a sufficient condition used in the analysis? Could coverage only in the directions relevant to rewards and fairness be enough? I think clarifying this would help understand how restrictive the assumption is.
-
Theorem 4.2 establishes general lower bound for and , while Theorem 4.1 already covers a smaller setting with and . Are the restrictions in Theorem 4.2 mainly due to the proof construction? Could the authors clarify whether the general dependence on and is expected to hold for smaller settings as well?
5 comments
- We tested several practical choices through (i) a confidence coefficient sweep, (ii) an initial exploration sweep, and (iii) sweeps of and (Sections A.4, A.5, and A.7). Selected penalized regrets are shown below.
| Setting | Adaptive ETE | Fixed ETE | CCLB | DO-LogB | GLB-OMD |
|---|---|---|---|---|---|
| Synthetic, | |||||
| Synthetic, | |||||
| Synthetic, | |||||
| SCM, |
Our algorithms perform well under several choices, although the best method depends on the setting. At a common , an ETE method has the lowest mean penalized regret at in the synthetic environment and at in the SCM. CCLB is lowest at (synthetic) and (SCM), and DO-LogB at (SCM).
- The theoretical tuning of Fixed ETE uses , which depends on the true parameter. The practical experiments instead use exploration with an empirical coefficient and require neither nor . Our main algorithm, Adaptive ETE, does not require and has lower mean violation and penalized regret than Fixed ETE in the reference SCM experiment.
[W2(a)] I also have a few questions about the theoretical assumptions. The paper assumes that both factual and counterfactual feature maps are known, which can be difficult in real applications.
We thank the reviewer for this interesting question. We added algorithms that estimate counterfactual features during initial exploration and evaluated them in Section A.6. We added a discussion of feature estimation and its limitations to Section C (Discussion).
Given the causal graph and intervention, we fit an SCM with linear conditional means and log scales to the initial exploration contexts. For each new context, Algorithm 3 infers the noise terms from the factual observations, reuses them under the intervention, and applies the factual feature encoder to obtain . Algorithms 4 and 5 replace with this estimate. Initial exploration actions are chosen uniformly, independently of estimated counterfactual features. Inaccurate feature estimates therefore do not affect these actions, and SCM estimation uses the same samples without additional initial exploration.
| Method | Features | Violation (SCM) | Penalized regret (SCM) |
|---|---|---|---|
| Fixed ETE | Known | ||
| Fixed ETE | Estimated | ||
| Adaptive ETE | Known | ||
| Adaptive ETE | Estimated |
The estimated-feature variants achieve very similar violation and penalized regret to their known-feature counterparts (Figure 10). For Adaptive ETE, both mean violation and penalized regret are slightly lower with estimated features.
[W2(b)] The authors show that some form of coverage is necessary, but I wonder whether the pooled covariance matrix really needs to be full rank. Could coverage only in the directions relevant to rewards and fairness be enough?
[Q3] In Section 3.1, the authors show that some form of coverage is necessary to guarantee learning, while Assumption 3.1 requires the pooled factual covariance matrix to be full rank. Is this full-rank condition necessary, or is it mainly a sufficient condition used in the analysis? Could coverage only in the directions relevant to rewards and fairness be enough? I think clarifying this would help understand how restrictive the assumption is.
Full rank in Assumption 3.1 is sufficient for our analysis, but it is not necessary for every learnable instance. Proposition 3.2 shows that learning can fail when factual observations cannot identify a direction that changes counterfactual fairness.
Coverage on a smaller subspace can suffice. If both feature maps lie in a known common subspace and Assumption 3.1 holds on that subspace, we can project onto it. This preserves rewards and fair actions, and our analysis applies in the reduced dimension. We added this coverage discussion to Section C (Discussion).
[W2(c)] Also, Theorem 4.2 requires and . Although Theorem 4.1 covers a smaller setting, it would be interesting to know whether the general lower bound, including its dependence on dimension and the number of actions, can be extended to smaller settings. I think discussing these points would help clarify the scope of the results.
[Q4] Theorem 4.2 establishes the general lower bound for and , while Theorem 4.1 already covers a smaller setting with and . Are the restrictions in Theorem 4.2 mainly due to the proof construction? Could the authors clarify whether the general dependence on and is expected to hold for smaller settings as well?
The restrictions and come from our construction in Section F.1. We use at least four candidate actions for the Fano argument and reserve a constant fraction of actions for informative observations.
These thresholds can likely be reduced by tightening the construction. The packing proof allows replacing by , which reduces the dimension needed for four candidates from to . Using fewer replicas of the informative action could also reduce the action threshold after adjusting the Fisher information bounds. Theorem 4.1 already gives the lower-bound order at , . We expect the construction thresholds to improve, but have not established the full dependence on and for all smaller settings. We added these limitations and possible refinements to Section C (Discussion).
[W1] My main concern is the difference between the theory and the experiments. In Section 5, the algorithms require a minimum exploration length n0 and use a confidence radius coefficient of 11ℓ. However, Appendix A.1 states that the experiments start with 100 exploration rounds and use a much smaller coefficient of 0.01. I wonder how much it affects the reported results. I also noticed that baselines use different confidence coefficients. It would be helpful to explain how these values were chosen and whether the results would remain similar under different settings.
[Q1] In Section 5, the theoretical analysis requires a minimum exploration length n0 and uses a confidence radius coefficient of 11ℓ. However, Appendix A.1 states that the experiments start with 100 exploration rounds and use a coefficient of 0.01. Could the authors explain why these values were chosen? Would the algorithms show similar regret and fairness violation results with larger confidence radii and exploration lengths?
[Q2] I noticed that the proposed methods and baselines use different confidence coefficients in Appendix A.1. Were these values tuned separately for each method or taken from the original implementations? Could the authors clarify whether the main experimental conclusions remain similar under different parameter settings?
We thank the reviewer for pointing out that our original experiments did not match the theory. The original 100-round initialization and coefficient 0.01 were empirical choices. For a fair comparison, the revised experiments use the same c for every algorithm and sweep it. We added experiments with theoretical and practical choices in Section A to evaluate the practical value of our algorithms. We added a discussion of theoretical and practical parameter choices to Section C (Discussion).
Our algorithms run much faster than the baselines in these experiments. To reduce the cost of CCLB and DO-LogB, all subsequent experiments use solvers that start from the previous solution and use the same fixed iteration limits for both methods.
Both ETE methods have lower mean penalized regret than all three baselines in both environments.