Decision Tree Algorithms for MDP
Authors: Elioth Sanabria
David Yao
Henry Lam
Venue: ICLR 2022 Submitted (2022)

Abstract: Decision trees are robust modeling tools in machine learning with human-interpretable 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.

Under review as a conference paper at ICLR 2022
A DECISION TREE ALGORITHM FOR MDP
Anonymous authors
Paper under double-blind review
ABSTRACT
Decision trees are robust modeling tools in machine learning with human- interpretable representations. The curse of dimensionality of Markov Decision Process (MDP) makes exact solution methods computationally intractable in prac- tice 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 tree of the solution policy the MDP in computationally tractable time. Our algorithm uses a tree grow- ing 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.
INTRODUCTION
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. ) has been able to successfully beat human performance in pre- viously 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 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 "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 (Szepesvári et al. (1998)) as well as the relatively slow convergence of the gradient-basee methods for training deep neural networks for regression.
In this paper, we aim to apply the essence of these two ideas to develop 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 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 of exact methods, such 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 [ 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 control- ling 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 AA = {+,-+) 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 [-4,, fa]} (position, horizontal
S s= {(x, v, 8, w) velocity, angle and angular velocity). Here, the state space is of infinite size [S] = co. Instead of using deep Qelarnnngg
[-(1, E [-82, E2), 0 E [-fs, fs),
decision tree based algorithm that outputs the policy in Figure 2

---

Under review as a conference paper at ICLR 2022
[8]
Exact Methods
LPDP
AA
MDP Solving Method:
Q-learnng based, Policy/Value Iteration. Parameterization of value function: ADP. Deep Learning Based. Parameterization policy function: Deep Learning Based.
Figure Solution Methods for MDP relative to state-action space size. The blue area denotes problems that are tractable using exact methods. The red area is the subset of problems where deep neural network based Q-learning is the most used solution method. The gray area is the subset of problems we aim to tackle.
This decision tree serves two functions simultaneously: It defines partition "aggregation" of the state space into disjoint regions that will be the states of a much smaller MDP; and second and most importantly, it summarizes the optimal policy
decision tree, giving transparent and in- terpretable 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 reduce state space of only 6 states.
w <
0.39
w > -0.39
0
-0--
0 < 0
00
0 > 0
0 :
0 +
0
Figure Cartpole solution policy n" (ax, v, 0, w) from our algorithm.
2 RELATED WORK
In the RL and MDP literature the idea of state aggregation starts early 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" (sx (177))) Our method takes ideas from the Variable Resolution idea where a given discretization is further refined by con- structing finer boxes around regions of the state space where the discretization does approximate well the value function. One of those methods is the "Trie Model" (see Moore (199T)) where a tree model with similar ideas to ours is used 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 make a split was identify regions of the state space where the model was inaceu- rate (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 "soft- aggregation" scheme where states belong to disjoint clusters with given probability (including the hard cluster case where states belong to only one cluster), our work borrows similar description of the aggregated MDP (from cluster level) that we to define our Linear Programming for- mulation. Bounds on the performance of value iteration over disjoint state aggregation are given in Van Roy (2006).
2

---

Under review as a conference paper at ICLR 2022
A large stream of literature then focuses parameterizzation of the value function means defeat the curse of dimensionality (which is an indirect way to aggregate the state space). Approximate Dynamic Programming (see [errtsekas (2008) for 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 neighhor approximations have been used in [Shah & Xie (2018). Kernel functions used in Ormoneit & Sen (2002) and Ormoneit & Glynn (2002) Decision Trees have been used in Ernst et al. (2005) 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 non-linear representation of the state-action value function (see Li (2117) for an overview) as well as a non-linear parameterization of the policy stated in the introduction. Actor-critic architectures (see Haarooaa et al. (2018) have also seen recent success 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 used for finding sequential state aggregations, our work differs in the crite- ria to make splits, whereas 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.
approximate the behavior of the whole MDP, Kim & Dean (2003)
Our method 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 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 Section A.3
METHODOLOGY
In this section describe methodology connecting the representation of policies decision trees and the aggregation of the original state space resulting in a much smaller MDP with equivalent optimal policy.
3.1 MARKOV DECISION PROCESSES
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, MDP is composed of an environment represented by state space S, a set of actions A. An agent in state s E S, takes an action a E A. After this, the agent transitions to state s' E S and receives reward E R with probability p(s', rls,a), which is independent of the previous history of states or actions, making the model a Markov chain. Given the state and action maps states s to a single action df) 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 policy is given by:
the reward is a quantity R(s, a, s'). A policy S + A is function that
Σ r R(s,, x (8r), sex1)
E
Given a complete description of the model, the policy that maximizes the cumulative reward is given by the Bellman optimality equation:
V*(s) > Plsssr Vz(s')),
(2)
(s(s) = max
P(s
(3)
'The extension stochastic policies straightforward and considered here.
3

---

Under review as a conference paper at ICLR 2022
Where Vs((s is the expected reward starting at state following policy я, the expression Va (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 I(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.
3.2 REPRESENTATION OF POLICIES AS DECISION TREES
In this subsection show the connection between state aggregation and policy representation as decision trees. A policy x is mapping between the state space S and the action set AA. This mapping similar to a classification problem, the sense that in a classification problem the goal is divide the input space into "regions" classifying them into different classes. In MDP, the goal is similar as the policy divides the state space into disjoint regions corresponding 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 = { such that the policy т can be approximated by the function E };} where (#()))) is collection of piecewise constant actions in (s)) = - A.
Given this relation between a policy and a decision tree ((s) =())=Ej EEi (c))1f to think of 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.
E & it is natural
The challenge lies in identifying a growing strategy for the trees that is able to find the optimal policy x" by iteratively partitioning the state space and taking the leaves of the tree 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 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.
3.3 AGGREGATED MDP
Suppose the state space of the original MDP is aggregated into J meta-states. This aggregation is a disjoint partition S U - 83 into disjoint events 6,. Then, for any state 8 E S there is only one index j. such that s E &,- To define an MDP under this aggregated state space let the transition probabilities be (for meta-states 6, 6' and action a E A):
(( P(8'E8,3EE,aa)
(4)
P(sE
R(E, 8²) E(R(s,a,s')) E6',EE,,d)
(5)
We summarize the dynamics implied by Equations and ( with the notation ((8", ())..))... solution method of the aggregated MDP using Linear Programming is given by solving the following optimization program:
A
miny. Σ)11(E))((8)
for j 1, ... J, a A, for j 1...., J, a A. Where μ is an arbitrary probability measure on the meta-states {6,) such that vu(E) > for all j = 1,.... J (see Chapter 6 of Puterman (1994)). Note that when the meta-states are singletons, that is, each event only contains one state, this formulation is equivalent solving the original MDP.
s.t. (6 ΣV rl,
V(E,) 2 (6),
4

---

Under review as a conference paper at ICLR 2022
The policy implied by the solution of this MDP (denoted it is naturally defined in the aggregated state space {& That is, #* { - A. Extending this policy to the original state space is straight-forward by letting # **(*) = i (63) for all E 63. Whenever a policy is defined, its state space can be interchangeably understood by this extension.
3.4 TREE PARTITION AND APPROXIMATION TO ORIGINAL MDP
A tree T is a collection of sequential binary partitions of the state space S. For example, suppose S = (a : Rd), that is, the state space is the set of d-dimensional real-valued vectors, where I; is the i-th entry of the vector I. A tree T is composed by set of J leaves L {6)) A leaf is sequence of binary splits of the state space, for example, the leaf & = Iú I T1, Jie > тą is composed by a sequence of binary splits of the state space (S or >) at some threshold level sequence Ti,.... Th E R. with i1. ... ig being index sequence of integers in (1.... .d) dd. The set of leaves is a disjoint partition of the state space, that is U/=1 = S and 6, n & = Ø for j # k.
Given tree T with set of leaves [ (6 the problem in Equation can be solved to obtain solution of the aggregated MDP. Let (=r)) be the cumulative expected reward of the original MDP under policy π and pdf À for the initial state (that is, X(8) 2 0 and EEEs A(s) = with edf A (s)) defined by some ordering of E S), that is, let G(T) == Ex [-i= R(s(, at, $t+1)/s0 = A (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 pl,,) equal to v(é,) = Exeæ, X(s). The intuition of why this measure approximates
G(#) is given by the fact that the optimal objective value of the linear program Dj=14( (. (6,) is the expected reward of the aggregated MDP with starting state given by the distribution By making ((8)) proportional to P(so E &j) in the original MDP we match the distribution of the initial state. As the dynamics P(ε', (6',,16, 06,00 a) are an average of the dynamics of the original MDP, we have G(#*)= Exee, P(50 E V.)V. (6,) is an approximation of G(**) where A* is the policy implied by solving the LP in Equation 6 In Section A.4 we discuss the optimality of the aggregated policy.
3.5 TREE ALGORITIIM FOR MDP
In this subsection we assume the state space is the set of d-dimensional real-valued vectors, that is, S = fo: : E Rdd, where z; is the i-th entry of the vector x. Let |&| be the Lebesgue measure of a subset & C Rdd The meta-states & = Ti, S TI, Ti, > The are composed by a sequence of binary splits of the state space (S >) some threshold level sequence .I.-.., Tk IR, with i1.... is being a index sequence of integers in .d).
Given a tree L. let G(C) be the expected reward of the MDP after solving the aggregated MDP with partition L in Equation (6) that is, G(C) == ((**) (as discussed, this in an approximation of the reward of the original MDP). Let the initial partition To with leaves set composed of one single meta-state & S. The set of leaves is Lo { As an improvement step, are interest in further partitioning the state space from Lo into partition L1 such that G(Lo) G(Li), meaning that the expected reward of the MDP (under the partition L1) is higher than under Ly. Intuitively, adding information allows to make better decisions. As Lo C Ci C .... C La, 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:
((Lo) I Ō(C,) < ... S G(Lx-1) S G(C,).
An interpretation of 77) is that a sequence of increasing partitions Co C ... C Lx S S each providing more information (and more accurate model approximation) such that at every iteration, as more information is available, better policies can be found.
Selecting partition can be done follows: Start with partition L. Given the set of leaves L, let L(x; T) := (6 E L : |6| 2 16, x < r/}. that is, the set of leaves where partitioning at I, would effectively partition it (thus reducing its uniform measure in the original state space).
Consider the candidate partition L(x,, T) == L L(xx S U)
U
(8, xg & u) > T),
that is, removing the events & from the leaf set by splitting them into two new leaves (events)
5

---

Under review as a conference paper at ICLR 2022
(6,z, T) and {E, > T}. Then, greedily select the partition that most increases the expected reward of the MDP. That is, by optimizing the following problem:
max G(C(Ei,)
(8)
Which can be seen selecting the variable and the threshold that best partitions the state space L and generates highest expected reward, each of these operations needs to compute the input probabil- ities for the LP Equations (4) and (5) and the LP in Equation (6). After finishing the pass, the new partition (set of new leaves) is equal to Lz5 ST") &EL(Z,
(6.00 S T Ju{8, I; > +*)
for 1", T" argmax,, G(C(I,; r)). The algorithm can be summarized as:
Algorithm 1: State-Space Partition Algorithm for MDP:
Step O: Initialize & = {60) With &o = S. Let 9. = G(C). Go to Step 1.
Step 1: Solve max,,, G(C(z, Go to Step 2.
Step 2: If maxi,, G(((xi,)) > go update g. f- maxi,r G(D(x, r)), L + (C L(z S (6, Ti- ST*) (6, Ti. > >*) } for i", = argmax; G(L(#1,) and
T)) U
go 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 step by step example run of the algorithm in a 2-dimensional grid.
3.6 COMPUTATIONAL COMPLEXITY
As discussed in subsection 3.2 the optimal policy x² of the original MDP can be represented by tree with J' leaves (approximating the optimal policy as x >*(s)= Σラ #(,;) E &j)). 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 A (this depends on the particular instance and its transition and reward structure). this section we discuss the computational effort at iteration 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(n²) where is the number of variables/constrainte (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 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. (202T.
The complexity of our procedure at iteration & is the number of partitions that can be done at iteration
k times the complexity of solving instances of LP of size = s(k))lA) (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) (SS), the complexity of our algorithm at iteration & is ((( (k)) (.P). That is, the number of available partitions (SS) k times the complexity of solving LP of size skk). As s(k) is a worst-case estimate of the size of the state-action space, letting A = s-1 (-((J) is conservative estimate of the number of iterations necessary for the algorithm find the tree.
The complexity can be then bounded as s be simplified to ((KSS)J*P AlP) by absorbing 8 (J*) as constant inside the big-O notation (noting that it is independent of the size of the state-action space). Comparing this with the com- plexity the original MDP of order ((((S]]A))P) highlights the potential computational savings of algorithm, K (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).
(J*'))AA which can
Up to a constant, our procedure is more efficient than solving the original problem if J < (K()). Or, in other words, up to a constant our procedure is /SI/VK(S (S)JJ" faster than solving the original MDP. This highlights that the savings of our procedure happen obviously when

---

See Section Under review as a conference paper at ICLR 2022
J" is small compared to (|). Note that the action space size |A| is always bottleneck 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 present an explicit from for the state space function size skk) and the corresponding complexity to the common "box" discretization scheme in 2 and d dimensions.
3.6.1 2- 2-DIMENSIONAL GRID
We describe the worst-case complexity of our algorithm 2-dimensional grid: Let the state space S = {(z, y) 1..... M, y ......N] . be 2-dimensional grid of sizes N times M. The size of the worst-case instances of the MDP at iteration is given by:
k+2) 2 2
k S 2m
s(k)
(9)
1k(m+))) m² +1
k 2m
for m := N A M. The expression comes from dividing rectangle using h lines (partitions),
ee vertical and ky horizontal, such that = kg + hy results in (kg + 1)(k, + 1) partitions rectangle. This product is maximal when qar 4y getting the bound on the number of partitions
(4 +1)² ( Next, as hi <. N and Ky I .M without loss of generality assume N < M. When the number of partitions k is greater than 2N have kg remains N for a total of (N + 1) N + 1) k(N + 1) - N2 + partitions.
In this case the number of new partitions available every iteration is K(S) -
(the minus & comes from the fact that at every iteration there is one partition less available out of N + MM possible partitions). Then, for 2m and without loss of generality N I M such that m N, the worst case complexity is O((N + M - k ()(k(m + A))) which can be simplified to (K ( + 1)) after canceling the + outside with & that greater than 2N, Compare this to the complexity of the original problem of (((N M [A))), In this case, our algorithm works best when N is far from from a complexity point of view as we can take (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 < < M instances of LP.
In summary, by letting m N M and m N V M the worst-case complexity of our procedure is (m + A))) compared to original problem of complexity O((NM)
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.
4 NUMERICAL EXAMPLES
4.1 GRIDWORLD
We present an instance of Gridworld as an example of our method. Gridworld consist of grid where an agent moves reach a goal (ending) state using one of four moves (actions) (moving up. down, right or left one step in the grid). Each state is represented by a coordinate (r,y) E 2 in grid. Each state (ær, y) has a reward r depending only in the state. In this setting transitions are deterministic once 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
(1.4. +,,,,,+
In Figure 4 we plot side by side the optimal policy by solving the original MDP and our tree algo- rithm 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.
7

---

Under review as a conference paper at ICLR 2022
Figure 3: Gridworld example: The green square is the starting state and the orange state is the goal. Each number in the grid represents the reward of visiting that state. The goal (starting at any point) is to reach the terminal state incurring minimum cost.
(a) Optimal policy
(b) Our tree policy after 3 iterations
Figure Side by side comparison of optimal policy nt and the tree policy implied by our algorithm.
4.2 CARTPOLE BALANCING
A popular benchmark for Reinforcement Learning problems is the so-called cartpole balancing problem, which consists controlling a cart that can move either to right or left a straight rail. Perpendicular to the axis of movement of the cart, there is pole attached to rotat- ing axis at its center. With two actions A {+,-} the goal to have the pole attached to the cart balanced. The state space of the system is 4-dimensional vector of real numbers = {(x, v 0,, ()) E [1,,,4],, E [- f2). E [-f3, (3), w E [-4,,4]], In Figure we present diagram of the cartpole system. the pole, represents the horizontal velocity of the cart (positive means moving to the right), is the angle (in radians) from the vertical upright position the pole (positive means the pole in clockwise position) and w is the angular velocity of the pole (positive means rotating clockwise).
the diagram represents the horizontal position of
W
Action=1
Figure 5: Cartpole state space and diagram.
In this case, we generate n 10, 000 random instances of data {(x, u, O, w), a, (x', v', d',a0 w²)} with a totally random policy (given state of the cart (z, v, 8, w). move the cart left or right with equal probability). The reward is equal to for every unit of time the pole stays upright (the angle 0 0.28 radians), otherwise the reward very different from the usual pipeline of doing reinforcement learning generated data and do not assume access to simulator to generate new policies in this case. With this sample data, estimate sample estimates of the parameters in Equations and
(meaning that the pole has fallen). Note that
only used previous
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 non-linear equations that in principle not given and subject to random perturbations. Typically, one way the infinite state space problem can be remedied by discretizing it resulting in the d-dimensional grid case discussed in Section A.2
8

---

Under review as a conference paper at ICLR 2022
(with d 4) with computational complexity O(IM,MM2M,MM22P for the original MDP resulting in large state space size even for moderate values of M1, M2, My, M4.
Using decision tree procedure in Algorithm 1 for M, 10 equidistant cuts of the domain [-&,, Cg] for = 1,.... solves the problem in 3 iterations of the algorithm (in this case, solving the cartpole problem consist in finding 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 total complexity of order 40(6 2) using Algorithm 1 compared solving 4-dimensional discretized MDP of complexity of order (10* x 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 per- turbation), the average expected reward 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 data-driven algorithm not deep learning based.
This method opens up a new angle to tackle non-linear continuous control problems without a sim- ulator in the presence of uncertainty where the optimal policy can be represented as lower dimen- sional tree policy. Moreover, the tree policy is attractive compared to black-box policy. Doing an adversarial analysis (an adversaria attack consist in finding inputs in the state space that generate an undesirable action, see [ehzadan & Munir (2017) on a finite tree is much easier than with a continuous deep neural network. For example, 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 unknown and an attacker can try to exploit the policy at these regions induce catastrophic outcomes.
based policy used for landing drone relying
5 CONCLUSION
In this paper we have presented a decision tree algorithm for MDP that is computationally tractable when the state space is prohibitively large long the optimal policy has a lower dimen- sional 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 online RI algorithm where an interpretable policy is desirable but exact methods are intractable as in the cartpole example.
REFERENCES
Vahid Behzadan and Arslan Munir. Vulnerability deep reinforcement learning to policy induction attacks. In International Conference on Machine Learning and Data Mining in Pattern Recogni- tion, pp. 262-275. Springer, 2017.
Dimitri Bertsekas. Approximate dynamic programming. 2008
Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM (JACM), 68(1):1-39, 2021.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503-556, 2005.
Bennett L Fox. Discretizing dynamic programs. Journal of Optimization Theory and Applications, 11(3):22--23, 1973.
Tuomas Haarojja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International confer- ence on machine learning, pp. 1861-1870. PMLR, 2018.

---

Under review as a conference paper at ICLR 2022
Kee-Eung Kim and Thomas Dean. Solving factored mdps using non--hooogeeouu partitions. Arti- ficial Intelligence, 147(1-2):22-2251
2003. 2003.
Lihong Li, Thomas J Walsh, and Michael L. Littman. Towards a unified theory of state abstraction for mdps. ISAIM, 4:5, 2006.
Yuxi Li. Deep reinforcement learning: An overview. arXiv preprint arXivv1701.0727.1 2017.
Andrew W Moore. Variable resolution dynamic programming: Efficiently learning action maps in multivariate real-valued state-spaces. In Machine Learning Proceedings 1991, pp. 333-337. Elsevier, 1991.
Dirk Ormoneit and Peter Glynn. Kernel-based reinforcement learning in average-cost problems. IEEE Transactions on Automatic Control, 47(10):1624-1633, 2002.
Dirk Ormoneit and Saunak Sen. Kernel-based reinforcement learning. Machine learning, 49(2): 161-178, 2002.
Martin I. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 1994.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon
Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):004-600 2020.
Devavrat Shah and Qiaomin Xie. Q-learning with nearest neighbors.
arXiv preprint
arXiv: 0000000000000... 2018
Satinder P Singh, Tommi Jaakkola, and Michael Jordan. Reinforcement learning with soft state aggregation. Advances in neural information processing systems, pp. 36.-3663,, 1995.
Csaba Szepesvári et al. The asymptotic convergence-rate of q-learning, Advances in neural infor- mation processing systems, pp. 1064-1070, 1998.
Pravin M Vaidya Speeding-up up linear programming using fast matrix multiplication. In 30th annual symposium foundations of computer science, pp. 332-337. IEEE Computer Society, 1989.
Benjamin Van Roy. Performance loss bounds for approximate value iteration with state aggregation. Mathematics of Operations Research, 3122)2334-244 2006.
Christopher JCH Watkins and Peter Dayan. Q-learning. Muchine learning, 8(3-4):279-29) 1992.
A APPENDIX
A.1 2-D GRIDWORLD EXAMPLE
We illustrate our algorithm with the following example: Let {(x, y) : x 1,..., M,y .,..., N) be 2-dimensional grid. In this 2-dimensional grid the action set is composed of four actions A = 4, +.,,,,,),, 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 7 E (0, 1). Let P((x', y/), rz(z, y), a) be the transition probabilities and rewards of the original problem (for example, if consider the deterministic case where every action takes the agent to the intended square without perturbation, then, P((x, y + 1)](x, y), for x .,.... M,y I,..., M 1).
At iteration 0 (initialization) we have &o = S, that is, all states are aggregated into a single state. Solving this "degenerate" MDP amounts to evaluate the following program:
miny, (()))V(())
s.t. (66,, a) = R(6, a, 60) + (66),
for E A, for A.
V(6) ( a).
10

---

Under review as a conference paper at ICLR 2022
R(66, a, G.) E(R(2', (')("',))((''' v/) &a, (x. y) E E,, is the average reward of perform-
ing action a E A in the aggregated state as in Equation
5 For example, R( -, -0) =
1 M E R(i,)), R(60; 60) = (M-1)N L= Ee R(i.j), R(6, 1,6) =
1
(M-I))
M Ee و 5) and R(60, 4, 60) M(N-T] iil 2بك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 6g = S.
M(N-1
The above program can be further simplified as ((6) y ((6))= - 1. This quantity is a rough approximation of the reward of the MDP by only perform- ing the action arg max R(6, a, E0) at every state in the original state space S.
(1 - ?) m R(6,, a, 60) as
At the next iteration, the goal is to split state 6o into two states 61 and &2 that has the highest increase in the expected reward of the MDP. The possible vertical splits are Tx = I....,M. .M while the horizontal splits are Ty I,..., .N. Performing split at level T, results in two states: 61 = r S Tz. and 62 = x >
Tz. This results in the following set of equations:
1
R(61,1,81
R(i,g), (() = - Et أEー1 R(i.)),
(N
1
-(61,-,611)
R(i,)), R() G.--IJ Eie ΣE=1 R(i,5).
(Tx N)N
im
R(62.1.82)
1
Σ
Σ R(I,), 6(62)),))) = (M (M-
D M
-i=r, +1 Ej=1 R(i.)),
(M- - -Tx) (NV 1)
i=T, +1
R(62, 02)
1
Σ
R(I,),, ((2,+,88) (M- Σ - Σソ= N
1
R(i.j),
(M -o 1)N
1 +2
1 N
R(6,, =
Σ
R(T + +15), 6() 1/2 E R(Tx.)).
With transition probabilities:
P +) = (Ta 1)N
=1- T
P(0)(6,, = N
ToN TT
N
8(6) -) (M - Tx2 - -1)N
(M - Tz)N = =1 1 -MM- - T1)
P( +) = (M-T.\N = (M - TZ)
N
p( = (( 11
166/66, t) = (2, =1
With these, at the first iteration the LP in Equation (6) with two states is solved for Ta (here let ((6)) be the uniform distribution, or simply said, the number of points in the grid in 61, that is
Tx N/N
MN Io V(6) + (M (M VN V(S)
minv,
MN MN
s.L. =2 P(6 a) ( 6x) + (6)))))
for = 1,2, A, for j = 1,2, E A.
V(6,) 2 a)
Solving an instance of this problem for each value of Tn and Ty, and choosing the one with highest value for the LP is the first iteration of the algorithm. The objective is the approximated expected reward of the original MDP by sampling the first state according to the distribution p(8))
Suppose that the partition with highest expected reward (value of the LP) is given by T The policy implied by the LP is π'" (61) = arg m 9" (81, a) and TT" (62) = arg .a 9" ())
Under the aggregated space.
11

---

Under review as a conference paper at ICLR 2022
As discussed previously, the objective of the LP can be also seen the approximated reward of the original MDP by following policy π (6)) whenever (z, E Ei and policy x (62) whenever (I, y) E 62.
At next iteration a similar process is followed, given the states 6 = = = T and 82 > Tz at the end of the previous iteration, these states would be further partitioned by considering the rest of partitions Ta = 1,...,, T 1, + 1,..., M and Ty = I,...,N.. Vertical partitions (across the rr-axis would partition the state space in partitiosns (states) E1 x T S Tzx 62 I S x x > Ta and Eg r > To for Tx < To or 81 = I S Tgp E2 = I > Tap T. S Tx and 63 x > Tx x > To for Tz > T. Horizontal partitions (across the y-axis) would partition the
state space into 4 partitions (states) given by: 61 = S T I Ty. &2 = x > T S T3> 63 = x S : y > Ty and 6
y > Tz.
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 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(x, S 7) in the algorithm subsection.
A.2 d-DIMENSIONAL GRID
In the worst case of a d-dimensional grid, let the state space S = {(II,...... .xa) x] I,..., M,,32 = ..... Fa 1,................... Ma} be grid of sizes Mi ... Ma. Without loss of gen- erality assume Mi < M2 S .... < Ma. Using a similar analysis as in the 2 dimensional case, a hyperrectagle in d-dimensions with k k1 +.... kg lines partitioning across every axes in every dimensions has 115-1 (k3 + 1) partitions. Likewise, this product is maximal when k
ka
resulting in at most (k/d + 1d partitions at iteration k.
When > Md/d. we have that k = MM and the number of partitions becomes (M1 + 1)
Mi c + 1) By induction this process can be continued until the last dimension to get
IM + (s= E M, + +) partitions in the worst case. This result can be summarized
with the function s(k) as:
(k/d 1)d
3 Mi/d
d-1
(M++1) / + 1)
Mi/d < k S M2/(d-2) 22
d-2
s(k) =
(M1 + 1) +1)
K- + +1)
M2/(d- - 2) < ks Ma/(d-3) (10)
[M; + +1) ( My +
k> Ma-1/(d- 1)
Similarly, the number of partitions available is k M,]-K - + 1. Recall the state space is of size |S| = 11;= My. Depending on the structure of the problem, the worst possible case of the algorithm is of similar complexity to the original problem when & 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 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 given MDP (S, AS,,,P, P. Rt 7) into aggregated representation (8, A, P, R, 7) is defined by function mapping elements from the original MDP into new aggregated states, that is, o S + S. The transitions and rewards of the original MDP are linear combinations adding up of the original rewards, that is, for e, 8' E S (the elements of $
12

---

Under review as a conference paper at ICLR 2022
denoted such as they be interpreted "events" of the original state space, for example, leaf of a decision tree describes an event of the original state space and all states falling into it are aggregated as single state):
P(6')6a)) = Σ
Σ
w(s)P(s'|sso)
(11)
SEP (8) S'E (8))
Ri6,a,6 (E)-1(6) S'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 [8) w(s) = for all & E s In Li et al. (2006)
depending on properties of the aggregation function a hierarchy of state aggregations presented. This hierarchy has on one side the coarsest possible aggregation where all states are collapsed to one, and 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 h.h.s. of the relationship). The hierarchy showed in the paper is summarized (Theorem 2 in the paper):
Φo Pmodel t22 Φo= ØQ' ł Qa- 2
(13)
Where Φn is the original (finest) representation of the MDP. Omadel is representation where the rewards and transition probabilities of the aggregated states is the same as 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. Oa' is 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, ox. is aggregation where all states in class have the same optimal action.
This is important discussion, because going 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 retrieve an equivalent solution to the original one. In Li al. (2066) 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 Φx 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 ótrees 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 equivalent to the original MDP. That is, a MDP (S, P. R, 7) has a solution π (s) = = 1(s E 6 (d6) where x (d,) for j 1, ......JJ is the solution of the MDP (S, R, and { are the leaf of tree composed of binary partitions.
The family of partitions étree is of computational interest as is between 6.. and Ox- in the partial ordering hierarchy of state aggregations, that is. 6e. - Ótree 2 Φx,, thus, potentially achiev- ing sizable computational savings for large state MDPs beyond the well studied first hierarchies (Amodel,, &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 and present an intuitive argument of when the structure of the original MDP lends itself to have tree structure such that the reduced MDP has an equivalent solution. In plain words, whenever the optimal structure (ge- ometry of the paths) of the MDP characterized by a (subb)moodu function, tree structure of an aggregated MDP will capture the structure of the optimal solution of the original problem.
"These can be seen analogous of Equations and 12 for a policy Tw with stationary distribution in that aggregation.
13

---

Under review as a conference paper at ICLR 2022
Consider the following gridworld example with state space S { y)
1...., M,
I, and reward equal to at (M, With action set A = ( In this case the solution of this MDP is given by the value function (2 y) = ( (1r.)) /(1 - -22) where dj (x, y) is the Manhattan distance the point (M, N) with reward equal to To see why this is the case, the solution from any point (z, y) is to take the deterministic shortest path to the point with reward 1, once this point is reached a reward of is accumulated at even period, that is a reward 7 (1.0) + 7². What is important
y² + 7 70 + +...) which is geometric series by the substitution 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
S which denotes the transition to a new state by applying an action to the current state (the U is random uniform representing the randomness in the case where transitions are not deterministic). In this case (1, y) is just the deterministic state that is reached by applying action a from state (z, y), for example, action a =-, makes T,(2: (z. y) (z + 1. y). With this, we have that the optimal policy is determined completely by the distance function di (2r, y) in the neighboring points spanned by the actions a E A:
T (x, v) arg min + di aeA
(14)
This follows from d1 (z, y) = 1+ (T y)) with a' = arg min d1 (Z, y)) because the The key observation is that while there are many
distance to any contiguous transition equal shortest paths to the high reward circuit, the metric implied by Ta (2., y) defines aggregation
of the policies as in Figure [ This follows from the fact that the distance function modular (1 v) 1 + d1 (To- (I, y)) as previously discussed.
Figure 6: The point N) with reward I represented by A configuration of the shortest path trajectory such that points in every partition have the same direction. This is optimal as the metric induced by (x, is the Manhattan distance.
Then, an MDP aggregation with states as Figure 7 has the same structure in its solution than the original MDP. For any point (z, y). the mapping to the aggregated states is given by & x < M.y y < M, &g- = x 2 M,y < M, &3 = r M.y 2 M and 61 x 2 M, y 2 M, or simply the blue lines in Figure
& As said before, Equations 4 Hand be seen as linear combinations (adding to 1) of the original rewards and transition probabilities. Then, the only state with positive reward
e, that is, R(&)) = 1 for preceding any action. Otherwise R(6) 0 for & E (61, E2
8s
Ea
62
Figure 7: Optimal policy n² in the aggregation of MDP in Figure
The structure of the solution of this MDP is given by:
π.' T'68) = arg min E(d(,, d(T,(6). = arg min E(p_1' 1 + dd(a(6))
(15)
a
asA
14

---

Under review as a conference paper at ICLR 2022
where d(Ta(E) 61) is the expected number of steps to state 6, from state To(6). In this instance of the problem, for any two connected states & and 6' by action a E A (for example, from &1 to 63 only the action 1 has positive probability of transitioning), with probability Pa the chain moves Pa. otherwise it stays with probability
Pa- From this, by the average of geometric distribution the average number of steps to connected states is d(6, Ta (6) = P The structure the aggregated MDP is optimal with respect
the original state space as R((s) is the only state with positive reward. Moreover, x (<x,)) y) = π (6) 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 Pr. 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 way, the modularity of the function d is what allows the reduction of the state space to work.
As last and key point, note that the optimal value function Vv (1 /(1 72) is in way a distraction from the true driver of the solution of the problem, the distance function d1 (z, y) From this point of view, aggregating states according the similarity of the value function is not the appropriate way of solving these instances.
15


Reviews:
[{"review_id": "GT3Xoezw2AM", "reviewer": "Reviewer_qMvr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "* The problem addressed by the paper - computationally tractable solutions to MDPs - is important. The submission is clear and, as far as I can see, correct.\n\n* The interpretability of the resulting policy is a clear strength of the method. \n\n* The rigorous analysis of the computational complexity is a strength of the paper. \n\n* Empirical analysis: On the one hand, I find the analysis convincing in so far that the method needs very few (!) state partitions to solve these problems. On the other hand, there are no comparisons to baselines on these problems.\n\n* The computational burden of repeatedly solving the Linear Programs with growing complexity is probably the main disadvantage and prevents you from affording many iterations. However, for MDPs where the optimal policy actually has a lower-dimensional tree structure, you won’t need that many iterations in turn. The paper clearly states that the method is dedicated to those problems only, so I think it is fine.\n\n* Novelty: The authors mention that the method is similar to the Trie Model from Moore (1991), but I am unfamiliar with it and don't have access to the Moore (1991) paper, so I cannot assess this.\n\nIn general, the paper is well written. However, a few minor comments:\n* Section 3.2, 2nd paragraph: „an analogous function approximation theorem for decision trees …“ I would appreciate a reference to this theorem in literature.\n*Section1, 2nd paragraph: typo: the use OF exact methods, …\n*Section 3.2, 4th paragraph: typo: …with respect to findinG optimal policies …\n*Section 3.5, 1st paragraph: repetitive to Section 3.4 1st paragraph\n*I would change the title. It says „Decision Tree AlgorithmS“, but there is only one algorithm in the paper. Maybe something like „A Decision Tree Algorithm for MDPs“ or „Decision Trees for MDPs“?\n\n------\nPost-rebuttal:\n\nI understand why there are concerns about the scalability of the algorithm. In fact, I believe the method doesn’t scale for some problems. Namely all of the problems where the optimal policy doesn’t not have the underlying tree structure. But if the problems are of that kind, the method will only need few iterations and then it doesn’t matter too much if the iterations are expensive.\n\nI agree that the experimental section lacks a comparison to baselines. And that the examples are simplistic. While I like the simplicity of the example problems (because they demonstrate the concept well), I can see that it is common for a conference like this to also include larger-scale experiments.\n\nReviewer vkFy pointed out that the benefit of having a decision tree structure for a policy is the interpretability and that in the grid and cart pole example there is not really a need for this. I agree, but another benefit of the decision tree structure is the potential decrease in number of training iterations and that’s what the gird and cart pole example demonstrate well. \n\nI cannot comment on the novelty of the approach as I am not familiar with some parts of the related work. The other reviews might have a point here, or not. \n\nI agree with the optimality issue described by reviewer HjwV, and also with the author’s answer to this issue. I don’t know if it is enough to include a section informally discussing it as proposed by the authors, or if it is necessary to fully formalize this insight.\n\nIn total, I think that the approach has potential and is worth to be published at some point, but addressing the raised points from the other reviewers could indeed further improve the paper.\n", "summary_of_the_paper": "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. \nThe 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. \nThe authors provide an extensive analysis of the computational complexity of their method and demonstrate its strengths in a Gridworld example and the Cartpole problem.", "summary_of_the_review": "I vote for acceptance as the described method is an intuitive approach to exploit lower dimensional structure to solve computationally difficult high-dimensional problems.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EMlB0akIot8", "reviewer": "Reviewer_MpCH", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nMy first concern here is the novelty. As the paper misses a major related work: Tree-Based Batch Mode Reinforcement Learning, D. Ernst et. al., the tree architecture has been studied extensively before. \nSecondly, the experiment section are not sufficient because a) they do not highlight if the algorithm is scalable since only grid world/cart-pole domains are presented b)there is no comparison with existing algorithms.  \nThirdly, I do not agree with Fig. 1. Algorithms like DQN are in fact in the gray area where the state space is huge but the action space is just 4-dimensional. So this goes back to my previous points of scalability and comparison with existing algorithms like DQN.\n\nI believe using trees in MDPs is good alternative to DNN, particularly because of their interpretability. It would be great if authors could comment/explore this. Furthermore, algorithms like monte-carlo trees provide a more adaptive search to zoom into \"important\" regions.", "summary_of_the_paper": "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. \n\n", "summary_of_the_review": "Trees are a great function approximators and have been studied in MDPs before. \nRecent successful algorithms are based on deep neural nets but authors do not compare the two approaches in terms of their scalability, interpretability and/or theoretically. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "43TMjbM6Sy", "reviewer": "Reviewer_vkFy", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The insight that solving a partitioned MDP is an approximate solution to the full MDP is not particularly novel and is presented in [1] - which I think really should be referenced in the paper. The originality then rests on connecting decision trees to partitions of the state space (again something that has been noted before, but also the method for building up the partition which I do think has some originality in its focus.\n\nThis is a batch RL method when the state space becomes large (i.e. the grey region of Figure 1) as far as I can see, that is to say this is not a method that can be deployed online in the environment and learn as it goes, it needs to have seen data from somewhere else. This I don't think is made particularity clear in the paper and should be included in a discussion.\n\nThe experimental section of the paper is not at the level it needs to be, the method should be demonstrated on more than just a grid world environment and cart pole, both of which are extremely toy problems that are easily solved. Comparisons should also be made to existing works in the literature - of which there are obviously many.\n\nRealistically the benefits of having a decision tree structure for a policy is so that the policy is interpretable and can be inspected and communicated well. There's not really any need for this in either a grid world or cart pole - a medical example on the other hand where you extracted a decision tree policy of a clinician (treating sepsis is a common example) would be really interesting.\n\nFigure 1 is taking up far too much space for what it is demonstrating.\n\n[1] Kim, Kee-Eung, and Thomas Dean. \"Solving factored MDPs using non-homogeneous partitions.\" Artificial Intelligence 147.1-2 (2003): 225-251.\n\n----- Post rebuttal -----\n\nI thank the authors for their responses to my points, they make sense and I think including these explanations in the paper would aid in framing and justifying some of these decisions. Consequently I think slightly raising my score is fair, although I would still be hesitant to recommend acceptance without seeing a paper with a more thorough comparison to related work both textually and experimentally.", "summary_of_the_paper": "The paper essentially draws on the insight that representing a policy as a decision tree is essentially the same as partitioning the state space and solving a simplified MDP on this less coarse space, and they present a method for then learning this partition before demonstrating results on a simple grid world example and the traditional cart pole control problem.", "summary_of_the_review": "I do not think the paper is ready for publication in its present form although the method is potentially promising. An expanded discussion on related work is needed alongside a much more developed experimental section. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3tTqDd57HHq", "reviewer": "Reviewer_HjwV", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea is simple and the computational complexity analysis, though not surprising, is convincing. \nWhat is missing is an estimate of the efficacy of the decision tree approximation. In general greedy construction of decision trees is not optimal and it is a good approximation when some submodular property of the objective function can be assumed. The authors seem to completely ignore the issue of optimality. They talk about an approximation but, as far as I understand, unless I am missing something they do not consider whether the approximation is good or bad. \n ", "summary_of_the_paper": "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. \nThe 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. ", "summary_of_the_review": "I think that without some comment about the issue of how well the obtained decision tree based policy approximate the optimal LP based policy, the paper is weak. It present a nice but obvious explanation of why by coarsening the state space one can reduce the complexity of computing a good policy. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers identified missing comparisons to existing baselines (Deep RL and other tree-based RL methods) as well as simplistic experiments as the main limitations of the paper. While the authors could address some of the issues raised by the reviewers, the missing comparisons and too simple experiments remain. I therefore agree with (most of) the reviewers that the paper can not be published at its current state.
Decision: Reject