Towards Fair Sequential Decision-Making: A Causal Decomposition Approach

Summary

The paper studies online contextual bandits under fairness constraints defined via Plečko–Bareinboim structural counterfactual measures — the counterfactual direct, indirect and spurious effects (Ctf-DE, Ctf-IE, Ctf-SE) — that jointly decompose the total-variation gap between two demographic groups. Rather than folding all pathway effects into one CATE-based constraint (as in the closest prior work of Chen et al., 2025), the authors treat the three pathway-level effects as separate long-term constraints, and design two algorithms: an ε-greedy OMD scheme for non-parametric contextual bandits (Algorithm 1) and a doubly-optimistic OMD-based method for parametric logistic bandits (Algorithm 2). Both achieve sublinear regret and sublinear cumulative constraint-violation bounds without Slater's condition and without a per-round cost that grows in $t$: the logistic version attains $O(1)$ per-round time, matching the state of the art for unconstrained logistic bandits. The conceptual contribution is a genuine advance: replacing pathway-agnostic CATE with a mechanism-level decomposition converts fairness from a single scalar to a vector of interpretable direct/indirect/spurious constraints — a formulation aligned with legal frameworks (disparate impact) and better suited to catching pathway-level discrimination that would be invisible to a single-scalar constraint whose components cancel. The main methodological move — a doubly-optimistic feasibility set combined with an ε-greedy explorer that keeps every context/action pair sampled enough to certify counterfactual feasibility — is technically sound and non-trivial, particularly the convex construction of the estimated feasible set for the non-convex sigmoid link. The dominant conceptual limitation is that the theory rests on strong assumptions: the mediator/confounder conditionals are treated as known to the learner (Assumption 3), and coverage is required over every counterfactual context (Assumption 2). The empirical evaluation is a single synthetic SCM and is compromised by an unfortunate parameter choice: the prescribed $\theta^\star = (\sqrt{1/2}, 0, 0, \sqrt{1/2})$ zeroes out the mediator/confounder reward coefficients, so the true Ctf-IE and Ctf-SE are identically zero. The mechanism the method is designed to control does not exist in the experiment, and the headline claim that DO-LogB dominates CCLB in penalized regret does not reproduce.

Strengths

• Conceptual contribution. Replacing CATE with a signed pathway-level decomposition (DE/IE/SE) is a meaningful step for online fairness: it distinguishes the mechanisms behind an observed disparity and is aligned with the mediation-inconsistency argument of MacKinnon et al. (2000) and the causal-fairness framework of Plečko & Bareinboim (2024).
• Non-trivial technical construction. The doubly-optimistic estimated feasible set $\hat\Pi^f_t$ is built to be both an outer bound on the true feasible set (Proposition 5) and convex in $\pi$, despite the non-convex sigmoid link. The corresponding LCB/UCB Lipschitz bounds in the constraint-violation proof are careful and clearly separate factual and counterfactual contributions.
• Improved complexity over the closest baseline. The $O(1)$ per-round cost via the OMD estimator is a substantive practical improvement over the $O(t)$ per-round cost of CCLB (Chen et al., 2025), and the analysis avoids Slater's-margin dependence in the regret bound (Remark 2). This gap is visible in the reproduced running-time plot: CCLB is roughly 3× slower than DO-LogB and about 16× slower than the unconstrained GLB-OMD baseline at $T=10{,}000$.
• Clean handling of the multi-constraint case. The three simultaneous fairness constraints (DE/IE/SE) are handled without an $m$-blowup in the leading rate, matching the paper's motivational claim that pathway-level fairness should not cost the learner in regret order.
• Well-scoped assumption comparison. Table 1 places the results in context (F-UCB, CCLB, Bernasconi et al., etc.) and honestly flags that the paper's regime differs on constraint feedback and factual/counterfactual context structure.
• Causal decomposition reproduces exactly. For Example 1 the identification formulas reproduce to floating-point precision: TV=0.078, CATE=0.05, Ctf-DE=0.05, Ctf-IE=−0.28, Ctf-SE=0.252, and the Proposition 1 identity TV = Ctf-DE − Ctf-IE − Ctf-SE closes to ~10⁻¹⁶.

Weaknesses

• Empirical section is trivialized by the paper's own $\theta^\star$ choice. With the prescribed $\theta^\star = (\sqrt{1/2}, 0, 0, \sqrt{1/2})$ and identity feature map, the mediator and confounder reward coefficients are exactly zero, so the true Ctf-IE and Ctf-SE are identically zero and CATE coincides with Ctf-DE. Two of the three pathway constraints DO-LogB is designed to enforce are trivially satisfied in the experiment, and the single-constraint CCLB baseline targets the same effective quantity as DO-LogB's direct-effect constraint. The main methodological advance — that decomposing TV into DE/IE/SE is preferable to a single CATE constraint — is not tested by this experiment. This is the underlying reason the headline penalized-regret claim does not hold up.
• Fairness label in the conclusion is wrong. The conclusion says the paper achieves 'individual fairness', but Ctf-DE/IE/SE are group-level counterfactual disparity measures. The rest of the paper correctly frames this as demographic-parity-style causal fairness. 'Individual fairness' is a distinct notion with its own literature (Dwork et al.).
• The results paragraph is internally contradictory. The sentence 'there is a large gap between our method (CCLB) and the methods of GLMUCB, GLM-OMD, and CCLB' both misidentifies CCLB as 'our method' and lists CCLB as a competitor in the same sentence, with the wrong algorithm name GLM-OMD vs. the paper's consistent GLB-OMD. A reader cannot reliably attribute Figure 2a's curves without cross-referencing the caption.
• 'Consistently dominates the Best-fair oracle' is either wrong or hides a violation. By construction, the best fair policy upper-bounds constrained-optimal cumulative reward. A constrained learner 'consistently dominating' it points to either a mislabeled oracle or to DO-LogB earning reward on rounds where its own constraints are violated. 'Best-fair oracle' is also introduced without prior definition.
• Assumption 3 (known conditionals) is strong and its impact is not analyzed. Assumption 3 treats $P(m|a,w)$, $P(w|a)$, $P(m|a',w)$, $P(w|a')$ as known. This offloads all causal identification onto pre-existing knowledge; the bounds should be read as guarantees for the online reward-learning subproblem given correct causal priors. The paper does not analyze robustness to misspecified conditionals or to plug-in estimates from an offline batch — which is what a deployment would actually use.
• Counterfactual-context coverage is asserted only in prose. Assumption 2 quantifies over factual $(a,w,m)$, but the discussion silently extends it to the counterfactual configuration $(a',w,m)$ with intervened attribute but factual mediator/confounder. Whether a single $\gamma_1$ over the factual joint implies the analogous bound for the counterfactual configuration is nontrivial and not proven.
• Horizon condition $\gamma_1 T \gtrsim 1$ is not carried into the theorems. The prose says the guarantees are meant for $T$ large enough that every context is observed. That is not stated as a hypothesis in Theorems 1/2; if $|X|$ is exponentially large, $\gamma_1 \sim 1/|X|$ and $\gamma_1 T \gtrsim 1$ silently requires $T \gtrsim |X|$.
• Proof-vs-algorithm mismatch on the sampling distribution. Part (iii) of the Algorithm 1 regret proof is written for $d_t \sim \pi_{X_t}$, whereas the algorithm actually samples from the mixture $\tilde\pi_{X_t}$. The parenthetical acknowledges the gap but does not close it.
• Constraint semantics: $\mathbb{E}[|\Delta|]$ vs. $|\mathbb{E}[\Delta]|$ is left implicit. The feasibility set puts the absolute value inside the expectation over decisions, which is strictly stronger than a policy-averaged signed effect and is not the same object as the signed decomposition in Proposition 1. This modeling choice is not discussed.
• Only one synthetic experiment and no ablations. The empirical study is a single Bernoulli SCM with three fixed constraints and an unstated $\omega_2$. There is no ablation over the exploration exponents $\omega, \omega_2$ (whose trade-off Remark 2 highlights), no sweep over the number of constraints (which the theory claims is free), and no semi-realistic dataset. Given the motivating example is legal-fairness-in-recommendation, at least one dataset closer to that setting would strengthen the empirical story.
• Presentation defects. The Section 5 material appears interleaved with the header, Definition 3's $\kappa$ direction is ambiguous (described as $O(e^S)$ yet used as $\dot\sigma \ge 1/\kappa$), a stray π_4 appears in the Bregman-projection step, the Appendix D spurious-effect derivation is labeled 'the indirect effect', a subscript typo n_{a', d, w, w} appears in the bonus, and the mean-value bound |σ̇(ζ)| ≤ 1 could be tightened to ≤ 1/4 (aligning with the paper's own curvature-exploiting narrative).

Reproducibility & code

• Headline aggregate did not reproduce. The paper's central empirical claim — DO-LogB achieves substantially lower penalized cumulative regret than the three baselines, with the gap growing over the horizon — did not hold in an independent reconstruction that used the paper's prescribed SCM and $\theta^\star$. At $T=10{,}000$ averaged over 16 replications, the endpoints were CCLB 456, DO-LogB 541, GLB-OMD 561, GLM-UCB 561. DO-LogB is not distinguishably best (per-seed std ~417), and the supporting sentence that 'CCLB has even larger penalized regret than both unconstrained baselines' inverts: CCLB is the best of the three by a clear margin.
• Root cause is a paper-side design flaw, not a replication artifact. With $\theta^\star = (\sqrt{1/2}, 0, 0, \sqrt{1/2})$, the reward depends only on $A$ and $D$; the true Ctf-IE and Ctf-SE evaluate to zero (~5×10⁻¹⁷) and CATE equals Ctf-DE. So DO-LogB's mechanism-level constraints reduce to what CCLB's CATE-based constraint already enforces, and DO-LogB has no advantage to demonstrate. No honest re-run can close this gap without changing $\theta^\star$ or the feature map.
• Causal computations reproduce exactly. The Example 1 identification formulas produce TV=0.078, CATE=0.05, Ctf-DE=0.05, Ctf-IE=−0.28, Ctf-SE=0.252 to floating-point precision, and the Proposition 1 decomposition identity closes to ~10⁻¹⁶.
• Code repository is a placeholder. The paper prints a GitHub URL as the code artifact, but the release contains only a Coming soon! README (the cited upstream URL is likewise empty). The entire ~864-line experimental harness — DO-LogB, CCLB, GLB-OMD, GLM-UCB, environment, plotting — had to be reimplemented from the paper text.
• Four undocumented tuning constants required to make DO-LogB function. Reconstruction needed (i) a bonus scale (CB_SCALE=0.02) to place the optimism bonus on the probability scale — without it the constraint never binds; (ii) an exploration constant (EPS_SCALE=0.05) on top of $\epsilon_{2,t}=t^{-\omega_2}$ — without it DO-LogB accumulates more violations than the unconstrained baselines; (iii) a practical confidence radius replacing the theoretical $\gamma_t(\alpha)$ from Proposition 4, which evaluates to ~23 and saturates the sigmoid; (iv) the decision support $D \sim \mathrm{Uniform}[-3,3]$, which the paper never specifies but which governs the reward/fairness tension. None is a deep flaw individually, but a reproducer must diagnose that the constrained method is silently collapsing to the unconstrained one and then re-derive several undocumented constants.
• Supporting empirical claims reproduce or partially reproduce. The running-time ordering (CCLB slowest at 76.6 s; GLB-OMD fastest at 4.7 s; DO-LogB at 25.4 s) matches the paper. Cumulative rewards versus the 'Best-fair' oracle match qualitatively (DO-LogB sits at or above the oracle throughout, so the interpretive concern about that oracle remains). Cumulative-violation curves partially match: DO-LogB does grow sublinearly (late slope 0.118) while the unconstrained baselines grow near-linearly (0.415), but CCLB also plateaus (0.124) rather than growing linearly as the accompanying text suggests — a direct consequence of the trivializing $\theta^\star$.
• Key hyperparameters are absent. The exploration exponents $\omega,\omega_2$, confidence level $\alpha$, learning rate $\eta$, and regularizer $\lambda$ that produced Figures 2 and 4 are not stated, nor are the baseline (CCLB, GLB-OMD, GLM-UCB) settings. The 'Best-fair oracle' and 'cumulative constraint violation' are defined verbally; the exact feasibility tolerance, per-round vs. population computation, and max-vs-sum aggregation are unspecified. The 16 replications' seed list and shaded-band convention are also missing.

Recommended Changes

Essential

• Redesign the experiment so that Ctf-IE and Ctf-SE are non-trivial. Change $\theta^\star$ (and/or the SCM edges into $W$ and $M$) so that the mediator and confounder reward coefficients are non-zero and CATE and Ctf-DE separate. This is a prerequisite for the empirical section to test the paper's actual contribution.
• Rerun and re-report Figures 2 and 4 under the redesigned SCM, and specifically confirm (or retract) the claim that DO-LogB attains lower penalized regret than CCLB and that CCLB accumulates near-linear violations. Both claims failed under the paper's own current $\theta^\star$.
• Release the code. Push the actual implementation of DO-LogB and the baselines (including the four practical constants that a reproducer must otherwise re-derive) to the printed URL before publication, along with hyperparameters and seed list. Alternatively, replace the URL with a scoped 'code will be released upon acceptance' note.
• Document all experimental hyperparameters. Add a table specifying $(\omega, \omega_2, \alpha, \eta, \lambda)$ for each algorithm and figure, together with the CCLB / GLB-OMD / GLM-UCB baseline parameter choices, the exact 'Best-fair' oracle definition (per-round vs population; feasibility tolerance), and the cumulative-violation aggregation (max/sum/clipped/signed).
• Fix the results paragraph. Rewrite the sentence that currently reads 'our method (CCLB) and the methods of GLMUCB, GLM-OMD, and CCLB' so that DO-LogB is unambiguously identified as the proposed method and the baselines are named consistently (GLM-UCB, GLB-OMD, CCLB).
• Clarify or retract the 'Best-fair oracle' domination claim. Either redefine 'Best-fair' rigorously and explain why domination is possible, or report the accompanying constraint-violation count for DO-LogB on the same rounds, or drop the claim.
• Replace 'individual fairness' in the conclusion with 'group-level counterfactual fairness' (or 'user-side fairness' as elsewhere in the paper) to match Definition 2 and Proposition 1.
• Analyze robustness to Assumption 3. Provide a plug-in variant of Theorem 4 that replaces the known conditionals $P(m|a,w),P(w|a)$ etc. with estimates from an offline batch of size $N$, so readers can see how the bounds degrade with mis-specification.

Suggested

• Add exploration-parameter ablations. Sweep $\omega_2 \in \{0, 1/4, 1/2-\varepsilon\}$ (and $\omega$ for Alg. 1) and plot both regret and violation, so the theoretical trade-off in Remark 2 is empirically confirmed.
• Add a multi-constraint scaling ablation. Vary $m \in \{1,3,5,10\}$ constraints (e.g., adding intersectional or per-subgroup fairness) to back the paper's claim that regret is independent of the number of constraints.
• Add one semi-realistic experiment. Adapt a public tabular fairness dataset (Adult, COMPAS) with an assumed mediation structure so the pathway decomposition can be seen to differ from CATE in a setting closer to the motivating recommendation example.
• Formalize counterfactual-context coverage. State Assumption 2 explicitly over the counterfactual configuration $(a'_t, w, m)$, or add a lemma showing the factual $\gamma_1$ implies the counterfactual bound under the SFM assumptions.
• Carry the $\gamma_1 T \gtrsim 1$ hypothesis into Theorems 1 and 2 so the guarantees are not vacuous when $|X|$ is exponentially large.
• Reconcile the proof/algorithm sampling distribution. State a short lemma (or restate Part (iii) of the Algorithm 1 proof) showing the martingale-difference property carries from $\pi_{X_t}$ to the mixture $\tilde\pi_{X_t}$ used by the algorithm.
• Nail down Definition 3 and the $\kappa$ convention. State Definition 3 formally in the main text (whether $\kappa = 1/\min_{Z,\theta}\dot\sigma$ or the max of $\dot\sigma^{-1}$) and reconcile with the $\dot\sigma \ge 1/\kappa$ inequality used in the constraint-violation proof.
• Clarify constraint semantics. State once, near the constrained optimization, whether the feasibility target is $\mathbb{E}_{d\sim\pi}[|\Delta^{(i)}_d|]$ (as currently written) or $|\mathbb{E}_{d\sim\pi}\Delta^{(i)}_d|$, and motivate the choice given the signed decomposition in Proposition 1.
• Fix small presentation defects. Correct the Appendix D 'the indirect effect' label to 'the spurious effect'; replace the stray π_4 in the Bregman-projection derivation; fix the n_{a', d, w, w} subscript in the bonus; tighten the mean-value bound |σ̇(ζ)| ≤ 1 to ≤ 1/4; align the local ω_2 ≥ 0 in Appendix F.3 with the theorem's ω_2 < 1/2; separate the compound cross-world/sequential-ignorability independence statement justifying (41); and reorder Assumption 4 to follow the feature-map definition.
• Reorder Section 5 / Conclusion prose so that experimental content (Algorithms, Metrics, Results, data-generation) sits under ## 5. Numerical Experiments and the Conclusion contains only concluding prose.