Learning Time Dependent Choice
  We explore questions dealing with the learnability of models of choice over
time. We present a large class of preference models defined by a structural
criterion for which we are able to obtain an exponential improvement over
previously known learning bounds for more general preference models. This in
particular implies that the three most important discounted utility models of
intertemporal choice -- exponential, hyperbolic, and quasi-hyperbolic
discounting -- are learnable in the PAC setting with VC dimension that grows
logarithmically in the number of time periods. We also examine these models in
the framework of active learning. We find that the commonly studied
stream-based setting is in general difficult to analyze for preference models,
but we provide a redeeming situation in which the learner can indeed improve
upon the guarantees provided by PAC learning. In contrast to the stream-based
setting, we show that if the learner is given full power over the data he
learns from -- in the form of learning via membership queries -- even very
naive algorithms significantly outperform the guarantees provided by higher
level active learning algorithms.
