On Some Geometric Behavior of Value Iteration on the Orthant: Switching System Perspective

Dynamic programming [1, 2] is a general and effective methodology for finding an optimal solution for Markov decision problems [3]. Value iteration is a popular class of dynamic programming algorithms, and its exponential convergence is a fundamental and well-established [1, 2] result through the contraction mapping property of the Bellman operator.

In this paper, we offer some additional insights on the value iteration based on switching system models [4, 5, 6, 7, 8, 9, 10, 11] in the control community. These models provide new geometric behaviors of value iteration to solve Markov decision problems [3]. In particular, the main contributions of this paper are twofold: 1) We present a switching system model of value iteration and, based on it, provide a different proof for the contraction property of value iteration. 2) Furthermore, from the new perspectives and frameworks, we study additional geometric behaviors of value iteration when the initial iterate lies in a special region. More specifically, the detailed contributions are summarized as follows:

1. 1.

   A switching system model of value iteration is introduced along with its special properties. Based on it, we offer a different proof for the following contraction property of the value iteration:

   $\displaystyle\left\|{Q_{k+1}-Q^{*}}\right\|_{\infty}\leq\gamma\left\|{Q_{k}-Q^{*}}\right\|_{\infty},$

   (1)

   where $Q_{k}$ is the $k$th iterate of the value iteration, $Q^{*}$ is the optimal Q-function, and $\gamma\in(0,1)$ is the so-called discount factor in the underlying Markov decision problem. Although this result is fundamental and classical, the proof technique utilized in this paper is distinct from the classical approaches, offering additional insights.

2. 2.

   Furthermore, from the additional insights provided in the first part, we prove new geometric behaviors of value iteration when the initial iterate lies in a special region. Specifically, when the initial iterate $Q_{0}$ is within the set $Q_{0}\leq Q^{*}$ (shifted orthant), the iterates of the value iteration remain in the set, displaying different behaviors than the cases with a general initial iterate. When $Q_{0}\leq Q^{*}$, one can establish the new contraction property

   $\displaystyle\left\|{Q_{k+1}-Q^{*}}\right\|_{M}\leq(\gamma+\varepsilon)\left\|{Q_{k}-Q^{*}}\right\|_{M}$

   (2)

   where $\left\|(\cdot)\right\|_{M}=\sqrt{(\cdot)^{T}M(\cdot)}$ is the weighted Euclidean norm, $\varepsilon>0$ is any real number such that $\gamma+\varepsilon\in(0,1)$, and $M$ is a positive definite matrix dependent on $\varepsilon>0$. This result corresponds to a contraction mapping property of the Bellman operator in terms of the weighted Euclidean norm, which cannot be derived from the classical approaches. Geometrically, the sublevel sets corresponding to the infinity norm $\left\|\cdot\right\|_{\infty}$ are squares, while the sublevel sets corresponding to the weighted Euclidean norm $\left\|\cdot\right\|_{M}$ are ellipsoids.

   A more notable result is that when $Q_{0}\leq Q^{*}$, the iterates satisfy the linear inequality

   $\displaystyle(\gamma+\varepsilon)v^{T}(Q_{k}-Q^{*})\leq v^{T}(Q_{k+1}-Q^{*})\leq 0,\quad\forall k\geq 0,$

   (3)

   where $\varepsilon>0$ is any real number such that $\gamma+\varepsilon\in(0,1)$, and $v$ is a positive vector dependent on $\varepsilon$. Geometrically, this implies that the component along the direction of $v$ in $Q_{k}-Q^{*}$ diminishes exponentially.

The analysis presented in this paper employs insights and tools from switching systems [4, 5, 6, 7, 8, 9, 10, 11], positive switching systems [12, 13, 14, 15], nonlinear systems [16], and linear systems [17]. We emphasize that our goal in this paper is to offer additional insights and analysis templates for value iteration via its connections to switching systems, rather than improving existing convergence rates. We anticipate that the proposed switching system perspectives may have the potential to be a useful tool, applicable in various settings, and stimulate the synergy between dynamic system theory and dynamic programming. Thus, further development of these methods could be a valuable avenue for future research. Finally, some ideas in this paper have been inspired by [11, 18], which develop switching system models of Q-learning [19]. However, most technical results and derivation processes are nontrivial and entirely different from those in [11, 18]. Another related work is [20], which provides a linear programming-based analysis of value iteration and also employs positive switching system models for their analysis. However, the previous work merely proposed a numerical linear programming-based analysis to verify convergence properties and did not obtain the explicit relations given in (1), (2) ,(3). Therefore, our analysis offers significantly different results than those in [20].

In this section, we study a discrete-time switching system model of Q-VI and establish its finite-time convergence based on the stability analysis of the switching system. Using the notation introduced in Section II-D, the update in Algorithm 1 can be rewritten as

Recall the definitions $\pi_{Q}(s)$ and $\Pi_{Q}$. Invoking the optimal Bellman equation $(\gamma P\Pi_{Q^{*}}-I)Q^{*}+R=0$, (7) can be further rewritten by

which is a SAS (switched affine system). In particular, for any $Q\in{\mathbb{R}}^{|{\cal S}||{\cal A}|}$, define

Hence, Q-VI can be concisely represented as the SAS

where $A_{Q_{k}}$ and $b_{Q_{k}}$ switch among matrices from $\{\gamma P\Pi^{\pi}:\pi\in\Theta\}$ and vectors from $\{\gamma P(\Pi^{\pi}-\Pi^{\pi^{*}})Q^{*}:\pi\in\Theta\}$ according to the changes of $Q_{k}$. Therefore, the convergence of Q-VI is now reduced to analyzing the stability of the above SAS. Th main obstacle in proving the stability arises from the presence of the affine term. Without it, we can easily establish the exponential stability of the corresponding deterministic switching system, under arbitrary switching policy. Specifically, we have the following result.

The above result follows immediately from the key fact that $\|A_{Q}\|_{\infty}\leq\gamma$, which we formally state in the lemma below.

However, because of the additional affine term in the original switching system (9), it is not obvious how to directly derive its finite-time convergence. To circumvent the difficulty with the affine term, we will resort to two simpler upper and lower bounds, which are given below.

The lower bound is in the form of an LTI system. Specifically, the lower bound corresponds to a special LTI system form known as a positive linear system [21], where all the elements of the system matrix $A_{Q^{*}}$ are nonnegative. In our analysis, this property will be utilized to derive new behaviors of Q-VI. Similarly, the system matrix $A_{Q_{k}}$ in the upper bound switches according to the changes in $Q_{k}$. Therefore, it can be proven that the upper bound is in the form of positive SLSs [12, 13, 14, 15], where all the elements of the system matrix for each mode are nonnegative.

In the previous section, we revisited the convergence of Q-VI from the perspective of switching system viewpoints. In this section, we study additional geometric behaviors of Q-VI, again using the switching system perspective. Let us suppose that $Q^{*}\geq Q_{0}$ holds. Please note that such an initial value can be found by setting

because

holds according to  Lemma 1. Then, using the bound provided in  Proposition 2, it can be proved that $Q^{*}\geq Q_{k},\forall k\geq 0$. This is equivalent to saying $0\geq Q_{k}-Q^{*},\forall k\geq 0$. In other words, if the initial iterate $Q_{0}$ falls within the shifted orthant, $Q^{*}\geq Q_{0}$, then future iterates will also stay within the same set, i.e., $Q^{*}\geq Q_{k},\forall k\geq 0$.

From the results above, it can be observed that the behavior of $Q_{k}-Q^{*}$ is fully dictated by the lower bound, which is a linear function of $Q_{k}-Q^{*}$. Therefore, the fundamental theory of linear systems can be applied to analyze the behavior of Q-VI. To facilitate this, the subsequent result reviews the Lyapunov theory for discrete-time linear systems.

The proof of  Proposition 4 is provided in the Appendix. Note that  Proposition 4 can be applied to general LTI systems. However, because the lower bound takes the form of positive linear systems, it can be demonstrated that the Lyapunov matrix $M$ also possesses the additional special property outlined below.

From the perspectives provided above, we can derive a bound on $Q_{k}-Q^{*}$ in terms of the weighted Euclidean norm $\left\|\cdot\right\|_{M}$. This is an alternative to the infinity norm $\left\|\cdot\right\|_{\infty}$, which cannot be derived from classical contraction mapping arguments.

The result in Theorem 1 provides

for an arbitrarily small $\varepsilon>0$, which implies

and

This relationship reveals different geometric convergence behaviors: the sublevel sets associated with the infinity norm $\left\|\cdot\right\|_{\infty}$ are squares, whereas those corresponding to the weighted Euclidean norm $\left\|\cdot\right\|_{M}$ are ellipsoids.

Furthermore, our new approach enables us to derive a bound on a linear function of $Q_{k}-Q^{*}$. Specifically, for positive LTI systems, one common Lyapunov function is a linear Lyapunov function of the form $V(x)=v^{T}x$ for a positive vector $v\in{\mathbb{R}}^{|{\cal S}|\times|{\cal A}|},v\geq 0$. We proceed by providing an explicit form of such a vector $v$.

The proof is given in Appendix. Proposition 6 proves that $V(x)=v^{T}x$ plays the role of a linear Lyapunov function for the positive LTI system. From Proposition 6, one can prove another convergence result of Q-VI.

Proposition 6 tells us that

which implies

Suppose that $Q_{k}-Q^{*}=[v]_{k}+[v]_{k}^{\bot}$, where $[v]_{k}$ represents the component of $Q_{k}-Q^{*}$ in the direction of $v$, and $[v]_{k}^{\bot}$ represents the components of $Q_{k}-Q^{*}$ orthogonal to $v$. Then, according to (11), the component of $Q_{k}-Q^{*}$ in the direction of $v$ diminishes exponentially. From the construction of $v$ in  Proposition 6, it can be seen that there could be infinitely many such vectors $v$, depending on the positive vector $w$. Therefore, $Q_{k}-Q^{*}$ becomes trapped in the intersections of the nonpositive orthant and infinitely many half planes. An illustration of a single half plane is provided in Figure 1.

In this paper, we have presented additional insights on value iteration, approached through the lens of switching system models in the control community. This offers a connection between value iteration and switching system theory and reveals additional geometric behaviors of value iteration. Specifically, we introduced a switching system model of value iteration and, based on it, provided a novel proof for the contraction property of the value iteration. Moreover, our insights led to the proof of new geometric behaviors of value iteration when the initial iterate resides in a particular set (the shifted orthant). We believe that the perspectives proposed here could serve as useful tools applicable in various settings. As such, further development of these methods may present a valuable future direction.