Help
Cart
Skip main navigation

Self-Adapting Approximations of Markov Decision Processes: A Guided Tour

Published Online:1 Nov 2026https://doi.org/10.1287/educ.2026.0308
Acknowledgments

The authors thank the editors of the INFORMS TutORials in Operations Research series for their valuable feedback.

Endnotes

1 The accompanying code is publicly available at https://github.com/Self-Adapting-MDP-Approximations (folder weakly-coupled).

2 The source paper Lin et al. [14] denotes the basis function weights by θ and the constant shift by τ. We use β=(β0,β1,…,βN) throughout this tutorial for consistency, with β0 playing the role of τ.

3 In Pakiman et al. [22], we use notation ρ rather than ϑ for the random features sampling distribution.

4 The accompanying code is publicly available at https://github.com/Self-Adapting-MDP-Approximations (folder continuous-mdp).

References

  • [1] D. Adelman and A. J. Mersereau. Relaxations of weakly coupled stochastic dynamic programs. Operations Research 56(3):712–727, 2008. Link, Google Scholar
  • [2] D. Adelman, A. Mersereau, and P. Pakiman. Dynamic optimization of workforce talent. Preprint, submitted September 25, https://doi.org/10.2139/ssrn.4964890, 2024.Google Scholar
  • [3] S. Agrawal. Recent advances in multiarmed bandits for sequential decision making. S. Netessine, editor. Operations Research & Management Science in the Age of Analytics, INFORMS TutORials in Operations Research. INFORMS, Catonsville, MD, 167–188, 2019.Link, Google Scholar
  • [4] D. P. Bertsekas. Neuro-dynamic programming. Encyclopedia of Optimization. Springer, Cham, 1–6, 2025.Crossref, Google Scholar
  • [5] D. Bertsimas and A. J. Mersereau. A learning approach for interactive marketing to a customer segment. Operations Research 55(6):1120–1135, 2007.Link, Google Scholar
  • [6] D. Bertsimas and V. V. Mišić. Decomposable Markov decision processes: A fluid optimization approach. Operations Research 64(6):1537–1555, 2016.Link, Google Scholar
  • [7] D. B. Brown and J. E. Smith. Index policies and performance bounds for dynamic selection problems. Management Science 66(7):3029–3050, 2020.Link, Google Scholar
  • [8] D. B. Brown and J. Zhang. Fluid policies, reoptimization, and performance guarantees in dynamic resource allocation. Operations Research 73(2):1029–1045, 2025.Link, Google Scholar
  • [9] F. Caro and J. Gallien. Dynamic assortment with demand learning for seasonal consumer goods. Management Science 53(2):276–292, 2007.Link, Google Scholar
  • [10] J. C. D’Aeth, S. Ghosal, F. Grimm, D. Haw, E. Koca, K. Lau, H. Liu, et al. Optimal hospital care scheduling during the SARS-CoV-2 pandemic. Management Science 69(10):5923–5947, 2023. Google Scholar
  • [11] D. P. de Farias and B. Van Roy. The linear programming approach to approximate dynamic programming. Operations Research 51(6):850–865, 2003.Link, Google Scholar
  • [12] B. de Jonge and P. A. Scarf. A review on maintenance optimization. European Journal of Operational Research 285(3):805–824, 2020.Crossref, Google Scholar
  • [13] M. C. Fu. Markov decision processes, AlphaGo, and Monte Carlo tree search: Back to the future. R. Batta and J. Peng, editors. Leading Developments from INFORMS Communities, INFORMS TutORials in Operations Research. INFORMS, Catonsville, MD, 68–88, 2017.Link, Google Scholar
  • [14] Q. Lin, S. Nadarajah, and N. Soheili. Revisiting approximate linear programming: Constraint-violation learning with applications to inventory control and energy storage. Management Science 66(4):1544–1562, 2020.Link, Google Scholar
  • [15] S. Mannor and H. Xu. Data-driven methods for Markov decision problems with parameter uncertainty. S. Netessine, editor. Operations Research & Management Science in the Age of Analytics, INFORMS TutORials in Operations Research. INFORMS, Catonsville, MD, 101–129, 2019.Link, Google Scholar
  • [16] A. R. Mazumder and S. Tayur. Five starter problems: Solving quadratic unconstrained binary optimization models on quantum computers. B. Denton, N. Noyan, and Y. Xie, editors. Advances in Analytics and Operations Research: Improving Decisions to Secure the Future, INFORMS TutORials in Operations Research. INFORMS, Catonsville, MD, 145–183, 2025.Link, Google Scholar
  • [17] S. Nadarajah and A. A. Cire. Self-adapting network relaxations for weakly coupled Markov decision processes. Management Science 71(2):1779–1802, 2025.Link, Google Scholar
  • [18] S. Nadarajah and A. A. Cire. Delayed allocation in marginalized flow models for weakly coupled Markov decision processes. Preprint, submitted February 10, https://doi.org/10.2139/ssrn.6127326, 2026.Google Scholar
  • [19] J. Ning. Easy affine Markov decision processes: Properties and applications. R. Batta and J. Peng, editors. Leading Developments from INFORMS Communities, INFORMS TutORials in Operations Research. INFORMS, Catonsville, MD, 28–47, 2017.Link, Google Scholar
  • [20] P. Pakiman and S. Nadarajah. Back to the future: Revisiting a pioneering approximation of average cost Markov decision processes using a multi-shot perspective. Preprint, submitted October 24, https://doi.org/10.2139/ssrn.4938885, 2024.Google Scholar
  • [21] P. Pakiman, B. Chen, S. Nadarajah, and S. Jasin. Adaptive risk mitigation in demand learning. Preprint, submitted December 15, https://arxiv.org/abs/2011.10690, 2025a.Google Scholar
  • [22] P. Pakiman, S. Nadarajah, N. Soheili, and Q. Lin. Self-guided approximate linear programs: Randomized multi-shot approximation of discounted Markov decision processes. Management Science 71(4):3384–3404, 2025b.Link, Google Scholar
  • [23] W. B. Powell. Approximate Dynamic Programming: Solving the Curses of Dimensionality. John Wiley & Sons, Hoboken, NJ, 2011.Crossref, Google Scholar
  • [24] W. B. Powell. Clearing the jungle of stochastic optimization. A. Newman and J. Leung, editors. Bridging Data and Decisions, INFORMS TutORials in Operations Research. INFORMS, Catonsville, MD, 109–137, 2014.Link, Google Scholar
  • [25] W. B. Powell. A unified framework for optimization under uncertainty. A. Gupta and A. Capponi, editors. Optimization Challenges in Complex, Networked and Risky Systems, INFORMS TutORials in Operations Research. INFORMS, Catonsville, MD, 45–83, 2016.Link, Google Scholar
  • [26] W. B. Powell and H. Topaloglu. Approximate dynamic programming for large-scale resource allocation problems. M. P. Johnson, B. Norman, and N. Secomandi, editors. Models, Methods, and Applications for Innovative Decision Making, INFORMS TutORials in Operations Research. INFORMS, Catonsville, MD, 123–147, 2006.Link, Google Scholar
  • [27] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Hoboken, NJ, 2014.Google Scholar
  • [28] A. Rahimi and B. Recht. Uniform approximation of functions with random bases. 2008 46th Annual Allerton Conference on Communication, Control, and Computing. Institute of Electrical and Electronics Engineers, Piscataway, NJ, 555–561, 2008. Google Scholar
  • [29] P. J. Schweitzer and A. Seidmann. Generalized polynomial approximations in Markovian decision processes. Journal of Mathematical Analysis and Applications 110(2):568–582, 1985.Crossref, Google Scholar
  • [30] Z. Scully and A. Terenin. The Gittins index: A design principle for decision making under uncertainty. B. Denton, N. Noyan, and Y. Xie, editors. Advances in Analytics and Operations Research: Improving Decisions to Secure the Future, INFORMS TutORials in Operations Research. INFORMS, Catonsville, MD, 28–70, 2025.Link, Google Scholar
  • [31] M. Sellmann. Meta-algorithms. D. M. Aleman and A. C. Thiele, editors. The Operations Research Revolution, INFORMS TutORials in Operations Research. INFORMS, Catonsville, MD, 47–55, 2015.Link, Google Scholar
  • [32] V. Siddhu and S. Tayur. Five starter pieces: Quantum information science via semidefinite programs. M. C. Chou, H. Gibson, and B. R. Staats, editors. Emerging and Impactful Topics in Operations, INFORMS TutORials in Operations Research. INFORMS, Catonsville, MD, 59–92, 2022.Link, Google Scholar
  • [33] N. Soheili, S. Nadarajah, and B. Yang. Weakly time-coupled approximation of Markov decision processes. Preprint, submitted March 13, https://arxiv.org/abs/2603.12636, 2026.Google Scholar
  • [34] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction, 2nd edition. MIT Press, Cambridge, MA, 2018.Google Scholar
  • [35] T. Wu, M. Zurek, Y. Chen, W. Wang, and Q. Xie. Lyapunov-based sample complexity analysis for weakly-coupled MDPs. NeurIPS 2025 Workshop MLxOR: Mathematical Foundations and Operational Integration of Machine Learning for Uncertainty-Aware Decision-Making, 2025.Google Scholar
  • [36] G. Zayas-Cabán, S. Jasin, and G. Wang. An asymptotically optimal heuristic for general nonstationary finite-horizon restless multi-armed, multi-action bandits. Advances in Applied Probability 51(3):745–772, 2019.Crossref, Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree