Constraint Relaxation in Approximate Linear Programs
Abstract
Approximate linear programming (ALP) is a reinforcement learning technique with nice theoretical properties, but it often performs poorly in practice. We identify some reasons for the poor quality of ALP solutions in problems where the approximation induces virtual loops. We then introduce two methods for improving solution quality. One method rolls out selected constraints of the ALP, guided by the dual information. The second method is a relaxation of the ALP, based on external penalty methods. The latter method is applicable in domains in which rolling out constraints is impractical. Both approaches show promising empirical results for simple benchmark problems as well as for a more realistic blood inventory management problem.
Cite
Text
Petrik and Zilberstein. "Constraint Relaxation in Approximate Linear Programs." International Conference on Machine Learning, 2009. doi:10.1145/1553374.1553478Markdown
[Petrik and Zilberstein. "Constraint Relaxation in Approximate Linear Programs." International Conference on Machine Learning, 2009.](https://mlanthology.org/icml/2009/petrik2009icml-constraint/) doi:10.1145/1553374.1553478BibTeX
@inproceedings{petrik2009icml-constraint,
title = {{Constraint Relaxation in Approximate Linear Programs}},
author = {Petrik, Marek and Zilberstein, Shlomo},
booktitle = {International Conference on Machine Learning},
year = {2009},
pages = {809-816},
doi = {10.1145/1553374.1553478},
url = {https://mlanthology.org/icml/2009/petrik2009icml-constraint/}
}