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 guar- antees, 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 hypoth- esis 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 proba- bility. Second, when the parameters of the hypotheses distribution are unknown, we propose an algorithm which learns the pa- rameters 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 guar- antees, 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 hypoth- esis 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 proba- bility. Second, when the parameters of the hypotheses distribution are unknown, we propose an algorithm which learns the pa- rameters 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 guar- antees, 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 hypoth- esis 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 proba- bility. Second, when the parameters of the hypotheses distribution are unknown, we propose an algorithm which learns the pa- rameters 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