Large-Scale Markov Decision Problems with KL Control Cost and its Application to Crowdsourcing
Yasin Abbasi-Yadkori, Peter Bartlett, Xi Chen, Alan Malek
Abstract
We study average and total cost Markov decision problems with large state spaces. Since the computational and statistical costs of finding the optimal policy scale with the size of the state space, we focus on searching for near-optimality in a low-dimensional family of policies. In particular, we show that for problems with a Kullback-Leibler divergence cost function, we can reduce policy optimization to a convex optimization and solve it approximately using a stochastic subgradient algorithm. We show that the performance of the resulting policy is close to the best in the low-dimensional family. We demonstrate the efficacy of our approach by controlling the important crowdsourcing application of budget allocation in crowd labeling.
BibTeX
@InProceedings{pmlr-v37-abbasi-yadkori15,
title = {Large-Scale Markov Decision Problems with KL Control Cost and its Application to Crowdsourcing},
author = {Abbasi-Yadkori, Yasin and Bartlett, Peter and Chen, Xi and Malek, Alan},
booktitle = {Proceedings of the 32nd International Conference on Machine Learning},
pages = {1053--1062},
year = {2015},
editor = {Bach, Francis and Blei, David},
volume = {37},
series = {Proceedings of Machine Learning Research},
address = {Lille, France},
month = {07--09 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v37/abbasi-yadkori15.pdf},
url = {https://proceedings.mlr.press/v37/abbasi-yadkori15.html},
abstract = {We study average and total cost Markov decision problems with large state spaces. Since the computational and statistical costs of finding the optimal policy scale with the size of the state space, we focus on searching for near-optimality in a low-dimensional family of policies. In particular, we show that for problems with a Kullback-Leibler divergence cost function, we can reduce policy optimization to a convex optimization and solve it approximately using a stochastic subgradient algorithm. We show that the performance of the resulting policy is close to the best in the low-dimensional family. We demonstrate the efficacy of our approach by controlling the important crowdsourcing application of budget allocation in crowd labeling.}
}