Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness

arXiv:2610.01377v1 Announce Type: new 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 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 Omegaleft(left[V_starmin{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_starmin{log K,d}right]^{1/3}T^{2/3}+kappa d/sigma_0^2right), 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.

Related

• Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback
• Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
• Counterfactual Tool Ranking under Utility, Cost, and Privilege Constraints

Source: arXiv cs.LG | 2026-10-02