# The Markovian Price of Information

arXiv: https://arxiv.org/abs/1902.07856 · HTML: https://mlsanity.com/paper/1902.07856/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2019.

## Built on by (most cited first, 8 of 8)

- [Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index](https://mlsanity.com/paper/2406.20062/) (2024)
- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [Online Learning for Min Sum Set Cover and Pandora's Box](https://mlsanity.com/paper/2202.04870/) (2022)
- [The Gittins Index: A Design Principle for Decision-Making Under Uncertainty](https://mlsanity.com/paper/2506.10872/) (2025)
- [Contextual Pandora's Box](https://mlsanity.com/paper/2205.13114/) (2022)
- [Approximating Pandora's Box with Correlations](https://mlsanity.com/paper/2108.12976/) (2021)
- [Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error](https://mlsanity.com/paper/2509.22023/) (2025)
- [T-TAMER: Provably Taming Trade-offs in ML Serving](https://mlsanity.com/paper/2509.22992/) (2025)

## Abstract (arXiv)

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.