Hugo Gimbert
email: hugo.gimbert@labri.fr

Florian Horn
email: f.horn@cwi.nl

SOLVING SIMPLE STOCHASTIC GAMES WITH FEW RANDOM VERTICES

Keywords: 2000 ACM Subject Classification: Games, Stochastic Processes simple stochastic games, algorithm

published or not. The documents may come

Solving Simple Stochastic Games with Few Random

Vertices

Introduction

Simple stochastic games (SSGs) are played by two players called Max and Min in a sequence of steps. The players move a pebble along the edges of a directed graph (V, E) whose vertices are partionned into three sets: V Max , V Min , and V R . When the pebble is on a vertex of V Max or V Min , the corresponding player chooses an outgoing edge and moves the pebble along it. When the pebble is on a vertex of V R (a random vertex), the outgoing edge is chosen randomly according to a fixed probability distribution. The players have opposite goals, as Max wants to reach a special sink vertex ⊚ while Min wants to avoid it forever. An example of SSG is depicted in Figure 1, with vertices of V Max represented as 's, vertices of V Min represented as 's, and vertices of V R represented as △'s.

SSGs are a natural model of reactive systems. Consider, for example, a hardware component. It can be modelled as an SSG, whose vertices represent the global states of the component and the target is some error state to avoid. The nature of a given vertex depends on who can influence the immediate evolution of the system: it is a Min vertex if the software can choose between different options, a Max vertex if there is a (non-deterministic) input asked from the user, and a random vertex if the evolution depends on a stochastic environment. An optimal strategy for Min can then be used as the basis for the synthesis of a "good" driver, i.e. one which minimises the probability of entering the error state independently of the behaviour of the user.

The main algorithmic problem about SSGs is the computation of values of the vertices and optimal strategies for the players. This problem was first adressed by Condon, who showed that deciding whether the value of a vertex is greater than 1 2 belongs to NP and co-NP [START_REF] Condon | The Complexity of Stochastic Games[END_REF]. Condon's algorithm guesses non-deterministically the values of vertices, which are rational numbers of linear size, and checks that they are solutions of some local optimality equations. This algorithm is correct only for stopping games, where the pebble reaches either the target or a sink target with probability one, regardless of the players' strategies. Any SSG can be transformed in polynomial time into a stopping SSG with (almost) the same values, but it incurs a quadratic blow-up of the size of the game.

Three other algorithms for solving SSGs are presented in [START_REF] Condon | On Algorithms for Simple Stochastic Games[END_REF]. The first one computes the values of the vertices using a quadratic program with linear constraints. The second one computes iteratively from below the values of the vertices, and the third is a strategy improvement algorithm à la Hoffman-Karp [START_REF] Hoffman | On Nonterminating Stochastic Games[END_REF]. The two latter algorithms, as the ones recently proposed in [START_REF] Somla | New Algorithms for Solving Simple Stochastic Games[END_REF], solve a series of linear programs which could be of exponential length. Furthermore, solving a linear program requires high-precision arithmetic, even if it can be done in polynomial time [START_REF] Khachiyan | A Polynomial Algorithm in Linear Programming[END_REF][START_REF] Renegar | A polynomial-time algorithm, based on newton's method, for linear programming[END_REF]. The best randomised algorithms achieve sub-exponential expected time e O( √ n) [START_REF] Ludwig | A Subexponential Randomized Algorithm for the Simple Stochastic Game Problem[END_REF][START_REF] Halman | Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems[END_REF]. In this paper we present two algorithms computing the values and optimal strategies in SSGs: the "permutation-enumeration" and the "permutation-improvement" algorithms. The common basis for both algorithms is that optimal strategies can be looked for in a subset of the positional strategies called permutation strategies. Permutation strategies are derived from permutations over the random vertices. In order to find optimal strategies, the permutation-enumeration algorithm performs an exhaustive search among all permutation strategies, whereas the permutation-improvement algorithm performs successive improvements of permutation strategies, à la Hoffman-Karp [START_REF] Hoffman | On Nonterminating Stochastic Games[END_REF].

The permutation-enumeration and the permutation-improvement algorithms share two advantages over existing algorithms. First, they perform much better on SSGs with few random vertices, as they run in polynomial time when the number of random vertices is logarithmic in the size of the game: it follows that the problem of solving SSGs is fixedparameter tractable when the parameter is the number of random vertices. Second, they do not rely on the transformation of the input SSG into a stopping SSG, which avoids the quadratic blow-up of the size of the game. Moreover, the permutation-enumeration algorithm does not use linear or quadratic programming, (it just computes the solutions to linear systems) and its worst-case complexity is O |V R |! • (|E| + |δ|) , where |V R | is the number of random vertices, |E| is the number of edges and |δ| is the maximal bitlength of transition probabilities. The nominal complexity of the permutation-improvement algorithm is higher but we do not know any non-trivial lower bound for its complexity: the permutation-improvement algorithm may actually run in polynomial time.

Outline. In Section 1, we provide formal definitions for SSGs, values and optimal strategies. We describe then in Section 2 the central notion of permutation strategies. Section 3 presents the permutation-enumeration algorithm, based on the self-consistency and liveness properties. Section 4 introduces an improvement policy for permutations which leads to the permutation-improvement algorithm.

Simple Stochastic Games

1.1. Plays and strategies. A simple stochastic game is a tuple (V, V Max , V Min , V R , E, δ, ⊚), where (V, E) is a graph, (V Max , V Min , V R ) is a partition of V , and ⊚ is a distinguished sink vertex in V called the target of the game. The transitions from the random vertices are equipped with probabilities described by the function δ :

V R → V → [0, 1], such that for all v ∈ V R , w ∈ V , δ(v)(w) > 0 ⇒ (v, w) ∈ E, and w∈V δ(v)(w) = 1.
An infinite play ρ is an infinite sequence ρ 0 ρ 1 • • • ∈ V ω of vertices such that for all i ∈ N, (ρ i , ρ i+1 ) ∈ E. It is winning for Max if there is a i ∈ N such that ρ i = ⊚ (as ⊚ is a sink, it follows that ∀j > i, ρ j = ⊚). Otherwise, ρ is winning for Min. A finite play is a finite prefix of an infinite play.

A (pure) strategy for Max is a mapping σ : V * V Max → V such that for each finite play h = h 0 . . . h i ending in a Max vertex, (h i , σ(h)) ∈ E. It is positional if it only depends on the last vertex of h: σ(h) = σ(h i ). A play ρ 0 ρ 1 . . . is consistent with σ if for every i such that ρ i ∈ V Max , ρ i+1 = σ(ρ 0 . . . ρ i ). Strategies for Min are defined analogously and are generally denoted by τ . 1.2. Measures and values. The set of plays is made into a measurable space on the σ-algebra generated by the canonical projections {V i } i∈N , where V i (ρ 0 ρ 1 . . . ) = ρ i [START_REF] Billingsley | Probability and Measure[END_REF]. Once an initial vertex v and two strategies σ and τ for players Max and Min have been fixed, the probability measure P σ,τ v is defined by:

P σ,τ v (V 0 = v) = 1 , P σ,τ v (V i+1 = σ(V 0 . . . V i ) | V i ∈ V Max ) = 1 , P σ,τ v (V i+1 = τ (V 0 . . . V i ) | V i ∈ V Min ) = 1 , P σ,τ v (V i+1 | V i ∈ V R ) = δ(V i )(V i+1 ) .
The expectation of a real-valued, measurable and bounded function ϕ under P σ,τ v is denoted E σ,τ v [ϕ]. We will often use implicitly the following formulae which rule the probabilities and expectations once a finite prefix h = h 0 . . . h i is fixed:

P σ,τ v (Γ | V 0 . . . V i = h 0 . . . h i ) = P σ[h],τ [h] h i (Γ[h]) , (1.1) E σ,τ v [ϕ | V 0 . . . V i = h 0 . . . h i ] = E σ[h],τ [h] h i [ϕ[h]] , (1.2)
where σ[h](ρ 0 ρ 1 . . .) = σ(h 0 . . . h i-1 ρ 0 ρ 1 . . .), and τ [h], Γ[h], and ϕ[h] are defined analogously.

If we fix only Max's strategy σ and the initial vertex v, the target vertex will be reached with probability at least:

inf τ P σ,τ v (Reach(⊚))
, where Reach(⊚) is the event {∃i ∈ N, V i = ⊚}. Starting from v, player Max has strategies that guarantee a winning outcome with a probability greater than:

val * (v) = sup σ inf τ P σ,τ v (Reach(⊚)) ,
minus ǫ for any ǫ > 0. Symmetrically, Min has strategies that guarantee a winning outcome with a probability less than:

val * (v) = inf τ sup σ P σ,τ v (Reach(⊚)) , plus ǫ for any ǫ > 0. It is clear that val * (v) ≤ val * (v).
In the case of SSGs, stronger results are known:

Theorem 1.1 ([Sha53, Gil57, LL69]). Let G = (V, V Max , V Min , V R , E, ⊚, δ) be a SSG. Then, for any vertex v ∈ V , val * (v) = val * (v)
. This common value is denoted by val(v). Furthermore, there are positional optimal strategies for both players, i.e. positional strategies σ # and τ # such that, for any strategies σ and τ :

P σ,τ # v (Reach(⊚)) ≤ val(v) ≤ P σ # ,τ v (Reach(⊚)) .
1.3. Normalised games. A SSG is normalised if the only vertex with value 1 is the target ⊚ and there is only one (sink) vertex ⊗ with value 0. Our motivations for the introduction of this notion are twofold. First, several proofs are much simpler for normalised games. Second, any SSG can be reduced to an equivalent normalised game in linear time and the resulting game is smaller than the original one. This reduction is presented on Figure 2: it simply consists in merging the region with value one into ⊚ and the region with value zero into a new sink vertex ⊗.

In the remainder of this article, we assume that we are working on a normalised SSG

G = (V, V Max , V Min , V R , E, δ, ⊚, ⊗), with k random vertices. val = 0 val = 1 Figure 2: Normalisation.

Permutation strategies

The existence of positional optimal strategies is a key property of SSGs and the cornerstone of many algorithms solving these games. The algorithms we propose rely on a refinement of this result: optimal strategies can be looked for among a subset of the positional strategies, the set of "permutation strategies".

As a matter of fact, Theorem 1.1 is a corollary of results of the present paper. The proofs of our results often rely on the existence of values and optimal (not only ǫ-optimal) strategies in SSGs. This could be avoided -the main point is to use val * instead of valbut we felt that it was not worth the extra complexity.

The main intuition underlying permutation strategies is that the only meaningful events in a play are the visits to random vertices. Between two visits the players only strive to impose which random vertex will be visited next, and the result of their interaction can be easily predicted. This is illustrated by Figure 3, which zooms on two details of Figure 1. In the left part of Figure 3, Max must choose between the two random vertices b and c (refusing to choose is not really an option). There is no reason to choose b in one of the vertices, and c in the other. We could consider only the strategies "always go to b" and "always go to c". In the right part of Figure 3, we consider relationships between the two players' strategies. From their respective vertices and , Max and Min can send the pebble to either a or b. We could restrict our attention to the cases where Max goes to one, and Min to the other.

Underlying these intuitions is the idea of a "preference order" over the random vertices. In the remainder of this article, we formalise it as a permutation: a one-to-one correspondance f between V R and {1, . . . , k}. For simplicity, we often write f i instead of f -1 (i) and we consider the sink and target vertices as random vertices with the implicit assumption that they are respectively the lowest and greatest vertices: f 0 = ⊗ and f k+1 = ⊚.

2.1. Attractors and f -regions. Once a permutation f : V R → {1, . . . , k} has been fixed, the f -strategies consist in Max trying to reach the highest (with respect to f ) possible random vertex, while Min tries to thwart her. Notice that the situation is not exactly symmetric, since the burden of reaching a random vertex lies with Max: in case the pebble remains forever in controlled vertices then player Min wins. The formal definition of permutation strategies is based on the notion of deterministic attractor.

Definition 2.1. Let X ⊆ V be a set of vertices. The deterministic attractor of Max to X, denoted by DetAtt(X), is computed recursively:

X 0 = X , X i+1 = X i ∪ v ∈ V Max | ∃w ∈ X i , (v, w) ∈ E ∪ v ∈ V Min | ∀w ∈ V, (v, w) ∈ E ⇒ w ∈ X i , DetAtt(X) = i>0 X i .
An attracting strategy to X for Max is a positional strategy σ such that:

∀i ≥ 1, σ(X i ) ⊆ X i-1 .
Symmetrically, a trapping strategy out of X for Min is a positional strategy τ such that:

τ (V \ DetAtt(X)) ⊆ V \ DetAtt(X) .
The f -regions associated with a permutation f : V R → {1, . . . , k} are defined as embedded deterministic attractors to the random vertices:

W f [k + 1] = {⊚} , ∀1 ≤ i ≤ k, W f [i] = DetAtt({f i , . . . , f k , ⊚}) \ j>i W f [j] , W f [0] = {⊗} .
2.2. Permutation strategies. The f -strategies σ f and τ f are strategies such that, on each W f [i]:

• σ f coincides with an attractor strategy to {f i , . . . , f k , ⊚},

• τ f coincides with a trapping strategy out of {f i+1 , . . . , f k , ⊚}.

The f -regions partition V , so we extend the definition domain of f : V R → {1, . . . , k} to V in a natural way:

f (v) = i if v ∈ W f [i].
The following properties are easy to prove:

∀v ∈ V Max , f (v) = f (σ f (v)) , (2.1) ∀v ∈ V Max , ∀(v, w) ∈ E, f (v) ≥ f (w) , (2.2) ∀v ∈ V Min , f (v) = f (τ f (v)) , (2.3) ∀v ∈ V Min , ∀(v, w) ∈ E, f (v) ≤ f (w) .
(2.4)

If Max plays σ f and Min plays τ f from an initial vertex v, the first random vertex reached by the pebble is the unique random vertex w such that f (w) = f (v). Figure 4 describes the f -regions and f -strategies of the game of Figure 1, for f = abcd. 2.3. The f -values. When both players use their respective permutation strategies, the probability that a pebble starting in v reaches ⊚ is denoted by ϕ f (v): In order to compute the f -values, we build a Markov chain M f designed to mimic the behaviour of G when the players use their f -strategies. Intuitively, we merge each region W f [i] into a single vertex i; formally, M f is a Markov chain with states S = {0, . . . , k + 1} such that 0 and k + 1 are absorbing and, for every 1 ≤ i ≤ k and 0 ≤ j ≤ k + 1, the transition probability from i to j is given by:

f 1 f 2 f 3 f 4
ϕ f (v) = P σ f ,τ f v (Reach(⊚)) .
p ij = v∈W f [j] δ(f i )(v) .
The values x * : {0, . . . , k + 1} → [0, 1] of M f are computed as follows. Let I ⊆ S be the set of vertices from which k + 1 is reachable in M f . Then, for each i / ∈ I, x * i = 0, and (x * i ) i∈I is the unique solution of the following linear system:

x * k+1 = 1 x * i = j∈I p i,j • x * j , which can be solved in time O |V R | 3 |δ| [Dix82]. For each v ∈ V , ϕ f (v) = x * f (v) .

The permutation-enumeration algorithm

In this section we describe the permutation-enumeration algorithm which computes optimal strategies for both players. This algorithm relies on the following key property of permutation strategies.

Theorem 3.1. In every SSG, there exists a permutation f such that σ f is optimal for Max and τ f is optimal for Min. This theorem suggests a very simple enumerative algorithm computing values and optimal strategies: check for each permutation f whether the f -strategies are optimal. Each test can be performed in polynomial time using linear programming [START_REF] Derman | Finite State Markovian Decision Processes[END_REF][START_REF] Condon | The Complexity of Stochastic Games[END_REF]. However, linear programming requires high-precision arithmetic and is expensive in practice. Our permutation-enumeration algorithm uses a simpler criterion based on a refinement of Theorem 3.1: we look for permutations which are live and self-consistent.

3.1. Liveness and self-consistency. The permutation-enumeration algorithm is based on two simple properties on permutations: self-consistency and liveness. Self-consistency expresses the adequation between a priori preferences (permutation f ) and resulting values (the f -values ϕ f ). Liveness stipulates that each random vertex has a positive probability to immediately lead to a better -from Max's point of view-region.

Definition 3.2. A permutation f is self-consistent if: ϕ f (f 1 ) ≤ ϕ f (f 2 ) ≤ . . . ≤ ϕ f (f k ) . Definition 3.3. A permutation f is live if: ∀1 ≤ i ≤ k, ∃j > i, ∃v ∈ W f [j], δ(f i )(v) > 0 .
As we show below, the f -strategies associated with a live and self-consistent permutation f are optimal and there is always such a permutation. The permutation-enumeration algorithm performs an exhaustive search for a live and self-consistent permutation. Proof. Correctness and termination are proved in Lemmas 3.7 and 3.10, respectively. The worst-case complexity follows from the fact that there are at most k! permutations and Proposition 2.2.

Input: A normalised simple stochastic game G = (V, V Max , V Min , V R , E, δ, ⊚, ⊗).
Before we proceed with the proofs of the main lemmas, let us make a case for liveness: Figure 5 shows that self-consistency is not enough to guarantee the optimality of the resulting strategies 1 . In this excerpt from the game of Figure 1, Max's strategy in should be to send the pebble to b, as Min could otherwise trap the play in {a, , }. However, consider the permutation g = bcad: Min sends the pebble from to c to avoid a; Max sends the pebble from to to reach either a or c. We have thus ϕ g (a) = ϕ g (c). As a matter of fact, we have ϕ g (b) ≤ ϕ g (a) = ϕ g (c) ≤ ϕ g (d), so g is self-consistent even though the g-values are not the correct ones. Liveness forbids this kind of gambits from Max. It replaces, in this aspect, the "stopping" hypothesis of Condon.

Correctness of the permutation-enumeration algorithm.

We first show that if a permutation f is live and self-consistent, the f -strategies are optimal (Lemma 3.7). We need two preliminary propositions. First, if f is self-consistent and Max plays according to σ f , the sequence (ϕ f (V i )) i∈N is a submartingale 2 and symmetrically if f is self-consistent and Min plays according to τ f the sequence (ϕ f (V i )) i∈N is a supermartingale. Proposition 3.5. Let f be a self-consistent permutation. Then, for any strategies σ and τ for Max and Min, vertex v, and integer i,

E σ f ,τ v [ϕ f (V i+1 ) | V 0 . . . V i ] ≥ ϕ f (V i ) , (3.1) E σ,τ f v [ϕ f (V i+1 ) | V 0 . . . V i ] ≤ ϕ f (V i ) . (3.2)
1 It would be enough in stopping games, but testing liveness is cheaper than the reduction. 2 We do not use any result about martingales in this paper.

Proof. In order to prove (3.1), it is enough to show that for any finite play h = h 0 . . . h i ,

E σ f ,τ v [ ϕ f (V i+1 ) | V 0 . . . V i = h 0 . . . h i ] ≥ ϕ f (h i ) . (3.3)
Depending on the owner of h i , (3.3) follows from one of the following properties of ϕ f :

∀v ∈ V Max , ϕ f (v) = ϕ f (σ f (v)) , (3.4) ∀v ∈ V Min , ∀(v, w) ∈ E, ϕ f (v) ≤ ϕ f (w) , (3.5) ∀v ∈ V R , ϕ f (v) = w∈V δ(v)(w) • ϕ f (w) . (3.6)
The equations (3.4) and (3.6) follows from the definition of ϕ f , and (3.5) follows from the self-consistency of f : by definition of the f -regions, if v ∈ V Min and (v, w)

∈ E then f (v) ≤ f (w) (see (2.2)), so ϕ f (v) ≤ ϕ f (w)
. The proof of (3.2) is similar and we do not detail it.

Second, we show a "stopping property" in the case where f is live and Max plays σ f . Proposition 3.6. Let f be a live permutation. Then, for any strategy τ for Min and initial vertex v,

P σ f ,τ v (Reach(⊚) ∨ Reach(⊗)) = 1 .
Proof. By definition of liveness,

α = min 1≤i≤k w∈ S j>i W f [j] δ(f i )(w)
P σ f ,τ v (V n = ⊚ | V 0 = ⊗) ≥ α k ,
or, since ⊚ and ⊗ are sinks:

P σ f ,τ v (∀m ≤ n, V m / ∈ {⊚, ⊗}) ≤ 1 -α k .
Equation (1.1) yields:

∀i ∈ N, P σ f ,τ v (∀m ≤ i • n, V m / ∈ {⊚, ⊗}) ≤ (1 -α k ) i , hence P σ f ,τ v (∀m ∈ N, V m / ∈ {⊚, ⊗}) = 0 hence Proposition 3.6.
We can now prove the correctness of the permutation-enumeration algorithm:

Lemma 3.7. Let f be a live and self-consistent permutation. Then σ f is optimal for Max and τ f is optimal for Min.

Proof. We first prove that σ f ensures that a pebble starting from v has probability at least ϕ f (v) to reach ⊚:

P σ f ,τ v (Reach(⊚)) = E σ f ,τ v lim i∈N ϕ f (V i ) (3.7) = lim i∈N E σ f ,τ v [ϕ f (V i )] (3.8) ≥ E σ f ,τ v [ϕ f (V 0 )] = ϕ f (v) , (3.9)
where (3.7) comes from Proposition 3.6, (3.8) is a property of expectations, and (3.9) comes from Proposition 3.5.

Then, we show that τ f ensures that a pebble starting from v has probability at most ϕ f (v) to reach ⊚:

P σ,τ f v (Reach(⊚)) ≤ E σ,τ f v lim inf i∈N ϕ f (V i ) (3.10) ≤ lim inf i∈N E σ,τ f v [ϕ f (V i )] (3.11) ≤ E σ,τ f v [ϕ f (V 0 )] = ϕ f (v) , (3.12)
where (3.10) holds because ⊚ is a sink and ϕ f (⊚) = 1, (3.11) is a property of expectations, and (3.12) comes from Proposition 3.5. Thus, for any strategies σ and τ for Max and Min,

P σ,τ f v (Reach(⊚)) ≤ P σ f ,τ f v (Reach(⊚)) ≤ P σ f ,τ v (Reach(⊚)) ,
which completes the proof of Lemma 3.7 3.3. Termination of the permutation-enumeration algorithm. Now we show the existence of a live and self-consistent permutation (Lemma Our construction is based on Proposition 3.8 and its correctness on Proposition 3.9.

Proposition 3.8. Let X ⊆ V be a set of vertices including the target vertex ⊚ and Y be V \ DetAtt(X). Then either Y = {⊗} or there is a random vertex v in Y such that:

val(v) = max{val(w) | w ∈ Y } , ∃w ∈ DetAtt(X), δ(v)(w) > 0 .
Proof. Let Z be the set of vertices with maximal value in Y :

Z = {v ∈ Y | val(v) = max w∈Y val(w)} ,
and suppose that:

∀v ∈ V R ∩ Z, ∀w ∈ DetAtt(X), δ(v)(w) = 0 . Let v be a vertex in Z.
As G is normalised, we just need to show that val(v) = 0, i.e. there is a strategy θ for Min such that for every strategy σ for Max, P σ,θ v (Reach(⊚)) = 0. By definition of DetAtt(X), there is a positional strategy τ for Min such that τ (Y ) ⊆ Y , and it follows from the definition of Z that τ (Z) ⊆ Z. As Z is also closed under random moves, a pebble starting in Z can only leave Z through a move of Max, which leads to Y \ Z as Y = V \ DetAtt(X).

We define now a non-positional strategy θ in which Min plays according to τ as long as the play remains in Z and switches definitively to an optimal strategy the first time the pebble moves out of Z. We can thus partition the plays starting in v and consistent with σ and θ depending on if and where the play gets out of Z: Γ Z is the set of plays remaining forever in Z, and for each w in Y \Z, Γ w is the set of plays where w is the first visited vertex outside of Z. Clearly P σ,θ v (Reach(⊚) | Γ Z ) = 0 and by definition of the strategy θ, ∀w ∈ Y \ Z, P σ,θ v (Reach(⊚) | Γ w ) ≤ val(w). Hence P σ,θ v (Reach(⊚)) ≤ max(0, max w∈Y \Z val(w)) and since this holds for every σ, val(v) ≤ max(0, max w∈Y \Z val(w)). By definition of Z this implies val(v) = 0. Proposition 3.9. Let f be a live permutation such that:

val(f 1 ) ≤ val(f 2 ) ≤ . . . ≤ val(f k ) . Then f is self-consistent.
Note that under the same hypotheses, Lemma 3.7 imply that f -strategies are optimal.

Proof. We first show that:

∀v ∈ V, ∀1 ≤ i ≤ k, (f (v) = i) ⇒ (val(v) = val(f i )) .
(3.13)

Consider the strategy σ * , which mimics σ f until the first time the pebble reaches a random vertex then switches definitively to an optimal strategy. By definition of σ f , the first random vertex belongs to {f i , . . . , f k , ⊚}, so σ * ensures that a pebble starting in q reaches ⊚ with probability at least min{val(f i ), . . . , val(f k ), val(⊚)} = val(f i ). A similar strategy τ * for Min ensures that this probability is at most val(f i ). So val(v) = val(f i ), and (3.13) follows. Now we prove that val and ϕ f coincide. According to (3.13) and by definition of permutation strategies,

∀v ∈ V Max , val(v) = val(σ f (v)) , ∀v ∈ V Min , val(v) = val(τ f (v)) , ∀v ∈ V R , val(v) = w∈V δ(v)(w) • val(w) .
So, if Max and Min play according to their f -strategies, the sequence val(V i ) i∈N is a martingale:

E σ f ,τ f v [val(V i+1 ) | V 0 . . . V i ] = val(V i ) . (3.14)
Consequenly, for every vertex v, ϕ f (v) = val(v):

ϕ f (v) = P σ f ,τ f v (Reach(⊚)) = E σ f ,τ f v lim i∈N val(V i ) (3.15) = lim i∈N E σ f ,τ f v [val(V i )] (3.16) = E σ f ,τ v [val(V 0 )] = val(v) , (3.17)
where (3.15) comes from Proposition 3.6, (3.16) is a property of expectations, and (3.17) comes from (3.14). Since val and ϕ f coincide, the hypothesis yields the self-consistency of f . This completes the proof of Proposition 3.9.

Lemma 3.10. There exists a live and self-consistent permutation.

Proof. We use iteratively Proposition 3.8 in order to build a permutation f such that, for every

k ≥ i ≥ 1, • val(f i ) = max {val(v) | v ∈ V \ DetAtt(f i+1 , f i+2 , . . . , f k )}; • ∃w ∈ DetAtt(f i+1 , f i+2 , . . . , f k ), δ(f i )(w) > 0.
By construction f is live and val(f 1 ) ≤ val(f 2 ) ≤ . . . ≤ val(f k ). Proposition 3.9 yields the self-consistency of f , and Lemma 3.10 follows.

The permutation-improvement algorithm

A drawback of the permutation-enumeration algorithm is that it considers each and every possible permutation of the random vertices, so |V R |! is a lower bound for the worst-case complexity of this algorithm. Strategy-improvement algorithms avoid such enumerations, instead these algorithms proceed by successive improvements of a strategy: information about sub-optimality of a strategy is used to determine a "better" strategy, which ensures convergence to an optimal strategy. In this section, we emulate this idea with a permutation-improvement algorithm.

4.1.

A natural but incorrect improvement policy. Starting from an initial permutation f , we would like to improve f again and again until the permutation strategies σ f and τ f are optimal. To test optimality we check that f is live and self-consistent (see Lemma 3.7). When f is live but not self-consistent we compute a new permutation g which is live and"better" than f . A natural improvement policy consists in choosing g consistent with the f -values i.e. g refines the pre-order induced by ϕ f . Unfortunately this is too naïve: the corresponding algorithm does not always terminate3 , a counter-example is given by Figure 6. .01

.9

.5 .5

.09 .01

.9

Figure 6: A counter-example for the naïve improvement algorithm.

If we start with the permutation f = acb, the f -strategies are as follows: in Max goes to b and in Min goes to c. Hence, the f -values of vertices a, c, and b are respectively .82, .9, and .5, so f is not self-consistent. The next permutation is g = bac, and the following g-strategies ensue: in Max goes to a and in Min goes to . The g-values of vertices b, a, and c are respectively .5, .1, and .18, so g is not self-consistent either. Moreover, the next permutation is f = acb, so the naïve algorithm oscillates endlessly between f and g, never reaching the correct permutation abc.

4.2.

A correct improvement policy. The correct permutation-improvement policy is a bit more complex: given a live but not self-consistent permutation f , we choose a permutation g which is live and self-consistent in the one-player game G[σ f ], where vertices of player Max have only one outgoing edge: the edge consistent with the positional f -strategy σ f . This improvement policy guarantees that the value of σ g is greater than the value of σ f (see Lemma 4.4) and is implemented by the following algorithm.

Input: A normalised simple stochastic game G = (V, V Max , V Min , V R , E, δ, ⊚, ⊗). Output: Optimal strategies for Max and Min. Pick a live permutation f ; Proof. According to Lemma 4.2 the algorithm returns a permutation which is both live and self-consistent in G hence according to Lemma 3.7 the corresponding permutation strategies are optimal in G which proves correctness of the algorithm.

1 repeat 2 if f is self-consistent in G then
Termination and the maximal number of iterations follows from Lemma 4.4, which proves that sucessive strategies σ f have better and better values.

The computation of a live and self-consistent permutation in G[σ f ] in line 2 is achieved in polynomial time in the following way. First, compute the values of the one-player game G[σ f ] using linear programming [START_REF] Hordijk | Linear Programming and Markov Decision Chains[END_REF][START_REF] Condon | On Algorithms for Simple Stochastic Games[END_REF]. Second, build in linear time a live permutation g consistent with these values like in the proof of Lemma 3.10. The permutation g is such that val σ f (g 1 ) ≤ val σ f (g 2 ) ≤ . . . ≤ val σ f (g k ), where val σ f denotes the values in the game

G[σ f ]. According to Proposition 4.3 the game G[σ f ] is normalised hence Proposition 3.9 guarantees that g is consistent in G[σ f ].
Let us compare briefly the permutation-enumeration and the permutation-improvement algorithms. Each improvement step of the permutation-improvement algorithm requires the computation of values of a one-player SSG, which can be performed using linear programming. These values could be computed as well using a permutation-improvement policy or a strategy-improvement algorithm in order to avoid linear programming altogether. Either way, we have to forfeit one of the advantages of the permutation-enumeration algorithm: the computational simplicity of its inner loop. On the other hand, we do not know any non-trivial lower bound on the number of loops in a run of the permutation-improvement algorithm: it may be polynomial.

∀1 ≤ i ≤ k, j>i X f [j] ⊆ j>i W f [j] . (4.1)
Thus, the liveness of f in G follows from its liveness in G[σ], and Lemma 4.2 ensues.

Proposition 4.3. Let f be a live permutation. Then G[σ f ] is normalised.

Proof. In the proof of Proposition 3.6, we have shown the existence of a positive real number α such that for any strategy τ for min and vertex

v = ⊗, P σ f ,τ v (V n = ⊚) ≥ α k hence only ⊗ has value 0 in G[σ f ]. Clearly only ⊚ has value 1 in G[σ f ] hence Proposition 4.3 follows.
4.4. Termination of the permutation-improvement algorithm. The value of a strategy σ is denoted val σ and defined by:

∀v ∈ V, val σ (v) = inf τ P σ,τ v (Reach(⊚))
. For proving termination of the permutation-improvement algorithm we prove that successive strategies σ f chosen by the algorithm have greater and greater values.

Lemma 4.4. Let f be a live permutation in G and g be a live and self-consistent permutation in G

[σ f ]. Then for all v ∈ V , val σ f (v) ≤ val σg (v) . (4.2) Moreover, if for all v ∈ V , val σg (v) = val σ f (v) then g is self-consistent in G.
Proof. A key remark in the proof of Lemma 4.4 is that:

val σ f (g 1 ) ≤ val σ f (g 2 ) ≤ . . . ≤ val σ f (g k ) . (4.3) Let ψ f ,g be the g-values in G[σ f ]. The self-consistency of g in G[σ f ] is: ψ f ,g (g 1 ) ≤ ψ f ,g (g 2 ) ≤ . . . ≤ ψ f ,g (g k ) .
Lemma 3.7 applied to G[σ f ] implies that the g-strategy of player Min in G[σ f ] is optimal in G[σ f ] hence ψ f ,g = val σ f and (4.3) follows.

Consider now the sequence (σ n ) n∈N , where σ n is the strategy where Max plays according to σ g until the pebble has visited n random vertices, and plays according to σ f afterwards. In particular σ 0 = σ f . We show that for every vertex v the sequence (val σ n (v)) n∈N is nondecreasing and that its limit is less than val σg (v). Since σ 0 = σ f this will prove Lemma (4.2).

We first show by induction that for any integer n,

∀v ∈ V, val σ n+1 (v) ≥ val σ n (v) . ( 4

.4)

Basis (n = 0): We have to prove that values of σ 1 are greater than values of σ f . Let v be a vertex, i be the index of the g-region of v in G, and j be the index of the g-region of v in G[σ f ]. As the moves of Max are restricted in G[σ f ] the definition of the g-regions gives i ≥ j and (4.3) yields: val σ f (g i ) ≥ val σ f (g j ) .

(4.5)

If Max plays with σ 1 , the definition of σ g ensures that the first random vertex belongs to {g i , g i+1 , . . . , g k , ⊚}, so val σ 1 (v) ≥ min{val σ f (g i ), val σ f (g i+1 ), . . . , val σ f (g k ), 1} and (4.3) yields: val σ 1 (v) ≥ val σ f (g i ) .

(4.6) On the other hand we prove: val σ f (v) = val σ f (g j ) .

(4.7) Let ψ f ,g denote g-values in G[σ g ]. We have already proved above that ψ f ,g is equal to val σ f . By definition of j, g j is the first random vertex in a play in G[σ f ] starting from v and consistent with a g-strategy for Min in G[σ f ] hence ψ f ,g (v) = ψ f ,g (g j ) which yields (4.7).

It follows from (4.5), (4.6), and (4.7) that (4.4) holds for n = 0. Inductive step (n ⇒ n + 1): The strategies σ n+2 and σ n+1 coincides with σ g until the first visit to a random vertex. Then σ n+2 switches to σ n+1 while σ n+1 switches to σ n . By induction hypothesis, val σ n+1 ≥ val σ n , so val σ n+2 ≥ val σ n+1 and (4.4) holds for n + 1. Now we show that for every v, lim n∈N val σ n (v) ≤ val σg (v). Let τ be a strategy for Min. We have: Let us suppose now that val σ f = val σg . Equation (4.3) yields:

val σg (g 1 ) ≤ val σg (g 2 ) ≤ . . . ≤ val σg (g k ) .

(4.11)

We can thus apply Proposition 3.9 to g in G[σ g ] which yields the self-consistency of g in G[σ g ]. By definition of g-zones, they coincide in G and G[σ g ] hence the g-values are equal in G and G[σ g ] and g is also self-consistent in G.

Conclusion

We have presented two algorithms computing optimal strategies in simple stochastic games: the permutation-enumeration and the permutation-improvement algorithms. Both of them rely on the existence of optimal permutation strategies. The permutationenumeration algorithm simply tests every permutation until it finds a live and self-consistent one. The permutation-improvement algorithm uses a smarter policy in order to choose a "better" permutation in the next round, à la Hoffman-Karp.

The permutation-enumeration algorithm has exponential worst-case complexity but it is a witness that solving SSGs is fixed-parameter tractable when the parameter is the number of random vertices. The nominal complexity of the permutation-improvement algorithm is a bit higher but we do not know any non-trivial lower bound on the number of improvement steps: the permutation-improvement algorithm may actually run in polynomial time.

Whether simple stochastic games are solvable in polynomial time remains a challenging open question.

Figure 1 :

 1 Figure 1: A Simple Stochastic Game.

Figure 3 :

 3 Figure 3: Coherence and contention.

Figure 4 :

 4 Figure 4: f -regions and f -strategies in the game of Figure 1.

  Proposition 2.2. Let f be a permutation. The f -regions and the f -strategies can be computed in time O |E| log * (|V |) and the f -values can be computed in time O |V R | 3 |δ| . Proof. The f -regions and f -strategies can be expressed in terms of deterministic games as they do not depend on what happens once a random vertex is reached. We can thus use the results of [AHMS08] to compute them in time O(|E| log * (|V |).

  Output: Optimal strategies for Max and Min. forall permutation f over V R do 1 compute the f -regions; 2 compute the f -values; 3 if f is live and self-consistent then 4 return σ f and τ f ; 5 Algorithm 1: The permutation-enumeration algorithm. Theorem 3.4. The permutation-enumeration algorithm terminates and returns optimal strategies for Max and Min. Its worst-case running time is O |V R |! • (|E| + |δ|) .

Figure 5 :

 5 Figure 5: Self-consistency does not guarantee optimality.

  is positive. Let n = |V | and k = |V R | then the definition of σ f yields:

3Algorithm 2 :

 2 return σ f and τ f ; 4 else 5 replace f with a live and self-consistent permutation in G[σ f ] ; 6 The permutation-improvement algorithm. The computation of a live and self-consistent permutation in G[σ f ] in line 2 relies on the computation of values of the one-player game G[σ f ]. Details are given in the proof of the following theorem.

  Theorem 4.1. The permutation-improvement algorithm terminates and returns optimal strategies for Max and Min in at most |V R |! improvement steps. Furthermore, each improvement step can be carried out in polynomial time.

4. 3 .

 3 Soundness and correctness of the permutation-improvement algorithm. The correctness proof is based on the following two results. Lemma 4.2. Let σ be a positional strategy for Max and f be a permutation. If f is live in G[σ] it is also live in G. Proof. Let W f and X f denote the f -regions in G and G[σ], respectively. By definition, ∪ j>i W f [j] is the deterministic attractor of Max to {f i , . . . , f k , ⊚} in G, while ∪ j>i X f [j] is the same attractor in G[σ]. As the moves of Max are restricted in G[σ], we get

  n, V m = ⊗) , = lim n P σ n ,τ v (∀m ≤ n, V m = ⊗) , 8) follows from Proposition 3.6, (4.9) holds because σ g coincides with σ n for at least n steps, and (4.10) by event inclusion and by definition of the value. This holds for every strategy τ hence val σg (v) ≥ lim n val σ n (v).Altogether, valσ f (v) = val σ 0 (v) ≤ val σ 1 (v) ≤ • • • ≤ lim n val σ n (v) ≤ val σg (v) hence (4.2), which achieves to prove the first part of the lemma.

Actually, the naïve algorithm terminates (and is correct) in the special case of one-player games[START_REF] Horn | Random Games[END_REF].

Acknowledgements We would like to thank Marcin Jurdziński for some fruitful discussions, the anonymous reviewers for several useful suggestions and Julien Cristau for his invaluable comments during the writing of the final version.

This research was partially supported by the french project ANR "DOTS". The second author held the tenure of an ERCIM "Alain Bensoussan" fellowship programme.


K Karrame

A Jakani

N L A Kakou

C Chang

M Colas

J C Nallatamby

R Sommet

Thermal Simulation and Characterization of GaN HEMT using Gate Resistance Thermometry and Thermoreflectance imaging

Keywords: GaN HEMT, Gate Resistance Thermometry, Thermoreflectance, temperature, FEM thermal simulation, 10W/mm

Two electrical methods and one optical method are used, in order to measure the temperature of the hot spot of a 150nm, 2x150µm GaN HEMT. One of the electrical methods is based on Gate Resistance Thermometry (GTR) [1] and the other one is based on the On State resistance Ron obtained from Id(Vgs,Vds) drain current characterization [2]. The optical one uses the reflectivity variation principle to measure the surface temperature and is based on CCD-thermoreflectance [3]. The measurement results are supported by nonlinear simulation, using Finite Element Method (FEM). The use of the GTR electrical method allows a characterization of the temperature along the gates close to the hot spot region and averages the temperature over the gate width. This method demonstrates a relative linearity in the variation of thermal resistance as function of the applied power dissipation and notably a higher thermal resistance value compared to the conventional way of RON extraction. We may notice that with the On State resistance, the average is realized over the Source-Drain length. The optical method based on the ThermoReflectance (TR) allows a measurement of the surface temperature of the component at the hot spot. The values obtained are consistent with those found by electrical methods and FEM simulation up to 10W/mm.

I. INTRODUCTION

In recent years, the advancement of applications based on the use of GaN HEMT transistors has allowed to obtain power performances in several fields of activity. However, these components are subjected to high power densities which induce high temperatures affecting their reliability and degrading their electrical performances. Thus, the thermal study of these power components becomes critical. In this paper, thermal simulations as well as thermal characterization by several methods are performed and compared in order to extract the temperature of the device and thermal resistance

II ELECTRICAL MEASUREMENTS OF THERMAL RESISTANCE

In order to measure the temperature of the UMS 2x150µm GaN HEMT two different electrical methods are used. The "Ron method" involves two steps: (a) calibration step and (b) measurement step. The detailed procedure of this measurement technique can be found in [START_REF] Sommet | Thermal modeling and measurements of AlGaN/GaN HEMTs including thermal boundary resistance[END_REF]. The second method involves the calibration of the gate [START_REF] Pavlidis | Characterization of AlGaN/GaN HEMTs Using Gate Resistance Thermometry[END_REF].

II.1. Rth measurement using RON calibration method

The first step (Temperature calibration) is used to express the device on-state resistance (RON) as a function of the temperature; this temperature is provided extrinsically by a thermal chuck on which the Device Under Test (DUT) is placed. The calibration is performed by varying the temperature of the thermal chuck, typically up to 125°C for a quiescent bias point (Vgs = Vds = 0V). The RON value is extracted from the linear region of the device characteristics using pulsed I(V) measurement for various chuck temperatures. Figure 1 shows that the extracted resistance RON increases linearly with temperature:

𝑅 𝑂𝑁 = 𝑎 𝑇 . ∆𝑇 + 𝑏 (1)
The second step (Power measurement) is used to express RON as a function of the power dissipation. It can be obtained by applying different drain biasing conditionsVDS0 for VGS0 = 0V.

With: 𝑏 = 𝑅 𝑂𝑁 at 𝑇 = 𝑇 0 or 𝑃 𝑑𝑖𝑠𝑠 = 0 𝑊

The thermal resistance can be obtained using "Thermal Ohm's Law" as the ratio of the slope coefficients of ( 1) and ( 2)

𝑅 𝑡ℎ = ∆ 𝑇 𝑃 𝑑𝑖𝑠𝑠 = 𝑎 𝑝 𝑎 𝑇 (4)
Note that the thermal resistance is a constant value and the extracted thermal resistance is 𝑅 𝑡ℎ = 39.8°𝐶/𝑊

II.2. Rth measurement using Gate Resistance Thermometry

The special interest of the transistor used in this experiment relies on the fact that the gates are connected on both side as shown in Figure 7 b) and can be used as a temperature sensor. The two terminals of the gate are set to a small difference of electrical potentials allowing a small current flow to take place between them. The gate resistance can be deduced and its variation with the temperature can be monitored. The first assumption is that the signal injected in the gate probe resistance is negligeable to increase the temperature of the device. The first step consists in a calibration of the resistance of the gate versus temperature provided by the thermal chuck. No dissipated power is applied, and the drain is grounded. This calibration curve is shown in Figure 3 and exhibits that the gate resistance increases linearly with the temperature of the thermal chuck and can be expressed by:

𝑅 𝑔 = 𝑎 𝑇 . ∆𝑇 + 𝑏 (5)
where 𝑎 𝑇 = 0.00347 and b = 11.47. These values are consistent with a gate metal temperature coefficient around 3.4E-4 corresponding to the ratio 𝑎 𝑇 /𝑏 and mainly due to Au metal.

The second step consists of expressing Rg as a function of the different dissipated powers applied in the channel thanks to different DC drain biasing voltages Vds. The dissipated power in the channel creates an increase of the temperature of the channel. This thermal energy is then transferred to the rest of the transistor by conduction and notably to the gates. Measurements show in Figure 4 that the gate resistance Rg is a quadratic function of the dissipated power. The Rg resistance can therefore be expressed as a function of power as follows:

𝑅 𝑔 (𝑃 𝑑𝑖𝑠𝑠 ) = 𝑎 2 𝑃 𝑑𝑖𝑠𝑠 2 + 𝑎 3 𝑃 𝑑𝑖𝑠𝑠 + 𝑏 (6)
From ( 5) and ( 6), it is possible to express the temperature rise also as a quadratic function of power dissipation:

∆𝑇 = 𝑎 2 𝑎 𝑇 𝑃 𝑑𝑖𝑠𝑠 ² + 𝑎 3 𝑎 𝑇 𝑃 𝑑𝑖𝑠𝑠 (7)
Thermal resistance can be expressed, according to "Ohm's Law" for Thermal Resistance, in terms of temperature difference and power dissipation using the following form: The measurements show that the thermal resistance is not constant and varies according to the dissipated power (Figure 5), it can be expressed as: The temperature is maximum in the channel below the gate on the drain side because the electric field is the most intense in this area (Figure 6), using the gates as a temperature sensor allows for a more accurate temperature measurement. Finally, the temperature averaged along the gates can be expressed according to the following equation:

𝑅 𝑡ℎ = 𝑎 2 𝑎 𝑇 𝑃 𝑑𝑖𝑠𝑠 + 𝑎 3 𝑎 𝑇 (9)
𝑇 = 𝑎 2 𝑎 𝑇 𝑃 𝑑𝑖𝑠𝑠 2 + 𝑎 3 𝑎 𝑇 𝑃 𝑑𝑖𝑠𝑠 + 𝑇 0 (10)

III. OPTICAL MEASUREMENT BY THERMOREFLECTANCE OF THERMAL RESISTANCE

The reflectivity of the material varies with the variation of its temperature [START_REF] Kendig | UV Thermal Imaging of RF GaN Devices with GaN Resistor Validation[END_REF], so it is possible to express the relationship between the relative change in reflectance (ΔR/R0) and the surface temperature by:

𝛥𝑅 𝑅 0 = 𝐶 𝑡ℎ . 𝛥𝑇 (14)
The coefficient 𝐶 𝑡ℎ depends on the surface of the material and the wavelength of the excitation LED. This coefficient is obtained during calibration by placing the transistor on a thermal stage. The reflectance is measured for two different temperatures 25°C and 100°C respectively. It is important to select the optimum wavelength that gives the highest 𝐶 𝑡ℎ value for a better measurement sensitivity.

III. 1. CALIBRATION

Considering the SiN passivation layer, a near UV wavelength of 365 nm is used to measure the temperature on the AlGaN layer through the SiN layer as close as possible to the hot spot. The TR coefficient measured through the calibration process is 𝐶 𝑡ℎ = -3𝑥10 -3 ± 1𝑥10 -5 °𝐶-1 for λ=365nm

III. 2. MEASUREMENTS

A steady state measurement has been performed for several dissipated powers near the gates between the two air bridges as shown in Figure 7 with the TR and CCD images of the 2x150µm transistor, illustrating the hot spot regions of the device. The results are similar to those obtained by GTR method which exhibit a variable thermal resistance versus dissipated power.

IV. NUMERICAL SIMULATION

A finite element thermal simulation using Salome-Meca software is performed in order to validate the measurement results. The nonlinear properties of materials are taken into consideration. Table 1 The device structure of a 2x150µm is considered symmetric with respect to X-axis and Y-Axis and therefore only the quarter of the device structure is used for the simulation. Meshing the device structure is an important aspect of device simulations. The mesh density should be fine in the device areas where the temperature and heat flux vary rapidly (99282 surface elements and 531342 volume elements).

VI. CONCLUSION

The temperature of a 150nm, 2x150µm GaN HEMT has been determined by several measurement methods including Ron thermometry, Gate Resistance Thermometry, Thermoreflectance imaging as well as FEM simulation for a power density up to 10W/mm. The RON method exhibits a constant thermal resistance of 40°C/W leading to a linear variation of temperature versus dissipated power. The other methods or the FEM simulation provide very close results even at high dissipated power. The break in the slope of the thermoreflectance results may be due to the calibration of thermoreflectance coefficient Cth performed only between 25°C and 100°C which is probably not sufficient to reach the best accuracy in the temperature determination at very high temperature and moreover for a semiconductor material.

Figure 1 :

 1 Figure 1 : On-state resistance RON vs thermal Chuck temperature The extracted RON, is a linear function of the dissipated power (Figure 2), and it can be expressed in the following form:

Figure 3 :

 3 Figure 3 : Gates resistor vs thermal chuck temperature

Figure 4 :

 4 Figure 4 : Gate resistor vs dissipated power

Figure 5 :

 5 Figure 5 : Rth vs dissipated power

Figure 6 :

 6 Figure 6 : Simplified structure of GaN HEMT transistor showing measurement spots and respective wavelengths used.

Figure 7 Figure 8 :

 78 Figure 7. a) TR image showing hot areas b) CCD camera image during measurement

Figure 9 .

 9 Figure 9. Quarter of the simplified geometry of the transistor The boundary conditions are: an initial temperature of 25 ℃, imposed at the baseplate of the SiC material, a surface heat flux density 𝜑 applied to the hot spot (Figure 9) described as: 𝜑 = (𝑘(𝑇)𝛻𝑇) • 𝑛 ⃗ = 𝑃 𝐷𝐼𝑆𝑆 4•𝑆 𝑔

Figure 10 .

 10 Figure 10. Comparison of the different temperature results

Table 1 .

 1 shows the equation used to define the thermal response of the different materials used in this work. Material properties[START_REF] Amar | Electrothermal Reliability of the High Electron Mobility Transistor (HEMT)[END_REF]

		𝑘(𝑇) = 𝑘 300 • (	𝑇 300	)	-𝛼	(15)
	Material	𝜌 (kg/𝑚 3 )	𝐶 𝑝 (J/kg/K)	𝑘 300 (W/m/K)	𝛼
	Au	19300	137	310	-
	GaN	6100	490	160	1.45
	SiC	3220	690	340	1.5
	Nucleation_Layer	6100	490	6.7	2.7

ACKNOWLEDGEMENT

The authors would like to acknowledge the financial support from Labex/Sigma-Lim and TAS company.


P Vigneshwara Raja

Jean-Christophe Nallatamby

Mohamed Bouslama

Jean Claude Jacquet

Raphael Sommet

Christophe Chang

Benoit Lambert

HTRB Stress Effects on 0.15 µm AlGaN/GaN HEMT Performance

Keywords: AlGaN/GaN HEMT, trap, gate leakage, HTRB, power drift, reliability

This paper describes the high temperature reverse bias (HTRB) stress effects on 0.15 µm AlGaN/GaN high-electron mobility transistors (HEMTs) with Fe-doped buffer. The HEMTs were stressed to OFF-state bias (VGS = -7 V, VDS = 25 V) at 175 °C for 1000 hours of duration. The subsequent degradation in the drain current is analyzed. The changes in IG-VG at VDS = 0 V (emulating gate Schottky diode leakage) are investigated before and after the stress to inspect the Schottky gate interface quality. The gate leakage current evolutions are further examined with the VG and VD sweeps. After ageing test, the deviation in the emission rate of Fe-related trap at EC -0.5 eV (located in buffer) is quantified by means of low-frequency (LF) output-admittance (Y22) and drain current transient (DCT) spectroscopy. Moreover, the drift in the output power (Pout) during first interim measurement of stressed HEMT is evaluated, with the supporting TCAD simulations. These preliminary HTRB test results are useful to understand the fundamental failure mechanisms of the HEMT due to the ageing in actual operating conditions.

I. INTRODUCTION

The ultra-submicrometer AlGaN/GaN HEMT technologies have proved effective for monolithic microwave integrated circuit (MMIC) and RF power amplifier (RFPA) applications. Nevertheless, the long-term reliability of the HEMT still needs further improvement for extending their operational lifetime. Before delivering the product to the market, the performance and reliability of the HEMT must be thoroughly checked to verify if the device will sustain the real-world environmental stresses and remain to meet the future demands [START_REF] Trew | AlGaN/GaN HFET reliability[END_REF]. The accelerated bias ageing test such as high temperature reverse bias (HTRB) encompasses elevated temperature storage and high gate-drain reverse bias to aggravate the various device failure modes with Arrhenius acceleration factor, thus meantime-to-failure (MTTF) of the device may be anticipated [START_REF] Trew | AlGaN/GaN HFET reliability[END_REF], [START_REF] Alamo | GaN HEMT reliability[END_REF]. These reliability studies are useful to identity the root cause of the degradation mechanisms and some hidden failures modes, thereby allowing us to prevent those device failures. Moreover, certain application areas of the HEMT require high power and temperature operation. Therefore, this work is focused on HTRB stress effects on the state-of-the-art 0.15 µm AlGaN/GaN HEMT characteristics.

The high gate leakage current of the gate Schottky contact is an important factor in affecting standby power dissipation, gate voltage swing and device reliability [START_REF] Alamo | GaN HEMT reliability[END_REF], [START_REF] Debnath | Charge-based compact model of gate leakage current for AlInN/GaN and AlGaN/GaN HEMTs[END_REF]. So, a special emphasis is devoted to investigate the HTRB induced changes in the gate current. Particularly, the gate leakage current is analyzed at VDS = 0 V condition (imitating gate Schottky diode) to inspect the metal/GaN/AlGaN/GaN Schottky interface properties, in relative to the pre-stress condition. The electron trapping in the HEMT due to the deep-level traps in the buffer layer reduces the maximum achievable performance during the dynamic operation [START_REF] Raja | Identification of buffer and surface traps in Fe-doped AlGaN/GaN HEMTs using Y21 frequency dispersion properties[END_REF]. The electrically active traps may also promote the gate-leakage current conductions through trapassisted tunneling and Poole-Frenkel emission [START_REF] Debnath | Charge-based compact model of gate leakage current for AlInN/GaN and AlGaN/GaN HEMTs[END_REF]. So, lowfrequency (LF) output-admittance (Y22) and drain current transient (DCT) characterizations are performed to evaluate the emission time constant evolutions of the Fe-related acceptor trap at EC -0.5 eV upon the ageing test. Moreover, the drop in the output power (Pout) during the first interim measurement of stressed HEMT is inspected by using supporting TCAD simulations. So, these preliminary HTRB test studies are expected to provide a fundamental understanding of the HEMT failure mechanisms due to aging in actual operating conditions.

II. EXPERIMENT

The studied AlGaN/GaN HEMT structure incorporates Fedoped GaN buffer layer grown on silicon carbide substrate, followed by AlGaN barrier layer, and GaN cap layer. The HEMT features ultra-short gate length of 0.15 µm with a gate width of 4×50 µm, nitride passivation layer at ungated surface and source terminated field plate configuration.

The HTRB stress tests were performed at IMS from University of Bordeaux and UMS by Florent Magnier [START_REF] Magnier | Investigation of trap induced power drift on 0.15 μm GaN technology after aging tests[END_REF]. The HEMTs were stressed to a higher reverse gate-drain bias voltage of VGS = -7 V and VDS = 25 V (VGD = -32 V) at an elevated temperature of 175 °C for a longer time duration of 1000 hours. Subsequently, the HTRB induced changes in the HEMT properties are analyzed.

The drain current and gate leakage current of the HEMT were measured before and after the stress test by using Agilent B1500A Semiconductor device parameter analyzer. The experimental step for LF Y22 and DCT is given elsewhere [START_REF] Raja | Identification of buffer and surface traps in Fe-doped AlGaN/GaN HEMTs using Y21 frequency dispersion properties[END_REF]. After ageing test, the Y22 parameters were acquired at the same bias point of VDSQ = 10 V and IDSQ = 50 mA/mm in the frequency range of 100 Hz to 1 MHz for different temperatures 25 °C to 125 °C. In DCT spectroscopy, drain-lag pulsing scheme (VDS switched from 10V to 20 V for 100 ms pulse width) was employed to populate the traps in the HEMT. Then VDS was reverted to its initial bias point (VDM = 10 V) and the emission transient was measured over 1 µs to 1 s for the temperatures ranging from 25 °C to 125 °C. The output power of stressed HEMT was measured at VDS = 20 V and IDS = 200 mA/mm at 5dB gain compression to evaluate the power drift.

III. RESULTS AND DISCUSSION

A. Drain Current Characteristics

B. Gate Leakage Current

To analyze the gate Schottky diode interface properties, gate current (IG) behavior is inspected at VDS = 0 V bias condition. The unstressed HEMT characteristics are discussed first. The forward IG-VG at VDS = 0 V obtained for various temperatures (25 °C to 125 °C) are shown in Fig. 2. Three different regions of current transport mechanisms are identified in the forward IG-VG. As the diode saturation current may only govern the current transport in Region-1, nearly constant and low current (< 10 pA) is observed. Beyond that, two linear regions (2 and 3) with different slopes are noticed in forward IG-VG, implying that the gate Schottky interface comprises of two diodes positioned in a back-to-back series arrangement [START_REF] Greco | Temperature dependent forward current-voltage characteristics of Ni/Au Schottky contacts on AlGaN/GaN heterostructures described by a two diodes model[END_REF]. Using thermionic emission model, Schottky barrier height (SBH) for the twodiode model (at 25 °C) is extracted as 1.15 eV (SBH-1) and 0.72 eV (SBH-2), respectively. The ideality factor (n) for the twodiodes is found to be 1.66 (n1) and 4.36 (n2) at 25 °C. The two-diode model suggests [START_REF] Greco | Temperature dependent forward current-voltage characteristics of Ni/Au Schottky contacts on AlGaN/GaN heterostructures described by a two diodes model[END_REF] that the first diode is associated with the typical metal/GaN cap interface. While the second diode may be related with the AlGaN/GaN interface. In this case, the Schottky barrier height (SBH-2) indicates the energy difference between the Fermi level of AlGaN/GaN 2DEG and the GaN conduction band. On the other hand, the second-diode parameters such as SBH2 (0.72-0.71 eV) and n2 (4.36-4.79) have shown a weak temperature dependency. After the ageing test, the forward IG is decreased (see Fig. 2), due to the mobility degradation and the corresponding increase in the SBHs, as observed from Fig. 3(a).

The temperature dependent reverse IG-VG (VDS = 0 V) properties demonstrate three different regions of operation, as represented in Fig. 2. In Region-4, only due to the reverse saturation current conduction, the leakage current is found to be very low (≤ 10 -13 A). The possible current transport mechanism in Region-5 is the Poole-Frenkel emission model, viz. fieldassisted emission of electrons from a trap near the metal/semiconductor interface to the continuum states corresponds to the conductive dislocations in the barrier layer [START_REF] Debnath | Charge-based compact model of gate leakage current for AlInN/GaN and AlGaN/GaN HEMTs[END_REF]. In Region-6, the reverse gate current is governed through the Fowler-Nordheim tunneling as identified from the curve fitting of the experimental data. In many reports [START_REF] Debnath | Charge-based compact model of gate leakage current for AlInN/GaN and AlGaN/GaN HEMTs[END_REF], [START_REF] Yan | On the reverse gate leakage current of AlGaN/GaN high electron mobility transistors[END_REF], the electric field variation was considered to be constant beyond the threshold voltage (< VTH) because of the depletion of 2DEG under the gate. In contrary, it is noticed from Fig. 2 that the leakage current increases rapidly beyond VTH due to the increase in the surface potential, as similar to the observations of Ghosh et al. [START_REF] Ghosh | Physics based modeling of gate current including fowler-nordheim tunneling in GaN HEMT[END_REF]. Therefore, the electric field profile computed from the TCAD simulation is used for the curve fitting analysis. The reverse IG-VG of the unstressed and stressed HEMT is also illustrated in Fig. 2; only a slight change in the gate leakage current at VDS = 0 V is noted after the ageing test. Hence, the gate Schottky interface quality is not much affected after the HTRB test carried out for 1000 hours. It is clear that IG increases with respect to VG for different VDS upon on the ageing test. Particularly, the augmentation is more pronounced at higher VDS values. The gate current versus drain voltage properties for different VG (-2 V to -4 V) are considerably increased in the stressed HEMTs, as illustrated in Fig. 4(b). It is hypothesized that the HTRB stress may induce leakage current paths through the creation of defects in the barrier layer [START_REF] Alamo | GaN HEMT reliability[END_REF]. Thus, IG is increased after HTRB stress, except for the case of IG-VG at VDS = 0 V.

C. Y22 and DCT Spectroscopy

Figure 5 depicts the LF Y22 parameters of the Fe-doped AlGaN/GaN HEMT measured before and after the ageing test for different temperatures (25 °C to 125 °C). Prior to the stress test, Arrhenius analysis of the Y22 frequency dispersion yields the activation energy of 0.47 eV. The emission rate of the trap [START_REF] Raja | Identification of buffer and surface traps in Fe-doped AlGaN/GaN HEMTs using Y21 frequency dispersion properties[END_REF] is reduced at each temperature upon the stress, as shown in Fig. 5. Accordingly, small increase in the activation energy (0.49 eV) is obtained from the post-stress experiment. This suggests that the potential barrier for the electron emission from the trap level is bit increased upon the ageing, as a result slightly higher thermal activation energy is computed for the Fe-related acceptor trap in the buffer [START_REF] Raja | Identification of buffer and surface traps in Fe-doped AlGaN/GaN HEMTs using Y21 frequency dispersion properties[END_REF]. Fig. 6(a) shows the DCT spectroscopy of the unstressed and stressed Fe-doped AlGaN/GaN HEMTs in the temperature range of 25 °C to 125 °C and their corresponding DCT derivative spectra are plotted in Fig. 6(b). From DCT spectroscopy, small increase in the emission time constant is noted after the stress experiments. However, almost the same activation energy is attained for both the unstressed (0.5 eV) and stressed (0.51 eV) HEMT. One point is evident that the emission time constant of the trap increases after the HTRB stress test.

D. Output Power Drift

Figure 7 shows the variation in the output power (Pout) during the first interim measurement for an unstressed HEMT and two stressed HEMT (A and B) devices. The output power is found to decline (power drift) with time in stressed HEMTs, which can degrade the RF and microwave performance of the HEMT.

There is no considerable change in Pout for the unstressed HEMT. To determine the possible physical mechanism behind the power drift, TCAD simulations are carried out by introducing acceptor trap at EC -0.53 eV / EC -0.73 eV / EC -0.93 eV in the barrier layer at different location (gate-source region / under gate / gate-drain region). Figure 8 demonstrates the knee-voltage smoothing in the simulated output characteristics after including acceptor trap under gate and in gate-drain region of the barrier layer. The knee-voltage smoothing is not observed by placing the trap in the following locations: (1) source-gate region of barrier layer and (2) any location in buffer region. These observations reveal that the OFF-state electrical and thermal stresses may create defects under gate and in gate-drain region of barrier layer [START_REF] Alamo | GaN HEMT reliability[END_REF], [START_REF] Magnier | Investigation of trap induced power drift on 0.15 μm GaN technology after aging tests[END_REF], thereby smoothing the IDS during the transition between linear and saturation region of output characteristics. This phenomenon causes power drift in the stressed HEMTs.

IV. CONCLUSION

The HTRB stress effects on the Fe-doped AlGaN/GaN HEMT are reported. The output and transfer drain current characteristics of the HEMT are degraded upon the ageing test. The forward IG-VG at VDS = 0 shows that the gate Schottky interface comprises of two diodes positioned in a back-to-back arrangement. The IG-VG at VDS = 0 is not affected much after the HTRB test, indicating that the quality of the gate Schottky interface is retained. However, IG increases with further variation in the gate and drain voltages. The emission rate of the Fe-related acceptor trap at EC -0.5 eV is decreased after the stress experiment, as observed from the LF Y22 and DCT. The output power drift is observed during first interim experiment of stressed HEMTs may be due to the creation of defects under gate and in gate-drain region of the barrier layer.

Figures 1 (

 1 Figures 1(a) and 1(b) show the output (IDS-VDS) and transfer (IDS-VGS) characteristics (at T = 25 °C) of the AlGaN/GaN HEMT before and after the HTRB stress. The drain current (IDS), magnitude of the threshold voltage |VTH| (positive shift in VTH)and transconductance (gm) are reduced after the HTRB test, due to the possible degradation in the 2DEG density (ns) and mobility (µs)[START_REF] Gu | Temperaturedependent dynamic degradation of carbon-doped GaN HEMTs[END_REF] caused by the thermally accelerated ageing (with Arrhenius rate) and the OFF-state electrical stress effects. As a result, the on-resistance (RON) of the HEMT increases after the stress experiment, as identified from the linear region of the IDS-VDS properties. Overall, the current driving capability of the HEMT is deteriorated upon the ageing test.

Fig. 1 .

 1 Fig. 1. (a) Output (IDS-VDS) and (b) transfer (IDS-VGS) characteristics of the AlGaN/GaN HEMT before and after the HTRB stress test.

Fig. 2 .

 2 Fig. 2. Temperature dependent (25 °C to 125 °C) IG-VG properties at VDS = 0 V of the unstressed and stressed HEMTs, show three different regions of current transport mechanisms on either direction.

Fig. 3 .

 3 Fig. 3. Temperature dependence of Schottky barrier height (SBH) and ideality factor (n) extracted from thermionic emission theory for the two-diode model, before and after the stress. The temperature dependence (25 °C to 125 °C) of SBH and n for the two-diode model is plotted in the Figs. 3 (a) and (b). It is perceived that the SBH-1 (1.15 eV to 1.26 eV) increases and n1 (1.66 to 1.4) decreases with the increasing temperature (opposite to the expected variation); this behavior can be attributed to the inhomogeneous Schottky barrier at metal/semiconductor interface on the AlGaN/GaN structure.On the other hand, the second-diode parameters such as SBH2 (0.72-0.71 eV) and n2 (4.36-4.79) have shown a weak temperature dependency. After the ageing test, the forward IG is decreased (see Fig.2), due to the mobility degradation and the corresponding increase in the SBHs, as observed from Fig.3(a).The temperature dependent reverse IG-VG (VDS = 0 V) properties demonstrate three different regions of operation, as represented in Fig.2. In Region-4, only due to the reverse

Fig. 4 .

 4 Fig. 4. (a) IG-VG for various drain voltages of 6 V, 8 V and 10 V and (b) gate current vs. drain voltage for different VG (-2 V, -3 V, -4 V) for unstressed and stressed HEMTs at 25 °C.

Figure 4 (

 4 Figure 4(a) shows the HTRB stress induced changes in IG-VG characteristics for various drain voltages (6 V to 10 V) at 25 °C.It is clear that IG increases with respect to VG for different VDS upon on the ageing test. Particularly, the augmentation is more pronounced at higher VDS values. The gate current versus drain voltage properties for different VG (-2 V to -4 V) are considerably increased in the stressed HEMTs, as illustrated in Fig.4(b). It is hypothesized that the HTRB stress may induce leakage current paths through the creation of defects in the barrier layer[START_REF] Alamo | GaN HEMT reliability[END_REF]. Thus, IG is increased after HTRB stress, except for the case of IG-VG at VDS = 0 V.

Fig. 5 .

 5 Fig. 5. LF Y22 parameters of the HEMT measured before and after the HTRB stress test at different temperatures (25 °C to 125 °C).

Fig. 6 (

 6 Fig. 6(a). DCT spectroscopy of the unstressed and stressed Fe-doped AlGaN/GaN HEMTs in the temperature range of 25 °C to 125 °C and (b) their corresponding DCT derivative spectra.

Fig. 7 .

 7 Fig. 7. Output power (at 5 dB gain compression) variation during first interim measurement of unstressed and two stressed HEMTs.

Fig. 8 .

 8 Fig. 8. Identification of knee-voltage smoothing in simulated output characteristics after including acceptor trap at EC -0.53 eV / EC -0.73 eV / EC -0.93 eV under gate and in gate-drain region of barrier layer.

ACKNOWLEDGMENT

The authors would like to thank Dr. F. Magnier for useful discussions and HTRB stress tests. We greatly appreciate and acknowledge the Agence Nationale de la Recherche (ANR) and Direction Générale de l'Armement (DGA) project contributors, France for funding under contract ANR-17-ASTR-0007-01 (COMPACT project).


Christin Laschke
email: laschke@leibniz-ipn.de

Victoria Shure
email: victoria.shure@hu-berlin.de

Birte Pöhler

Bettina Rösken-Winter
email: bettina-roesken-winter@hu-berlin.de

Facilitator practices during PD courses in response to teacher orientations for supporting at-risk students

Keywords: Professional development, facilitator practices, teacher orientations

The orientations that teachers possess impact their instructional decisions. Accordingly, PD facilitators need to be able to identify and respond to these orientations, especially when teachers demonstrate orientations contradictory to PD principles. Facilitators are thus faced with the challenge of balancing PD content goals and atmospheric goals. We first examine teacher orientations at the beginning of a PD. Second, as facilitators' situative goals and orientations become apparent in facilitators' practices, we examine facilitators' practices applied in response to teachers' orientations. Results reflect previous evidence of teachers' procedural, syllabus bound, short-term, and individual orientations. Our research furthermore revealed various practices facilitators use to respond to teachers' various orientations such as confirming teachers' statements, implicitly and explicitly referring to PD principles, and using examples from their own lives or instruction.

Introduction

Teacher orientations are crucial for instructional decisions in the classroom. Thus, if teachers view, for example, mathematical proficiency as implementing different mathematical procedures, they will highlight different instructional goals in comparison to teachers who accentuate conceptual understanding (e.g. [START_REF] Schoenfeld | Toward professional development for teachers grounded in a theory of decision making[END_REF][START_REF] Zohar | Higher order thinking skills and low-achieving students: Are they mutually exclusive[END_REF]. In the PD program Mastering Math, which represents the context of our study, the focus centers on fostering teachers' ability to enhance at-risk students' understanding of mathematical concepts. As orientations such as diagnostic, conceptual, long-term and communicative were identified as decisive to enhance at-risk students' understanding [START_REF] Prediger | Conducting PD discussions on language repertoires: A case study on facilitators' practices[END_REF], these are the focus of the PD. Accordingly, the facilitators need to identify what orientations teachers possess and consider how they can respond in order to move forward towards the content goal of the PD. In the theory section, we first elaborate on teacher orientations for supporting at-risk students and, second, on goals and orientations as part of facilitator practices. In the empirical part of the paper, we present data from three PD courses to scrutinize teacher orientations and patterns of facilitator practices in response to these orientations.

Teacher orientations for supporting at-risk students

Teacher orientations can have consequences for supporting at-risk students, especially in building conceptual understanding. In expanding upon prior conceptualization of orientations, for instance by [START_REF] Schoenfeld | Toward professional development for teachers grounded in a theory of decision making[END_REF], [START_REF] Prediger | Investigating and promotion teachers' expertise for language-responsive mathematics teaching[END_REF] created a framework of mathematics teacher expertise that includes orientations as one of five facets: "Orientations refer to content-related and more general beliefs that implicitly or explicitly guide the teachers' perceptions and prioritisations of jobs" (p. 370). Evidence on teacher orientations and practices connected to at-risk students, revealed that teachers often focus on assisting students in developing procedural knowledge and less so on constructing conceptual knowledge (Beswick, 2007;[START_REF] Wilhelm | Examining relations between teachers' explanations of sources of students' difficulty in mathematics and students' opportunities to learn[END_REF][START_REF] Zohar | Teachers' beliefs about low-achieving students and higher order thinking[END_REF]. Furthermore, teachers tend to base requirements on those dictated by the school syllabus, highlight short-term mastery instead of working toward long-term goals (Moser Opitz, 2007;[START_REF] Prediger | Design research with a focus on content-specific professionalization processes: the case of noticing students' potentials[END_REF], and emphasize individual student issues [START_REF] Krähenmann | Inclusive mathematics instruction: A conceptual framework and selected research results of a video study[END_REF] as opposed to rich discourse including all students and their products [START_REF] Karsenty | Exploring informal mathematical products of low achievers at the secondary school level[END_REF]. According to these results, the following contrasting orientations can be used to identify the practices teachers show to support at-risk students' understanding: diagnostic or syllabus-bound orientation; conceptual or procedural orientation; longterm or short-term orientation; and communicative or individualistic orientation. Thereby, empirical studies identified orientations based on a diagnostic, conceptual, long-term and communicative approach as supportive to enhance at-risk students understanding [START_REF] Prediger | Conducting PD discussions on language repertoires: A case study on facilitators' practices[END_REF].

Goals and orientations as part of facilitator practices

In terms of what (novice) PD facilitators need to know and do to be able to provide successful PD programs for mathematics teachers, researchers have increasingly examined what constitutes necessary PD facilitator knowledge and practices [START_REF] Borko | Examining novice teacher leaders facilitation of mathematics professional development[END_REF][START_REF] Lesseig | Leader noticing of facilitation in videocases of mathematics professional development[END_REF]. In view of diagnostic, conceptual, long-term and communicative orientations as the basis for the PD guiding principles and forming the content goals of the PD within the context of Mastering Math, the facilitators need to deal with diverse teacher orientations while targeting these PD content goals. Whether the PD content goal is reached depends on the practices that are "recurrent patterns of a facilitator's utterances and actions" [START_REF] Prediger | Conceptualizing content-related PD facilitator expertise[END_REF] when conducting a PD. Practices are characterized by pedagogical tools facilitators use such as PD activities and their categories for noticing and thinking that can be based on the content knowledge and pedagogical content knowledge facilitators bring to the PD. Furthermore, the situative goals facilitators pursue, such as content goals or atmospheric goals, depend on facilitators' orientations, such as goal orientation, participant orientation, or esteem for participants, and are part of facilitators' practices [START_REF] Prediger | Conceptualizing content-related PD facilitator expertise[END_REF]. According to prior case studies on facilitators' practices in a PD, situations can occur that let different goals compete with one another and challenge facilitators to navigate between them or turn from one to another [START_REF] Prediger | Conducting PD discussions on language repertoires: A case study on facilitators' practices[END_REF]. In the light of the PD program Mastering Math, facilitators may be faced with such a situation, in that teachers show orientations contradictory to the PD guiding principles (for example a procedural instead of a conceptual orientation), challenging facilitators to balance content goals and atmospheric goals. As facilitators' situative goals and orientations become apparent in facilitators' practices, we examine the practices applied in response to teacher orientations and the patterns of practices facilitators show. Against the aforementioned theoretical background, we pursue the following research questions: RQ1: What orientations for supporting at-risk students do teachers show during PD courses related to this topic? RQ2: What practices do the PD facilitators apply to respond to teachers' orientations? RQ3: What patterns of facilitator practices and underlying situative goals can be detected?

Methodology Participants

Three PD groups (PD 1: N=17, PD 2: N=10; PD 3: N= 9) of the Mastering Math PD program participated in the study. The participating teachers possess different mathematical or nonmathematical backgrounds and different experiences in teaching primary students, as some attended a primary teacher education program and completed their internship, and some are teaching out-offield. For each of the three PD groups, two PD facilitators were responsible to conduct the PD as a tandem. The facilitators are teachers themselves, and teach mathematics either in primary or secondary school. They also draw on different teaching experiences and various educational backgrounds, ranging from primary teacher education programs including an internship, to a major in mathematics or in special education. All facilitators received the same preparation to conduct the PD, then provided similar PD content and used similar methods.

Data collection and analysis

Within each PD group, a group discussion was conducted, videotaped and transcribed. Within this PD activity, teachers were asked to situate themselves in relation to the juxtaposition of all orientations (for example "It is important for at-risk students to find out if they have mastered basic arithmetic skills" for procedural orientation, or "It is important for at-risk students to find out if they have understood basic concepts and representations" for conceptual orientation).

As a first step, the individual teacher utterances were analyzed utilizing a coding system with the aforementioned teacher orientations for supporting at-risk students (see table 1) following a deductive approach. The transcripts were coded by two experts in the field of mathematics education. Intercoder-reliability over all groups showed sufficient consistency (Kappa=0.98) (McHugh, 2012). Absolute and relative frequencies are reported to quantify the orientations. As a second step, all statements of facilitators in response to teachers' statements were coded by two researchers, using an inductive approach. First, the two researches coded the transcript of PD group 1 independently. Second, the identified categories where discussed and revised, resulting in codes seen in the first column of Table 2. Third, the transcripts of the three PD groups were coded, according to the intercoder-reliability with a sufficient consistency (PD group 1: Kappa=1,0; PD group 2: Kappa=0.89, PD group 3: Kappa=0.93) (McHugh, 2012). Additionally, we coded the facilitators' practices in response to the teacher orientations and report absolute frequencies. An inductive approach was used and resulted in four categories (see first column of Table 3, applied by two coders who fully agreed).

Results

According to the analysis of teacher orientations that were visible in the group discussions in the three PDs (RQ1), some teachers had, to an extent, internalized some of the guiding principles of the PD program (see the green marked orientations), including supporting conceptual learning, focusing on long-term mastery, and establishing a communicative atmosphere that involves all students. These orientations were most visible overall in the PD groups (see Table 1). In regard to the individual PD groups, however, differences can be seen in terms of the main orientations. While PD group 1 (n = 17) tended to display both a conceptual and a long-term mastery orientation, PD group 2 (n = 9) showed more of a short-term orientation, followed by syllabus-bound, both shortterm and long-term, communicative, and lastly, individualistic orientations. PD group 3 (n = 10), in contrast, displayed all orientations with less emphasis on any particular orientation. In all of the PD groups, teachers showed contradictory orientations. Even when a teacher or some of them showed orientations that agree with the guiding principles of the PD program Mastering Math (see the green marked orientations), usually there was also at least one another teacher who revealed orientations that do not agree with the guiding principles (red marked), such as "(…) has mastered the task, even if the background knowledge may not change, but it is a success for them (…)" or who weighed the pros and cons of both contradictory orientations (orange marked) by referring, for example, to the need to take into account the different perspectives students and teachers have, such as "[…] the current material can't be understood, if there are gaps before that are too big (…) for the short-term success of the children this is here [short-term] much better and for the motivation also, but […] as a teacher I have them but then rather the longer-term development in view".

Teachers' statements that, in some cases, point to orientations contradictory to the PD guiding principles represent the starting point of the PD with which facilitators need to deal with when targeting the PD content goals. We examined the practices and patterns of practices facilitators showed in response to teachers' orientations as a next step (RQ 2 and RQ 3). The analysis of the facilitator practices in reaction to the statements made by the teachers in the three PD groups revealed a variety of practices in the three groups (RQ2). When analyzing facilitators' reactions and responses to orientations teachers articulated, the number of statements that agree, disagree or weigh pros and cons were considered (see table 2). Facilitators in PD group 1 most often needed to react to teachers' statements that were in agreement with PD guiding principles. Accordingly, the number of facilitator statements providing confirmation is the highest in that group. However, the facilitators did not provide confirmation to all of the agreeing statements, but instead took note of them, recognizable through verbalized acknowledging. • Taking a neutral position 0 0 0

• Not commenting 0 1 0

• Invalidating a statement 0 0 0 weighs pros and cons of PD guiding principles (=5 statements) (=1statement) (=7 statements)

• Acknowledging 0 0 1

• Providing confirmation 3 1 1
• Taking a neutral position 0 0 1

• Invalidating a statement 2 0 1

• Reinterpreting a statement 1 0 0 is in disagreement with PD guiding principles (=3 statements) (=4 statements) (=4 statements)

• Acknowledging 0 0 0

• Providing confirmation 1 1 0

• Taking a neutral position 0 0 0

• Invalidating a statement 2 3 1 • Reinterpreting a statement 1 2 0
If teachers' statements were in disagreement with the PD guiding principles or the teachers weighed pros and cons, the facilitators, in most cases, invalidated or reinterpreted teachers' statements, pursuing the content goal, but also provided confirmation when teachers weighed pros and cons, preferring to keep a good atmosphere as a situative goal. The facilitators' practice of providing confirmation, even when a teacher's statement did not agree with the PD principles, is part of a pattern we identified also in PD group 3 (RQ3). Facilitators first showed esteem for participants by providing confirmation as a first step, presumably to maintain a good atmosphere. As a second step, they invalidated or reinterpreted the teacher's statement, to stick to the content goal, by referring to PD guiding principles when highlighting the important role of understanding:

Facilitator: "Absolutely. And exactly it always depends on the person. […] In the short term I totally agree with you that you should build up self-confidence and strengthen the child a bit. But the understanding is […] and according to the concept of being able to do math safely is really the absolute crux.

[…] I can't understand the small, I can't understand the bignever. Ability. And then this child will always have failures his whole life long in mathematics lessons.

[…] That we think about it that understanding is really the absolute basis."

In sum, the facilitators in PD group 1 used the chance to refer to PD guiding principles implicitly or explicitly eight times when responding to teachers' statements (see table 3) and additionally illustrated one of the principles by means of driving a car as an everyday example.

The facilitators in PD group 2 pursued another pattern to respond to teachers' statements. Only two teacher statements in this group were in agreement with PD guiding principles. The facilitators did not comment on the two statements directly but acknowledged the statement and returned to it later on to provide confirmation more than one time in order to pursue the content goal of the PD. Furthermore, when all teachers showed nonverbal agreement with the PD guiding principles, the facilitators did not ask them to provide an argument, resulting in a lower number of statements in agreement with the PD principles. Instead of asking teachers for arguments, the facilitator used the chance to praise the orientations of the teachers and additionally to refer to the PD guiding principles implicitly (see Table 3), using an alternative way to target the content goal. In the case of teacher statements in disagreement with PD guiding principles, the facilitators invalided and/or reinterpreted the statement, and, in one case, they provided confirmation. Also, in regard to the one statement that weighed pros and cons, the facilitators provided confirmation of it. In these cases, facilitators pursued an atmospheric goal instead of the content goal.

The facilitators of PD group 3 responded to one of the five statements with the PD guiding principles, agreeing with teachers' orientations by providing confirmation two times, but missed responding to four of them. Instead of directly providing confirmation with PD principles to agreeing statements, the facilitators provided anecdotes from their private lives or from their own teaching experiences.

The same occurred in response to disagreeing statements or statements that weighed pros and cons (in sum 7 times, see Table 3). The facilitators referred implicitly or explicitly to PD guiding principles in response to all kinds of statements in six cases. Both contributed to maintaining a good atmosphere in the PD course. In sum, very often, they referred to examples out of their private lives and own instruction, as well as to PD guiding principles, explicitly or implicitly, pursuing an atmospheric goal. Instead of responding to teachers' statements directly, they decided to let the discussion between teachers flow, looking for statements of other teachers that invalidated the disagreeing statement. Furthermore, they avoided direct responses that invalidated or reinterpreted teachers' statements, also contributing to a good atmosphere and, at the same time, preserving the PD content goal. • examples from own instruction 0 0 5

• explicit reference to the PD guiding principles 5 1 4

• implicit reference to the PD guiding principles 3 3 2

Discussion and conclusion

The orientations teachers showed when they started a PD course on fostering the ability to monitor and enhance students' understanding of basic concepts are to some extent in line with previous evidence that points to a more procedural (Beswick, 2007;[START_REF] Wilhelm | Examining relations between teachers' explanations of sources of students' difficulty in mathematics and students' opportunities to learn[END_REF], syllabus bound, short-term [START_REF] Prediger | Design research with a focus on content-specific professionalization processes: the case of noticing students' potentials[END_REF], and individual orientation [START_REF] Krähenmann | Inclusive mathematics instruction: A conceptual framework and selected research results of a video study[END_REF], instead of a conceptual, diagnostic, long-term and communicative orientation. The latter orientations build the principles of the PD program and inform the content goals facilitators need to target when conducting the PD. The study revealed various practices facilitators use to respond to teachers' various orientations. Facilitators in PD group 1 mostly invited teachers to make a statement or bring an argument to the discussion. In the light of the PD guiding principles, the facilitator succeeded in being a good role model in that he or she exemplified a communicative orientation. Facilitators in PD group 2, in contrast, let many chances pass to invite teachers into a discussion or to ask them to bring arguments for their orientation and therefore missed examining whether teachers actually have conceptual orientations or whether they hold procedural orientations. Facilitators in PD group 3 faced many disagreeing statements as well as statements that weighed pros and cons and they responded to these statements with various examples from their daily lives and their own teaching practices, combined with explicit or implicit references to PD guiding principles.

In regard to the typical facilitators' patterns we identified, first, in many cases, the facilitators avoided reinterpreting or invalidating teachers' statements directly, but started their responses by providing confirmation before invalidating or reinterpreting them, presumably in order to maintain a good atmosphere. An additional pattern was found, also probably aiming to maintain good atmosphere within the PD groups: Instead of responding directly to statements that were not fully in agreement with PD guiding principles, the facilitators in two of the groups often used anecdotes or examples of their own instruction or referred to PD principles. Recourse to examples and principles seems to help the facilitators to pursue the content goal with a simultaneous preservation of a good atmosphere.

The study reveals the variety of facilitator practices used to respond to teachers' orientations and contributes to the understanding of multiple ways and patterns that appear in facilitators' moderation strategies when conducting PD courses. In line with the results of further case studies [START_REF] Prediger | Conducting PD discussions on language repertoires: A case study on facilitators' practices[END_REF], the challenge facilitators face when navigating between different PD goals they need to manage becomes obvious; in our study, facilitators' practices in all three of the PD groups demonstrated how facilitators attempted to balance content goals and atmospheric goals. As a next step, we suggest the investigation of whether facilitators' abilities to focus more strongly on the content goal while simultaneously considering atmospheric goals can be fostered by discussing PD incidents in video clubs and probing PD situations in simulated learning environments.

Table 1 : Teacher orientations overall and in the three PD groups in percentages

 1

	Teacher	All PD	PD group	PD group	PD group	PD group	PD group	PD group
	orientation	groups	1 (in %)	1 (absolute	2 (in %)	2 (absolute	3 (in %)	3 (absolute
		(in %)		instances)		instances)		instances)
	Conceptual	15.56	22.73	5	0	0	12.50	2
	Both	6.67	4.54	1	0	0	12.50	2
	Procedural	6.67	9.09	2	0	0	6.25	1
	Diagnostic	2.22	4.54	1	0	0	0	0
	Both	4.44	4.54	1	0	0	6.25	1
	Syllabus-bound 2.22	0	0	14.29	1	0	0
	Long-term	15.56	22.73	5	14.29	1	6.25	1
	Both	11.11	9.09	2	14.29	1	12.50	2
	Short-term	6.67	4.54	1	28.57	2	12.50	2
	Communicative 13.33	13.64	3	14.29	1	12.50	2
	Both	6.67	4.54	1	0	0	12.50	2
	Individualistic	4.44	0	0	14.29	1	6.25	1

Table 2 : Absolute instances of facilitator practices in response to teacher statements in the PD groups

 2

	Facilitator practice in reaction to a teacher	Group 1	Group 2	Group 3
	statement that	facilitators	facilitators	facilitators
	is in agreement with PD guiding principles	(=14 statements) (=2 statements) (=5 statements)
	• Acknowledging	4	2	2
	• Providing confirmation	9	3	2

Table 3 : Absolute instances of facilitators reference to practice in the three PD groups

 3

	Facilitators use of	Group 1	Group 2	Group 3
	• anecdotes or everyday examples	1	0	2