--- _id: '2715' abstract: - lang: eng text: 'We consider Markov decision processes (MDPs) with specifications given as Büchi (liveness) objectives. We consider the problem of computing the set of almost-sure winning vertices from where the objective can be ensured with probability 1. We study for the first time the average case complexity of the classical algorithm for computing the set of almost-sure winning vertices for MDPs with Büchi objectives. Our contributions are as follows: First, we show that for MDPs with constant out-degree the expected number of iterations is at most logarithmic and the average case running time is linear (as compared to the worst case linear number of iterations and quadratic time complexity). Second, for the average case analysis over all MDPs we show that the expected number of iterations is constant and the average case running time is linear (again as compared to the worst case linear number of iterations and quadratic time complexity). Finally we also show that given that all MDPs are equally likely, the probability that the classical algorithm requires more than constant number of iterations is exponentially small.' alternative_title: - LIPIcs author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Manas full_name: Joglekar, Manas last_name: Joglekar - first_name: Nisarg full_name: Shah, Nisarg last_name: Shah citation: ama: 'Chatterjee K, Joglekar M, Shah N. Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives. In: Vol 18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2012:461-473. doi:10.4230/LIPIcs.FSTTCS.2012.461' apa: 'Chatterjee, K., Joglekar, M., & Shah, N. (2012). Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives (Vol. 18, pp. 461–473). Presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Hyderabad, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461' chicago: Chatterjee, Krishnendu, Manas Joglekar, and Nisarg Shah. “Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives,” 18:461–73. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461. ieee: 'K. Chatterjee, M. Joglekar, and N. Shah, “Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives,” presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Hyderabad, India, 2012, vol. 18, pp. 461–473.' ista: 'Chatterjee K, Joglekar M, Shah N. 2012. Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 18, 461–473.' mla: Chatterjee, Krishnendu, et al. Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives. Vol. 18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 461–73, doi:10.4230/LIPIcs.FSTTCS.2012.461. short: K. Chatterjee, M. Joglekar, N. Shah, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 461–473. conference: end_date: 2012-12-17 location: Hyderabad, India name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science' start_date: 2012-12-15 date_created: 2018-12-11T11:59:13Z date_published: 2012-12-10T00:00:00Z date_updated: 2023-02-23T10:06:04Z day: '10' ddc: - '000' department: - _id: KrCh doi: 10.4230/LIPIcs.FSTTCS.2012.461 ec_funded: 1 file: - access_level: open_access checksum: d4d644ed1a885dbfc4fa1ef4c5724dab content_type: application/pdf creator: system date_created: 2018-12-12T10:13:53Z date_updated: 2020-07-14T12:45:45Z file_id: '5040' file_name: IST-2016-525-v1+1_42_1_.pdf file_size: 519040 relation: main_file file_date_updated: 2020-07-14T12:45:45Z has_accepted_license: '1' intvolume: ' 18' language: - iso: eng license: https://creativecommons.org/licenses/by-nc-nd/4.0/ month: '12' oa: 1 oa_version: Published Version page: 461 - 473 project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik publist_id: '4180' pubrep_id: '525' quality_controlled: '1' related_material: record: - id: '1598' relation: later_version status: public scopus_import: 1 status: public title: Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives tmp: image: /images/cc_by_nc_nd.png legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) short: CC BY-NC-ND (4.0) type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 18 year: '2012' ...