Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness

Junhyuk Huh; Seoungbin Bae; Dabeen Lee

cs.LGOct 1, 2026

Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness

Authors: Junhyuk Huh, Seoungbin Bae, Dabeen Lee

Organizations: Faculty of Mathematics, University of Cambridge · Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University

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 $Ω(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 $Ω\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}+κd/σ_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.

Figures & tables

Result	Knowledge of $V_{\star}$	Guarantee
Fixed ETE (Alg. 1 )	Used to choose $m$	$\widetilde{O}\bigl([V_{\star}\min\{\log K,d\}]^{1/3}T^{2/3}+\kappa d/\sigma_{0}^{2}\bigr)$
Adaptive ETE (Alg. 2 )	Not assumed	$\widetilde{O}\bigl([V_{\star}\min\{\log K,d\}]^{1/3}T^{2/3}+\kappa d/\sigma_{0}^{2}\bigr)$
Lower bound (Theorem 4.2 )	—	$\Omega\bigl((V_{\star}\min\{\log K,d\})^{1/3}T^{2/3}\bigr)$
Proposition 3.2	—	$\Omega(T)$ without a coverage assumption

Table 1 : Upper and lower bounds for the joint loss, which is the sum of regret and violation.

Action	Reward role	Information role	Fairness role
$H$	high reward	uninformative	fair only in environment $0$
$S$	slightly lower reward	uninformative	always fair
$E$	low reward	informative	always fair

Table 2 : Roles of the three actions in the two-dimensional family.

Panel of Figure 1 — Figure 1 : Cumulative regret, cumulative stage-wise positive violations, and penalized cumulative regret for the proposed methods and baselines.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2 : Comparison of cumulative regret, cumulative stage-wise positive violations, and penalized cumulative regret under varying $\rho$ and $\tau$ .

Explore similar work

May 27, 2026stat.ML

Counterfactually Fair Regression via Optimal Transport

We consider the problem of learning a counterfactually fair regressor. We adopt a causal uncertainty view in which counterfactual fairness is defined with resampled noise. We focus on obtaining theoretical fairness guarantees for a new post-processing estimator. We begin by showing that counterfactual fairness is equivalent to satisfying demographic parity conditional on the latent variable. This allows us to provide a closed-form expression of the optimal fair regressor via a barycentric quantile map. In order to handle continuous latent variables, we propose a discretized post-processing method. Then, under mild regularity assumptions, we prove high-probability finite-sample fairness guarantees for our estimator, providing an unfairness decay at rate

\tilde O(n^{-1/3})

, and establishing a matching risk bound of order

\tilde O(n^{-1/3})

. We provide a matching lower bound on the excess risk of almost fair predictions. Finally, we extend our results to the setting of relaxed counterfactual fairness. We validate our approach on real-world and synthetic data.

M. Generali Lince, S. Gaucher, J-J. Vie +1

Inria, Soda team · CREST, ENSAE, IP Paris · CMAP, CNRS, Ecole Polytechnique, Institut Polytechnique de Paris +1

Algorithmic Fairness Causal Inferences Causal

Ask PDF

Jul 15, 2026stat.ML

Price of Fairness in Bandits: A Tight Minimax Characterization

In bandit problems, standard regret-minimizing algorithms treat exploration as an amortized cost, which can expose early participants to unfair ex-ante losses in settings such as clinical trials. Recent work addresses this by evaluating the sequence of per-round expected rewards through the generalized

p

-mean, interpolating between utilitarian welfare (

p=1

), Nash welfare (

p\to0

), and Rawlsian fairness (

p\to-\infty

). Although tight guarantees are known for

p\ge0

, the strictly fair regime

q=-p>0

remains unresolved because negative-power means are dominated by the smallest per-round rewards. For

σ

-sub-Gaussian rewards with nonnegative means, the best prior algorithm relied on uniform early exploration and achieved regret

O(k^{(q+1)/2}/\sqrt{T})

, while the only general lower bound was the classical

Ω(σ\sqrt{k/T})

. Thus it was unclear whether the extra dependence on

k

was intrinsic to strict fairness or an artifact of uniform exploration. We close this gap by identifying the exact polynomial price of strict fairness. Using a needle-in-haystack construction, we prove an algorithm-independent lower bound

Ω(σ\sqrt{k^{\max(1,q)}/T})

; for

q>1

, this shows that the penalty

k^{q/2}

is information-theoretically unavoidable. We then introduce \textsf{UCB-HARE} (Harmonic Anchored Rank Exploration), which replaces uniform exploration with an inverse-weighted harmonic rank schedule protected by a certified positive-mean anchor. Its regret is

\widetilde{O}(σ\sqrt{k^{\max(1,q)}/T})

, matching the lower bound up to logarithmic factors. Experiments on synthetic instances confirm that \textsf{UCB-HARE} improves over uniform-exploration baselines, with gains increasing as

q

grows.

Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray Chowdhury

1Indian Institute of Technology Kharagpur · 2Mohamed bin Zayed University of Artificial Intelligence · 3Indian Institute of Technology Kanpur

Bandits Minimax Algorithmic Fairness Prices

Ask PDF

Aug 9, 2026stat.ML

A Distribution Mapping Approach to Counterfactually Fair Reinforcement Learning

Reinforcement learning (RL) seeks to optimize sequential decisions to maximize population-level benefits over time. However, when deployed in high-stakes settings such as healthcare, RL decisions might systematically restrict some subpopulation's access to valuable services in a manner contrary to the values and goals of stakeholders. Counterfactual fairness (CF) offers a promising framework to address this problem based on causal reasoning. This paper develops a data preprocessing algorithm that, when used in tandem with policy learning, enables CF in RL. Our algorithm relies on a novel quantile distribution mapping method for sequentially estimating the counterfactual states and rewards in the data preprocessing step, subsuming common additivity assumptions used for counterfactual prediction as a special case. We theoretically prove that the per-step level of counterfactual unfairness and infinite-horizon suboptimality gap can be bounded under mild regularity conditions. We also empirically test our algorithm in numerical experiments as well as in application to a real-world interventional digital health dataset.

Jianhan Zhang, Jitao Wang, John D. Piette +3

University of Michigan · LSE

Counterfactual Learning Distributional Reinforcement Learning Algorithmic Fairness Causal Inferences Distributions Optimality

Ask PDF