Self-Adapting Approximations of Markov Decision Processes: A Guided Tour
Abstract
Sequential decision making under uncertainty arises across business, engineering, and science. Markov decision processes (MDPs) offer a rich modeling language, but translating models into implementable policies requires confronting challenging state and action spaces and nonconvex optimization landscapes. Approximations are essential, and making them accessible and performant without algorithmic expertise allows users to focus on formulating MDPs that capture real-world features rather than simplifying their models to facilitate solution. Obtaining a policy involves a three-stage COR cycle: constructing a parametrized model that approximates the MDP, optimizing for the parameters of this model, and refining the model by learning from the solution. These stages involve design choices that burden the user, leading them to simplify or skip stages. This tutorial provides an overview of methods that reduce the user burden using COR as its guide. Construction ranges from lightweight extensible models to automated structural reformulations. Optimization leverages mathematical programming and first-order methods that have matured in theory and off-the-shelf software. Refinement performs feature expansion and approximation tightening, feeding back into the construct stage. When a combination of techniques across COR stages results in both accessibility and performance, we refer to it as a self-adapting approximation. Such an approximation adapts to problem structure, instance data, or solution progress. We guide readers through these ideas across weakly coupled MDPs and general continuous state–action MDPs, providing generalizable foundations and a code base to get started on a simple example. The tutorial concludes by outlining the potential for foundation models and quantum computing to further impact this area.
Funding: A. A. Cire gratefully acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) [Grants RGPIN-2020-06054 and RGPIN-2026-07964]. S. Nadarajah and N. Soheili gratefully acknowledge support from the College of Business Administration at the University of Illinois Chicago.
Your Access Options
-
Login Options
Purchase Options
Save for laterOther Options
Token AccessClaim access using a tokenRestore guest accessApplies for purchases made as a guest
