acceptodds
Under review as a conference paper at ICLR 2027

Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness

Abstract

We study causal logistic bandits with counterfactual fairness constraints. The causal structure is given through known factual and counterfactual feature maps that share an unknown logistic reward parameter, but the learner observes only factual rewards. Consequently, the directions determining counterfactual feasibility need not be identifiable from the available feedback. The closest prior analyses either omit a coverage condition or impose a comparatively strong one, and do not establish matching lower bounds. We first show that some coverage condition is necessary: without a coverage-type restriction, factually indistinguishable environments with different optimal fair actions force expected joint loss. Under a weaker full-rank condition on the factual covariance pooled across actions, we identify a target-specific information scale that measures the difficulty of estimating rewards and counterfactual effects from factual feedback. We construct worst-case families satisfying this condition on which every policy incurs expected joint loss . We also give an explore–then–exploit procedure tuned using and an adaptive algorithm that does not require its value. Both algorithms achieve , where is regret relative to the best fair action and denotes the cumulative stage-wise positive violations. Thus the upper and lower bounds match in their leading dependence on , , and , up to logarithmic factors.

Primary area:
reinforcement learning
Keywords:
bandits, logistic bandits, fairness, fairness constraint, counterfactual fairness

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_fdPVOpenReview ↗
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 V⋆V_\star and derive matching upper and lower bounds with a T2/3T^{2/3} rate. The paper also proposes fixed and adaptive explore-then-exploit algorithms, with the adaptive version not requiring prior knowledge of V⋆V_\star. 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 T2/3T^{2/3} 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 n0n_0 and use a confidence radius coefficient of 11ℓ11\sqrt{\ell}. 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 d≥46d \geq 46 and K≥8K \geq 8. 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

  1. In Section 5, the theoretical analysis requires a minimum exploration length n0n_0 and uses a confidence radius coefficient of 11ℓ11\sqrt{\ell}. 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?

  2. 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?

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

  4. Theorem 4.2 establishes general lower bound for d≥46d \geq 46 and K≥8K \geq 8, while Theorem 4.1 already covers a smaller setting with d=2d=2 and K=3K=3. Are the restrictions in Theorem 4.2 mainly due to the proof construction? Could the authors clarify whether the general dependence on dd and KK is expected to hold for smaller settings as well?

5 comments

[W1] My main concern is the difference between the theory and the experiments. In Section 5, the algorithms require a minimum exploration length n0n_0 and use a confidence radius coefficient of 11ℓ11\sqrt{\ell}. 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 n0n_0 and uses a confidence radius coefficient of 11ℓ11\sqrt{\ell}. 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 100100-round initialization and coefficient 0.010.01 were empirical choices. For a fair comparison, the revised experiments use the same cc 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).

  • We first refined conservative constants in the proofs to reduce the required initial exploration (Section 5). We then ran both algorithms with the theoretical confidence and exploration choices at T=2,000,000T=2{,}000{,}000 (Section A.3).
MethodViolation (Synthetic)Penalized regret (Synthetic)Time (s)
Adaptive ETE24864.5±16.9\boldsymbol{24864.5\pm16.9}346431.5±292.9‾\underline{346431.5\pm292.9}174.8±1.0‾\underline{174.8\pm1.0}
Fixed ETE55914.5±89.155914.5\pm89.1489309.9±400.8489309.9\pm400.8102.0±0.3\boldsymbol{102.0\pm0.3}
CCLB47203.8±155.2‾\underline{47203.8\pm155.2}336980.4±410.7\boldsymbol{336980.4\pm410.7}2657.9±3.22657.9\pm3.2
DO-LogB81451.4±196.681451.4\pm196.6521497.9±684.1521497.9\pm684.11668.2±103.01668.2\pm103.0
GLB-OMD97616.6±33.397616.6\pm33.3557363.5±370.5557363.5\pm370.5493.4±6.5493.4\pm6.5

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.

  • We also conducted practical experiments. We replaced the confidence coefficient with the same constant cc for every algorithm. For Fixed ETE and Adaptive ETE, we set m=min⁡{T,⌈8C2T2/3⌉}m=\min\{T,\lceil8C_2T^{2/3}\rceil\} and ninit=min⁡{T,⌈C2T2/3⌉}n_{\mathrm{init}}=\min\{T,\lceil C_2T^{2/3}\rceil\}. The reference experiments use T=10,000T=10{,}000, c=1c=1, and C2=1/4C_2=1/4.
MethodViolation (Synthetic)Penalized regret (Synthetic)Violation (SCM)Penalized regret (SCM)
Adaptive ETE141.4±13.7‾\underline{141.4\pm13.7}1639.1±161.0‾\underline{1639.1\pm161.0}1.045±0.131\boldsymbol{1.045\pm0.131}724.8±58.1\boldsymbol{724.8\pm58.1}
Fixed ETE112.5±25.1\boldsymbol{112.5\pm25.1}1561.5±191.2\boldsymbol{1561.5\pm191.2}1.128±0.1491.128\pm0.149737.7±68.1‾\underline{737.7\pm68.1}
CCLB249.5±21.9249.5\pm21.91748.6±97.41748.6\pm97.41.092±0.079‾\underline{1.092\pm0.079}996.0±57.3996.0\pm57.3
DO-LogB268.0±14.5268.0\pm14.52182.1±55.62182.1\pm55.61.207±0.0531.207\pm0.053743.4±30.8743.4\pm30.8
GLB-OMD486.2±5.3486.2\pm5.32781.7±15.72781.7\pm15.71.231±0.0531.231\pm0.053757.6±23.8757.6\pm23.8

Both ETE methods have lower mean penalized regret than all three baselines in both environments.

  • We tested several practical choices through (i) a confidence coefficient sweep, (ii) an initial exploration sweep, and (iii) sweeps of ρ\rho and τ\tau (Sections A.4, A.5, and A.7). Selected penalized regrets are shown below.
SettingAdaptive ETEFixed ETECCLBDO-LogBGLB-OMD
Synthetic, c=0.1c=0.1897.7±667.1‾\underline{897.7\pm667.1}708.9±241.5\boldsymbol{708.9\pm241.5}1923.7±123.01923.7\pm123.01546.9±57.31546.9\pm57.32784.5±16.42784.5\pm16.4
Synthetic, C2=2C_2=21644.4±155.5\boldsymbol{1644.4\pm155.5}2852.5±77.82852.5\pm77.81748.6±97.4‾\underline{1748.6\pm97.4}2182.1±55.62182.1\pm55.62781.7±15.72781.7\pm15.7
Synthetic, ρ=1/4\rho=1/41826.6±118.0‾\underline{1826.6\pm118.0}1912.0±207.41912.0\pm207.41768.2±113.1\boldsymbol{1768.2\pm113.1}2244.2±59.82244.2\pm59.82786.0±18.52786.0\pm18.5
SCM, τ=0.002\tau=0.002658.2±19.1\boldsymbol{658.2\pm19.1}664.7±21.1664.7\pm21.1826.6±64.1826.6\pm64.1660.1±21.3‾\underline{660.1\pm21.3}662.6±20.2662.6\pm20.2

Our algorithms perform well under several choices, although the best method depends on the setting. At a common cc, an ETE method has the lowest mean penalized regret at c∈{0.01,0.1,1}c\in\{0.01,0.1,1\} in the synthetic environment and at c∈{0.01,1,100}c\in\{0.01,1,100\} in the SCM. CCLB is lowest at c∈{10,100}c\in\{10,100\} (synthetic) and c=10c=10 (SCM), and DO-LogB at c=0.1c=0.1 (SCM).

  • The theoretical tuning of Fixed ETE uses V⋆V_\star, which depends on the true parameter. The practical experiments instead use T2/3T^{2/3} exploration with an empirical coefficient and require neither θ⋆\theta^\star nor V⋆V_\star. Our main algorithm, Adaptive ETE, does not require V⋆V_\star 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 ϕ^G\widehat\phi^G. Algorithms 4 and 5 replace ϕG\phi^G 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.

MethodFeaturesViolation (SCM)Penalized regret (SCM)
Fixed ETEKnown1.1276±0.14891.1276\pm0.1489737.7±68.1737.7\pm68.1
Fixed ETEEstimated1.1284±0.14581.1284\pm0.1458739.0±63.7739.0\pm63.7
Adaptive ETEKnown1.0454±0.1309‾\underline{1.0454\pm0.1309}724.8±58.1‾\underline{724.8\pm58.1}
Adaptive ETEEstimated0.9940±0.1384\boldsymbol{0.9940\pm0.1384}705.0±63.5\boldsymbol{705.0\pm63.5}

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 d≥46d\ge46 and K≥8K\ge8. 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 d≥46d\ge46 and K≥8K\ge8, while Theorem 4.1 already covers a smaller setting with d=2d=2 and K=3K=3. Are the restrictions in Theorem 4.2 mainly due to the proof construction? Could the authors clarify whether the general dependence on dd and KK is expected to hold for smaller settings as well?

The restrictions d≥46d\ge46 and K≥8K\ge8 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 e(d−1)/32e^{(d-1)/32} by e(d−1)/16e^{(d-1)/16}, which reduces the dimension needed for four candidates from 4646 to 2424. 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 V⋆1/3T2/3V_\star^{1/3}T^{2/3} lower-bound order at d=2d=2, K=3K=3. We expect the construction thresholds to improve, but have not established the full dependence on dd and KK for all smaller settings. We added these limitations and possible refinements to Section C (Discussion).

Reviewer_grXUOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies causal logistic bandits under counterfactual fairness constraints. The authors point out an identification issue in prior work and establish the necessity of a coverage condition for achieving both sublinear regret and fairness violation. Under the coverage condition, they derive minimax lower bounds with a matching explore-then-exploit algorithm.

Overall, this is a well-written paper with theoretical insights.

Critical strengths

By constructing a counterexample, the authors demonstrate the necessity of appropriate coverage for simultaneously achieving sublinear regret and fairness violation, addressing a theoretical gap in prior work.

The theoretical part is sound. The information complexity measure V⋆V_\star characterizes the difficulty of learning counterfactual fairness constraints. The matching O~(T2/3)\widetilde{O}(T^{2/3}) upper and lower bounds are interesting.

The authors further propose an adaptive choice of the exploration length that does require prior knowledge of V⋆V_\star with a theoretical guarantee.

Critical weaknesses

The lower-bound construction chooses a fairness threshold τ\tau that scales as T−1/3T^{-1/3}. It is unclear whether the same minimax rate holds for a general fixed positive fairness threshold independent of TT.

Different from the theoretical radius coefficient and exploration length in the main text, the experimental implementation uses empirical choices instead. Additionally, different radius coefficients are selected for different baselines.

The proposed methods assume that counterfactual feature maps are known, which may be unrealistic in practical applications without the knowledge of the underlying causal structure and potentially unobserved variables. The paper does not address how these features can be identified or estimated, which may limit its practical applicability.

Questions for authors

Can the authors establish the lower bound for a fixed fairness threshold τ\tau independent of TT?

How sensitive are the empirical results to the confidence radius and exploration length? Would the improvements persist under comparable hyperparameter tuning across baselines?

3 comments

[W1] The lower-bound construction chooses a fairness threshold τ\tau that scales as T−1/3T^{-1/3}. It is unclear whether the same minimax rate holds for a general fixed positive fairness threshold independent of TT.

[Q1] Can the authors establish the lower bound for a fixed fairness threshold τ\tau independent of TT?

We have not established the minimax lower bound for an arbitrary fixed positive τ\tau. In our two-environment construction (Section E.1), the high-reward action HH satisfies

|\Delta_1(H)|=\mu(\alpha)-\frac12\le\frac{\alpha}{4}.$$ The proof chooses $\alpha\asymp T^{-1/3}$ when the other parameters are fixed. For fixed $\tau>0$, eventually $\alpha/4\le\tau$. Then $H$ is fair and optimal in both environments, so always choosing it has zero regret and violation. The lower-bound argument no longer applies. The same issue occurs in the general construction, where the candidate actions' effects are also of order $\alpha$. An extension would require a construction with effects on both sides of the fixed threshold while keeping the environments difficult to distinguish. We find the reviewer's question very interesting and leave it for future work. We added this limitation to **Section C (Discussion)**. ### **[W2] Different from the theoretical radius coefficient and exploration length in the main text, the experimental implementation uses empirical choices instead. Additionally, different radius coefficients are selected for different baselines.** ### **[Q2] How sensitive are the empirical results to the confidence radius and exploration length? Would the improvements persist under comparable hyperparameter tuning across baselines?** We added experiments with theoretical and practical choices in **Section A** to address the difference from the theory and sensitivity to parameter choices. - We first refined conservative constants in the proofs to reduce the required initial exploration (**Section 5**). We then ran both algorithms with the theoretical confidence and exploration choices at $T=2{,}000{,}000$ (**Section A.3**). In that synthetic experiment, Adaptive ETE has the lowest mean violation, while CCLB has the lowest mean penalized regret. In subsequent experiments, the CCLB and DO-LogB solvers use the same fixed iteration limits. - For the practical experiments, we replaced the confidence coefficient by the same constant $c$ for every algorithm. For our algorithms, we set $m=\min\{T,\lceil8C_2T^{2/3}\rceil\}$ and $n_{\mathrm{init}}=\min\{T,\lceil C_2T^{2/3}\rceil\}$. The reference results are below. | Method | Violation (Synthetic) | Penalized regret (Synthetic) | Violation (SCM) | Penalized regret (SCM) | |---|---:|---:|---:|---:| | **Adaptive ETE** | $\underline{141.4\pm13.7}$ | $\underline{1639.1\pm161.0}$ | $\boldsymbol{1.045\pm0.131}$ | $\boldsymbol{724.8\pm58.1}$ | | **Fixed ETE** | $\boldsymbol{112.5\pm25.1}$ | $\boldsymbol{1561.5\pm191.2}$ | $1.128\pm0.149$ | $\underline{737.7\pm68.1}$ | | CCLB | $249.5\pm21.9$ | $1748.6\pm97.4$ | $\underline{1.092\pm0.079}$ | $996.0\pm57.3$ | | DO-LogB | $268.0\pm14.5$ | $2182.1\pm55.6$ | $1.207\pm0.053$ | $743.4\pm30.8$ | | GLB-OMD | $486.2\pm5.3$ | $2781.7\pm15.7$ | $1.231\pm0.053$ | $757.6\pm23.8$ | Both ETE methods have lower mean penalized regret than all three baselines in both environments at $c=1$. - We evaluated every algorithm at $c\in\{0.01,0.1,1,10,100\}$ (**Section A.4**). For our algorithms, we varied $C_2\in\{1/8,1/4,1/2,1,2\}$ (**Section A.5**). We also varied $\tau$ and $\rho$ (**Section A.7**). Selected penalized regret results are below. | Setting | **Adaptive ETE** | **Fixed ETE** | CCLB | DO-LogB | GLB-OMD | |---|---:|---:|---:|---:|---:| | Synthetic, $c=0.1$ | $\underline{897.7\pm667.1}$ | $\boldsymbol{708.9\pm241.5}$ | $1923.7\pm123.0$ | $1546.9\pm57.3$ | $2784.5\pm16.4$ | | Synthetic, $C_2=2$ | $\boldsymbol{1644.4\pm155.5}$ | $2852.5\pm77.8$ | $\underline{1748.6\pm97.4}$ | $2182.1\pm55.6$ | $2781.7\pm15.7$ | | Synthetic, $\rho=1/4$ | $\underline{1826.6\pm118.0}$ | $1912.0\pm207.4$ | $\boldsymbol{1768.2\pm113.1}$ | $2244.2\pm59.8$ | $2786.0\pm18.5$ | | SCM, $\tau=0.002$ | $\boldsymbol{658.2\pm19.1}$ | $664.7\pm21.1$ | $826.6\pm64.1$ | $\underline{660.1\pm21.3}$ | $662.6\pm20.2$ | Our algorithms perform well under several choices, but the best method depends on the setting. At a common $c$, an ETE method has the lowest mean penalized regret at $c\in\{0.01,0.1,1\}$ in the synthetic environment and at $c\in\{0.01,1,100\}$ in the SCM. CCLB is lowest at $c\in\{10,100\}$ (synthetic) and $c=10$ (SCM), and DO-LogB at $c=0.1$ (SCM).

[W3] The proposed methods assume that counterfactual feature maps are known, which may be unrealistic in practical applications without the knowledge of the underlying causal structure and potentially unobserved variables. The paper does not address how these features can be identified or estimated, which may limit its practical applicability.

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 ϕ^G\widehat\phi^G. Algorithms 4 and 5 replace ϕG\phi^G 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.

MethodFeaturesViolation (SCM)Penalized regret (SCM)
Fixed ETEKnown1.1276±0.14891.1276\pm0.1489737.7±68.1737.7\pm68.1
Fixed ETEEstimated1.1284±0.14581.1284\pm0.1458739.0±63.7739.0\pm63.7
Adaptive ETEKnown1.0454±0.1309‾\underline{1.0454\pm0.1309}724.8±58.1‾\underline{724.8\pm58.1}
Adaptive ETEEstimated0.9940±0.1384\boldsymbol{0.9940\pm0.1384}705.0±63.5\boldsymbol{705.0\pm63.5}

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.

Thank you for the additional experiments. I remain supportive of the paper and will keep my rating at 3 (weak acceptance).

Reviewer_CbhbOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper consider a logistic bandit with a fairness constraint on a counterfactual outcome. The factual and counterfactual feature maps share one unknown parameter, and only factual rewards are observed, so the counterfactual outcome used to check fairness is never seen. The goal is to keep both regret against the best fair action and cumulative fairness violation small.

The paper shows three things. First, a coverage condition is necessary: an explicit small example has statistically identical data under two environments while the best fair action differs, so every policy loses linearly. Second, under a pooled full-rank coverage condition, worst-case instances force loss of order the two-thirds power of the horizon, scaled by a new quantity that measures how hard the reward and fairness directions are to learn from factual data, and limited by the smaller of the logarithm of the number of actions and the dimension. Third, two explore-then-exploit algorithms achieve the same order — one tuned with that scale, one adaptive that does not need it — each up to logarithms and an additive burn-in. Validation is by proof, plus two simulated experiments.

Critical strengths

The two-environment example has statistically identical data but a different best fair action, so no policy avoids linear loss; an assumption the literature makes is turned into the proven boundary of what is learnable. It explains why earlier guarantees could not simply be improved, and it tells future work exactly which assumption to attack.

Critical weaknesses

The theory does not apply to the reported experiments. The theorems assume the initial estimation block is shorter than the horizon. With the paper's own settings that block is about 1070 times the horizon, the theorem would prescribe exploring the whole horizon. The experiments run a different algorithm: exploration stops after about 1200 rounds, the confidence coefficient is 0.01 against baselines' 2 and 0.25, one variant uses the true parameter and cannot be run online, the horizon is never varied, and the supplement has only plotting code. This is the weakness that most constrains my rating: the only empirical support for the bounds comes from a setting and an algorithm the theorems do not cover, so the practical value of the new scale, and the size of its constants, stay untested.

Questions for authors

What setting would bring the experiments inside the assumptions — a longer horizon, a rescaled instance?

2 comments

[W1] The theory does not apply to the reported experiments. The theorems assume the initial estimation block is shorter than the horizon. With the paper's own settings that block is about 1070 times the horizon, the theorem would prescribe exploring the whole horizon. The experiments run a different algorithm: exploration stops after about 1200 rounds, the confidence coefficient is 0.01 against baselines' 2 and 0.25, one variant uses the true parameter and cannot be run online, the horizon is never varied, and the supplement has only plotting code. This is the weakness that most constrains my rating: the only empirical support for the bounds comes from a setting and an algorithm the theorems do not cover, so the practical value of the new scale, and the size of its constants, stay untested.

[Q1] What setting would bring the experiments inside the assumptions - a longer horizon, a rescaled instance?

We thank the reviewer for pointing out that our original experiments did not match the theory. 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).

  • We first refined conservative constants in the proofs to reduce the required initial exploration (Section 5). We then ran both algorithms with the theoretical confidence and exploration choices at T=2,000,000T=2{,}000{,}000 (Section A.3).
MethodViolation (Synthetic)Penalized regret (Synthetic)Time (s)
Adaptive ETE24864.5±16.9\boldsymbol{24864.5\pm16.9}346431.5±292.9‾\underline{346431.5\pm292.9}174.8±1.0‾\underline{174.8\pm1.0}
Fixed ETE55914.5±89.155914.5\pm89.1489309.9±400.8489309.9\pm400.8102.0±0.3\boldsymbol{102.0\pm0.3}
CCLB47203.8±155.2‾\underline{47203.8\pm155.2}336980.4±410.7\boldsymbol{336980.4\pm410.7}2657.9±3.22657.9\pm3.2
DO-LogB81451.4±196.681451.4\pm196.6521497.9±684.1521497.9\pm684.11668.2±103.01668.2\pm103.0
GLB-OMD97616.6±33.397616.6\pm33.3557363.5±370.5557363.5\pm370.5493.4±6.5493.4\pm6.5

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.

  • We also conducted practical experiments. We replaced the confidence coefficient with the same constant cc for every algorithm. For Fixed ETE and Adaptive ETE, we set m=min⁡{T,⌈8C2T2/3⌉}m=\min\{T,\lceil8C_2T^{2/3}\rceil\} and ninit=min⁡{T,⌈C2T2/3⌉}n_{\mathrm{init}}=\min\{T,\lceil C_2T^{2/3}\rceil\}. The reference experiments use T=10,000T=10{,}000, c=1c=1, and C2=1/4C_2=1/4.
MethodViolation (Synthetic)Penalized regret (Synthetic)Violation (SCM)Penalized regret (SCM)
Adaptive ETE141.4±13.7‾\underline{141.4\pm13.7}1639.1±161.0‾\underline{1639.1\pm161.0}1.045±0.131\boldsymbol{1.045\pm0.131}724.8±58.1\boldsymbol{724.8\pm58.1}
Fixed ETE112.5±25.1\boldsymbol{112.5\pm25.1}1561.5±191.2\boldsymbol{1561.5\pm191.2}1.128±0.1491.128\pm0.149737.7±68.1‾\underline{737.7\pm68.1}
CCLB249.5±21.9249.5\pm21.91748.6±97.41748.6\pm97.41.092±0.079‾\underline{1.092\pm0.079}996.0±57.3996.0\pm57.3
DO-LogB268.0±14.5268.0\pm14.52182.1±55.62182.1\pm55.61.207±0.0531.207\pm0.053743.4±30.8743.4\pm30.8
GLB-OMD486.2±5.3486.2\pm5.32781.7±15.72781.7\pm15.71.231±0.0531.231\pm0.053757.6±23.8757.6\pm23.8

Both ETE methods have lower mean penalized regret than all three baselines in both environments.

  • We tested several practical choices through (i) a confidence coefficient sweep, (ii) an initial exploration sweep, and (iii) sweeps of ρ\rho and τ\tau (Sections A.4, A.5, and A.7). Selected penalized regrets are shown below.
SettingAdaptive ETEFixed ETECCLBDO-LogBGLB-OMD
Synthetic, c=0.1c=0.1897.7±667.1‾\underline{897.7\pm667.1}708.9±241.5\boldsymbol{708.9\pm241.5}1923.7±123.01923.7\pm123.01546.9±57.31546.9\pm57.32784.5±16.42784.5\pm16.4
Synthetic, C2=2C_2=21644.4±155.5\boldsymbol{1644.4\pm155.5}2852.5±77.82852.5\pm77.81748.6±97.4‾\underline{1748.6\pm97.4}2182.1±55.62182.1\pm55.62781.7±15.72781.7\pm15.7
Synthetic, ρ=1/4\rho=1/41826.6±118.0‾\underline{1826.6\pm118.0}1912.0±207.41912.0\pm207.41768.2±113.1\boldsymbol{1768.2\pm113.1}2244.2±59.82244.2\pm59.82786.0±18.52786.0\pm18.5
SCM, τ=0.002\tau=0.002658.2±19.1\boldsymbol{658.2\pm19.1}664.7±21.1664.7\pm21.1826.6±64.1826.6\pm64.1660.1±21.3‾\underline{660.1\pm21.3}662.6±20.2662.6\pm20.2

Our algorithms perform well under several choices, although the best method depends on the setting.

  • The theoretical tuning of Fixed ETE uses V⋆V_\star, which depends on the true parameter. The practical experiments instead use T2/3T^{2/3} exploration with an empirical coefficient and require neither θ⋆\theta^\star nor V⋆V_\star. Our main algorithm, Adaptive ETE, does not require V⋆V_\star and has lower mean violation and penalized regret than Fixed ETE in the reference SCM experiment.

  • Thank you for pointing out the code upload error. We corrected the supplementary package and included the full experiment code.

Dear Reviewer Cbhb, Thank you for your careful review. We have addressed each of your comments and questions in our rebuttal and would be grateful if you could take a look when you have a chance. Thanks, Authors

Comments on the paper

1 comment

We apologize for the delay in posting our response. The additional experiments took longer to complete than we expected. We have taken care to address each of your comments and questions in our rebuttal and would be grateful if you could review it when you have a chance.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.