2018-09 Learnability and Models of Decision Making under Uncertainty 26 Pages

Abstract
We study whether some of the most important models of decision-making under
uncertainty are uniformly learnable. Imagine an analyst who seeks to learn, or
estimate, an agent’s preference using data on the agent’s choices. A model is learnable
if the analyst can construct a learning rule to learn the agent’s preference, when
preferences conforms to the model, with enough data, and uniformly over processes
that generate choice problems. We consider the Expected Utility, Choquet Expected
Utility and Max-min Expected Utility models: arguably the most important models
of decision-making under uncertainty. We show that Expected Utility and Choquet
Expected Utility are learnable. Morever, the sample complexity of the former is linear,
and of the latter exponential, in the number of states. This means that accurate
estimation of Choquet Expected Utility may require very large sample sizes, while Expected
Utility requires modest sample sizes. The Max-min Expected Utility model is
learnable when there are two states, but not when there are three states or more. Our
results exhibit a close relation between learnability and the axioms that characterise
the model.