Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness
This paper studies causal logistic bandits with counterfactual fairness constraints, where the learner observes only factual rewards and must infer counterfactual effects through shared logistic parameters. The core contribution is establishing minimax optimal regret-violation tradeoffs under a weak pooled coverage condition, showing that a target-specific information scale $V_\star$ governs the estimation difficulty and yielding matching $\widetilde{\Theta}(T^{2/3})$ upper and lower bounds.
The paper makes a solid theoretical contribution by tightening the understanding of what coverage is necessary and sufficient for learning counterfactual fairness from factual feedback alone. The lower bound construction is careful, and the algorithms achieve matching rates up to logarithmic factors. However, the bounds control slightly different quantities---the lower bounds are on expected joint loss while the upper bounds control $\max\{R_T, V_T\}$ with high probability---and the additive burn-in term $\kappa d / \sigma_0^2$ is not reflected in the lower bounds.
The necessity result (Proposition 3.2) is crisp and convincing: without a coverage-type condition, the learner faces factually indistinguishable environments that force $\Omega(T)$ joint loss. The target-specific information scale $V_\star$ is well-motivated as the largest local variance for estimating rewards and counterfactual effects from uniform factual exploration. Both the fixed and adaptive explore-then-exploit algorithms are natural, and the analysis using optimistic screening with logistic MLE confidence intervals is cleanly executed. The experiments confirm the theoretical predictions across varying factual scales.
A subtle but real discrepancy exists between the lower bounds, which bound worst-case $\mathbb{E}[R_T + V_T]$, and the upper bounds, which bound $\max\{R_T, V_T\}$ with probability at least $1-\delta$. This means the upper bound on the expected sum is not directly established, and the high-probability guarantee leaves a logarithmic gap that is not fully aligned with the expectation-based lower bounds. The lower bound constructions also impose restrictive dimensionality requirements ($d \geq 46$ and $K \geq 8$ in Theorem 4.2), raising the question of whether the same minimax rate holds for small action spaces and low dimensions. Additionally, the additive term $\kappa d / \sigma_0^2$ arising from the initial estimation threshold $n_0$ appears in the upper bounds but has no counterpart in the lower bounds; when the pooled covariance's minimum eigenvalue $\sigma_0^2$ is small, this term can dominate short-horizon regimes.
The comparison to Chen et al. (2025) and Chen et al. (2026) is fair and well-articulated: the authors correctly point out that the former omits a coverage condition while the latter imposes a covariate-diversity assumption requiring every action separately to cover every parameter direction, which is stronger than the pooled full-rank condition used here. The experiments, though limited to a synthetic $d=10$ instance and one structural causal model with $T=10{,}000$, clearly illustrate that both ETE methods incur lower cumulative stage-wise positive violations and lower penalized regret than the primal-dual and OMD baselines. Still, the empirical evaluation does not explicitly verify the scaling with $V_\star$ or the tightness of the $T^{2/3}$ rate.
The algorithms are described in sufficient detail for reproduction, including explicit formulas for the MLE, the estimated Fisher matrix $\widehat{H}_n$, and the logit radius $b_n(z) = 11\sqrt{\ell} \|z\|_{\widehat{H}_n^{-1}}$. However, the constants (e.g., $1024$, $11$, and the factor in $n_0 = \widetilde{O}(\kappa d / \sigma_0^2)$) are large and apparently unoptimized, which could hinder practical deployment. The adaptive algorithm does not require knowledge of $V_\star$, but the initial sample size $n_0$ depends on an explicit correction threshold $\Gamma_{\text{corr}}$ that is not straightforward to set without problem-specific tuning. No code or data repository is mentioned.
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 $\Omega(T)$ expected joint loss. Under a weaker full-rank condition on the factual covariance pooled across actions, we identify a target-specific information scale $V_\star$ 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 $\Omega\left(\left[V_\star\min\{\log K,d\}\right]^{1/3}T^{2/3}\right)$. We also give an explore--then--exploit procedure tuned using $V_\star$ and an adaptive algorithm that does not require its value. Both algorithms achieve $\max\{R_T,V_T\}=\widetilde{O}\left(\left[V_\star\min\{\log K,d\}\right]^{1/3}T^{2/3}+\kappa d/\sigma_0^2\right)$, where $R_T$ is regret relative to the best fair action and $V_T$ denotes the cumulative stage-wise positive violations. Thus the upper and lower bounds match in their leading dependence on $T$, $V_\star$, and $\min\{\log K,d\}$, up to logarithmic factors.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.