{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:32:29Z","timestamp":1759336349950,"version":"3.40.4"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,8,29]],"date-time":"2014-08-29T00:00:00Z","timestamp":1409270400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Softw Tools Technol Transfer"],"published-print":{"date-parts":[[2015,8]]},"DOI":"10.1007\/s10009-014-0344-z","type":"journal-article","created":{"date-parts":[[2014,8,28]],"date-time":"2014-08-28T08:56:04Z","timestamp":1409216164000},"page":"457-467","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Approximate planning and verification for large Markov decision processes"],"prefix":"10.1007","volume":"17","author":[{"given":"Richard","family":"Lassaigne","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sylvain","family":"Peyronnet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,8,29]]},"reference":[{"issue":"1","key":"344_CR1","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1023\/A:1008739929481","volume":"15","author":"R Alur","year":"1999","unstructured":"Alur, R., Henzinger, T.A.: Reactive modules. Formal Methods System Design 15(1), 7\u201348 (1999)","journal-title":"Formal Methods System Design"},{"key":"344_CR2","doi-asserted-by":"crossref","unstructured":"Andrea, B., Luca De A.: Model checking of probabalistic and nondeterministic systems. In: Proc. 15th conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 1026 of Lecture Notes in Computer Science, pp. 499\u2013513. Springer, Berlin (1995)","DOI":"10.1007\/3-540-60692-0_70"},{"issue":"1","key":"344_CR3","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theory Comput. 8(1), 121\u2013164 (2012)","journal-title":"Theory Comput."},{"issue":"2\u20133","key":"344_CR4","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1023\/A:1013689704352","volume":"47","author":"P Auer","year":"2002","unstructured":"Auer, P., Cesa-Bianchi, N., Fischer, P.: Finite-time analysis of the multiarmed bandit problem. Mach. Learn. 47(2\u20133), 235\u2013256 (2002)","journal-title":"Mach. Learn."},{"issue":"1","key":"344_CR5","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1023\/A:1009634810396","volume":"5","author":"DP Bertsekas","year":"1999","unstructured":"Bertsekas, D.P., Castanon, D.A.: Rollout algorithms for stochastic scheduling problems. J. Heuristics 5(1), 89\u2013108 (1999)","journal-title":"J. Heuristics"},{"key":"344_CR6","doi-asserted-by":"crossref","unstructured":"Chang, H.S., Fu, M.C., Hu, J., Marcus, S.I.: A survey of some simulation-based algorithms for markov decision processes. Commun. Inf. Systems 7(1), 59\u201392 (2007)","DOI":"10.4310\/CIS.2007.v7.n1.a4"},{"issue":"4","key":"344_CR7","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1145\/210332.210339","volume":"42","author":"C Courcoubetis","year":"1995","unstructured":"Courcoubetis, C., Yannakakis, M.: The complexity of probabilistic verification. J. ACM (JACM) 42(4), 857\u2013907 (1995)","journal-title":"J. ACM (JACM)"},{"key":"344_CR8","doi-asserted-by":"crossref","unstructured":"Fearnley, J.: Exponential lower bounds for policy iteration. In: Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6\u201310, 2010, Proceedings, Part II, volume 6199 of Lecture Notes in Computer Science, pp. 551\u2013562. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-14162-1_46"},{"key":"344_CR9","doi-asserted-by":"crossref","unstructured":"Friedmann, O.: An exponential lower bound for the parity game strategy improvement algorithm as we know it. In: Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009, 11\u201314 August 2009, Los Angeles, CA, USA, pp. 145\u2013156. IEEE Computer Society (2009)","DOI":"10.1109\/LICS.2009.27"},{"issue":"2","key":"344_CR10","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.entcs.2005.10.016","volume":"135","author":"G Guirado","year":"2006","unstructured":"Guirado, G., H\u00e9rault, T., Lassaigne, R., Peyronnet, S.: Distribution, approximation and probabilistic model checking. Electr. Notes Theor. Comput. Sci. - Proc. of Parallel and Distributed Model Checking (PDMC) 135(2), 19\u201330 (2006)","journal-title":"Electr. Notes Theor. Comput. Sci. - Proc. of Parallel and Distributed Model Checking (PDMC)"},{"key":"344_CR11","doi-asserted-by":"crossref","unstructured":"Hamidouche, K., Borghi, A., Esterie, P., Falcou, J., Peyronnet, S.: Three high performance architectures in the parallel approximate probabilistic model checking boat. In: Proc. of Parallel and Distributed Model Checking (PDMC) (2010)","DOI":"10.1109\/PDMC-HiBi.2010.12"},{"key":"344_CR12","unstructured":"Hansen, T.D., Miltersen, P.B., Zwick, U.: Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. In: Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 7\u20139, 2011. Proceedings, pp. 253\u2013263. Tsinghua University Press (2011)"},{"key":"344_CR13","doi-asserted-by":"crossref","unstructured":"Henriques, D., Martins, J.G., Zuliani, P., Platzer, A., Clarke, E.M.: Statistical model checking for markov decision processes. In: Quantitative Evaluation of Systems (QEST), 2012 Ninth International Conference on, pp. 84\u201393 (2012)","DOI":"10.1109\/QEST.2012.19"},{"key":"344_CR14","doi-asserted-by":"crossref","unstructured":"H\u00e9rault, T., Lassaigne, R., Magniette, F., Peyronnet, S.: Approximate probabilistic model checking. In: Proceedings of the 5th verification, model checking, and abstract interpretation (VMCAI), volume 2937 of Lecture Notes in Computer Science, pp. 73\u201384. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-24622-0_8"},{"key":"344_CR15","doi-asserted-by":"crossref","unstructured":"Herault, T., Lassaigne, R., Peyronnet, S.: APMC 3.0: Approximate verification of discrete and continuous time markov chains. In: Third International Conference on the Quantitative evaluation of systems (QEST), pp. 129\u2013130. IEEE Computer Society (2006)","DOI":"10.1109\/QEST.2006.5"},{"key":"344_CR16","doi-asserted-by":"crossref","unstructured":"Hinton, A., Kwiatkowska, M.Z., Norman, G., Parker, D.: PRISM: A tool for automatic verification of probabilistic systems. In: Tools and algorithms for construction and analysis of systems (TACAS), volume 3920 of Lecture Notes in Computer Science, pp. 441\u2013444. Springer, Berlin (2006)","DOI":"10.1007\/11691372_29"},{"issue":"301","key":"344_CR17","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"key":"344_CR18","volume-title":"Dynamic Programming and Markov Process","author":"RA Howard","year":"1960","unstructured":"Howard, R.A.: Dynamic Programming and Markov Process. MIT Press, Cambridge (1960)"},{"key":"344_CR19","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Luby, M.: Monte-carlo algorithms for enumeration and reliability problems. In: Proc. of the 24th Annual symposium on foundations of computer science (FOCS), pp. 56\u201364. IEEE (1983)","DOI":"10.1109\/SFCS.1983.35"},{"issue":"2\u20133","key":"344_CR20","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1023\/A:1017932429737","volume":"49","author":"M Kearns","year":"2002","unstructured":"Kearns, M., Mansour, Y., Ng, A.Y.: A sparse sampling algorithm for near-optimal planning in large Markov decision processes. Mach. Learn. 49(2\u20133), 193\u2013208 (2002)","journal-title":"Mach. Learn."},{"key":"344_CR21","doi-asserted-by":"crossref","unstructured":"Kwiatkowska, M., Norman, G., Parker, D.: PRISM 4.0: Verification of probabilistic real-time systems. In: Gopalakrishnan, G., Qadeer, S. (eds.), Proc. 23rd International Conference on Computer Aided Verification (CAV\u201911), volume 6806 of LNCS, pp. 585\u2013591. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-22110-1_47"},{"key":"344_CR22","doi-asserted-by":"crossref","unstructured":"Lassaigne, R., Peyronnet, S.: Approximate planning and verification for large markov decision processes. In: Proceedings of the ACM Symposium on applied computing, SAC 2012, pp. 1314\u20131319. ACM (2012)","DOI":"10.1145\/2245276.2231984"},{"issue":"1\u20133","key":"344_CR23","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.apal.2007.11.006","volume":"152","author":"R Lassaigne","year":"2008","unstructured":"Lassaigne, R., Peyronnet, S.: Probabilistic verification and approximation. Ann. Pure Appl. Logic 152(1\u20133), 122\u2013131 (2008)","journal-title":"Ann. Pure Appl. Logic"},{"key":"344_CR24","unstructured":"Legay, A., Sedwards, S.: Lightweight monte carlo algorithm for markov decision processes. arXiv preprint, arXiv:1310.3609 (2013)"},{"key":"344_CR25","doi-asserted-by":"crossref","DOI":"10.1002\/9780470316887","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"ML Putterman","year":"1994","unstructured":"Putterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, New York (1994)"},{"issue":"2","key":"344_CR26","first-page":"250","volume":"2","author":"R Segala","year":"1995","unstructured":"Segala, R., Lynch, N.: Probabilistic simulations for probabilistic processes. Nordic J. Comput. 2(2), 250\u2013273 (1995)","journal-title":"Nordic J. Comput."},{"key":"344_CR27","unstructured":"Tesauro, G., Galperin, G.R.: On-line policy improvement using monte-carlo search. Adv. Neural Inf. Process. Systems, 1068\u20131074 (1997)"},{"key":"344_CR28","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: Automatic verification of probabilistic concurrent finite state programs. In: Proc. of the 26th Foundations of Computer Science (FOCS), pp. 327\u2013338 (1984)","DOI":"10.1109\/SFCS.1985.12"},{"issue":"3","key":"344_CR29","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1287\/moor.1050.0149","volume":"30","author":"Y Ye","year":"2005","unstructured":"Ye, Y.: A new complexity result on solving the markov decision problem. Math. Oper. Res. 30(3), 733\u2013749 (2005)","journal-title":"Math. Oper. Res."}],"container-title":["International Journal on Software Tools for Technology Transfer"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10009-014-0344-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10009-014-0344-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10009-014-0344-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T11:15:05Z","timestamp":1746357305000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10009-014-0344-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,29]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["344"],"URL":"https:\/\/doi.org\/10.1007\/s10009-014-0344-z","relation":{},"ISSN":["1433-2779","1433-2787"],"issn-type":[{"type":"print","value":"1433-2779"},{"type":"electronic","value":"1433-2787"}],"subject":[],"published":{"date-parts":[[2014,8,29]]}}}