  This paper examines whether one can learn to play an optimal action while
only knowing part of true specification of the environment. We choose the
optimal pricing problem as our laboratory, where the monopolist is endowed with
an underspecified model of the market demand, but can observe market outcomes.
In contrast to conventional learning models where the model specification is
complete and exogenously fixed, the monopolist has to learn the specification
and the parameters of the demand curve from the data. We formulate the learning
dynamics as an algorithm that forecast the optimal price based on the data,
following the machine learning literature (Shalev-Shwartz and Ben-David
(2014)). Inspired by PAC learnability, we develop a new notion of learnability
by requiring that the algorithm must produce an accurate forecast with a
reasonable amount of data uniformly over the class of models consistent with
the part of the true specification. In addition, we assume that the monopolist
has a lexicographic preference over the payoff and the complexity cost of the
algorithm, seeking an algorithm with a minimum number of parameters subject to
PAC-guaranteeing the optimal solution (Rubinstein (1986)). We show that for the
set of demand curves with strictly decreasing uniformly Lipschitz continuous
marginal revenue curve, the optimal algorithm recursively estimates the slope
and the intercept of the linear demand curve, even if the actual demand curve
is not linear. The monopolist chooses a misspecified model to save
computational cost, while learning the true optimal decision uniformly over the
set of underspecified demand curves.
