Year: 2021

Abstract:
Decision trees are robust modeling tools in machine learning with humaninterpretable representations. The curse of dimensionality of Markov Decision Process (MDP) makes exact solution methods computationally intractable in practice for large state-action spaces. In this paper, we show that even for problems with large state space, when the solution policy of the MDP can be represented by a tree-like structure, our proposed algorithm retrieves a tree of the solution policy of the MDP in computationally tractable time. Our algorithm uses a tree growing strategy to incrementally disaggregate the state space solving smaller MDP instances with Linear Programming. These ideas can be extended to experience based RL problems as an alternative to black-box based policies.

heading: 1 INTRODUCTION
text: Deep neural network based Reinforcement Learning (RL) has seen recent success in tackling Markov Decision Problem (MDP) instances with large state-action space. For example, the MuZero model (Schrittwieser et al. (2020)) has been able to successfully beat human performance in previously computationally untractable problems such as Shogi, Chess and Atari games with a single modeling paradigm. The success of these methods can be traced to two fundamental ideas in RL: First, the iterative nature of the Q-learning algorithm (see Watkins & Dayan (1992)) where the state-action value function can be updated locally without having to handle the whole state-action space at once as in exact methods; Second, the non-linear parameterization of the state-action value function and the policy function with deep neural networks, where in a sense, the state space model is “learned” and compressed without having to update and explore the whole state space. While successful methods, they are not devoid of drawbacks. Their strength in not taking into account the whole action-state space is also their weakness which manifests in the well-known worst case slow convergence of Q-learning (see Szepesvári et al. (1998)) as well as the relatively slow convergence of the gradient-based methods for training deep neural networks for regression.
In this paper, we aim to apply the essence of these two ideas to develop an algorithm to solve a subset of instances of MDP, that while having large enough state-action space such that exact methods are computationally intractable, their solution policy admits a representation as a decision tree that can be computed by exact methods. In summary, we aim to do an improvement over these instances with two ideas: First, the use of exact methods, such as Dynamic Programming (DP) or Linear Programming (LP), rather than iterative methods to compute the state-action value function; Second, the use of decision trees to partition the state space and codify the optimal policy rather than using deep neural networks. In Figure 1 we show the subset of problems we aim to tackle in the gray area. That is, problems with large enough state space such that exact methods are not tractable, but the action space is still not too large. This is key, as the size of the policy function representation as a decision tree depends on the structure of the state space being partitionable in regions with the same optimal action.
To illustrate these concepts we consider the cartpole balancing example, which consists of controlling a cart that can move either to right or left in a straight rail. Perpendicular to the axis of movement of the cart, there is a pole attached to a rotating axis at its center. With two actions A = {←,→} the goal is to have the pole attached to the cart balanced in the upright position for the longest possible amount of time. The state space of the system is a 4-dimensional vector of real numbers S = {(x, v, θ, w) : x ∈ [−ℓ1, ℓ1], v ∈ [−ℓ2, ℓ2], θ ∈ [−ℓ3, ℓ3], w ∈ [−ℓ4, ℓ4]} (position, horizontal velocity, angle and angular velocity). Here, the state space is of infinite size |S| = ∞. Instead of using deep Q-learning, we use a decision tree based algorithm that outputs the policy in Figure 2.
This decision tree serves two functions simultaneously: It defines a partition or “aggregation” of the state space S into disjoint regions that will be the states of a much smaller MDP; and second and most importantly, it summarizes the optimal policy as a decision tree, giving a transparent and interpretable control policy. These two points are the same ideas that make deep Q-learning methods successful: Aggregation of the space and non-linear parameterization of the optimal policy. The MDP went from having a infinite cardinality to a reduce state space of only 6 states.

heading: 2 RELATED WORK
text: In the RL and MDP literature the idea of state aggregation starts as early as the discipline itself as an answer to the curse of dimensionality for large state-action spaces. One of such ideas is to make a large state space discrete by aggregating states into “boxes” (see Fox (1973)). Our method takes ideas from the Variable Resolution idea where a given discretization is further refined by constructing finer boxes around regions of the state space where the discretization does not approximate well the value function. One of those methods is the “Trie Model” (see Moore (1991)) where a tree model with similar ideas to ours is used to identify regions of the state space that need to be further partitioned while still applying Dynamic Programming methods to obtain a policy. Their main criterion to make a split was to identify regions of the state space where the model was inaccurate (in a value function sense) and increase the resolution of the MDP by further partitioning these regions. In Singh et al. (1995) the convergence for the Q-learning algorithm is proved for the “softaggregation” scheme where states belong to disjoint clusters with a given probability (including the hard cluster case where states belong to only one cluster), our work borrows a similar description of the aggregated MDP (from a cluster level) that we use to define our Linear Programming formulation. Bounds on the performance of value iteration over disjoint state aggregation are given in Van Roy (2006).
A large stream of literature then focuses on parameterization of the value function as means to defeat the curse of dimensionality (which is an indirect way to aggregate the state space). Approximate Dynamic Programming (see Bertsekas (2008) for a summary overview) is a parameterization of the value function by a lower-dimensional linear basis of the state space. On the non-linear case, nearest neighbor approximations have been used in Shah & Xie (2018). Kernel functions are used in Ormoneit & Sen (2002) and Ormoneit & Glynn (2002). Decision Trees have been used in Ernst et al. (2005) to similarly approximate the Q-function of unseen samples. Much of the recent literature focus on Deep Neural Network based RL which can be seen as a non-linear representation of the state-action value function (see Li (2017) for an overview) as well as a non-linear parameterization of the policy as stated in the introduction. Actor-critic architectures (see Haarnoja et al. (2018)) have also seen recent success in tackling large scale problems.
A characterization theory of state aggregations is studied in Li et al. (2006), where the most common families of aggregations (bisimulation, and equivalent value function aggregations) is studied and a hierarchy between them is given. A related work to ours is Kim & Dean (2003) where a similar sequential partition is used for finding sequential state aggregations, our work differs in the criteria to make splits, whereas we approximate the behavior of the whole MDP, Kim & Dean (2003) chooses a split based on the maximum distance between value functions from one iteration to the next positioning their work closer to the variable resolution literature.
Our method is new in the sense that instead of exclusively focusing on the resolution relative to the value function (that is, instead of trying to approximate and interpolate the value function at unseen points) we find a state aggregation abstraction of the original state space with a reduced state space with the same optimal policy as in the original state space, given that the original MDP admits such representation. We further discuss the theory and potential computational savings of MDP abstraction in Section A.3.

heading: 3 METHODOLOGY
text: In this section we describe our methodology connecting the representation of policies as decision trees and the aggregation of the original state space resulting in a much smaller MDP with equivalent optimal policy.

heading: 3.1 MARKOV DECISION PROCESSES
text: A Markov Decision Process (MDP) is a modeling framework that in simple terms finds optimal decisions with a changing environment over time with the goal of finding the “best” actions given the state of the environment. Formally, a MDP is composed of an environment represented by a state space S, a set of actions A. An agent in state s ∈ S , takes an action a ∈ A. After this, the agent transitions to state s′ ∈ S and receives a reward r ∈ R with probability p(s′, r|s, a), which is independent of the previous history of states or actions, making the model a Markov chain. Given the state and action s, a the reward is a quantity R(s, a, s′). A policy π : S → A is a function that maps states s ∈ S to a single action a1. For simplicity, assume that there is a terminal state that ends the subsequent transitions (an absorbing state E). This state is reached in a random number of T transitions. The cumulative discounted reward an agent receives by interacting in the system using a policy π is given by:
Eπ [ ∞∑ t=0 γtR(st, π(st), st+1) ] . (1)
Given a complete description of the model, the policy that maximizes the cumulative reward is given by the Bellman optimality equation:
Vπ(s) := ∑ s′,r P(s′, r|s, π(s))[r + Vπ(s′)], (2)
V∗(s) = max a ∑ s′,r P(s′, r|s, a)[r + V∗(s′)]. (3)
1The extension to stochastic policies is straightforward and not considered here.
Where Vπ(s) is the expected reward starting at state s following policy π, the expression Vπ(s) can be intuitively derived by a first-step analysis on the fact that the system is memoryless by the Markov property of Markov chains, that is, the expected reward in one state is simply the one step expected reward obtained in that state r (after taking action π(s) and transitioning to state s′) plus the expected reward of starting at state s′. The optimal policy V∗(s) is simply taking the greediest action a at every state s in the expected reward sense.

heading: 3.2 REPRESENTATION OF POLICIES AS DECISION TREES
text: In this subsection we show the connection between state aggregation and policy representation as decision trees. A policy π is a mapping between the state space S and the action setA. This mapping is similar to a classification problem, in the sense that in a classification problem the goal is to divide the input space into “regions” classifying them into different classes. In MDP, the goal is similar as the policy divides the state space S into disjoint regions corresponding to elements of the action set A. Similar to Deep Neural Networks (DNN), decision trees are also good function approximators. An analogous function approximation theorem for decision trees is that for any policy π(s), there exist a tree T with J leaves L = {Ej}Jj=1 such that the policy π can be approximated by the function π(s) = ∑J j=1 π̄(Ej)1{s ∈ Ej} where {π̄(Ej)}Jj=1 is a collection of piecewise constant actions in A. Given this relation between a policy and a decision tree π(s) = ∑J j=1 π̄(Ej)1{s ∈ Ej}, it is natural to think of a related MDP where the states are the partitions of the state space rather than the larger (and potentially infinite) original state space. This approximated MDP could be far away from accurately approximate the reward of the original MDP but its resolution is good enough to identify the optimal policies.
The challenge lies in identifying a growing strategy for the trees that is able to find the optimal policy π∗ by iteratively partitioning the state space and taking the leaves of the tree as meta-states of a reduced MDP approximating the behavior of this policy in the original state space. The growing strategy needs an objective value that is able the compare the overall quality of different trees with respect to finding optimal policies in the original state space. For example, as any tree algorithm normally starts by collapsing all states into a single one, any partition into two disjoint subsets needs to take into account the sizes of the partitions as well as the approximated behavior of the aggregated MDP with respect to the original state space and quantify its improvement with respect to the initial tree where all states are collapsed into one.

heading: 3.3 AGGREGATED MDP
text: Suppose the state space of the original MDP is aggregated into J meta-states. This aggregation is a disjoint partition S = ∪Jj=1 Ej into disjoint events Ej . Then, for any state s ∈ S there is only one index j, such that s ∈ Ej . To define an MDP under this aggregated state space let the transition probabilities be (for meta-states E ,E ′ and action a ∈ A):
P(E ′|E , a) = P(s ′ ∈ E ′, s ∈ E , a) P(s ∈ E , a) , (4)
R(E , a,E ′) = E(R(s, a, s′)|s′ ∈ E ′, s ∈ E , a). (5) We summarize the dynamics implied by Equations (4) and (5) with the notation P(E ′, r|E , a). A solution method of the aggregated MDP using Linear Programming is given by solving the following optimization program:
minV,q ∑J j=1 µ(Ej)V (Ej) (6)
s.t. q(Ej , a) = ∑J
k=1 ∑ r P(Ek, r|Ej , a)[r + γV (Ek)], for j = 1, . . . , J, a ∈ A,
V (Ej) ≥ q(Ej , a), for j = 1, . . . , J, a ∈ A. Where µ is an arbitrary probability measure on the meta-states {Ej} such that µ(Ej) > 0 for all j = 1, . . . , J (see Chapter 6 of Puterman (1994)). Note that when the meta-states E are singletons, that is, each event only contains one state, this formulation is equivalent to solving the original MDP.
The policy implied by the solution of this MDP (denoted π̃) is naturally defined in the aggregated state space {Ej}Jj=1. That is, π̃∗ : {Ej}Jj=1 → A. Extending this policy to the original state space is straight-forward by letting π̃∗(s) = π̃∗(Ej) for all s ∈ Ej . Whenever a policy is defined, its state space can be interchangeably understood by this extension.

heading: 3.4 TREE PARTITION AND APPROXIMATION TO ORIGINAL MDP
text: A tree T is a collection of sequential binary partitions of the state space S. For example, suppose S = {x : x ∈ Rd}, that is, the state space is the set of d-dimensional real-valued vectors, where xi is the i-th entry of the vector x. A tree T is composed by a set of J leaves L = {Ej}Jj=1. A leaf is a sequence of binary splits of the state space, for example, the leaf E = xi1 ≤ τ1, · · · , xik > τk is composed by a sequence of binary splits of the state space (≤ or >) at some threshold level sequence τ1, . . . , τk ∈ R, with i1, · · · , ik being a index sequence of integers in {1, · · · , d}. The set of leaves is a disjoint partition of the state space, that is ∪Jj=1Ej = S and Ej ∩ Ek = ∅ for j ̸= k.
Given a tree T with a set of leaves L = {Ej}Jj=1 the problem in Equation 6 can be solved to obtain a solution of the aggregated MDP. Let G(π) be the cumulative expected reward of the original MDP under policy π and pdf λ for the initial state (that is, λ(s) ≥ 0 and ∑ s∈S λ(s) = 1 with cdf Λ(s)
defined by some ordering of s ∈ S), that is, let G(π) := Eπ [∑∞ t=0 γ tR(st, at, st+1)|s0 = Λ−1(U) ] where U is an independent uniform (0, 1) random variable.
An approximation of the expected reward G given by the aggregated MDP can be obtained by setting the measure µ(Ej) equal to µ(Ej) = ∑ s∈Ej λ(s). The intuition of why this measure approximates
G(π̃) is given by the fact that the optimal objective value of the linear program ∑J
j=1 µ(Ej)V∗(Ej) is the expected reward of the aggregated MDP with starting state given by the distribution µ. By making µ(Ej) proportional to P(s0 ∈ Ej) in the original MDP we match the distribution of the initial state. As the dynamics P(E ′, r|E , a) are an average of the dynamics of the original MDP, we have G̃(π̃∗) := ∑ s∈Ej P(s0 ∈ Ej)V∗(Ej) is an approximation of G(π̃
∗) where π̃∗ is the policy implied by solving the LP in Equation (6). In Section A.4 we discuss the optimality of the aggregated policy.

heading: 3.5 TREE ALGORITHM FOR MDP
text: In this subsection we assume the state space is the set of d-dimensional real-valued vectors, that is, S = {x : x ∈ Rd}, where xi is the i-th entry of the vector x. Let |E | be the Lebesgue measure of a subset E ⊆ Rd. The meta-states E = xi1 ≤ τ1, · · · , xik > τk are composed by a sequence of binary splits of the state space (≤ or >) at some threshold level sequence τ1, . . . , τk ∈ R, with i1, · · · , ik being a index sequence of integers in {1, · · · , d}.
Given a tree L, let G̃(L) be the expected reward of the MDP after solving the aggregated MDP with partition L in Equation (6), that is, G̃(L) := G̃(π̃∗) (as discussed, this in an approximation of the reward of the original MDP). Let the initial partition T0 with leaves set composed of one single meta-state E0 = S. The set of leaves is L0 = {E0}. As an improvement step, we are interest in further partitioning the state space from L0 into a partition L1 such that G̃(L0) < G̃(L1), meaning that the expected reward of the MDP (under the partition L1) is higher than under L0. Intuitively, adding information allows to make better decisions. As L0 ⊂ L1 ⊂ · · · ⊂ Lk, meaning that the sets of leaves is grown from the set of leaves from the previous iteration. Then, a sequence of increasing expected reward partitions would be found, that is, a sequence:
G̃(L0) ≤ G̃(L1) ≤ · · · ≤ G̃(Lk−1) ≤ G̃(Lk). (7) An interpretation of (7) is that a sequence of increasing partitions L0 ⊂ · · · ⊂ Lk ⊆ S each providing more information (and a more accurate model approximation) such that at every iteration, as more information is available, better policies can be found.
Selecting a partition can be done as follows: Start with a partition L. Given the set of leaves L, let L(xi ≤ τ) := {E ∈ L : |E | ≥ |E , xi ≤ τ |}, that is, the set of leaves where partitioning at xi ≤ τ would effectively partition it (thus reducing its uniform measure in the original state space). Consider the candidate partition L(xi, τ) := L\L(xi ≤ τ)∪
⋃ E∈L(xi≤τ) {E , xi ≤ τ}∪{E , xi > τ},
that is, removing the events E from the leaf set by splitting them into two new leaves (events)
{E , xi ≤ τ} and {E , xi > τ}. Then, greedily select the partition that most increases the expected reward of the MDP. That is, by optimizing the following problem:
max i,τ
G̃(L(xi, τ)). (8)
Which can be seen as selecting the variable i and the threshold τ that best partitions the state space L and generates highest expected reward, each of these operations needs to compute the input probabilities for the LP in Equations (4) and (5) and the LP in Equation (6). After finishing the pass, the new partition (set of new leaves) is equal toL\L(xi∗ ≤ τ∗)∪
⋃ E∈L(xi∗≤τ∗) {E , xi∗ ≤ τ∗}∪{E , xi∗ > τ∗}
for i∗, τ∗ = argmaxi,τ G̃(L(xi, τ)). The algorithm can be summarized as: Algorithm 1: State-Space Partition Algorithm for MDP:
• Step 0: Initialize L = {E0}. With E0 = S. Let g∗ := G̃(L). Go to Step 1. • Step 1: Solve maxi,τ G̃(L(xi, τ)). Go to Step 2. • Step 2: If maxi,τ G̃(L(xi, τ)) > g∗ update g∗ ← maxi,τ G̃(L(xi, τ)), L ← (L \ L(xi∗ ≤ τ))∪
⋃ E∈L(xi∗≤τ∗) {E , xi∗ ≤ τ∗} ∪ {E , xi∗ > τ∗} for i∗, τ∗ = argmaxi,τ G̃(L(xi, τ)) and
go to Step 1. Otherwise, stop.
Each new partition may split more than one leaf node at every iteration. See the example in Section A.1 for a step by step example run of the algorithm in a 2-dimensional grid.

heading: 3.6 COMPUTATIONAL COMPLEXITY
text: As discussed in subsection 3.2 the optimal policy π∗ of the original MDP can be represented by a tree with J∗ leaves (approximating the optimal policy as π∗(s) = ∑J∗ j=1 π̃(Ej)1{s ∈ Ej}). Suppose our procedure can find an equivalent tree after a certain number of iterations such that the size of the tree is equal to J∗ at such iteration k (this depends on the particular instance and its transition and reward structure). In this section we discuss the computational effort at iteration k of our algorithm and use this result to bound the overall computational complexity of our algorithm.
Solving an MDP using Linear Programming as in Equation (6) has complexity of order O(np) where n is the number of variables/constraints (in our LP formulation the number of constraints is equal to the number of variables in Equation (6) which is the size of the state-action space |S||A|). The degree of the polynomial can be taken as p = 2.5 if following the algorithm for LP in Vaidya (1989) or even lower when considering more recent advances in matrix multiplication as in Cohen et al. (2021).
The complexity of our procedure at iteration k is the number of partitions that can be done at iteration k times the complexity of solving instances of LP of size n = s(k)|A| (the size of the instances increases as the iterations of our algorithm increase). As the number of total possible partitions is bounded by some constant (dependent on the size of the original state space) K(S), the complexity of our algorithm at iteration k is O((K(S)−k)s(k)p|A|p). That is, the number of available partitions K(S) − k times the complexity of solving a LP of size s(k). As s(k) is a worst-case estimate of the size of the state-action space, letting k = s−1(J∗) is a conservative estimate of the number of iterations necessary for the algorithm to find the tree.
The complexity can be then bounded as s−1(J∗)O((K(S)−s−1(J∗))s(s−1(J∗))p|A|p) which can be simplified to O(K(S)J∗p|A|p) by absorbing s−1(J∗) as a constant inside the big-O notation (noting that it is independent of the size of the state-action space). Comparing this with the complexity of the original MDP of order O((|S||A|)p) highlights the potential computational savings of our algorithm, as K(S)≪ |S| (for intuition, consider the case when S is a discretized d-dimensional grid of size |S| = Md, across every dimension there are M possible levels to partition, then the total number of partitions is K(S) = Md). Up to a constant, our procedure is more efficient than solving the original problem if J∗ < |S|/ √ K(S). Or, in other words, up to a constant our procedure is |S|/ √ K(S)J∗ faster than solving the original MDP. This highlights that the savings of our procedure happen obviously when
J∗ is small compared to |S|. Note that the action space size |A| is always a bottleneck as the LP instances are of size always proportional to |A| at every iteration. Thus, our procedure is tractable as long as the action space A is relatively small. Likewise, the savings in computation also depend on the size J∗ of the tree which a priori is not known.
In the next two subsections we present an explicit from for the state space function size s(k) and the corresponding complexity to the common “box” discretization scheme in 2 and d dimensions.

heading: 3.6.1 2-DIMENSIONAL GRID
text: We describe the worst-case complexity of our algorithm a 2-dimensional grid: Let the state space S = {(x, y) : x = 1, . . . ,M, y = 1, . . . , N} be a 2-dimensional grid of sizes N times M . The size of the worst-case instances of the MDP at iteration k is given by:
s(k) =
{( k+2 2 )2 k ≤ 2m
k(m+ 1)−m2 + 1 k > 2m (9)
for m := N ∧ M . The expression comes from dividing a rectangle using k lines (partitions), kx vertical and ky horizontal, such that k = kx + ky results in (kx + 1)(ky + 1) partitions of a rectangle. This product is maximal when qx = qy getting the bound on the number of partitions( k 2 + 1 )2 = ( k+2 2 )2 . Next, as kx ≤ N and ky ≤ M without loss of generality assume N < M . When the number of partitions k is greater than 2N we have kx remains at N for a total of (N + 1)(k −N + 1) = k(N + 1)−N2 + 1 partitions. In this case the number of new partitions available at every iteration is K(S)− k = N +M − k+1 (the minus k comes from the fact that at every iteration there is one partition less available out of N + M possible partitions). Then, for k > 2m and without loss of generality N ≤ M such that m = N , the worst case complexity is O((N +M −k+1)(k(m+1)|A|)p) which can be simplified to O(M(k(N +1)|A|)p) after canceling the N +1 outside with k that is greater than 2N . Compare this to the complexity of the original problem of O((NM |A|)p). In this case, our algorithm works best when N is far from M from a complexity point of view as we can take M (which in this case is the maximum between N and M ) from inside the polynomial of the LP complexity and deal with a smaller size 2N < k < M instances of LP.
In summary, by letting m = N ∧M and m̄ = N ∨M the worst-case complexity of our procedure is O(m̄(k(m + 1)|A|)p) compared to original problem of complexity O((NM |A|)p). See Section A.2 for the complexity analysis of the d-dimensional case. The d-dimensional grid case is also promising for applications where the state space is continuous (and thus infinite and uncountable) but some suggested discretization is possible (either data-driven or ad-hoc). In this case, while the state space is infinite, the partition algorithm can guide an optimal discretization structure. See the cartpole balancing example in the numerical section.

heading: 4 NUMERICAL EXAMPLES

heading: 4.1 GRIDWORLD
text: We present an instance of Gridworld as an example of our method. Gridworld consist of a grid where an agent moves to reach a goal (ending) state using one of four moves (actions) A = {↑, ↓,→,←} (moving up, down, right or left one step in the grid). Each state is represented by a coordinate (x, y) ∈ Z2+ in a grid. Each state (x, y) has a reward r depending only in the state. In this setting transitions are deterministic once an action is taken (this can be relaxed without loss of generality, to allow jumps or stochastic transitions once an action is taken). We illustrate an instance of Gridworld in Figure 3.
In Figure 4 we plot side by side the optimal policy by solving the original MDP and our tree algorithm in Algorithm 1. Although the instance is trivial it highlights the computational savings of our methodology by only needing 6 states (other than the initial and terminal states which are given) rather than 28 in the original state space.

heading: 4.2 CARTPOLE BALANCING
text: A popular benchmark for Reinforcement Learning problems is the so-called cartpole balancing problem, which consists of controlling a cart that can move either to right or left in a straight rail. Perpendicular to the axis of movement of the cart, there is a pole attached to a rotating axis at its center. With two actions A = {←,→} the goal is to have the pole attached to the cart balanced. The state space of the system is a 4-dimensional vector of real numbers S = {(x, v, θ, w) : x ∈ [−ℓ1, ℓ1], v ∈ [−ℓ2, ℓ2], θ ∈ [−ℓ3, ℓ3], w ∈ [−ℓ4, ℓ4]}. In Figure 5 we present a diagram of the cartpole system. x in the diagram represents the horizontal position of the pole, v represents the horizontal velocity of the cart (positive means moving to the right), θ is the angle (in radians) from the vertical upright position of the pole (positive means the pole is in a clockwise position) and w is the angular velocity of the pole (positive means rotating clockwise).
In this case, we generate n = 10, 000 random instances of data {(x, v, θ, w), a, r, (x′, v′, θ′, w′)} with a totally random policy (given a state of the cart (x, v, θ, w), move the cart left or right with equal probability). The reward r is equal to 1 for every unit of time the pole stays upright (the angle is |θ| < 0.28 radians), otherwise the reward r is 0 (meaning that the pole has fallen). Note that is very different from the usual pipeline of doing reinforcement learning as we only used a previous generated data and do not assume access to a simulator to generate new policies in this case. With this sample data, we estimate sample estimates of the parameters in Equations (4) and (5).
As it is, the problem is hard as the control problem is continuous on the state variables. Moreover, the equations governing the mechanics of the cart are non-linear equations that in principle are not given and subject to random perturbations. Typically, one way the infinite state space problem can be remedied is by discretizing it resulting in the d-dimensional grid case discussed in Section A.2
(with d = 4) with computational complexity O(|M1M2M3M42|p) for the original MDP resulting in a large state space size even for moderate values of M1,M2,M3,M4.
Using our decision tree procedure in Algorithm 1 for Mi = 10 equidistant cuts of the domain [−ℓi, ℓi] for i = 1, . . . , 4 solves the problem in 3 iterations of the algorithm (in this case, solving the cartpole problem consist in finding a policy that maintains the pole stable in the upright position beyond a threshold time). The size of the instances at the 3rd iteration of our algorithm is just 6 states for a total complexity of order 40(6× 2)p using Algorithm 1 compared to solving a 4-dimensional discretized MDP of complexity of order (104 × 2)p. The policy that solves the cartpole problem is plotted in Figure 2. For n′ = 1000 random unseen instances controlled with the policy in Figure 2 (started in the upright position with a random perturbation), the average expected reward is 187.93 with median 199.0 (the instances were stopped once the reward reached 200). It is important to note that this control tilts the cart slightly to the left, nonetheless, given the succinct policy representation it is noteworthy that the cartpole can be successfully controlled at all with a data-driven algorithm not deep learning based.
This method opens up a new angle to tackle non-linear continuous control problems without a simulator in the presence of uncertainty where the optimal policy can be represented as a lower dimensional tree policy. Moreover, the tree policy is attractive compared to a black-box policy. Doing an adversarial analysis (an adversarial attack consist in finding inputs in the state space that generate an undesirable action, see Behzadan & Munir (2017)) on a finite tree is much easier than with a continuous deep neural network. For example, a tree based policy used for landing a drone relying on sensors can be easily stress tested for reliability as the policy of the tree has a finite number of scenarios where an action is deterministically chosen. This cannot be said from a policy encoded in a black-box deep neural network as there can always be regions in the input space where the action chosen is unknown and an attacker can try to exploit the policy at these regions to induce catastrophic outcomes.

heading: 5 CONCLUSION
text: In this paper we have presented a decision tree algorithm for MDP that is computationally tractable even when the state space is prohibitively large as long as the optimal policy has a lower dimensional tree structure. On top of computational tractability the tree structure of the solution policy is transparent and interpretable.
Further research effort is needed in exploring the statistical properties of sampling partitions to speed up the algorithm (as in traditional tree algorithms). Another interesting open research question is to establish a theory for adversarial RL for tree-based policies. Moreover, there is an open path for extending these ideas to an online RL algorithm where an interpretable policy is desirable but exact methods are intractable as in the cartpole example.

heading: A APPENDIX
text: A.1 2-D GRIDWORLD EXAMPLE
We illustrate our algorithm with the following example: Let S = {(x, y) : x = 1, . . . ,M, y = 1, . . . , N} be a 2-dimensional grid. In this 2-dimensional grid the action set is composed of four actions A = {↑, ↓,←,→}, that is, moving up, down, left or right in the grid. Moreover, let the rewards R(x, y) arbitrary real values assigned to each point in the grid. The reward of the MDP is discounted at a rate γ ∈ (0, 1). Let P((x′, y′), r|(x, y), a) be the transition probabilities and rewards of the original problem (for example, if we consider the deterministic case where every action takes the agent to the intended square without perturbation, then, P((x, y + 1)|(x, y), ↑) = 1 for x = 1, . . . ,M, y = 1, . . . ,M − 1). At iteration 0 (initialization) we have E0 = S, that is, all states are aggregated into a single state. Solving this “degenerate” MDP amounts to evaluate the following program:
minV,q µ(E0)V (E0)
s.t. q(E0, a) = R(E0, a,E0) + γV (E0), for a ∈ A, V (E0) ≥ q(E0, a), for a ∈ A.
R(E0, a,E0) = E{R(x′, y′)|(x′, y′) ∈ E0, (x, y) ∈ E0, a} is the average reward of performing action a ∈ A in the aggregated state as in Equation (5). For example, R(E0,→,E0) =
1 (M−1)N ∑M i=2 ∑N j=1 R(i, j), R(E0,←,E0) = 1 (M−1)N ∑M−1 i=1 ∑N j=1 R(i, j), R(E0, ↑,E0) =
1 M(N−1) ∑M i=1 ∑N j=2 R(i, j) and R(E0, ↓,E0) = 1 M(N−1) ∑M i=1 ∑N−1 j=1 R(i, j), note how on each expected value, the boundary (of states that are not visited) is removed. The transition probabilities are all equal to one, as any action is going to move to the only state E0 = S. The above program can be further simplified as V (E0) = (1 − γ)−1 maxa∈A R(E0, a,E0) as µ(E0) = 1. This quantity is a rough approximation of the reward of the MDP by only performing the action argmaxa∈A R(E0, a,E0) at every state in the original state space S . At the next iteration, the goal is to split state E0 into two states E1 and E2 that has the highest increase in the expected reward of the MDP. The possible vertical splits are τx = 1, . . . ,M while the horizontal splits are τy = 1, . . . , N . Performing a split at level τx results in two states: E1 = x ≤ τx and E2 = x > τx. This results in the following set of equations:
R(E1, ↑,E1) = 1
τx(N − 1) τx∑ i=1 N∑ j=2 R(i, j), R(E1, ↓,E1) = 1τx(N−1) ∑τx i=1 ∑N−1 j=1 R(i, j),
R(E1,→,E1) = 1
(τx − 1)N τx∑ i=2 N∑ j=1 R(i, j), R(E1,←,E1) = 1(τx−1)N ∑τx−1 i=1 ∑N−1 j=1 R(i, j),
R(E2, ↑,E2) = 1
(M − τx)(N − 1) M∑ i=τx+1 N∑ j=2 R(i, j), R(E2, ↓,E2) = 1(M−τx)(N−1) ∑M i=τx+1 ∑N−1 j=1 R(i, j),
R(E2,→,E2) = 1
(M − τx − 1)N M∑ i=τx+2 N∑ j=1 R(i, j), R(E2,←,E2) = 1(M−τx−1)N ∑M−1 i=τx+1 ∑N j=1 R(i, j),
R(E1,→,E2) = 1
N N∑ j=1 R(τx + 1, j), R(E2,←,E1) = 1N ∑N j=1 R(τx, j).
With transition probabilities:
P(E1|E1,→) = (τx − 1)N
τxN = 1− τ−1x , P(E2|E1,→) = NτxN = τ −1 x ,
P(E2|E2,←) = (M − τx − 1)N (M − τx)N = 1− (M − τx)−1, P(E1|E2,←) = N(M−τx)N = (M − τx) −1,
P(E1|E1, ↑) = P(E1|E1, ↓) = 1, P(E2|E2, ↑) = P(E2|E2, ↓) = 1.
With these, at the first iteration the LP in Equation (6) with two states is solved for τx (here we let µ(E1) be the uniform distribution, or simply said, the number of points in the grid in E1, that is τxN/MN ):
minV,q τxN MN V (E1) + (M−τx)N MN V (E2) s.t. q(Ej , a) = ∑2
k=1 P(Ek|Ej , a)[R(Ej , a,Ek) + γV (Ek)], for j = 1, 2, a ∈ A, V (Ej) ≥ q(Ej , a), for j = 1, 2, a ∈ A.
Solving an instance of this problem for each value of τx and τy , and choosing the one with highest value for the LP is the first iteration of the algorithm. The objective is the approximated2 expected reward of the original MDP by sampling the first state according to the distribution µ(E ).
Suppose that the partition with highest expected reward (value of the LP) is given by τ∗x . The policy implied by the LP is π∗(E1) = argmaxa∈A q ∗(E1, a) and π∗(E2) = argmaxa∈A q ∗(E2, a).
2Under the aggregated space.
As discussed previously, the objective of the LP can be also seen as the approximated reward of the original MDP by following policy π∗(E1) whenever (x, y) ∈ E1 and policy π∗(E2) whenever (x, y) ∈ E2. At next iteration a similar process is followed, given the states E1 = x ≤ τ∗x and E2 = x > τ∗x at the end of the previous iteration, these states would be further partitioned by considering the rest of partitions τx = 1, . . . , τ∗x − 1, τ∗x + 1, . . . ,M and τy = 1, . . . , N . Vertical partitions (across the x-axis) would partition the state space in 3 partitiosns (states) E1 = x ≤ τ∗x , x ≤ τx, E2 = x ≤ τ∗x , x > τx and E3 = x > τ∗x for τx < τ∗x or E1 = x ≤ τ∗x , E2 = x > τ∗x , x ≤ τx and E3 = x > τ∗x , x > τx for τx > τ ∗ x . Horizontal partitions (across the y-axis) would partition the state space into 4 partitions (states) given by: E1 = x ≤ τ∗x , y ≤ τy , E2 = x > τ∗x , y ≤ τy , E3 = x ≤ τ∗x , y > τy and E4 = x > τ∗x , y > τx. These two situations can be visualized by partitioning a rectangle vertically (across the x-axis) at first iteration, at the next iteration another vertical partition would result in 3 states, while a horizontal one (across the whole rectangle) would divide the state space into 4 regions. Whenever a partition is performed it might or not affect all states at the previous iteration, identifying which states are further divided is what motivates the definition of the set L(xi ≤ τ) in the algorithm subsection.
A.2 d-DIMENSIONAL GRID
In the worst case of a d-dimensional grid, let the state space S = {(x1, . . . , xd) : x1 = 1, . . . ,M1, x2 = . . . , xd = 1, . . . ,Md} be a grid of sizes M1 × · · · ×Md. Without loss of generality assume M1 ≤ M2 ≤ · · · ≤ Md. Using a similar analysis as in the 2 dimensional case, a hyperrectagle in d-dimensions with k = k1+ · · ·+kd lines partitioning it across every axes in every dimensions has ∏d j=1(kj + 1) partitions. Likewise, this product is maximal when k1 = · · · = kd resulting in at most (k/d+ 1)d partitions at iteration k.
When k > M1/d, we have that k1 = M1 and the number of partitions becomes (M1 + 1) (
k−M1 d−1 + 1 )d−1 . By induction this process can be continued until the last dimension to get∏d−1
j=1(Mj + 1) ( k − ∑d−1 j=1 Mj + 1 ) partitions in the worst case. This result can be summarized
with the function s(k) as:
s(k) =  (k/d+ 1)d k ≤M1/d (M1 + 1) ( k−M1 d−1 + 1 )d−1 M1/d < k ≤M2/(d− 2) (M1 + 1)(M2 + 1) ( k−M1−M2 d−1 + 1 )d−2 M2/(d− 2) < k ≤M3/(d− 3) ...∏d−1 j=1(Mj + 1) ( k − ∑d−1 j=1 Mj + 1 ) k > Md−1/(d− 1)
(10)
Similarly, the number of partitions available is K(S) − k = [ ∑d
j=1 Mj ] − k + 1. Recall the state space is of size |S| = ∏d j=1 Mj . Depending on the structure of the problem, the worst possible case of the algorithm is of similar complexity to the original problem when k is large. Nonetheless, in a usual instance of the problem the optimal partition selected by the algorithm does not follow the adversarial structure of these worst-case bounds of increasing the number of partitions as the objective value is rather trying to increase the overall reward of the MDP than just greedily increase the size of the state space.
A.3 STATE AGGREGATION THEORY
We borrow the state aggregation framework of Li et al. (2006) to describe our proposed tree space aggregation procedure. A state aggregation of a given MDP (S,A, P,R, γ) into an aggregated representation (S̃,A, P̃ , R̃, γ) is defined by a function ϕ mapping elements from the original MDP into new aggregated states, that is, ϕ : S → S̃. The transitions and rewards of the original MDP are linear combinations adding up to 1 of the original rewards, that is, for E ,E ′ ∈ S̃ (the elements of S̃
are denoted as such as they can be interpreted as “events” of the original state space, for example, a leaf of a decision tree describes an event of the original state space and all states falling into it are aggregated as a single state):
P(E ′|E , a) = ∑
s∈ϕ−1(E ) ∑ s′∈ϕ−1(E ′) w(s)P(s′|s, a), (11)
R(E , a,E ′) = ∑
s∈ϕ−1(E ) ∑ s′∈ϕ−1(E ′) w(s)R(s, a, s′). (12)
The weights w(s) can be interpreted as the relative importance of each state into their aggregated state, these weights add to 1, that is ∑ s∈ϕ−1(E ) w(s) = 1 for all E ∈ S̃3. In Li et al. (2006) depending on properties of the aggregation function ϕ a hierarchy of state aggregations is presented. This hierarchy has on one side the coarsest possible aggregation where all states are collapsed to one, and on the other end the finest possible aggregation of the original state space (that is, the original representation of the state space). They describe a partial ordering between these aggregations (one aggregation contains another if all its partitions are subsets of the partitions of the other state aggregation, this is denoted by ⪰ where the finer aggregation scheme goes on the l.h.s. of the relationship). The hierarchy showed in the paper is summarized as (Theorem 2 in the paper):
ϕ0 ⪰ ϕmodel ⪰ ϕQπ ⪰ ϕQ∗ ⪰ ϕa∗ ⪰ ϕπ∗ . (13)
Where ϕ0 is the original (finest) representation of the MDP. ϕmodel is a representation where the rewards and transition probabilities of the aggregated states is the same as in the original MDP (the so-called bisimulation aggregation in the literature). ϕQπ is an aggregation where all states aggregated have the same Q-function value for all policies π. In ϕQ∗ all aggregated states have the same Q-function value for the optimal policy only and all actions a ∈ A. ϕa∗ is an aggregation where all aggregated states have the same optimal action and the optimal Q-function evaluated at the optimal action is the same for all states aggregated. Lastly, ϕπ∗ is an aggregation where all states in a class have the same optimal action.
This is an important discussion, because going to the right of the hierarchy (coarser aggregations of the state space) would achieve higher computational savings if solving an aggregated representation of the MDP allows to retrieve an equivalent solution to the original one. In Li et al. (2006) is showed that up to the aggregation scheme ϕa∗ there are guarantees of optimality by solving the problem in the aggregated state space using Q-learning. There is also a negative result for the aggregation ϕπ∗ where convergence to the optimal policy of the original MDP is not guaranteed.
In this paper we propose another family of aggregations that we call ϕtree, which is an abstraction where the original solution of the MDP has a tree structure and a reduced (aggregated) MDP where the states are determined by the leaf of such tree and its optimal solution is equivalent to the original MDP. That is, a MDP (S,A, P,R, γ) has a solution π∗(s) = ∑J j=1 1{s ∈ Ej}π∗(Ej) where π∗(Ej) for j = 1, . . . , J is the solution of the MDP (S̃,A, P̃ , R̃, γ) and {Ej}Jj=1 are the leaf of a tree composed of binary partitions.
The family of partitions ϕtree is of computational interest as it is between ϕa∗ and ϕπ∗ in the partial ordering hierarchy of state aggregations, that is, ϕa∗ ⪰ ϕtree ⪰ ϕπ∗ , thus, potentially achieving sizable computational savings for large state MDPs beyond the well studied first 3 hierarchies (ϕmodel, ϕQπ and ϕQ∗ ) trying to aggregate the state space according to the value function.
A.4 DISCUSSION ON OPTIMALITY OF ALGORITHM 1
Here we present an informal discussion of the convergence of Algorithm 1 and present an intuitive argument of when the structure of the original MDP lends itself to have a tree structure such that the reduced MDP has an equivalent solution. In plain words, whenever the optimal structure (geometry of the paths) of the MDP is characterized by a (sub-)modular function, a tree structure of an aggregated MDP will capture the structure of the optimal solution of the original problem.
3These can be seen as analogous of Equations 4 and 12 for a policy πw with stationary distribution w in that aggregation.
Consider the following gridworld example with state space S = {(x, y) : x = 1, . . . ,M, y = 1, . . . , N} and reward equal to 1 at (M,N). With action set A = {↑, ↓,←,→}. In this case the solution of this MDP is given by the value function V∗(x, y) = γd1(x,y)/(1− γ2) where d1(x, y) is the Manhattan distance to the point (M,N) with reward equal to 1. To see why this is the case, the solution from any point (x, y) is to take the deterministic shortest path to the point with reward 1, once this point is reached a reward of 1 is accumulated at even period, that is a reward γd1(x,y)(1 + γ2 + γ4 + γ6 + · · · ) which is a geometric series by the substitution γ′ = γ2. What is important here is that the structure of the optimal policy with respect to the other states follows a structure determined by the distance function. To this end, define the random variable T : S × A × U → S which denotes the transition to a new state by applying an action to the current state (the U is a random uniform representing the randomness in the case where transitions are not deterministic). In this case Ta(x, y) is just the deterministic state that is reached by applying action a from state (x, y), for example, action a =→, makes Ta(x, y) = (x+ 1, y). With this, we have that the optimal policy is determined completely by the distance function d1(x, y) in the neighboring points spanned by the actions a ∈ A:
π∗(x, y) = argmin a∈A 1 + d1(Ta(x, y)), (14)
This follows from d1(x, y) = 1 + d1(Ta∗(x, y)) with a∗ = argmina∈A d1(Ta(x, y)) because the distance to any contiguous transition is equal to 1. The key observation is that while there are many shortest paths to the high reward circuit, the metric implied by Ta(x, y) defines an aggregation of the policies as in Figure 6. This follows from the fact that the distance function is modular d1(x, y) = 1 + d1(Ta∗(x, y)) as previously discussed.
Then, an MDP aggregation with 4 states as in Figure 7 has the same structure in its solution than the original MDP. For any point (x, y), the mapping to the aggregated states is given by E1 = x < M, y < M , E2 = x ≥ M,y < M , E3 = x < M, y ≥ M and E4 = x ≥ M,y ≥ M , or simply the blue lines in Figure 6. As said before, Equations 4 and 5 can be seen as linear combinations (adding to 1) of the original rewards and transition probabilities. Then, the only state with positive reward is E4, that is, R(E4) = 1 for preceding any action. Otherwise R(E ) = 0 for E ∈ {E1,E2,E3}.
The structure of the solution of this MDP is given by:
π∗(E ) = argmin a∈A E[d̃(E , Ta(E )) + d̃(Ta(E ),E4)] = argmin a∈A E[p−1a + d̃(Ta(E ),E4)], (15)
where d̃(Ta(E ),E4) is the expected number of steps to state E4 from state Ta(E ). In this instance of the problem, for any two connected states E and E ′ by action a ∈ A (for example, from E1 to E3 only the action a = ↑ has positive probability of transitioning), with probability pa the chain moves to pa, otherwise it stays with probability 1− pa. From this, by the average of a geometric distribution the average number of steps to connected states is d̃(E , Ta(E )) = p−1a . The structure of the aggregated MDP is optimal with respect to the original state space as R(E4) is the only state with positive reward. Moreover, π∗(x, y) = π∗(E ) for (x, y) ∈ E . Note that there is also a correspondence between the transient states of the optimal policy of the aggregated MDP and the transient states of the original MDP. The recurrent states of the aggregated MDP contain the recurrent of the original MDP.
This argument can be extended to problems where the optimal policy in both aggregated and original state spaces is given by two modular functions d, d̃ that captures the span of the actions and the recurrent circuits of maximum reward (given any policy π, the MDP behaves as a Markov Chain with transition matrix Pπ . Then, the solution of the MDP is a Markov Chain that can be canonically decomposed into transient and closed recurrent classes, these classes are by definition high reward circuits). In a way, the modularity of the function d is what allows the reduction of the state space to work.
As a last and key point, note that the optimal value function V∗(x, y) = γd1(x,y)/(1 − γ2) is in a way a distraction from the true driver of the solution of the problem, the distance function d1(x, y). From this point of view, aggregating states according to the similarity of the value function is not the appropriate way of solving these instances.

Review summaries:
The authors propose a method to solve MDPs with large state-space and moderately sized action-space, where a decision tree can represent the optimal policy.  The decision tree is learned by iteratively partitioning the state space such that the approximation of the policy by the expanded decision tree improves the expected reward. Finding the best partition in each step involves solving a Linear Programm.  The authors provide an extensive analysis of the computational complexity of their method and demonstrate its strengths in a Gridworld example and the Cartpole problem.

This paper studies using decision tress in lieu of deep neural networks in MDPs. The authors use them to partition the state space and represent the policies. Then they use LP to find the optimal policy. The authors claim to tackle the "gray area" where the state space is huge but not large action spaces as one of their key contributions.   

The paper presents an approach to the MDP based on the construction of a decision tree that is expected to well approximate the optimal policy while reducing the complexity of computing such an effective policy.  The idea is to partition the state space into meta states and use a single action for all the states in the same class. The classical greedy construction of decision tree is applied to determine the partitioning. The splitting criterion is to choose at each iteration among all present leaves the one that allows the splitting with maximum gain in terms of expected reward.