{'fraction_non_alphanumeric': 0.06798113408276889, 'fraction_numerical': 0.01436221142593709, 'mean_word_length': 3.8520302821748107, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A variational formula for risk-sensitive reward

We derive a variational formula for the optimal growth rate of reward in the infinite horizon risk-sensitive control problem for discrete time Markov decision processes with compact metric state and action spaces, extending a formula of Donsker and Varadhan for the Perron-Frobenius eigenvalue of a positive operator. This leads to a concave maximization formulation of the problem of determining this optimal growth rate.


Introduction
Infinite time horizon risk-sensitive control seeks to maximize the asymptotic growth rate for mean multiplicative reward in the standard Markov decision theory setting. The optimal reward multiplier per step turns out to be the Perron-Frobenius eigenvalue of a positive 1-homogeneous nonlinear operator. The existence of this Perron-Frobenius eigenvalue and an associated eigenfunction is ensured by the nonlinear Krein-Rutman theorem of [37, Theorem 3.1.1 and Proposition 3.1.5] under suitable conditions (see also [36], [33], [32], [12], [3]). Our aim here is to build on this nonlinear Krein-Rutman theorem to provide a variational formula for the optimal growth rate of reward in the spirit of the Donsker-Varadhan formula for the Perron-Frobenius eigenvalue of a nonnegative matrix [15, section 3.1.2], [18], [22].
Risk-sensitive control has traditionally been studied in the framework of cost minimization, see e.g. [16], [26], [27] for recent work on general state space models and [20], [24] for its discrete state space precursors. Work on risk-sensitive reward maximization has been relatively uncommon, see e.g. [28]. Unlike in the case of the classical discounted or ergodic costs, the two risk-sensitive control problems are not trivially equivalent by treating cost as a negative reward. In fact, risk-sensitive reward maximization is the natural set-up in portfolio optimization, see e.g. [13]. Nevertheless, it has been commonplace to replace it by risk-sensitive cost minimization so as to exploit the vastly more abundant available machinery for the latter problem, see, e.g. equation (18) of [6]. Interestingly, our approach is tailored for the risk-sensitive reward maximization problem.
The paper is organized as follows. This section presents the basic notation and control-theoretic framework. In section 2 we develop the role of the nonlinear Krein-Rutman theorem in giving an expression for the optimal reward multiplier per stage. In section 3 this is parlayed into a variational expression for the optimal growth rate of reward. Theorem 4 in section 3 is the main result of this paper. Alternative variational formulations derived from the primary one are discussed in section 4; each of these provides a different kind of insight into how to think about the optimal growth rate of reward. Some examples are worked out in section 5 to illustrate the nature of the results. We close the paper with some concluding remarks in section 6.
We turn next to introducing our notation and the control-theoretic framework. For a compact metric space X , M(X ) and P(X ) will denote respectively the space of finite (signed) Borel measures on X and the space of probability measures on X , both with the topology of weak convergence [9]. C(X ) will denote the Banach space of continuous maps X → R with the supremum norm, denoted by · . Thus M(X ) is the dual Banach space of C(X ), with the weak-* topology [39]. Let S be a prescribed compact metric space called the state space and U another compact metric space, called the action space. We shall consider an S-valued controlled Markov process (X n , n ≥ 0) controlled by a U-valued control process (Z n , n ≥ 0) defined as follows. Consider a complete probability space (Ω, F , P ) where Ω := (S × U) ∞ , and F is its product Borel σ-field. For ω = [(ω 0 , ω ′ 0 ), (ω 1 , ω ′ 1 ), (ω 2 , ω ′ 2 ), · · · ] ∈ Ω with ω i ∈ S and ω ′ i ∈ U ∀i, define 'canonical' random variables X i = ω i , Z i = ω ′ i , i ≥ 0. The probability measure P on (Ω, F ) is then the law of ((X n , Z n ), n ≥ 0) defined as follows. The law of X 0 is prescribed and the law of ((X n , Z n ), n ≥ 0) is constructed inductively. For this purpose, define two increasing families of sub-σ-fields of F : F − n := σ(X m , m ≤ n; Z m , m < n) and F n := σ(X m , m ≤ n; Z m , m ≤ n) for n ≥ 0. First define the conditional is a prescribed kernel, i.e. φ 0 (du|x) is a probability distribution in P(U) for all x and φ 0 (A|x) is Borel measurable in x for all Borel subsets A ⊂ U. Let P n denote the law of ((X 0 , Z 0 ), (X 1 , Z 1 ), · · · , (X n , Z n )), defined as a probability measure on (Ω, F n ), starting with n = 0. Define the law of X n+1 given F n as p(dy|X n , Z n ) where is a prescribed kernel, i.e. p(dy|x, u) is a probability distribution in P(S) for all (x, u) ∈ S × U and p(A|x, u) is Borel measurable in (x, u) for all Borel subsets A ⊂ S. Define the conditional law of Z n+1 given F − n+1 as is a prescribed kernel for each n. These together define P n+1 . By the Ionescu-Tulcea theorem (p. 101, [38]), we define a unique P on (Ω, F ). By construction, for all Borel A ⊂ S, The (Z n , n ≥ 0) constructed above will be referred to as admissible controls. We shall also consider two special classes of admissible controls: stationary Markov controls of the form for some measurable v : S → U, and randomized stationary Markov controls satisfying for some kernel ϕ(du|x) : S → P(U). By a standard abuse of terminology, we identify these with the maps v(·), ϕ(·|·) resp. The sets thereof will be denoted by SM and RM respectively. We view SM as a subset of RM by identifying v(·) with δ v(·) , the Dirac measure at v(·).
The infinite horizon risk-sensitive reward we seek to characterize is where the second supremum is over all admissible controls. Here r(x, u, y) is an extended-real-valued function on S × U × S, called the 'per stage reward' on transitioning from x to y under action u. It should be noted that we will allow e r(x,u,y) = 0 for some (x, u, y), so r(x, u, y) should be thought of as being allowed to take the extended real value −∞. Throughout the paper, we make the following assumptions about r(x, u, y) and p(dy|x, u). We will occasionally explicitly recall these assumptions to remind the reader of this.
We shall denote by e r M the least upper bound for e r(·,·,·) , which is finite by virtue of assumption (A0).
Towards the end of the next section we will build up to the main variational formula by first considering the case where we have additional restrictions captured by the following assumptions.
If p(dx) and q(dx) are finite nonnegative Borel measures on a compact metric space X , we write D(p(dx) q(dx)) for the relative entropy of p(dx) with respect to q(dx), defined by See e.g. [41] for some of the basic properties of relative entropy.

The Perron-Frobenius eigenvalue
Let assumptions (A0) and (A1) be in force. Define the operator T : For fixed x ∈ S on the left hand side of (3) the supremum on the right hand side is the expectation of a continuous affine function on a compact set of probability measures. Hence, it is a maximum attained at a Dirac measure.
For each fixed f ∈ C(S), a standard measurable selection theorem [5, Lemma 1, p. 182] allows us to choose the family of maximizers, parametrized by x ∈ S, as a measurable function v : S → U. To see that T is a map e r(x,u,y) − e r(x ′ ,u,y) .
As x → x ′ , the first term on the right tends to zero by (A1) and the second term on the right tends to zero by uniform continuity of e r , being a continuous function defined on a compact set, by (A0). In fact, this shows that T f, f ≤ R, are equicontinuous and bounded. Also, from the definition of T , it is straightforward to check that which establishes T as a continuous (in fact, Lipschitz) map C(S) → C(S).
Likewise, define, for f ∈ C(S), where the supremum is over all admissible control processes. Then T (1) = T , by virtue of the measurable selection theorem alluded to after (3). We use the convention T (0) := the identity map.
is a semigroup of operators on C(S). ✷ Proof of Lemma 1: Note that we need to verify that T (n) for n ≥ 2 maps C(S) to C(S) as part of the stated claim. This follows as a corollary of the proof, which establishes that T (n) is the n-fold concatenation of T with itself. The proof follows by a standard dynamic programming argument. Specifically, we first have where the inner supremum in the second line is over the control sequence from time 1 onwards, conditioned on X 0 = x 0 , Z 0 = z 0 , X 1 = x 1 (say). Secondly, let ǫ > 0. By [10, Lemma 1, p. 55], conditioned on (X 0 , Z 0 , X 1 ), there exists an admissible state-control sequence ( is an admissible state-control sequence and Combining (4), (5) and using the fact that ǫ > 0 was arbitrary, it follows that T (n) = T (1) •T (n−1) . A similar argument shows that The semigroup (T (n) , n ≥ 0), is precisely the discrete time counterpart of the Nisio semigroup [35].
Let C + (S) := {f ∈ C(S) : f (x) ≥ 0} denote the set of nonnegative functions in C(S). Then C + (S) is a cone, i.e. it is closed under addition and scalar multiplication by nonnegative real numbers, and we have C + (S) ∩ (−C + (S)) = {θ} where θ denotes the constant function that is identically zero. Thus C + (S) defines a partial order on C(S), denoted ≥, This is the set of finite nonnegative measures on S, which we denote by M + (S). For more on cones in Banach spaces, see [2].
Let us now make the additional assumption (A0+) and (A1+). One can then verify the following additional properties of T (n) for each n ≥ 1.
1. T (n) is strictly increasing, i.e., f < g implies T (n) f < T (n) g. In view of the fact established above that (T (n) , n ≥ 0) is a semigroup, it suffices to prove this claim for n = 1. We know that there is a measurable function v : S → U such that > 0 , because f < g, f = g and support(p(dy|x, u)) = S ∀ x, u.
This follows from the fact that for any u 0 ∈ U, where we use the fact that support(p(dy|x, u 0 )) = S.

T (n) is compact. (This holds under the weaker assumptions (A0) and
(A1).) It suffices to verify this for n = 1, the general case being then a consequence of the semigroup property.
Hence it is relatively compact in C(S) by the Arzela-Ascoli theorem. Let δ ∈ [0, 1] → w δ (·) denote its common modulus of continuity relative to a compatible metric κ on S.
By Arzela-Ascoli theorem, it is relatively compact, implying that T : The preceding considerations allow us to state the following theorem.
Before proceeding to the proof of Theorem 1, it is appropriate to make a few remarks. A great deal is known about analogs of the Perron-Frobenius theorem for increasing positively one-homogeneous maps on finite dimensional vector spaces, see the recent book [30]. When the map is on an ordered Banach space (and one talks about a Krein-Rutman theorem rather than a Perron-Frobenius theorem, in view of the seminal work in [29]), we rely on Theorem 3.1.1, Proposition 3.1.5, and Lemma 3.1.7 of [37], as seen in the proof below (see also [36], [33]). These results in [37] are themselves stated in a much broader context than the special case of the Banach space C(S) and the order structure defined by the cone C + (S), with S a compact metric space, which suffices for our purposes. The recent papers [32] and [12] claim even stronger nonlinear Krein-Rutman theorems. However, it has been recognized in [3] that some of the claims in these papers are wrong. The proof of the Theorem 1 given below does not rely in any way on [32], [12], or [3].
Proof of Theorem 1: We define Since (T (n) , n ≥ 0) is a positive semigroup, it is straightforward to check that exists. By the fourth of the properties of the semigroup (T (n) , n ≥ 0) shown above, we have r(T ) > 0. It will turn out that the ρ promised in the statement of Theorem 1 is just r(T ). Strong positivity of T , which was shown above, verifies assumption A4 in [37, pg. 47], and the facts that T is compact (as established above), onehomogeneous, and order preserving are respectively the conditions A1, A2, and A3 in [37, pg.47]. Thus [37, Proposition 3.1.5.] provides the additional requirement in the statement of [37, Theorem 3.1.1] that T have an eigenvalue, and [37, Theorem 3.1.1] states that with ρ taken to be r(T ) there exists a ψ ∈ int(C + (S)) such that (6) holds.
It remains to establish (7), where we now know that ρ = r(T ). We have which comes from substituting ψ as a choice for f on the right hand side. Similarly, we have Thus it suffices to establish Given f ∈ int(C + (S)), we have T f dµ f dµ . Since this holds for all f ∈ int(C + (S)), this establishes the first inequality in (8). The proof of the second inequality in (8) is similar, based on [37, Lemma 3.1.7 (iii)]. This concludes the proof of Theorem 1. ✷ Next we show that log ρ is in fact the optimal growth rate of the risksensitive reward. For a development of the analogous result in the case of controlled diffusion processes, see [4]. As argued earlier, in connection with the right hand side of (3), for each x ∈ S, the supremum on the right hand side of (6) is the expectation of a continuous affine function on a compact set of probability measures, and is therefore a maximum attained at a Dirac measure. A standard measurable selection theorem [5, Lemma 1, p. 182] then allows us to identify the family of maximizers, parametrized by x ∈ S, with an element of SM, which we denote by v * (·). Letting (X * n , n ≥ 0) denote the chain governed by the stationary Markov strategy v * (·) and (Z * n = v * (X * n ), n ≥ 0) the corresponding control sequence, we then have and, more generally, by iterating, we have, for all x ∈ S, Since ψ(x) ∈ int(C + (S)), we have 0 < c < ψ(·) < C < ∞ for some constants c, C when ψ is chosen with, say, ψ = 1. Thus, for all x ∈ S, For any other admissible state-control sequence ((X n , Z n ), n ≥ 0), we have Iterating, and therefore We have proved: Under the assumptions (A0+) and (A1+), we have, for all x ∈ S, where the supremum on the right is over all admissible controls and ρ on the left is given as in Theorem 1. Furthermore, this supremum is a maximum attained at some v * (·) ∈ SM. ✷ An immediate consequence is the following. where λ is the optimal growth rate of reward, as defined in (2), and ρ is as defined in Theorem 1. ✷
Theorem 4. Under the assumptions (A0) and (A1), the optimal growth rate of reward λ, as defined in (2), has the variational characterization ✷ Before proving Theorem 4, let us first consider the uncontrolled case. We can fit this into our framework by taking U to be a set with one point, so that p(dy|x, u) =p(dy|x) for all u ∈ U, for some kernelp(dy|x), and r(x, u, y) =r(x, y) for all u ∈ U, for somer(·, ·). Theorem 4 then specializes to the statement that the growth rate of the reward, under the respective specializations of conditions (A0) and (A1), is given by where α(dx, dy) = α 0 (dx)α 1 (dy|x) and This is then a version of the Donsker-Varadhan formula for the Perron-Frobenius eigenvalue of a positive operator [15], [18], [22].
Since this kernel and reward satisfy the conditions (A0+) and (A1+), we have from Theorem 3 that the optimal growth rate of reward for the risksensitive reward maximization problem for this kernel and reward, call it λ ǫ , is given by From the formulation of the risk-sensitive objective we see that λ ǫ is nondecreasing in ǫ, and that λ ǫ ≥ λ for all ǫ > 0, where λ is defined as in (2). This can be seen by writing the expression for the n-step multiplicative reward, i.e.
✷. It is straightforward to check that the assumptions (A0), (A1) hold for theS-valued chain with trivial control spaceŪ and with the transition kernel and one step reward as above. , u, y). Let
The upshot is that we have proved Under (A0+), (A1+), this supremum is in fact a maximum by virtue of Theorem 2.
2. Since D(·||·) is convex and lower semi-continuous in its arguments as noted earlier, (10) is a concave maximization problem on the convex 3 set It is worthwhile to compare this formulation with the classical dynamic programming approach. Recall that the dynamic programming equation (6) is the nonlinear eigenvalue problem ρV (x) = sup ϕ p(dy|x, u)ϕ(dy|u)e r(x,u,y) V (y) .
We treat x as a fixed parameter on the right hand side. By the Gibbs variational principle, we have Equation (19) is the dynamic programming equation for an ergodic team problem whose 'per stage payoff' function is where µ specifies an additional control variable the choice of which is in fact the distribution of the next state and control, whereas the original randomized control ϕ affects only the payoff. This is a team problem as opposed to a control problem because while both controls have the same objective, viz., to maximize a common reward, they are implemented in a non-cooperative manner. This is reminiscent of, e.g., [24], which considers the cost minimization formulation in which a similar procedure leads to a zero sum ergodic game. There does not, however, appear to be any corresponding development earlier for the reward maximization problem with a positive reward. While this is completely analogous to the game situation, we have obtained it without an explicit minorization condition as in [16], or the 'condition B' of [26]. We have instead conditions (A0) and (A1) which are relatively mild, and compactness of state space, which is not. We are working towards relaxing the latter.
An important point to note here is that we have an equivalent problem of maximizing a concave upper semi-continuous function over the convex set G 1 . This is in contrast with the ergodic team problem of maximizing the same function over the nonconvex set i.e., where the controls ϕ, µ ′ are chosen by the two team members noncooperatively. The latter is what one obtains from the team formulation via log transformation.
3. It is also worth noting that the entropic penalty implicit in our variational formula also arises in different contexts [8], [23], [40]. It is also known that this common limit can be written as Here Π ranges over d×d transition probability matrices that are G-compatible for the directed graph G, i.e. such that π(y|x) > 0 implies that (x, y) ∈ E G , and π ranges over invariant probability distributions for Π. Note that this is the largest entropy rate among all stationary Markov chains whose transition probability matrix is compatible with the graph. This characterization of the growth rate of the number of paths in an irreducible graph is a consequence of the Donsker-Varadhan formula for the Perron-Frobenius eigenvalue of a nonnegative matrix. Let us verify this as a corollary of Theorem 4 in the case without controls. We take the state space in Theorem 4 to be S, i.e. the vertex set of the graph. The control space U is a set consisting of a single point, which we write as U = {u}. Let p(y|x, u) := 1 d(x) for d(x) := the out-degree of x and (x, y) ∈ E G , and let Substituting these into the right hand side of (10) gives the expression in (20).
We now bring risk-sensitive control into this mix of ideas. Let U be a finite set and suppose now that for each u ∈ U we are given a directed graph G u with vertex set S. Assume that each vertex has at least one out-going edge in each G u . We pose the problem of maximizing max x∈S lim inf where nowN n (x) is the largest number of directed paths of length n one can create when starting at x and at each time choosing one of the graphs along which to move (i.e. one of the control actions) depending on the history of the states visited so far. More generally, we might allow for a randomized choice of the graph to be used at each time, based on the history of the states and the realizations of the control so far, and ask for the maximum growth rate of the expectation of the number of directed paths of each length that we can create in this way. This problem can be posed in a framework that is amenable to an application of Theorem 4. As in the case without controls, we set p(y|x, u) := 1 for all (x, y) ∈ E Gu , where d u (x) denotes the out-degree of vertex x in G u , and we now set According to Theorem 4 this maximum growth rate is given by where the maximum is over all η(x, u, y) =η(x, u)η 2 (y|x, u) with η 2 (y|x, u) > 0 implying that (x, y) ∈ E Gu , and such that where, as usual, η 0 (x) := uη (x, u). Note that this has following interpretation: among all stationary Markov chains ((X n , Z n ), n ≥ 0) with state space S × U that are compatible with the family of graphs in the sense that if a transition from (x, u) to (y, u ′ ) has positive probability then (x, y) ∈ E Gu , maximize the conditional entropy of the next state given the current stateentropy pair, i.e. maximize H(X 1 |X 0 , U 0 ). The interpretation of the growth rate of the number of directed paths of a given length in a directed graph as an entropy rate has considerable practical importance in coding theory. Each directed path of length n can be viewed as an allowed sequence of length n, with coordinates from the state space S, and the set of such directed paths is then viewed as a set of constrained sequences [14,Problem 4.16], [31]. The problem of constrained coding has been extensively studied. In one version of this problem, the goal is to come up with algorithms that can take an infinitely long sequence of symbols from a finite set of size m and produce S-valued sequences as output in a one-toone fashion, and such that the output sequences meet the constraints defined by the graph, see [31,Sec. 5.2] for more details. Naturally, it is not possible to do this if log m exceeds the growth rate given by (20); finding efficient algorithms to do this whenever log m is less than the growth rate given in (20) was a key early success in this area [1], [31]. Investigating the question of constrained coding up to the maximum possible conditional entropy rate given by the application of Theorem 4 to the controlled graph formulation above would be an interesting challenge.

Portfolio optimization
As another example, we consider the portfolio optimization problem from [6], except that we consider the reward maximization framework instead of cost minimization as in the classic work of Cover [13]. The model is as follows. The underlying 'factor process' {X n } is a discrete time Markov chain on a finite state space Q := {1, · · · , m} (say) with an irreducible transition matrix Q = [[q(j|i)]]. The control space will be the simplex A := {a = a 1 , · · · , a m ] ∈ R m : a i ≥ 0 ∀i, i a i ≤ 1}, with a i denoting the proportion of wealth invested in the ith risky asset. In particular, 1 − i a i is then the proportion invested in the risk-less bank account. We denote by {π n } the A-valued control sequence, representing the trading strategy, i.e., π n,i will be the proportion of wealth invested in the ith risky asset at time n. {W n } is the process of m-dimensional vectors of price relatives such that W n+1 is conditionally independent of X i , i < n; W i , π i , i ≤ n, given (X n , X n+1 ) and its conditional law given the latter is specified by a kernel ν(x, y, dw) : Q × Q → R m with support in the interior of the positive cone in R m . Let e r , r > 0, denote the per period multiplier of wealth invested in the bank account (thus e r − 1 is the interest rate). Let 1 denote the constant vector of all 1's. The evolution of the wealth process {V t } is given by where V 0 := 1. The objective is to maximize the risk-adjusted growth rate of wealth Here θ is the risk sensitivity parameter. The control sequence {π n } is assumed to be adapted to the factor process {X n } and the controls, i.e. the distribution of π n is chosen as a function of (X 0 , . . . , X n , π 0 , . . . , π n−1 ).
It is useful to constrast the objecive we consider with that considered in [6] of maximizing, for θ > 0, the quantity lim inf In [6], this problem is considered by writing the objective in (24) By constrast, our formulation is able to handle both the case of riskaversion and risk-seeking. The Taylor's series expansion indicates that if the objective in (23) is multiplied by − 2 θ , then it corresponds to risk-aversion for positive θ and to risk-seeking for negative θ.
One can show that for all n ≥ 1 and all admissible controls, we have , whereẼ is the expectation with respect to the law where p(x 0 ) is the initial distribution of X 0 , the admissible controls are determined by the kernels φ 0 (·|·), . . . , φ n−1 (·|·), and the salient point is that the transition kernel for the evolution of the factor process under this change of measure is given by the kernel p(·|·, ·) defined above. To see this, first observe that W 1 , . . . , W n are conditionally independent and identically distributed given ( For an admissible control strategy, we can write this as which is the same as which equalsẼ e − θ 2 n−1 m=0 r(Xm,πm) . Hence the problem of maximizing (23) is equivalent to the risk-sensitive control problem for a controlled Markov chain on Q with action space A and controlled transition probabilities p(y|x, a), x, y ∈ Q, a ∈ A, the objective being to maximize the reward λ := sup where the second supremum is over admissible controls. The optimal growth rate for the wealth is then given by where G := η(x, da, y) ∈ P(Q × A × Q) : η(x, da, y) =η(x, da)η 2 (y|x, a) = η 0 (x)η 1 (da|x)η 2 (y|x, a) such that η 0 is stationary under the transition matrix η 1 (da|x)η 2 (y|x, a) .
In order to justify this, we need to verify that the conditions (A0) and (A1) are satisfied. Here Q plays the role of S, A plays the role of U, and − θ 2 r(x, a) plays the role of r(x, u, y) in the general theory. The validity of (A0) follows from the continuity of the logarithm function. The validity of (A1) follows from the continuity of the logarithm function, the fact that Q is finite, and because y ′ q(y ′ |x)µ(x, a, y) is strictly positive for all (x, a).
If we discretize A, this is a finite dimensional concave maximization problem eminently amenable to standard nonlinear programming tools.

Minimizing exit rate from a domain
Consider a set of controlled stochastic matrices on a finite state space S = {1, · · · , s} denoted by P u = [[p(j|i, u)]] i,j∈S . Here u is the control parameter taking values in A, where A is a compact metric action space. We assume that u → P u is continuous and P u is irreducible for all u. Let S 0 ⊂ S be a nonempty proper subset of S and let S 1 := S c 0 denote its complement. Leť P u denote the restriction of P u to S 1 and for a sequence of random variables {X n } with values in S, define τ := inf{n ≥ 0 : X n ∈ S 0 }.
We are interested in determining λ := sup i∈S 1 sup lim inf n↑∞ 1 n log P (τ > n) , where the second supremum is over all admissible controls, and the law of τ is determined by the control strategy. Namely, we are interested in the problem of finding the slowest exit rate from S 1 over admissible control strategies. WriteP u = D u Q u where D u is a diagonal matrix with its ith diagonal entry d(i, u) := j∈S 1 p(j|i, u) and Q u := [[q(j|i, u)]] is a stochastic matrix on S 1 given by q(j|i, u) := d(i, u) −1 p(j|i, u), where we will also assume that d(i, u) > 0 for all i ∈ S 1 and u ∈ A. It can be checked that for any admissible control strategy and i ∈ S 1 , we have P (τ > n) = E e n−1 m=0 log(d(Xm,Um)) , where U m denotes the choice of control at time m, and {X n } is the S 1valued Markov chain, having the transition probability matrix Q Um at time m. Therefore, with the choices S := S 1 , U := A, and r(i, u, j) := log d(i, u), the problem is amenable to our general theory.
Then our results show that λ = max η∈G i,j∈S 1 A η(i, du, j) log(d(i, u)) − i∈S 1 Aη (i, du)D(η 2 (j|i, u)||q(j|i, u)) , where G denotes the set of η ∈ P(S 1 × A × S 1 ) for which η 0 is invariant under the transition kernel A η 1 (du|i)η 2 (j|i, u). To verify this, we need to check the validity of the conditions (A0) and (A1). The former is a consequence of the assumed continuity of u → P u . The latter is a consequence of the fact that S 1 is finite and that u → Q u is continuous, which in turn follows from the assumed continuity of u → P u and the assumption that d(i, u) > 0 for all i ∈ S 1 and u ∈ A.