---
_id: '13967'
abstract:
- lang: eng
  text: 'A classic solution technique for Markov decision processes (MDP) and stochastic
    games (SG) is value iteration (VI). Due to its good practical performance, this
    approximative approach is typically preferred over exact techniques, even though
    no practical bounds on the imprecision of the result could be given until recently.
    As a consequence, even the most used model checkers could return arbitrarily wrong
    results. Over the past decade, different works derived stopping criteria, indicating
    when the precision reaches the desired level, for various settings, in particular
    MDP with reachability, total reward, and mean payoff, and SG with reachability.In
    this paper, we provide the first stopping criteria for VI on SG with total reward
    and mean payoff, yielding the first anytime algorithms in these settings. To this
    end, we provide the solution in two flavours: First through a reduction to the
    MDP case and second directly on SG. The former is simpler and automatically utilizes
    any advances on MDP. The latter allows for more local computations, heading towards
    better practical efficiency.Our solution unifies the previously mentioned approaches
    for MDP and SG and their underlying ideas. To achieve this, we isolate objective-specific
    subroutines as well as identify objective-independent concepts. These structural
    concepts, while surprisingly simple, form the very essence of the unified solution.'
acknowledgement: This research was funded in part by DFG projects 383882557 “SUV”
  and 427755713 “GOPro”.
article_processing_charge: No
arxiv: 1
author:
- first_name: Jan
  full_name: Kretinsky, Jan
  id: 44CEF464-F248-11E8-B48F-1D18A9856A87
  last_name: Kretinsky
  orcid: 0000-0002-8122-2881
- first_name: Tobias
  full_name: Meggendorfer, Tobias
  id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
  last_name: Meggendorfer
  orcid: 0000-0002-1712-2165
- first_name: Maximilian
  full_name: Weininger, Maximilian
  id: 02ab0197-cc70-11ed-ab61-918e71f56881
  last_name: Weininger
citation:
  ama: 'Kretinsky J, Meggendorfer T, Weininger M. Stopping criteria for value iteration
    on stochastic games with quantitative objectives. In: <i>38th Annual ACM/IEEE
    Symposium on Logic in Computer Science</i>. Vol 2023. Institute of Electrical
    and Electronics Engineers; 2023. doi:<a href="https://doi.org/10.1109/LICS56636.2023.10175771">10.1109/LICS56636.2023.10175771</a>'
  apa: 'Kretinsky, J., Meggendorfer, T., &#38; Weininger, M. (2023). Stopping criteria
    for value iteration on stochastic games with quantitative objectives. In <i>38th
    Annual ACM/IEEE Symposium on Logic in Computer Science</i> (Vol. 2023). Boston,
    MA, United States: Institute of Electrical and Electronics Engineers. <a href="https://doi.org/10.1109/LICS56636.2023.10175771">https://doi.org/10.1109/LICS56636.2023.10175771</a>'
  chicago: Kretinsky, Jan, Tobias Meggendorfer, and Maximilian Weininger. “Stopping
    Criteria for Value Iteration on Stochastic Games with Quantitative Objectives.”
    In <i>38th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Vol. 2023.
    Institute of Electrical and Electronics Engineers, 2023. <a href="https://doi.org/10.1109/LICS56636.2023.10175771">https://doi.org/10.1109/LICS56636.2023.10175771</a>.
  ieee: J. Kretinsky, T. Meggendorfer, and M. Weininger, “Stopping criteria for value
    iteration on stochastic games with quantitative objectives,” in <i>38th Annual
    ACM/IEEE Symposium on Logic in Computer Science</i>, Boston, MA, United States,
    2023, vol. 2023.
  ista: 'Kretinsky J, Meggendorfer T, Weininger M. 2023. Stopping criteria for value
    iteration on stochastic games with quantitative objectives. 38th Annual ACM/IEEE
    Symposium on Logic in Computer Science. LICS: Symposium on Logic in Computer Science
    vol. 2023.'
  mla: Kretinsky, Jan, et al. “Stopping Criteria for Value Iteration on Stochastic
    Games with Quantitative Objectives.” <i>38th Annual ACM/IEEE Symposium on Logic
    in Computer Science</i>, vol. 2023, Institute of Electrical and Electronics Engineers,
    2023, doi:<a href="https://doi.org/10.1109/LICS56636.2023.10175771">10.1109/LICS56636.2023.10175771</a>.
  short: J. Kretinsky, T. Meggendorfer, M. Weininger, in:, 38th Annual ACM/IEEE Symposium
    on Logic in Computer Science, Institute of Electrical and Electronics Engineers,
    2023.
conference:
  end_date: 2023-06-29
  location: Boston, MA, United States
  name: 'LICS: Symposium on Logic in Computer Science'
  start_date: 2023-06-26
date_created: 2023-08-06T22:01:10Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-12-13T12:06:10Z
day: '01'
department:
- _id: KrCh
doi: 10.1109/LICS56636.2023.10175771
external_id:
  arxiv:
  - '2304.09930'
  isi:
  - '001036707700042'
intvolume: '      2023'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2304.09930
month: '07'
oa: 1
oa_version: Preprint
publication: 38th Annual ACM/IEEE Symposium on Logic in Computer Science
publication_identifier:
  isbn:
  - '9798350335873'
  issn:
  - 1043-6871
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Stopping criteria for value iteration on stochastic games with quantitative
  objectives
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2023
year: '2023'
...