PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness

Junhyuk Huh, Seoungbin Bae, Dabeen Lee

arXiv:2610.01377v1cs.LG

TL;DR

Causal logistic bandits with counterfactual fairness require learning fair actions from factual rewards even though counterfactual rewards are unobserved. The paper establishes the need for factual coverage, develops bounds under pooled full-rank coverage, and shows that an adaptive algorithm attains a rate matching the lower bound in its leading dependencies.

  • Problem

    Because only factual rewards are observed, it is unclear whether the feedback identifies the parameter directions needed to determine counterfactual fairness.

    Source: §1 · p. 1

  • Method

    The paper imposes pooled factual coverage, defines a target-specific information scale V⋆, and gives explore–then–exploit and adaptive procedures for learning fair actions.

    Source: §1 · p. 2

  • Results

    Under pooled coverage, the upper and lower bounds match in their leading dependence on T, V⋆, and min{log K, d}, up to logarithms.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Without a coverage-type restriction, indistinguishable factual histories with different optimal fair actions force Ω(T) expected joint loss in at least one environment.

    Source: §1 · p. 2

    The guarantees assume a known finite global inverse-curvature bound κ and positive-definite pooled factual covariance.

    Source: §2 · p. 3, §3.1 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

The paper studies fair causal logistic bandits where factual feedback must support both reward learning and assessment of counterfactual fairness. It shows why factual coverage matters, develops upper and lower bounds under pooled coverage, and gives an adaptive procedure that does not require knowing the target scale V⋆.

1 Introduction

  • The learner observes factual rewards but not counterfactual rewards, so it must use factual feedback to identify both rewarding actions and fair actions.The known factual and counterfactual feature maps share an unknown logistic reward parameter.Source: §1 · p. 1
  • The paper measures estimation difficulty for rewards and counterfactual effects from uniform factual exploration with a target scale V⋆.The closest prior work either lacks coverage guarantees or requires every action separately to cover every parameter direction, and does not provide a matching lower bound.Source: §1 · p. 2
  • Without a coverage restriction, two environments with identical observable histories but different optimal fair actions force every policy to incur Ω(T) expected joint loss in at least one environment.The paper therefore rules out uniform guarantees of both sublinear regret and sublinear violation over the unrestricted class.Source: §1 · p. 2
  • Under pooled full-rank factual coverage, the paper constructs worst-case lower-bound families and upper bounds that match in their leading dependence on T, V⋆, and min{log K, d}, up to logarithms.The adaptive procedure uses observable confidence widths and achieves the V⋆-dependent rate without taking V⋆ as input.Source: §1 · p. 2

2 Problem Formulation

The learner observes factual and counterfactual feature maps for each action, but receives a reward only for the chosen action. Fairness is defined by a tolerance on the factual–counterfactual mean-reward difference, under boundedness, curvature, and nonempty-feasibility assumptions.

2 Problem Formulation

  • Known feature maps encode factual and counterfactual logits using the same unknown parameter, while the learner observes only the chosen action’s Bernoulli reward.The counterfactual reward and the corresponding effect are not observed; the shared parameter is the structural assumption used to infer counterfactual information from factual observations.Source: §2 · p. 3
  • The model assumes a convex compact parameter set with bounded parameter and feature norms, and a known finite global inverse-curvature bound κ.A known upper bound on κ can replace κ in the algorithms and guarantees.Source: §2 · p. 3
  • An action is fair when its absolute factual–counterfactual effect is at most the threshold τ, and the fair oracle chooses the highest-reward action in that feasible set.The paper defines joint loss as cumulative regret relative to this oracle plus cumulative stage-wise positive violations.Source: §2 · p. 3
  • The true fair-action set is assumed nonempty for almost every context.Source: §2 · p. 3

3 Coverage and the Target Scale V⋆

The paper shows that factual coverage is necessary for sublinear fair learning, then uses pooled full-rank factual covariance to quantify the information available for estimating reward and fairness targets. Its target scale V⋆ captures the local variance of those target estimates under uniform factual exploration.

3.1 Coverage and Learnability

  • Without a restriction on unidentifiable parameter directions, no policy can guarantee both sublinear regret and sublinear violation uniformly over the model class.The construction uses one context, two actions, and two parameters with identical factual reward laws but different counterfactual rewards, changing the optimal fair action.Source: §3.1 · p. 4
  • Pooled factual covariance being positive definite rules out directions invisible to factual features, while individual action covariances may remain singular.This condition is weaker than requiring every action separately to cover every parameter direction.Source: §3.1 · p. 4

3.2 The Target Scale V⋆

  • The reward, counterfactual-reward, and effect gradients identify which parameter directions matter for each target.Since the counterfactual-reward gradient is the reward gradient minus the effect gradient, its information-norm is also bounded in terms of V⋆.Source: §3.2 · pp. 4–5
  • The target scale V⋆ measures the largest local variance for estimating reward and counterfactual-effect targets from uniform factual exploration.The Fisher information I⋆ describes information in parameter directions, while qᵀI⋆⁻¹q gives the local variance for estimating a target in direction q.Source: §3.2 · p. 4

4 Lower Bounds

The lower bounds use environments where learning counterfactual feasibility requires costly factual observations, despite full-rank pooled factual covariance. Their worst-case rates match the upper bounds in leading dependence on T and V⋆, up to logarithmic factors.

4 Lower Bounds

  • The constructed lower bounds match the upper bounds in their leading dependence on T and V⋆, up to logarithmic factors.The environments make the information needed to distinguish different optimal fair actions depend on V⋆, while pooled factual covariance remains full rank.Source: §4 · p. 5

4.1 Two-Environment Three-Action Construction

  • Ω(C^(1/3)T^(2/3)) joint loss follows by balancing costly exploration against uncertainty about whether the high-reward action is fair.Only observations from the informative action distinguish the two environments; the construction has d = 2 and K = 3, with V⋆,j ≍ C.Source: §4.1 · pp. 5–6

4.2 The General Lower Bound

  • Ω((D log M)^(1/3)T^(2/3)) joint loss follows because identifying the sole fair candidate among M environments requires information of order log M.The construction yields log M ≍ min{log K, d}, with V⋆,j ≍ D; Theorem 4.2 sets D = (d − 1)(1 + ρ²)/(ρ² ˙µ(B)).Source: §4.2 · p. 6

5 Algorithms and Upper Bounds

The algorithms use uniform factual exploration to estimate rewards and counterfactual effects, then confidence intervals to screen actions and control regret and violations. Fixed-length exploration can be tuned using V⋆, while adaptive exploration uses observable interval widths instead.

5.1 Confidence Intervals and Optimistic Screening

  • Both procedures estimate the shared logistic parameter and use it to form factual and counterfactual reward intervals from uniform exploration data.The confidence analysis makes these intervals valid simultaneously across fits and rounds with probability at least 1 − δ.Source: §5.1 · pp. 7–8
  • Valid reward and effect intervals retain the optimal fair action and bound each selected action’s regret and positive violation by the largest interval width.The screening rule keeps actions whose effect interval intersects [−τ, τ], then selects the retained action with the largest reward upper endpoint.Source: §5.1 · p. 7

5.2 Fixed-Length Explore–Then–Exploit

  • With V⋆-tuned exploration, fixed-length ETE achieves joint loss O(n0 + (V⋆ℓ)1/3T2/3), balancing exploration against exploitation costs.The bound applies with high probability under the stated assumptions; ℓ is a confidence factor.Source: §5.2 · pp. 8–9

5.3 Adaptive Explore–Then–Exploit

  • Adaptive ETE exploits when current interval widths are small and collects another exploration batch when they are large, so exploration can resume after exploitation begins.It checks observable widths rather than using V⋆ to decide when to explore.Source: §5.3 · p. 9
  • Adaptive ETE achieves max{RT, VT} ≤ min{T, 4ncrit + J + 1} with high probability, without requiring V⋆ as an input.Its rate has the same leading order as fixed-length ETE, up to logarithmic factors.Source: §5.3 · p. 9

6 Experiments

The experiments compare the proposed ETE methods with learning baselines on regret, cumulative stage-wise positive violations, and penalized regret. The reported results favor ETE on violations and penalized regret, while additional experiments vary the information scale and fairness threshold.

6 Experiments

  • The synthetic experiment weakens factual representation of a counterfactual-visible coordinate while leaving mean rewards, fair action sets, and best fair actions unchanged.The coordinate’s true coefficient is zero, so varying its factual scale changes information for certifying counterfactual fairness.Source: §6 · p. 11
  • The structural causal model experiment uses a binary sensitive attribute, covariate, mediator, and action-specific variable, and retains contexts with at least 12 fair actions.For Figure 1(b), the setting uses K = 20, T = 10,000, and τ = 0.001.Source: §6 · p. 11
  • Both ETE methods incur lower cumulative stage-wise positive violations and lower penalized regret than the learning baselines in Figure 1.Some baselines achieve negative regret by selecting high-reward unfair actions, but have higher cumulative violations and penalized regret.Source: §6 · p. 11, Figure 1 · p. 11

A.1 Metrics and Implementation Details

  • Reported curves average 10 independent runs, with shading and error bars spanning two standard deviations.Fixed ETE-oracle uses an empirical V⋆ estimate based on θ⋆ and offered contexts, so that benchmark is not implementable online.Source: §A.1 · pp. 15–16

A.2 Synthetic Experiment

The experiments vary counterfactual-effect information while holding rewards and fair action sets fixed, then test the algorithms on a structural causal model with logistic rewards. They report how performance changes with information scale and fairness threshold.

A.2 Synthetic Experiment

  • In the synthetic experiment, action 1 is always fair, while changing ρ alters only information in the last coordinate and leaves means, fair sets, and best-fair actions unchanged.The setup used d = 10, K = 5, T = 10,000, ρ = 0.25, and τ = 0.05 for Figure 1(a); the mean number of fair actions was 3.00.Source: §A.2 · p. 16
  • As V⋆ rose from 2.58 to 21.52 across ρ values 1, 1/2, 1/4, and 1/8, fixed ETE-oracle had larger violation and penalized regret, while Adaptive ETE worsened at the largest V⋆.The empirical V⋆ values, averaged over 10 trials, were 2.58, 3.25, 7.29, and 21.52, respectively.Source: §A.2 · p. 16

A.3 Structural Causal Model

  • The structural causal model adapts Chen et al. (2025) by clipping and rescaling features, replacing its Gaussian-noise threshold model with logistic rewards, and using shared exogenous variables in factual and counterfactual worlds.Coordinate-wise clipping and a factor of 1/5 keep both feature vectors’ norms at most one.Source: §A.3 · p. 17
  • Across all six tested τ values, one of the two ETE algorithms had the smallest mean penalized regret among the learning algorithms.Rejection sampling produced a different accepted-context distribution for each τ.Source: §A.3 · p. 17

B Related Work

Related work spans causal bandits, counterfactual fairness, constrained bandits, and logistic bandits. The paper distinguishes its setting through factual-only feedback for learning counterfactual feasibility and a pooled-covariance coverage condition.

Causal bandits and counterfactual fairness

Bandits with constraints

  • Unlike prior stage-wise or cumulative constrained-bandit formulations, this work controls cumulative stage-wise positive violations without separate constraint feedback, using the same factual observations for reward and fairness estimation.The cited prior work includes stage-wise constraints (Amani et al., 2019; Khezeli and Bitar, 2020; Moradipari et al., 2020; Amani et al., 2020; Pacchiano et al., 2021) and signed cumulative violation.Source: B Related Work · p. 18

Logistic bandits

  • The target scale V⋆ measures the largest inverse-Fisher variance over reward and effect directions, rather than uncertainty only at available action features as in logistic-bandit analyses.The paper also relates its exploration-length balance to the T^2/3 rate of Hao et al. (2020).Source: B Related Work · pp. 18–19

Coverage assumptions

C Proof of Proposition 3.2

The proof constructs observationally indistinguishable environments with different optimal fair actions, establishing linear joint loss without coverage. It then develops a worst-case instance whose pooled factual covariance satisfies the coverage condition.

C Proof of Proposition 3.2

  • If a policy selects action 1 at most T/3 times in expectation, environment 0 incurs expected regret at least T/6; otherwise, environment 1 incurs expected violation at least T/6.The environments have identical observed-history distributions, yet action 1 is optimal and fair in environment 0 while only action 2 is fair in environment 1.Source: C Proof of Proposition 3.2 · p. 19
  • The proof’s constructed two-action example has pooled factual covariance of rank one, while the parameter difference changes action 1’s counterfactual prediction, so the coverage assumption excludes it.The construction satisfies the stated boundedness and curvature assumptions.Source: C Proof of Proposition 3.2 · p. 20

D.1 Construction of the Worst-Case Instance

  • The three-action worst-case construction uses a high-reward action H, an always-fair baseline S, and an informative action E; H is fair in one environment but incurs violation in the other.S and E have zero effect in both environments, while E supplies information through factual feedback.Source: §D.1 · pp. 20–21
  • The informative action has joint cost greater than gα in both environments, while actions other than H cost at least gα in environment 0 and H costs at least 3gα in environment 1.These costs create the tradeoff between using E to distinguish environments and incurring loss on other actions.Source: §D.1 · pp. 21–22
  • The construction’s pooled factual covariance has minimum eigenvalue σ0^2, and its target information scale is bounded below and above by constant multiples of C.The proof states that the full-rank coverage assumption holds.Source: §D.1 · pp. 22–23

D.2 Main Proof of Theorem 4.1

The lower-bound proof compares environments according to how often the informative action is selected and balances exploration cost against difficulty distinguishing them. A second construction extends the argument to multiple high-reward candidates.

D.2 Main Proof of Theorem 4.1

  • Theorem 4.1’s proof splits policies into cases where the informative action is used often or rarely, then balances the resulting bounds by choosing α.In the rare-use case, the factual reward distributions of H and S are identical across the two environments.Source: §D.2 · pp. 23–24
  • The proof concludes the lower bound and compares the two environments’ target scales V⋆,j as asymptotically equivalent to C.The informative-action cost and environment-indistinguishability argument provide the two cases being balanced.Source: §D.2 · p. 24

E.1 Construction of the Worst-Case Instance

  • The multi-environment construction has M high-reward candidates, a safe action, and informative replicas; in environment j, H_j is the unique fair high-reward action and the fair oracle.Wrong high-reward candidates incur violations, while the safe action has zero effect and joint cost gα.Source: §E.1 · pp. 25–26
  • In the multi-environment construction, uniform action sampling selects an informative action with probability p, and the pooled factual covariance has minimum eigenvalue σ0^2.The target scale V⋆,j is bounded between 20D/3 and 2D/3.Source: §E.1 · pp. 26, 28

E.2 Main Proof of Theorem 4.2

The proof constructs hard environments and analyzes whether a policy gathers enough informative observations to identify the fair action. Balancing the resulting costs yields a worst-case lower bound, then expressed using K and d.

E.2 Main Proof of Theorem 4.2

  • Non-informative actions have identical factual reward distributions across environments, while informative observations distinguish them.The proof bounds the logit difference for informative replicas to control the information in those observations.Source: §E.2 · pp. 28–29
  • The proof splits policies according to how many informative actions they select, with few such actions limiting their ability to identify the environment.It infers an environment index from the selected action and applies information bounds to the resulting error event.Source: §E.2 · pp. 29–30
  • Choosing α to balance the two cases yields the lower-bound rate, and the proof translates the environment count M into K- and d-dependent terms.The construction uses M=⌊K/2⌋ in one case and a dimension-based bound otherwise.Source: §E.2 · p. 30
  • Every policy incurs worst-case expected joint loss at least on the order of (D log M)^(1/3)T^(2/3).The construction relates the target scale V⋆,j to D and converts log M to dependence on K and d.Source: §E.2 · p. 30

F Proof of Theorems 5.3 and 5.4

This section proves regret and violation guarantees using valid factual, counterfactual, and effect confidence intervals, bounding their widths and combined failure probability and establishing the needed concentration and MLE conditions. For the adaptive algorithm, it separately bounds exploration, trigger, and exploitation rounds.

F Proof of Theorems 5.3 and 5.4

  • Theorem 5.3 bounds later regret and violations by interval widths, while the first m rounds contribute at most m; its proof then derives the stated rate from the choice of m.The displayed intermediate bound is max{R_T, V_T} ≤ n_0 + 1 + 2a^(1/3) when m < T; if m = T, the trivial horizon bound yields the result.Source: F Proof of Theorems 5.3 and 5.4 · pp. 31–32
  • For Theorem 5.4, exploration and exploitation each contribute at most n̄, and trigger rounds at most J + 1, giving max{R_T, V_T} ≤ 4n_crit + J + 1.Failed width tests occur before n_crit, and each ensuing batch at most doubles its sample size; the proof also caps the bound by T.Source: F Proof of Theorems 5.3 and 5.4 · pp. 31–32

F.1 Proof of Lemma 5.2

  • The confidence analysis establishes a Fisher-matrix lower bound at every checkpoint and, with high probability, finite unique MLEs and invertible estimated Fisher matrices.The proof uses concentration for the exploration samples and rules out separating hyperplanes to establish MLE existence; spanning design vectors then gives strict convexity and uniqueness.Source: §2.2 · pp. 33–36

2.2 ∥u∥H(θ⋆)−1

  • With probability at least 1 − δ, checkpoint estimates satisfy the stated confidence bounds simultaneously, including for factual and counterfactual feature vectors at rounds when the checkpoint is used.The proof controls the error using either an action-wise route when KT ≤ 5d or a dimension-wise route when 5d < KT.Source: §2.2 · pp. 36–37
  • The listed failure probabilities sum to 7δ/16, which is less than δ.Source: §2.2 · p. 38
  • On the event that the MLEs are finite and the empirical Fisher matrices are invertible, monotonicity and the confidence bound make the reward and effect intervals valid.Source: §2.2 · p. 38
  • The maximum over actions proves width bound (5) by combining queried-direction bounds for factual and counterfactual intervals.The proof uses an inverse-Fisher bound and a logistic-derivative comparison to control the widths.Source: §2.2 · pp. 38–39

G Technical Lemmas

The technical lemmas provide information-theoretic and analytic tools used in the proofs, including bounds for distinguishing environments and constructing separated vectors. The paper also discloses how generative-AI tools contributed to its development.

G Technical Lemmas

  • The technical lemmas establish that log μ is 1-Lipschitz and that a positive-definite quadratic optimization has supremum attained at M^-1q.Source: G Technical Lemmas · pp. 39, 41
  • Before each randomized action, the history includes the current context; conditional on that history and action, the reward is a new Bernoulli draw.Source: G Technical Lemmas · p. 39
  • When only actions in E differ across environments and each conditional observation has KL at most γ, the history KL is bounded by γ times the expected number of selections from E.The proof uses the KL chain rule; shared context and policy-action terms vanish.Source: G Technical Lemmas · p. 40
  • Data processing bounds information retained in a measurable function of the history, and Fano’s inequality relates mutual information to environment-estimation error.The lemmas also cover randomized policies using an environment-independent seed.Source: G Technical Lemmas · pp. 40–41
  • For n≥45, the vector-construction lemma guarantees a collection of vectors with the required pairwise inequalities.Its proof draws vectors independently and uses Hoeffding’s inequality and a union bound.Source: G Technical Lemmas · p. 41

Use of Generative-AI Tools

  • Generative-AI tools assisted with hard instances, lower-bound proofs, both algorithms and their upper-bound proof, manuscript polishing, reference exploration, and simulation code.The authors state that they take responsibility for the final arguments and presentation.Source: Use of Generative-AI Tools · p. 42

Related papers

Loading 2610.01377v1…