Average optimality for risk-sensitive control with general state space
Average optimality for risk-sensitive control with general state space
The Annals of Applied Probability
2007, Vol. 17, No. 2, 654–675
DOI: 10.1214/105051606000000790
c© Institute of Mathematical Statistics, 2007
AVERAGE OPTIMALITY FOR RISK-SENSITIVE CONTROL WITH
GENERAL STATE SPACE1
By Anna Jaśkiewicz
Wroc law University of Technology
This paper deals with discrete-time Markov control processes on
a general state space. A long-run risk-sensitive average cost crite-
rion is used as a performance measure. The one-step cost function is
nonnegative and possibly unbounded. Using the vanishing discount
factor approach, the optimality inequality and an optimal stationary
strategy for the decision maker are established.
1. Introduction and the model. This paper deals with discrete-time
Markov control processes on a general state space. The one-step cost function
is nonnegative and possibly unbounded. The decision maker is supposed to
be risk-averse with a constant risk coefficient γ > 0. The risk-sensitive aver-
age cost criterion is used as a performance measure. The aim of the work is to
establish the optimality inequality for risk-sensitive dynamic programming
and derive an optimal stationary policy. The result is proved under two
different sets of compactness-continuity assumptions, namely, for Markov
control processes with weakly continuous transition probabilities [Condition
(W)], as well as transition probabilities that are continuous with respect
to setwise convergence [Condition (S)]. A similar problem for risk-neutral
stochastic control models has been examined in [27] using the vanishing dis-
count factor approach. However, it is well known that, for risk-sensitive con-
trol models, an analogous approximation of the average cost via a sequence
of the corresponding discounted models does not work. Instead of this, fol-
lowing [9, 15, 16], we introduce an auxiliary discounted minimax problem.
A variational formula that expresses the mutual relationship between the
relative entropy function and the logarithmic moment-generating function
enables us to connect the discounted minimax model with the original one.
Received March 2006; revised September 2006.
1Supported by MEiN Grant 1 P03A 01030.
AMS 2000 subject classifications. Primary 60J05, 90C39; secondary 60A10.
Key words and phrases. Risk-sensitive control, Borel state space, average cost optimal-
ity inequality.
This is an electronic reprint of the original article published by the
Institute of Mathematical Statistics in The Annals of Applied Probability,
2007, Vol. 17, No. 2, 654–675. This reprint differs from the original in pagination
and typographic detail.
http://arxiv.org/abs/0704.0394v1
http://www.imstat.org/aap/
http://dx.doi.org/10.1214/105051606000000790
http://www.imstat.org
http://www.ams.org/msc/
http://www.imstat.org
http://www.imstat.org/aap/
http://dx.doi.org/10.1214/105051606000000790
2 A. JAŚKIEWICZ
Next, assuming that a certain family of functions is bounded [Condition (B)]
and using Fatou’s lemma (for weakly or setwise convergent measures), we
obtain the optimality inequality.
The predecessor of our result is Theorem 4.1 in [16], where the optimality
inequality for the risk-sensitive dynamic programming with a countable state
space was established. Instead of boundedness assumption (B), Hernández-
Hernández and Marcus [16] assume that there exists a stationary policy
which induces a finite average cost that is equal some constant in each
state. On the other hand, it is well known that an optimal risk-sensitive
average cost may depend on the initial state (see Example 1). This behavior
happens if the risk factor is too large. Instead of this restriction on the
risk coefficient, we use Condition (B), which makes the process reach “good
states” sufficiently fast.
There is a rich literature in risk-sensitive control, going back at least to
the seminal works of Howard and Matheson [18] and Jacobson [19], which
covered the finite horizon case. The average cost criterion on the infinite
horizon was studied in [5, 8, 14, 15, 16, 31] for a denumerable state space
and in [10, 11, 20] for a general state space. It is also worth mentioning
that risk-sensitive control finds natural applications in portfolio managment,
where the objective is to maximize the growth rate of the expected utility
of wealth; see [3, 4, 30] and the references cited therein.
The paper is organized as follows. Below a Markov control model with
the long-run average cost criterion as a performance measure is described, as
well as some basic notation is set up. In Section 2 we introduce preliminaries
and present the auxiliary discounted minimax problem, which is, in turn,
solved in Section 3. The main result is established in Section 4. Section 5
contains a discussion of Condition (B), and in the Appendix a variational
formula for the logarithmic moment-generating function is stated.
A discrete-time Markov control process is specified by the following ob-
jects:
(i) The state space X is a standard Borel space (i.e., a nonempty Borel
subset of some Polish space).
(ii) A is a Borel action space.
(iii) K is a nonempty Borel subset of X×A. We assume that, for each
x ∈X , the nonempty x-section
A(x) = {a ∈A : (x,a) ∈K}
of K is compact and represents the set of actions available in state x.
(iv) q is a regular conditional distribution from K to X.
(v) The one-step cost function c is a Borel measurable mapping from K
to [0,+∞].
RISK-SENSITIVE CONTROL 3
Then the history spaces are defined as H0 = X, Hk = (X ×A)
k ×X and
H∞ = (X ×A)
∞. As usual, a policy π = {πk, k = 0,1, . . .} ∈ Π is a sequence
of transition probabilities from Hk to A such that πk(A(xk)|hk) = 1, where
hk = (x0, a0, . . . , xk) ∈Hk. The class of stationary policies is identified with
the class F of measurable functions f from X to A such that f(x) ∈A(x). It
is well known that F is nonempty [6]. By the Ionescu–Tulcea theorem [24],
for each policy π and each initial state x0 = x, a probability measure P
and a stochastic process {(xk, ak)} are defined on H∞ in a canonical way,
where xk and ak describe the state and the decision at stage k, respectively.
By Eπx we denote the expectation operator with respect to the probability
measure Pπx .
Let γ > 0 be a given risk factor. For any initial state x ∈X and policy
π ∈ Π, we define the following risk-sensitive average cost criterion:
J(x,π) = lim sup
logEπx exp
c(xk, ak)
Our aim is to minimize J(x,π) within the class of all policies and find a
policy π∗, for which
J∗(x) := inf
J(x,π) = J(x,π∗).
Throughout the paper the following assumption will be supposed to hold
true even without explicit reference:
∃π̃ ∈ Π J(x, π̃) < +∞.(G)
Remark 1. Throughout the remainder, we assume that the risk factor
γ > 0 is arbitrary and fixed. Therefore, here and subsequently, we shall not
indicate that some quantities depend on γ [e.g., we write J(x,π) instead of
Jγ(x,π), dropping the index γ].
2. Preliminaries. Let Pr(X) be the set of all probability measures on
X. Fix ν ∈ Pr(X). The relative entropy function R(·‖ν) is a mapping from
Pr(X) into R defined as follows:
R(µ‖ν) :=
dµ, µ≪ ν,
+∞, otherwise.
It is well known that R(µ‖ν) is nonnegative for any µ ∈ Pr(X) and R(µ‖ν) =
0 if and only if µ = ν (consult Lemma 1.4.1 in [12]).
We shall consider the following auxiliary minimax problem, associated
with our original Markov control process. The set X is the state space,
4 A. JAŚKIEWICZ
while A and Pr(X) are the action sets for the decision maker and op-
ponent, respectively. The process then operates as follows. In a state xn,
n = 0,1, . . . , the controller chooses an action an ∈ A(xn), while the oppo-
nent selects µn(·)[xn, an] ∈ Pr(X). As a consequence, the controller pays
γc(xn, an)−R(µn‖q(·|xn, an)) to his opponent, and the system moves to the
next state according to the probability distribution µn(·)[xn, an].
We shall deal with the following classes of strategies. It will cause no
confusion if we continue to use the same letters to denote strategies for
the controller. Namely, π stands for a randomized control strategy (policy),
whereas f denotes a stationary strategy. We write Π and F to denote the sets
of corresponding strategies. For the opponent’s class of strategies, we confine
to the stationary one, which is identified with the class P of stochastic kernels
p on X given K.
Let (Ω,F) be the measurable space consisting of the sample space Ω =
(X × A)∞ and its product σ-algebra F . Then for an initial state x ∈ X,
and strategies π and p, there exists a unique probability measure Pπpx and,
again, a stochastic process {(xk, ak)} is defined (Ω,F) in a canonical way,
where xk denotes the state at time k and ak is the action for the controller.
With some abuse of notation, we let hk stand for the history of the process
up to the kth state, that is,
hk = (x0, a0, x1, . . . , ak−1, xk).
The corresponding expectation operator is denoted by Eπpx .
For fixed x ∈ X, π ∈ Π and p ∈ P , we define the following functional
costs:
Vβ(x,π, p) =
βkEπpx [γc(xk, ak) −R(p(·|xk, ak)‖q(·|xk, ak))],(1)
where β ∈ (0,1) is the discount factor, and
j(x,π, p) = lim sup
Eπpx [γc(xk, ak) −R(p(·|xk, ak)‖q(·|xk, ak))].
Note that, since the function R(·‖·) is lower semicontinuous on Pr(X) ×
Pr(X) and p and q are stochastic kernels [i.e., measurable functions of (x,a)],
it follows that the mapping
(x,a) 7→R(p(·|x,a)‖q(·|x,a))
is measurable (Lemma 1.4.3(f) in [12]). Observe that Vβ(x,π, p) and j(x,π, p)
might be undetermined, because c can be unbounded. We thus restrict the
set of admissible strategies for the opponent in the following way.
RISK-SENSITIVE CONTROL 5
Definition 1. Given π = {πk} ∈ Π, we say that p ∈ P is a π-admissible
strategy iff
A(xk)
R(p(·|xk, a)‖q(·|xk, a))πk(da|hk) < +∞,(2)
and moreover, there exists a constant C ≥ 0, possibly depending on π and
p, such that
A(xk)
[γc(xk, a) −R(p(·|xk, a)‖q(·|xk, a))]πk(da|hk) + C ≥ 0,
for all histories of the process hk, k ≥ 0, induced by p and π. We denote
this set by Q(π). [Note that this set is nonempty, since p = q ∈Q(π) for any
π ∈ Π.]
Let us introduce the following notation. For any π ∈ Π, p ∈ Q(π) and
n≥ 1, define
Jn(x,π) = logE
x exp
c(xk, ak)
jn(x,π, p) =
Eπpx [γc(xk, ak) −R(p(·|xk, ak)‖q(·|xk, ak))].
Now we are ready to present the result that was originally proved in
[16] for Markov strategies. However, it still remains valid when arbitrary
strategies for the decision maker are considered. Therefore, for the sake of
clarity, we state the result with its proof.
Proposition 1. Let x∈X and p ∈Q(π). Then:
(a) supp∈Q(π) jn(x,π, p) ≤ Jn(x,π) for each n≥ 1,
(b) lim supn→∞ supp∈Q(π)
jn(x,π, p) ≤ γJ(x,π).
Proof. (a) Let p ∈ Q(π) be any stochastic kernel. For n = 1, we con-
clude
j1(x,π, p) ≤ E
x (γc(x,a0)) ≤ logE
γc(x,a0) = J1(x,π),
where the first inequality holds since the relative entropy is nonnegative, and
the second one is due to Jensen’s inequality. Now assume that the hypothesis
is true for some n≥ 1. Clearly,
jn+1(x,π, p) =
Eπpx [γc(xk, ak) −R(p(·|xk, ak)‖q(·|xk, ak))]
= Eπpx
[γc(xk, ak) −R(p(·|xk, ak)‖q(·|xk, ak))], n≥ 1.
6 A. JAŚKIEWICZ
Denote by π(1) the “1-shifted” strategy, that is,
(·|hk) = πk+1(·|x0, a0, hk), k ≥ 0.
Then, we have
jn+1(x,π, p)
= Eπpx [γc(x,a0) + jn(x1, π
(1), p) −R(p(·|x,a0)‖q(·|x,a0))]
≤ Eπpx (γc(x,a0))
+ Eπpx (E
x {[Jn(x1, π
(1)) −R(p(·|x,a0)‖q(·|x,a0))]|a0})
= Eπx log e
γc(x,a0)
+ Eπpx
Jn(x1, π
(1))p(dx1|x,a0) −R(p(·|x,a0)‖q(·|x,a0))
log eγc(x,a0)π0(da0|x)
eJn(x1,π
(1))q(dx1|x,a0)π0(da0|x)
eγc(x,a0)+
γc(xk,ak)q(dx1|x,a0)π0(da0|x)
≤ log
eγc(x,a0)+
γc(xk,ak)q(dx1|x,a0)π0(da0|x)
= Jn+1(x,π).
Clearly, the first inequality follows from the induction hypothesis. The third
inequality is due to Jensen’s inequality, whilst the second one follows from
Lemma A in the Appendix. Since p ∈Q(π) is arbitrary, we get the desired
conclusion.
Part (b) follows directly from part (a). �
Remark 2. Note that in the proof of Proposition 1 we did not really
have to use the fact that p ∈ Q(π). The only assumption which plays an
essential role is condition (2). Namely, it guarantees that jn(x,π, p) is well
defined for all n≥ 1, x ∈X and π ∈ Π. However, in Definition 1 we restrict
the opponent’s class of strategies to the set Q(π) in order to be able to apply
the Hardy–Littlewood theorem. In actual fact, later on it will be clear that
the set Q(π), where π ∈ Π, is sufficiently large. Namely, the supremum of
certain discounted functional costs over the set Q(π) will not change if we
add new elements to Q(π); see the proofs of Lemmas 1 and 2.
RISK-SENSITIVE CONTROL 7
Let π̃ be as in assumption (G) and let p ∈Q(π̃). Then from the Hardy–
Littlewood theorem (Theorem H.2 in [13]), we get
lim sup
(1 − β)Vβ(x, π̃, p) ≤ lim sup
jn(x, π̃, p)
and from Proposition 1(b),
lim sup
p∈Q(π̃)
jn(x, π̃, p) ≤ γJ(x, π̃).
Combining these two inequalities, we conclude that
lim sup
(1− β)Vβ(x, π̃, p) ≤ γJ(x, π̃) for every p ∈Q(π̃).
This in turn yields
lim sup
(1− β)Vβ(x) ≤ γJ(x, π̃),(4)
where Vβ(x) is the upper value of functional cost (1), that is,
Vβ(x) = inf
p∈Q(π)
Vβ(x,π, p).
Consequently, inequality (4) and assumption (G) together lead to the fol-
lowing:
Vβ(x) < +∞(5)
for each x ∈X and β ∈ (0,1). In addition, Vβ(x) ≥ 0. Now defining
ρ := inf
J(x,π), mβ := inf
Vβ(x)
and observing that
lim sup
(1 − β)mβ ≤ γρ,(6)
one can deduce that there exists a sequence of discount factors {βn} con-
verging to 1 for which
(1− βn)mβn = l,(7)
where l is a certain nonnegative constant.
8 A. JAŚKIEWICZ
3. A solution to the auxiliary discounted minimax problem. The main
thrust of this section is to solve the auxiliary discounted minimax problem
introduced in the previous section. In other words, we look for a discounted
functional equation whose solution is the function Vβ . This is done by an ap-
proximation of the above-mentioned minimax models by ones with bounded
cost functions. These models in turn are solved by a fixed point argument in
Proposition 1. Next, we show in Lemma 1 that the corresponding solutions
equal the upper values of some discounted costs on the infinite horizon. Fi-
nally, the limit passage in Lemma 2 gives the desired discounted functional
equation with the function Vβ as a solution.
We shall need the following two sets of compactness-semicontinuity as-
sumptions, which will be used alternatively.
Condition (S).
(i) The set A(x) is compact.
(ii) For each x ∈X and every Borel set D ⊂X, the function q(D|x, ·) is
continuous on A(x).
(iii) The cost function c(x, ·) is lower semicontinuous for each x ∈X.
Condition (W).
(i) The set A(x) is compact and the set-valued mapping x 7→ A(x) is
upper semicontinuous, that is, {x ∈X : A(x) ∩ B 6= ∅} is closed for every
closed set B in A.
(ii) The transition law q is weakly continuous on K, that is, the function
(x,a) 7→
u(y)q(dy|x,a), (x,a) ∈K,
is continuous function for each bounded continuous function u.
(iii) The cost function c is lower semicontinuous on K.
By Lb(X) and Bb(X), we denote the set of all bounded lower semicontin-
uous and bounded Borel measurable functions on X, respectively. Further,
let N stand for the set of positive integers. Choose N ∈ N and define the
truncated cost function
cN (x,a) = min{N,c(x,a)}.
The following result was proved under Condition (W) for bounded cost
functions by a fixed point argument; see page 72 in [10]. However, a simple
and obvious modification of the proof gives the conclusion under Condition
(S) as well.
RISK-SENSITIVE CONTROL 9
Proposition 2. Under (W) [(S)], for any discount factor β ∈ (0,1) and
a number N ∈N, there exists a unique function wNβ ∈ Lb(X) [w
β ∈Bb(X)]
such that
= min
a∈A(x)
N (x,a)
q(dy|x,a)
for each x ∈X, and
0 ≤ (1 − β)wNβ (x) ≤Nγ.(9)
Moreover, there exists a stationary strategy f0 ∈ F (possibly depending on β
and N) that attains the minimum in (8).
Let β and N be fixed just in the next lemma.
Lemma 1. Assume (W) or (S). Then, it holds
wNβ (x)
= inf
p∈Q(π)
Eπpx β
k[γcN (xk, ak) −R(p(·|xk, ak)‖q(·|xk, ak))]
for any initial state x ∈X.
Proof. Note that (8) can be rewritten in the following equivalent form:
wNβ (x) = min
a∈A(x)
γcN (x,a) + log
q(dy|x,a)
.(11)
Applying Lemma A in the Appendix to (11), we get
wNβ (x)
= min
a∈A(x)
µ∈∆(x,a)
γcN (x,a) −R(µ‖q(·|x,a)) + β
wNβ (y)µ(dy)
∆(x,a) := {µ ∈ Pr(X) :R(µ‖q(·|x,a)) < +∞}, (x,a) ∈K.
Moreover, the measure
µ0(dy)[x,a] =
q(dy|x,a)
q(dy|x,a)
achieves the supremum in (12). Put
p0(dy|x,a) = µ0(dy)[x,a] for each (x,a) ∈K.(13)
10 A. JAŚKIEWICZ
Note that p0 ∈Q(π) for any strategy π ∈ Π. This directly follows from the
definition of R(p0(·|x,a)‖q(·|x,a)) and (9). Simple calculations give the up-
per bound
R(p0(·|x,a)‖q(·|x,a)) ≤ 2
1 − β
for every (x,a) ∈K.
Let p0 be defined as in (13). By (12), we then have
wNβ (x) ≤ γc
N (x,a) −R(p0(·|x,a)‖q(·|x,a)) + β
wNβ (y)p
0(dy|x,a).
By iteration of this inequality n times, it follows
wNβ (x) ≤
βkEπp
x [γc
N (xk, ak) −R(p
0(·|xk, ak)‖q(·|xk, ak))]
+ βn+1Eπp
β (xn+1),
where π is any strategy for the controller. Now, letting n→∞ and making
use of (9), we conclude
wNβ (x) ≤
βkEπp
x [γc
N (xk, ak) −R(p
0(·|xk, ak)‖q(·|xk, ak))].
Since π is arbitrary, we get
wNβ (x) ≤ inf
βkEπp
x [γc
N (xk, ak) −R(p
0(·|xk, ak)‖q(·|xk, ak))]
≤ inf
p∈Q(π)
βkEπpx [γc
N (xk, ak)(14)
−R(p(·|xk, ak)‖q(·|xk, ak))].
Note that inequality (14) is valid because p0 ∈Q(π).
On the other hand, by (12), we can write
wNβ (x) ≥ γc
N (x, f0(x)) −R(p(·|x, f0(x))‖q(·|x, f0(x)))
wNβ (y)p(dy|x, f
0(x)),
with f0 as in Proposition 2 and any p ∈Q(f0). Proceeding along the same
line, we infer
wNβ (x) ≥
x [γc
N (xk, f
0(xk)) −R(p(·|xk, f
0(xk))‖q(·|xk, f
0(xk)))].
RISK-SENSITIVE CONTROL 11
Since p ∈Q(f0) is arbitrary, we easily deduce
wNβ (x) ≥ sup
p∈Q(f0)
x [γc
N (xk, f
0(xk))
−R(p(·|xk, f
0(xk))‖q(·|xk, f
0(xk)))]
≥ inf
p∈Q(π)
βkEπpx [γc
N (xk, ak)
−R(p(·|xk, ak)‖q(·|xk, ak))].
Finally, combining (14) with (15) completes the proof. �
In the remainder of the paper, we shall use the following notation. Let
L(X) denote the set of all lower semicontinuous functions on X, whereas
B(X) stands for the set of all Borel measurable functions on X.
Lemma 2. Let (W) [(S)] hold and β ∈ (0,1). Then, we have the follow-
(a) The function
wβ(x) := lim
wNβ (x)
is finite and nonnegative for each x ∈X. Moreover, wβ ∈L(X) [wβ ∈B(X)].
(b) The functional equation holds
ewβ(x) = min
a∈A(x)
eγc(x,a)
eβwβ(y)q(dy|x,a)
for all x ∈X. Furthermore, there exists a Borel measurable selector fβ ∈ F
of the minima in (16).
(c) For any x ∈X, wβ(x) = Vβ(x).
Proof. Let x ∈X and β ∈ (0,1) be fixed. From (10), it is easily seen
that the sequence {wNβ (x)} is nondecreasing in N. Therefore, wβ(x) =
limN→∞w
β (x) exists and by (9), it is nonnegative. Clearly, under (S),
wβ ∈B(X), whereas, under (W), wβ ∈L(X); see Proposition 10.1 in [26].
In order to prove that wβ(x) is finite for each x ∈X, observe first that,
for any π ∈ Π, p ∈Q(π) and N ∈N,
Vβ(x,π, p) =
βkEπpx [γc(xk, ak) −R(p(·|xk, ak)‖q(·|xk, ak))]
βkEπpx [γc
N (xk, ak) −R(p(·|xk, ak)‖q(·|xk, ak))].
12 A. JAŚKIEWICZ
Moreover, from Lemma 1, we have
Vβ(x) = inf
p∈Q(π)
Vβ(x,π, p)
≥ inf
p∈Q(π)
βkEπpx [γc
N (xk, ak) −R(p(·|xk, ak)‖q(·|xk, ak))]
= wNβ (x).
Hence, letting N →∞, it follows
Vβ(x) ≥ lim
wNβ (x) = wβ(x).(17)
By (5), Vβ(x) is finite for each x ∈X, so is wβ(x). This finishes the proof of
part (a).
In order to prove part (b), note that by (11) and part (a) the limit
a∈A(x)
γcN (x,a) + log
q(dy|x,a)
exists. Since the first and the second term in (18) are nondecreasing and
(W) or (S) holds, then we may interchange the limit with the minimum
(see Proposition 10.1 in [26]). Furthermore, making use of the Lebesgue
monotone convergence theorem, we conclude (16). The existence of a Borel
measurable selector fβ ∈ F follows from the compactness–semicontinuity
assumptions and Proposition D.5 in [17].
We now turn to proving part (c). Again, taking a logarithm on both sides
of (16), it follows
wβ(x) = min
a∈A(x)
γc(x,a) + log
eβwβ(y)q(dy|x,a)
.(19)
Applying Lemma A in the Appendix to (19), we easily obtain
wβ(x)
= min
a∈A(x)
µ∈∆(x,a)
γc(x,a) −R(µ‖q(·|x,a)) + β
wβ(y)µ(dy)
∆(x,a) = {µ ∈ Pr(X) :R(µ‖q(·|x,a)) < +∞}, (x,a) ∈K.
Observe that by (20), for any p ∈Q(fβ), the following holds:
wβ(x) ≥ γc(x, fβ(x)) −R(p(·|x, fβ(x))‖q(·|x, fβ(x)))
wβ(y)p(dy|x, fβ(x)).
RISK-SENSITIVE CONTROL 13
Iterating this inequality n times, we immediately obtain
wβ(x) ≥
x [γc(xk, fβ(xk))
−R(p(·|xk, fβ(xk))‖q(·|xk, fβ(xk)))]
+ βn+1E
x wβ(xn+1)(21)
x [γc(xk, fβ(xk))
−R(p(·|xk, fβ(xk))‖q(·|xk, fβ(xk)))].
Now note that, by Definition 1,
x [γc(xk, fβ(xk)) −R(p(·|xk, fβ(xk))‖q(·|xk, fβ(xk)))] ≥−C,
for some C ≥ 0 and k ≥ 1. Thus, letting n→∞ in (21), it follows
wβ(x) ≥
x [γc(xk, fβ(xk)) −R(p(·|xk, fβ(xk))‖q(·|xk, fβ(xk)))]
= Vβ(x, fβ, p).
Since p ∈Q(fβ) is arbitrary, we see that
wβ(x) ≥ sup
p∈Q(fβ)
Vβ(x, fβ, p) ≥ Vβ(x).(22)
Inequalities (17) and (22) combined conclude the proof of part (c). �
4. A solution to the risk-sensitive control problem. For any x ∈X and
any discount factor β ∈ (0,1), define
hβ(x) := Vβ(x) −mβ
with mβ = infx∈X Vβ(x). Obviously, hβ is nonnegative.
The following boundedness assumption is supposed to hold true. As men-
tioned in the Introduction, we put off discussing it until Section 5:
Condition (B). For any x ∈X , supβ∈(0,1) hβ(x) < +∞.
Remark 3. A similar assumption and its equivalent variants were used
to study the expected average cost criterion for Markov decision processes
in the risk-neutral setting [17, 27, 28]. Roughly speaking, Hernández-Lerma
and Lasserre [17], Schäl [27], and Sennott [28] assume that the family of the
so-called normalized β-discounted cost functions is bounded. This assump-
tion, however, simply holds for ergodic Markov decision processes. More
14 A. JAŚKIEWICZ
precisely, if the n-step transition probabilities converge to the unique in-
variant probability measure geometrically fast, and the cost functions are
bounded (or more generally satisfy a certain growth hypothesis), then the
aforementioned family of functions is pointwise relatively compact [21, 22].
It is worth pointing out that this requirement is crucial to obtain the opti-
mality inequality in the risk-neutral case; see [27, 28]. In Section 5 we provide
an example that illustrates that also in the risk-sensitive case Condition (B)
cannot be weakened.
We shall need the following two versions of Fatou’s lemma for converging
measures.
Lemma 3. Let {µn} be a sequence of probability measures converging to
µ ∈ Pr(X) and let {hn} be a sequence of measurable nonnegative functions
on X. Then,
h(y)µ(dy) ≤ lim inf
hn(y)µn(dy)
in the following cases:
(a) {µn} converges setwise to µ [i.e.,
f(y)dµn(y) →
f(y)dµ(y)∀f ∈
Bb(X)], and h(x) = lim infn→∞ hn(x);
(b) {µn} converges weakly to µ, and h(x) = inf{lim infn→∞ hn(xn) :xn →
x}; moreover, h ∈ L(X).
Proof. Part (a) is due to Royden [25], page 231, whereas part (b) was
proved by Serfozo [29]. For the proof of lower semicontinuity of h, the reader
is referred to Lemma 3.1 in [22]. �
Now we are in a position to state the main result of the paper. This theo-
rem concerns a study of the risk-sensitive average cost optimality inequality,
which is sufficient to establish the existence of an optimal stationary policy.
Theorem 1. Assume (B) and (W) [or (S)]. Then, for each risk factor
γ > 0, there exist a constant l̂ and a nonnegative function h ∈ L(X) [h ∈
B(X)] and f̂ ∈ F such that
h(x) + l̂ ≥ min
a∈A(x)
γc(x,a) + log
eh(y)q(dy|x,a)
= γc(x, f̂(x)) + log
eh(y)q(dy|x, f̂(x))
RISK-SENSITIVE CONTROL 15
for all x ∈X. Moreover,
= inf
J(x,π) = J(x, f̂).
In other words, l̂/γ is the optimal risk-sensitive average cost and f̂ is a
risk-sensitive average cost optimal stationary policy.
Remark 4. (a) There are two papers [16, 27] that can be treated as
predecessors of our work. They both deal with the optimality inequality but
within two different frameworks. The first work [16] establishes the optimal-
ity equation for the risk-sensitive dynamic programming on a denumarable
state space. In the other one, the result is obtained for Markov control pro-
cesses on an uncountable state space for the risk factor γ = 0. From this
point of view, our result is an extention of Theorem 4.1 in [16] to a general
state space and Theorem 3.8 in [27] to the risk-sensitive case. Moreover, the
common feature of the discussed results is that their proofs are based on the
vanishing discount factor approach. Our proof also relies on this method, and
similarly, as in [27] or [21, 22], makes use of the Fatou lemmas for setwise
and weakly convergent measures.
(b) Finally, it is also worth mentioning that there are papers studying the
optimality equation in the risk-sensitive dynamic programming, which is of
the following form:
h(x) + l̂ = min
a∈A(x)
γc(x,a) + log
eh(y)q(dy|x,a)
.(24)
The constant l̂
is (under suitable assumptions) an optimal cost with respect
to the risk-sensitive average cost criterion. Let us mention and discuss a few
representative papers that deal with equation (24). In [8, 15] Markov control
models satisfying a simultaneous Doeblin condition, on a finite and countable
state space, respectively, are considered. The cost functions are supposed to
be bounded and the risk factor must be sufficiently small. Otherwise, as
argued in [8], the optimality equation need not have a solution.
In [10] Di Masi and Stettner extend the result to a general state space
by retaining bounded cost functions and replacing a simultaneous Doeblin
condition with a very strong assumption on transition probabilities. In [11],
however, they replace this assumption by one imposed on the risk coeffi-
cient. Finally, the class of Markov control models that requires neither any
ergodicity conditions nor the smallness of the risk factor was pointed out by
Jaśkiewicz in [20].
Fairly recently Borkar and Meyn [5] considered Markov decision processes
with unbounded cost functions on a denumarable state space. Their result
16 A. JAŚKIEWICZ
assumes the following: the state space is irreducible under all Markov poli-
cies, the costs are norm-like, and there exists a policy that induces a finite
average risk-sensitive cost. Moreover, their proof is based on a multiplicative
ergodic theorem that was studied in more detail in [1].
Proof of Theorem 1. Let {βn} be a sequence of discount factors
converging to 1 for which (7) holds. Defining
l̂ := l = lim
(1 − βn)mβn
and applying (6), we note that
≤ inf
J(x,π)(25)
for any x ∈X. Assume for a while that inequality (23) is satisfied and there
exists f̂ ∈ F as in the statement of Theorem 1. We prove that f̂ is an optimal
policy. From (23), we have
h(x) ≥ γc(x, f̂(x)) − l̂ + log
eh(y)q(dy|x, f̂(x)).
By iteration of this inequality n times, we obtain
h(x) ≥ logEπx exp
γc(xk, f̂(xk)) + h(xn+1)
− (n+ 1)l̂.
Since h is nonnegative, we infer
+ l̂≥
Jn+1(x, f̂)
with Jn+1(x, f̂) defined in (3). Letting n→∞, it follows
≥ J(x, f̂), x ∈X.(26)
Hence, (25) and (26) together imply
= J(x, f̂) = inf
J(x,Π)
for each x ∈X.
We next focus on showing inequality (23). Let n≥ 1 and put hn := hβn ,
fn := fβn. Note that (19) can be rewritten in the following form:
(1 − βn)mβn + hn(x) = min
a∈A(x)
γc(x,a) + log
eβnhn(y)q(dy|x,a)
= γc(x, fn(x)) + log
eβnhn(y)q(dy|x, fn(x)).
RISK-SENSITIVE CONTROL 17
(i) Assume first (S) and define
h(x) = lim inf
hn(x).
Taking the lim inf on both sides of (27), we get
lim inf
((1 − βn)mβn + hn(x))
= l̂ + h(x) = lim inf
a∈A(x)
γc(x,a) + log
eβnhn(y)q(dy|x,a)
Making use of Lemma 3(a) and the measurable selection theorem (see Propo-
sition D.5(a) in [17]), one can prove that there exists f̂ ∈ F such that (23)
holds.
(ii) Now assume (W). Fix x0 ∈X and choose any xn → x0, n→∞. Take
a subsequence {nk} of positive integers such that
lim inf
hn(xn) = lim
hnk(xnk).
Then by (27),
lim inf
((1− βn)mβn + hn(xn))
= l̂ + lim inf
hn(xn) = l̂ + lim
hnk(xnk)
= lim
a∈A(xnk )
γc(xnk , a) + log
eβnkhnk (y)q(dy|xnk , a)
= lim
γc(xnk , fnk(xnk)) + log
eβnkhnk (y)q(dy|xnk , fnk(xnk))
Note that G = {x0} ∪ {xn} is compact in X. From the upper semicontinu-
ity of x 7→A(x), compactness of every A(z) and Berge’s theorem (see [2] or
Theorem 7.4.2 in [23]), it follows that
z∈GA(z) is compact in A. There-
fore, {fnk(xnk)} has a subsequence converging to some a0 ∈A. By (W)(i),
a0 ∈ A(x0), that is, (x0, a0) ∈ K. Without loss of generality, assume that
fnk(xnk) → a0, k →∞. By the lower semicontinuity of the cost function c
and (28), we have
l̂ + lim inf
hn(xn) ≥ γc(x0, a0) + lim
eβnkhnk (y)q(dy|xnk , fnk(xnk)).
This and Lemma 3(b) imply that
l̂ + lim inf
hn(xn) ≥ γc(x0, a0) + log
eh̃(y)q(dy|x0, a0),
where eh̃ is the generalized lim inf of the sequence eh̃k = ehnk . Clearly, h≤ h̃.
By Lemma 3(b), h ∈L(X). Thus,
l̂ + lim inf
hn(xn) ≥ γc(x0, a0) + log
eh(y)q(dy|x0, a0).(29)
18 A. JAŚKIEWICZ
Since xn → x0 was chosen arbitrarily, we infer from (29) that
l̂ + h(x0) ≥ γc(x0, a0) + log
eh(y)q(dy|x0, a0).
The last inequality shows that, for any x ∈X, there exists an ax ∈A(x) such
l̂ + h(x) ≥ γc(x,ax) + log
eh(y)q(dy|x,ax)
≥ min
a∈A(x)
γc(x,a) +
eh(y)(y)q(dy|x,a)
By our compactness–semicontinuity assumptions and Proposition D.5(b) in
[17], there exists some f̂ ∈ F such that (23) holds. �
5. A discussion. This section is devoted to a discussion of Condition (B).
We start with revisiting Example 3.1 in [8].
Example 1. Put X = {0,1}, A = {a}, c(x) := c(x,a) = x and the tran-
sition matrix is as follows:
ρ 1 − ρ
where ρ ∈ (0,1). Recall that the following was proved.
Let us consider three cases for the risk factor γ:
(I) γ <− log(1− ρ),
(II) γ = − log(1− ρ),
(III) γ >− log(1− ρ).
Then if (I) or (II) hold, the optimal risk-sensitive average cost equals 0
and is independent of the initial state. In case (III) we have J∗(0) = 0 and
J∗(1) = 1 +
log(1−ρ)
> 0. In addition, it is interesting to observe that, for
(II) and (III) cases, there does not exist a function h :X 7→ R such that
optimality inequality (23) is satisfied. Indeed, to see this take x = 1 and
consider (III). The optimality inequality is then as follows:
γJ∗(1) + h(1) = γ + log(1 − ρ) + h(1) ≥ γ + log(eh(1)(1− ρ) + eh(0)ρ).
Note that the right-hand side is strictly greater than γ + log(eh(1)(1 − ρ)),
which equals to the left-hand side. Similar calculations for case (II) also
lead to a contradiction. Hence, although an optimal cost is constant, the
optimality inequality need not have a solution.
Now we turn to checking Condition (B). Let Vβ be as in Lemma 2. Clearly,
Vβ = w
β for N ≥ 1 and Vβ(0) = 0. Then, by (8) under (I), we get
Vβ(1) = γ + log[e
βVβ(1)(1 − ρ) + ρ] < γ + log[eVβ(1)(1 − ρ) + ρ].
RISK-SENSITIVE CONTROL 19
Hence,
Vβ(1) < log
eγ(1− ρ)
1− eγ(1− ρ)
∀β ∈ (0,1),
and consequently, supβ∈(0,1) hβ(x) < +∞.
Now let the risk factor γ be as in (III). Then by (8),
Vβ(1) > γ + log(1 − ρ) + βVβ(1),
which in turn implies that
Vβ(1) >
γ + log(1− ρ)
Thus, hβ(1) = Vβ(1) goes to the infinity when β ր 1.
For case (II), we obtain
Vβ(1) = − log(1− ρ) + log[e
βVβ(1)(1− ρ) + ρ]
= βVβ(1) + log
1 + e−βVβ(1)
1 − ρ
If Vβ(1) ր +∞ when β ր 1, then the right-hand side of (31) also goes to the
infinity. On the contrary, assume that supβ∈(0,1) Vβ(1) ≤C for some constant
C > 0. Then,
Vβ(1) ≥
log[1 + e−Cρ/(1 − ρ)]
which leads to a contradiction when β ր 1. In consequence, in case (II) the
family {hβ(1)} does not satisfy Condition (B) either.
Therefore, the following conclusion can be drawn. Condition (B) is nec-
essary to obtain a solution to the optimality inequality.
For a verification of Condition (B), one can use Lemma 4 below. For a
similar result in the risk-neutral, case we refer to [27, 28]. For some η ≥ 0,
define the stopping time
τ = τ(β) := inf{n≥ 0 :Vβ(xn) ≤mβ + η}.
Lemma 4. For η ≥ 0, β ∈ (0,1) and x ∈X,
hβ(x) ≤ η + inf
logEπx exp
γc(xk, ak)
Proof. By Lemma 2(b), (c) and the fact that Vβ(y) ≥ 0, y ∈ X , we
Vβ(x) = min
a∈A(x)
γc(x,a) + log
eβVβ(y)q(dy|x,a)
< γc(x,a) + log
eVβ(y)q(dy|x,a)
20 A. JAŚKIEWICZ
for each x ∈X. Subtracting mβ from both sides in (32), we obtain
Vβ(x) −mβ < γc(x,a) + log
e(Vβ(y)−mβ )q(dy|x,a).
Iteration of this inequality up to the stopping time τ yields
Vβ(x) −mβ < logE
c(xk,ak)+η
= η + logEπx exp
c(xk, ak)
Since π ∈ Π is an arbitrary policy, we easily get the conclusion. �
Note that the fact
Eπx exp
γc(xk, ak)
< +∞(33)
has the following interpretation: before the process will reach “good states,”
the incurred costs at “early stages” should not be too large. Indeed, let us
define a set D as follows. We say that
x ∈D iff Vβ(x) ≤mβ + η
for a certain η ≥ 0. Clearly, D 6= ∅. Denote by τD the first return time of
the process, governed by fβ, to set D. Certainly, if (33) holds with τ := τD,
then Condition (B) is satisfied.
In Example 1 we can take D = {0} and η = 0, since Vβ(0) ≤ 0 + 0. If γ is
as in (I), then (33) holds:
E1 exp
τ0−1∑
γc(xk)
enγ(1− ρ)n−1ρ =
eγ(1− ρ)
1− eγ(1− ρ)
In other cases (33) fails to hold and, in addition, the earlier calculations
show that hβ(1) = +∞.
Summing up, the presented example shows that, without Condition (B)
imposed on the family of functions {hβ(x)}, β ∈ (0,1), a solution to the
optimality inequality need not exist, and moreover, the optimal risk-sensitive
average cost may depend on the initial state. In view of the above discussion,
Condition (B) is designed to prevent the accrual of infinite expected costs.
Namely, the costs incurred at transient states, that may be occupied only
at “early stages,” have an important and definite influence on a long-run
performance measure. Therefore, Condition (B) requires the model to be
sort of communicating insofar as certain sets of “good states” to be reached
sufficiently fast. Then, the optimal risk-sensitive average cost is constant and
the optimality inequality takes place. In addition, it is worth mentioning that
RISK-SENSITIVE CONTROL 21
the ergodicity itself of a Markov process/chain does not help so much as in
the risk-neutral case. In other words, for an ergodic Markov chain, it may
happen that the optimal risk-sensitive average cost depends on the initial
state as in Example 1. Moreover, in this example one can even prove in
a straightforward way that under case (I) [either under Condition (B) or
for sufficiently small risk factors], the optimality equation (24) is satisfied.
Therefore, it would be interesting to know whether Condition (B) (together
with some compactness–continuity assumptions) is sufficient to obtain a
solution to the optimality equation. There is a conjecture that, since in the
risk-neutral case a counterpart of Condition (B) is not sufficient [7], neither
is it in the risk-sensitive setting. But this question is beyond the scope of
the paper and remains open.
APPENDIX
The lemma below establishes a variational formula for the logarithmic
moment-generating function. The reader is referred to Theorem 4.5.1 and
Proposition 1.4.2 in [12] for its proof.
Lemma A. Let X be a Polish space, h a measurable function mapping
on X into R, which is either bounded from below or bounded from above,
and ν a probability measure on X .
(a) Then, we have the variational formula
ehdν = sup
−R(µ‖ν) +
where
∆ = {µ ∈ Pr(X ) :R(µ‖ν) < +∞}.
(b) Let µ0 denote the probability measure on X , which is µ0 ≪ ν and
satisfies
(x) =
eh(x)∫
eh dν
Then, the supremum in the variational formula is attained uniquely at µ0.
Acknowledgments. A part of this research was done while the author
was a Humboldt research fellow and visiting the University of Ulm. The
author gratefully acknowledges support from the Alexander von Humboldt
Foundation.
The second part of this paper was written at the Institute of Mathematics
and Computer Science, Wroc law University of Technology.
The author is greatly indebted to Professor Ulrich Rieder for drawing
her attention to paper [16], suggesting the problem and for several helpful
conversations.
22 A. JAŚKIEWICZ
REFERENCES
[1] Balaji, S. and Meyn, S. P. (2000). Multiplicative ergodicity and large deviations for
an irreducible Markov chains. Stochastic Process. Appl. 90 123–144. MR1787128
[2] Berge, E. (1963). Topological Spaces. MacMillan, New York.
[3] Bielecki, T., Hernández-Hernández, D. and Pliska, S. (1999). Risk-senisitive
control of finite state Markov chains in discrete time, with applications to port-
folio managment. Math. Methods Oper. Res. 50 167–188. MR1732397
[4] Bielecki, T. and Pliska, S. (1999). Risk-senisitive dynamic asset managment. Appl.
Math. Optim. 39 337–360. MR1675114
[5] Borkar, V. S. and Meyn, S. P. (2002). Risk-sensitive optimal control for
Markov decision processes with monotone cost. Math. Oper. Res. 27 192–209.
MR1886226
[6] Brown, L. D. and Purves, R. (1973). Measurable selections of extrema. Ann.
Statist. 1 902–912. MR0432846
[7] Cavazos-Cadena, R. (1991). A counterexample on the optimality equation in
Markov decision chains with the average cost criterion. Systems Control Lett. 16
387–392.
[8] Cavazos-Cadena, R. and Fernández-Gaucherand, E. (1999). Controlled Markov
chains with risk-sensitive criteria: Average cost, optimal equations and optimal
solutions. Math. Methods Oper. Res. 49 299–324. MR1687362
[9] Dai Pra, P., Meneghini, L. and Runggaldier, W. J. (1996). Some connections
between stochastic control and dynamic games. Math. Control Signals Systems
9 303–326. MR1450355
[10] Di Masi, G. B. and Stettner,  L. (2000). Risk-sensitive control of discrete-time
Markov processes with infinite horizon. SIAM J. Control Optim. 38 61–78.
MR1740607
[11] Di Masi, G. B. and Stettner,  L. (2000). Infinite horizon risk sensitive control of
discrete time Markov processes with small risk. Systems Control Lett. 40 15–20.
MR1829070
[12] Dupuis, P. and Ellis, R. S. (1997). A Weak Convergence Approach to the Theory
of Large Deviations. Wiley, New York. MR1431744
[13] Filar, J. and Vrieze, K. (1997). Competitive Markov Decision Processes. Springer,
New York. MR1418636
[14] Fleming, W. H. and Hernández-Hernández, D. (1997). Risk-sensitive control of
finite state machines on an infinite horizon. SIAM J. Control Optim. 35 1790–
1810. MR1466928
[15] Hernández-Hernández, D. and Marcus, S. I. (1996). Risk sensitive control of
Markov processes in countable state space. Systems Control Lett. 29 147–155.
[Corrigendum (1998) Systems Control Lett. 34 105–106.] MR1422212
[16] Hernández-Hernández, D. and Marcus, S. I. (1999). Existence of risk-sensitive
optimal stationary policies for controlled Markov processes. Appl. Math. Optim.
40 273–285. MR1709324
[17] Hernández-Lerma, O. and Lasserre, J. B. (1993). Discrete-Time Markov Control
Process: Basic Optimality Criteria. Springer, New York. MR1363487
[18] Howard, R. A. and Matheson, J. E. (1972). Risk-sensitive Markov decision pro-
cesses. Management Sci. 18 356–369. MR0292497
[19] Jacobson, D. H. (1973). Optimal stochastic linear systems with exponential per-
formance criteria and their relation to deterministic differential games. IEEE
Trans. Automat. Control 18 124–131. MR0441523
http://www.ams.org/mathscinet-getitem?mr=1787128
http://www.ams.org/mathscinet-getitem?mr=1732397
http://www.ams.org/mathscinet-getitem?mr=1675114
http://www.ams.org/mathscinet-getitem?mr=1886226
http://www.ams.org/mathscinet-getitem?mr=0432846
http://www.ams.org/mathscinet-getitem?mr=1687362
http://www.ams.org/mathscinet-getitem?mr=1450355
http://www.ams.org/mathscinet-getitem?mr=1740607
http://www.ams.org/mathscinet-getitem?mr=1829070
http://www.ams.org/mathscinet-getitem?mr=1431744
http://www.ams.org/mathscinet-getitem?mr=1418636
http://www.ams.org/mathscinet-getitem?mr=1466928
http://www.ams.org/mathscinet-getitem?mr=1422212
http://www.ams.org/mathscinet-getitem?mr=1709324
http://www.ams.org/mathscinet-getitem?mr=1363487
http://www.ams.org/mathscinet-getitem?mr=0292497
http://www.ams.org/mathscinet-getitem?mr=0441523
RISK-SENSITIVE CONTROL 23
[20] Jaśkiewicz, A. (2006). A note on risk-sensitive control of invariant models. Technical
Report, Wroc law University of Technology.
[21] Jaśkiewicz, A. and Nowak, A. S. (2006). On the optimality equation for average
cost Markov control processes with Feller transition probabilities. J. Math. Anal.
Appl. 316 495–509. MR2206685
[22] Jaśkiewicz, A. and Nowak, A. S. (2006). Zero-sum ergodic stochastic games with
Feller transition probabilities. SIAM J. Control Optim. 45 773–789. MR2247715
[23] Klein, E. and Thompson, A. C. (1984). Theory of Correspondences. Wiley, New
York. MR0752692
[24] Neveu, J. (1965). Mathematical Foundations of the Calculus of Probability. Holden-
Day, San Francisco, CA. MR0198505
[25] Royden, H. L. (1968). Real Analysis. MacMillan, New York. MR0151555
[26] Schäl, M. (1975). Conditions for optimality in dynamic programming and for the
limit n-stage optimal policies to be optimal. Z. Wahrsch. Verw. Gebiete 32 179–
196. MR0378841
[27] Schäl, M. (1993). Average optimality in dynamic programming with general state
space. Math. Oper. Res. 18 163–172. MR1250112
[28] Sennott, L. I. (1999). Stochastic Dynamic Programming and the Control of Queue-
ing Systems. Wiley, New York. MR1645435
[29] Serfozo, R. (1982). Convergence of Lebesgue integrals with varying measures.
Sankhyã Ser. A 44 380–402. MR0705462
[30] Stettner,  L. (1999). Risk sensitive portfolio optimization. Math. Methods Oper.
Res. 50 463–474. MR1731299
[31] Whittle, P. (1990). Risk-Sensitive Optimal Control. Wiley, Chichester. MR1093001
Institute of Mathematics and Computer Science
Wroc law University of Technology
Wybrzeże Wyspiańskiego 27
PL-50-370 Wroc law
Poland
E-mail: ajaskiew@im.pwr.wroc.pl
http://www.ams.org/mathscinet-getitem?mr=2206685
http://www.ams.org/mathscinet-getitem?mr=2247715
http://www.ams.org/mathscinet-getitem?mr=0752692
http://www.ams.org/mathscinet-getitem?mr=0198505
http://www.ams.org/mathscinet-getitem?mr=0151555
http://www.ams.org/mathscinet-getitem?mr=0378841
http://www.ams.org/mathscinet-getitem?mr=1250112
http://www.ams.org/mathscinet-getitem?mr=1645435
http://www.ams.org/mathscinet-getitem?mr=0705462
http://www.ams.org/mathscinet-getitem?mr=1731299
http://www.ams.org/mathscinet-getitem?mr=1093001
mailto:ajaskiew@im.pwr.wroc.pl
	Introduction and the model
	Preliminaries
	A solution to the auxiliary discounted minimax problem
	A solution to the risk-sensitive control problem
	A discussion
	Appendix
	Acknowledgments
	References
	Author's addresses
