A study of value iteration and policy iteration for Markov decision processes in Deterministic systems

1.   Introduction

A Markov chain, introduced by the Soviet mathematician Andrey Markov in the early 20th century, is a class of stochastic processes characterized by the property that future states depend only on the current state, independent of the sequence of preceding states. Early applications of Markov decision theory concentrated on solving optimal decision problems in deterministic settings. However, decision-making in real-world scenarios typically involves significant uncertainty and risk, prompting the expansion of decision theory frameworks to encompass stochastic environments. Markov decision processes (MDPs) provide a structured approach for stochastic optimization in control systems. In cases where the transition probability is degenerate, resulting in a deterministic distribution, the control system is termed a deterministic system, a concept rooted in the work of Bellman ^[1]. Within deterministic systems, the transition dynamics can be explicitly defined by a transition function, situating these systems within a specialized domain of stochastic Markov decision theory where state evolution follows deterministic rules. The foundational theory of discrete-time Markov decision processes (MDPs), as outlined by Hernandez and Lasserre ^[2,3], includes a comprehensive treatment of random optimization problems under both discounted and non-discounted criteria. Section 1.2 of their work provides a detailed exploration of deterministic systems, though certain critical conclusions may not universally hold, as noted in further discussions by Hernandez et al. ^[4]. Earlier work by Meyn and Tweedie ^[5] recharacterized deterministic systems as nonlinear systems, positing the transition function as a nonlinear mapping—a perspective demonstrated in examples provided by Hernandez et al. ^[4]. While many real-world MDPs involve optimization with stochastic (or "random") transition probabilities, problems featuring deterministic transition probabilities are applicable across various domains, including linear programming and certain economic models ^[6,7]. These applications highlight the practical breadth of deterministic optimization within stochastic frameworks, underscoring its relevance in systems with known transition dynamics. Building on this framework, Hernandez et al. ^[4] examined the average cost optimization problem for discrete-time MDPs in deterministic systems. Their analysis focused on establishing the conditions for the existence of an average cost criterion, operating under the assumptions that both the state and action spaces are Borel spaces and that all costs are non-negative. To this end, they employed three distinct approaches: the average cost inequality, the stationary method, and the vanishing discount method. Notably, the literature does not extend to discussing two approximate processes applicable to dynamic programming within deterministic systems: the value iteration (VI) process and the policy iteration (PI) process.

In these three approaches, the average cost inequality method facilitates a comparative analysis of strategies by evaluating expected returns. This framework enables decision-makers to determine optimal strategies through the calculation of expected outcomes across various decisions. When state transitions and rewards are stochastic, the average cost inequality serves as a tool to assess the expected returns across potential future states, thereby addressing inherent uncertainties. For deterministic systems, however, the average cost inequality offers a direct method for comparing deterministic returns, leveraging the known state transition functions to provide clear strategic insights. The steady-state approach, or stable strategy method, aims to identify policies under which the system's state distribution converges to a steady state over time in specific Markov decision processes. In this equilibrium, returns across different states stabilize, emphasizing policy consistency and clarity within deterministic systems, where predictable state transitions are key to achieving stable returns in the long term. The vanishing discount method, on the other hand, incorporates time preference by discounting future returns, thus emphasizing their present value. Through a discount factor—typically set between 0 and 1—future returns gradually diminish in influence, aligning decisions with immediate priorities. In deterministic systems, a discount factor close to 1 underscores the value of long-term returns, promoting decision-making that is stable, consistent, and geared toward sustained effectiveness.

1.1.   Where do the ways of implementation originate from?

The two primary approaches proposed here aim to address dynamic programming challenges by enhancing computational efficiency. Before establishing their validity, it is essential to review the underlying dynamic programming framework. Building on the work of Hernandez and Lasserre ^[2,3] and Gaitsgory et al. ^[8], the computation of the cost function transitions from a sequence of integral functions to a summation of costs over specific state-action pairs. This reformulation significantly improves the efficiency of iterative procedures and provides a foundation for examining the validity of the value iteration (VI) process in deterministic systems.

Costa and Dufour ^[9] extended this approach by deriving new results for the average cost criterion under the Feller property of transition probabilities, thus ensuring policy iteration (PI) convergence under these conditions. However, they noted that the Feller property alone does not fully guarantee PI validity within deterministic frameworks. In their verification, Meyn ^[10] demonstrated that PI has a linear convergence rate, effectively reflecting its convergence properties. This prompts consideration of whether similar methods can be employed to validate these approaches fully.

When analyzing the VI and PI processes under the average cost criterion, they find application in both finite-level cost growth assessments and in operations research at the infinite-horizon level, as initially explored by Bellman ^[11] and Howard ^[12]. On the topic of discount factors, Dai and Menoukeu ^[13] investigated the optimal stopping problem for value functions under stochastic discounting, with relevance to pulse control problems. Feinberg and Liang ^[14] further explored scenarios where the discount factor approaches 1, thereby approximating deterministic behavior. Using a similar approach, Yu et al. ^[15] confirmed the existence of an optimal value in game-theoretic settings under these conditions.

In deterministic systems, discussions typically adopt an offline approach that applies to all cases where the transition function is deterministic, regardless of whether these functions are linear or nonlinear. This contrasts with the online policy iteration method proposed by He et al. ^[16], specifically targeting nonlinear systems. He et al.'s work emphasizes real-time, dynamic processes, using policy iteration to forecast future outcomes under uncertain conditions by approximating nonlinear problems as linear ones. Similarly, the online reinforcement learning study by Fang et al. ^[17] encounters comparable challenges. Although both approaches are based on Markov decision processes, online reinforcement learning methods do not require prior knowledge of state transitions that are better suited for scenarios where data collection and model training occur concurrently.

In another study by Fang et al. ^[18], an online fuzzy optimization algorithm based on Markov jump systems demonstrated convergence and introduced a completely model-free, offline policy iteration fuzzy reinforcement learning algorithm. This algorithm effectively controls without relying on system dynamics or transition probability information. This fully model-free approach is fundamentally different from deterministic systems that depend on known system dynamics and transition probabilities.

1.2.   Key innovations

This study primarily investigates value iteration (VI) and policy iteration (PI) for deterministic Markov decision processes (DMDPs), introducing their application under the average cost (AC) criterion within deterministic systems for the first time. Section 2 examines the existence of dynamic programming processes within deterministic systems, noting that while Hernandez et al. ^[4] have extensively explored these systems, many foundational theorems in this specialized domain remain unverified.

In Section 3, we focus on establishing the validity of VI within deterministic systems. If the value function converges under deterministic conditions, this convergence confirms the existence of an optimal value function in DMDPs, thereby enabling the derivation of an optimal policy set. Section 4 addresses the convergence of PI, where each step of policy evaluation and improvement incorporates VI, iteratively refining policies toward optimality.

VI and PI serve as essential methods for analyzing the convergence of decision processes in stochastic systems. Therefore, verifying the validity of these iterations within deterministic contexts is vital to advancing research across the entire field of Markov decision processes.

2.   Dynamic programming problems in deterministic systems

DMDPs, as a subfield of stochastic processes, have been discussed by Hernandez and Laura ^[4] to have the following form for their transition function:

Given the cost function for each stage, the total cost function $c(x, a)$ within time $T$ is expressed as follows:

Equation (2.2) represents the total cost generated by the path taken in the decision-making process under a given initial state $x_0$ and strategy $\lambda$. Due to the infinity of time, the average cost is calculated by taking the limit over time:

The convergence of MDPs is discussed by using the convergence of the average cost function.

VI and PI are classic methods for solving dynamic programming problems, first introduced by Howard ^[12]. The following verifies whether the dynamic programming problem holds in deterministic systems. The specific definition of dynamic programming problems is as follows:

for the above equation, the time is calculated by the backward $t = N, N-1, ..., 1, 0$.

Theorem 1. Let $J_{0}, J_{1}, ..., J_{T-1}, J_{T}$ be a function on the state space $X$ and from $t = T$ to $t = 0$, if the value function is defined as:

the momentary cost function is:

Then, there must exist a set of strategies ${\Lambda_t}$ that $\lambda_t(x)\in \Lambda(x)$ contains the minimum value in the above equation, i.e.:

and for each stage, there will exist a deterministic policy $\lambda^{*} = \left\{\lambda_{1}, \lambda_{2}, \ldots, \lambda_{t-1}\right\}$ such that the following equation holds:

Proof of Theorem 1. Let $\lambda = {\lambda_t}$ be the set of fixed strategies, and $C_{t}$ be the value of the cost from the time $T$ to the time $t$, and given the state $x_{t} = x$ at the moment $t$, if $t = 0, 1, ..., T-1$.

Assuming that for all $t = 0, 1, ..., T$

holds. When ${\lambda = \lambda^*}$,

holds. In particular when taken to $t = 0$, for any state $x$, there are

If the hypothesis holds, the desired result Eq (2.5) is obtained.

Now, verify Eqs (2.8) and (2.9): When $t = T$, it is obtained from Eqs (2.4) and (2.7):

The inductive hypothesis method: if for $t = T-1, ..., 1, 0$:

holds, then for Eq (2.7).

So there is:

If $t = 0$, then there is:

The equation holds when the set of optimal strategies is taken. □

It follows from the above proof that DP holds under deterministic systems.

3.   Value iteration in deterministic systems

In deterministic systems, dynamic programming problems offer a clearer and more efficient framework for applying value iteration and policy iteration, facilitating a faster determination of value functions or optimal policy sets. Section 3 centers on an in-depth examination of value iteration, exploring its convergence properties and implications for identifying optimal solutions.

3.1.   The basic idea of value iteration

In the deterministic system, the cost function is shown in Eq (2.2), and the AC is shown in Eq (2.3), if we make:

For any $n\geq1$, representing the optimal cost of the $n$-th stage and the:

Definition 1.

Assumption 1. The OCP (2.1)–(2.3) satisfies:

(1) The value function for each stage $t$ in sequence $\left\{J_{n}^{*}(x)\right\}$ is equicontinuous;

(2) There exists a continuous function $F$ such that $x_{n+1} = F\left(x_{n}, a_{n}\right)$;

(3) If there exists a termination cost function $l(x)$ that satisfies:

$b(x)$ is any bounded non-negative function with:

$L(x)$ for a mapping$X \rightarrow R$ hold.

In the Borel space, consider a fixed state $z$ and define the following equations:

The following conditions are given:

where $(\rho^*, l(x))$ is the solution to the AC equation.

The purpose of VI is to find ${\lambda_n}$ such that the following equation holds true:

Introduce the canonical triplet$(\rho^*, l(x), \lambda^*)$ to satisfy the following equation:

In Eq (3.1), $\rho^*$ denotes the average optimal cost, $l(x)$ denotes a termination cost function, and $\lambda^*$ denotes the optimal strategy.

3.2.   Value iteration processes

Theorem 2. For the difference function:

For all $x \in X$ and $n\geq0$, the following three inequalities hold:

(1)$h(x) \geq-N$;

(2) $h_n\left(F^{m}\left(x, \left(\lambda_{n+m-1}, \lambda_{n+m-2}, \ldots, \lambda_{n}\right)\right) \leq h_{n+m}(x)\right.$;

(3) $h_{n}(x) \leq h_{n-1}\left(F\left(x, \lambda_{n}\right)\right).$

Proof of Theorem 2. (1) By

Also due to $-N\leq l(x) \leq b(x)$ :

when $l(x) \equiv 0$ is available,

is the general cost function:

When $\rho = \rho^{*}$, :

therefore

(2)

Therefore, we get $h_{n}(F(x, \lambda)) \leq h_{n+1}(x)$, which is the same as

(3)

□

Theorem 3. For the sequnce $\left\{h_{n}(x)\right\}$:

(1) $\left\{h_{n}(x)\right\}$ is uniformly continuous and bounded;

(2) For each sub-sequence $\left\{h_{n_{i}}(x)\right\}$ there exists a constant $k$ such that

(3) If any subsequence $\left\{h_{n_{i}}(x)\right\}$ converges to the unique constant $k$, then $\left\{h_{n}(x)\right\}$ converges to the constant $k$.

Proof of Theorem 3. (1) For any $x_1, x_2 \in X$, from Eq (3.3) we can obtain:

due to the uniform continuity of the function $J_{n}^{*}$, it is bounded. Furthermore,

since: $h_0$ is $l_0(x)$, and $l(x)$ is finite, we have

thus:

(2) Assuming $\left\{h_{n_{i}}(x)\right\}$ is a subsequence of $\left\{h_{n}(x)\right\}$ by (1) and Ascoli's theorem ^[2,3], it is known that as $i \rightarrow \infty$ converges to a continuous function $\theta$,

When $n$ is fixed and $m \rightarrow \infty$,

for deterministic systems, the probability $P$ values are either 0 or 1. As $P\left(F^{m}(x, a)\right) = 1$, the VI converges and satisfies

By Fatou's lemma:

let

be such that

thus

Furthermore, due to the arbitrariness of $P$ we know that $\theta(x) = k$. Since

if $\left\{h_{n_{i}}(x)\right\}$ is assumed not to converge to $k$, implying the existence of $\varepsilon > 0$ such that the subsequence $\left\{h_{n_{i}}(x)\right\}$ converges in the following manner:

Contradicting (2).

(3) If (2) holds, for another sub-sequence $\left\{h_{n_{j}}(x)\right\}$ of $\left\{h_{n}(x)\right\}$, as in the proof of (2), if $\left\{h_{n_{j}}(x)\right\}$ converges to $k^{\prime}$, then from Eqs (3.3) and (3.4) we can deduce that $k \geq k^{\prime}$, $k \leq k^{\prime}$ and for all states $x$,

holds. Otherwise, the sequence $\left\{h_{n}(x)\right\}$ and $\left\{x_{j}\right\}$ must converge to

contradicts the condition of 3, so

□

Theorem 4. (Theorem of VI Convergence): With the above assumptions holding, the value iteration processes are convergent, i.e., $p_n(x)$ converges to $l(x)$ and $q_n(x)$ converges to $\rho^*$ and the following holds:

Proof of Theorem 4. For the canonical triplet $\left(\rho^{*}, l, \lambda\right)$ that solves the average optimal equation (3.1), and when $n \rightarrow \infty$, the value of the deviation function converges to a constant $k$. Hence, for

satisfy:

Therefore, the VI converges. □

4.   Policy iteration in deterministic systems

In Section 3, the convergence of value iteration (VI) within deterministic systems is confirmed under specific assumptions. Once the optimal value function is obtained in practical applications, the corresponding optimal policy can then be derived. Policy iteration (PI) is generally employed to identify the optimal policy through an iterative approach that alternates between policy evaluation and policy improvement, progressively refining the policy until optimality is achieved. Each step in the PI process involves evaluating the policy using the value function and improving the policy via the selection function. Section 4 delves into the application and convergence of PI within deterministic systems, emphasizing its effectiveness in obtaining optimal decision policies.

4.1.   The basic idea of policy iteration

For the initial stage of the policy $\lambda$, there exists a cost function $V\left(\lambda_{0}, \cdot\right)$ related to the discount factor $\alpha$:

the relationship between its cost function and the AC function Eq (2.3) without the discount factor is:

When $\alpha \rightarrow 1$, $V \rightarrow J$. The cost function is defined $V(\lambda_0, \cdot)$ as $\omega_{0}(\cdot)$ and it satisfies the following equation:

A kernel function is defined by Eq (4.1):

Equation (4.3) signifies iterating into the system with a policy $\lambda_0$, reaching time $t$ and utilizing this kernel function to reflect the deviation in function values. In deterministic systems, the discount factor $\varepsilon \rightarrow 1$. The selection rules for policy iteration are introduced:

From Eq (4.4), it follows that the policy $\lambda_1$ at the first time step leads to:

at this point

Given the optimal policy $\lambda_t$ at $t$-th, the cost function along the path is as follows:

the optimal policy $\lambda_{t+1}$ at time $t+1$ satisfies the following equation:

Equations (4.2), (4.4)–(4.6) represent the processes of PI in MDPs, where in each iteration, the minimum cost for each stage needs to be calculated to choose the optimal policy based on this minimum cost.

Remark: The function presented in Eq (4.3) draws on concepts introduced by Meyn ^[10], where it is described as the sum of probability distribution functions in stochastic systems. In deterministic systems, however, the probability distribution values are restricted to either 0 or 1, allowing for integration with the discrepancy function. From Eq (4.3), it becomes evident that the core mechanism of policy iteration involves alternating between policy evaluation and policy improvement through the value iteration method. At each step, this approach enables the selection of an optimal policy based on iterative evaluation.

4.2.   Policy iteration processes

Without considering the termination cost $l(x)$, the discrepancy value function $h(\cdot)$ for Eq (3.2) in Section 3 is redefined as follows:

Theorem 5. Assuming there exists an initial policy $\lambda_0$, and the AC generated by the iteration processes at this point is $\rho_0$, if the following two conditions hold for the DMDPs:

(1) The cost function is continuous in product space and there exists a cost function $\underline{c}(x)$ such that for any $\kappa$ there exists $c(x, a) \geq \underline{c}(x)$;

(2) There exists a state $\chi \in X$ and a continuous function $s: X \rightarrow (0, 1)$ satisfying the following conditions:

When $n \geq 1$, there exists a canonical triplet $\left(\lambda_{n-1}, H_{n-1}, \rho_{n-1}\right)$, which is generated by the initial policy iteration $\lambda_0$ under Eq (4.4), further $\lambda_n$ obtained by iteration in Eq (4.5) satisfies the following inequality:

then for stage $n$-th, the algorithm will have a solution $\left(\lambda_{n}, H_{n}, \rho_{n}\right)$ and the related value function:

is finite and satisfies Proposition 1.

Remark: In stochastic processes, defining a continuous function $s(x)$ ^[10] ensures that for any state $x$, the probability of transitioning to another state remains within the range $(0, 1)$ until convergence is achieved in the iteration process. The kernel function used in these processes is given by:

where $\varepsilon$ represents a discount factor. In contrast, within deterministic systems, the probability of states participating in the iteration path due to policy selection is precisely 1. Thus, this paper primarily employs the discrepancy value function in place of the transition function used in stochastic processes, as indicated in Eq (4.3).

In the context of deterministic systems, kernel functions play a critical role in assessing the stability and convergence of policy iteration. Specifically, when the result of a kernel function equals zero, it indicates that the selected set of policies fails to consistently follow the same iterative path throughout the policy iteration process. Thus, the kernel function value reflects the consistency and reliability of policies during iteration. Moreover, the construction of the kernel function is crucial for verifying the convergence of policy iteration. In stochastic processes, the kernel function helps determine whether each state can effectively converge to a corresponding state at the boundary, thus ensuring convergence of the entire policy iteration. However, in deterministic systems, the lack of randomness means there is no need to consider boundary state points. Instead, the focus shifts to constructing a kernel function that verifies whether the chosen policy function ensures that the optimal state consistently follows the same iterative path. This simplification renders kernel function analysis in deterministic systems more efficient and straightforward. Additionally, enhancing the construction methods of kernel functions—such as refining their definitions and computational approaches—can improve the performance of policy iteration, thereby offering stronger theoretical support for analyzing deterministic systems.

Property 1. Difference function: The discrepancy cost function has the following properties:

Equation (4.8) represents a degenerate form of the AC equation, where

denotes the feasible state-action pair under the optimal policy at the $n$-th stage. $H_{n-1}$ represents the deviation function obtained from the $n-1$th stage of PI, with the value of this deviation function being the sum of the differences between the cost function and the AC along the subsequent iteration path.

Equation (4.9) indicates that the discrepancy value under the optimal policy differs from the discrepancy value along any feasible path state at the $n$-th stage. Equation (4.10) introduces the sequence $\gamma_{n}$, which signifies that as the iteration process reaches the $n-1$-th stage, the current deviation function is evaluated, and the next optimal policy is applied to continue calculating the deviation function along the current path. If the current selection in the iteration process fails to lead to convergence, even after selecting the next optimal policy, deviations may persist that the system cannot accept. In this context, the discrepancy $\gamma$ describes the potential for convergence within the iterative process.

From Eq (4.4):

The transformed form of Eq (4.8) is as follows:

By combining Eqs (4.11) and (4.12), we obtain:

Therefore, it is not difficult to derive:

If the sequence $\left\{\rho_{n}\right\}$ is monotonically decreasing, then there exists a lower bound 0 for $\left\{\gamma_{n}\right\}$ and also a lower bound for the sequence $\left\{H_{n}\right\}$.

Proposition 1. (1) Uniform boundedness: For some constants $0 < N < \infty$ such that

(2) Almost monotonicity:

There exists a sequence of functions $\left\{g_{n}: n \geq 0\right\}$ such that:

for some positive sequence satisfying the linear relationship

When $n$ increases $\alpha_{n} \downarrow 1, \; \beta_{n} \downarrow 0.$

In reference ^[10] the stability of the decision processes are reflected through the regression of linear functions. In this paper, the convergence of the cost function also satisfies this condition, where as $n$ increases, the function $H(x_n)$ point of convergence to ${g_n(x)}$, i.e.:

Proof of Theorem 5. Let $S$ be a compact set:

The upper bound for $\underline{c}(x)$ is not restricted to a specific value $2 \rho_{0}$ and can also be any finite function that contains $c(x)$. If there exists $\delta > 0$ such that

The state $\chi$ that each $\lambda_{n-1}$ can reach after the $n-1$th stage under the policy. The function $H(x)$ is almost everywhere bounded, and from Eqs (4.10) and (4.11), we have

If the selected state falls within the set $S$, then ${P_S} = 1$, for the cost function at stage $n$ the cost function is obvious, it is evident:

By Fatou's lemma, it is obtained that

The following inequality for the sum of probabilities falling into the set $S$ ensures the validity of the following expression:

Due to the boundedness of the cost function $c(\cdot)$, the following holds:

$\pi$ represents a constant for the difference between the maximum cost and the average cost. The original expression becomes:

In particular, when:

we have:

By Eq (4.14), the following inequality can be derived:

Thus, an upper bound for the discrepancy function is obtained as follows::

Likewise, it can be obtained that:

Thus, there exists:

Let

satisfying Eq (4.14). □

This completes the proof. Theorem 5 primarily describes the characteristics that policy iteration exhibits in deterministic systems, laying the foundation for the subsequent theorems.

4.3.   Convergence of the PI

In the previous section, the discussion of PI shifted focus to the discrepancy function, which has demonstrated that the cumulative cost discrepancy converges linearly to a value function. This result shows that in the decision-making process, the discrepancies between stages gradually stabilize, providing a preparatory condition for the convergence of PI. As a consequence, this approach relaxes the verification conditions for convergence. The following section will further validate the convergence of PI.

Assumption 2. For

(1) Each stage $n$, if the policy iteration generates a canonical triplet $(\lambda_{n-1}, H_{n-1}, \rho_{n-1})$ satisfying the Poisson equation (4.8):

which results in a solution and for $H_{t-1}$ being a bounded function

$H_{n-1}(x)$ it can be minimized, utilizing the decision Eq (4.4)

to find the next stage's policy $\lambda_n(x)$ for the next stage $n$.

(2) For a fixed $x$, the cost function $c(x, \cdot)$ and the function $\underline{c}(x)$ on the action space are functions resembling a norm, for any $x\in X$, $n \in Z^+$ for any satisfying:

Under this assumption, the algorithm iteratively generates stable policies.

Theorem 6. Strategy convergence theorem: If the above assumptions hold, for a certain stage $n$, the policy set $\left\{\lambda_{i}: i < n\right\}$ and the associated cumulative discrepancy functions $\left\{H_{i}: i < n\right\}$ are both defined through the policy iteration process, provided that:

(1) The relevant value function has a lower bound $i \leq n-1$;

(2) Under tight sets, the level sets of the value functions of the MDPs obtained under the strategy as per assumption 2 are all bounded.

Then for the PI, there exists a solution $(\lambda_n, H_n, \rho_n)$ such that

(1) The cumulative cost $H_n$ discrepancy is bounded from below;

(2) When $0 \leq i \leq t$, the constant $\rho_i$ is the average cost function at $i$ stage, i.e.,

and the cost sequence decreases, i.e.:

If the cumulative cost discrepancy

then the policy iteration converges.

Remark: In deterministic systems, the deterministic nature of the transition function and the validity of the average cost optimality inequality imply that the selection of policies during the iterative process effectively transforms into the selection of iterative paths. On one hand, the reduction of randomness contributes to enhancing the convergence of the algorithm. Throughout the iteration, there is an expectation that the optimal policy obtained at each stage will be included along the same iterative path. An increase in path determinacy signifies that policy selections will become more consistent, thereby improving the likelihood of converging to the optimal policy. On the other hand, the reduction of randomness can elevate the efficiency of the algorithm. When paths are more stable, the outcomes obtained during iteration will become more reliable, assisting in the reduction of unnecessary computations and accelerating convergence speed. The reduction of randomness reinforces the predictability of the decision-making processes, allowing the iterative algorithm to better assess the convergence of the policies. It is only when the randomness in path selection is diminished that the convergence conditions for the iteration can be satisfied, which is advantageous for both algorithm design and performance evaluation. In summary, as the number of iterations increases, the reduction of path randomness not only decreases the computational load but also provides a clearer indication of whether the iteration can converge, ultimately enhancing the performance of the algorithm in deterministic systems.

5.   Application of VI and PI

In Sections 3 and 4, the VI and the PI are proved to hold under deterministic systems. The idea is to optimize the policy step by step until the optimal policy is found by performing the two steps of policy evaluation and policy improvement alternately. In the policy iteration process, the two steps of policy evaluation and policy improvement are performed at each iteration, but the value function is used in each step. In Section 4, the main focus is on the PI for deterministic systems.

Example: (Brock-Mirman model ^[6,7]): For the infinite model, the criterion of discounting and non-discounting was introduced by Brock and Mirman ^[6,7]. The state and control variables $x_t, a_t$ denote capital and expenses at the time $t = 0, 1, 2, ...$, respectively. The state space is $X = (0, \infty)$, and the action space $A = (0, \infty)$ are Borel space, $A(x) = \left(0, r x^{\theta}\right]$. The dynamic process of the system is as follows:

Its initial state is $x_0$. Consider the objective function is to optimize the long-term AC:

Proof. From:

it can be shown that the cost function is:

for the AC inequality:

5.1.   Use of VI

These are the results obtained by Hernández et al. ^[4] on the AC criterion, which will be used as a basis to continue the discussion of the value iteration process in the following: assumption 1 is satisfied for Eqs (5.2)–(5.4), and for the difference function:

If $t \rightarrow \infty$, then:

Therefore, it can be seen that the discrepancy function is converging to a fixed value, and the iterative convergence of values is satisfied. □

5.2.   Use of PI

Continuation of Brock-Mirman model. If the $t$th difference function:

already satisfies Properties 1 and 2, then for the difference function at $t$th

The $T_{\lambda_{t}}$th is equal to the $T_{\lambda_{t-1}}$; this is because the strategy $\lambda_t$ at the $t$th is continued to be realized under the path generated by $\lambda_t-1$, so there is, when $t \rightarrow \infty$:

Satisfying the convergence of the PI. □

In the financial domain, many problems exhibit significant nonlinear characteristics, such as portfolio selection and option pricing. These nonlinear challenges often involve multiple factors, each contributing complex nonlinear effects. Such intricate dependencies not only complicate the direct resolution of the problems but also significantly increase the dimensionality of the state space.

In deterministic systems, the processes of value iteration and policy iteration provide an effective framework for addressing these challenges. In high-dimensional state spaces, these algorithms consolidate information from multiple related states into an abstract value by updating the state value function. This abstraction simplifies the decision-making process and reduces dimensionality, making it more feasible to handle high-dimensional decision problems. The Bellman equation plays a central role in this context. It recursively updates state values, effectively performing expected calculations of potential future returns for each state. Through each update, the algorithm uses existing information to assess the effectiveness of the current policy, thereby refining the strategy over time. Due to the dynamic nature of the system, the value dependencies among different states lead to the phenomenon of information sharing. This implies that the algorithm can efficiently synthesize and integrate information across iterations, utilizing prior learning to inform current decision-making. This mechanism of information sharing enables the derivation of effective strategies, even in the presence of complex, high-dimensional nonlinear problems.

Value iteration and policy iteration under deterministic systems not only offer a clear decision-making process but also provide theoretical support for tackling nonlinear problems. They leverage the interdependencies among states and the mechanisms of information sharing, thereby effectively addressing complex decision-making challenges.

5.3.   Simulation

In the value iteration, with the number of states is set to 10, the number of actions is set to 3, and the threshold value is set to $1 \times 10^{-3}$; the following results are obtained:

● Final value function: [0,3,3,0,0,0,3,3,0,0].

● Final average cost: 1.2.

● Figure 1.

From the above results, we can obtain the following results:

$(1)$ Final value function: This vector represents the optimal value for each state, obtained by the convergence of the value iteration algorithm. Some states (positions 2, 3, 7, and 8) have a higher value of 3, while other states have a value of 0. This indicates a higher expected return in these particular states, possibly due to their ability to reach the target state faster or reduce the average cost more effectively. The distribution of the value function reflects the priority or preference in different states, where states with a value of 3 are considered more advantageous, due to higher rewards or lower costs in these states.

$(2)$ Average cost: The average cost represents the expected cost per time step over an infinite operational period. The final average cost is 1.2, indicating that the current policy stabilizes the system's long-term operating cost.

$(3)$ Convergence analysis:

● Average cost convergence (middle plot): The average cost stabilizes at 1.2 after a few iterations, indicating that the current policy is near-optimal, as the average cost no longer fluctuates significantly. The stability of the average cost reflects the policy's effectiveness in balancing cost and return, allowing the system to operate at a low cost.

● Policy change convergence (left plot): In the left plot, the policy change rate rapidly decreases to near zero after the initial few iterations. This fast convergence aligns with the final value function and average cost results, indicating that the policy iteration finds a stable set of policies within a few steps, maintaining the final average cost at 1.2.

● Time per iteration (right plot): The time per iteration remains constant, showing that computation time did not increase with changes in state or policy. This is due to the simplification of the state space or the optimized handling of the algorithm.

In the policy iteration, when the number of states is set to 10, the number of actions is set to 3, but the threshold value is set to $1 \times 10^{-6}$ (policy iteration is faster), the following results are obtained:

● Final Policy: [0,0,0,2,1,0,0,0,2,1].

● Final Value Function: [0,0,0,0,0,0,0,0,0,0].

● Final average cost: 0.6.

● Figure 2.

From the above results, we can obtain the following results:

$(1)$ Final policy: The final policy vector represents the optimal action for each state in the state space. Each element corresponds to an action that minimizes the long-term cost for the specific state. In this case, the policy has converged, indicating the algorithm has found the preferred actions for each state based on the cost and transition functions.

$(2)$ Final value function: The value function for each state has converged to zero, suggesting that each state's cost balances out over time, leading to zero additional value. This outcome aligns with the final average cost and implies a steady-state configuration.

$(3)$ Final average cost: The average cost per time step, computed over an infinite horizon, converges to 0.6. This value indicates the expected cost that the system incurs per step under the optimal policy, reflecting a balance that minimizes the total cost per step.

$(4)$ Convergence analysis:

● Convergence rate of policy iteration (left plot): The policy change rate decreases rapidly, converging toward zero within a few iterations, indicating that the policy stabilizes quickly.

● Average cost convergence (middle plot): The average cost converges smoothly to 0.6, maintaining stability across iterations, suggesting the system reaches a steady state with minimal fluctuation in cost.

● Time per iteration (right plot): The time per iteration remains consistent, indicating that each iteration takes a similar amount of computational time, reflecting the stability of the processes.

Based on the simulation results mentioned above, we observe that the iterative process in deterministic systems is very rapid. When the initial threshold is set to $1 \times 10^{-3}$, policy iteration can achieve convergence in a remarkably short time. Therefore, even with increased precision requirements during the policy iteration process, convergence can still be realized within a short period ($1 \times 10^{-6}$).

As can be clearly seen from Figures 1 and 2, stability can be achieved in the iterative process without substantial fluctuations. This phenomenon is largely attributed to the fact that, in deterministic environments, the state transitions of the system are deterministic and the entire iterative processes are conducted offline. This presents a significant contrast to the work of He ^[16] and Fang ^[17,18]. Thus, the degraded value iteration and policy iteration are more suitable for this specific subfield of deterministic systems.

6.   Conclusions

This study primarily focuses on demonstrating the convergence of the value iteration and policy iteration under the average criterion in deterministic systems. The main areas of focus are divided into the following three parts:

$(1)$ Verification of the validity of DP in deterministic systems;

$(2)$ Convergence verification of the VI based on the AC criterion;

$(3)$ Convergence verification of the PI based on the AC criterion.

In deterministic systems, value iteration (VI) can converge to the optimal value function, exhibiting a notably improved convergence speed. Furthermore, policy iteration (PI), based on the value function, also demonstrates enhanced convergence. A comparison between the contents of Sections 3 and 4 reveals that PI is more intricate than VI. In practical applications, PI is often easier to understand, and the policy derived at each update step is more meaningful compared to the policy obtained after VI convergence. As demonstrated in Section 5, both value iteration and policy iteration algorithms in deterministic systems can more effectively address certain nonlinear problems.

However, the limitations of existing theorems primarily lie in their lack of robustness. Specifically, the theorems regarding stochastic Markov processes necessitate considering the "boundary" surrounding each state point, which influences the selected state and typically requires integration to eliminate uncertainty. In contrast, deterministic systems do not face this uncertainty: given a current state and action, the subsequent state will be deterministic, not subject to random fluctuations. Therefore, the transition function in deterministic systems needs adjustment. The originally stochastic transition function, arising from multiple state points, can be simplified into an indicator function, rendering state transitions clear and stable. This transformation not only simplifies the complexity of the model but also allows for the avoidance of challenges and limitations related to randomness in the application of theorems.

During the derivation process in this study, it was further observed that the policy iteration algorithm in deterministic systems exhibits decreasing randomness in paths as the number of iterations increases, a result distinct from those observed in stochastic processes. Given that the field of deterministic systems has not yet been fully developed into a comprehensive framework, certain aspects still rely on existing theorems. For example, in Sections 2 and 3, dynamic programming processes discussed by Hernandez et al. ^[4] were employed, and in Section 5, the properties of the policy iteration algorithm were based on Meyn's work ^[10] There may be better methods for defining kernel functions in deterministic systems. Hernandez ^[2] raised several unresolved questions at the conclusion of their work, emphasizing the need for further development in addressing these challenges. Once a more comprehensive system is established, adjustments can be made to address the imperfections in the framework set forth in this study.

Author contributions

Conceptualization, Zheng.H;

Methodology, Zheng.H;

Validation, Wang.D;

Formal analysis, Zheng.H and Wang.D;

Writing—original draft preparation, Zheng.H and Wang.D;

Writing—review and editing, Zheng.H;

Visualization, Wang.D. All authors have read and approved the final version of the manuscript for publication.

Conflict of interest

All authors disclosed no relevant relationship.