1 Search Results for "Kash, Ian A."

Document
DOI: 10.4230/LIPIcs.ITCS.2021.77
Buying Data over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions

Authors: Nicole Immorlica, Ian A. Kash, and Brendan Lucier

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We consider a model where an agent has a repeated decision to make and wishes to maximize their total payoff. Payoffs are influenced by an action taken by the agent, but also an unknown state of the world that evolves over time. Before choosing an action each round, the agent can purchase noisy samples about the state of the world. The agent has a budget to spend on these samples, and has flexibility in deciding how to spread that budget across rounds. We investigate the problem of choosing a sampling algorithm that optimizes total expected payoff. For example: is it better to buy samples steadily over time, or to buy samples in batches? We solve for the optimal policy, and show that it is a natural instantiation of the latter. Under a more general model that includes per-round fixed costs, we prove that a variation on this batching policy is a 2-approximation.
Cite as

Nicole Immorlica, Ian A. Kash, and Brendan Lucier. Buying Data over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 77:1-77:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{immorlica_et_al:LIPIcs.ITCS.2021.77,
  author =	{Immorlica, Nicole and Kash, Ian A. and Lucier, Brendan},
  title =	{{Buying Data over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{77:1--77:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.77},
  URN =		{urn:nbn:de:0030-drops-136161},
  doi =		{10.4230/LIPIcs.ITCS.2021.77},
  annote =	{Keywords: Online Algorithms, Value of Data, Markov Processes}
}
  • Refine by Author
  • 1 Immorlica, Nicole
  • 1 Kash, Ian A.
  • 1 Lucier, Brendan

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Markov decision processes

  • Refine by Keyword
  • 1 Markov Processes
  • 1 Online Algorithms
  • 1 Value of Data

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact