Robust Optimization for Hybrid MDPs with State-Dependent Noise
Zahra Zamani, Scott Sanner, Karina Valdivia Delgado, Leliane Nunes de Barros · ANU Open Research (Australian National University) · 2013
Recent advances in solutions to Hybrid MDPs with discrete and continuous state and action spaces have significantly extended the class of MDPs for which exact solutions can be derived, albeit at the expense of a restricted transition noise model. In this paper, we work around limitations of previ-ous solutions by adopting a robust optimization ap-proach in which Nature is allowed to adversarially determine transition noise within pre-specified con-fidence intervals. This allows one to derive an op-timal policy with an arbitrary (user-specified) level of success probability and significantly extends the class of transition noise models for which Hybrid MDPs can be solved. This work also significantly extends results for the related “chance-constrained” approach in stochastic hybrid control to accommo-date state-dependent noise. We demonstrate our ap-proach working on a variety of hybrid MDPs taken from AI planning, operations research, and control theory, noting that this is the first time robust so-lutions with strong guarantees over all states have been automatically derived for such problems. 1