Learning Recourse from Data: Sharp Cost Rates and Limits of Optimal-Action Recovery

Counterfactual recourse identifies admissible changes that lead to a favorable prediction. It is usually computed for a fitted predictor treated as fixed, yet that predictor is itself estimated from finite data. We study recovery of the minimum recourse cost and the complete optimal-action set defined by an unknown population decision score. In smooth nonparametric binary regression with Euclidean cost and known translated convex action sets, we give design and boundary–action conditions under which score estimation error controls cost error uniformly over queries. We establish matching minimax bounds on explicit full-action and binding-box families, including cases where constraints change the minimizing action and its cost. The two targets nevertheless have different statistical limits: on a fixed regular family with full observational coverage, minimum cost is uniformly consistently estimable, but the complete exact optimal-action set is not. Arbitrarily small score perturbations can break ties between distant optima while barely changing cost. Uniqueness and uniform quadratic growth provide a positive counterpart through an upper bound for action-location recovery. Controlled experiments demonstrate finite-query Euclidean recovery and show that changing action constraints can amplify cost error for the same fitted score. These results distinguish estimating the minimum required change from recovering every minimum-cost choice.