Tanja Kocjančič Antolík

Cécile Fougeron
email: cecile.fougeron@univ-paris3.fr

Consonant distortions in dysarthria due to Parkinson's disease, Amyotrophic Lateral Sclerosis and Cerebellar Ataxia

Keywords: dysarthria, consonant distortion, auditoryperceptual analysis

This paper addresses the presence and type of consonant distortions in speech of 79 French speakers with dysarthria due to Parkinson's disease (PD), Amyotrophic Lateral Sclerosis (ALS) and cerebellar ataxia (CA), and 26 control speakers. A total of 4990 consonants including selected occurrences of /d/, /g/, /t/, /k/ and /s/ in CV word-initial syllables, and /t/ in CV word medial and IP initial position were examined manually. Results show that the ALS group stands out with the more distorted consonants, while the PD and CA performed similarly. The distribution of the type of distortions differs also in the three dysarthric groups. While the most frequent type of distortion in ALS is incomplete closures of stops, devoicing of voiced consonant is the most frequent in the PD and CA groups. In the ALS group, distortions are also more uniformly distributed over consonant type and positions, while voiced consonants are more prone to distortion in PD and CA, as well as consonants in word medial position for PD. Finally, consonant distortions contribute strongly to perceived intelligibility and articulatory imprecision for the ALS and PD group.

Introduction

Dysarthria is a cover term for a group of speech disorders caused by impaired muscular control due to a damage to the central or peripheral nervous system. The exact muscular impairment follows the underlying damage and causes different types of dysarthria. Among other levels of speech production, the impairment affects articulatory mechanism, causing reduced range, force, timing and precision of articulatory movements. One of the most common consequences is the presence of consonantal distortions, which is also one of the main features that are assessed in clinical practice. The question however remains whether such distortion profile can be used reliably to differentiate between different types of dysarthria, and if so, how do different consonant distortion profiles correlate to other speech characteristics.

In order the answer the above questions, the objective of this study is two-fold: [START_REF] Darley | Differential diagnostic patterns of dysarthria[END_REF] to investigate the presence and type of consonantal distortions in the speech of speakers with Parkinson's disease (PD), amyotrophic lateral sclerosis (ALS) and cerebellar ataxia (CA), and also healthy control speakers (HS); [START_REF] Logemann | Frequency and cooccurrence of vocal tract dysfunctions in the speech of a large sample of Parkinson patients[END_REF] to investigate the relation between consonantal distortions, intelligibility and perceived articulation imprecision in the dysarthric groups. The three groups of dysarthric speakers, PD, ALS and CA are all associated with a different type of underlying neural cause and different type of dysarthria. PD is caused by basal ganglia damage, causing slowness in movement and movement initiation, rigidity, and is associated with hypokinetic dysarthria. ALS originates in upper and lower motor neuron damage, most typically manifests with muscle weakness and atrophy, and leads to a mixed type of dysarthria. CA results from cerebellar damage which disrupts coordination of muscular activity and causes ataxic dysarthria. Although these types of dysarthria differ in the exact speech profile, they all show articulatory difficulties with consonantal articulation. In their perceptual evaluation of altered speech dimensions [START_REF] Darley | Differential diagnostic patterns of dysarthria[END_REF], imprecision of consonants is ranked first for ALS and CA, and is ranked fourth (after prosodic features) for PD. Additionally, for the three dysarthria types, the perceptual scores on the feature 'imprecise consonants' are strongly correlated to intelligibility judgments (.91 for PD and ALS, .77 for CA) [START_REF] Darley | Differential diagnostic patterns of dysarthria[END_REF]. Several studies have described the types of consonant distortions, which can be observed in PD, ALS or CA, but little work has been done on French dysarthric speakers, and very few studies have compared the three dysarthria types on the same speech data. In PD, the described consonantal imprecisions usually include distortions based on the manner of articulation, with incomplete closure in stops, [START_REF] Logemann | Frequency and cooccurrence of vocal tract dysfunctions in the speech of a large sample of Parkinson patients[END_REF] [3] [4] [START_REF] Ackerman | Articulatory deficits in Parkinson's dysarthria: an acoustic analysis[END_REF] and on voice features, with voiceless stops being realized fully or partially voiced [START_REF] Kent | Prosodic disturbances and neurological lesion[END_REF] [START_REF] Weismar | Acoustic description of dysarthric speech: perceptual correlates and physiological inferences[END_REF]. Devoicing of voiced stops, fully or partially, is also noticed and constitutes one of the main feature of the 9 French speakers with PD of [START_REF] Duez | Acoustic analysis of occlusive weakening in Parkinsonian French speech[END_REF]. In ALS, imprecise consonants are hallmark feature, and also the one showing the greatest deterioration with the progression of ALS [START_REF] Kent | Speech deterioration in amyotrophic lateral sclerosis: a case study[END_REF]. The most common types of distortions reported in the literature include changes in voicing, particularly voicing of syllable initial consonants [START_REF] Kent | Impairment of speech intelligibility in men with amyotrophic lateral sclerosis[END_REF] [10], in manner of articulation, affecting stops, nasals and affricates, and in place of articulation [START_REF] Kent | Impairment of speech intelligibility in men with amyotrophic lateral sclerosis[END_REF]. Less detail about the types of consonantal imprecision is known for CA, but consonant distortions contribute to the slurred aspect of ataxic dysarthria, with stops often described as fricated and unreleased [START_REF] Kent | Cineradiographic assessment of articulatory mobility in the dysarthrias[END_REF]. In the following, we will investigate consonant distortions occurring in the reading of a text by a large cohort of French dysarthric speakers. Differences between ALS, PD and CA dysarthria profiles will be tested on the amount and types of consonantal distortions, and also according to their distribution. The nature of the target consonants (voicing, manner, place of articulation) and its positions in the word and sentence will then be examined. Finally, we will see how consonant distortions contribute to perceived alterations in the speech of the three dysarthria groups.

Methodology

Speakers

A total of 105 French speakers took part in this study, 79 with dysarthria due to PD, ALS or CA and 26 HS without any speech problems. All patients had their speech assessed and recorded at a neurological or voice and speech department of different hospitals [START_REF] Fougeron | Developing an acoustic-phonetic characterization of dysarthric speech in French[END_REF]. An earlier perceptual evaluation of intelligibility and articulatory imprecision performed by 22 listeners revealed that they differed on these two measures [START_REF] Audibert | Distorsions de l'espace vocalique: quelles mesures? Application à la dysarthrie[END_REF]. Details of speakers are presented in Table 1.

F <age> M <age> Intell. score Art. imp score N PD 8 <60-81> 23 <48-85> .6 <0-2.8> .7 <.1-2.7> 31 ALS 15 <50-89> 11 <44-74> 1.1 <.1-2.6> 1.5 <.2-2.9> 26 CA 9 <33-79> 13 <32-86> .9 <.2-1.7> 1.3 <.4-2.3> 22 HS 15 <33-76> 11 <32-62> 0 <0-.2> .1 <0-.5>

Speech material

All participants read the same short story of 169 words [START_REF] Fougeron | Developing an acoustic phonetic characterization of dysarthric speech in French[END_REF].

In this story, we have been able to select 48 words with consonants that could be included in the analysis: 25 /t/, five /d/, five /k/, four /g/ and nine /s/. All the consonants except /t/s are in word initial position. For the /t/s, there was enough exemplars in the text to manipulate the position of the consonant: 4 /t/s are at the beginning of a word which is initial in a sentence, probably preceded by a pause, and thus initial in an Intonational Phrase (IPi), 13 /t/s are word-initial but IP medial (Wi), and 8 /t/s are word-medial (Wm).

ALS

Data analysis

The entire set of recordings was transcribed and segmented by using an automatic speech alignment system [START_REF] Audibert | Evaluation d'un alignement automatique sur la parole dysarthrique[END_REF]. To avoid possible errors, the segmentation of the 4990 target consonants was nonetheless manually corrected. An evaluation of the realization of the selected consonants was done by an expert speech and language therapist (first author). Consonants were labeled as distorted or not based on visual inspection of their acoustic realization and perceptual assessment, and the types of distortion were categorized according to the following criteria: Distortions linked to manner of articulation: Incomplete closure (InClo): presence of noise or formants during the closure portion of the stops (i.e. spirantization and gliding) Nasalization: presence of a strong nasal component Stopping: presence of closure and/or burst in fricatives Distortions linked to laryngeal articulation (voice):

Voicing: partial or total voicing of voiceless consonants Devoicing: partial or total devoicing of voiced consonants.

Distortions linked to place of articulation:

Retraction: backing of the place of articulation Other types:

Omission of a segment Un-intelligible segment

Results and discussions

Distortions in the 4 groups over all consonants

Overall, few distortions are found in our data: only 8% of the 4990 consonants were categorized as distorted. The dysarthric patients produce almost all of these (with a rate of distortion of 10% when we exclude the control speakers), and only 4 cases are found in the control group. Within the dysarthric groups, the ALS produced the most distortions, with 18% of their consonants produced abnormally. CA and PD groups on the other hand presents quite a few cases, with distortions on only 6% and 7% of their consonants, respectively.

In addition to differences in the rate of distortions, the three dysarthric groups differ in the type of distortions. As shown in Table 3, the distortions in the ALS group most frequently concern the consonant manner of articulation (67%), followed by voice specification (37%). Distortions of manner and voice were reported previously as two of the most commonly observed speech characteristics in ALS [START_REF] Kent | Impairment of speech intelligibility in men with amyotrophic lateral sclerosis[END_REF]. Within the manner category, incomplete closure is the most common and nasalization very rare in our data. The latter is rather surprising since dysarthria in ALS is often characterized by a notable hypernasality [START_REF] Darley | Differential diagnostic patterns of dysarthria[END_REF]. This might suggest that the velopharyngeal impairment causing nasalization in ALS is more of a suprasegmental feature than a segmental one and it does not jeopardize the nasal/oral contrast of French stops. Nonetheless, comparison between groups on this feature shows that even if these cases of nasalization are rare, they occur in the ALS group only. Distortion patterns for the PD and CA groups show the reverse tendency than the one of the ALS, with more changes in voice features (54% of PD's distortions, 53% of CA's ones) than in manner (31% and 27% respectively). In both groups the change in voice occurs in both directions: voicing of voiceless consonants and devoicing of voiced consonants. However, the PD group differs from the CA group in the distribution of those: devoicing of voiced consonants is more frequent than voicing of voiceless consonants in the PD group, while the asymmetry is not so clear in the CA group. Within the few cases of distortion linked to manner of articulation in these two groups, the predominant distortion is incomplete closure, which was reported to be a typical characteristic of ataxic dysarthria and a frequent feature of hypokinetic dysarthria

[2] [3] [4] [5] [6].

Position and nature of the distorted consonants.

In this section, we will evaluate whether some consonants and some positions are more prone to distortions according to the type of dysarthria.

Position of the target consonant

The rate of distortions of the consonant /t/ is compared here for /t/s placed Wm, Wi, or IPi position (Table 4). In the ALS group, word initial and word medial /t/s are distorted at a similar rate (23% of the Wm /t/s are distorted, and 18% of the Wi). On the contrary, in the PD group word medial /t/s are more frequently distorted than word initial /t/s, even though the rate of distortion in both cases is quite small. Most of the distortions in both word initial and medial positions for the ALS group are incomplete closures; while the distortions in word medial position for the PD group are either incomplete closure or voicing. PD is characterized by difficulties in initiating movement and the results show that for these speakers it is more difficult to make the occlusion and/or to stop and restart voicing in the Wm intervocalic position than in initial position, as was shown by [START_REF] Fougeron | Developing an acoustic phonetic characterization of dysarthric speech in French[END_REF]. Another interesting point in this comparison is the behavior of the IP initial position for the ALS group. At the beginning of an Intonational phrase (thus preceded by a pause), /t/s are less distorted than in other position. While this trend needs to be confirmed in a more systematic investigation (with more IP-initial tokens), the fact that /t/s are more preserved in this prosodically important position (as shown for stress syllable by [START_REF] Ackerman | Articulatory deficits in Parkinson's dysarthria: an acoustic analysis[END_REF] for PD) could be exploited in rehabilitation.

ALS CA PD IPi 10% 1% 2% Wi 18% 3% 1% Wm 23% 4% 7%

Nature of the target consonant

In this section we test whether patients make more distortions on (a) voiced vs. voiceless consonants, on (b) front vs. back consonants, and on (c) stops vs. fricatives. (a) As illustrated in Figure 1, voiced and voiceless consonants are both distorted to a similar degree for the ALS group (18 and 19%, respectively). For the other two groups, there is a clear asymmetry: voiced consonants are more prone to distortions than voiceless ones. For the PD group, these results replicate the results of [START_REF] Audibert | Evaluation d'un alignement automatique sur la parole dysarthrique[END_REF] in French. Again, the differences in distortion type between the groups emerge: ALS patients do realize some voiced and voiceless stops with incomplete closure, while PD and CA patients tend to devoice voiced stops. (b) Distortions on alveolar vs. velar stops are illustrated on the left of Figure 2. Again, the ALS group does not show a preference depending on the place of articulation of the stops: 19% of the velar and 19% of the alveolar stops are distorted and most of them have incomplete closure. For the PD group there is a slight tendency for alveolar to be more resistant, but the small number of distortions for this group does not allow strong conclusions (as well as for the CA group).

(c) Distortions on fricatives (/s/) and stops (/t/) are illustrated on the right of Figure 2. In the ALS group, the distortions in the two categories differ more in types than in number: /s/ distortions involve the voicing of the voiceless fricative, while most distorted /t/s have an incomplete closure. The types of distortions on the fricatives seem also different in the groups: mostly voicing in ALS and more diverse in CA (with retraction, stopping, voicing). In summary, distortions in the ALS group are found to be more uniformly distributed over consonant types: be they voiced or unvoiced, front or back, distortions of stops result mostly from a failure to achieve the lingo-palatal occlusion. This failure can be explained by muscle weakness, which is stable across segments. Another characteristic of the ALS group is the voicing of voiceless consonants, notable especially for fricatives but also for voiceless stops. For the PD and CA groups, asymmetries in the distortion profile, such as a greater resistance of voiceless stops, are found. Small trends like the resistance of alveolar over velars for PD or stops over fricative in PD and CA, need to be further studied on a larger set of consonants.

Consonant distortions & perceived features

Table 5 shows the relationship between the rate of distortions observed on the consonants selected for this study and the perceptual evaluation made by 22 judges on 1 minute of speech extracted from text reading for each speaker, in terms of 'speech intelligibility' and global 'articulatory imprecision'.

The amount of consonant distortions is well correlated with the alteration scores for the ALS and PD groups. More distortions are found for the least intelligible patients and for patients perceived to have the most articulatory imprecisions. For these groups, articulatory imprecisions explain 60 (PD) to 70% (ALS) of the intelligibility scores. Interestingly, although only 18% of all analyzed consonants were distorted in the ALS group, this feature appears to be particularly salient. For the CA group on the contrary, the intelligibility of the speakers is not much affected by the rate of consonantal distortion, which was found to be quite low in this group. Other speech dimensions must be more prevalent in this group. The low correlation for the CA group and the high correlation for the PD group are in contradiction with [START_REF] Darley | Differential diagnostic patterns of dysarthria[END_REF]'s perceptual assessments, where consonant imprecision strongly contributed to intelligibility for ALS (.91) and CA (.77) while the relationship is not even mentioned for PD.

Conclusions

Although the total amount of consonants examined in the study was large (4990 consonants), the number of consonants per speaker was restricted (48 consonants) as was the number of consonant in each of the inspected categories. This data limitation is probably why the number of distortions was quite limited, with only 10% of the patient's consonants being distorted. Nonetheless, this study is the first examination of consonantal distortions on such a large cohort of French dysarthric speakers which has allowed us to obtain an overview of the main features of ALS, PD and CA profiles. It also gives us valuable information for future, more targeted, research which will include a larger set of consonants in specific categories (in IP initial position, voiced consonants, fricatives) and in which the distortion profiles will be quantified and the groups will be assessed on acoustic measurements.

Figure 1 :

 1 Figure 1: Distortion on voiced (+v) and voiceless (-v) consonants for the 3 groups. (InClo=incomplete closure; InClo+voice=incomplete closure and voicing; other=other distortions). % over the total number of voiced and voiceless consonants in each group.

Figure 2 :

 2 Figure 2: Distortion on velar (vel, /k,g/) vs. alveolar (alv, /t,d/) stops and on fricative (fric, /s/) vs. stop (/t/) for the 3 groups. Incomplete closure for stops and stopping for fricative are represented by 'InClo/stopg'. % over the total number of consonants category in each group.

26 Table 1 .

 261 Number

of speakers per group, by sex, with <age range> in years. Intelligibility (Intell.) and articulatory imprecision (Art. imp.) score (mean and <range>) are given. They were judged on a five-point scale, with 4 marking the poorest intelligibility and the greatest articulatory imprecision by 22 listeners.

Table 2 .

 2 Number of tokens included in the different analyses for each of the speaker groups. The last line gives the total number of consonant tokens analyzed. (*= only /t/ in Wiposition are included). of this consonant set, yielding to a total of 4990 tokens across all speakers, we grouped the consonants into different subsets to investigate the effect of a number of factors on consonant distortions. Table2shows the number of consonant tokens considered in each sub-analysis and the total number of consonants analyzed for each speaker group.

				CA	PD	HS
	position IPi	103	85	123	104
		Wi	331	278	399	338
		Wm	206	173	247	208
	voice	/d,g/	233	196	277	234
		/t,k/*	458	387	553	468
	PoA	/k,g/	231	197	278	234
		/t,d/*	460	386	552	468
	manner /t/*	233	192	276	234
		/s/	331	278	399	338
	Total = 4990	1233 1033 1476 1248
	Out

Table 3 .

 3 Type of distortions, as a % of all the observed distortions in each speaker group.

	Distortions affecting voice for the ALS group are
	represented mainly by the voicing of voiceless consonants,
	which is consistent with earlier descriptions [9] [10].
		ALS	CA	PD
		(N=219)	(N=59)	(N=99)
	Manner	67%	27%	31%
	InClo	60%	22%	28%
	Nasalization	5%	0%	0%
	Stopping	2%	5%	3%
	PoA	3%	12%	3%
	Retraction	3%	12%	3%
	Voice	37%	53%	54%
	Devoicing	2%	29%	37%
	Voicing	35%	24%	16%
	Other	5%	8%	13%
	Omission	3%	8%	12%
	Unintell	1%	0%	1%

Table 4 :

 4 Rate of distortions for IPi, Wi and Wm /t/s

Table 5 :

 5 Correlation coefficient and (r

	|r| &	Intell.	Art. Imp.
	(r 2 )
	ALS	.83 (.7)	.76 (.6)
	CA	.49 (.2)	.4 (.2)
	PD	.77 (.6)	.72 (.5)

2

) between distortion rate, intelligibility scores (Intell) and perceived articulatory imprecision (Art.Imp).

Acknowledgements

This work is supported by the ANR Typaloc (ANR-12-BSH2-0003) and the Labex EFL (ANR/CGI).


Hugo Gimbert
email: hugo.gimbert@laposte.net

Pure stationary optimal strategies in Markov decision processes

Markov decision processes (MDPs) are controllable discrete event systems with stochastic transitions. Performances of an MDP are evaluated by a payoff function. The controller of the MDP seeks to optimize those performances, using optimal strategies. There exists various ways of measuring performances, i.e. various classes of payoff functions. For example, average performances can be evaluated by a mean-payoff function, peak performances by a limsup payoff function, and the parity payoff function can be used to encode logical specifications. Surprisingly, all the MDPs equipped with mean, limsup or parity payoff functions share a common non-trivial property: they admit pure stationary optimal strategies. In this paper, we introduce the class of prefix-independent and submixing payoff functions, and we prove that any MDP equipped with such a payoff function admits pure stationary optimal strategies. This result unifies and simplifies several existing proofs. Moreover, it is a key tool for generating new examples of MDPs with pure stationary optimal strategies.

Introduction

Controller synthesis. One of the central questions in system theory is the controller synthesis problem : given a controllable system and a logical specification, is it possible to control the system so that its behaviour meets the specification?

In the most classical framework, the transitions of the system are not stochastic and the specification is given in LTL or CTL*. In that case, the controller synthesis problem reduces to computing a winning strategy in a parity game on graphs [START_REF] Thomas | On the synthesis of strategies in infinite games[END_REF].

There are two natural directions to extend this framework. First direction consists in considering systems with stochastic transitions [dA97]. In that case the controller wishes to maximize the probability that the specification holds. The corresponding problem is the computation of an optimal strategy in a Markov decision process with parity condition [START_REF] Courcoubetis | Markov decision processes and regular events[END_REF].

Second direction to extend the classical framework of controller synthesis consists in considering quantitative specifications [START_REF] Alfaro | How to specify and verify the long-run average behavior of probabilistic systems[END_REF][START_REF] Chatterjee | Markov decision processes with multiple objectives[END_REF]. Whereas a logical specification specifies good and bad behaviours of the system, a quantitative specification evaluates performances of the system in a more subtle way. These performances are evaluated by a payoff function, which associates a real value with each run of the system. Synthesis of a controller which maximizes performances of the system corresponds to the computation of an optimal strategy in a payoff game on graphs.

For example, consider a logical specification that specifies that the system should not reach an error state. Then using a payoff function, we can refine this logical specification. For example, we can specify that the number of visits to the error states is as small as possible, or also that the average time between two occurrences of the error state is as long as possible. Observe that logical specifications are a special case of quantitative specifications, where the payoff function takes only two possible values, 1 or 0, depending whether or not the behaviour of the system meets the specification.

In the most general case, the transitions of the system are stochastic and the specification is quantitative. In that case, the controller wishes to maximize the expected value of the payoff function, and the controller synthesis problem consists in computing an optimal strategy in a Markov decision process.

Positional payoff functions. Various payoff functions have been introduced and studied, in the framework of Markov decision processes but also in the broader framework of two player stochastic games. For example, the discounted payoff [START_REF] Shapley | Stochastic games[END_REF][START_REF] Chatterjee | Markov decision processes with multiple objectives[END_REF] and the total payoff [START_REF] Thuijsman | The Bad Match, a total reward stochastic game[END_REF] are used to evaluate shortterm performances. Long-term performances can be computed using the meanpayoff [START_REF] Gilette | Stochastic games with zero stop probabilities[END_REF][START_REF] Alfaro | How to specify and verify the long-run average behavior of probabilistic systems[END_REF] or the limsup payoff [START_REF] Maitra | Discrete gambling and stochastic games[END_REF] that evaluate respectively average performances and peak performances. These functions are central tools in economic modelization. In computer science, the most popular payoff function is the parity payoff function, which is used to encode logical properties.

Very surprisingly, the discounted, total, mean, limsup and parity payoff functions share a common non-trivial property. Indeed, in any Markov decision process equipped with one of those functions there exists optimal strategies of a very simple kind : they are at the same time pure and stationary. A strategy is pure when the controller plays in a deterministic way and it is stationary when choices of the controller depend only on the current state, and not on the full history of the run. For the sake of concision, pure stationary strategies are called positional strategies, and we say that a payoff function itself is positional if in any Markov decision process equipped with this function, there exists an optimal strategy which is positional.

The existence of positional optimal strategies has algorithmic interest. In fact, this property is the key for designing several polynomial time algorithms that compute values and optimal strategies in MDPs [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF][START_REF] Filar | Competitive Markov Decision Processes[END_REF].

Recently, there has been growing research activity about the existence of positional optimal strategies in non-stochastic two-player games with infinitely many states [START_REF] Grädel | Positional determinacy of infinite games[END_REF][START_REF] Colcombet | On the positional determinacy of edge-labeled games[END_REF][START_REF] Kopczyński | Half-positional determinacy of infinite games[END_REF] or finitely many states [START_REF] Björklund | Memoryless determinacy of parity and mean payoff games: a simple proof[END_REF][START_REF] Gimbert | Games where you can play optimally without any memory[END_REF]. The framework of this paper is different, since it deals with finite MDPs, i.e. oneplayer stochastic games with finitely many states and actions.

Our results. In this paper, we address the problem of finding a common property between the classical payoff functions introduced above, which explains why they are all positional. We give the following partial answer to that question.

First, we introduce the class of submixing payoff functions, and we prove that a payoff function which is submixing and prefix-independent is also positional (cf. Theorem 1).

This result partially solves our problem, since the parity, limsup and meanpayoff functions are prefix-independent and submixing (cf. Proposition 1).

Our result has several interesting consequences. First, it unifies and shortens disparate proofs of positionality for the parity [START_REF] Courcoubetis | Markov decision processes and regular events[END_REF], limsup [START_REF] Maitra | Discrete gambling and stochastic games[END_REF] and mean [START_REF] Bierth | An expected average reward criterion[END_REF][START_REF] Neyman | Stochastic games and applications[END_REF] payoff function (section 4). Second, it allows us to generate a bunch of new examples of positional payoff functions (section 5).

Plan. This paper is organized as follows. In section 2, we introduce notions of controllable Markov chain, payoff function, Markov decision process and optimal strategy. In section 3, we state our main result : prefix-independent and submixing payoff functions are positional (cf. Theorem 1). In the same section, we give elements of proof of Theorem 1. In section 4, we show that our main result unifies various disparate proofs of positionality. In section 5, we present new examples of positional payoff functions.

Markov decision processes

Let S be a finite set. The set of finite (resp. infinite) sequences on S is denoted S * (resp. S ω ). A probability distribution on S is a function δ : S → R such that ∀s ∈ S, 0 ≤ δ(s) ≤ 1 and s∈S δ(s) = 1. The set of probability distributions on S is denoted D(S).

Controllable Markov chains and strategies

Definition 1. A controllable Markov chain A = (S, A, (A(s)) s∈S , p) is composed of:

a finite set of states S and a finite set of actions A, for each state s ∈ S, a set A(s) ⊆ A of actions available in s, transition probabilities p : S × A → D(S) .

When the current state of the chain is s, then the controller chooses an available action a ∈ A(s), and the new state is t with probability p(t|s, a).

A triple (s, a, t) ∈ S × A × S such that a ∈ A(s) and p(t|s, a) > 0 is called a transition.

A history in A is an infinite sequence h = s 0 a 1 s 1 • • • ∈ S(AS) ω such that for each n, (s n , a n+1 , s n+1 ) is a transition. State s 0 is called the source of h. The set of histories with source s is denoted P ω A,s . A finite history in A is a finite sequence h = s 0 a 1 • • • a n-1 s n ∈ S(AS) * such that for each n, (s n , a n+1 , s n+1 ) is a transition. s 0 is the source of h and s n its target. The set of finite histories (resp. of finite histories with source s) is denoted P * A (resp. P * A,s ). A strategy in A is a function σ : P * A → D(A) such that for any finite history h ∈ P * A with target t ∈ S, the distribution σ(h) puts non-zero probabilities only on actions that are available in t, i.e. (σ(h

)(a) > 0) =⇒ (a ∈ A(t)). The set of strategies in A is denoted Σ A .
As explained in the introduction of this paper, certain types of strategies are of particular interest, such as pure and stationary strategies. A strategy is pure when the controller plays in a determnistic way, i.e. without using any dice, and it is stationary when the controller plays without using any memory, i.e. his choices only depend on the current state of the MDP, and not on the entire history of the play. Formally : Definition 2. A strategy σ ∈ Σ A is said to be:

• pure if ∀h ∈ P * A , (σ(h)(a) > 0) =⇒ (σ(h)(a) = 1) , • stationary if ∀h ∈ P * A with target t, σ(h) = σ(t) , • positional if it is pure and stationary.
Since the definition of a stationary strategy may be confusing, let us remark that t ∈ S denotes at the same time the target state of the finite history h ∈ P * A and also the finite history t ∈ P * A,t of length 1.

Probability distribution induced by a strategy

Suppose that the controller uses some strategy σ and that transitions between states occur according to the transition probabilities specified by p(•|•, •). Then intuitively the finite history s 0 a 1 • • • a n s n occurs with probability

σ(s 0 )(a 1 ) • p(s 1 |s 0 , a 1 ) • • • σ(s 0 • • • s n-1 )(a n ) • p(s n |s n-1 , a n ) .
In fact, it is also possible to measure probabilities of infinite histories. For this purpose, we equip P ω A,s with a σ-field and a probability measure. For any finite history h ∈ P * A,s , and action a, we define the sets of infinite plays with prefix h or ha:

A theorem of Ionescu Tulcea (cf. [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF]) implies that there exists a unique probability measure P σ s on P ω A,s such that for any finite history h ∈ P * A,s with target t, and for every a ∈ A(t),

P σ s (ha | h) = σ(h)(a) , (1)
P σ s (har | ha) = p(r|t, a) . (2)
We will use the following random variables. For n ∈ N, and t ∈ S,

S n (s 0 a 1 s 1 • • • ) = s n the (n + 1)-th state, A n (s 0 a 1 s 1 • • • ) = a n the n-th action, H n = S 0 A 1 • • • A n S n
the finite history of the first n stages, N t = |{n > 0 : S n = t}| ∈ N ∪ {+∞} the number of visits to state t.

(3)

Payoff functions

After an infinite history of the controllable Markov chain, the controller gets some payoff. There are various ways for computing this payoff.

Mean payoff. The mean-payoff function has been introduced by Gilette [START_REF] Gilette | Stochastic games with zero stop probabilities[END_REF] and is used to evaluate average performance. Each transition (s, a, t) of the controllable Markov chain is labeled with a daily payoff r(s, a, t) ∈ R. An history s 0 a 1 s 1 • • • gives rise to a sequence r 0 r 1 • • • of daily payoffs, where r n = r(s n , a n+1 , s n+1 ). The controller receives the following payoff:

φ mean (r 0 r 1 • • • ) = lim sup n∈N 1 n + 1 n i=0 r i . (4)
Discounted payoff. The discounted payoff has been introduced by Shapley [START_REF] Shapley | Stochastic games[END_REF] and is used to evaluate short-term performance. Each transition (s, a, t) is labeled not only with a daily payoff r(s, a, t) ∈ R but also with a discount factor 0 ≤ λ(s, a, t) < 1. The payoff associated with a sequence (r 0 , λ 0 )(r 1 , λ 1 )

• • • ∈ (R × [0, 1[) ω
of daily payoffs and discount factors is:

φ λ disc ((r 0 , λ 0 )(r 1 , λ 1 ) • • • ) = r 0 + λ 0 r 1 + λ 0 λ 1 r 2 + • • • . (5)
Parity payoff. The parity payoff function is used to encode temporal logic properties [START_REF] Grdel | Automata, Logics and Infinite Games[END_REF]. Each transition (s, a, t) is labeled with some priority c(s, a, t) ∈ {0, . . . , d}. The controller receives payoff 1 if the highest priority seen infinitely often is odd, and 0 otherwise. For

c 0 c 1 • • • ∈ {0, . . . , d} ω , φ par (c 0 c 1 • • • ) = 0 if lim sup n c n is even, 1 otherwise. ( 6
)
General payoffs. In the sequel, we will give other examples of payoff functions.

Observe that in the examples we gave above, the transitions were labeled with various kinds of data: real numbers for the mean-payoff, couple of real numbers for the discounted payoff and integers for the parity payoff. We wish to treat those examples in a unified framework. For this reason, we consider now that each controllable Markov chain A comes together with a finite set of colours C and a mapping col : S × A × S → C, which colors transitions.

In the case of the mean payoff, transitions are coloured with real numbers hence C ⊆ R, whereas in the case of the discounted payoff colours are couples C ⊆ R × [0, 1[ and for the parity game colours are integers C = {0, . . . , d}.

For an history (resp. a finite history) h = s 0 a 1 s 1 • • • , the colour of the history h is the infinite (resp. finite) sequence of colours col(h) = col(s 0 , a 1 , s 1 ) col(s 1 , a 2 , s 2 ) • • • . Definition 3. Let C be a finite set. A payoff function on C is a measurable1 and bounded function φ : C ω → R .

After an history h, the controller receives payoff φ(col(h)) .

Values and optimal strategies in Markov decision processes

Definition 4. A Markov decision process is a couple (A, φ), where A is a controllable Markov chain coloured by a set C and φ is a payoff function on C .

Let us fix a Markov decision process M = (A, φ). After history h, the controller receives payoff φ(col(h)) ∈ R. We extend the definition domain of φ to P ω A,s : ∀h ∈ P ω A,s , φ(h) = φ(col(h)) . The expected value of φ under the probability P σ s is called the expected payoff of the controller and is denoted E σ s [φ]. It is well-defined because φ is measurable and bounded. The value of a state s is the maximal expected payoff that the controller can get : val(M)(s) = sup

σ∈Σ A E σ s [φ] .
A strategy σ is said to be optimal in M if for any state s ∈ S,

E σ s [φ] = val(M)(s) .

Optimal positional control

We are interested in those payoff functions that ensure the existence of positional optimal strategies. It motivates the following definition.

Definition 5. Let C be a finite set of colors and φ a payoff function on C ω . Then φ is said to be positional if for any controllable Markov chain A coloured by C, there exists a positional optimal strategy in the MDP (A, φ).

Our main result concerns the class of payoff functions with the following properties. Definition 6. Let φ be a payoff function on C ω . We say that φ is prefixindependent if for any finite word u ∈ C * and infinite word v ∈ C ω , φ(uv) = φ(v). See [START_REF] Chatterjee | Concurrent games with tail objectives[END_REF] for interesting results about concurrent stochastic games with prefix-independent payoff functions. We say that φ is submixing if for any sequence of finite non-empty words u

0 , v 0 , u 1 , v 1 , . . . ∈ C * , φ(u 0 v 0 u 1 v 1 • • • ) ≤ max { φ(u 0 u 1 • • • ) , φ(v 0 v 1 • • • ) } .
The notion of prefix-independence is classical. The submixing property is close to the notions of fairly-mixing payoff functions introduced in [GZ04] and of concave winning conditions introduced in [START_REF] Kopczyński | Half-positional determinacy of infinite games[END_REF]. We are now ready to state our main result.

Theorem 1. Any prefix-independent and submixing payoff function is positional.

The proof of this theorem is based on the 0-1 law and an induction on the number of actions. Due to space restrictions, we do not give details here, a full proof can be found in [Gim].

Unification of classical results

We now show how Theorem 1 unifies proofs of positionality of the parity [START_REF] Courcoubetis | Markov decision processes and regular events[END_REF], the limsup and liminf [START_REF] Maitra | Discrete gambling and stochastic games[END_REF] and the mean-payoff [START_REF] Bierth | An expected average reward criterion[END_REF][START_REF] Neyman | Stochastic games and applications[END_REF] functions.

The parity, mean, limsup and liminf payoff functions are denoted respectively φ par , φ mean , φ lsup and φ linf . Both φ par and φ mean have already been defined in subsection 2.3. φ lsup and φ linf are defined as follows. Let C ⊆ R be a finite set of real numbers, and

c 0 c 1 • • • ∈ C ω . Then φ lsup (c 0 c 1 • • • ) = lim sup n c n φ linf (c 0 c 1 • • • ) = lim inf n c n .
The four payoff functions φ par , φ mean , φ lsup and φ linf are very different. Indeed, φ lsup measures the peak performances of the system, φ linf the worst performances, and φ mean the average performances. The function φ par is used to encode logical specifications, expressed in MSO or LTL for example [START_REF] Grdel | Automata, Logics and Infinite Games[END_REF].

Proposition 1. The payoff functions φ lsup , φ linf , φ par and φ mean are submixing.

Proof. Let C ⊆ R be a finite set of real numbers and u 0 , v 0 , u 1 , v 1 , . . . ∈ C * be a sequence of finite non-empty words on

C. Define u = u 0 u 1 • • • ∈ C ω , v = v 0 v 1 • • • ∈ C ω and w = u 0 v 0 u 1 v 1 • • • ∈ C ω .
The following elementary fact immediately implies that φ lsup is submixing.

φ lsup (w) = max{φ lsup (u), φ lsup (v)} . (7)
In a similar way, φ linf is submixing since

φ linf (w) = min{φ linf (u), φ linf (v)} . (8)
Now suppose that C = {0, . . . , d} is a finite set of integers and consider function φ par . Remember that φ par (w) equals 1 if φ lsup (w) is odd and 0 if φ lsup (w) is even. Then using (7) we get that if φ par (w) has value 1 then it is the case of either φ par (u) or φ par (v). It proves that φ par is also submixing. Now let us consider function φ mean . A proof that φ mean is submixing already appeared in [START_REF] Gimbert | When can you play positionally?[END_REF], and we reproduce it here, updating the notations. Again C ⊆ R is a finite set of real numbers. Let c 0 , c 1 , . . . ∈ C be the sequence of letters of C such that w = (c i ) i∈N . Since word w is a shuffle of words u and v, there exists a partition (I 0 , I 1 ) of

N such that u = (c i ) i∈I0 and v = (c i ) i∈I1 . For any n ∈ N, let I n 0 = I 0 ∩ {0, . . . , n} and I n 1 = I 1 ∩ {0, . . . , n}. Then for n ∈ N, 1 n + 1 n i=0 c i = |I n 0 | n + 1   1 |I n 0 | i∈I n 0 c i   + |I n 1 | n + 1   1 |I n 1 | i∈I n 1 c i   ≤ max    1 |I n 0 | i∈I n 0 c i , 1 |I n 1 | i∈I n 1 c i    .
The inequality holds since

|I n 0 | n+1 + |I n 1 | n+1 = 1.
Taking the superior limit of this inequality, we obtain φ mean (w) ≤ max{φ mean (u), φ mean (v)}. It proves that φ mean is submixing.

Since φ lsup , φ linf , φ par and φ mean are clearly prefix-independent, Proposition 1 and Theorem 1 imply that those four payoff functions are positional. Hence, we unify and simplify existing proofs of [START_REF] Courcoubetis | Markov decision processes and regular events[END_REF][START_REF] Maitra | Discrete gambling and stochastic games[END_REF] and [START_REF] Bierth | An expected average reward criterion[END_REF][START_REF] Neyman | Stochastic games and applications[END_REF]. In particular, we use only elementary tools for proving the positionality of the mean-payoff function, whereas [START_REF] Bierth | An expected average reward criterion[END_REF] uses martingale theory and relies on other papers, and [START_REF] Neyman | Stochastic games and applications[END_REF] uses a reduction to discounted games, as well as analytical tools.

Generating new examples of positional payoff functions.

We present three different techniques for generating new examples of positional payoff functions.

Mixing with the liminf payoff

In last section, we saw that peak performances of a system can be evaluated using the limsup payoff, whereas its worst performances are computed using the liminf payoff. The compromise payoff function is used when the controller wants to achieve a trade-off between good peak performances and not too bad worst performances. Following this idea, we introduced in [GZ04] the following payoff function. We fix a factor λ ∈ [0, 1], a finite set C ⊆ R and for u ∈ C ω , we define

φ λ comp (u) = λ • φ lsup (u) + (1 -λ) • φ linf (u) .
The fact that φ λ comp is submixing is a corollary of the following proposition.

Proposition 2. Let C ⊆ R, 0 ≤ λ ≤ 1 and φ be a payoff function on C. Suppose that φ is prefix-independent and submixing. Then the payoff function

λ • φ + (1 -λ) • φ linf (9)
is also prefix-independent and submixing.

The proof is straightforward, using (8) above. According to Theorem 1 and Proposition 1, any payoff function defined by equation ( 9), where φ is either φ mean , φ par or φ lsup , is positional. Hence, this technique enable us to generate new examples of positional payoffs.

The approximation operator

Consider an increasing function f : R → R and a payoff function φ : C ω → R.

Then their composition f • φ is also a payoff function and moreover, if φ is positional then f • φ also is. Indeed, a strategy optimal for an MDP (A, φ) is also optimal for the MDP (A, f • φ).

An example is the threshold function f = 1 ≥0 which associates 0 with strictly negative real numbers and 1 with positive number. Then f • φ indicates whether the performance evaluated by φ reaches the critical value of 0.

Hence any increasing function f : R → R defines a unary operator on the family of payoff functions, and this operator stabilizes the family of positional payoff functions. In fact, it is straightforward to check that it also stabilizes the sub-family of prefix-independent and submixing payoff functions.

The hierarchical product

Now we define a binary operator between payoff functions, which also stabilizes the family of prefix-independent and submixing payoff functions. We call this operator the hierarchical product.

Let φ 0 , φ 1 be two payoff functions on sets of colours C 0 and C 1 respectively. We do not require C 0 and C 1 to be identical nor disjoints.

The hierarchical product φ 0 φ 1 of φ 0 and φ 1 is a payoff function on the set of colours C 0 ∪ C 1 and is defined as follows. Let u = c 0 c 1 • • • ∈ (C 0 ∪ C 1 ) ω and u 0 and u 1 the two projections of u on C 0 and C 1 respectively. Then

(φ 0 φ 1 )(u) = φ 0 (u 0 ) if u 0 is infinite, φ 1 (u 1 ) otherwise.
This definition makes sense : although each word u 0 and u 1 can be either finite or infinite, at least one of them must be infinite.

Let us give examples of use of hierarchical product. For e ∈ N, let 0 e and 1 e be the payoff functions defined on the one-letter alphabet {e} and constant equal to 0 and 1 respectively. Let d be an odd number, and φ par be the parity payoff function on {0, . . . , d}. Then

φ par = 1 d 0 d-1 • • • 1 1 0 0 .
Another example of hierarchical product was given in [START_REF] Gimbert | Games where you can play optimally without any memory[END_REF][START_REF] Gimbert | Deterministic priority mean-payoff games as limits of discounted games[END_REF], where we defined and establish properties about the priority mean-payoff function. This payoff function is in fact the hierarchical product of d mean-payoff functions. Remark that another way of fusionning the parity payoff and the mean-payoff functions has been presented in [START_REF] Chatterjee | Mean-payoff parity games[END_REF], and the resulting payoff function is not positional. In contrary, it turns out that the priority mean-payoff function is positional, as a corollary of Theorem 1, and the following proposition, whose proof is easy. Proposition 3. Let φ 0 and φ 1 be two payoff functions. If φ 0 and φ 1 are prefixindependent and submixing, then φ 0 φ 1 also is.

Towards a quantitative specification language?

In the previous section, we defined two unary operators and one binary operator over payoff functions. Moreover, we proved that the class of prefix-independent and submixing payoff functions is stable under these operators. As a consequence, if we start with the constant, the limsup, the liminf and the mean payoff functions, and we apply recursively our three operators, we get a huge family of sub-mixinf and prefix-independent payoff functions. According to Theorem 1, all those functions are positional.

We hope that this result is a first step towards a rich quantitative specification language. For example, using the hierarchical product, we can express properties such as: "Minimize the frequency of visits to error states. In the case where error states are visited only finitely often, maximize the peak performances." The positionality of those payoff functions gives hope that the corresponding controller synthesis problems are solvable in polynomial time.

In that paper, we have introduced the class of prefix-independent and submixing payoff functions, and we proved that they are positional. Moreover, we have defined three operators on payoff functions, that can be used to generate new examples of MDPs with positional optimal strategies.

There are different natural directions to continue this work. First, most of the results of this paper can be extended to the broader framework of two-player zero-sum stochastic games with full information. This is ongoing work with Wies law Zielonka, to be published soon.

Second, the results of the last section give rise to natural algorithmic questions. For MDPs equipped with mean, limsup, liminf, parity or discounted payoff functions, the existence of optimal positional strategies is the key for designing algorithms that compute values and optimal strategies in polynomial time [START_REF] Filar | Competitive Markov Decision Processes[END_REF]. For examples generated with the mixing operator and the hierarchical product, it seems that values and optimal strategies are computable in exponential time, but we do not know the exact complexity. Also it is not clear how to obtain efficient algorithms when payoff functions are defined using approximation operators.

To conclude, let us formulate the following conjecture about positional payoff functions. "Any payoff function which is positional for the class of non-stochastic one-player games is positional for the class of Markov decision processes".

Appendix A Proof of Theorem 1

This appendix gives a proof of Theorem 1 and is organized as follows. In the first subsection, we establish two useful elementary lemmas. Then in subsection A.2, we prove Theorem 2, which is Theorem 1 for the special case of Markov chains. In subsection A.3, we establish that the expected value of histories that never reach their initial state is no more than the value of that state. Then in subsection A.4, we introduce the notion of a split of an arena. Basic properties of the split operation are described in Proposition 4, and Theorem 4 shows how one can simulate a strategy in an arena with strategies in the split of that arena. Theorem 5 and 6 are the key results to show that value of a state in an arena is no more than its maximal value in splits of the arena, i.e. Corollary 1. End of proof of Theorem 1 is given in subsection A.7.

A.1 Preliminary lemmas

In the proof of Theorem 1, we will often use the following lemmas. First one is called the shifting lemma.

Lemma 1 (shifting lemma). Let A be a controllable Markov chain, s, t ∈ S some states, h ∈ P * A,s a finite history with source s and target t, σ a strategy in A, and X a real valued random variable such that sup X

= +∞ or inf X = -∞. Then E σ s [X | h] = E σ[h] t [ X[h] ], (10)
where σ[h] is the strategy defined as

σ[h](s 0 a 1 • • • s n ) = σ(ha 1 • • • s n ) and X[h] is the random variable defined by X[h](s 0 a 1 s 1 • • • ) = X(ha 1 s 1 • • • ).
The proof is elementary, we give it for the sake of completness.

Proof. First observe that since sup X = +∞ or inf X = -∞, the values of (10) are well-defined. Let l ∈ P * A,s and X l be the indicator function of the set O l . We are going to show that (10) holds when X = X l .

First suppose that l is a prefix of h, then E σ s [X l | h] = 1 and X l [h] = 1 hence (10) holds in that case. Now suppose that h is a prefix of l, then there exists

a 1 s 1 a 2 • • • s n ∈ (AS) * such that l = ha 1 s 1 a 2 • • • s n .
Then, using the definition of P σ s , i.e. equations (1) and (2), we get:

E σ s [X l | h] = P σ s (l | h) = σ(h)(a 1 ) • p(s 1 |t, a 1 ) • • • σ(ha 1 s 1 • • • s n-1 )(a n ) • p(s n |s n-1 , a n ) = P σ[h] t (ta 1 s 1 • • • a n s n ) = E σ[h] t [X l [h]] .
Hence (10) holds in that case. Now suppose that h is not a prefix of l, and l is not a prefix of h. Then the events O l and O h are disjoints, and X l [h] is uniformly equals to 0. Hence we get

E σ s [X l | h] = P σ s (O l | O h ) = 0 = E σ[h] t [ X l [h] ],
and again (10) holds in that last case.

Hence, for any l ∈ P * A,s , equation (10) holds for X = X l = 1 O l . Since the class of sets O h generates the σ-field on P ω A,s , we get that (10) holds for any random variable.

The following lemma will also be very useful.

Lemma 2. Let A be a controllable Markov chain, s a state of A, E ⊆ P ω A,s an event and σ and τ two strategies. Let us suppose that σ and τ coincide on E, in the sense that for all finite history ∈ P * A,s , (h is a prefix of an history in E) =⇒ (σ(h) = τ (h)) .

Then,

P σ s ( | E) = P τ s ( | E) . (11)
Again the proof is elementary and we give it for the sake of completness.

Proof. We start with proving:

P σ s (E) = P τ s (E) (12)
Let h ∈ P * A,s and E = O h . Then equality ( 12) is a direct consequence of the definition of P σ s and P τ s . Since the sets O h generate the σ-field over P ω A,s , equation (12) is true for any event E.

Let F be an event. Then σ and τ coincide on E ∩ F . Applying (12) with E ∩ F , we get P σ s (E ∩ F ) = P τ s (E∩ F ). Together with (12), we get (11).

A.2 About Markov chains

Second step consists in proving theorem 2, which establishes a property of Markov chains. A controllable Markov chain A is a Markov chain when ∀s ∈ S, |A(s)| = 1. In that case, there is a unique strategy σ in A. The measure of probability on P ω A,s associated with that unique strategy is denoted P s instead of P σ s . Theorem 2. Let M = (A, φ) be MDP. Suppose that A is a Markov chain and φ is prefix-independent. Let s be a recurrent state of A. Then

P s (φ > val(M)(s)) = 0 . ( 13
)
Proof. Let E be the event:

E = {φ > val(G, s)}.
We first prove that E is independent of O h , for any h ∈ P * A,s .

Let t ∈ S be a state and h ∈ P * A,s a finite history with target t. The case where P s (h) = 0 is clear hence we suppose that P s (h) > 0. Since φ is prefixindependent, 1 E [h] = 1 E . Using the shifting lemma 1 we obtain :

P s (E | h) = P t (E). ( 14
)
Let C t,s be the set of finite history with source t, target s, and that reaches s only once. Since P s (h) > 0, states s and t are in the same recurrence class, hence

1 = P t ({∃n, S n = s}) = l∈Cs,t P t (l) . ( 15
) Hence P t (E) = l∈Cs,t P t (l) • P t (E | l) = l∈Cs,t P t (l) • P s (E) = P s (E) , (16)
where the first equality follows from (15), the second is similar to (14) and the third from (15) again. Together with (14), we obtain:

P s (E | h) = P s (E) . (17)
Hence we have proven that for any h ∈ P * A,s , event E is independent of O h . But E is member of the σ-field generated by the sets O h . It implies that E is independent of itself, hence

P s (E) = P s (E ∩ E) = P s (E) 2 ,
which proves that P s (E) is either 0 or 12 . Suppose for a moment that P s (E) = 1 and find a contradiction. Then P s (φ > val(G, s)) = 1, hence E s [φ] > val(G, s), which contradicts the definition of val(G, s).

We deduce that P s (E) = 0 whch gives (13) and achieves the proof of this theorem.

A.3 Histories that never reach again their initial state

Consider the definition of N s given by equation (3). The event {N s = 0} means that the history never reaches again s after the first stage. The following theorem states a property about the expected value of those histories.

Theorem 3. Let M = (A, φ) be a Markov decision process, s a state of A and σ a strategy. Suppose that φ is prefix-independent. Then

E σ s [φ | N s = 0] ≤ val(M)(s). ( 18
)
Proof. Let f : P * A,s → P * A,s be the mapping that "forget cycles on s", defined by:

f (s 0 a 1 • • • s n ) = s k a k+1 • • • s n , where k = max{i | s i = s} .
Let τ the strategy that consists in forgetting the cycles on s, and apply σ. Formally τ is defined by τ (h) = σ(f (h)). We are going to show that:

E σ s [φ | N s = 0] = E τ s [φ], (19)
which implies immediatly (18), by definition of the value of a state. Even if (19) may seem obvious, we proof it for the sake of completness. We suppose that

e = P σ s (N s = 0) > 0 , (20)
otherwise ( 18) is not defined, and there is nothing to prove. First we show that

P τ s (N s = ∞) = 0. ( 21
)
Let K ⊆ P * A,s the set of simple cycles on s, i.e.:

K = {s 0 a 1 • • • s n ∈ P * A,s | s 0 = s n = s and for 0 < k < n, s k = s}.
Then for any n ∈ N,

P τ s (N s ≥ n + 1) = h∈K P τ s (N s ≥ n + 1 | h) • P τ s (h) = h∈K P τ [h] s (N s ≥ n) • P τ s (h) = h∈K P τ s (N s ≥ n) • P τ s (h) = P τ s (N s ≥ n) • P τ s (N s > 0) = P τ s (N s ≥ n) • (1 -e)
The first equality is a conditionning on the date of the first return on s, for the second we use the shifting lemma. The third equality holds since by definition of τ and K, ∀h ∈ K, τ [h] = τ . The fourth equality is by definition of K, and the fifth by definition (20) of e.

Taking the limit of this equation when n tends to ∞, we get P τ s (N s = +∞) = P τ s (N s = +∞) • (1 -e) . Using (20), we obtain (21).

We can now achieve the proof. Define last s , the last date where history reaches s:

last s = sup{n ∈ N, S n = s}.
Then {N s = ∞} = {last s = ∞}, hence (21) implies P τ s (last s < ∞) = 1, and

E τ s [φ] = n∈N E τ s [φ | last s = n] • P τ s (last s = n). = n∈N h∈P * A,s E τ s [φ | last s = n, H n = h] • P τ s (last s = n, H n = h). ( 22
)
Let n ∈ N and h ∈ P * A,s such that P τ,s (last s = n, H n = h) > 0. Then

E τ s [φ | last s = n, H n = h] = E τ [h] s [φ | last s = 0] = E τ s [φ | last s = 0] = E σ s [φ | last s = 0]. ( 23
)
The first equality is obtained using the shifting lemma and the prefix-independence of φ. The second equality comes from the fact that since P τ,s (last s = N, H N = h) > 0, h is s and by definition of τ , τ [h] = τ . The third equality comes from the fact that τ and σ coincide on the set {last s = 0}, and applying the lemma 2. Eventually, ( 23) and ( 22) give

E τ s [φ] = E σ s [φ| last s = 0]. Since {N s = 0} = {last s = 0}, we get E τ s [φ] = E σ s [φ|N s = 0] . ( 24
)
By definition of the value of a state, val(G)(s) ≥ E τ s [φ], which together with (24) gives ( 18) and achieves the proof of this theorem.

A.4 Submixing payoff functions and split of an MDP

The proof of 1 is by induction on the number of actions in the MDP. For that purpose, we introduce the notion of split of an MDP, and associated projections. Definition 7. Let A be a controllable Markov chain and s ∈ S a state such that |A(s)| > 1. Let (A 0 (s), A 1 (s)) a partition of A(s) in two non-empty sets.

Let A 0 = (S, A 0 , (A 0 (s)) s∈S , p, col) be the controllable Markov chain obtained from A = (S, A, (A(s)) s∈S , p, col) in the following way. We restrict the set of actions available in s to A 0 (s). For t = s, nothing changes, i.e. A 0 (t) = A(t). The transition probabilities p and the coulouring mapping col do not change. Let A 1 be the controllable Markov chain obtained symetrically, restricting the set of actions available in s to A 1 (s).

Then (A 0 , A 1 ) is called a split of A on s. For MDPs M = (A, φ), M 0 = (A 0 , φ) and M 1 = (A 1 , φ), we also say that (M 0 , M 1 ) is a split of M on s. Now consider a split (A 0 , A 1 ) of a controllable Markov chain A on a state s. There exists a natural projection (π 0 , π 1 ) from finite histories h ∈ P * A,s to couples of finite histories (h 0 , h 1 ) ∈ P * A0,s × P * A1,s . Let us decribe informally this projection.

Consider a finite history h ∈ P * A,s . Then h factorizes in a unique way in a sequence

h = h 0 h 1 • • • h k h k+1 , (25)
such that

• for 0 ≤ i ≤ k, h i is a simple cycle on s,
• h k+1 is a finite history with source s, which does not reach s again.

For any 0 ≤ i ≤ k + 1, the source of h i is s hence the first action a i in h i is avaialable in s, i.e. a i ∈ A(s). Since (A 0 (s), A 1 (s)) is a partition of A(s), we have either a i ∈ A 0 (s) or a i ∈ A 1 (s). Then π 0 (h) is obtained by deleting from the factorization (25) of h every simple cycle h i which first action a i is in A 1 (s). Symetrically, π 1 (h) is obtained by erasing every simple cycle h i such that a i ∈ A 0 (s). Let us formalize this construction in an inductive way. First we define inductively the mode of a play. For h ∈ P * A,s , a ∈ A(h) and t ∈ S

mode(hat) =      mode(h) if the target of h is not s. 0 if the target of h is s and a ∈ A 0 (s) 1 if the target of h is s and a ∈ A 1 (s) (26)
For i ∈ {0, 1}, the projection π i is defined by π i (s) = s, and for h ∈ P * A,s , a ∈ A(h) and t ∈ S,

π i (hat) = π i (h)at if mode(hat) = i π i (h) if mode(hat) = 1 -i. (27)
The definition domain of π 0 and π 1 naturally extends to P ω A,s , in the following way. Let h = s 0 a 1 s 1 • • • ∈ P ω A,s be an infinite history, and for every n ∈ N, let

h n = s 0 a 1 • • • s n . Then for every n ∈ N, π 0 (h n ) is a prefix of π 0 (h n+1 ). If the sequence (π 0 (h n ))
n∈N is stationary equal to some finite word h ∈ P * A0,s , then we define π 0 (h) = h . Otherwise, the sequence (π 0 (h n )) n∈N has a limit h ∈ P ω A0,s , and we define π 0 (h) = h . Let us define the random variables: Definition 8. The two random variables

Π 0 = π 0 (S 0 A 1 S 1 • • • ) with values in P * A0,s ∪ P ω A0,s Π 1 = π 1 (S 0 A 1 S 1 • • • ) with values in P * A1,s ∪ P ω A1,s
are called the projections associated with the split (A 0 , A 1 ).

Useful properties of Π 0 and Π 1 are summarized in the following proposition.

Proposition 4. Let A be a controllable Markov chain, s, t states of A, (A 0 , A 1 ) a split of A on s, and Π 0 and Π 1 the projections associated with that split.

• Let h 0 ∈ P * A0,s be a finite history in A 0 , with source s and target t, and a ∈ A 0 (t). Let be the prefix order relation on finite and infinite words. Then ∀r ∈ S,

P σ s (h 0 ar Π 0 | h 0 a Π 0 ) = p(r|t, a). (28)
• Let x ∈ R and φ be a prefix-independent submixing payoff function. Then

{N s = ∞ and φ > x} ⊆ {Π 0 is infinite and N s (Π 0 ) = ∞ and φ(Π 0 ) > x} {Π 1 is infinite and N s (Π 1 ) = ∞ and φ(Π 1 ) > x} . (29)
Proof. We first prove (28). Let π 0 and π 1 be the functions defined by ( 27) and (26) above. Remark that their definition show that hey are both -increasing. Remember that for h ∈ P * A,s we denote the event {h

S 0 A 1 S 1 • • • } as O h . Y = {h ∈ P * A,s | π 0 (h) =
We start with inclusion ⊆. Let r ∈ S, h ∈ Y and l ∈ P ω A,s such that har l. Since h ∈ Y , and by definition ( 26) and ( 27), we deduce that ∀r, mode(har) = 0 and π 0 (har) = h 0 ar. Since π 0 is -increasing, and har l, we get π 0 (har) π 0 (l), hence h 0 ar π 0 (l) thus l ∈ {h 0 ar Π 0 }. It proves inclusion ⊆ of (30).

Let us prove now inclusion ⊇ of (30). Let r ∈ S and l ∈ {h 0 ar Π 0 }.

Then h 0 ar π 0 (l). Rewrite l as l = s 0 a 1 s 1 • • • . Since Π 0 is -increasing, ∃n ∈ N s.t. h 0 ar π 0 (s 0 • • • s n-1 a n s n ) and h 0 ar π 0 (s 0 • • • s n-1 ). Define h = s 0 a 1 • • • s n-1
, then last equation rewrites as h 0 ar π 0 (h) and h 0 ar π 0 (ha n s n ). According to definition (27) of π 0 , it necessarilly means that h 0 = π 0 (h) and h 0 ar = π 0 (h)a n s n . Hence h ∈ Y , a n = a and s n = r, thus har l and l ∈ ∪ h∈Y {har}. It achieves to prove (30).

Let X the prefix-free closure of Y , i.e.

X = {h ∈ Y | ∃h ∈ Y s.t. h = h
and (O ha ) h∈X is a partition of {h 0 a π 0 } .

From (31), we get for r ∈ S,

P σ s (h 0 ar π 0 ) = h∈X P σ s (O har ) = h∈X p(r|t, a) • P σ s (ha) from (2)
= p(r|t, a)

• h∈X P σ s (ha) = p(r|t, a) • P σ s (h 0 a π 0 ) from (32),
It achieves the proof of (28). Now let us prove (29). Let φ be a prefix-independent submixing payoff function, and x ∈ R. Let h ∈ {N s = +∞ and φ > x}.

Suppose first that π 1 (h) is a finite word. Then according to (27), the set {h ∈ P * A,s | h h and mode(h ) = 1} is finite. According to (27) again, it implies that h and π 0 (h) are identical, except for a finite prefix. Since φ is prefix-independent, it implies φ(h) = φ(π 0 (h)). Moreover, since N s (h) = +∞, we have N s (π 0 (h)) = +∞. This two last facts prove (29) in the case where π 1 (h) is finite.

The case where π 0 (h) is finite is symmetrical. Let us suppose now that both π 0 (h) and π 1 (h) are infinite. We prove that there exists u 0 , v 0 , u 1 , v 1 ∈ (SA) * such that

h = u 0 v 0 u 1 v 1 • • • π 0 (h) = u 0 u 1 u 2 • • • (33) π 1 (h) = v 0 v 1 v 2 • • • . Write h = s 0 a 1 s 1 • • • . Let {n 0 < n 1 < . . .} = {n > 0 | mode(s 0 a 1 • • • s n ) = 0 and mode(s 0 a 1 • • • s n+1 ) = 1} , {m 0 < m 1 < . . .} = {m > 0 | mode(s 0 a 1 • • • s m ) = 1 and mode(s 0 a 1 • • • s m+1 ) = 0} .
Then, by definition (26),

∀i ∈ N, s ni = s mi = s . (34)
Without loss of generality suppose a 1 ∈ A 0 (s). Then by (26), mode(s

0 a 1 s 1 ) = 0 hence 0 < n 0 < m 0 < n 1 < • • • . Define u 0 = s 0 a 1 • • • s n0-1 a n0 , for i ∈ N define v i = s ni • • • a mi and for i ∈ N define u i+1 = s mi • • • a ni+1 .
Then by (27) we get (33). Since φ is submixing, (33) implies φ(h) ≤ max{φ(π 0 (h)), φ(π 1 (h)}. Since φ(h) > x we deduce x < max{φ(π 0 (h)), π 1 (h)}, i.e.

(φ(π 0 (h)) < x) or (φ(π 1 (h)) < x).

(35)

Moreover, by (34) and (33), histories π 0 (h) and π 1 (h) reaches infinitely often s, hence N s (π 0 (h)) = N s (π 1 (h)) = +∞ . This last fact together with (35) implies (29) which achieves this proof.

The following theorem shows that any strategy σ in A can be simulated by a strategy σ 0 in A 0 , in a way that for any Π 0 -measurable event E in A, the probability of E under σ in A is less than the probability of Π 0 (E) under σ 0 in A 0 . Theorem 4. Let A be a controllable Markoc chain, σ a strategy in A, s a state of A such that |A(s)| ≥ 2, (A 0 , A 1 ) a split of A on s, and Π 0 he associated projection. Then there exists a strategy σ 0 in A 0 such that for any event E 0 ⊆ P ω A0,s P σ,s (π 0 ∈ E 0 ) ≤ P σ0,s (E 0 ).

(36)

Proof. The symbol denotes the prefix ordering on finite and infinite words. For two words u, v, we write u v if u is a strict prefix of v i.e. if u v and u = v.

For any state t = s, let us choose in an arbitrary way an action a t ∈ A(t), and let us also choose an action a s ∈ A 0 (s). For any h ∈ P * A0,s with target t and for any action a ∈ A(t), we define

σ 0 (h)(a) =      P σ s (ha Π 0 | h Π 0 ) if P σ s (h Π 0 ) > 0 1 if P σ s (h Π 0 ) = 0 and a = a t 0 if P σ s (h Π 0 )
= 0 and a = a t Then σ 0 is a strategy in A 0 since by definition of ,

P σ s (h Π 0 ) = a∈A(t) P σ s (ha Π 0 ) .
We first show (36) in the particular case where there exists h 0 ∈ P * A0,s such that E 0 = {l ∈ P ω A0,s | h l}. Remember that we abuse the notation and write simply E 0 = h. With this notation, we wish to prove that:

∀h ∈ P * A0,s , P σ s (h Π 0 ) ≤ P σ0 s (h ). ( 37
)
We prove (37) inductively. If h = s then since Π 0 has values in P * A,s ∪ P ω A,s , we get P σ s (s π 0 ) = 1 = P σ0 s (s). Now let us suppose that (37) is proven for some finite history h ∈ P * A0,s . Let t be the target of h and a ∈ A 0 (t), and let us prove that (37) holds for h = hat. First case is P σ s (h Π 0 ) = 0, then a fortiori P σ s (har Π 0 ) = 0, and (37) holds for h = hat. Now let us suppose P σ s (h Π 0 ) = 0. Then,

P σ s (har Π 0 ) = p(r|t, a) • P σ s (ha Π 0 ) = p(r|t, a) • P σ s (ha Π 0 | h Π 0 ) • P σ s (h Π 0 ) = p(r|t, a) • σ 0 (h)(a) • P σ s (h Π 0 ) ≤ p(r|t, a) • σ 0 (h)(a) • P σ s (h Π 0 ) ≤ p(r|t, a) • σ 0 (h)(a) • P σ0 s (h) = P σ0
s (har). The first equality comes from (28), and the third is by definition of σ 0 . The last inequality is by induction hypothesis and the last equality by (1) and (2). It achieves the proof of equality (37).

Let us achieve the proof of Theorem 4. Let E be the collection of events E 0 ⊆ P ω A0,s such that (36) holds. Then observe that E is stable by enumerable disjoint unions and enumerable increasing unions. According to (37), E contains all the events (O h0 ) h0∈P * A 0 ,s . Since E is stable by enumerable disjoint unions, it contains the collection { h0∈H0 O h0 | H 0 ⊆ P * A0,s }. This last collection is a Boolean algebra. Since E is stable by enumerable increasing union, it implies that E contains the σ-field generated by (O h0 ) h0∈P * A 0 ,s , i.e. all measurable sets of P ω A0,s . It achieves this proof.

A.5 Histories that never come back in their initial state.

We deduce from theorem 3 the following result.

Theorem 5. Let M = (A, φ) be an MDP, s a state, σ a strategy and (M 0 , M 1 ) a split of M on s. Let us suppose that φ is prefix-independent. Then

E σ s [φ | N s < ∞] ≤ max{val(M 0 )(s), val(M 1 )(s)}. ( 38
)
Proof. Let us define v 0 = val(M 0 , φ) and v 1 = val(M 1 )(φ). For any action a ∈ A(s) we denote σ a the strategy in A defined for h ∈ P * A,s by: σ a (h) = σ(h) if the target of h is not s σ a (h) chooses action a with probability 1 otherwise.

Remark that the strategy σ a always chooses the same action when plays reaches state s, and it is either a strategy in A 0 or a strategy in A 1 . From Theorem 3, we deduce ∀a ∈ A(s),

E σa s [φ | N s = 0] ≤ max{v 0 , v 1 }. (39)
Since σ and σ a coincide on {N s = 0, A 1 = a}, lemma 2 implies :

E σ s [φ | A 1 = a, N s = 0] = E σa s [φ | A 1 = a, N s = 0] = E σa s [φ | N s = 0] ,
where the last equality holds since by definition of σ a , P σa s (A 1 = a) = 1. Together with (39), we get E σ s [φ | A 1 = a, N s = 0] ≤ max{v 0 , v 1 }, whatever be action a and strategy σ. It implies :

∀σ ∈ Σ A , E σ s [φ | N s = 0] ≤ max{v 0 , v 1 }.
Conditioning on the last moment where history reaches s, and using the shifting lemma anf the prefix-independence of φ, this last equation implies :

E σ s [φ | N s < ∞] ≤ max{v 0 , v 1 }.
It achieves the proof of Theorem 5.

A.6 Histories that infinitely often reach their initial state.

The following theorem shows that if an history reaches infinitely often its initial state, then its value is no more than the value of that state.

Theorem 6. Let M = (A, φ) be an MDP, s a state and σ a strategy. Suppose that φ is prefix-independent and submixing. Then

P σ s (φ > val(M)(s) | N s = ∞) = 0. ( 40
)
Moreover, suppose that |A(s)| ≥ 2 and let (M 0 , M 1 ) be a split of M on s. Then

P σ s (φ > max{val(M 0 )(s), val(M)(s)} | N s = ∞) = 0. (41)
Proof. We prove that theorem by induction on N (A) = s∈S (|A(s)| -1).

If N (A) = 0 then A is a Markov chain. In that case, P σ s (N s = ∞) > 0 iff s is a recurrent state iff P σ s (N s = ∞) = 1. Hence (40) is a direct consequence of Theorem 2. Moreover, since N (A) = 0, then ∀s, |A(s)| = 1 and we do not need to prove (41). Now let us suppose that N (A) > 0 and that Theorem 6 is proven for any A such that N (A ) < N (A). We first prove (41). Let s be a state, σ a strategy, suppose that |A(s)| > 2 and let (A 0 , A 1 ) be a split of A on s. Let M 0 = (A 0 , φ), M 1 = (A 1 , φ), v 0 = val(M 0 , φ), v 1 = val(M 1 , φ), and Π 0 , Π 1 the associated projections. Let

E 0 = {h 0 ∈ P ω A0,s | φ(h 0 ) > v 0 and N s (h 0 ) = +∞} E = {h ∈ P ω A,s | π 0 (h) ∈ E 0 } .
We start with proving that

P σ s (E) = 0. ( 42
)
From Theorem 4, there exists a strategy σ 0 in A 0 such that P σ s (Π 0 ∈ E 0 ) ≤ P σ0

s (E 0 ). Hence

P σ,s (E) = P σ,s (Π 0 ∈ E 0 ) ≤ P σ0,s (E 0 ) = P σ0,s (φ > v 0 and N s = +∞) = 0,
where this last equality holds by induction hypothesis, since N (A 0 ) < N (A). Hence we have shown (42) and by symmetry, we obtain for i ∈ {0, 1},

P σ s (Π i is infinite and N s (Π i ) = ∞ and φ(Π i ) > v i ) = 0 .
For achieving the proof of (40) we must prove that T = S, i.e. U = ∅. Suppose the contrary, and let us search a contradiction. If U = ∅, then the set

W = {s ∈ U | val(M)(s) = min t∈U val(M)(t)}
is not empty and contains a state s ∈ W . According to (44), there exists a unique action a available in s. Now we show that ∀t ∈ S such that p(t|s, a) > 0,

if t ∈ U then val(M)(t) ≥ val(M)(s) (45) if t ∈ T then val(M)(t) > val(M)(s) . (46)
The case where t ∈ U is clear since we choose s with minimal value in U . Now let t ∈ T such that p(t|s, a) > 0 and let us prove 46. Since s ∈ U , s ∈ T and by definition of T ,

∃σ ∈ Σ A s.t. P σ s (φ > val(M)(s) and N s = ∞) > 0 . (47)
Now remark that since p(t|s, a) > 0 we have

P σ s (N t = ∞ | N s = ∞) = 1.
Together with (47), it implies

P σ s (φ > val(M)(s) and N t = ∞) > 0 .
Conditioning this probability on the first moment the history reaches state t, we deduce that there exists a finite history h ∈ P * A,s with source s and target t such that P σ s (φ > val(M)(s) and N t = ∞ | h) > 0 . Since φ is prefix-independent, and according to the shifting lemma it implies : Finally we get a contradiction, hence U = ∅. This achieves the proof of Theorem 6.

A.7

Proof of Theorem 1

Remark that we can synthesize the results of this appendix as follows.

Corollary 1. Let M = (A, φ) be an MDP, s a state of A and (M 0 , M 1 ) a split of M on s. Suppose that φ is prefix-independent and submixing. Then val(M)(s) = max{val(M 0 )(s), val(M 1 )(s)}.

(49)

Proof. Let σ ∈ Σ A . Then

E σ s [φ] = E σ s [φ | N s < ∞] • P σ s (N s < ∞) + E σ s [φ | N s = ∞] • P σ s (N s = ∞) ≤ max{val(M 0 )(s), val(M 1 )(s)} • (P σ s (N s < ∞) + P σ s (N s = ∞)) = max{val(M 0 )(s), val(M 1 )(s)}
The second inequality is a consequence of Theorems 6 and 5. Since it is true for any strategy σ, we get : val(M)(s) ≤ max{val(M 0 )(s), val(M 1 )(s)} .

To conclude, notice that a strategy for the MDP M 0 or M 1 is also a strategy for the MDP M, hence val(M 0 )(s) ≤ val(M)(s) and val(M 1 )(s) ≤ val(M)(s). Now we can achieve the proof of Theorem 1.

Proof. of Theorem 1. We prove Theorem 1 by induction on N (A) = s∈S (|A(s)|-1).

First case is the case where N (A) = 0, i.e. A is a Markov chain. In that case, there exists a unique strategy, which is necessarilly optimal and positional. Now let us suppose that N (A) = s∈S (|A(s)| -1) > 0 and that Theorem 1 is proven for any A such that N (A ) < N (A). Since N (A) > 0, there exists a state s of A such that |A(s)| ≥ 2. Let (M 0 , M 1 ) be a split of M on s. Without loss of generality, we can suppose that :

val(M 0 )(s) ≥ val(M 1 )(s) , (50)
and according to corollary 1, we deduce : val(M 0 )(s) = val(M)(s) .

By inductive hypothesis, there exists a positional strategy σ 0 optimal for the MDP M 0 . We are going to prove that σ 0 is also optimal for MDP M. Let σ ∈ Σ A and t ∈ S. Then Let τ ∈ Σ A defined as follows :

τ (s 0 a 1 • • • s n ) = σ(s 0 a 1 • • • s n ) if ∀0 ≤ i ≤ n, s i = s, σ 0 (s n ) otherwise.
Then we have the three following equalities. First, since σ and τ coincide on the event {∀n, S n = s}, lemma 2 implies : where the inequality comes from the shifting lemma and the prefix-independence of φ, the first equality from (50), the second from the fact that σ 0 is optimal in M 0 and the third by the shifting lemma again. Finally, (54), ( 53) and (58) together with (52) prove that

E σ t [
∀t ∈ S, ∀σ ∈ Σ A , E σ t [φ] ≤ E τ t [φ] . (60)
By definition, τ always chooses an action of A 0 (s) when the history has target s, hence τ is a strategy in A 0 . Since σ 0 is optimal in M 0 hence we get :

∀t ∈ S, E τ t [φ] ≤ E σ0 t [φ] .
Since σ 0 is also a strategy in A, this last equation together with (60) proves that σ 0 is optimal in M. Since σ 0 is positional, it achieves the proof of the inductive step, and of Theorem 1.

  h 0 and ∃r ∈ S, π 0 (har) = h 0 ar}. Let us start with proving ∀r ∈ S, h∈Y {O har } = {h 0 ar π 0 } .

  union is in fact a disjoint union. Hence, ∀r ∈ S, (O har ) h∈X is a partition of {h 0 ar π 0 } ,

  Now consider (29) of Proposition 4, with x = max{v 0 , v 1 }. Together with the last equation, it gives (41). Now we prove that (40) holds. First we show that (40) holds for any state s such that |A(s)| ≥ 2. Any strategy in A 0 or A 1 is a strategy in A, hence val(M)(s) ≥ max{v 0 , v 1 } and we deduce from (41) that P σ s (φ > val(M)(s) | N s = ∞) = 0. Hence the setT = {s ∈ S | ∀σ ∈ Σ A , P σ s (φ > val(M)(s) and N s = ∞) = 0}(43)contains any state s ∈ S such that |A(s)| ≥ 2. Hence (40) holds for any s such that |A(s)| ≥ 2. Let U = S\T . We have proven that : ∀s ∈ U, |A(s)| = 1 .

  val(M)(s) and N t = ∞) > 0.Since t ∈ T , the definition of T implies :P σ[h] t (φ > val(M)(t) and N t = ∞) = 0 .Those two last equations imply val(M)(t) > val(M)(s), which achieves the proof of (46). Now we are close to get the contradiction we are looking for. Since φ is prefix-independent, we deduce :val(M)(s) = t:p(t|s,a)>0 p(t|s, a) • val(M)(t).Together with (46) we get :∀t ∈ S, (p(t|s, a) > 0) =⇒ (t ∈ U ) and (val(M)(t) = val(M)(s)) .This last equation holds for any s ∈ W . Thus any transition with source in W has target in W . It implies that any history in A with source in W stays in W with probability 1, hence the restriction A[W ] of A to the set of states W is a controllable Markov chain, and∀s ∈ W, val(M)(s) = val(M[W ])(s) (48) Let M[W ] = (A[W ], φ). By definition of U , there exists a strategy σ in A[W ] such that P σ,s (φ > val(M)(s) and N s = ∞) > 0 and together with (48) we getP σ s (φ > val(M[W ])(s) and N s = ∞) > 0 .Since W ⊆ U and according to (44), A[W ] is a Markov chain. According to the last equation, P s N s = ∞ > 0 hence s is a recurrent state. Hence the last equation contradicts Theorem 2.

  E σ t [φ] = E σ t [φ | ∃n, S n = s] • P σ t (∃n, S n = s)+ E σ t [φ | ∀n, S n = s] • P σ t (∀n, S n = s). (52)

  φ | ∀n, S n = s] • P σ t (∀n, S n = s) = E τ t [φ | ∀n, S n = s] • P τ t (∀n, S n = s). (53)Second, by definition of τ , P σ t (∃n, S n = s) = P τ t (∃n, S n = s) .

		(54)
	And finally,
	E σ t [φ | ∃n, S n = s] ≤ val(M)(s)	(55)
	= val(M 0 )(s)	(56)
	= E σ0 s [φ]	(57)
	= E τ t [φ | ∃n, S n = s] ,	(58)
		(59)

relatively to the Borelian σ-field on C ω .

For the sake of completeness, we gave all details, although this part of the proof is classical. An event E such that (17) holds is called a tail-event. The fact that probability of a tail event is either 0 or 1 is called Levy's or Kolmogorov's law[START_REF] Durett | Probability Theory and Examples[END_REF].

Acknoledgments

I would like to thank Wies law Zielonka for numerous discussions about payoff games on MDP's.

A short version of this report has been accepted for the 24th Symposium for Theoretical This research was supported by Instytut Informatyki of Warsaw University, European Research Training Network: Games and Automata for Synthesis and Valida