Risk-sensitive control has been an active area of research in the past 30 years and has found numerous applications in finance [17], cognitive neuroscience [28], and many more. Unlike the more classical case of the ergodic control problems which lead to the well known Bellman equation, infinite-horizon risk-sensitive (IHRS) control problems lead to a multiplicative dynamic programming equation, since they seek to minimize a cost or maximize a reward given by the exponential growth rate of a multiplicative cost or, resp., reward. This is one of the reasons why the risksensitive control penalty is desirable since it captures the higher order moments of the running cost in addition to its expectation.
Risk-sensitive control problems have been extensively examined for discrete time discrete state space controlled Markov chains [13,14,18,19,25] as well as the continuous time dynamics modeled by controlled di↵usions [10,12,20,21,26,27]. For the IHRS control problems, the corresponding value iteration (VI) algorithm, which ends up being a multiplicative analog of the classical VI algorithm for ergodic control problems, was also studied for the discrete time discrete state space setting such as in [13,15,16]. In [8], the multiplicative VI algorithm was studied for discrete-time Markov chains on a compact Polish space with a compact metric action space.
For controlled di↵usions, the corresponding VI algorithms have not thoroughly investigated until the recent work in [8]. In that reference, a first step is taken by proposing multiplicative VI and RVI algorithms for the IHRS control problem of di↵usions on the whole Euclidean space. The problem was studied under the framework of blanket(uniform) stability of the controlled di↵usion.
A key component towards that result is the local convergence of the multiplicative VI algorithm assuming that there exists a control for which the ground state di↵usion is positive recurrent, that is, the convergence is established only within a neighborhood of the solution to the risk-sensitive HJB equation (see (3.1)). Then the global convergence of the multiplicative RVI algorithm starting from any positive initial condition is established under the blanket (uniform) exponential ergodicity assumption.
Blanket/Uniform exponential ergodicity refers to a process that is positive recurrent and whose transition probabilities converge to the invariant distribution uniformly over all controls at an exponential rate. This condition is usually checked by means of establishing a Foster-Lyapunov inequality. As expected, this is not an easy condition to verify and few dynamical systems are as such, including the large-scale parallel-server queueing networks studied in [9,23]. In this paper, we consider the IHRS control problem of di↵usions assuming a near-monotone running cost without the blanket (uniform) ergodicity property, as recently studied in [1,7]. The near-monotonicity condition essentially penalizes any unstable behavior when the state gets large via the running cost function. In addition, we impose a further structural assumption relating the running cost function to the solution of the multiplicative dynamic programming equation as in Assumption 4.1. Under these assumptions, we improve upon the results in [8] by establishing the following:
• There exists a control under which the ground state di↵usion is exponentially ergodic.
• A global convergence result: for any positive initial condition, the multiplicative VI and RVI algorithms converge to the solution of the risk sensitive HJB equation. As this paper extends the results in [8] towards a better understanding of the RVI algorithm design under an IHRS criterion, we draw upon some of the notations and results from that paper.
1.1. Organization of the paper. In the next subsection, we summarize the notation used in the paper. In Section 2, we describe the model and state some of the assumptions used. In Section 3, we review some results concerning the existence and uniqueness of a solution to the risk-sensitive HJB equation under the IHRS criterion. In Section 4, we introduce the multiplicative VI algorithm and establish its global convergence (starting from any positive initial condition) to the solution of the risk-sensitive HJB equation under Assumption 4.1. In Section 5, we establish the global convergence of the multiplicative RVI algorithm. Finally, Section 6 is devoted to summarize the results and propose some future directions. 1.2. Notation. We use R d (and R d + ), d 1, to denote real-valued d-dimensional (nonnegative) vectors, and write R for the real line. We use z T to denote the transpose of z. For x, y 2 R, x ^y = min{x, y}.
For a set A ✓ R d , 1 A to denote the indicator function of A. The Euclidean norm on R d is denoted by | • |, and h• , •i stands for the inner product. A ball of radius r > 0 in R d around a point x is denoted by B r (x), or simply as B r if x = 0. We also let B ⌘ B 1 .
We denote by ⌧(A) the first exit time of the process {X t } t 0 from the set A ⇢ R d , defined by
We let ⌧ R := ⌧(B R ), and ⌧R := ⌧(B c R ). Given a strictly positive real function f on R d , the f -norm of a function g : R d ! R is given by
.
All random processes live in a complete probability space (⌦, F, P). Let X = {X t : t 0} be a controlled di↵usion on R d taking the form
The process {W t } t 0 is a d-dimensional standard Wiener process, and the control process {U t } t 0 lives in a compact metrizable space U. The sets of admissible controls U, and stationary Markov controls U sm are defined in the standard manner [4].
We consider the infinite-horizon risk-sensitive (IHRS) control problem: For U 2 U, and a given running cost c : R d ⇥ U ! [1, 1), the risk-sensitive objective function is defined by
and the IHRS optimal values are denoted by
where k k := Tr T 1 /2 denotes the Hilbert-Schmidt norm of the matrix . In addition, b is continuous. (ii) A ne growth condition. For some ✓ 2 [0, 1) and a constant 0 , we have
(iii) Nondegeneracy. Let a := T . For each R > 0 and some positive constant
We continue with the following definition of near-monotonicity.
We impose the following structural assumptions in Assumptions 2.2 and 2.3 on the running cost c, namely near-monotonicity, and on the drift b and variance matrix a to ensure the existence of a solution to the risk sensitive Hamilton-Jacobi-Bellman (HJB) equation: Assumption 2.2. The running cost c is continuous and satisfies min
Note that (2.2) implies that the running cost c is inf-compact.
Assumption 2.3. The following hold for the matrix a, drift b and cost c.
(i) The matrix a is bounded.
(ii) For some ✓ 2 [0, 1) and a constant 0 , we have
(iii) The drift b satisfies the following structural property
Note that Assumptions 2.2 and 2.3 appeared previously in [1] as su cient conditions for the existence of a solution of the HJB equation of the IHRS control problem and in [7] to establish that the solution of the HJB equation has a polynomial growth.
To describe the risk-sensitive HJB equation below, we introduce the following concepts and notation.
The extended generator of the controlled di↵usion X t in (2.1) is given by
For ease of notation, we use
for v 2 U sm , which we adopt for the rest of this paper and we let L v for v 2 U sm , denote the operator defined as in (2.3), but with b(x, u) replaced by b v (x). Note that when v 2 U sm , we use v as a subscript in
This is a semilinear operator in R d . The associated generalized eigenvalue is written as
We assume that ⇤ < 1. Note that in specific problems, this is verified via a Foster-Lyapunov equation of the form
which is bounded away from 0, and some v 2 U sm , and for 0 , 1 > 0.
In this section, we review some important results on the HJB equation of the IHRS control problem and the associated ground di↵usion. Note that these results have been established in [8,Theorem 3.1]. In [1, Proposition 1.1, Proposition 1.3, Theorem 1.4], the following results are established under the assumption that the running cost c is near-monotone relative to ⇤ ⇤ which implies that ⇤ ⇤ < 1. Let C 0 be the class of nonnegative functions which are not identically equal to 0 and vanish at infinity. Proposition 3.1. Under Assumptions 2.1 to 2.3, the following properties hold.
(i) The multiplicative (risk-sensitive) HJB equation
and ⇤ < 1. (ii) Any v 2 U sm that satisfies the following is stable and optimal:
We denote by U ⇤ sm the set of measurable selectors from the minimizer of (3.2). (iii) We have
the function ⇤ has the stochastic representation
for all r > 0 and v 2 U ⇤ sm . Observe that using the semilinear operator G in (2.4), the risk-sensitive HJB equation in (3.1) can be written as the following G (x) = (x) . Then finding the risk-sensitive HJB solution ( ⇤ , ⇤ ) is equivalent to finding the eigenfunction and eigenvalue for the above equation. If there were no control, then the equation is referred to as the multiplicative Poisson equation (MPE) in the literature. In that case, the solution is related to the principal eigenvalue problem studied in the PDE literature [11]. For the controlled di↵usion, properties from the associated MPE and principal eigenvalue problem turn out to be useful when one chooses the control u to be Markov controls v(x) in U sm . Proposition 3.1(ii) asserts that any stationary Markov control v which is a measurable selector from the minimizer of (3.2) is stable and optimal, i.e., ⇤ x v = ⇤ ⇤ for all x 2 R d where
In addition, Proposition 3.1(iii) asserts that the optimal risk-sensitive value is equal to the generalized eigenvalue defined in (2.5). Let v 2 U ⇤ sm . Using Proposition 3.1(iii) in addition to Jensen's inequality, we get the following lim sup
This together with (2.2) implies that the di↵usion X t in (2.1) is positive recurrent under any v 2 U ⇤ sm . By [1, Lemma 2.1], this implies that ⇤ is inf-compact, which in turn implies by (3.1) that the di↵usion in (2.1) is exponentially ergodic under any v 2 U ⇤ sm . So far, we have discussed the assumptions needed to ensure the existence of a solution ⇤ to (3.1). Before discussing the conditions for uniqueness of the solution, we give the following definition. Uniqueness of the eigenfunction ⇤ , which we refer to as the ground state, is related to the ergodic properties of the ground state di↵usion.
The ground state di↵usion takes the form
with := log ⇤ . Recall the definition of
This is the extended generator of the ground state di↵usion X ⇤ t under a control u 2 U. This definition can be extended to e L v for any Markov control v (not necessarily stationary) by replacing u 2 U with v in (3.5). Clearly, e L v , with v 2 U sm , is the extended generator of X ⇤ t under a Markov control v.
Similar to (2.4), we define the following semilinear operator:
Note the coe cient 1 2 in front of a(x)r (x), so unlike (2.4), G ⇤ (x) 6 = min u2U ⇥ e L u (x) + c(x, u) ⇤ . However, simple calculations using (3.1) show that
Note that the sets of measurable selectors from the minimizers of (3. In addition, since Proposition 3.1(iii) asserts that ⇤ x v = ⇤ , we have that strict monotonicity of ⇤ at c on the right implies that the solution pair ( ⇤ , ⇤ ) is unique by [1, Theorem 1.2] if condition (3.3) holds.
In Section 4, under Assumption 4.1, we will show that the ground state di↵usion is exponentially ergodic in Lemma 4.1. Based on the previous discussion, this implies that the solution pair to (3.1) is unique. Thus, studying the convergence of the VI algorithm to the solution of the multiplicative HJB equation is a well-posed problem.
In this section, we prove that the multiplicative VI algorithm converges to the solution ⇤ of (3.1) starting from any initial positive function under the structural assumption relating the running cost function c to the ground state ⇤ in Assumption 4.1.
Formally, let
We introduce the multiplicative VI algorithm through the following equation
It is then clear that the VI algorithm is not feasible to implement as it assumes that the value of ⇤ is known. This is the reason we resort to the multiplicative RVI algorithm in Section 5 where the unknown ⇤ is replaced by the initial value in (5.1).
Before establishing the main result in this paper, we provide the following structural assumption and discuss how it is related to the existing assumptions in the relevant literature. Recall that = log ⇤ .
Assumption 4.1. There exist positive constants ✓ 1 and ✓ 2 such that min u2U c(x, u)
For example, for a bounded non-degenerate matrix a and a quadratic cost c, we have that r = r ⇤ ⇤ has at most a linear growth by [7,Lemma 4.5]. In this case, Assumption 4.1 holds. Consider the following example in the case of an uncontrolled di↵usion:
Then ⇤ (x) = e x 2 is an eigenfunction with an eigenvalue ⇤ = 1. In addition the ground state di↵usion in this case is positive recurrent (in fact geometrically ergodic as it will be shown in Lemma 4.1) since (x) = x 2 is a Lyapunov function. Note also that
Here we used ✓ 1 = 2 and ✓ 2 = 1.
Note that an analogous assumption to Assumption 4.1 appeared previously in the study of the ergodic control problem as
where denoted the solution of the ergodic HJB equation. Equation (4.2) was used to establish global convergence of the VI algorithm in continuous time [5,Theorem 3.20] as well as in the discrete setting [3,24] for ergodic control problems. The global convergence of the multiplicative VI algorithm under Assumption 4.1 was left as an open conjecture in [8]. Observe that Assumption 4.1 is a modification of (4.2) to account for the relative entropy term 1 2 T (x)r (x) 2 arising from the logarithmic transformation.
Recall that global convergence refers to the convergence of the multiplicative VI algorithm to the solution ⇤ of (3.1) starting from any positive initial condition, whereas local convergence means converging to this solution starting within a neighborhood of it. Assumption 4.1 will be used to establish the existence of a stable control in Lemma 4.1 and we then establish the global convergence of the multiplicative VI algorithm under Assumption 4.1 in Theorem 4.2. These results extends upon those in [8] where only local convergence of the multiplicative VI algorithm was shown under the assumption that there exits a control for which the ground state di↵usion is positive recurrent.
Recall that U ⇤ sm is the set of measurable selectors from the minimizer of (3.2) and let v ⇤ 2 U ⇤ sm . We start with the following result.
This implies that the process {X ⇤ t } t 0 in (3.4) is geometrically ergodic under any v ⇤ 2 U ⇤ sm .
Proof. Under Assumption 4.1, we have the following
where in the first equality we used (3.5), in the second we used (3.6) combined with (2.3), and in the third one we used (3.7). This completes the proof. ⇤
Thus the ground state di↵usion X ⇤ t in (3.4) is positive recurrent under any v ⇤ 2 U ⇤ sm which implies that the ground state ⇤ is unique as discussed previously.
We continue with the following definitions that are needed when establishing the global convergence of the multiplicative VI algorithm defined in (4.1). Definition 4.1. Let {v t } t 0 be an a.e. measurable selector from the minimizer of (4.1). We define the corresponding (nonstationary) Markov control vt := vt s = vt s (x) , s 2 [0, t] . Let S t [ 0 ](x), t 0, denote the solution of (4.1) starting from an initial condition 0 . It is clear that S t [ ⇤ ] = ⇤ for all t 0 by Proposition 3.1 (i), and that the uniqueness of the ground state ⇤ implies that any positive initial condition 0 satisfying S t [ 0 ] = 0 for all t 0 must equal the ground state ⇤ up to a positive multiplicative constant.
Let E denote the set of equilibria of S t , or equivalently, the set of solutions of the risk-sensitive HJB equation in (3.1), that is, E := {r ⇤ : r > 0} .
(4.3) We continue with the following important lemma. Lemma 4.2. Let (t, x) be as in (4.1). Under Assumption 4.1, for any
Proof. Let (t, x) denote the canonical solution of (4.1) with initial data 0 and let {v t , t 2 R + } denote a measurable selector from the corresponding minimizer. Without loss of generality we assume 0 1 since the solution of (4.1) is invariant under scalar multiplication. Let ' := log and recall that = log ⇤ . Note that ' satisfies
Hence, by (4.7) we get
Therefore, we obtain exp e ✓ 1 t (x)
.
Concerning the upper bound, we note that
where the first and the last equalities follow from the definition of S t [.] and the fact that ⇤ 2 E which is the set of equilibria of S t [.], and the inequality by the monotonicity of f 7 ! S t [f ]. This completes the proof. ⇤
Before establishing the main result in this paper, we recall the following result from [8, Theorem 3.2] with a slight modification.
For positive constants 0 and 1 , we define the set G ⇢ C 2 (R d ) by
We then have the following result.
Proof. Here we use the following argument: Recall that under Assumption 4.1 the ground state di↵usion was shown to be positive recurrent in Lemma 4.1.
By Lemma 4.2, every !-limit point h of S t [ 0 ] lies in the set
Recall that the !-limit set of 0 is invariant under S t . Since by Theorem 4.1 the only invariant subsets of G are the points of E \ G, the result follows. This completes the proof. ⇤
As mentioned before, the multiplicative VI algorithm is not feasible to implement as it requires
⇤ to be known. In this section, we introduce the multiplicative RVI algorithm and show that the convergence of the VI algorithm to the solution ⇤ of (3.1) implies the convergence of the RVI algorithm to this solution.
Hence we modify (4.1) and introduce the multiplicative RVI algorithm as follows:
with (0, x) = 0 (x).
While the convergence of (5.1) is usually viewed as a stabilization of a nonlinear parabolic PDE in the sense of Has 0 minskiȋ [22], we prefer to think of it as a continuous-time continuous-space analogue of the RVI algorithm proposed in [29].
We start with the following lemma.
Lemma 5.1. Suppose that the multiplicative VI algorithm in (4.1) converges to a solution c 0 ⇤ of (3.1) for some constant c 0 , then the RVI algorithm in (5.1) also converges to c 1 ⇤ for some constant c 1 .
Proof. The proof is adopted from [8, Section 3.3] and we add it for completeness. Note that if solves (5.1), then (t, x) = (t, x) e R t 0 ( (s,0) ⇤) ds
(5.2) solves (4.1).
In addition, from (5. (5.4)
Recall that ⇤ (0) = 1 by Proposition 3.1(i). Since (t, 0) ! c 0 ⇤ (0) = c 0 > 0 as t ! 1 by assumption, it follows by (5.4) that (t,x) (t,x) converges to c 0 ⇤ as t ! 1. ⇤
We continue with the following theorem on the global convergence of the multiplicative RVI algorithm.
Theorem 5.1. Let Assumptions 2.1 to 2.3 and 4.1 hold. Then, for any initial condition 0 2 C 2 (R d ) with inf R d 0 > 0, the solution of (5.1) converges as t ! 1 to ⇤ uniformly on compact sets of R d .
Proof. This follows directly by combining Lemma 5.1 with Theorem 4.2. ⇤
In this paper, we considered the IHRS control problem for non-degenerate controlled di↵usions with a compact action space, and controlled through the drift. Using only a structural assumption on the running cost function which amounts to a strong form of near-monotonicity, we established the existence of a controller for which the ground state di↵usion is exponentially ergodic and showed that the multiplicative VI/RVI algorithms converge globally (starting from any positive initial condition) to the solution of the multiplicative HJB equation corresponding to the IHRS control problem.
It would be interesting to check if a similar assumption to Assumption 4.1 can be used to establish these results in the case of a discrete-time Markov chain with a compact Polish state space [3] and for controlled jump di↵usions [6].