@article{Ho:2014:10.1137/130944254,
author = {Ho, CP and Parpas, P},
doi = {10.1137/130944254},
journal = {SIAM Journal on Control and Optimization},
pages = {3854--3886},
title = {Singularly perturbed markov decision processes: a multiresolution algorithm},
url = {http://dx.doi.org/10.1137/130944254},
volume = {52},
year = {2014}
}

Download

TY  - JOUR
AB  - Singular perturbation techniques allow the derivation of an aggregate model whose solution is asymptotically optimal for Markov decision processes with strong and weak interactions. We develop an algorithm that takes advantage of the asymptotic optimality of the aggregate model in order to compute the solution of the original model. We derive conditions for which the proposed algorithm has better worst case complexity than conventional contraction algorithms. Based on our complexity analysis, we show that the major benefit of aggregation is that the reduced order model is no longer ill conditioned. The reduction in the number of states (due to aggregation) is a secondary benefit. This is a surprising result since intuition would suggest that the reduced order model can be solved more efficiently because it has fewer states. However, we show that this is not necessarily the case. Our theoretical analysis and numerical experiments show that the proposed algorithm can compute the optimal solution with a reduction in computational complexity and without any penalty in accuracy.
AU  - Ho,CP
AU  - Parpas,P
DO  - 10.1137/130944254
EP  - 3886
PY  - 2014///
SN  - 0363-0129
SP  - 3854
TI  - Singularly perturbed markov decision processes: a multiresolution algorithm
T2  - SIAM Journal on Control and Optimization
UR  - http://dx.doi.org/10.1137/130944254
UR  - http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000346845100017&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
UR  - https://epubs.siam.org/doi/10.1137/130944254
UR  - http://hdl.handle.net/10044/1/21116
VL  - 52
ER  - 

Download