---
_id: '6942'
abstract:
- lang: eng
  text: "Graph games and Markov decision processes (MDPs) are standard models in reactive
    synthesis and verification of probabilistic systems with nondeterminism. The class
    of   \U0001D714 -regular winning conditions; e.g., safety, reachability, liveness,
    parity conditions; provides a robust and expressive specification formalism for
    properties that arise in analysis of reactive systems. The resolutions of nondeterminism
    in games and MDPs are represented as strategies, and we consider succinct representation
    of such strategies. The decision-tree data structure from machine learning retains
    the flavor of decisions of strategies and allows entropy-based minimization to
    obtain succinct trees. However, in contrast to traditional machine-learning problems
    where small errors are allowed, for winning strategies in graph games and MDPs
    no error is allowed, and the decision tree must represent the entire strategy.
    In this work we propose decision trees with linear classifiers for representation
    of strategies in graph games and MDPs. We have implemented strategy representation
    using this data structure and we present experimental results for problems on
    graph games and MDPs, which show that this new data structure presents a much
    more efficient strategy representation as compared to standard decision trees."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Pranav
  full_name: Ashok, Pranav
  last_name: Ashok
- first_name: Tomáš
  full_name: Brázdil, Tomáš
  last_name: Brázdil
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Jan
  full_name: Křetínský, Jan
  last_name: Křetínský
- first_name: Christoph
  full_name: Lampert, Christoph
  id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
  last_name: Lampert
  orcid: 0000-0001-8622-7887
- first_name: Viktor
  full_name: Toman, Viktor
  id: 3AF3DA7C-F248-11E8-B48F-1D18A9856A87
  last_name: Toman
  orcid: 0000-0001-9036-063X
citation:
  ama: 'Ashok P, Brázdil T, Chatterjee K, Křetínský J, Lampert C, Toman V. Strategy
    representation by decision trees with linear classifiers. In: <i>16th International
    Conference on Quantitative Evaluation of Systems</i>. Vol 11785. Springer Nature;
    2019:109-128. doi:<a href="https://doi.org/10.1007/978-3-030-30281-8_7">10.1007/978-3-030-30281-8_7</a>'
  apa: 'Ashok, P., Brázdil, T., Chatterjee, K., Křetínský, J., Lampert, C., &#38;
    Toman, V. (2019). Strategy representation by decision trees with linear classifiers.
    In <i>16th International Conference on Quantitative Evaluation of Systems</i>
    (Vol. 11785, pp. 109–128). Glasgow, United Kingdom: Springer Nature. <a href="https://doi.org/10.1007/978-3-030-30281-8_7">https://doi.org/10.1007/978-3-030-30281-8_7</a>'
  chicago: Ashok, Pranav, Tomáš Brázdil, Krishnendu Chatterjee, Jan Křetínský, Christoph
    Lampert, and Viktor Toman. “Strategy Representation by Decision Trees with Linear
    Classifiers.” In <i>16th International Conference on Quantitative Evaluation of
    Systems</i>, 11785:109–28. Springer Nature, 2019. <a href="https://doi.org/10.1007/978-3-030-30281-8_7">https://doi.org/10.1007/978-3-030-30281-8_7</a>.
  ieee: P. Ashok, T. Brázdil, K. Chatterjee, J. Křetínský, C. Lampert, and V. Toman,
    “Strategy representation by decision trees with linear classifiers,” in <i>16th
    International Conference on Quantitative Evaluation of Systems</i>, Glasgow, United
    Kingdom, 2019, vol. 11785, pp. 109–128.
  ista: 'Ashok P, Brázdil T, Chatterjee K, Křetínský J, Lampert C, Toman V. 2019.
    Strategy representation by decision trees with linear classifiers. 16th International
    Conference on Quantitative Evaluation of Systems. QEST: Quantitative Evaluation
    of Systems, LNCS, vol. 11785, 109–128.'
  mla: Ashok, Pranav, et al. “Strategy Representation by Decision Trees with Linear
    Classifiers.” <i>16th International Conference on Quantitative Evaluation of Systems</i>,
    vol. 11785, Springer Nature, 2019, pp. 109–28, doi:<a href="https://doi.org/10.1007/978-3-030-30281-8_7">10.1007/978-3-030-30281-8_7</a>.
  short: P. Ashok, T. Brázdil, K. Chatterjee, J. Křetínský, C. Lampert, V. Toman,
    in:, 16th International Conference on Quantitative Evaluation of Systems, Springer
    Nature, 2019, pp. 109–128.
conference:
  end_date: 2019-09-12
  location: Glasgow, United Kingdom
  name: 'QEST: Quantitative Evaluation of Systems'
  start_date: 2019-09-10
date_created: 2019-10-14T06:57:49Z
date_published: 2019-09-04T00:00:00Z
date_updated: 2025-04-14T13:51:05Z
day: '04'
department:
- _id: KrCh
- _id: ChLa
doi: 10.1007/978-3-030-30281-8_7
external_id:
  arxiv:
  - '1906.08178'
  isi:
  - '000679281300007'
intvolume: '     11785'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1906.08178
month: '09'
oa: 1
oa_version: Preprint
page: 109-128
project:
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11402-N23
  name: Rigorous Systems Engineering
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
  grant_number: ICT15-003
  name: Efficient Algorithms for Computer Aided Verification
publication: 16th International Conference on Quantitative Evaluation of Systems
publication_identifier:
  eisbn:
  - '9783030302818'
  isbn:
  - '9783030302801'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Strategy representation by decision trees with linear classifiers
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 11785
year: '2019'
...