Learning to Decide with AI Assistance under Human-Alignment

Technical Summary: Learning to Decide with AI Assistance under Human-Alignment

Problem Formulation
This paper addresses the challenge of learning optimal decision policies in high-stakes domains where human decision-makers are assisted by AI models. The setting is defined by binary predictions and binary decisions. In each interaction $t$, a decision-maker observes a feature vector $(x, v)$, a classifier's prediction $\hat{y}$, and the classifier's confidence $b \in B$ (where $B \subseteq [0, 1]$). The decision-maker also possesses a personal confidence $h \in H$ regarding the label $y=1$, where $H$ is a finite, totally ordered discrete set. The goal is to learn a policy $\pi(h, b) \in \{0, 1\}$ that maximizes expected utility $u(a, y)$, given that utility is higher when the decision $a$ matches the true label $y$.

The core difficulty lies in the decision-maker's inability to effectively modulate trust based solely on the AI's communicated confidence. Previous work (Corvelo Benz and Gomez-Rodriguez, 2023, 2025) suggests that the degree of "alignment" between the AI's confidence and the human's confidence significantly impacts the utility of AI-assisted decision-making. However, the extent to which this alignment influences the complexity of learning an optimal policy through repeated interactions remained unelucidated.

Methodology and Theoretical Framework
The authors frame the problem of learning to decide with AI assistance as a two-armed online contextual learning problem with full feedback.

• Context: The pair of confidence values $(h_t, b_t)$.
• Arms: The binary decisions $a \in \{0, 1\}$.
• Feedback: Full feedback is available because, given the label $y_t$, the decision-maker can compute the utility for both possible actions.

The paper establishes a lower bound on the expected regret for any learner in the general case (without assuming alignment) and then analyzes the complexity under the assumption of perfect alignment. Perfect alignment is defined such that for any $h < h'$ and $b < b'$, the conditional probability $P(Y=1 | H=h, B=b)$ is non-increasing with respect to the confidence levels.

Key Contributions and Results

1. General Lower Bound:
   The authors prove that without alignment assumptions, the expected regret $E[R(T)]$ for any learner is lower-bounded by $\Omega(\sqrt{|H| \cdot |B| \cdot T})$. This indicates that the complexity of learning scales with the product of the sizes of the human and AI confidence sets.

2. Regret Reduction under Perfect Alignment:
   Under the assumption of perfect alignment, the optimal policy $\pi^*$ is shown to be a threshold function over the AI confidence $b$, where the threshold $b^*(h)$ depends on the human confidence $h$.

   • Algorithm: The authors propose an online learning algorithm (Algorithm 1) that learns these thresholds. It treats the problem as $|H|$ independent multi-armed bandit problems (one for each human confidence level), where the "arms" are the candidate thresholds in $B$.
   • Regret Bound 1: Using the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality to bound estimation errors uniformly across thresholds, the algorithm achieves an expected regret of $O(\sqrt{|H| \cdot T \log T})$. Notably, this bound is independent of the size of the AI confidence set $|B|$.
   • Regret Bound 2: When $\sqrt{|H|} = O(\log T)$ and $B$ is countable, the authors derive a non-trivial generalization of the DKW inequality for threshold policies. This allows reformulating the problem as learning a single function $\ell: H \to B$ rather than $|H|$ independent thresholds. This improves the regret bound to $O(\sqrt{T} \log T)$, removing dependence on both $|H|$ and $|B|$.

3. Robustness to Imperfect Alignment:
   The paper demonstrates theoretically that if perfect alignment does not hold, the degree of misalignment (measured by Maximum Alignment Error, MAE) bounds the gap between the utility of the learned policy and the optimal policy. Specifically, the learned policy is near-optimal, with the performance gap scaling linearly with the MAE.

Experimental Validation
The theoretical findings are validated using real data from two human-subject studies:

• Human-Alignment Dataset (Corvelo Benz and Gomez-Rodriguez, 2025): Participants predicted outcomes in a card game with varying degrees of AI-human confidence alignment across different groups.
• Human-AI Interactions Dataset (Vodrahalli et al., 2022a): Participants performed binary classification tasks (Art, Sarcasm, Cities, Census) with AI assistance.

Results:

• The proposed algorithm (Algorithm 1) consistently achieved lower empirical average regret compared to a vanilla contextual online learning baseline (Algorithm 2) across all groups and tasks, with the exception of the 'Census' task where monotonicity was violated.
• The results confirm that even when perfect alignment is not strictly present, the assumption of perfect alignment yields better performance than making no such assumption, provided a weaker notion of alignment (monotonicity of $P(Y=1|H, B)$ with respect to $B$) holds.

Significance
The paper claims that alignment between AI and human confidence can fundamentally reduce the complexity of learning to make decisions with AI assistance. By leveraging the structural properties induced by alignment (specifically, the threshold nature of the optimal policy), learners can achieve significantly tighter regret bounds that are independent of the granularity of the AI's confidence output. This suggests that designing AI systems with confidence metrics that are aligned with human intuition is not merely a usability feature but a mechanism to accelerate the learning of optimal decision policies in repeated interactions.