# Decomposition Methods for Solving Finite-Horizon Large MDPs

Authors: Bouchra el Akraoui; Cherki Daoui; Abdelhadi Larach; khalid Rahhali
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Conventional algorithms for solving Markov decision processes (MDPs) become intractable for a large finite state and action spaces. Several studies have been devoted to this issue, but most of them only treat infinite-horizon MDPs. This paper is one of the first works to deal with non-stationary finite-horizon MDPs by proposing a new decomposition approach, which consists in partitioning the problem into smaller restricted finite-horizon MDPs, each restricted MDP is solved independently, in a specific order, using the proposed hierarchical backward induction (HBI) algorithm based on the backward induction (BI) algorithm. Next, the sub-local solutions are combined to obtain a global solution. An example of racetrack problems shows the performance of the proposal decomposition technique.


---

## Body

## 1. Introduction

Stochastic models have recently gained a lot of attention in the artificial intelligent (AI) communities; it offers a suitable framework for solving problems with uncertainties. MDPs [1] are one such model that achieved promising results in numerous applications[2–4]. Most real-world problems have very large state spaces that require many mathematical operations and substantial memory. It is intractable to solve them with classical MDPs algorithms [5]. Motivated by these considerations, several recent types of research have used the decomposition technique to overcome the computational complexity. The decomposition approach introduced by Bather [6] divides the state space into strongly connected components (SCCs) according to certain levels and solves the small problems called restricted MDPs separately at each level to obtain the global solution of the original MDP by combining the partial solutions. Subsequently, Ross and Varadarajan [7] also proposed a similar decomposition technique for solving constrained limiting average MDPs. It is employed in various categories of MDPs (discounted, average, and weighted MDPs) in diverse studies [8, 9]. The weakness point of these approaches is their polynomial execution complexity. To accelerate the execution time Chafik and Daoui integrate the decomposition and parallelism schemes [10], unfortunately, the decomposition algorithm remains polynomial at runtime. Following, to accelerate the convergence time of the decomposition, Larach, and Daoui [11] investigated the state space decomposition approach into SCCs according to some levels based on Tarjan’s algorithm [12]. Subsequent work [13–15] developed approaches to solve MDPs with factorization methods that were introduced by [16]. The goal of factoring a problem is to decompose it into smaller items. Factored MDPs produce compact representations of complex and uncertain systems allowing for an exponential reduction in the complexity of the representation [17]. These factorized approaches represent states as factorized states with an internal structure and state transition matrices as dynamic Bayesian networks (DBNs). However, methods for solving representations based on factorized DBNs do not exploit advances in tensor decomposition methods for representing large atomic MDPs. More recently, research such as [17, 18] exploits a similar idea to the thesis of Smart and [19] aims at improving the efficiency of MDP solvers by using tensor decomposition methods to compact state transition matrices. The solver uses the value iteration and policy iteration algorithms to compute the solution compactly. The authors try different ways to parallelize their proposed approaches, but no improvement in the execution time is observed. These methods are based on multiplications between small tensor components. More recently, work has been carried out to address this problem in the context of parallelism [20] presenting a way to decompose an MDP into SCCs and find dependency chains for these SCCs. They solve independent chains of SCCs with a proposed variant of the topological value iteration (TVI) algorithm, called parallel chained TVI aimed at improving the execution time on GPUs. In this context, research groups [21–23] have improved iterative algorithms in parallel versions to accelerate their convergence.The literature mentioned above focuses only on solving different types ofMDPs under the infinite-horizon criterion. It is difficult to find papers that focus on solving large non-stationary finite-horizon MDPs. This paper is oriented in this underexplored direction, the main objective of this work is to propose a new decomposition technique tackling the challenges of reducing memory requirements and computational cost.The proposed technique consists in partitioning the global problem into smaller restricted finite-horizonMDPs, each restricted MDP is solved independently, in a specific order, using the backward induction algorithm. Next, the sub-local solutions are combined to obtain a global solution.There are several problems modeled asMDPs with an initial given state i0, then the optimal action f(i0), and the optimal value VT(i0) are computed by solving just the restricted MDP corresponding to the classes accessible from the class containing i0 (one does not need to consider all states). This is also an advantage of this method, which reduces memory consumption and speeds up the computation time.The remainder of the article is organized as follows: the second section introduces the fundamentals of finite-horizonMDPs. The third section focuses on the decomposition technique and describes the new finite-horizon restricted MDP. The fourth section presents the proposed hierarchical backward induction algorithm. The last section illustrates the advantages of this decomposition technique by its application to a racetrack problem. The paper concludes with conclusions and prospects for future work.


## 2. Markov Decision Process

Markov decision processes have been widely studied as an elegant mathematical formalism for many decision-making problems in a variety of fields of science and engineering [24]. The objective is to approximate the best decision policies (action selection) to achieve maximum expected rewards (minimum costs) in a given stochastic dynamic environment satisfying the Markov property [1]. In this section, we will present non-stationary finite-horizon MDP with a finite state and action spaces.Formally, a non-stationaryMDP with a finite-horizon is defined by five-tuple (S, A, T, P, and R), where S and A are the state and action spaces; T is the time horizon; P denotes the state transition probability function, where PSt+1=j|St=i,At=a=piajt is the probability of transition from state i to state j by taking action a at time t; St (At) is a random variable indicating the state (action) at time t; R supplies the reward function defined on state transitions, where riat indicates the reward gained if the action a is executed in the state at t period. Most solvers of MDPs attempt to find an optimal policy that specifies (optimal) action should be taken for each agent at each state. If the process will be considered a finite planning horizon T, an optimal policy π∗ is given as the policy that maximizes the expected reward. π∗ maximizes the value function of the Bellman equation [24]: viTπ∗=supπviTπ,i∈E, where viTπ is the total expected reward in T periods, given that the process starts from initial state i and the policy π is used.(1)viTπ=∑t=1T∑j∈E∑a∈AjPπXt=j,Yt=a|X1=irjat,where Xt and Yt are the random variables representing, respectively, the state and action at time t. Besides, we define the optimal value vector VT:(2)ViT=supπviTπ,i∈E.It is well known that the backward induction algorithm is one of the most common iterative methods used to find an optimal policy. In the next section, we will discuss it in more detail.


## 3. Backward Induction Algorithm

In this section, we compute an optimal policy as well as the optimal value vector using the backward induction algorithm, its iterative process starting at the end of the planning horizonT, one computes the values for the previous periods. Then, after T iterations an optimal policy is found.The following theorem introduced in [25] demonstrates the validity of the BI algorithm:Theorem 1.
LetxiT+1=0, i ∈ S. Define recursively for t = T, T - 1,…, 1, a deterministic decision rule ft and the vector xt as follows:(i)
rfti+Pftxt+1i=maxa∈Airiat+∑jpiajtxjt+1,i∈S,(ii)
xt=rft+Pftxt+1,then R∗= (f1, f2, …, fT) is an optimal policy and x1 is the optimal value vector VT.Proof.
(see [25]).
To accelerate the execution time of the classicalBIalgorithm, the authors used the proposal of [11], they introduced for each action a the list of state-action successors denoted by Γa+i, where Γa+i=j∈E:Piajt>0,t=1,…,T. This allowed to reduce the time complexity from OTAE2 to OTΓa+E2 arithmetic operations, where Γa+ denotes the average number of state-action successors; T designs the horizon and E is the number of states. Algorithm 1 describes the ameliorated backward induction algorithm (ABI) as follows:Algorithm 1: Ameliorated backward induction.
(1)
ABI (In MDP: E,P,A,R,T; Out VT,R∗(2)
t⟵T+1;(3)
∀j∈E Take vjT+1⟵0;(4)
Repeat(5)
t⟵t−1:(6)
For eachi∈E Do(7)
rfti+Pftvt+1i=maxa∈Airiat+∑j∈Γa+ipiajtvjt+1 //The Deterministic Decision Rule ft(8)
vt=rft+Pftvt+1(9)
For eachi∈E Do(10)
R∗=f1,f2,…,fT is an optimal policy and v1 is the optimal value vector.11
ReturnVT,R∗


## 4. Hierarchical Backward Induction Algorithm

TheBI algorithm becomes quite impractical to compute an optimal policy for finite-horizon MDPs with large state space. For non-stationary finite-horizon MDPs, the computing load can increase further. To overcome this issue, we describe, in this section, a new decomposition technique for improving the performance and reducing the time running.


### 4.1. The Decomposition Technique

Let us consider an oriented graphG = (S, U), associated with the original MDP, where S is a set of nodes that represents a state space and U=i,j∈S:∃a∈AiPiaj≻0 is a set of directed arcs. There exists a unique partition S = C1∪C2…∪Cp of the state space S into strongly connected classes. Note that the SCCs are deﬁned to be the classes with respect to the relation on G deﬁned by i is strongly connected to j if and only if i = j or there exists a directed path from i to j and a directed path from j to i. There are many good algorithms in graph theory for the computation of such partition, e.g., see [11].Now, we construct by induction the levels of the graphG. The level L0 is formed by all closed classes Ci, that is for all i∈Ci;a∈Ai:Piaj=0 for all j∉Ci. The level Lp is formed by all classes Ci such that the end of any arc emanating from Ci is in some levels Lp−1, Lp−2,. . ., L0. After finding the SCCs using Tarjan’s algorithm, their belonging levels are found by using the following algorithm (algorithm 2) introduced in [26].Algorithm 2: Finding levels.
(i)
(Ω) ⟵ E; n ⟵ 0; Ln ⟵{ Ci: Ci is closed }(ii)
If L0 = E Stop.(iii)
Otherwise, unless Ω ≠ ∅; do(iv)
DeleteLn (i.e., Ω ⟵ Ω/Ln and eliminate all arcs coming into Ln);(v)
Ln + 1 ⟵{ Ci: Ci is closed in the restricted MDP to Ω};(vi)
n ⟵n + 1.For each levelLn, n = 0, 1, 2, ..., L. Let (Clk), k ∈{1, 2, …, K(l)} be the strongly connected classes corresponding to the nodes in level l (see Figure 1). Each class Clk leads to a partial MDPlk that is solved independently, the global solution is obtained by combining these partial solutions.Figure 1
Example of SCCs and their levels.The hierarchical method used by several researchers for several categories ofMDPs, addresses the “curse of dimensionality” of large MDPs, was described by [27] and later further developed by [11, 26]. It consists of breaking up the state space into small subsets, solving the restricted MDPs problems corresponding to these subsets, and combining these solutions to determine the solution of the global problem. Based on the above decomposition technique, the authors propose, a hierarchical backward induction (HBI) algorithm by decomposing the original finite-horizon MDPs into restricted MDPs corresponding to each SCC. These restricted MDPs are solved independently and according to their level.The performance of the proposed algorithm is exposed after the search for the optimal policy of the known initial state, the algorithm solves only the restrictedMDP corresponding to the reachable classes of the initial state. For example, in Figure 1, the initial state S0 is in class C10. Only the restricted MDPs corresponding to the SCCs: C10, C00, and C01 are solved.In the next section, we will define newMDPs called the restricted finite-horizon MDPs.


### 4.2. The Restricted Finite-Horizon MDPs

In this work, we consider non-stationary finite-horizonMDPs with large finite state and action spaces. Now, we construct the restricted MDPnk corresponding to each strongly connected class Cnk, k ∈ {1, 2, …, K (n)} in level Ln as follows:(i)
etEn=∪iεCpk,p=0,1,…,n−1andkε1,2,…,kp.(ii)
States space:Snk=Cnk∪jεEn|∑iεCnk,a∈Ai;piajt>0,t=1,…,T;(iii)
Actions space: ForiεSnk,Anki=Ai,ifiεCnkθ,Otherwize;(iv)
Transition probabilities: Fort = 1,2, …,T,(v)
fori,jεSnk,pnkti,a,j=piajtif,iεCnk,a∈Ai1,ifi=j,i∉Cnk;(vi)
Reward function: Fort = 1,2, …,T.(vii)
IfiϵCnk,rpkti,a=riat;(viii)
IfiεSnk/Cnk, ∃mε0,1,…,n−1,∃hε1,2,…,km {: iεCmh,rnkti,θ=VmhTi/N.N is the horizon and VmhT is the optimal value vector of MDPmh calculated in the previous levels.According to the definition of the restricted finite-horizonMDPs, we remark that.The restricted finite-horizonMDPs are solved according to the ascending order of levels and in the same level Lp. The restricted finite-horizon MDPs are independent, so they can be solved in parallel.


### 4.3. Hierarchical Backward Induction Algorithm

Based on the above restricted finite-horizonMDPs, the authors present in this section, a new algorithm called hierarchical backward induction (HBI) algorithm (algorithm 3). The main contribution is to show that the optimal value in the restricted MDPpk is equal to the optimal value in the original MDP (Theorem 2).Now, the corresponding restricted finite-horizonMDPs are constructed and immediately solved by using this procedure:Algorithm 3: Hierarchical backward induction.
(1)
HBI (In MDP: E,P,A,R,T, Out (VT,R∗)(2)
FindSCCs and their belonging levels using Tarjan’s algorithm(3)
For each level Lp,p=0,…, Lp Do(4)
For each class Clpk, in level Lp(5)
Construct the restricted finite-horizon MDPpk(6)
End For(7)
End For(8)
For each level Lp,p=0,…, Lp Do(9)
For each classCpk, in level Lp over planning horizon T, Do(10)
ABI (MDPpk)(11)
End For(12)
End For(13)
ReturnVT,R∗The following theorem shows the validity of theHBI algorithm.Theorem 2.
LetR∗= (f1, f2, …, fT) and VT are, respectively, an optimal policy and the optimal value vector in the original MDP. If Rpk=fpk1,fpk2,…,fpkT and VpkT are, respectively, an optimal policy and the optimal value vector in the restricted MDPpk, then for all i ϵ Cpk, for t = 1,2, …,T, fpkt (i) = ft (i) is an optimal action in the original MDP and VpkTi=VTi.Proof.
The proof is by induction. Forp=0 (level L0);k∈1,...,K0. Let R0k=f0k1,f0k2,…,f0kT and V0kT are, respectively, an optimal policy and the optimal value vector in the restricted MDP0k.
According to Theorem1, we have for t = T, T − 1,…, 1:(3)∀i∈S0k,f0kti=argmaxa∈A0kir0kti,a+∑j∈S0kp0kti,a,jxjt+1,xt=rf0kt+Pf0ktxt+1,from the definition of the restricted MDP0k, the state space S0k = C0k, the action space A0k(i) = A(i) for i ∈ S0k, for t = T, T − 1,…, 1 the transition probabilities p0kti,a,j=pti,a,j for all i, j ∈ C0k, a ∈ A0k (i), the rewards r0kti,a=riat.
Furthermore, the classC0k is closed then for t = 1, …, T. From (3), we have(4)∀i∈C0k,f0kti=argmaxa∈Airiat+∑j∈Epti,a,jxjt+1,xt=rf0kt+Pf0ktxt+1,therefore, for all i∈C0k and t = 1, …, T, f0kti=fti is an optimal action for the global MDP and(5)V0kTi=xi1=VTi.
Suppose that the result is true until the levelp-1. Now we shall show that the result is still true in the level p.
The state space of the restrictedMDPpk is Spk=Cpk∪j∈Ep:piajt>0for alliεCpk,aεAi, where(6)Ep=∪iεCmk,m=0,1,…,p−1;kε1,2,…,Km.
LetRpk=fpk1,fpk2,…,fpkT and VpkT are, respectively, an optimal policy and the optimal value vector in the restricted MDPpk.
According to Theorem 1, we have fort = T, T − 1,…, 1:(7)∀i∈Spk,fpkti=argmaxa∈Apkirpkti,a+∑j∈Cpkppkti,a,jxjt+1xt=rfpkt+Pfpktxt+1,,
Based on the definition of the restrictedMDPpk, for i ∈ Spk, if i ∈ Cpk, Apk(i) = A(i), for a ∈ Apk(i), the rewards rpkti,a=riat and the transition probabilities ppkti,a,j=pti,a,j for all j ∈ Spk.
In fact, that and sinceppkti,a,j=0,∀i∈Spk,∀jεE/Spk, then for t = 1, …, T,fpkt verifies(8)∀i∈Cpk,fpkti=argmaxa∈Airiat+∑j∈Epti,a,jxjt+1,xt=rfpkt+Pfpktxt+1.
By consequence, fori∈Cpk and t = 1, …, T, fpkti=fti is an optimal action for the global MDP, and, VpkTi=xi1=VTi.
Now, It remains to see the case wherei∈Spk/Cpk,∑m∈0,1,…,p−1,∑h∈1,2,…,Km:i∈Cmh and rpkti,θ=Vmhti/N.
From the recurrence hypothesisfmhti=fti is an optimal action for the global MDP, calculated in previous levels, it remains to verify that VpkTi=VTi.
Since fori∈Spk/Cpk and t = 1, …, T, fpkti=θ then Pfpktii = 1 and rfpkti =  Vmhti/N.
It follows from (5):(9)VpkTi=xi1=…=∑s=1NPfpk1Pfpk2…Pfpks−1rfpks=∑s=1NVmhtiN=VTi.Remark 1.
If the initial state i0 is known, its optimal action f(i0) and its optimal value VT(i0) are computed by solving just few restricted MDPs: one does not need to consider all states. The following algorithm (algorithm 4) explains this issue.
It is clear that, f(i0) and VT(i0) are obtained by solving only MDPmk. ♦
To demonstrate the benefit of the proposedHBI algorithm, we consider a case study of the racetrack problem described in the following section.Algorithm 4: Accelerated HBI algorithm.
Step 1.
Determine the classCmk such that i0 ∈ Cmk.Step 2.
Determine the classes Cnh, n∈{0, 1, …, m}; h ∈{1, 2,.., k(n)} such that the end of any arc emanating from Cmk is in the classes CnhStep 3.
Solve the restricted MDPnh found in Step 2.


## 4.1. The Decomposition Technique

Let us consider an oriented graphG = (S, U), associated with the original MDP, where S is a set of nodes that represents a state space and U=i,j∈S:∃a∈AiPiaj≻0 is a set of directed arcs. There exists a unique partition S = C1∪C2…∪Cp of the state space S into strongly connected classes. Note that the SCCs are deﬁned to be the classes with respect to the relation on G deﬁned by i is strongly connected to j if and only if i = j or there exists a directed path from i to j and a directed path from j to i. There are many good algorithms in graph theory for the computation of such partition, e.g., see [11].Now, we construct by induction the levels of the graphG. The level L0 is formed by all closed classes Ci, that is for all i∈Ci;a∈Ai:Piaj=0 for all j∉Ci. The level Lp is formed by all classes Ci such that the end of any arc emanating from Ci is in some levels Lp−1, Lp−2,. . ., L0. After finding the SCCs using Tarjan’s algorithm, their belonging levels are found by using the following algorithm (algorithm 2) introduced in [26].Algorithm 2: Finding levels.
(i)
(Ω) ⟵ E; n ⟵ 0; Ln ⟵{ Ci: Ci is closed }(ii)
If L0 = E Stop.(iii)
Otherwise, unless Ω ≠ ∅; do(iv)
DeleteLn (i.e., Ω ⟵ Ω/Ln and eliminate all arcs coming into Ln);(v)
Ln + 1 ⟵{ Ci: Ci is closed in the restricted MDP to Ω};(vi)
n ⟵n + 1.For each levelLn, n = 0, 1, 2, ..., L. Let (Clk), k ∈{1, 2, …, K(l)} be the strongly connected classes corresponding to the nodes in level l (see Figure 1). Each class Clk leads to a partial MDPlk that is solved independently, the global solution is obtained by combining these partial solutions.Figure 1
Example of SCCs and their levels.The hierarchical method used by several researchers for several categories ofMDPs, addresses the “curse of dimensionality” of large MDPs, was described by [27] and later further developed by [11, 26]. It consists of breaking up the state space into small subsets, solving the restricted MDPs problems corresponding to these subsets, and combining these solutions to determine the solution of the global problem. Based on the above decomposition technique, the authors propose, a hierarchical backward induction (HBI) algorithm by decomposing the original finite-horizon MDPs into restricted MDPs corresponding to each SCC. These restricted MDPs are solved independently and according to their level.The performance of the proposed algorithm is exposed after the search for the optimal policy of the known initial state, the algorithm solves only the restrictedMDP corresponding to the reachable classes of the initial state. For example, in Figure 1, the initial state S0 is in class C10. Only the restricted MDPs corresponding to the SCCs: C10, C00, and C01 are solved.In the next section, we will define newMDPs called the restricted finite-horizon MDPs.


## 4.2. The Restricted Finite-Horizon MDPs

In this work, we consider non-stationary finite-horizonMDPs with large finite state and action spaces. Now, we construct the restricted MDPnk corresponding to each strongly connected class Cnk, k ∈ {1, 2, …, K (n)} in level Ln as follows:(i)
etEn=∪iεCpk,p=0,1,…,n−1andkε1,2,…,kp.(ii)
States space:Snk=Cnk∪jεEn|∑iεCnk,a∈Ai;piajt>0,t=1,…,T;(iii)
Actions space: ForiεSnk,Anki=Ai,ifiεCnkθ,Otherwize;(iv)
Transition probabilities: Fort = 1,2, …,T,(v)
fori,jεSnk,pnkti,a,j=piajtif,iεCnk,a∈Ai1,ifi=j,i∉Cnk;(vi)
Reward function: Fort = 1,2, …,T.(vii)
IfiϵCnk,rpkti,a=riat;(viii)
IfiεSnk/Cnk, ∃mε0,1,…,n−1,∃hε1,2,…,km {: iεCmh,rnkti,θ=VmhTi/N.N is the horizon and VmhT is the optimal value vector of MDPmh calculated in the previous levels.According to the definition of the restricted finite-horizonMDPs, we remark that.The restricted finite-horizonMDPs are solved according to the ascending order of levels and in the same level Lp. The restricted finite-horizon MDPs are independent, so they can be solved in parallel.


## 4.3. Hierarchical Backward Induction Algorithm

Based on the above restricted finite-horizonMDPs, the authors present in this section, a new algorithm called hierarchical backward induction (HBI) algorithm (algorithm 3). The main contribution is to show that the optimal value in the restricted MDPpk is equal to the optimal value in the original MDP (Theorem 2).Now, the corresponding restricted finite-horizonMDPs are constructed and immediately solved by using this procedure:Algorithm 3: Hierarchical backward induction.
(1)
HBI (In MDP: E,P,A,R,T, Out (VT,R∗)(2)
FindSCCs and their belonging levels using Tarjan’s algorithm(3)
For each level Lp,p=0,…, Lp Do(4)
For each class Clpk, in level Lp(5)
Construct the restricted finite-horizon MDPpk(6)
End For(7)
End For(8)
For each level Lp,p=0,…, Lp Do(9)
For each classCpk, in level Lp over planning horizon T, Do(10)
ABI (MDPpk)(11)
End For(12)
End For(13)
ReturnVT,R∗The following theorem shows the validity of theHBI algorithm.Theorem 2.
LetR∗= (f1, f2, …, fT) and VT are, respectively, an optimal policy and the optimal value vector in the original MDP. If Rpk=fpk1,fpk2,…,fpkT and VpkT are, respectively, an optimal policy and the optimal value vector in the restricted MDPpk, then for all i ϵ Cpk, for t = 1,2, …,T, fpkt (i) = ft (i) is an optimal action in the original MDP and VpkTi=VTi.Proof.
The proof is by induction. Forp=0 (level L0);k∈1,...,K0. Let R0k=f0k1,f0k2,…,f0kT and V0kT are, respectively, an optimal policy and the optimal value vector in the restricted MDP0k.
According to Theorem1, we have for t = T, T − 1,…, 1:(3)∀i∈S0k,f0kti=argmaxa∈A0kir0kti,a+∑j∈S0kp0kti,a,jxjt+1,xt=rf0kt+Pf0ktxt+1,from the definition of the restricted MDP0k, the state space S0k = C0k, the action space A0k(i) = A(i) for i ∈ S0k, for t = T, T − 1,…, 1 the transition probabilities p0kti,a,j=pti,a,j for all i, j ∈ C0k, a ∈ A0k (i), the rewards r0kti,a=riat.
Furthermore, the classC0k is closed then for t = 1, …, T. From (3), we have(4)∀i∈C0k,f0kti=argmaxa∈Airiat+∑j∈Epti,a,jxjt+1,xt=rf0kt+Pf0ktxt+1,therefore, for all i∈C0k and t = 1, …, T, f0kti=fti is an optimal action for the global MDP and(5)V0kTi=xi1=VTi.
Suppose that the result is true until the levelp-1. Now we shall show that the result is still true in the level p.
The state space of the restrictedMDPpk is Spk=Cpk∪j∈Ep:piajt>0for alliεCpk,aεAi, where(6)Ep=∪iεCmk,m=0,1,…,p−1;kε1,2,…,Km.
LetRpk=fpk1,fpk2,…,fpkT and VpkT are, respectively, an optimal policy and the optimal value vector in the restricted MDPpk.
According to Theorem 1, we have fort = T, T − 1,…, 1:(7)∀i∈Spk,fpkti=argmaxa∈Apkirpkti,a+∑j∈Cpkppkti,a,jxjt+1xt=rfpkt+Pfpktxt+1,,
Based on the definition of the restrictedMDPpk, for i ∈ Spk, if i ∈ Cpk, Apk(i) = A(i), for a ∈ Apk(i), the rewards rpkti,a=riat and the transition probabilities ppkti,a,j=pti,a,j for all j ∈ Spk.
In fact, that and sinceppkti,a,j=0,∀i∈Spk,∀jεE/Spk, then for t = 1, …, T,fpkt verifies(8)∀i∈Cpk,fpkti=argmaxa∈Airiat+∑j∈Epti,a,jxjt+1,xt=rfpkt+Pfpktxt+1.
By consequence, fori∈Cpk and t = 1, …, T, fpkti=fti is an optimal action for the global MDP, and, VpkTi=xi1=VTi.
Now, It remains to see the case wherei∈Spk/Cpk,∑m∈0,1,…,p−1,∑h∈1,2,…,Km:i∈Cmh and rpkti,θ=Vmhti/N.
From the recurrence hypothesisfmhti=fti is an optimal action for the global MDP, calculated in previous levels, it remains to verify that VpkTi=VTi.
Since fori∈Spk/Cpk and t = 1, …, T, fpkti=θ then Pfpktii = 1 and rfpkti =  Vmhti/N.
It follows from (5):(9)VpkTi=xi1=…=∑s=1NPfpk1Pfpk2…Pfpks−1rfpks=∑s=1NVmhtiN=VTi.Remark 1.
If the initial state i0 is known, its optimal action f(i0) and its optimal value VT(i0) are computed by solving just few restricted MDPs: one does not need to consider all states. The following algorithm (algorithm 4) explains this issue.
It is clear that, f(i0) and VT(i0) are obtained by solving only MDPmk. ♦
To demonstrate the benefit of the proposedHBI algorithm, we consider a case study of the racetrack problem described in the following section.Algorithm 4: Accelerated HBI algorithm.
Step 1.
Determine the classCmk such that i0 ∈ Cmk.Step 2.
Determine the classes Cnh, n∈{0, 1, …, m}; h ∈{1, 2,.., k(n)} such that the end of any arc emanating from Cmk is in the classes CnhStep 3.
Solve the restricted MDPnh found in Step 2.


## 5. Case Study and Experimental Results

To show the advantage of the proposedHBI algorithm, we consider a standard control racetrack problem described by Martin Gardner [28] and Barto [29]. The goal is to control the movement of a race car along a predefined racetrack so that the racer can get to the finish line from starting the line in the minimum amount of time.At each time step, the state of the racer is given by the tuples (Xt, Yt, Vx(t), Vy(t)) that represent the position and speed of the car in the x, y dimensions at time t. The actions are pairs a = (ax, ay) of instantaneous accelerations, where ax, ay ϵ {−1, 0, 1}. We assume that the road is ‘slippery’ and the car may fail to accelerate. An action a = (ax, ay) has its intended effect 90% of the time; 10% of the time the action effects correspond to those of the action a0 =(0; 0). Also, when the car hits a wall, its velocity is set to zero and its position is left intact. When the car is state (Xt, Yt, Vx(t), Vy(t)) and the action taken is a = (ax, ay), it transit with 90% probability to a state (Xt + Vx(t)+ax, Yt + Vy(t) +ay, Vx(t)+ax, Vy(t)+ay).Let s = (Xt, Yt, Vx(t), Vy(t)), a = (ax, ay) and s″= (Xt + Vx(t)+ax, Yt + Vy(t)+ay, Vx(t)+ax, Vy(t)+ay), the transition probability is defined as follows:(10)Ps′|s,a=1,0.9,0.1,0,ifs′=sands=s″,ifs≠s′ands′=s″,ifs=s′ands′≠s″,otherwise.To complete the formulation of the finite-horizonMDP problem, we need to define the reward function and the horizon. Independently of the action taken, the immediate reward for all non-goal states is equal to −1, i.e., Ri =  − 1 and it is equal to zero for any goal state reached, i.e., Rg = 0. The horizon is determined after the decomposition into levels; indeed, during this decomposition, the maximum level obtained will be considered as the horizon.To restrict the possible infinite state space, we assume that the speed of the car in thex, y dimensions are bounded in the range [ − 7,  + 7], i.e., Vx(t), Vy(t) ϵ [−7, +7]. The speed will not change if the agent attempts to accelerate beyond these limits.The proposed algorithms are tested using Intel(R) Core(TM) i7-6500 U (2.6 GHz),C++ implementation, Windows 10 operating system (64 bits).Figure2 presents the three racetracks considered, blues cells represent the initial states, and green cells represent the goal states.Figure 2
Racetrack’s example.Table1 presents the horizon, the number of SCCs, and the number of possible states obtained with the decomposition algorithm into levels for the three considered racetrack problems. As it can be seen, the number of states is reduced. Table 2.Table 1
Characteristics of the three racetracks.
MDP’s horizonNumber of possible statesNumber of SCCsRace-1311327505120Race-2181062005103Race-3481233003554Note. The value iteration (VI) algorithm under the infinite-horizon discounted MDP is used in [30] in order to solve racetrack problems. presents the comparison between VI, BI, and HBI algorithms. As it can be seen, the BI algorithm outperforms the VI algorithm, but the proposed HBI algorithm is more efficient than the BI algorithm.Table 2
Performance of theHBI algorithm.
Execution time (s)VI algorithmBI algorithmHBI algorithmRace-19, 74, 43Race-26, 73, 62, 6Race-38, 43, 92, 8Figures3–5 show the policy obtained with VI, BI, and HBI algorithms for the three racetracks problems. As it can be seen, we obtain the same policy with the three algorithms.Figure 3
Road generated by VI, BI, and HBI algorithms for the racetrack-1.Figure 4
Road generated by VI, BI, and HBI algorithms for the racetrack-2.Figure 5
Road generated by VI, BI, and HBI algorithms for the racetrack-3.


## 6. Conclusion

In this paper, we have presented a new hierarchical backward induction algorithm for finite-horizon non-stationaryMDP that is successful for large state spaces. It consists in decomposing the original problem into smaller restricted MDPs; indeed in each level and for each SCC a restricted finite-horizon MDP is constructed and solved independently from the other restricted MDPs of the same level. This proposed method accelerated the calculation time and reduces the memory requirement.To show the advantage of the proposedHBI algorithm, we applied it to racetrack problems. The experimental results show that the HBI algorithm outperforms better the standard BI and value iteration algorithm. From a perspective, the use of parallelism techniques could further accelerate the convergence of the hierarchical finite-horizon MDPs.



---

*Source: 8404716-2022-08-13.xml*