{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,28]],"date-time":"2026-05-28T00:58:07Z","timestamp":1779929887624,"version":"3.53.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T00:00:00Z","timestamp":1769904000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T00:00:00Z","timestamp":1769904000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Softw Tools Technol Transfer"],"published-print":{"date-parts":[[2026,2]]},"DOI":"10.1007\/s10009-026-00849-x","type":"journal-article","created":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T14:45:45Z","timestamp":1774536345000},"page":"5-25","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Floyd-Warshall approach to value computation in Markov decision processes"],"prefix":"10.1007","volume":"28","author":[{"given":"Aymeric","family":"C\u00f4me","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eric","family":"Fabre","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lo\u00efc","family":"H\u00e9lou\u00ebt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,3,26]]},"reference":[{"issue":"98","key":"849_CR1","first-page":"1","volume":"22","author":"A. Agarwal","year":"2021","unstructured":"Agarwal, A., Kakade, S.M., Lee, J.D., Mahajan, G.: On the theory of policy gradient methods: optimality, approximation, and distribution shift. J. Mach. Learn. Res. 22(98), 1\u201376 (2021)","journal-title":"J. Mach. Learn. Res."},{"key":"849_CR2","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-3-642-04081-8_6","volume-title":"CONCUR 2009 - Concurrency Theory","author":"E. Asarin","year":"2009","unstructured":"Asarin, E., Degorre, A.: Volume and entropy of regular timed languages: discretization approach. In: CONCUR 2009 - Concurrency Theory. LNCS, vol.\u00a05710, pp.\u00a069\u201383 (2009)"},{"key":"849_CR3","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/978-3-662-54580-5_16","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"C. Baier","year":"2017","unstructured":"Baier, C., Klein, J., Kl\u00fcppelholz, S., Wunderlich, S.: Maximizing the conditional expected reward for reaching the goal. In: Legay, A., Margaria, T. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. LNCS, vol.\u00a010206, pp.\u00a0269\u2013285 (2017)"},{"key":"849_CR4","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/978-3-319-91908-9_21","volume-title":"Computing and Software Science - State of the Art and Perspectives","author":"C. Baier","year":"2019","unstructured":"Baier, C., Hermanns, H., Katoen, J.-P.: The 10, 000 facets of MDP model checking. In: Steffen, B., Woeginger, G.J. (eds.) Computing and Software Science - State of the Art and Perspectives. LNCS, vol.\u00a010000, pp.\u00a0420\u2013451. Springer, Berlin (2019)"},{"key":"849_CR5","series-title":"LNCS","first-page":"1","volume-title":"Algebraic Informatics - 6th International Conference, CAI 2015, Proceedings","author":"B. Balle","year":"2015","unstructured":"Balle, B., Mohri, M.: Learning weighted automata. In: Maletti, A. (ed.) Algebraic Informatics - 6th International Conference, CAI 2015, Proceedings. LNCS, vol.\u00a09270, pp.\u00a01\u201321. Springer, Berlin (2015)"},{"issue":"1\u20132","key":"849_CR6","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0004-3702(94)00011-O","volume":"72","author":"A.G. Barto","year":"1995","unstructured":"Barto, A.G., Bradtke, S.J., Singh, S.P.: Learning to act using real-time dynamic programming. Artif. Intell. 72(1\u20132), 81\u2013138 (1995)","journal-title":"Artif. Intell."},{"key":"849_CR7","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1613\/jair.806","volume":"15","author":"J. Baxter","year":"2001","unstructured":"Baxter, J., Bartlett, P.L.: Infinite-horizon policy-gradient estimation. J. Artif. Intell. Res. 15, 319\u2013350 (2001)","journal-title":"J. Artif. Intell. Res."},{"key":"849_CR8","doi-asserted-by":"publisher","first-page":"5726","DOI":"10.1109\/CDC.2017.8264524","volume-title":"2017 IEEE 56th Annual Conference on Decision and Control (CDC)","author":"H. Bazille","year":"2017","unstructured":"Bazille, H., Fabre, E., Genest, B.: Diagnosability degree of stochastic discrete event systems. In: 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp.\u00a05726\u20135731 (2017)"},{"key":"849_CR9","volume-title":"Dynamic Programming and Optimal Control","author":"D.P. Bertsekas","year":"1995","unstructured":"Bertsekas, D.P.: Dynamic Programming and Optimal Control, vol.\u00a01, 1st edn. MIT Press, Cambridge (1995)","edition":"1"},{"issue":"3","key":"849_CR10","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/s11768-011-1005-3","volume":"9","author":"D.P. Bertsekas","year":"2011","unstructured":"Bertsekas, D.P.: Approximate policy iteration: a survey and some new methods. J. Control Theory Appl. 9(3), 310\u2013335 (2011)","journal-title":"J. Control Theory Appl."},{"key":"849_CR11","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/978-3-031-68416-6_17","volume-title":"Quantitative Evaluation of Systems and Formal Modeling and Analysis of Timed Systems","author":"A. C\u00f4me","year":"2024","unstructured":"C\u00f4me, A., Fabre, \u00c9., H\u00e9lou\u00ebt, L.: A Floyd-Warshall approach to value computation in Markov decision processes. In: Hillston, J., Soudjani, S., Waga, M. (eds.) Quantitative Evaluation of Systems and Formal Modeling and Analysis of Timed Systems. LNCS, vol.\u00a014996, pp.\u00a0284\u2013301. Springer, Berlin (2024)"},{"key":"849_CR12","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/11682462_32","volume-title":"LATIN 2006: Theoretical Informatics","author":"C. Cortes","year":"2006","unstructured":"Cortes, C., Mohri, M., Rastogi, A., Riley, M.D.: Efficient computation of the relative entropy of probabilistic automata. In: LATIN 2006: Theoretical Informatics, pp.\u00a0323\u2013336. Springer, Berlin (2006)"},{"key":"849_CR13","first-page":"181","volume":"42","author":"P. Dai Mausam","year":"2011","unstructured":"Dai Mausam, P., Weld, D.S., Goldsmith, J.: Topological value iteration algorithms. J. Artif. Intell. Res. 42, 181\u2013209 (2011)","journal-title":"J. Artif. Intell. Res."},{"issue":"1","key":"849_CR14","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/j.tcs.2005.07.033","volume":"345","author":"L. de Alfaro","year":"2005","unstructured":"de Alfaro, L., Faella, M., Henzinger, T.A., Majumdar, R., Stoelinga, M.: Model checking discounted temporal properties. Theor. Comput. Sci. 345(1), 139\u2013170 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"849_CR15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-642-21455-4_3","volume-title":"Formal Methods for Eternal Networked Software Systems","author":"V. Forejt","year":"2011","unstructured":"Forejt, V., Kwiatkowska, M.Z., Norman, G., Parker, D.: Automated verification techniques for probabilistic systems. In: Bernardo, M., Issarny, V. (eds.) Formal Methods for Eternal Networked Software Systems. LNCS, vol.\u00a06659, pp.\u00a053\u2013113. Springer, Berlin (2011)"},{"key":"849_CR16","volume-title":"Matrix Computations","author":"G.H. Golub","year":"2013","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix Computations. JHU Press (2013)"},{"key":"849_CR17","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-319-11439-2_10","volume-title":"8th International Workshop on Reachability Problems (RP\u201914)","author":"S. Haddad","year":"2014","unstructured":"Haddad, S., Monmege, B.: Reachability in MDPs: refining convergence of value iteration. In: 8th International Workshop on Reachability Problems (RP\u201914), vol.\u00a08762, pp.\u00a0125\u2013137. Springer, Berlin (2014)"},{"issue":"1\u20132","key":"849_CR18","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/S0004-3702(01)00106-0","volume":"129","author":"E.A. Hansen","year":"2001","unstructured":"Hansen, E.A., Zilberstein, S.: Lao\u22c6: a heuristic search algorithm that finds solutions with loops. Artif. Intell. 129(1\u20132), 35\u201362 (2001)","journal-title":"Artif. Intell."},{"issue":"5","key":"849_CR19","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1007\/BF01211866","volume":"6","author":"H. Hansson","year":"1994","unstructured":"Hansson, H., Jonsson, B.: A logic for reasoning about time and reliability. Form. Asp. Comput. 6(5), 512\u2013535 (1994)","journal-title":"Form. Asp. Comput."},{"issue":"2","key":"849_CR20","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"P.E. Hart","year":"1968","unstructured":"Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100\u2013107 (1968)","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"849_CR21","volume-title":"Dynamic Programming and Markov Processes","author":"R.A. Howard","year":"1960","unstructured":"Howard, R.A.: Dynamic Programming and Markov Processes. MIT Press, Cambridge (1960)"},{"issue":"1","key":"849_CR22","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1115\/1.3662552","volume":"82","author":"R.E. Kalman","year":"1960","unstructured":"Kalman, R.E.: A new approach to linear filtering and prediction problems. J. Basic Eng. 82(1), 35\u201345 (1960)","journal-title":"J. Basic Eng."},{"issue":"1","key":"849_CR23","first-page":"130","volume":"21","author":"A. Kolobov","year":"2011","unstructured":"Kolobov, A., Mausam, M., Weld, D., Geffner, H.: Heuristic search for generalized stochastic shortest path MDPs. Proc. Int. Conf. Autom. Plan. Sched. 21(1), 130\u2013137 (2011)","journal-title":"Proc. Int. Conf. Autom. Plan. Sched."},{"issue":"2\u20133","key":"849_CR24","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0004-3702(90)90054-4","volume":"42","author":"R.E. Korf","year":"1990","unstructured":"Korf, R.E.: Real-time heuristic search. Artif. Intell. 42(2\u20133), 189\u2013211 (1990)","journal-title":"Artif. Intell."},{"key":"849_CR25","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1007\/978-3-319-68167-2_25","volume-title":"Automated Technology for Verification and Analysis","author":"J. Kret\u00ednsk\u00fd","year":"2017","unstructured":"Kret\u00ednsk\u00fd, J., Meggendorfer, T.: Efficient strategy iteration for mean payoff in Markov decision processes. In: D\u2019Souza, D., Narayan Kumar, K. (eds.) Automated Technology for Verification and Analysis. LNCS, vol.\u00a010482, pp.\u00a0380\u2013399. Springer, Berlin (2017)"},{"key":"849_CR26","first-page":"1107","volume":"4","author":"M.G. Lagoudakis","year":"2003","unstructured":"Lagoudakis, M.G., Parr, R.: Least-squares policy iteration. J. Mach. Learn. Res. 4, 1107\u20131149 (2003)","journal-title":"J. Mach. Learn. Res."},{"issue":"19","key":"849_CR27","first-page":"1","volume":"17","author":"A. Lazaric","year":"2016","unstructured":"Lazaric, A., Ghavamzadeh, M., et al.: Analysis of classification-based policy iteration algorithms. J. Mach. Learn. Res. 17(19), 1\u201330 (2016)","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"849_CR28","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1023\/A:1022635613229","volume":"13","author":"A.W. Moore","year":"1993","unstructured":"Moore, A.W., Atkeson, C.G.: Prioritized sweeping: reinforcement learning with less data and less time. Mach. Learn. 13(1), 103\u2013130 (1993)","journal-title":"Mach. Learn."},{"issue":"3","key":"849_CR29","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1002\/wics.13","volume":"1","author":"J.L. Nazareth","year":"2009","unstructured":"Nazareth, J.L.: Conjugate gradient method. Wiley Interdiscip. Rev. Comput. Stat. 1(3), 348\u2013353 (2009)","journal-title":"Wiley Interdiscip. Rev. Comput. Stat."},{"key":"849_CR30","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0004-3702(86)90072-X","volume":"29","author":"J. Pearl","year":"1986","unstructured":"Pearl, J.: Fusion, propagation, and structuring in belief networks. Artif. Intell. 29, 241\u2013288 (1986)","journal-title":"Artif. Intell."},{"key":"849_CR31","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316887","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"M.L. Puterman","year":"1994","unstructured":"Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming, 1st edn. Wiley, New York (1994)","edition":"1"},{"issue":"27","key":"849_CR32","first-page":"79","volume":"25","author":"S. Russell","year":"1995","unstructured":"Russell, S., Norvig, P.: A modern approach. Artif. Intell. 25(27), 79\u201380 (1995)","journal-title":"Artif. Intell."},{"issue":"49","key":"849_CR33","first-page":"1629","volume":"16","author":"B. Scherrer","year":"2015","unstructured":"Scherrer, B., Ghavamzadeh, M., Gabillon, V., Lesner, B., Geist, M.: Approximate modified policy iteration and its application to the game of Tetris. J. Mach. Learn. Res. 16(49), 1629\u20131676 (2015)","journal-title":"J. Mach. Learn. Res."},{"key":"849_CR34","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1999","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1999)"},{"key":"849_CR35","first-page":"1889","volume-title":"32nd International Conference on Machine Learning, PMLR","author":"J. Schulman","year":"2015","unstructured":"Schulman, J., Levine, S., Abbeel, P., Jordan, M., Moritz, P.: Trust region policy optimization. In: 32nd International Conference on Machine Learning, PMLR, vol.\u00a037, pp.\u00a01889\u20131897 (2015)"},{"key":"849_CR36","unstructured":"Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy optimization algorithms (2017)"},{"issue":"5","key":"849_CR37","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1002\/nav.21992","volume":"70","author":"A. Sidford","year":"2023","unstructured":"Sidford, A., Wang, M., Wu, X., Ye, Y.: Variance reduced value iteration and faster algorithms for solving Markov decision processes. Nav. Res. Logist. 70(5), 423\u2013442 (2023)","journal-title":"Nav. Res. Logist."},{"key":"849_CR38","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/B978-1-55860-335-6.50042-8","volume-title":"Machine Learning Proceedings 1994","author":"S.P. Singh","year":"1994","unstructured":"Singh, S.P., Jaakkola, T., Jordan, M.I.: Learning without state-estimation in partially observable Markovian decision processes. In: Machine Learning Proceedings 1994, pp.\u00a0284\u2013292. Elsevier, Amsterdam (1994)"},{"issue":"4","key":"849_CR39","doi-asserted-by":"publisher","first-page":"794","DOI":"10.2307\/3213832","volume":"19","author":"M.J. Sobel","year":"1982","unstructured":"Sobel, M.J.: The variance of discounted Markov decision processes. J. Appl. Probab. 19(4), 794\u2013802 (1982)","journal-title":"J. Appl. Probab."},{"key":"849_CR40","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1109\/TNN.2004.842673","volume":"16","author":"R.S. Sutton","year":"2005","unstructured":"Sutton, R.S., Barto, A.G.: Reinforcement learning: an introduction. IEEE Trans. Neural Netw. 16, 285\u2013286 (2005)","journal-title":"IEEE Trans. Neural Netw."},{"key":"849_CR41","unstructured":"Sutton, R.S., McAllester, D., Singh, S., Mansour, Y.: Policy gradient methods for reinforcement learning with function approximation. Adv. Neural Inf. Process. Syst. 12 (1999)"},{"key":"849_CR42","doi-asserted-by":"crossref","unstructured":"Tamar, A., Wu, Y., Thomas, G., Levine, S., Abbeel, P.: Value iteration networks. Adv. Neural Inf. Process. Syst. 29 (2016)","DOI":"10.24963\/ijcai.2017\/700"},{"key":"849_CR43","first-page":"744","volume-title":"Proceedings of the 20th European Conference on Artificial Intelligence, ECAI\u201912","author":"F. Teichteil-K\u00f6nigsbuch","year":"2012","unstructured":"Teichteil-K\u00f6nigsbuch, F.: Path-constrained Markov decision processes: bridging the gap between probabilistic model-checking and decision-theoretic planning. In: Proceedings of the 20th European Conference on Artificial Intelligence, ECAI\u201912, pp.\u00a0744\u2013749. IOS Press, NLD (2012)"},{"key":"849_CR44","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.automatica.2017.11.012","volume":"88","author":"L. Xia","year":"2018","unstructured":"Xia, L.: Mean\u2013variance optimization of discrete time discounted Markov decision processes. Automatica 88, 76\u201382 (2018)","journal-title":"Automatica"}],"container-title":["International Journal on Software Tools for Technology Transfer"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10009-026-00849-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10009-026-00849-x","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10009-026-00849-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,22]],"date-time":"2026-05-22T16:02:17Z","timestamp":1779465737000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10009-026-00849-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["849"],"URL":"https:\/\/doi.org\/10.1007\/s10009-026-00849-x","relation":{},"ISSN":["1433-2779","1433-2787"],"issn-type":[{"value":"1433-2779","type":"print"},{"value":"1433-2787","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2]]},"assertion":[{"value":"27 February 2026","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2026","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}