The Markovian Price of Information

Anupam Gupta, Haotian Jiang, Ziv Scully, Sahil Singla

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

Suppose there are n Markov chains and we need to pay a per-step price to advance them. The “destination” states of the Markov chains contain rewards; however, we can only get rewards for a subset of them that satisfy a combinatorial constraint, e.g., at most k of them, or they are acyclic in an underlying graph. What strategy should we choose to advance the Markov chains if our goal is to maximize the total reward minus the total price that we pay? In this paper we introduce a Markovian price of information model to capture settings such as the above, where the input parameters of a combinatorial optimization problem are given via Markov chains. We design optimal/approximation algorithms that jointly optimize the value of the combinatorial problem and the total paid price. We also study robustness of our algorithms to the distribution parameters and how to handle the commitment constraint. Our work brings together two classical lines of investigation: getting optimal strategies for Markovian multi-armed bandits, and getting exact and approximation algorithms for discrete optimization problems using combinatorial as well as linear-programming relaxation ideas.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings
EditorsAndrea Lodi, Viswanath Nagarajan
PublisherSpringer Verlag
Pages233-246
Number of pages14
ISBN (Print)9783030179526
DOIs
StatePublished - 2019
Event20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 - Ann Arbor, United States
Duration: May 22 2019May 24 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11480 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019
Country/TerritoryUnited States
CityAnn Arbor
Period5/22/195/24/19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Gittins index
  • Multi-armed bandits
  • Probing algorithms

Fingerprint

Dive into the research topics of 'The Markovian Price of Information'. Together they form a unique fingerprint.

Cite this