# Exact Decomposition Approaches for Markov Decision Processes: A Survey

Authors: Cherki Daoui; Mohamed Abbad; Mohamed Tkiouat
Journal: Advances in Operations Research
 (2010)

---

## Abstract

As classical methods are intractable for solving Markov decision processes
(MDPs) requiring a large state space, decomposition and aggregation techniques are very useful to cope with large problems. These techniques are
in general a special case of the classic Divide-and-Conquer framework to
split a large, unwieldy problem into smaller components and solving
the parts in order to construct the global solution. This paper reviews
most of decomposition approaches encountered in the associated literature
over the past two decades, weighing their pros and cons. We consider several categories of MDPs (average, discounted, and weighted MDPs), and
we present briefly a variety of methodologies to find or approximate optimal strategies.


---

## Body

## 1. Introduction

This survey focuses on decomposition techniques for solving large MDPs.  However, in this section we begin by discussing briefly some approaches to treat large Markov chain models because they contain basic ideas of methods to tackle large MDPs.


### 1.1. Large Markov Chain Models

Markov chain models are still the most general class of analytic models widely used for performance and dependability analysis. This class of problems is robust in terms of its ability to represent a very broad class of models of interest. Unfortunately, the characteristics of many models (complex interactions between components, sophisticated scheduling strategies, synchronization among parallel tasks, etc.) preclude the possibility of closed-form solutions, in general. Numerical solution methods are the most general solution methods [1]. The most pervasive practical limitation to the use of numerical solution techniques is the size of the state space of realistic models. One natural way to deal with this problem is via state space reduction techniques, that is, a transformation of the model to one with fewer states. Another is to modify the model to one with a structure which enables efficient solution. The transformed model in general is an approximation of the original model. Several classes of such transformations are described below.There are several methods of state space reduction that are applicable to Markov chain models. One such method is combining “lumpable states” [2]. When lumping applies, it is exact, but only partial information is retrievable from the solution except in very special circumstances. Also, lumping is only valid for models that have certain very limited types of structure.Another method to treat large state spaces is aggregation/disaggregation [3]. This applies particularly well to cases in which the system model can be viewed as an interacting set of tightly coupled subsystems. The solution method is generally an iterative one in which submodels are solved and the obtained results are used to adjust the submodels repetitively until a convergence criterion is met. This is an efficient procedure if (a) the model is decomposable into tightly coupled submodels, (b) the state space of each submodel is practically solvable, and (c) the number of such submodels is not too large.There is an additional property of many models that is not capitalized on by any of the above methods. In many important cases, although the state space is extremely large, the stationary state probability distribution is highly skewed, that is, only a small subset of the states account for the vast majority of the probability mass. This is easily illustrated by considering the nature of several modeling application areas. This observation indicates that most of the probability mass is concentrated in a relatively small number of states in comparison to the total number of states in the model. During its lifetime, the system spends most of its time in this relatively small subset of states and only rarely reaches other states. The above observation is used to motivate truncation of the model state space, that is, choose to only represent a subset of the more “popular” states and ignore the remainder, deleting transitions from the represented states to the “discarded states”. Some form of heuristic is often used to decide which states to retain and which to discard. For dependability models a simple heuristic might be to discard all states in which the system has more than a certain number of failed components. A more sophisticated heuristic for determining which states to retain is described in [4]. The most persistent practical constraint to the use of the above state space truncation is that in certain models (health management, reliability, security problems) deleting some infrequently states may cause significant fatalities.There is also the issue of how much error is introduced by state space truncation. For some transient measures, error bounds are easily obtained by introducing trap states [5]. For example, in dependability analysis we may be interested in interval reliability. For this purpose one can introduce a trap state and change all transitions to “discarded states” into transitions to the trap state. Then the importance of the error is a direct function of the probability that the system is in the trap state at the end of the interval. For-steady state measures, the issue of error bounds can be more difficult. There are a number of approaches available for computing bounds or for proving that one model provides a bound compared with some other model. Among these we can quote the method of Courtois and Semal [6, 7], the methods based on sample-path analysis and stochastic ordering [8, 9], and the bias terms approach of Van Dijk [10].In [11], the authors explain with some examples where the model modifications only affect the less popular states and therefore have less effect on the performance measures. They also present some methods to compute bounds on performance measures.


### 1.2. Large Markov Decision Models

Over the past five decades there has been a lot of interest within planning community in using stochastic models, which provide a good framework to cope with uncertainties. Among them, Markov decision processes [12–22], either fully observable (MDP or FOMDP) or partially observable (POMDP), have been the subject of several recent studies [23–30]. The optimal strategy is computed with respect to all the uncertainties, but unfortunately, classical algorithms used to build these strategies are intractable with the twin drawbacks of large environments and lack of model information in most real-world systems [31–33]. Several recent studies aim to obtain a good approximation of the optimal strategy. Among them, aggregation and decomposition techniques have been the subject of a lot of attention. These techniques are really different flavors of the well-known framework Divide-and-Conquer: (1) partitioning the state space on regions, that is, transforming the initial MDP into small local MDPs, (2) independently solving the local MDPs, and (3) combining the local solutions to obtain an optimal (or near-optimal) strategy for the global MDP.In preparing this survey, we first attempt to summarize some general decomposition approaches introduced in [34–38]. These works have proposed some algorithms to compute optimal strategies as opposed to nearly all methods to treat large MDPs that compute only near optimal strategies. Moreover, they are suitable to several categories of MDPs (average, discounted and weighted MDPs) and can be applicable to many practical planning problems. These algorithms are based on the graph associated to the original MDP and by introducing some hierarchical structure of this graph.A lot of other recent works are concerned with autonomous exploration systems which require planning under uncertainty. In [39], the authors present a main decomposition technique to cope with large state spaces for practical problems encountered in autonomous exploration systems. They assume that an expert has given a partition of the state space into regions; a strategy is independently computed for each region. These local solutions are pieced together to obtain a global solution. Subproblems correspond to local MDPs over regions associated with a certain parameter that provides an abstract summary of the interactions among regions. Next, two algorithms are presented for combining solutions to subproblems. The first one, called Hierarchical Policy Construction, solves an abstract MDP (each region becomes an abstract state). This algorithm finds for each region an optimal local strategy, that is, an optimal region to reach. The second algorithm, called Iterative Improvement Approach, iteratively approximates parameters of the local problems to converge to an optimal solution. In [40], the approach is analogous to the latter one but aims to show how domain characteristics are exploited to define the way regions communicate with each other. The authors represent the MDP as a directed graph which allows to precisely define the cost of going from one region to another. The approach in [41] is quite different. The authors present a particular structured representation of MDPs, using probabilistic STRIPS rules. This representation allows to quickly generate clusters of states which are used as states of an abstract MDP. The solution to this abstract MDP can be used as an approximate solution for the global MDP.Other authors aim to use macro-actions to efficiently solve large MDPs [42, 43]. Given a partition of the state space, a set of strategies are computed for each region. A strategy in a region is called a macro-action. Once the transition and the reward functions have been transformed to cope with macro-actions, an abstract MDP is solved using these macro-actions. The problem with this approach is that the quality of the solution is highly dependent on the quality of the set of strategies computed for each region. To ensure high quality, a large set of macro-actions have to be computed. As the transition and reward functions have to be computed for each macro-action, the time needed to find macro-actions can outweigh the speedup provided by macro-actions during strategy computing. The approach in [44] is quite similar, but based on Reinforcement Learning (RL).It is important to note that the above approaches differ essentially for the following reasons: the choice of the regions, the manner to combine the local solutions, and the quality of the final solution (optimal or only near optimal). For instance, in [35, 36] the authors use graph theory and choose the communicating classes as regions whereas in [39, 40, 45, 46] they use algorithmic geometry of field for determining the regions.There is also the remark that most of these state space decomposition methods are valid if (a) each subproblem is practically solvable, (b) the number of such subproblems is not too large, and (c) combining such subproblems is not difficult.On the other hand, most research in Reinforcement Learning (RL) is based on the theoretical discrete-time state and action formalism of the MDP. Unfortunately, as stated before, it suffers from the curse of dimensionality [47] where the explicit state and action space enumeration grow exponentially with the number of state variables and the number of agents, respectively. To deal with this issue, RL introduces Monte Carlo methods, stochastic approximation, trajectory sampling, temporal difference backups, and function approximation. However, even these methods have reached their limits. As a result, we discuss briefly in this survey broad categorizations of factored and hierarchical approaches which break up a large problem into smaller components and solve the parts [48–58]. The main idea of these approaches is to leverage the structure present in most real-world domains. For instance, the state of the environment is much better described in terms of the values of the states variables than by a monolithic number. This fact leads to powerful concepts of state aggregation and abstraction.In order to solve linear programs of very large sizes, decomposition principles [59] that divide a large linear program into many correlated linear programs of smaller sizes have been well studied, among which the Dantzig-Wolfe decomposition [60] may be the most well known. Further, in view of [61] the MDPs can be solved as linear programs using Dantzig-Wolfe decomposition. Thus, in this paper we present briefly the classical Dantzig-Wolfe decomposition procedure.The paper is organized as follows Section2 presents the problem formulation. Section 3 treats extensively some decomposition approaches introduced in [34–36, 38]. Section 4 presents the decomposition technique proposed by Dean and Lin [39]. Section 5 reviews some Reinforcement Learning methods proposed in the associated literature to alleviate the curse of dimensionality. Section 6 describes briefly the classic Dantzig-Wolfe decomposition procedure. We conclude and discuss open issues in Section 7.


## 1.1. Large Markov Chain Models

Markov chain models are still the most general class of analytic models widely used for performance and dependability analysis. This class of problems is robust in terms of its ability to represent a very broad class of models of interest. Unfortunately, the characteristics of many models (complex interactions between components, sophisticated scheduling strategies, synchronization among parallel tasks, etc.) preclude the possibility of closed-form solutions, in general. Numerical solution methods are the most general solution methods [1]. The most pervasive practical limitation to the use of numerical solution techniques is the size of the state space of realistic models. One natural way to deal with this problem is via state space reduction techniques, that is, a transformation of the model to one with fewer states. Another is to modify the model to one with a structure which enables efficient solution. The transformed model in general is an approximation of the original model. Several classes of such transformations are described below.There are several methods of state space reduction that are applicable to Markov chain models. One such method is combining “lumpable states” [2]. When lumping applies, it is exact, but only partial information is retrievable from the solution except in very special circumstances. Also, lumping is only valid for models that have certain very limited types of structure.Another method to treat large state spaces is aggregation/disaggregation [3]. This applies particularly well to cases in which the system model can be viewed as an interacting set of tightly coupled subsystems. The solution method is generally an iterative one in which submodels are solved and the obtained results are used to adjust the submodels repetitively until a convergence criterion is met. This is an efficient procedure if (a) the model is decomposable into tightly coupled submodels, (b) the state space of each submodel is practically solvable, and (c) the number of such submodels is not too large.There is an additional property of many models that is not capitalized on by any of the above methods. In many important cases, although the state space is extremely large, the stationary state probability distribution is highly skewed, that is, only a small subset of the states account for the vast majority of the probability mass. This is easily illustrated by considering the nature of several modeling application areas. This observation indicates that most of the probability mass is concentrated in a relatively small number of states in comparison to the total number of states in the model. During its lifetime, the system spends most of its time in this relatively small subset of states and only rarely reaches other states. The above observation is used to motivate truncation of the model state space, that is, choose to only represent a subset of the more “popular” states and ignore the remainder, deleting transitions from the represented states to the “discarded states”. Some form of heuristic is often used to decide which states to retain and which to discard. For dependability models a simple heuristic might be to discard all states in which the system has more than a certain number of failed components. A more sophisticated heuristic for determining which states to retain is described in [4]. The most persistent practical constraint to the use of the above state space truncation is that in certain models (health management, reliability, security problems) deleting some infrequently states may cause significant fatalities.There is also the issue of how much error is introduced by state space truncation. For some transient measures, error bounds are easily obtained by introducing trap states [5]. For example, in dependability analysis we may be interested in interval reliability. For this purpose one can introduce a trap state and change all transitions to “discarded states” into transitions to the trap state. Then the importance of the error is a direct function of the probability that the system is in the trap state at the end of the interval. For-steady state measures, the issue of error bounds can be more difficult. There are a number of approaches available for computing bounds or for proving that one model provides a bound compared with some other model. Among these we can quote the method of Courtois and Semal [6, 7], the methods based on sample-path analysis and stochastic ordering [8, 9], and the bias terms approach of Van Dijk [10].In [11], the authors explain with some examples where the model modifications only affect the less popular states and therefore have less effect on the performance measures. They also present some methods to compute bounds on performance measures.


## 1.2. Large Markov Decision Models

Over the past five decades there has been a lot of interest within planning community in using stochastic models, which provide a good framework to cope with uncertainties. Among them, Markov decision processes [12–22], either fully observable (MDP or FOMDP) or partially observable (POMDP), have been the subject of several recent studies [23–30]. The optimal strategy is computed with respect to all the uncertainties, but unfortunately, classical algorithms used to build these strategies are intractable with the twin drawbacks of large environments and lack of model information in most real-world systems [31–33]. Several recent studies aim to obtain a good approximation of the optimal strategy. Among them, aggregation and decomposition techniques have been the subject of a lot of attention. These techniques are really different flavors of the well-known framework Divide-and-Conquer: (1) partitioning the state space on regions, that is, transforming the initial MDP into small local MDPs, (2) independently solving the local MDPs, and (3) combining the local solutions to obtain an optimal (or near-optimal) strategy for the global MDP.In preparing this survey, we first attempt to summarize some general decomposition approaches introduced in [34–38]. These works have proposed some algorithms to compute optimal strategies as opposed to nearly all methods to treat large MDPs that compute only near optimal strategies. Moreover, they are suitable to several categories of MDPs (average, discounted and weighted MDPs) and can be applicable to many practical planning problems. These algorithms are based on the graph associated to the original MDP and by introducing some hierarchical structure of this graph.A lot of other recent works are concerned with autonomous exploration systems which require planning under uncertainty. In [39], the authors present a main decomposition technique to cope with large state spaces for practical problems encountered in autonomous exploration systems. They assume that an expert has given a partition of the state space into regions; a strategy is independently computed for each region. These local solutions are pieced together to obtain a global solution. Subproblems correspond to local MDPs over regions associated with a certain parameter that provides an abstract summary of the interactions among regions. Next, two algorithms are presented for combining solutions to subproblems. The first one, called Hierarchical Policy Construction, solves an abstract MDP (each region becomes an abstract state). This algorithm finds for each region an optimal local strategy, that is, an optimal region to reach. The second algorithm, called Iterative Improvement Approach, iteratively approximates parameters of the local problems to converge to an optimal solution. In [40], the approach is analogous to the latter one but aims to show how domain characteristics are exploited to define the way regions communicate with each other. The authors represent the MDP as a directed graph which allows to precisely define the cost of going from one region to another. The approach in [41] is quite different. The authors present a particular structured representation of MDPs, using probabilistic STRIPS rules. This representation allows to quickly generate clusters of states which are used as states of an abstract MDP. The solution to this abstract MDP can be used as an approximate solution for the global MDP.Other authors aim to use macro-actions to efficiently solve large MDPs [42, 43]. Given a partition of the state space, a set of strategies are computed for each region. A strategy in a region is called a macro-action. Once the transition and the reward functions have been transformed to cope with macro-actions, an abstract MDP is solved using these macro-actions. The problem with this approach is that the quality of the solution is highly dependent on the quality of the set of strategies computed for each region. To ensure high quality, a large set of macro-actions have to be computed. As the transition and reward functions have to be computed for each macro-action, the time needed to find macro-actions can outweigh the speedup provided by macro-actions during strategy computing. The approach in [44] is quite similar, but based on Reinforcement Learning (RL).It is important to note that the above approaches differ essentially for the following reasons: the choice of the regions, the manner to combine the local solutions, and the quality of the final solution (optimal or only near optimal). For instance, in [35, 36] the authors use graph theory and choose the communicating classes as regions whereas in [39, 40, 45, 46] they use algorithmic geometry of field for determining the regions.There is also the remark that most of these state space decomposition methods are valid if (a) each subproblem is practically solvable, (b) the number of such subproblems is not too large, and (c) combining such subproblems is not difficult.On the other hand, most research in Reinforcement Learning (RL) is based on the theoretical discrete-time state and action formalism of the MDP. Unfortunately, as stated before, it suffers from the curse of dimensionality [47] where the explicit state and action space enumeration grow exponentially with the number of state variables and the number of agents, respectively. To deal with this issue, RL introduces Monte Carlo methods, stochastic approximation, trajectory sampling, temporal difference backups, and function approximation. However, even these methods have reached their limits. As a result, we discuss briefly in this survey broad categorizations of factored and hierarchical approaches which break up a large problem into smaller components and solve the parts [48–58]. The main idea of these approaches is to leverage the structure present in most real-world domains. For instance, the state of the environment is much better described in terms of the values of the states variables than by a monolithic number. This fact leads to powerful concepts of state aggregation and abstraction.In order to solve linear programs of very large sizes, decomposition principles [59] that divide a large linear program into many correlated linear programs of smaller sizes have been well studied, among which the Dantzig-Wolfe decomposition [60] may be the most well known. Further, in view of [61] the MDPs can be solved as linear programs using Dantzig-Wolfe decomposition. Thus, in this paper we present briefly the classical Dantzig-Wolfe decomposition procedure.The paper is organized as follows Section2 presents the problem formulation. Section 3 treats extensively some decomposition approaches introduced in [34–36, 38]. Section 4 presents the decomposition technique proposed by Dean and Lin [39]. Section 5 reviews some Reinforcement Learning methods proposed in the associated literature to alleviate the curse of dimensionality. Section 6 describes briefly the classic Dantzig-Wolfe decomposition procedure. We conclude and discuss open issues in Section 7.


## 2. Markov Decision Processes

We consider a stochastic dynamic system which is observed at discrete-time pointst=1,2,…. At each time point t, the state space of the system is denoted by Xt, where Xt is a random variable whose values are in a state space E. At each time point t, if the system is in state i, an action a∈A(i)={1,2,…,m(i)} has to be chosen. In this case, two things happen: a reward r(i,a) is earned immediately, and the system moves to a new state j according to the transition probability piaj. Let At be the random variable which represents the action chosen at time t. We denote by Ht=(E×A)t-1×E the set of all histories up to time t and by Ψ={(q1,q2,…,q|A|):∑a=1|A|qa=1,qa≥0,1≤a≤|A|} the set of probability distributions over A=⋃i∈EA(i).A strategyπ is defined by a sequence π=(π1,π2,…), where πt: Ht→Ψ is a decision rule. A Markov strategy is one in which πt depends only on the current state at time t. A stationary strategy is a Markov strategy with identical decision rules. A deterministic (or pure) strategy is a stationary strategy whose single decision rule is nonrandomized. An ultimately deterministic strategy is a Markov strategy π=(π1,π2,…) such that there exist a deterministic strategy g and an integer t0 such that πt=g for all t≥t0. Let F, FM, FS, FD, and FUD be the sets of all strategies: Markov strategies, stationary strategies, deterministic strategies, and ultimately deterministic strategies, respectively.LetPπ(Xt=j,At=a∣X1=i) be the conditional probability that at time t the system is in state j and the action taken is a, given that the initial state is i and the decision maker uses a strategy π. Now, if Rt denotes the reward earned at time t, then, for any strategy π and initial state i, the expectation of Rt is given by Eπ(Rt,i)=∑j∈E∑a∈A(j)Pπ(Xt=j,At=a∣X1=i)r(j,a).The manner in which the resulting stream of expected rewards{Eπ(Rt,i):t=1,2,…} is aggregated defines the MDPs discussed in the sequel.In thediscounted reward MDP, the corresponding overall reward criterion is defined by Viα(π)=∑t=1∞αt-1Eπ(Rt,i),i∈E, where α∈[0,1) is a fixed discount rate. A strategy f* is called discounted optimal if, for all i∈E,Viα(f*)=maxπ∈FViα(π)=Vα(i). We will denote this MDP by Γ(α).In theaverage reward MDP, the overall reward criterion is defined by Φi(π)=limT→∞inf(1/T)∑t=1TEπ(Rt,i),i∈E. A strategy f* is called average optimal if for all i∈E,Φi(f*)=maxπ∈FΦi(π)=V(i). We will denote this MDP by Γ.In theweighted reward MDP, the overall reward criterion is defined by ωi(π)=λ(1-α)Viα(π)+(1-λ)Φi(π),i∈E, where λ∈[0,1] is a fixed weight parameter, and α is the discount rate in the MDP Γ(α). We denote this MDP by Γ(α,λ). A strategy f* is called optimal if for all i∈E,ωi(f*)=maxπ∈Fωi(π). Let ϵ>0; for any i∈E, some strategy f* is called ϵ-i-optimal if ωi(f*)≥supπ∈Fωi(π)-ϵ. A strategy f* is called ϵ-optimal if f* is ϵ-i-optimal for all i∈E.Remark 2.1.
(i) It is well known that each of the two first above problems possesses an optimal pure strategy, and there are a number of finite algorithms for its computation (e.g., see [18, 62–64]). (ii) In [65], the authors consider weighted MDPs and show that optimal strategies may not exist and propose an algorithm to determine an ϵ-optimal strategy.


## 3. Some Decomposition Techniques for MDPs

Classical algorithms for solving MDPs cannot cope with the size of the state spaces for typical problems encountered in practice [31–33]. In this section, we will summarize two decomposition techniques for tackling this complexity: the first is proposed by Ross and Varadarajan [38] and the second is introduced by Abbad and Boustique [36]. These techniques propose some algorithms to compute optimal strategies for several categories of MDPs (average, discounted, and weighted MDPs), as opposed to most solutions for large MDPs that compute only near-optimal strategies and are suitable to only some types of planning problems. Also, we will present some related works.


### 3.1. Ross-Varadarajan Decomposition

Considered are discrete-time MDPs with finite state and action spaces under the average reward optimality criterion [38]. We begin by introducing some notions of communication for MDPs.Definition 3.1.
A set of statesI communicate if, for any two states x,y∈I with x≠y, there exists a pure strategy g such that y is accessible from x under P(g).An MDP is said to be communicating if the state space E communicates.Definition 3.2.
A set of statesI strongly communicate if there exists a stationary strategy f such that I is a subset of a recurrent class associated with P(f).Definition 3.3.
A set of statesC are a communicating class (a strongly communicating class) if (i) C communicates (strongly communicates), and (ii) if x∈C and y∉C, then {x,y} does not communicate (strongly communicate).Ross and Varadarajan [38] show that there is a unique natural partition of state space E into strongly communicating classes (SCC): C1,C2,…,Cp and a set T of states that are transient under any stationary strategy. This decomposition is inspired from Bather's decomposition algorithm [37]. The sets Ei in the Bather decomposition are the strongly communicating classes Ci and the set of transient states T is the union of the sets T1,T2,…,Tm in [37]. This decomposition is also later formalized by Kallenberg in [66, Algorithm 7] which studied irreducibility, communicating, weakly communicating, and unichain classification problems for MDPs. A polynomial algorithm is given to compute this partition. Further, they propose an algorithm to solve large MDPs composed of the following steps: (i) solving some small MDPs restricted to each SCC, (ii) aggregating each SCC into one state and finding an optimal strategy for the corresponding aggregated MDP, and (iii) combining solutions found in the latter steps to obtain a solution to the entire MDP.Here, we will define correctly the latter two types of MDPs.The Restricted MDPs
For eachi=1,2,…,p, the restricted MDP to the class Ci is denoted by Γi, and is defined by: the state space Ci. For each x∈Ci, the action space is Fx={a∈A(x):pxay=0 for all y∉Ci}; the transition probabilities and the rewards are still analogous to those in the original problem; however, they are restricted to the state space Ci and the action spaces Fx,x∈Ci.The Aggregated MDP
The aggregated MDP is defined by:(i)
the state spaceE¯={1,…,p,p+1,…,p+t}, where t=|T|,(ii)
the action spacesA¯(i)=A(i) if i∈{p+1,…,p+t} and A¯(i)={θ}∪{(x,a):x∈Ci,a∉Fx} if i∈{1,…,p},(iii)
the transition probabilities(3.1)p¯iθi=1ifi∈{1,…,p},p¯i(x,a)j=∑y∈Cjpxayifi,j∈{1,…,p},p¯iaj=∑y∈Cjpiayifi∈{p+1,…,p+t},j∈{1,…,p},a∈A(i),p¯iaj=piajifi,j∈{p+1,…,p+t},(iv)
the rewardsr¯(i,a)=r(i,a) if i∈{p+1,…,p+t} and a∈A(i), r¯(i,θ)=γi if i∈{1,…,p}, r¯(i,(x,a))=r(x,a) if i∈{1,…,p}.
Remark 3.4.
For eachi=1,…,p, the restricted MDP Γi is communicating, and then it can be solved by the simpler linear programming in [51]. As a consequence, all the states in Γi have a similar optimal value γi.The most important step in the algorithm above consists in solving the aggregated MDP which is also an MDP, and then it can be solved by using the classical algorithms [34]. Ross and Varadarajan [38] did not give any new method for solving the aggregated MDP. As a result, the aim of [34] is to provide some algorithms which exploit the particular structure of the aggregated MDP and improve the classical ones. The authors consider deterministic MDPs and aggregated MDPs without cycles. In the sequel of this subsection, we will present briefly these algorithms.


#### 3.1.1. Deterministic MDPs

The work in [34] considers firstly deterministic MDPs and shows that the singletons {i},i∈{1,2,…,p}, are the only strongly communicating classes for the aggregated MDP. This result permits to prove the correctness of the following simple algorithm which constructs g¯: an optimal strategy in the aggregated MDP.Algorithm 3.5.
Step 1.
One hasE¯:={1,…,p,p+1,…,p+t}, v(i):=γi for i∈{1,…,p} and v(i):=(mink∈{1,…,p}γk)-1 for i∈{p+1,…,p+t}.Step 2.
Computei* such that γi*=(maxj∈{1,…,p}γj) and determine W={i∈{1,…,p}:γi=γi*}. For j∈W, set g¯(j):=θ and v(j)=γi*.Step 3.
Whilei∈E¯-W, a¯i∈A¯(i), j∈W: p¯ia¯ij>0 do g¯(i)=a¯i, W:=W∪{i}, v(i):=γi*.Step 4.
(i) IfE¯=W, stop: g¯ is an aggregated optimal strategy. (ii) If E¯≠W, find i′such that v(i′)=maxk∈E¯-Wv(k) and determine W={i∈{1,…,p}:v(i)=v(i′)}. For j∈W, set g¯(j):=θ, v(j):=v(i′), and E¯:=E¯-W.


#### 3.1.2. The Aggregated MDP and Cycles

LetG¯=(V¯,S¯) be the graph associated with the aggregated MDP; that is, the state space represents the set of nodes and S¯:={(i,j)∈E¯×E¯:p¯ia¯j>0 for some a¯∈A¯(i)} is the set of arcs. We say that an aggregated MDP has no cycle if the associated graph has no cycle containing two or more nodes. The next algorithm extends Algorithm 3.5 in the case where the original MDP may be not deterministic and its aggregated MDP has no cycle [34].Algorithm 3.6.
Step 1.
One hasE¯:={1,…,p,p+1,…,p+t};v(i):=γi for i∈{1,…,p};v(i):=(mink∈{1,…,p}γk)-1 for i∈{p+1,…,p+t}.Step 2.
Computeγ*=maxk∈{1,…,p}γk and determine W={i∈{1,…,p}:γi=γ*}. For j∈W, set g¯(j):=θ.Step 3.
While there existi∈E¯-W, a¯i∈A¯(i) such that ∑j∈Wp¯ia¯ij=1, do: g¯(i)=a¯i, W:=W∪{i}, v(i):=γ*.Step 4.
While there existsi∈{1,…,p}-W such that p¯ia¯j=0 for all a¯∈A¯(i)-θ, j≠i, do: g¯(i):=θ, W:=W∪{i}.Step 5.
IfE¯≠W, while there exists i∈E¯-W such that, for all a¯∈A¯(i), ∑j∈Wp¯ia¯j=1, do: w(i):=maxa¯∈A¯(i)∑j∈Wp¯ia¯jv(j); if v(i)>w(i), set g¯(i):=θ; if v(i)≤w(i) set g¯(i):=argmaxa¯∈A¯(i)∑j∈Wp¯ia¯jv(j) and v(i):=w(i); W:=W∪{i}. If E¯=W, stop; g¯ is an aggregated optimal strategy.Remark 3.7.
(i) The previous algorithm is applicable if the decomposition leads toT=∅, because in this case the aggregated MDP has no cycle. (ii) In [1], the authors have also considered an arbitrary MDP without any condition and they have presented two algorithms for the computation of an aggregated optimal strategy. The latter comes up with some significant simplifications on the classical policy improvement algorithm and linear programming algorithm. In the construction they have exploited the fact that the recurrent classes in the aggregated MDP are singletons.


### 3.2. Abbad-Boustique Decomposition

Abbad and Boustique [36] propose an algorithm to compute an average optimal strategy which is based on the graph associated to the original MDP introducing some hierarchical structure of this graph. The main contribution of their approach consists in constructing by induction the levels of the graph G and solving the restricted MDPs corresponding to each level. The local solutions of the latter MDPs provide immediately an optimal strategy in the entire MDP. This state space decomposition into levels is inspired by the work in[67].LetG=(V,S) be a directed graph associated to the original MDP. A communicating class for the MDP corresponds to a connected component in the graph G. Thus, there exists a unique partition of the state space E into communicating classes C1, C2,…,Cq, which can be determined via standard depth-first algorithms [68]. The level L0 is formed by all classes Ci such that Ci is closed. The nth level Ln is formed by all classes Ci such that the end of any arc emanating from Ci is in some level Ln-1,Ln-2, …,L0.Let (Clk), k∈{1,2,…,K(l)}, be the classes corresponding to the nodes in level l. The restricted MDPs corresponding to each level Ln, n=0,1,2,…,L, are constructed, by induction, as follows.


#### 3.2.1. Construction of the Restricted MDPs in LevelL0

For eachk=1,2,…,K(0), we denote by Γ0k the restricted MDP corresponding to the class C0k, that is, the restricted MDP in which the state space is S0k=C0k. Note that any restricted MDP, Γ0k is well defined since any class C0k is closed and can be solved easily by a finite algorithm (see [69]).


#### 3.2.2. Construction of the Restricted MDPs in LevelLn, n≥1

LetEn=∪{Cmk,m=0,…,n-1;k=1,…,K(m)}. Let Tmk(i) be the optimal value in state i∈En, computed in the previous MDP: Γmk(m<n). For each k=1,2,…,K(n), we denote by Γnk the MDP defined by the following.(i)
State space. Snk=Cnk∪{j∈En:piaj>0 for some i∈Cnk,a∈A(i)}.(ii)
Action spaces. For each i∈Snk, the associated action space is Ank(i)=A(i) if i∈Cnk and Ank(i)={θ}ifi∉Cnk.(iii)
Transition probabilities. For each i,j∈Snk, Pnk(j∣i,a)=piaj if i∈Cnk, a∈A(i) and Pnk(j∣i,a)=1 if i=j, i∉Cnk.(iv)
Rewards. Let i∈Snk; if  i∈Cnk, then rnk(i,a):=r(i,a).Ifi∉Cnk, then there exist m∈{0,1,…,n-1},thereexisth∈{1,2,…,K(m)}:i∈Cmh, andrnk(i,θ):=Tmh(i).The basic result of Abbad-Boustique approach shows that the optimal value for a fixed state in any restricted MDP is equal to the optimal value in the original MDP. Consequently, optimal actions in the restricted MDPs are still optimal in the original MDP. Such approach is advantageous because it allows that an optimal action and the optimal value for a fixed state can be computed only through some restricted MDPs before solving the entire MDP; however, there is still considerable overhead in determining the communicating classes.The work in [35] is a main related work on Abbad-Boustique decomposition. The authors have considered the discounted and weighted optimality criterion with finite state and action spaces. With these criterions the Ross-Varadarajan decomposition is not available. That is why the authors have used the approach introduced in [36], and they have constructed the levels and the restricted MDPs in a similar way as above. In the discounted optimality criterion, they also have showed that optimal actions in the restricted MDP are still optimal in the original MDP, and they have proposed an algorithm to find an optimal strategy. Under the weighted optimality criterion, they have first proposed an algorithm which constructs an ϵ-optimal strategy corresponding to each restricted MDP; whereas, in [65], for each state i∈E, an ϵ-i- optimal strategy is constructed by solving the entire MDP. Finally, by coalescing the last restricted ϵ-optimal strategies they have presented an algorithm which determines an ϵ-optimal strategy in the original MDP.Remark 3.8.
(i) The decomposition approaches presented in [34, 37, 57, 66] are merely motivating if (a) the cardinalities of the Strongly Communicating Classes (SCCs): C1,C2,…,Cp and a set T are small compared to the cardinality of the state space E and (b) the number p of the SCCs is not too large. However, they are most suitable to solve constrained MDPs. (ii) the approaches proposed in [35, 36] alleviate the last inconvenient; however, there is still considerable overhead in determining the communicating classes.


## 3.1. Ross-Varadarajan Decomposition

Considered are discrete-time MDPs with finite state and action spaces under the average reward optimality criterion [38]. We begin by introducing some notions of communication for MDPs.Definition 3.1.
A set of statesI communicate if, for any two states x,y∈I with x≠y, there exists a pure strategy g such that y is accessible from x under P(g).An MDP is said to be communicating if the state space E communicates.Definition 3.2.
A set of statesI strongly communicate if there exists a stationary strategy f such that I is a subset of a recurrent class associated with P(f).Definition 3.3.
A set of statesC are a communicating class (a strongly communicating class) if (i) C communicates (strongly communicates), and (ii) if x∈C and y∉C, then {x,y} does not communicate (strongly communicate).Ross and Varadarajan [38] show that there is a unique natural partition of state space E into strongly communicating classes (SCC): C1,C2,…,Cp and a set T of states that are transient under any stationary strategy. This decomposition is inspired from Bather's decomposition algorithm [37]. The sets Ei in the Bather decomposition are the strongly communicating classes Ci and the set of transient states T is the union of the sets T1,T2,…,Tm in [37]. This decomposition is also later formalized by Kallenberg in [66, Algorithm 7] which studied irreducibility, communicating, weakly communicating, and unichain classification problems for MDPs. A polynomial algorithm is given to compute this partition. Further, they propose an algorithm to solve large MDPs composed of the following steps: (i) solving some small MDPs restricted to each SCC, (ii) aggregating each SCC into one state and finding an optimal strategy for the corresponding aggregated MDP, and (iii) combining solutions found in the latter steps to obtain a solution to the entire MDP.Here, we will define correctly the latter two types of MDPs.The Restricted MDPs
For eachi=1,2,…,p, the restricted MDP to the class Ci is denoted by Γi, and is defined by: the state space Ci. For each x∈Ci, the action space is Fx={a∈A(x):pxay=0 for all y∉Ci}; the transition probabilities and the rewards are still analogous to those in the original problem; however, they are restricted to the state space Ci and the action spaces Fx,x∈Ci.The Aggregated MDP
The aggregated MDP is defined by:(i)
the state spaceE¯={1,…,p,p+1,…,p+t}, where t=|T|,(ii)
the action spacesA¯(i)=A(i) if i∈{p+1,…,p+t} and A¯(i)={θ}∪{(x,a):x∈Ci,a∉Fx} if i∈{1,…,p},(iii)
the transition probabilities(3.1)p¯iθi=1ifi∈{1,…,p},p¯i(x,a)j=∑y∈Cjpxayifi,j∈{1,…,p},p¯iaj=∑y∈Cjpiayifi∈{p+1,…,p+t},j∈{1,…,p},a∈A(i),p¯iaj=piajifi,j∈{p+1,…,p+t},(iv)
the rewardsr¯(i,a)=r(i,a) if i∈{p+1,…,p+t} and a∈A(i), r¯(i,θ)=γi if i∈{1,…,p}, r¯(i,(x,a))=r(x,a) if i∈{1,…,p}.
Remark 3.4.
For eachi=1,…,p, the restricted MDP Γi is communicating, and then it can be solved by the simpler linear programming in [51]. As a consequence, all the states in Γi have a similar optimal value γi.The most important step in the algorithm above consists in solving the aggregated MDP which is also an MDP, and then it can be solved by using the classical algorithms [34]. Ross and Varadarajan [38] did not give any new method for solving the aggregated MDP. As a result, the aim of [34] is to provide some algorithms which exploit the particular structure of the aggregated MDP and improve the classical ones. The authors consider deterministic MDPs and aggregated MDPs without cycles. In the sequel of this subsection, we will present briefly these algorithms.


### 3.1.1. Deterministic MDPs

The work in [34] considers firstly deterministic MDPs and shows that the singletons {i},i∈{1,2,…,p}, are the only strongly communicating classes for the aggregated MDP. This result permits to prove the correctness of the following simple algorithm which constructs g¯: an optimal strategy in the aggregated MDP.Algorithm 3.5.
Step 1.
One hasE¯:={1,…,p,p+1,…,p+t}, v(i):=γi for i∈{1,…,p} and v(i):=(mink∈{1,…,p}γk)-1 for i∈{p+1,…,p+t}.Step 2.
Computei* such that γi*=(maxj∈{1,…,p}γj) and determine W={i∈{1,…,p}:γi=γi*}. For j∈W, set g¯(j):=θ and v(j)=γi*.Step 3.
Whilei∈E¯-W, a¯i∈A¯(i), j∈W: p¯ia¯ij>0 do g¯(i)=a¯i, W:=W∪{i}, v(i):=γi*.Step 4.
(i) IfE¯=W, stop: g¯ is an aggregated optimal strategy. (ii) If E¯≠W, find i′such that v(i′)=maxk∈E¯-Wv(k) and determine W={i∈{1,…,p}:v(i)=v(i′)}. For j∈W, set g¯(j):=θ, v(j):=v(i′), and E¯:=E¯-W.


### 3.1.2. The Aggregated MDP and Cycles

LetG¯=(V¯,S¯) be the graph associated with the aggregated MDP; that is, the state space represents the set of nodes and S¯:={(i,j)∈E¯×E¯:p¯ia¯j>0 for some a¯∈A¯(i)} is the set of arcs. We say that an aggregated MDP has no cycle if the associated graph has no cycle containing two or more nodes. The next algorithm extends Algorithm 3.5 in the case where the original MDP may be not deterministic and its aggregated MDP has no cycle [34].Algorithm 3.6.
Step 1.
One hasE¯:={1,…,p,p+1,…,p+t};v(i):=γi for i∈{1,…,p};v(i):=(mink∈{1,…,p}γk)-1 for i∈{p+1,…,p+t}.Step 2.
Computeγ*=maxk∈{1,…,p}γk and determine W={i∈{1,…,p}:γi=γ*}. For j∈W, set g¯(j):=θ.Step 3.
While there existi∈E¯-W, a¯i∈A¯(i) such that ∑j∈Wp¯ia¯ij=1, do: g¯(i)=a¯i, W:=W∪{i}, v(i):=γ*.Step 4.
While there existsi∈{1,…,p}-W such that p¯ia¯j=0 for all a¯∈A¯(i)-θ, j≠i, do: g¯(i):=θ, W:=W∪{i}.Step 5.
IfE¯≠W, while there exists i∈E¯-W such that, for all a¯∈A¯(i), ∑j∈Wp¯ia¯j=1, do: w(i):=maxa¯∈A¯(i)∑j∈Wp¯ia¯jv(j); if v(i)>w(i), set g¯(i):=θ; if v(i)≤w(i) set g¯(i):=argmaxa¯∈A¯(i)∑j∈Wp¯ia¯jv(j) and v(i):=w(i); W:=W∪{i}. If E¯=W, stop; g¯ is an aggregated optimal strategy.Remark 3.7.
(i) The previous algorithm is applicable if the decomposition leads toT=∅, because in this case the aggregated MDP has no cycle. (ii) In [1], the authors have also considered an arbitrary MDP without any condition and they have presented two algorithms for the computation of an aggregated optimal strategy. The latter comes up with some significant simplifications on the classical policy improvement algorithm and linear programming algorithm. In the construction they have exploited the fact that the recurrent classes in the aggregated MDP are singletons.


## 3.1.1. Deterministic MDPs

The work in [34] considers firstly deterministic MDPs and shows that the singletons {i},i∈{1,2,…,p}, are the only strongly communicating classes for the aggregated MDP. This result permits to prove the correctness of the following simple algorithm which constructs g¯: an optimal strategy in the aggregated MDP.Algorithm 3.5.
Step 1.
One hasE¯:={1,…,p,p+1,…,p+t}, v(i):=γi for i∈{1,…,p} and v(i):=(mink∈{1,…,p}γk)-1 for i∈{p+1,…,p+t}.Step 2.
Computei* such that γi*=(maxj∈{1,…,p}γj) and determine W={i∈{1,…,p}:γi=γi*}. For j∈W, set g¯(j):=θ and v(j)=γi*.Step 3.
Whilei∈E¯-W, a¯i∈A¯(i), j∈W: p¯ia¯ij>0 do g¯(i)=a¯i, W:=W∪{i}, v(i):=γi*.Step 4.
(i) IfE¯=W, stop: g¯ is an aggregated optimal strategy. (ii) If E¯≠W, find i′such that v(i′)=maxk∈E¯-Wv(k) and determine W={i∈{1,…,p}:v(i)=v(i′)}. For j∈W, set g¯(j):=θ, v(j):=v(i′), and E¯:=E¯-W.


## 3.1.2. The Aggregated MDP and Cycles

LetG¯=(V¯,S¯) be the graph associated with the aggregated MDP; that is, the state space represents the set of nodes and S¯:={(i,j)∈E¯×E¯:p¯ia¯j>0 for some a¯∈A¯(i)} is the set of arcs. We say that an aggregated MDP has no cycle if the associated graph has no cycle containing two or more nodes. The next algorithm extends Algorithm 3.5 in the case where the original MDP may be not deterministic and its aggregated MDP has no cycle [34].Algorithm 3.6.
Step 1.
One hasE¯:={1,…,p,p+1,…,p+t};v(i):=γi for i∈{1,…,p};v(i):=(mink∈{1,…,p}γk)-1 for i∈{p+1,…,p+t}.Step 2.
Computeγ*=maxk∈{1,…,p}γk and determine W={i∈{1,…,p}:γi=γ*}. For j∈W, set g¯(j):=θ.Step 3.
While there existi∈E¯-W, a¯i∈A¯(i) such that ∑j∈Wp¯ia¯ij=1, do: g¯(i)=a¯i, W:=W∪{i}, v(i):=γ*.Step 4.
While there existsi∈{1,…,p}-W such that p¯ia¯j=0 for all a¯∈A¯(i)-θ, j≠i, do: g¯(i):=θ, W:=W∪{i}.Step 5.
IfE¯≠W, while there exists i∈E¯-W such that, for all a¯∈A¯(i), ∑j∈Wp¯ia¯j=1, do: w(i):=maxa¯∈A¯(i)∑j∈Wp¯ia¯jv(j); if v(i)>w(i), set g¯(i):=θ; if v(i)≤w(i) set g¯(i):=argmaxa¯∈A¯(i)∑j∈Wp¯ia¯jv(j) and v(i):=w(i); W:=W∪{i}. If E¯=W, stop; g¯ is an aggregated optimal strategy.Remark 3.7.
(i) The previous algorithm is applicable if the decomposition leads toT=∅, because in this case the aggregated MDP has no cycle. (ii) In [1], the authors have also considered an arbitrary MDP without any condition and they have presented two algorithms for the computation of an aggregated optimal strategy. The latter comes up with some significant simplifications on the classical policy improvement algorithm and linear programming algorithm. In the construction they have exploited the fact that the recurrent classes in the aggregated MDP are singletons.


## 3.2. Abbad-Boustique Decomposition

Abbad and Boustique [36] propose an algorithm to compute an average optimal strategy which is based on the graph associated to the original MDP introducing some hierarchical structure of this graph. The main contribution of their approach consists in constructing by induction the levels of the graph G and solving the restricted MDPs corresponding to each level. The local solutions of the latter MDPs provide immediately an optimal strategy in the entire MDP. This state space decomposition into levels is inspired by the work in[67].LetG=(V,S) be a directed graph associated to the original MDP. A communicating class for the MDP corresponds to a connected component in the graph G. Thus, there exists a unique partition of the state space E into communicating classes C1, C2,…,Cq, which can be determined via standard depth-first algorithms [68]. The level L0 is formed by all classes Ci such that Ci is closed. The nth level Ln is formed by all classes Ci such that the end of any arc emanating from Ci is in some level Ln-1,Ln-2, …,L0.Let (Clk), k∈{1,2,…,K(l)}, be the classes corresponding to the nodes in level l. The restricted MDPs corresponding to each level Ln, n=0,1,2,…,L, are constructed, by induction, as follows.


### 3.2.1. Construction of the Restricted MDPs in LevelL0

For eachk=1,2,…,K(0), we denote by Γ0k the restricted MDP corresponding to the class C0k, that is, the restricted MDP in which the state space is S0k=C0k. Note that any restricted MDP, Γ0k is well defined since any class C0k is closed and can be solved easily by a finite algorithm (see [69]).


### 3.2.2. Construction of the Restricted MDPs in LevelLn, n≥1

LetEn=∪{Cmk,m=0,…,n-1;k=1,…,K(m)}. Let Tmk(i) be the optimal value in state i∈En, computed in the previous MDP: Γmk(m<n). For each k=1,2,…,K(n), we denote by Γnk the MDP defined by the following.(i)
State space. Snk=Cnk∪{j∈En:piaj>0 for some i∈Cnk,a∈A(i)}.(ii)
Action spaces. For each i∈Snk, the associated action space is Ank(i)=A(i) if i∈Cnk and Ank(i)={θ}ifi∉Cnk.(iii)
Transition probabilities. For each i,j∈Snk, Pnk(j∣i,a)=piaj if i∈Cnk, a∈A(i) and Pnk(j∣i,a)=1 if i=j, i∉Cnk.(iv)
Rewards. Let i∈Snk; if  i∈Cnk, then rnk(i,a):=r(i,a).Ifi∉Cnk, then there exist m∈{0,1,…,n-1},thereexisth∈{1,2,…,K(m)}:i∈Cmh, andrnk(i,θ):=Tmh(i).The basic result of Abbad-Boustique approach shows that the optimal value for a fixed state in any restricted MDP is equal to the optimal value in the original MDP. Consequently, optimal actions in the restricted MDPs are still optimal in the original MDP. Such approach is advantageous because it allows that an optimal action and the optimal value for a fixed state can be computed only through some restricted MDPs before solving the entire MDP; however, there is still considerable overhead in determining the communicating classes.The work in [35] is a main related work on Abbad-Boustique decomposition. The authors have considered the discounted and weighted optimality criterion with finite state and action spaces. With these criterions the Ross-Varadarajan decomposition is not available. That is why the authors have used the approach introduced in [36], and they have constructed the levels and the restricted MDPs in a similar way as above. In the discounted optimality criterion, they also have showed that optimal actions in the restricted MDP are still optimal in the original MDP, and they have proposed an algorithm to find an optimal strategy. Under the weighted optimality criterion, they have first proposed an algorithm which constructs an ϵ-optimal strategy corresponding to each restricted MDP; whereas, in [65], for each state i∈E, an ϵ-i- optimal strategy is constructed by solving the entire MDP. Finally, by coalescing the last restricted ϵ-optimal strategies they have presented an algorithm which determines an ϵ-optimal strategy in the original MDP.Remark 3.8.
(i) The decomposition approaches presented in [34, 37, 57, 66] are merely motivating if (a) the cardinalities of the Strongly Communicating Classes (SCCs): C1,C2,…,Cp and a set T are small compared to the cardinality of the state space E and (b) the number p of the SCCs is not too large. However, they are most suitable to solve constrained MDPs. (ii) the approaches proposed in [35, 36] alleviate the last inconvenient; however, there is still considerable overhead in determining the communicating classes.


## 3.2.1. Construction of the Restricted MDPs in LevelL0

For eachk=1,2,…,K(0), we denote by Γ0k the restricted MDP corresponding to the class C0k, that is, the restricted MDP in which the state space is S0k=C0k. Note that any restricted MDP, Γ0k is well defined since any class C0k is closed and can be solved easily by a finite algorithm (see [69]).


## 3.2.2. Construction of the Restricted MDPs in LevelLn, n≥1

LetEn=∪{Cmk,m=0,…,n-1;k=1,…,K(m)}. Let Tmk(i) be the optimal value in state i∈En, computed in the previous MDP: Γmk(m<n). For each k=1,2,…,K(n), we denote by Γnk the MDP defined by the following.(i)
State space. Snk=Cnk∪{j∈En:piaj>0 for some i∈Cnk,a∈A(i)}.(ii)
Action spaces. For each i∈Snk, the associated action space is Ank(i)=A(i) if i∈Cnk and Ank(i)={θ}ifi∉Cnk.(iii)
Transition probabilities. For each i,j∈Snk, Pnk(j∣i,a)=piaj if i∈Cnk, a∈A(i) and Pnk(j∣i,a)=1 if i=j, i∉Cnk.(iv)
Rewards. Let i∈Snk; if  i∈Cnk, then rnk(i,a):=r(i,a).Ifi∉Cnk, then there exist m∈{0,1,…,n-1},thereexisth∈{1,2,…,K(m)}:i∈Cmh, andrnk(i,θ):=Tmh(i).The basic result of Abbad-Boustique approach shows that the optimal value for a fixed state in any restricted MDP is equal to the optimal value in the original MDP. Consequently, optimal actions in the restricted MDPs are still optimal in the original MDP. Such approach is advantageous because it allows that an optimal action and the optimal value for a fixed state can be computed only through some restricted MDPs before solving the entire MDP; however, there is still considerable overhead in determining the communicating classes.The work in [35] is a main related work on Abbad-Boustique decomposition. The authors have considered the discounted and weighted optimality criterion with finite state and action spaces. With these criterions the Ross-Varadarajan decomposition is not available. That is why the authors have used the approach introduced in [36], and they have constructed the levels and the restricted MDPs in a similar way as above. In the discounted optimality criterion, they also have showed that optimal actions in the restricted MDP are still optimal in the original MDP, and they have proposed an algorithm to find an optimal strategy. Under the weighted optimality criterion, they have first proposed an algorithm which constructs an ϵ-optimal strategy corresponding to each restricted MDP; whereas, in [65], for each state i∈E, an ϵ-i- optimal strategy is constructed by solving the entire MDP. Finally, by coalescing the last restricted ϵ-optimal strategies they have presented an algorithm which determines an ϵ-optimal strategy in the original MDP.Remark 3.8.
(i) The decomposition approaches presented in [34, 37, 57, 66] are merely motivating if (a) the cardinalities of the Strongly Communicating Classes (SCCs): C1,C2,…,Cp and a set T are small compared to the cardinality of the state space E and (b) the number p of the SCCs is not too large. However, they are most suitable to solve constrained MDPs. (ii) the approaches proposed in [35, 36] alleviate the last inconvenient; however, there is still considerable overhead in determining the communicating classes.


## 4. Dean-Lin Decomposition

the study by Dean and Lin in [39] is one of the first works that introduces decomposition techniques for planning in stochastic domains. Their framework as stated before is also a special case of Divide-and-Conquer: given a partition of the state space into regions, (i) reformulate the problem in terms of smaller MDPs over the subspaces of the individual regions, (ii) solve each of these subproblems, and then (iii) combine the solutions to obtain a solution to the original problem. In this section, we discuss briefly Dean-Lin approach and some related works.LetP be any partition of E,P={R1,…,Rm} such that E=∪i=1mRi and Ri∩Rj=∅, for all i≠j. We refer to a region R∈P as an aggregate (or a macro) state. The periphery of an aggregate state R (denoted Periphery(R)) is the set of states not in R but reachable in a single transition from some state in R, that is, {j|j∉Randthere existi∈R,a∈A(i),piaj>0}.To model interactions among regions, a set of parameters are introduced. LetU=∪R∈PPeriphery(R), and λi for each i∈U denote a real-valued parameter. Let λ¯∈ℜ|U| denote a vector of all such λi parameters, and let λ¯|R denote a subvector of λ¯ composed of λi, where i is in Periphery(R). Parameter λi serves as a measure of the expected cost of starting from a periphery state, andλ¯|R provides an abstract summary of how the other regions affect R. Given a particular λ¯, the original MDP is decomposed into smaller MDPs. For a region R and the subvector λ¯|R, a local MDP Mλ¯|R is defined by the following:(i)
state spaceR ∪ Periphery(R),(ii)
state transition matrix (qij): qij=pij for i∈R, and qii=1 for i∈ Periphery(R),(iii)
cost matrix (kij): kij=cij for i,j∈R;kij=λj+cij for i∈R and j∈ Periphery(R);kii=0 for i∈ Periphery(R).Letπ* denote an optimal strategy for the original MDP. Ifλi=Viα(π*), the authors show that the resulting local strategies for the local MDPs define an optimal strategy on the entire state space. They further propose two methods for either guessing or successively approximating Viα(π*) for all i∈U: a hierarchical construction approach and iterative improvement approach.The former constructs an abstract MDP by considering individual regions as abstract states and their local strategies as abstract actions. The solution to this abstract MDP finds for each region an optimal region to reach, thus yielding a solution on the original MDP. Unfortunately, this approach does not guarantee to produce an optimal strategy; however, it has an intuitive interpretation that makes it particularly suitable for robot navigation domains.The second method iteratively approximatesViα(π*) to converge to an optimal solution. On each iteration, for each region R a specific estimate of the parameter values of region R is considered and the resulting MDP to obtain a local strategy is solved. By examining the resulting local strategies we get information to engender a new estimate of the parameter values that is guaranteed to improve the global solution. This information about local strategies also tells us when the current solution is optimal or within some specified tolerance and it is therefore appropriate to terminate the iterative procedure. The iterative approach computes several strategies for each region, which is not good news, but it provides an optimal strategy. Also, it is important to note that this approach is based on a reduction to the methods of Kushner and Chen [61] that demonstrates how to solve MDPs as linear programs using Dantzig-Wolfe decomposition [60]. For more details, we refer the reader to the longer version of the paper in [70].Closely related to hierarchical construction approach, two methods have been proposed in [42, 43]. They also solve an abstract MDP composed of one abstract state per region, but many strategies, called macro-actions, are computed in each region. In [43], to compensate this weakness only a small set of strategies are calculated per region, without loss of optimality.In [40], the approach aims also to solve weakly coupled MDPs, but it is quite different to Dean-Lin approach for the following reasons: (i) only one strategy is computed in each region which reduces time consuming on each iteration and (ii) the MDP is represented as a directed graph, and so a simple heuristic valuated graph is used to estimate periphery state values. This approach constructs strategies that are only near optimal; however, they are computed quickly.The related work on abstraction and decomposition is extensive. In the area planning and search assuming deterministic action models, there is the work on macro-operators [71] and hierarchies of state space operators [72, 73]. Closely related is the work on decomposing discrete-event systems modeled as (deterministic) finite state machines [74]. In the area of reinforcement learning, there is work on deterministic action models and continuous state spaces [75] and stochastic models and discrete state spaces [76]. Finally, the approach described in [46] represents a special case of the Dean-Lin framework, in which the partition consists of singleton sets for all of the states in the envelope and a set for all the states in the complement of the envelope.


## 5. Hierarchical Reinforcement Learning

Reinforcement Learning (RL) is a machine learning paradigm in which an agent learns a behavioral policy through direct interaction with an unknown, stochastic environment [77]. Most research in RL is based on the theoretical discrete-time state and action formalism of the MDP. Unfortunately, it suffers from the curse of dimensionality [47], where the explicit state and action space enumeration grow exponentially with the number of state variables and the number of agents, respectively. So, RL has introduced Monte Carlo methods, stochastic approximation, trajectory sampling, temporal difference backups, and function approximation. However, even these methods have reached their limits. As a result, we discuss briefly in this section broad categorizations of factored, and hierarchical approaches which break up a large problem into smaller components and solving the parts.


### 5.1. Factored Approaches

When the state space of the MDP can be specified as a cross-product of sets of state variablesEi(E=E0×E1×⋯×En), it is called a factored MDP (FMDP). The concepts of state abstraction and aggregation are strongly related to the idea of a factored state space. A factored formulation also allows for system dynamics to be specified using a more natural and intuitive representation instead of an S×S probability matrix per action. Representations that can describe such structure are 2-slice Dynamic Bayesian Networks (DBNs) [78] and probabilistic STRIPS operators, the former being more popular in the literature.In [48], the authors exploit such a factored state space directly, and reveal reduction in the computation and memory required to compute the optimal solution. The assumption is that the MDP is specified by a set of DBNs, one for each action, although the claim made is that it is amenable to a probabilistic STRIPS specification too. In addition to using the network structure to elicit variable independence, they use decision-tree representations of the conditional probability distributions (CPDs) to further exploit propositional independence. Next, they construct the structured policy iteration (SPI) algorithm which aggregates states for two distinct reasons: either if the states are assigned the same action by the current strategy, or if states have the same current estimated value. With the aggregation in place, the learning algorithm (based on modified policy iteration) only computes at the coarser level of these state partitions instead of that of the individual states. The algorithm itself is split into two phases, structured successive approximation and structured policy improvement, mirroring the two phases of classical policy iteration. It is important to note that SPI will see fewer advantages if the optimal strategy cannot be compactly represented by a tree structure, and for the reason that there is still big overhead in finding the state partitions.In [53], Algebraic Decision Diagrams (ADDs) replace the decision-tree learning of SPI for the value function and strategy representation. The paper deals with a very large MDP (≈63 million states) and shows that the learned ADD value function representation is considerably more compact than the corresponding learned decision tree in most cases. However, a big disadvantage of using ADDs is that the state variables must be boolean, which makes the modified state space larger than the original.In order to solve large weakly coupled FMDPs, the state space of the original MDP is divided into regions that comprise sub-MDPs which run concurrently (the original MDP is a cross-product of the sub-MDPs) [79]. It is assumed that states variables are only associated with a particular task and the numbers of resources that can be allocated to the individual tasks are constrained; these global constraints are what cause the weak coupling between the sub-MDPs. Their approach contains two phases: an offline phase that computes the optimal solutions (value functions) for the individual sub-MDPs and an online phase that uses these local value functions to heuristically guide the search for global resource allocation to the subtasks.One class of methods for solving weakly coupled FMDPs involves the use of linear value function approximation. In [52], the authors present two solution algorithms (based on approximate linear and dynamic programming) that approximate the value functions using a linear combination of basis functions, each basis function only depending on a small subset of the state variables. In [80], a general framework is proposed that can select a suitable basis set and modify it based on the solution quality. Further, they use piecewise linear combination of the subtask value functions to approximate the optimal value function for the original MDP. The above approaches to solving FMDPs are classified under decision-theoretic planning in that they need a perfect model (transition and reward) of the FMDP. The work in [50] proposes the SDYNA framework that can learn in large FMDPs without initial knowledge of their structure. SDYNA incrementally builds structured representations using incremental decision-tree induction algorithms that learn from the observations made by the agent.


### 5.2. Hierarchical Approaches

To deal with large-scale FMDPs, RL approaches aim to leverage the structure of the state space. However, they do not impart enough structure to the strategy space itself. Hierarchical reinforcement learning (HRL) is a broad and very active subfield of RL that imposes hierarchical structure onto the state, action, and strategy spaces. To alleviate the curse of dimensionality, HRL applies principled methods of temporal abstraction to the problem; decision-making should not be required at every step but instead temporally extended activities or macro-operators or subtasks can be selected to achieve subgoals.The work in [49] proposes a new approach which relies on a programmer to design a hierarchy of abstract machines that limit the possible strategies to be considered. In this hierarchy, each subtask is defined in terms of goal states or termination conditions. Each subtask in the hierarchy corresponds to its own MDP, and the methods seek to compute a strategy that is locally optimal for each subtask.Many researches in RL allow the learner to work not just with primitive actions, but with higher-level, temporally-extended actions, called options [55, 57, 58, 81]. An option is a closed-loop policy that operates over a period of time, and is defined by the tuple (I,π,β), where π is its strategy, I⊂S is the initiation set of states, and β(s) is the probability of termination in state s. The theory of options is based on the theories of MDPs and semi-Markov decision processes (SMDPs), but extends these in significant ways. Options and models of options can be learned for a wide variety of different subtasks, and then rapidly combined to solve new tasks. Using options enables planning and learning simultaneously, at a wide variety of times scales, and toward a wide variety of subtasks. However, the agent's action set is augmented rather than simplified by options which intensify the dimensionality of action spaces.A Hierarchical Abstract Machine (HAM) is a program that diminishes the number of decisions by partially representing the strategy in the form of finite state machines (FSMs) with a few nondeterministic choice points [56]. HAMs also exploit the theory of SMDPs, but the emphasis is on restricting the policy space rather than augmenting the action space. A HAM is a collection of three tuples Hi=(μ,I,δ), where μ is a finite set of machine states, I is the initial state, and δ is the transition function determining the next state using either deterministic or stochastic transitions. The main types of machine states are: start (execute the current machine), action (execute an action), call (execute another machine), choice (select the next machine state), and stop (halt execution and return control). Further, for any MDP M and any HAM H, there exists an induced MDP M0=H∘M [56] that works with a reduced search space using single-step and multistep (or high-level) actions. As a consequence, the induced MDP is in fact a SMDP, because actions can take more that one timestep to complete. A learning algorithm for the induced SMDP is a variation of Q-learning called SMDP Q-learning. This algorithm can be applied to the HAMs framework using an extended Q-table Q([s,m],a), which is indexed by an environment state s, machine state m, and action a taken at a choice state m. Just like options, these HAMs have to be expertly designed because they place strict restrictions on the final strategy possible for the original MDP.In the MAXQ framework [51], the temporally extended actions or subtasks are organized hierarchically. Faster learning is facilitated by constraining and structuring the space of strategies, encouraging the reuse of subtasks, and enabling effective task-specific state abstraction and aggregation. Unlike options and HAMs, the MAXQ framework does not reduce the original MDP into one SMDP. Instead, the original MDP M is split into sub-SMDPs M0,M1,…,Mn, where each sub-SMDP represents a subtask.The big contribution of [82–85] consists in extending the MAXQ framework to the average reward setting with promising results. The work in [86] is a simple extension of the MAXQ framework to the multiagent setting, and it leverages the structure of the task hierarchy to communicate high-level coordination information among the agents. Learning the structure of the task hierarchy is a very promising area of HRL research. The work in [87] introduces HEXQ, an algorithm that uses frequency of change in the state variables to partition the state space into subtasks—the faster a variable changes, the more likely it is part of the state abstraction of a lower-level subtask. Empirical results pit HEXQ against MAXQ (with a predefined hierarchy) and show that, though there is initial overhead in discovering the hierarchy, HEXQ ends up performing comparably. The work in [88] uses planning to automatically construct task hierarchies based on abstract models of the behaviors' purpose. It then applies RL to flesh out these abstractly defined behaviors, and to learn the choices for ambiguous plans.


## 5.1. Factored Approaches

When the state space of the MDP can be specified as a cross-product of sets of state variablesEi(E=E0×E1×⋯×En), it is called a factored MDP (FMDP). The concepts of state abstraction and aggregation are strongly related to the idea of a factored state space. A factored formulation also allows for system dynamics to be specified using a more natural and intuitive representation instead of an S×S probability matrix per action. Representations that can describe such structure are 2-slice Dynamic Bayesian Networks (DBNs) [78] and probabilistic STRIPS operators, the former being more popular in the literature.In [48], the authors exploit such a factored state space directly, and reveal reduction in the computation and memory required to compute the optimal solution. The assumption is that the MDP is specified by a set of DBNs, one for each action, although the claim made is that it is amenable to a probabilistic STRIPS specification too. In addition to using the network structure to elicit variable independence, they use decision-tree representations of the conditional probability distributions (CPDs) to further exploit propositional independence. Next, they construct the structured policy iteration (SPI) algorithm which aggregates states for two distinct reasons: either if the states are assigned the same action by the current strategy, or if states have the same current estimated value. With the aggregation in place, the learning algorithm (based on modified policy iteration) only computes at the coarser level of these state partitions instead of that of the individual states. The algorithm itself is split into two phases, structured successive approximation and structured policy improvement, mirroring the two phases of classical policy iteration. It is important to note that SPI will see fewer advantages if the optimal strategy cannot be compactly represented by a tree structure, and for the reason that there is still big overhead in finding the state partitions.In [53], Algebraic Decision Diagrams (ADDs) replace the decision-tree learning of SPI for the value function and strategy representation. The paper deals with a very large MDP (≈63 million states) and shows that the learned ADD value function representation is considerably more compact than the corresponding learned decision tree in most cases. However, a big disadvantage of using ADDs is that the state variables must be boolean, which makes the modified state space larger than the original.In order to solve large weakly coupled FMDPs, the state space of the original MDP is divided into regions that comprise sub-MDPs which run concurrently (the original MDP is a cross-product of the sub-MDPs) [79]. It is assumed that states variables are only associated with a particular task and the numbers of resources that can be allocated to the individual tasks are constrained; these global constraints are what cause the weak coupling between the sub-MDPs. Their approach contains two phases: an offline phase that computes the optimal solutions (value functions) for the individual sub-MDPs and an online phase that uses these local value functions to heuristically guide the search for global resource allocation to the subtasks.One class of methods for solving weakly coupled FMDPs involves the use of linear value function approximation. In [52], the authors present two solution algorithms (based on approximate linear and dynamic programming) that approximate the value functions using a linear combination of basis functions, each basis function only depending on a small subset of the state variables. In [80], a general framework is proposed that can select a suitable basis set and modify it based on the solution quality. Further, they use piecewise linear combination of the subtask value functions to approximate the optimal value function for the original MDP. The above approaches to solving FMDPs are classified under decision-theoretic planning in that they need a perfect model (transition and reward) of the FMDP. The work in [50] proposes the SDYNA framework that can learn in large FMDPs without initial knowledge of their structure. SDYNA incrementally builds structured representations using incremental decision-tree induction algorithms that learn from the observations made by the agent.


## 5.2. Hierarchical Approaches

To deal with large-scale FMDPs, RL approaches aim to leverage the structure of the state space. However, they do not impart enough structure to the strategy space itself. Hierarchical reinforcement learning (HRL) is a broad and very active subfield of RL that imposes hierarchical structure onto the state, action, and strategy spaces. To alleviate the curse of dimensionality, HRL applies principled methods of temporal abstraction to the problem; decision-making should not be required at every step but instead temporally extended activities or macro-operators or subtasks can be selected to achieve subgoals.The work in [49] proposes a new approach which relies on a programmer to design a hierarchy of abstract machines that limit the possible strategies to be considered. In this hierarchy, each subtask is defined in terms of goal states or termination conditions. Each subtask in the hierarchy corresponds to its own MDP, and the methods seek to compute a strategy that is locally optimal for each subtask.Many researches in RL allow the learner to work not just with primitive actions, but with higher-level, temporally-extended actions, called options [55, 57, 58, 81]. An option is a closed-loop policy that operates over a period of time, and is defined by the tuple (I,π,β), where π is its strategy, I⊂S is the initiation set of states, and β(s) is the probability of termination in state s. The theory of options is based on the theories of MDPs and semi-Markov decision processes (SMDPs), but extends these in significant ways. Options and models of options can be learned for a wide variety of different subtasks, and then rapidly combined to solve new tasks. Using options enables planning and learning simultaneously, at a wide variety of times scales, and toward a wide variety of subtasks. However, the agent's action set is augmented rather than simplified by options which intensify the dimensionality of action spaces.A Hierarchical Abstract Machine (HAM) is a program that diminishes the number of decisions by partially representing the strategy in the form of finite state machines (FSMs) with a few nondeterministic choice points [56]. HAMs also exploit the theory of SMDPs, but the emphasis is on restricting the policy space rather than augmenting the action space. A HAM is a collection of three tuples Hi=(μ,I,δ), where μ is a finite set of machine states, I is the initial state, and δ is the transition function determining the next state using either deterministic or stochastic transitions. The main types of machine states are: start (execute the current machine), action (execute an action), call (execute another machine), choice (select the next machine state), and stop (halt execution and return control). Further, for any MDP M and any HAM H, there exists an induced MDP M0=H∘M [56] that works with a reduced search space using single-step and multistep (or high-level) actions. As a consequence, the induced MDP is in fact a SMDP, because actions can take more that one timestep to complete. A learning algorithm for the induced SMDP is a variation of Q-learning called SMDP Q-learning. This algorithm can be applied to the HAMs framework using an extended Q-table Q([s,m],a), which is indexed by an environment state s, machine state m, and action a taken at a choice state m. Just like options, these HAMs have to be expertly designed because they place strict restrictions on the final strategy possible for the original MDP.In the MAXQ framework [51], the temporally extended actions or subtasks are organized hierarchically. Faster learning is facilitated by constraining and structuring the space of strategies, encouraging the reuse of subtasks, and enabling effective task-specific state abstraction and aggregation. Unlike options and HAMs, the MAXQ framework does not reduce the original MDP into one SMDP. Instead, the original MDP M is split into sub-SMDPs M0,M1,…,Mn, where each sub-SMDP represents a subtask.The big contribution of [82–85] consists in extending the MAXQ framework to the average reward setting with promising results. The work in [86] is a simple extension of the MAXQ framework to the multiagent setting, and it leverages the structure of the task hierarchy to communicate high-level coordination information among the agents. Learning the structure of the task hierarchy is a very promising area of HRL research. The work in [87] introduces HEXQ, an algorithm that uses frequency of change in the state variables to partition the state space into subtasks—the faster a variable changes, the more likely it is part of the state abstraction of a lower-level subtask. Empirical results pit HEXQ against MAXQ (with a predefined hierarchy) and show that, though there is initial overhead in discovering the hierarchy, HEXQ ends up performing comparably. The work in [88] uses planning to automatically construct task hierarchies based on abstract models of the behaviors' purpose. It then applies RL to flesh out these abstractly defined behaviors, and to learn the choices for ambiguous plans.


## 6. Dantzig-Wolfe Decomposition

Kushner and Chen [61] investigate the use of the Dantzig-Wolfe decomposition in solving large MDPs as linear programs. Thus, in this section we describe briefly this classic decomposition procedure. A reference for a more complete description is [89].We consider linear programming problems with the following a block angular structure:(6.1)Min∑l=1hclxl,s.t.[A1A2···AhB1B2···Bh][x1x2····xh]=[ab1b2···bh],xl≥0,l=1,2,…,h,
where the Al are mo×nl matrices and the Bl are ml×nl matrices with full row rank. Problems of this type can be decomposed by using the Dantzig-Wolfe decomposition. We get h subproblems, corresponding to the constraints Blxl=bl.Letpjl,j∈Pl, denote the extreme points of the subproblem related to Bl. Problem (6.1) can be reformulated as:
(6.2)min∑l=1h∑j∈Pl(clpjl)x¯jl,s.t.∑i=1h∑j∈Pl(Alpjl)x¯jl=a,∑j∈Plx¯jl=1,l=1,…,h,x¯jl≥0.Problem (6.2) is called the full master problem. Instead of looking at the full master problem we only consider a subset of the columns and then generate new columns when they are needed. The reduced or the restricted master problem has m0+h rows, where the last h corresponds to the convexity constraints. We assign the dual variables y to the first m0 constraints of the restricted master problem and λ to the h convexity constraints. In each master iteration, the restricted master problem is solved. Each of the subproblems is then solved with the cost vector (cl-yAl). Hence, the lth subproblem to be solved is
(6.3)min(cl-yAl)x̃l,s.t.Blx̃l=bl,x̃l≥0.If there exists a solutionx̃l with (cl-yAl)x̃l-λl<0, then a column with negative reduced cost has been found, and it is introduced into the restricted master. The new column is given as [Alx̃lel], where el∈ℜh is the lth unit-vector. It has the cost clx̃l.Both the master problem and the subproblems axis on the use of simplex method in solving the linear program in (6.2). We refer the readers to [90] for more details about (i) cycling prevention and (ii) the initialization of the simplex method using big-M method. Using the Dantzig-Wolfe decomposition, the solution is improved iteratively and converges to an optimum solution in a finite number of iterations.


## 7. Conclusion

The benefit of decomposition techniques is that we are able to deal with subproblems of smaller size; the tradeoff is that often extra effort is required to combine the solutions to these subproblems into a solution to the original problem. Thus, some new methods are expected to cope with the difficulty of combining the subproblems.Many of the approaches discussed in this survey are collection of separate mature fields coming together to deal with the twin drawbacks of curse of dimensionality and lack of model information in most real-world systems. For instance, many Hierarchical Reinforcement Learning concepts utilize some notions of programming languages such as subroutines, task stacks, and control threads. We speculate if any other domains are forthcoming to be imported.



---

*Source: 659432-2010-07-07.xml*