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

Yuxin Chen, Jean-Michel Renders, Morteza Haghir Chehreghani, Andreas Krause
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:311-320, 2017.

Abstract

We consider the optimal value of information 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 a 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-chen17a, title = {Efficient Online Learning for Optimizing Value of Information: Theory and Application to Interactive Troubleshooting}, author = {Chen, Yuxin and Renders, Jean-Michel and Chehreghani, Morteza Haghir and Krause, Andreas}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {311--320}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/chen17a/chen17a.pdf}, url = {https://proceedings.mlr.press/r15/chen17a.html}, abstract = {We consider the optimal value of information 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 a 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Efficient Online Learning for Optimizing Value of Information: Theory and Application to Interactive Troubleshooting %A Yuxin Chen %A Jean-Michel Renders %A Morteza Haghir Chehreghani %A Andreas Krause %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-chen17a %I PMLR %P 311--320 %U https://proceedings.mlr.press/r15/chen17a.html %V R15 %X We consider the optimal value of information 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 a 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. %Z Reissued by PMLR on 04 October 2026.
APA
Chen, Y., Renders, J., Chehreghani, M.H. & Krause, A.. (2017). Efficient Online Learning for Optimizing Value of Information: Theory and Application to Interactive Troubleshooting. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:311-320 Available from https://proceedings.mlr.press/r15/chen17a.html. Reissued by PMLR on 04 October 2026.

Related Material