Causal logistic bandits achieve optimal fairness regret with limited feedback
Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness
Machine Learning
Summary
This paper studies decision-making systems that balance learning rewards with fairness constraints, focusing on cases where answers are seen only in real, not hypothetical, situations. The authors show that some assumptions about data coverage are necessary to avoid large errors when choosing fair actions. They develop new algorithms that efficiently learn the best fair choices over time, and prove that these algorithms perform as well as theoretically possible. Their work bridges the gap between understanding fairness constraints in causal models and learning from actual observations.
What this means in practice
- •For algorithm designers: Design learning algorithms that ensure fair decisions under causal constraints using only observed feedback.
- •For online recommendation teams: Implement bandit methods that fairly personalize recommendations when counterfactual outcomes are not directly observable.
A theory result. No direct application yet.
Authors
Junhyuk Huh, Seoungbin Bae, Dabeen Lee
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.