The Markovian price of information

DOI10.1007/978-3-030-17953-3_18MaRDI QIDQ2293091zbMATH OpenOpenAlexFDO

Authors Anupam Gupta, Haotian Jiang, Ziv Scully, Sahil Singla

Publication date 6 February 2020

Full work available at URL https://arxiv.org/abs/1902.07856

zbMATH Keywords

Gittins indexmulti-armed banditsprobing algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Markov and semi-Markov decision processes (90C40)

Abstract: Suppose there are $n$ Markov chains and we need to pay a per-step emph{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 emph{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 emph{robustness} of our algorithms to the distribution parameters and how to handle the emph{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.

Recommendations

• The price of information in combinatorial optimization
• A Markov chain choice problem
• Learning Theory
• Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part II: Markovian rewards
• On targeting Markov segments

Cited in

(12)

• The value of information for price dependent demand
• An adversarial model for scheduling with testing
• Shadow price of information in discrete time stochastic optimization
• On targeting Markov segments
• The price of information in combinatorial optimization
• Optimal online contention resolution schemes via ex-ante prophet inequalities
• Market Selection and the Information Content of Prices
• Stochastic Probing with Increasing Precision
• Learning-augmented query policies for minimum spanning tree with uncertainty
• Random order vertex arrival contention resolution schemes for matching, with applications
• Matching with nested and bundled Pandora boxes
• Designing exploration contracts

This page was built for publication: The Markovian price of information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2293091)