# Nonuniqueness versus Uniqueness of Optimal Policies in Convex Discounted Markov Decision Processes

Authors: Raúl Montes-de-Oca; Enrique Lemus-Rodríguez; Francisco Sergio Salem-Silva
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

From the classical point of view, it is important to determine if in a Markov decision process (MDP), besides their existence, the uniqueness of the optimal policies is guaranteed. It is well known that uniqueness does not always hold in optimization problems (for instance, in linear programming). On the other hand, in such problems it is possible for a slight perturbation of the functional cost to restore the uniqueness. In this paper, it is proved that the value functions of an MDP and its cost perturbed version stay close, under adequate conditions, which in some sense is a priority. We are interested in the stability of Markov decision processes with respect to the perturbations of the cost-as-you-go function.


---

## Body

## 1. Introduction

From the classical point of view (for instance, in Hadamard’s concept of well-posedness [1]) in a mathematical modeling problem, it is crucial that both the existence and the uniqueness are secured. But, in optimization, neither of these is guaranteed, and even if extra conditions ensure the existence of optimizers, their uniqueness will not automatically follow. For instance, in linear programming, we even have the extreme case that when there are two different optimal vectors all of their convex linear combinations become optimal automatically. But a slight perturbation of the cost functional will “destroy" most of the optimizers. In this sense, nonuniqueness in linear programming is highly unstable. This question is of interest with respect to the standard discounted Markov decision model, as in [2], which presents conditions that guarantee the uniqueness of the optimal policies.In this paper, we study a family of perturbations of the cost of an MDP and establish that, under convexity and adequate bounds, the value functions of both the original and the cost-perturbed Markov decision processes (MDPs) are uniformly close. This result will eventually help us determine whether both the uniqueness and the nonuniqueness are stable with respect to this kind of perturbation.The structure of this paper is simple. Firstly, the preliminaries and assumptions of the model are outlined. Secondly, the main theorem is stated and proved, followed by the main example. A brief section with the concluding remarks closes the paper.


## 2. Preliminaries: Discounted MDPs and Convexity Assumptions

Let(X,A,{A(x):x∈X},Q,c) be a Markov control model (see [3] for details and terminology) which consists of the state space X, the control (or action) set A, the transition law Q, and the cost-per-stage c. It is assumed that both X and A are subsets of ℝ (this is supposed for simplicity, but it is also possible to present the theory of this paper considering that X and A are subsets of Euclidean spaces of the dimension greater than one). For each x∈X, there is a nonempty measurable set A(x)⊂A whose elements are the feasible actions when the state of the system is x. Define 𝕂∶={(x,a):x∈X,a∈A(x)}. Finally, the cost-per-stage c is a nonnegative and measurable function on 𝕂.LetΠ be the set of all (possibly randomized, history-dependent) admissible policies. By standard convention, a stationary policy is identified with a measurable function f:X→A such that f(x)∈A(x) for all x∈X. The set of stationary polices is denoted by 𝔽. For every π∈Π and an initial state x∈X, let
(1)V(π,x)=Exπ[∑t=0∞‍αtc(xt,at)]
be the total expected discounted cost when using the policy π, given the initial state x. The number α∈(0,1) is called the discount factor (α is assumed to be fixed). Here {xt} and {at} denote the state and the control sequences, respectively, and Exπ is the expectation operator. A policy π* is said to be optimal if V(π*,x)=V*(x) for all x∈X, where V*(x)=infπ∈ΠV(π,x), x∈X. V* is called the optimal value function. The following assumption will also be taken into consideration.Assumption 1.
(a)c is lower semicontinuous and inf-compact on 𝕂 (i.e., for every x∈X and r∈ℝ the set {a∈A(x):c(x,a)≤r} is compact).
(b) The transition lawQ is strongly continuous, that is, w(x,a)=∫‍u(y)Q(dy∣x,a), (x,a)∈𝕂 is continuous and bounded on 𝕂, for every measurable bounded function u on X.
(c) There exists a policyπ such that V(π,x)<∞, for each x∈X.Remark 2.
The following consequences of Assumption1 are well known (see Theorem 4.2.3 and Lemma  4.2.8 in [3]).(a)
The optimal value functionV* is the solution of the optimality equation (OE), that is, for all x∈X,
(2)V*(x)=mina∈A(x){c(x,a)+α∫‍V*(y)Q(dy∣x,a)}.There is alsof*∈𝔽 such that
(3)V*(x)=c(x,f*(x))+α∫‍V*(y)Q(dy∣x,f*(x)),x∈X,andf* is optimal.(b)
For everyx∈X, vn(x)↑V*(x), with vn defined as
(4)vn(x)=mina∈A(x){c(x,a)+α∫‍vn-1(y)Q(dy∣x,a)},x∈X,n=1,2,…, and v0(x)=0. Moreover, for each n, there is fn∈𝔽 such that for each x∈X,
(5)mina∈A(x){c(x,a)+α∫‍vn-1(y)Q(dy∣x,a)}=c(x,fn(x))+α∫‍vn-1(y)Q(dy∣x,fn(x)).Let(X,A,{A(x):x∈X},Q,c) be a fixed Markov control model. Take M as the MDP with the Markov control model (X,A,{A(x):x∈X},Q,c). The optimal value function, the optimal policy which comes from (3), and the minimizers in (5) will be denoted for M by V*, f*, and fn, n=1,2,…, respectively. Also let vn, n=1,2,…, be the value iteration functions for M. Let G(x,a) ∶= c(x,a) + α∫‍V*(y)Q(dy∣x,a), (x,a)∈𝕂.It will be also supposed that the MDPs taken into account satisfy one of the following Assumptions3 or 4.Assumption 3.
(a)X and A are convex.
(b)(1-λ)a+a′∈A((1-λ)x+x′) for all x, x′∈X, a∈A(x), a′∈A(x′), and λ∈[0,1]. Besides, it is assumed that if x and y∈X, x<y, then A(y)⊆A(x), and A(x) are convex for each x∈X.
(c)Q is induced by a difference equation xt+1=F(xt,at,ξt), with t=0,1,…, where F:X×A×S→X is a measurable function and {ξt} is a sequence of independent and identically distributed (i.i.d.) random variables with values in S⊆ℝ, and with a common density Δ. In addition, we suppose that F(·,·,s) is a convex function on 𝕂, for each s∈S, and if x and y∈X, x<y, then F(x,a,s)≤F(y,a,s) for each a∈A(y) and s∈S.
(d)c is convex on 𝕂, and if x and y∈X, x<y, then c(x,a)≤c(y,a), for each a∈A(y).Assumption 4.
(a) The same as Assumption3(a).
(b)(1-λ)a+a′∈A((1-λ)x+x′) for all x, x′∈X, a∈A(x), a′∈A(x′), and λ∈[0,1]. Besides, A(x) is assumed to be convex for each x∈X.
(c)Q is given by the relation xt+1=γxt+δat+ξt, t=0,1,…, where {ξt} are i.i.d. random variables taking values in S⊆ℝ with the density Δ, γ and δ are real numbers.
(d)c is convex on 𝕂.Remark 5.
Assumptions3 and 4 are essentially the same as assumptions C1 and C2 in pages 419–420 of reference [2], with the difference that we are now able to assume that the function c(·,·) is convex and not necessarily strictly convex. (in fact, in [2], Conditions C1 and C2 take into account the more general situation in which both X and A are subsets of Euclidean spaces of the dimension greater than one). Also note that it is possible to obtain that each of Assumptions 3 and 4 implies that, for each x∈X, G(x,·) is convex but not necessarily strictly convex (hence, M does not necessarily have a unique optimal policy). The proof of this fact is a direct consequence of the convexity of the cost function c and of the proof of Lemma  6.2 in [2].


## 3. Main Result and an Example

Forϵ>0, consider the following MDP denoted by Mϵ with the Markov control model (X,A,{A(x)∣x∈X},Q,c*), where c*(x,a)=c(x,a)+ϵa2, (x,a)∈𝕂, where c is the cost function for M. Observe that both MDPs M and Mϵ coincide in the components of the Markov control model except for the cost function; moreover, 𝔽 is the same set in both models. Additionally we suppose that.Assumption 6.
There is a policyϕ such that Exϕ[∑t=0∞αtc*(xt,at)]<∞, for each x∈X.Remark 7.
Suppose that, forM, Assumption 1 holds. Then, it is direct to verify that if Mϵ satisfies Assumption 6, then it also satisfies Assumption 1.ForMϵ, let W*, g*, and gn, n=1,2,…, denote the optimal value function, the optimal policy which comes from (3), and the minimizers in (5), respectively. Moreover, let wn, n=1,2,…, be the corresponding value iteration functions for Mϵ.Remark 8.
Suppose that, forM, one of Assumptions 3 or 4 holds. Then, notice that as c is a convex function, it is trivial to prove that c* is strictly convex. Then, under Assumption 6, it follows that Mϵ satisfies C1 or C2 in [2] and that G* is strictly convex, where G*(x,a)=c*(x,a)+α∫‍W*(y)Q(dy∣x,a), (x,a)∈𝕂, so g* is unique.LetΘ:X→ℝ, so that Θ(x)≥W*(x) and Θ(x)≥V*(x), x∈X, and take, for each x∈X, B(x)={a∈A(x):c(x,a)≤Θ(x)} and B*(x)={a∈A(x):c*(x,a)≤Θ(x)}.Remark 9.
It is easy to verify, using Assumption1, that for each x∈X, B(x) and B*(x) are nonempty and compact. Moreover, since c≥0 and from Remark 2, fn(x), f*(x)∈B(x); gn(x), g*(x)∈B*(x) for each x∈X and n≥1. It is also trivial to prove that, for each x∈X, B*(x)⊆B(x); hence fn(x), f*(x), gn(x), g*(x)∈B(x), for each x∈X and n≥1.Condition 10.
There exists a measurable functionZ:X→ℝ, which may depend on α, such that c*(x,a)-c(x,a)=ϵa2≤ϵZ(x), and ∫‍Z(y)Q(dy∣x,a)≤Z(x) for each x∈X and a∈B(x).Remark 11.
With respect to the existence of the functionZ mentioned in Condition 10 that satisfies that ∫‍Z(y)Q(dy∣x,a)≤Z(x) for each x∈X and a∈B(x), it is important to note that this kind of requirement has been previously used in the unbounded MDPs literature (see, for instance, the Remarks presented on page 578 of [4]).Theorem 12.
Suppose that Assumptions1 and 6 hold, and that, for M, one of Assumptions 3 or 4 holds. Let ϵ be a positive number. Then,(a)
ifA is compact, |W*(x)-V*(x)|≤ϵK2/(1-α), x∈X, where K is the diameter of a compact set D such that 0∈D and A⊆D;(b)
under Condition10, |W*(x)-V*(x)|≤ϵZ(x)/(1-α), x∈X.Proof.
The proof of case (a) follows from the proof of case (b) given thatZ(x)=K2, x∈X (observe that in this case, if a∈A, then a2=(a-0)2≤K2).
(b) Assume thatM satisfies Assumption 3 (the proof for the case in which M satisfies Assumption 4 is similar).
Firstly, for eachx∈X,
(6)w1(x)-v1(x)=mina∈A(x)c*(x,a)-mina∈A(x)c(x,a)≥c*(x,g1(x))-c(x,g1(x))=ϵ(g1(x))2≥0,(7)|w1(x)-v1(x)|=w1(x)-v1(x)=mina∈A(x)c*(x,a)-mina∈A(x)c(x,a)(8)≤c*(x,f1(x))-c(x,f1(x))(9)=ϵ(f1(x))2(10)≤ϵZ(x).
Secondly, assume that for some positive integern and for each x∈X,
(11)0≤wn(x)-vn(x)=|wn(x)-vn(x)|≤(1+α+α2+⋯+αn)ϵZ(x).
Consequently, using Condition10, for each x∈X,
(12)wn+1(x)-vn+1(x)(13)=mina∈A(x)[c*(x,a)+α∫‍wn(y)Q(dy∣x,a)]-mina∈A(x)[c(x,a)+α∫‍vn(y)Q(dy∣x,a)]≤[c*(x,fn(x))+α∫‍wn(y)Q(dy∣x,fn(x))]-[c(x,fn(x))+α∫‍vn(y)Q(dy∣x,fn(x))]=c*(x,fn(x))-c(x,fn(x))+α∫‍[wn(y)-vn(y)]Q(dy∣x,fn(x))≤ϵZ(x)+α(1+α+α2+⋯+αn)ϵZ(x)=(1+α+α2+⋯+αn+1)ϵZ(x).
On the other hand, from (11) and the fact that c*(x,a)-c(x,a)=ϵa2, a∈A(x), for each x∈X,
(14)wn+1(x)-vn+1(x)=mina∈A(x)[c*(x,a)+α∫‍wn(y)Q(dy∣x,a)]-mina∈A(x)[c(x,a)+α∫‍vn(y)Q(dy∣x,a)]≥[c*(x,gn(x))+α∫‍wn(y)Q(dy∣x,gn(x))]-[c(x,gn(x))+α∫‍vn(y)Q(dy∣x,gn(x))]=c*(x,gn(x))-c(x,gn(x))+α∫‍[wn(y)-vn(y)]Q(dy∣x,fn(x))≥0.
In conclusion, combining (10), (13), and (14), it is obtained that, for each x∈X, (11) holds for all n≥1. Now, letting n→+∞ in (11), we get |W*(x)-V*(x)|≤ϵZ(x)/(1-α), x∈X.The following corollary is immediate.Corollary 13.
Suppose that Assumptions1 and 6 hold. Suppose that for M one of Assumptions 3 or 4 holds (hence, M does not necessarily have a unique optimal policy). Let ϵ be a positive number. If A is compact or Condition 10 holds, then there exists an MDP Mϵ with a unique optimal policy g*, such that inequalities in Theorem 12 (a) or (b) hold, respectively.Example 14.
LetX=(0,∞), A=A(x)=(-∞,0], for all x∈X. The dynamic of the system is given by
(15)xt+1=xteat+ξt,t=0,1,…. Here, ξ0,ξ1,… are i.i.d. random variables with values in S=(-∞,0] and with a common continuous bounded density denoted by Δ. The cost function is given by c(x,a)=x+|a|, x∈X (observe that c is convex but not strictly convex).Lemma 15.
Example14 satisfies Assumptions 1, 3, and 6, and Condition 10.Proof.
Assumption1 (a) trivially holds. The proof of the strong continuity of Q is as follows: if u:X→ℝ is a measurable and bounded function, then, using the change of variable theorem, a simple computation shows that
(16)∫(0,∞)‍u(y)Q(dy∣x,a)=∫(-∞,0]‍u(xea+s)Δ(s)ds=∫(0,xea]‍u(w)Δ(lnwx-a)1wdw,(x,a)∈𝕂. As u is a bounded function and Δ is a bounded continuous function, it follows directly, using the convergence dominated theorem, that
(17)∫(0,xea]‍u(w)Δ(lnwx-a)1wdw,(x,a)∈𝕂 is a continuous function on 𝕂. Hence,
(18)∫(0,∞)‍u(y)Q(dy∣·,·)
is a continuous function on 𝕂.
By direct computations we get, for the stationary policyg(x)=0, x∈X, both V(g,x)=Exg[∑t=0∞αtc(xt,at)] and W(g,x)=Exg[∑t=0∞αtc*(xt,at)] are less or equal to Θ(x)=x/(1-α) for all x∈X (observe that, in this case, Θ(x)≥W*(x) and Θ(x)≥V*(x), x∈X); consequently, Assumptions 1 and 6 hold.
On the other hand, Assumptions3(a), (b), and (d) are immediate. Let F(x,a,s)=xea+s,x∈(0,∞),a,s∈(-∞,0]. Clearly, F(·,a,s) is nondecreasing in the first variable.
Now, takeλ∈[0,1] and (x,a), (x′, a′)∈𝕜 and s∈S. Then, considering that es, eλa, and e(1-λ)a′ are less or equal than one,
(19)F(λx+(1-λ)x′,λa+(1-λ)a′,s)=(λx+(1-λ)x′)e(λa+(1-λ)a′+s)=es(λx+(1-λ)x′)eλae(1-λ)a′=es[λxeλae(1-λ)a′+(1-λ)x′eλae(1-λ)a′]≤es[λxeλa+(1-λ)x′e(1-λ)a′]=λF(x,a,s)+(1-λ)F(x′,a′,s),
hence, F(·,·,s) is convex, that is, Assumption 3(c) holds.
Now, for eachx∈X,
(20)B(x)={a∈ℝ:x+|a|≤x1-α}={a∈ℝ:|a|≤αx1-α}.
Hence, takingZ(x)=[αx/(1-α)]2, x∈X, using (20) and, again, that ea+s≤1, it is possible to obtain that for each x∈X and a∈B(x),
(21)c*(x,a)-c(x,a)=ϵa2≤ϵ[αx1-α]2,
and that ∫‍Z(y)Q(dy∣x,a) = [α/(1-α)]2 ∫‍y2Q(dy∣x,a) = [α/(1-α)]2x2 ∫‍[e(a+s)]2Δ(s)ds ≤ [α/(1-α)]2x2 = Z(x).


## 4. Concluding Remarks

The specific form of the perturbation used in this paper is taken from [5, Exercise 28, page 81], where it is established that a convex function f perturbed by a suitable quadratic positive function becomes strictly convex and coercive. In fact, this kind of perturbation is very much related to the one Tanaka et al. propose in their paper [6], and further research in this direction is being conducted.Both state and action spaces are considered to be subsets ofℝ, just for simplicity of exposition. All the results hold in ℝn. In this case, if A⊆ℝn(n>1), then it is possible to take
(22)c*(x,a)=c(x,a)+ϵ∥a∥2,(x,a)∈𝕂, where ∥a∥2=a12+⋯+an2,  a=(a1,…,an) (see [5, Exercise 28, page 81]), and all the results on this article remain valid.Theorem12, on the closeness of the value functions of the original and the perturbed MDPs, requires conditions that are all very common in the MDPs technical literature. The importance of the result lies in the fact that it is a crucial step to the study of the problem of stability under the cost perturbation of the uniqueness or nonuniqueness of optimal policies.Finally, we should mention that this research was motivated by our interest in understanding the relationship between nonuniqueness and robustness in several statistical procedures based on optimization.



---

*Source: 271279-2013-03-27.xml*