Dynamic Programming-Compatible Uncertainty Sets in Robust Markov Decision Processes

References

• [1] Auer P, Jaksch T, Ortner R (2009) Near-optimal regret bounds for reinforcement learning. Koller D, Schuurmans D, Bengio Y, Bottou L, eds. Adv. Neural Inform. Processing Systems 21: Proc. Twenty-Second Annual Conf. Neural Inform. Processing Systems, vol. 21 (Curran Associates, Inc., Red Hook, NY), 89–96.Google Scholar
• [2] Behzadian B, Petrik M, Ho CP (2021) Fast algorithms for l∞ constrained s-rectangular robust MDPs. Ranzato M, Beygelzimer A, Dauphin YN, Liang PS, Wortman Vaughan J, eds. Adv. Neural Inform. Processing Systems, vol. 34 (Curran Associates, Inc., Red Hook, NY), 25982–25992.Google Scholar
• [3] Ben-Tal A, Nemirovski A (2021) Lectures on Modern Convex Optimization 2020 (SIAM, Philadelphia).Google Scholar
• [4] Berinde V (2007) Iterative Approximation of Fixed Points (Springer, Berlin).Google Scholar
• [5] Chambolle A, Pock T (2016) On the ergodic convergence rates of a first-order primal–dual algorithm. Math. Programming 159(1):253–287.Crossref, Google Scholar
• [6] Delage E, Mannor S (2010) Percentile optimization for Markov decision processes with parameter uncertainty. Oper. Res. 58(1):203–213.Link, Google Scholar
• [7] Filippi S, Cappé O, Garivier A (2010) Optimism in reinforcement learning and Kullback–Leibler divergence. Viswanath P, Meyn S, eds. 2010 48th Annual Allerton Conf. Comm. Control Comput. (Allerton) (IEEE, Piscataway, NJ), 115–122.Google Scholar
• [8] Givan R, Leach S, Dean T (2000) Bounded-parameter Markov decision processes. Artificial Intelligence 122(1–2):71–109.Crossref, Google Scholar
• [9] Goh J, Bayati M, Zenios SA, Singh S, Moore D (2018) Data uncertainty in Markov chains: Application to cost-effectiveness analyses of medical innovations. Oper. Res. 66(3):697–715.Link, Google Scholar
• [10] Goyal V, Grand-Clément J (2023) Robust Markov decision processes: Beyond rectangularity. Math. Oper. Res. 48(1):203–226.Link, Google Scholar
• [11] Grand-Clément J, Petrik M (2025) On the convex formulations of robust Markov decision processes. Math. Oper. Res. 50(3):1681–1706.Link, Google Scholar
• [12] Grand-Clément J, Petrik M, Vieille N (2026) Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimality. Oper. Res. 74(4):2088–2112.Google Scholar
• [13] Hiriart-Urruty J-B, Lemaréchal C (1996) Convex Analysis and Minimization Algorithms I: Fundamentals, vol. 305 (Springer Science & Business Media, New York).Google Scholar
• [14] Ho CP, Petrik M, Wiesemann W (2018) Fast Bellman updates for robust MDPs. Internat. Conf. Machine Learn. (PMLR), 1979–1988.Google Scholar
• [15] Ho CP, Petrik M, Wiesemann W (2021) Partial policy iteration for L1-robust Markov decision processes. J. Machine Learn. Res. 22(1):12612–12657.Google Scholar
• [16] Ho CP, Petrik M, Wiesemann W (2022) Robust phi-divergence MDPs. Adv. Neural Inform. Proc. Systems 35:32680–32693.Google Scholar
• [17] Hu Y, Ma H, Li N, Dai B (2025) Efficient duple perturbation robustness in low-rank MDPs. Ozay N, Balzano L, Panagou D, Abate A, eds. Proc. 7th Annual Learn. Dynam. Control Conf. (L4DC 2025), Proceedings of Machine Learning Research, vol. 283 (PMLR, New York), 723–737.Google Scholar
• [18] Iyengar G (2005) Robust dynamic programming. Math. Oper. Res. 30(2):257–280.Link, Google Scholar
• [19] Kumar N, Gupta A, Elfatihi MM, Ramponi G, Levy KY, Mannor S (2025) Non-rectangular robust MDPs with normed uncertainty sets. Belgrave D, Zhang C, Montoya LN, Lin HT, Pascanu R, Koniusz P, Ghassemi M, Chen N, Meza Ruíz IV, Loaiza-Bonilla A, eds. Adv. Neural Inform. Processing Systems 38: Main Conf. (Curran Associates, Inc., Red Hook, NY), 43270–43313.Google Scholar
• [20] Li M, Kuhn D, Sutter T (2025) Towards optimal offline reinforcement learning. Preprint, submitted March 15, https://arxiv.org/abs/2503.12283.Google Scholar
• [21] Li Y, Zhao T, Lan G (2022) First-order policy optimization for robust Markov decision process. Preprint, submitted June 10, https://arxiv.org/abs/2209.10579.Google Scholar
• [22] Ma X, Liang Z, Blanchet J, Liu M, Xia L, Zhang J, Zhao Q, Zhou Z (2022) Distributionally robust offline reinforcement learning with linear function approximation. Preprint, submitted January 27, https://arxiv.org/abs/2209.06620.Google Scholar
• [23] Mannor S, Mebel O, Xu H (2016) Robust MDPs with k-rectangular uncertainty. Math. Oper. Res. 41(4):1484–1509.Link, Google Scholar
• [24] Nilim A, Ghaoui LE (2005) Robust control of Markov decision processes with uncertain transition probabilities. Oper. Res. 53(5):780–798.Link, Google Scholar
• [25] Puterman ML (2014) Markov Decision Processes: Discrete Stochastic Dynamic Programming (John Wiley & Sons, Hoboken, NJ).Google Scholar
• [26] Rockafellar RT (2015) Convex Analysis: (PMS-28) (Princeton University Press, Princeton, NJ).Google Scholar
• [27] Straszewicz S (1935) Über exponierte punkte abgeschlossener punktmengen. Fundamenta Mathematicae 24(1):139–143.Crossref, Google Scholar
• [28] Tewari A, Bartlett PL (2007) Bounded parameter Markov decision processes with average reward criterion. Bshouty NH, Gentile C, eds. Learn. Theory: 20th Annual Conf. Learn. Theory, COLT 2007, Lecture Notes in Computer Science, vol. 4539 (Springer-Verlag, Berlin, Germany), 263–277.Google Scholar
• [29] Wang Q, Ho CP, Petrik M (2023) Policy gradient in robust MDPs with global convergence guarantee. Krause A, Brunskill E, Cho K, Engelhardt B, Sabato S, Scarlett J, eds. Proc. 40th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 202 (PMLR, Cambridge, MA), 35763–35797.Google Scholar
• [30] Wang S, Si N, Blanchet J, Zhou Z (2023) On the foundation of distributionally robust reinforcement learning. Preprint, submitted November 15, https://arxiv.org/abs/2311.09018.Google Scholar
• [31] Wang Y, Zou S (2022) Policy gradient method for robust reinforcement learning. Chaudhuri K, Jegelka S, Song L, Szepesvári C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 162 (PMLR, Cambridge, MA), 23484–23526.Google Scholar
• [32] Wang Y, Velasquez A, Atia G, Prater-Bennette A, Zou S (2023) Robust average-reward Markov decision processes. Williams B, Chen Y, Neville J, eds. Proc. Thirty-Seventh AAAI Conf. Artificial Intelligence (AAAI-23), vol. 37 (AAAI Press, Washington, DC), 15215–15223.Google Scholar
• [33] Wiesemann W, Kuhn D, Rustem B (2013) Robust Markov decision processes. Math. Oper. Res. 38(1):153–183.Link, Google Scholar