License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.62
URN: urn:nbn:de:0030-drops-101550
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10155/
Go to the corresponding LIPIcs Volume Portal

Chase, Zachary ; Prasad, Siddharth

Learning Time Dependent Choice

pdf-format:
LIPIcs-ITCS-2019-62.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{chase_et_al:LIPIcs:2018:10155,
  author =	{Zachary Chase and Siddharth Prasad},
  title =	{{Learning Time Dependent Choice}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{62:1--62:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10155},
  URN =		{urn:nbn:de:0030-drops-101550},
  doi =		{10.4230/LIPIcs.ITCS.2019.62},
  annote =	{Keywords: Intertemporal Choice, Discounted Utility, Preference Recovery, PAC Learning, Active Learning}
}

Keywords: Intertemporal Choice, Discounted Utility, Preference Recovery, PAC Learning, Active Learning
Collection: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 08.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI