# Efficient Online Learning for Optimizing Value of Information: Theory and Application to Interactive Troubleshooting

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Mar 2017.

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

- [A Survey on Active Feature Acquisition Strategies](https://mlsanity.com/paper/2502.11067/) (2025)
- [Active Learning of Driving Scenario Trajectories](https://mlsanity.com/paper/2108.03217/) (2021)
- [Online Learning of Energy Consumption for Navigation of Electric Vehicles](https://mlsanity.com/paper/2111.02314/) (2021)
- [Efficient Online Decision Tree Learning with Active Feature Acquisition](https://mlsanity.com/paper/2305.02093/) (2023)
- [Cost-Efficient Online Decision Making: A Combinatorial Multi-Armed Bandit Approach](https://mlsanity.com/paper/2308.10699/) (2023)
- [Towards an Interpretable Data-driven Trigger System for High-throughput Physics Facilities](https://mlsanity.com/paper/2104.06622/) (2021)
- [Passive and Active Learning of Driver Behavior from Electric Vehicles](https://mlsanity.com/paper/2203.02179/) (2022)
- [Non-Myopic Active Feature Acquisition via Pathwise Policy Gradients](https://mlsanity.com/paper/2605.05511/) (2026)

## Abstract (arXiv)

We consider the optimal value of information (VoI) problem, where the goal is to sequentially select a set of tests with a minimal cost, so that one can efficiently make the best decision based on the observed outcomes. Existing algorithms are either heuristics with no guarantees, or scale poorly (with exponential run time in terms of the number of available tests). Moreover, these methods assume a known distribution over the test outcomes, which is often not the case in practice. We propose an efficient sampling-based online learning framework to address the above issues. First, assuming the distribution over hypotheses is known, we propose a dynamic hypothesis enumeration strategy, which allows efficient information gathering with strong theoretical guarantees. We show that with sufficient amount of samples, one can identify a near-optimal decision with high probability. Second, when the parameters of the hypotheses distribution are unknown, we propose an algorithm which learns the parameters progressively via posterior sampling in an online fashion. We further establish a rigorous bound on the expected regret. We demonstrate the effectiveness of our approach on a real-world interactive troubleshooting application and show that one can efficiently make high-quality decisions with low cost.