Approximate Value Trees in Structured Dynamic Programming
Abstract
We propose and examine a method of approximate dynamic programming for Markov decision processes based on structured problem representations. We assume an MDP is represented using a dynamic Bayesian network, and construct value functions using decision trees as our function representation. The size of the representation is kept within acceptable limits by pruning these value trees so that leaves represent possible ranges of values, thus approximating the value functions produced during optimization. We propose a method for detecting convergence,prove errors bounds on the resulting approximately optimal value functions and policies, and describe some preliminary experimental results.
Cite
Text
Boutilier and Dearden. "Approximate Value Trees in Structured Dynamic Programming." International Conference on Machine Learning, 1996.Markdown
[Boutilier and Dearden. "Approximate Value Trees in Structured Dynamic Programming." International Conference on Machine Learning, 1996.](https://mlanthology.org/icml/1996/boutilier1996icml-approximate/)BibTeX
@inproceedings{boutilier1996icml-approximate,
title = {{Approximate Value Trees in Structured Dynamic Programming}},
author = {Boutilier, Craig and Dearden, Richard},
booktitle = {International Conference on Machine Learning},
year = {1996},
pages = {54-62},
url = {https://mlanthology.org/icml/1996/boutilier1996icml-approximate/}
}