  Graph games and Markov decision processes (MDPs) are standard models in
reactive synthesis and verification of probabilistic systems with
nondeterminism. The class of $\omega$-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.
