Progressive State Space Disaggregation for Infinite Horizon Dynamic Programming

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 20:38:43

Abstract: High dimensionality of model-based Reinforcement Learning and Markov Decision Processes can be reduced using abstractions of the state and action spaces. Although hierarchical learning and state abstraction methods have been explored over the past decades, explicit methods to build useful abstractions of models are rarely provided. In this work, we provide a new state abstraction method for solving infinite horizon problems in the discounted and total settings. Our approach is to progressively disaggregate abstract regions by iteratively slicing aggregations of states relatively to a value function. The distinguishing feature of our method, in contrast to previous approximations of the Bellman operator, is the disaggregation of regions during value function iterations (or policy evaluation steps). The objective is to find a more efficient aggregation that reduces the error on each piece of the partition. We provide a proof of convergence for this algorithm without making any assumptions about the structure of the problem. We also show that this process decreases the computational complexity of the Bellman operator iteration and provides useful abstractions. We then plug this state space disaggregation process in classical Dynamic Programming algorithm namely Approximate Value Iteration, Q-Value Iteration and Policy Iteration. Finally, we conduct a numerical comparison on randomly generated MDPs as well as classical MDPs. Those experiments show that our policy-based algorithm is faster than both traditional dynamic programming approach and recent aggregative methods that use a fixed number of adaptive partitions.

Main paper: 
 : 
 function. The distinguishing feature of our method, in contrast to previous approximations of the Bellman operator, is the disaggregation of regions during value function iterations (or policy evaluation steps). The objective is to find a more efficient aggregation that reduces the error on each piece of the partition. We provide a proof of convergence for this algorithm without making any assumptions about the structure of the problem. We also show that this process decreases the computational complexity of the Bellman operator iteration and provides useful abstractions. We then plug this state spaceThe Markov Decision Process (MDP) serves as a comprehensive framework for addressing stochastic dynamic control problems. Within this framework, the environment undergoes stochastic evolution influenced by the actions of an agent. The primary objective is to optimize expected gains through strategic decision-making (Puterman 2014) . The overarching objective is to identify the optimal sequence of actions, referred to as a policy, that maximizes the overall return. This pursuit extends to a diverse array of problem domains, as highlighted in a recent overview (Boucherie and Van Dijk 2017) . These encompass challenges in inventory control, energy management, network optimization involving queues, and navigating stochastic shortest paths in robot exploration. Achieving near-optimal control is crucial, necessitating precise solutions to effectively address these problems.The curse of dimensionality is a well-documented challenge in the Markov Decision Process (MDP) framework, particularly when dealing with large state spaces. To overcome this, various strategies decompose complex MDPs into more manageable counterparts. Notably, Factored MDPs (Guestrin et al. 2003) represent states as dynamic feature vectors, using Dynamic Bayesian Networks for compact representation and efficient computation. Another recent approach, Reduced-Rank MDPs (Siddiqi, Boots, and Gordon 2010) , expresses transition probabilities as scalar products of continuous functions, offering an effective dimensionality reduction technique. A general and promising method for MDP approximation is the Hierarchical Solution (Hengst 2012) , which considers either temporal abstractions for actions persisting over time (Sutton, Precup, and Singh 1999) , or state abstractions by aggregating states into meaningful regions (Li, Walsh, and Littman 2006) , enhancing efficiency in handling complex MDPs.In the context of state aggregation, the key challenge lies in determining the optimal grouping of different states and evaluating the quality of this aggregation. The selection of merging criteria becomes pivotal, and various criteria have been proposed in the literature. For instance, (Dean and Givan 1997) employs bisimulation for state grouping, (Singh, Jaakkola, and Jordan 1994) introduces a soft aggregation where states have probabilities of belonging to an aggregated region, (Ferrer-Mestres et al. 2020 ) restricts the number of regions, and (Abel, Hershkowitz, and Littman 2016) provides a compilation of several aggregation criteria. Assessing the quality of aggregation involves leveraging results from approximated dynamic programming and stochastic optimization, as discussed in (Tsitsiklis and Van Roy 1996) and further explored in (Abel, Hershkowitz, and Littman 2016; Abel 2019) .The incorporation of the aggregation process into solution algorithms, such as Modified Policy Iteration (MPI) or Value Iteration (VI), serves to enhance computational efficiency. In the realm of MPI, (Bertsekas, Castanon et al. 1988 ) employs aggregation based on the Bellman Residual to accelerate the process. More recently, (Chen et al. 2022) applies aggregation to VI by grouping states with similar values, demonstrating a contemporary approach to improving computational speed.We introduce a class of iterative aggregation algorithms for solving infinite horizon problems with both expected discounted and expected total criteria. Our approach integrates state abstraction with Approximate Value Iteration, Q-Value, and Policy Iteration algorithms. The iterative process begins by consolidating the entire state space into a single region. Subsequently, at each step, the current regions are subdivided based on the states' current values. The process concludes when each region groups states with similar values and when the current value function approximates the optimal one. A key innovation is the progressive aggregation along iteration steps, gathering states with similar evolution under the Bellman operator application. This refined state abstraction enhances algorithm efficiency. We provide a convergence proof without assumptions about the problem's structure, demonstrating decreased computational complexity and valuable abstractions. Numerical comparisons across diverse models underscore the algorithm's favorable standing in the Markov Decision Process literature, particularly in comparison to other abstraction algorithms.The structure of the article unfolds as follows: initially, we establish a connection between approximate Bellman operators with State Aggregation and the Bellman operator of the abstract MDP. Subsequently, we articulate an error bound for the optimal value function, contingent on the quality of the aggregation employed. Following this theoretical foundation, we introduce our algorithms. Lastly, we assess the efficacy of our method through benchmarking on classical models, showcasing its efficiency in comparison to alternative approaches.Our approach is grounded in Markov Decision Processes, a well-documented field. We clarify notations, outline Dynamic Programming methods for model resolution, and integrate recent advancements in State Abstraction and Approximate Dynamic Programming.Markov Decision Processes Markov Decision Processes provide a framework for decision-making optimization (Puterman 2014). Formally, a finite MDP is specified as a tuple ⟨S, A, T, R, γ⟩, where S is the set of possible states, A is the set of actions that the agent can select, T (s, a, s ′ ) ∈ [0, 1] is the environment transition probability from s to s ′ under action a and R (s, a) ∈ R describes the reward received by the agent in s triggering action a. Finally, we consider bounded rewards and a discount factor γ ∈ (0, 1] to weight the incoming reward priority.The objective is to maximize the expected sum of discounted immediate rewards in the upcoming trajectory of states for an infinite horizon. The researched solution is a deterministic policy π : S → A that can decide which action to select when in state s ∈ S. For a given policy π, it is thus possible to define the value function that gives a value to each state. It is defined as the expected return applying the policy π and we have ∀s ∈ S:V π (s) = E st+1∼T (st,at,•) ∞ t=0 γ t R (s t , π(s t )) |s 0 = s .The planning problem is centered on maximizing the expected return. In our setting, it exists a non necessarily unique policy π * such that V π * (s) = max π V π (s) simultaneoulsy for all states s. It is worth noting that the optimal 145 value function V π * (denoted as V * ) is the unique solution to the optimal Bellman EquationV (s) = max a∈A R (s, a) + γ s ′ ∈S T (s, a, s ′ ) • V (s ′ ) ,(1) for all s ∈ S (Puterman 2014) . Along this article, we denote by (T * V ) (s) the right term of Equation (1).Dynamic Programming Any value function can be com-150 puted recursively. Hence, for a given policy π ∈ A S , we consider here the Bellman OperatorT π : V ∈ R S → R π + γT π • V ∈ R S .with R π (s) = R (s, π(s)) and T π (s, s ′ ) = T (s, π(s), s ′ ). This Bellman operator updates any value function V relatively to the reward an transition functions. It contracts the 155 function space and its iteration can lead to a value function solution of the Bellman equation V = T π V .One also considers the optimal Bellman Operator T * defined by Equation (1).So far, we have considered the state value function V , but 160 a similar analysis can be conducted for the state-action value function Q defined byQ π (s, a) = E (st,at)t ∞ t=0 γ t R (s t , π(s t )) |s 0 = s, a 0 = a .The optimal Bellman Operator in the Q-value case exists and is defined asT * Q : Q ∈ R S×A → R + γT • max a∈A (Q) ∈ R S×A .The practical solving of a MDP, can be done either by 165 maximizing the expected return V π for any state or by minimizing the Bellman residual namely ∥V -T * V ∥ ∞ . The Dynamic Programming methods generally aim to decrease the Bellman residual. In Value Iteration algorithm (respectively Q-Value Iteration), one iterates the contracting op-170 timal Bellman operator to approximate the fixed point solution of the optimal Bellman equation 2014) . In Policy Iteration algorithm that alternate between finding the solution to V = T π V and updating the current policy π according toEQUATION175 π t+1 (s) ← arg max a∈A R (s, a) + γ s ′ ∈S T (s, a, s ′ ) V πt (s ′ ) .The concept of constructing a new MDP through state aggregation has been explored in the literature, particularly in the examination of abstract MDPs (Li, Walsh, and Littman 2006) . This involves considering a ground MDP, denoted as M G = ⟨S, A, T, R, γ⟩, 180 and creating a new abstract MDP, denoted as M A = ⟨S A , A, T A , R A , γ⟩, from it. We first define State Aggregation.Definition 1 (State aggregation). Let M G an MDP and S = K k=1 S k a partition of the state space. Let assume we give a weight ω k (s) to each state of a region S k relatively to the other states of this region S k . The weights ω k are positive and sum to 1 on each region. Moreover, if s / ∈ S k , ω k (s) = 0. We finally store the weights into a matrix ω ∈ [0, 1] K×|S| and the state-region correspondence in a matrix ϕ such that ϕ[s, k] = 1 s∈S k . It is now possible to define a state aggregation by the tuple ((S k ) k , ϕ, ω).When all states of a region are equally weighted, ω can be computed as follows: Bertsekas, Castanon et al. 1988) ω k (s) = 1 |S k | which corresponds to ω = ϕ T • ϕ -1 • ϕ T (S A = {s k , 1 ≤ k ≤ K}, A A = A, T A = ω • T • ϕ and R A = ω • R.The interest of State Abstraction is therefore to reduce the size of the original MDP gathering state with similar properties like a close optimal value, a close optimal policy or a close optimal Q-value (Abel, Hershkowitz, and Littman 2016) . It can be used to approximate the ground optimal policy but also to highlight a structure in the ground MDP.Programming involves applying an operator to enhance the current solution, Approximate Dynamic Programming focuses on updating an approximated version of the value function (Powell 2007) . In our context, we adopt the linear parameterizationV θ (s) = K k=1 θ k 1 s∈S k ,with (S k ) k a state aggregation. Those value function are constant over each region S k . The approximate Bellman operator relative to this family of functions (denoted ΠT * ) is made of the optimal Bellman operator and a projection matrix Π that averages the value on each region to obtain a piecewise constant value function.Definition 3 (Projected optimal Bellman operator (Tsitsiklis and Van Roy 1996)). Let note P the set of value function that are piecewise constant relatively to (S k ) k . Then, the operator ΠT * that checks∀V ∈ R S , ΠT * ∈ arg min T ∈P ∥T V -T * V ∥ 2is the projected optimal Bellman Operator ΠT * = ϕ • ω • T * where ϕ and ω are described in Definition 1 of a state aggregation.In the following sections, we will consider each of the projected Bellman Operators ΠT * , ΠT * Q and ΠT π for any policy π with Π = ϕ • ω.In what follows, we describe the relationship between the 235 projected Bellman operators and State Abstraction. We first prove that a projected Bellman operator is exactly the Bellman operator of a smaller abstract MDP. As we want to implement those operators, we evaluate theirs complexity and compare it to the optimal Bellman operator T * .Projected Bellman Equations and abstract MDP We are now interested in the unique solution of each of the equationsQ = ΠT * Q Q and V = ΠT π V .We will namely prove that those projected equations are Bellman equations for the associated abstract MDP. Let us note that it does not gener-245 alize to the equation V = ΠT * V . Indeed, as Q and V π contains action information through Q and π, any value function solution to Ṽ = ΠT Ṽ is not necessarily associated with a piecewise constant policy. The solution of V = ΠT * V is therefore not necessarily the optimal value function of the 250 abstract MDP.It is now interesting to note that the functions solution to these equations Q = ΠT * Q Q and V = ΠT π V are piecewise constant. Indeed, the operator Π make the function being constant over the regions (S k ) k . We are therefore adopting 255 the following notations. Let Ṽ a piecewise constant value function relatively to a partition (S k ) k . The entries of Ṽ are in a way redundant : for any state s ∈ S k , Ṽ (s) has the same value. We therefore build a contracted representation V ∈ R K which contains a single value for each region: 260 ∀s ∈ S k , Ṽ (s) = V(k). This new value function V can be a value function to the associated abstract MDP. Moreover, it is possible to switch between Ṽ and V using the relations Ṽ = ϕ•V and V = ω• Ṽ . We use similar notation concerning the Q-value using Q and Q.In the following proposition, we suggest that the solution toQ = ΠT * Q Q is also the optimal Q-value function of the abstract MDP. Proposition 1. Let ((S k ) k , ϕ, ω) be an aggregation of the state space. Let Q = ϕ • Q be the unique solution to the 270 Q-projected optimal Bellman equation Q = ΠT * Q Q. Then Q is the optimal Q-value function of the abstract MDP M A described in Definition 2.The proof simply consists in establishing that the equationQ = ΠT * Q Q can be written as the optimal Bellman equation 275 Q = T * Q Q for the abstract MDP. Proof. Let Q = ϕ•Q the unique solution to Q = ΠT * Q Q. Let Q *A the optimal Q-value of the abstract MDP M A . Let show that those Q-value are the solution to the same equation. Theequation Q = ΠT * Q Q can be written : 280 Q = ΠT * Q Q ⇐⇒ ϕ • Q = ϕ • ω • T * Q (ϕ • Q) ⇐⇒ Q = ω • T * Q (ϕ • Q) ⇐⇒ Q = ω • R + γω • T • ϕ • max a∈A (Q) ⇐⇒ Q = R A + γT A • max a∈A (Q) .which is precisely the optimal Bellman equation for the abstract MDP M A . As the solution to each of the equation is unique, we can conclude that Q = Q * A .As in (Abel, Hershkowitz, and Littman 2016) , we focus here on π A an arbitrary policy on the abstract state space S A .We define its generalization π G to the ground state space S, by the piecewise constant policy given by:π(s) = π A (s k ) , ∀s ∈ S k , ∀k ∈ 1 ; K .Proposition 1 has an equivalent for the T π operator. Hence in Proposition 2, we state that the value of any abstract policy Ṽ π A is the solution of a projected Bellman equation290 Ṽ π A = ΠT π A Ṽ π A at the ground level.Proposition 2. Let ((S k ) k , ϕ, ω) an aggregation of the state space. Let π A : S A → A an arbitrary policy and π G : S → A its generalization to the ground state space S. Then, the value of this policy on the abstract MDP V π A is the solution 295 of the following projected Bellman equationϕ • V π A = ΠT π G (ϕ • V π A ) .The proof still relies on the unicity of the solution of a fixed-point equality.Proof. In the following, we prove the equivalence of the equations300 Ṽ = ΠT π G Ṽ and V = T π A Vwhich suffices to conclude on the proposition.Ṽ = ΠT π G Ṽ ⇐⇒ ϕ • V = ΠT π G (ϕ • V) ⇐⇒ ϕ • V = ϕ • ω • (R π G + γ • T π G • ϕ • V) ⇐⇒ V = ω • R π G + γ • ω • T π G • ϕ • V ⇐⇒ V = R π A A + γ • T π A A V ⇐⇒ V = T π A VThose equivalences imply the wanted equality and therefore on the property.As we proved here that the solution of projected Bellman equation if the optimal value function of an abstract MDP, we now study the complexity of iterating a projected Bellman Operator.In this part, we prove the convergence of any sequence of value functions (or Q value function) on which we iterate any projected 310 Bellman Operator.Proposition 3. 1. Let Q 0 ∈ R S×A be an arbitrary Q-value function and let the iterationQ t+1 ← ΠT * Q Q t .Then the series (Q t ) t∈N converges to the unique solution to the projected optimal Bellman equation Q = ΠT * Q Q.2. Let π ∈ A S be an arbitrary policy. Let V 0 ∈ R S any value function, and let the iteration V t+1 ← ΠT π V t . Then (V t ) converges to the unique solution to the projected Bellman equation V = ΠT π V.In (Bertsekas 2018 ) was established the contraction property of the operator ΠT * . We generalize it to ΠT * Q and ΠT π for any policy π to prove Proposition 3. Proposition 4. The operators ΠT * Q and ΠT π for any policy π are contracting.Proof. The proof relies on the contraction induced by the Bellman operator and on the following inequality true for anyT ∈ {T * Q , T π }: ∥ϕ • ω • (T V -T V ′ ) ∥ ∞ ≤ ∥T V -T V ′ ∥ ∞as ϕ simply repeat the entries in any vector V ∈ R S . This property can be applied to ΠT * Q and ΠT π for any policy π to conclude the proof.From now on, iterating any of the operator T * , ΠT * , ΠT * Q or ΠT π makes any value function converge to a unique piecewise constant final value function. In the following, we will be interested in the complexity of the computation of the solution of the projected Bellman equation and will propose a bound on the error to the optimal value function depending on the specific aggregation and on the current value.Projected Operators complexity Now, we will consider the complexity of computing the projected Bellman operators ΠT * , ΠT * Q and ΠT π G for any piecewise constant policy π G . Proposition 5. The complexity of the computation of the projected Bellman operators ΠT * Q and ΠT π G for any piecewise constant policy π G are respectively O(K 3 |A|) and O(K 3 ).Q and ΠT π G can be viewed as the Bellman operators T * Q and T π A , then theirs complexity can be computed from the abstract MDP point of view. We therefore deduce their complexity from the matrix computationsT * Q (Q) = R A + γ • T A • max a∈A (Q) and T π A (V) = R π A A + γ • T π A A • V knowing that the complexity of the product M • N , with M ∈ R l×m , and N ∈ R m×n is equal to l • m • n.From now, we consider the computation complexity of the projected optimal Bellman operator ΠT * assuming we will iterate it. Proposition 6. For any piecewise constant value function Ṽ , the number of operations to computeΠT * Ṽ is O(|S| 2 K |A|). Proof. Considering ΠT * (ϕ • V) = ϕ • ω max a∈A (R + γ • T • ϕ • V)the precomputation of the matrix product same value function) and the projected Bellman residual Ṽ -ΠT Ṽ but does not use the optimal value function.We then provide the Progressive Disaggregation algorithm which is based on this bound : we iteratively improve the aggregation quality (reducing one term of the bound of theorem 1) and decrease the projected Bellman residual by applying the projected Bellman operator.Theorem 1 (optimal Error Bound with arbitrary partition).Let any piecewise constant value function Ṽ ∈ R S . Its distance to the optimal value function V * can be bounded as 385 follows:EQUATIONwhere Span S k (V ) := max s∈S k V (s) -min s∈S k V (s).Proof. We mainly use the classical inequality:∀ V ∈ R S , ∥V -V * ∥ ∞ ≤ 1 1 -γ ∥V -T * V ∥ ∞and also the following one:∀V ∈ R S , ∥V -ΠV ∥ ∞ ≤ max 1≤k≤K Span S k (V ) .Concatenating inequalities, we get:390 ∥V * -Ṽ ∥ ∞ ≤ 1 1 -γ ∥ Ṽ -T * Ṽ ∥ ∞ ≤ 1 1 -γ ∥ΠT * Ṽ -T * Ṽ ∥ ∞ + ∥ Ṽ -ΠT * Ṽ ∥ ∞ ≤ 1 1 -γ max 1≤k≤K Span S k T * Ṽ + ∥ Ṽ -ΠT * Ṽ ∥ ∞We furthermore note that max 1≤k≤K Span S k T * Ṽ measures how much the aggregation groups states having the same value and that ∥ Ṽ -ΠT * Ṽ ∥ ∞ estimates the optimality of the current piecewise value function relatively to the projected Bellman operator.Corollary 1. Inequality 2 can also be formulated using ΠT * Q and ΠT π G for any piecewise constant policy π G .We therefore propose an algorithm with initialization Ṽ0 = (0) s∈S and a unique region S 0 = {S}. We then iterate the two following steps successively:• Apply ΠT * until ∥ Ṽ -ΠT * Ṽ ∥ ∞ is smaller than ϵ • Compute T * V t . Divide each region until max s∈S k V t+1 -min s∈S k V t+1 is smaller than ϵ for each region k ∈ 1 ; K .When applying this process, we separate states having different trajectories through value iteration. Moreover note that the ΠT * operator changes at each region division step. The goal is also to take advantage of the time savings from the projected Bellman operator application compared to the optimal ground one.In this section, we provide the pseudocode for the algorithm that we described previously. We precise its adaptation to Qvalue iteration and Modified Policy Iteration. We then prove the convergence of the algorithm and lead a complexity analysis to conclude on its performance condition.Formulation In Algorithm 1, we describe the Progressive Disaggregation Value Iteration (PDVI) process. It can be summarized into while the bound of the Theorem 1 is not lower than ϵ, then alternate between dividing heterogeneous regions and updating the piecewise constant value function Ṽ . We managed to make the region division to have a O(|S|) complexity. This allows to profit from piecewise constant update savings.Algorithm 1: Progressive Disaggregation Value Iteration Input: M = ⟨S, A, T, R, γ⟩, ϵ > 0 Output: A value V , an aggregation (S k ) k of the state space 1: K := 1, S 1 := S, V 0 := (0) 1≤k≤K 2: while∥V t -ΠT * V t ∥ ∞ + max 1≤k≤K Span S k (T * V t ) > 2ϵ do 3: V t+1 := T * (ϕ • V t ) 4: if max 1≤k≤K Span S k (V t+1 ) > ϵ then 5: (S k ) k = UpdateRegion(k, V k , (S k ) k , ϵ) 6: end if 7: while ∥V t -ΠT * V t ∥ ∞ > ϵ do 8: V t+1 ← ΠT * V t 9:end while 10: end while11: return (V, (S k ) k ) Algorithm 2: UpdateRegions Input: V , (S k ) k , ϵ Output: Updated partition {S ′ k } 1: for l ∈ 1 ; K do 2: if max s∈S l V -min s∈S l V > ϵ then 3: (S k ) k = (S k ) k \S l 4: for p ∈ 0 ; ⌈ 1 ϵ (max V |S l -min V |S l )⌉ do 5: I p := min V |S l + p.ϵ, min V |S l + (p + 1).ϵ 6: S p := {s ∈ S l , V (s) ∈ I p } 7: if S p ̸ = ∅ then 8: (S k ) k := (S k ) k ⊔ S 9:end if 10:end for 11:end if 12: end for 13: return Updated partition {S k } As this algorithm consists in iterating ΠT * and dividing regions along T * V , we generalize it to the Q-value process by applying ΠT * Q and divide the regions along T * Q Q. We name this new algorithm Progressive Disaggregation Q-Value Iteration (PDQVI). In the region division step, we ensure maxs∈S k ,a∈A Q -min s∈S k ,a∈A Q ≤ ϵ.Moreover, PDQVI provide a state abstraction gathering states with close optimal Q-value Q * . We also propose a Modified Policy Iteration-type algorithm named Progressive Disaggregation Policy Iteration 435 (PDPI). In Modified Policy Iteration, we start from an arbitrary given policy. We then iteratively evaluate its value function V π (solution of V π = T π V π ) and update the policy using V π . In PDPI, we changed the Policy Evaluation part into a disaggregation process, progressively dividing regions and evaluating the solution of V = ΠT π V at the same time.Convergence property In this part, we state a guarantee of convergence for PDVI, PDQVI and PDPI and characterize the aggregation provided by the algorithms.Proposition 7 (Convergence guarantee for PDVI). Algorithm 1 finishes in a finite number of steps. Let (V, (S k ) k ) be the value and the abstraction returned. Then :∥ϕ • V -V * ∥ ∞ ≤ 2ϵ 1 -γwhere the precision ϵ is an input of the algorithm. Moreover, for all k ∈ 1 ; K , for all s, s ′ ∈ S k , we have|V * (s) -V * (s ′ )| ≤ 4ϵ 1 -γ .We stated here that PDVI converges with an accuracy similar to Value Iteration and aggregates states having close optimal value.Proof. At first, let prove that Algorithm 1 stops within |S| + 1 steps by contradiction. Let assume that455 ∥V t -ΠT * V t ∥ ∞ + max 1≤k≤K Span S k (T * V t ) > 2ϵafter |S|+2 steps. As at the end of each step t ∈ 0 ; |S|+2 , ∥V t -ΠT * V t ∥ ∞ ≤ ϵ (due to the lines 7-9 condition), then it follows that max 1≤k≤K Span S k (T * V t ) > ϵ as the while condition is not fulfilled. We therefore deduce that for each of the steps t ∈ 1 ; |S| + 1 , a disaggregation step has occured. Given that for each disaggregation step, the number of region strictly increases, we deduce that at step t = |S| + 1, the state aggregation is made of |S| + 1 regions. This can not occur. So, the final precision condition∥ϕ • V -V * ∥ ∞ ≤ 2ϵ 1 -γis then ensured by the while loop condition combined with Theorem 1.Finally, let us show that the regions (S k ) k group states having close optimal value. Let k ∈ 1 ; K any region and s, s ′ ∈ S k . We observe that∥V * (s) -V * (s ′ )∥ ∞ ≤ ∥V * (s) -Ṽ (s)∥ ∞ + ∥ Ṽ (s) -V * (s ′ )∥ ∞ = ∥V * (s) -Ṽ (s)∥ ∞ + ∥ Ṽ (s ′ ) -V * (s ′ )∥ ∞ ≤ 4ϵ 1 -γ .The equality comes from Ṽ (s) = Ṽ (s ′ ) as s and s ′ are in the same region. The last inequality can be stated using the final precision of the algorithm.We also mention that PDQVI aggregates states having close optimal Q-value Q * and PDPI also groups states having same optimal value V * . Both converge and provide optimal Q-value and optimal policies following the same steps for the proof. We add that the proof of the policy-based disaggregation algorithm convergence contains some subtility, especially when it is necessary to keep the value function V π from one policy evaluation to the next one. We finally state that PDQVI and PDPI still converge in the expected totalreward criterion γ = 1. This convergence result can only be checked with the assumption R ≥ 0 as we use the convergence properties of Value Iteration and Policy Iteration in the expected total-reward case (Puterman 2014) .We provide here a complexity analysis for PDVI, PDQVI and PDPI and see that the worst-case complexity of those algorithms can be higher than the traditional ones. This characterization will also explain why our disaggregation method can be outperformed by traditional ones on some specific models that we identify. Hence, to prove the bounds that we exhibit, one consider an instance of chained states inspired from the Four Room model described in (Hengst 2012) .Proposition 8 (Disaggregation algorithm complexity). Let assume that any Value Iteration-like algorithm takes n steps to reach an ϵ-close optimal value. To reach an ϵ-optimal value function, our algorithms require the following number of operations.Let consider the execution of |S| iterations of the ΠT * operator. According to the Proposition 6, each iteration of ΠT * takes O(K |S| 2 |A|) operations. We assume it takes n operations to approximate the solution of the projected optimal Bellman equation Ṽ = ΠT * Ṽ with an accuracy ϵ. The state s 1 is considered as an exit state and is therefore absorbing. Concerning the reward, each action made in a state different from the exit generates a -1 reward. Dean, and Kaelbling 1995) . We obviously lose in complexity during disaggregation in some specific cases that we detailed here.s 1 s 2 s 3 R = -1 R = -1 R = -1 R = 0 R = -1Nevertheless we claim (based on numerical experiments performed later) that these worst-case bounds are not reached in practice and that the average complexity of our algorithm is much better.We conducted a benchmark of our solving methods on three scalable models. To run this benchmark, we implemented several solvers. We compared PDVI, PDQVI and PDPI to usual Value Iteration, Modified Policy Iteration, as well as Bertsekas Adaptive Aggregation (Bertsekas, Castanon et al. 1988) and Chen Adaptive Aggregation (Chen et al. 2022). Our comparison with a diverse set of solving methods show that our disaggregation algorithms outperforms other methods on most of the models.We selected configurable models with variable state space and action space sizes. We evaluated MDPs on a randomly generated transition matrix, a toy model (four rooms), and a real-life problem. The Random MDPs are commonly used in the literature to benchmark solvers (Archibald, McKinnon, and Thomas 1995; Bhatnagar et al. 2009) . The Four Rooms model is a stochastic shortest path model (Hengst 2012; Sutton and Barto 2018) that we scaled to explore the state space size impact. Finally, we faced a real-life queue management situation with scalable servers and queue sizes (Ohno and Ichiki 1987; Tournaire et al. 2022 ) already used for benchmark in (Puterman 2014) .We ran the solving process on one thread of a CPU Intel Xeon Gold 6154 @ 3.00GHz. The code has been written in Python using numpy and scipy libraries to encode sparse matrices and the experiment used at most 16GB of RAM. Chen Adaptive Aggregation method was far behind the other value-based method up to a factor 2, we therefore decided to only keep other methods in the following results.Random models Our slicing strategy gave its best on random models. We drew random distributions T (s, a, .) on S for any (s, a) ∈ S × A. We also build R with random coefficients in [0, 1]. We set |S| = 500 and |A| = 50 and a variable proportion of nonzero entries (named density) in the transition matrix. As the density of the transition matrix impacted the most the optimal value function shape, we set a maximum of diversity in this parameter going from 1% (almost empty matrix) to 65% (two over three pairs of state are connected by a nonzero transition) of nonzero entries.As shown in Table 1 , Progressive Disaggregation methods demonstrate their advantages for both value and policybased approaches, aligning with the theoretical analysis in the previous section. Indeed, small densities of T induce independent states while higher densities of T smooth the optimal value functions.Real model We considered a Tandem Queue situation inspired from a real-world server operation (Ohno and Ichiki 1987) . Here, the agent manages to scale several servers relatively to the load of a system made of two tandem queues with parallel servers. To this end, it is possible to activate or deactivate servers. There are 3 actions (add, keep or remove a server) for each queue which gives 9 actions in total. We could scale here the size of the queue and the size of the server to adjust the state space dimension. We present the results for |S| ∈ {8100, 12544}. According to common hypothesis in this domain, we chose a queue size (15 and 16) greater than the server size (6 and 7) (Tournaire et al. 2022 We finally considered the well-known grid model four rooms (Hengst 2012 ). This model is made of four rooms set out in square (5 × 5 states for each room) with doors connecting pairs of rooms. As a stochastic shortest path model, the goal is to reach the exit (a given state of the grid) and each action in (N , S, E, W ) leads to the next close state with a probability .8 (if there is no wall in this direction), otherwise we stay in place. To adapt it into a discounted model, the agent restarts at the beginning when reaching the exit. We scaled the model to greater room sizes in order to make it more complex. The model is therefore 615 very sparse: 2. |S| . |A| coefficient are non-zero in the transition matrix of size |S| 2 . |A| which implies a sparsity of at least 98% for our instance. The slicing algorithm performs better and better as the state space dimension increases for the policy-based version.In this experiment, we increased the discount factor up to 0.999 and the final precision to 10 -3 so that the valuebased methods struggle a bit more and are outperformed by policy-based ones. The results are shown in Table 3 . Note that, the partition found by our method gathers states which 625 are equidistant from the exit.Solving and approaching the exact MDP solution remain questions that deeply depend on the problem structure. In this context, we present an approximation method that combines State Abstraction and aggregation methods to accelerate traditional dynamic programming algorithms.We focused on three main aspects. Initially, we established a robust connection between the projected Bellman operator and the abstract MDP's Bellman operator, extending it to the Q-value case and introducing a policy-based version. Following that, we presented a bound on the distance to the optimal value function based on a given state abstraction, leading to a progressive disaggregation process to refine state partitions. Our algorithm tests demonstrated the effectiveness of this approach, particularly in solving MDPs with dense transition matrices. Compared to Modified Policy Iteration and other Adaptive Aggregation methods, the policy-based approach significantly outperformed in solving realistic MDP instances with well-known models.Our approach could benefit from further testing on MDP instances. Additionally, algorithmic enhancements could be introduced to switch to traditional dynamic programming methods when the partition proves inefficient. As disaggregation methods faces challenges primarily in cases close to the shortest path problem, it is crucial to tailor our approach to be more specific to this type of problem. Taking inspiration from the approximation of Tsitsiklis and Castañon, this method could also be combined with progressive disaggregation process. Future work should also investigate generalizations to the model-free Reinforcement Learning problem, incorporating not only state grouping but also the approximation of the state space using Deep Learning methods. 
 
 Appendix:  


Decision: In this paper, the authors work on the "classical" (i.e. non DL-based) methods for solving MDPs. The contributions are sound and interesting to the ICAPS community. The main issue with this paper is that the author did not fully position their work w.r.t. prior work on DP for RL that also used state aggregation techniques. If the paper is accepted I urge the authors to include a more complete discussion of this related work in their paper.

We appreciate your rebuttal responses!

Reviews: review: strength_weakness: strength_weakness: - The comparison between the proposed Progressive Disaggregation methods and the state-of-the-art Adaptive Aggregation methods (i.e., Bertsekas Adaptive Aggregation and Chen Adaptive Aggregation) should be made more explicit to allow the reader to better and simply understand what is the methodological difference that allows Progressive Disaggregation to achieve a performance improvement. This comparison could be put in a specific section or in a related work section.
- The related work section is missing, I suggest introducing it and using it to show the differences between SOTA methods and the proposed method. This would allow the reader to better understand which is the original contribution of the paper, which is currently not stressed enough, from my point of view.
- The contribution seems original but the literature cited in the paper is not recent, hence the topic seems not to be very hot. The only recent work cited is (Chen et al. 2022), a workshop paper presenting an Adaptive State Aggregation Algorithm for Markov Decision Processes to which the proposed method has been compared.
- In analyzing the literature, maybe authors could also consider point-based policy iteration and value iteration methods (and related literature). They have been introduced in the context of POMDPs but I think the goal is similar and a comparison could be interesting. Furthermore, this analysis could allow the authors to extend the bibliography which is at the moment quite short (and it considers not very recent works).
- Since the recent literature about RL for high dimensionality environments is very focussed on model-free methods and model-based methods that learn the model, I think this work should make more explicity the relationship with that part of the literature to better explain the positioning compared to the rest of the literature. I think this would strenghten the paper and make it more interesting also for researchers working with recent model-free and model-based RL methods.  
- As in the previous point, I suggest making explicit the relationship between the proposed work and model-approximation/policy-approximation/policy-gradient/DRL methods. Why and when should a reader use the proposed approach instead of recent/popular RL methods on high-dimensionality domains?
- Again, a comparison between this approach and online approaches, such as Monte Carlo Tree Search based methods should be considered. Why and when should a reader use the proposed approach instead MCTS-based RL methods on high-dimensionality domains?
- It would be nice to make available the code to guarantee reproducibility
questions: questions: See section "Weaknesses Of The Paper".
strength_weakness: strength_weakness: IMHO the main weakness is that no code is provided or promised.

I would also have been curious to see more of the algorithms' behavior, e.g., which value of $K$ is reached, in how many iterations, ... But there is not much space left.


The following is a list of small comments or issues, but not serious weaknesses:

- [Title] The authors may want to add a line break before "for" to better balance the title.

[39]
- "Van Dijk" -> "van Dijk"

[67]
<- "(Dean and Givan 1997) employs" (A parenthesis cannot act as a subject.)
-> "Dean and Givan (1997) employ"

[68]
<- "(Singh, Jaakkola, and Jordan 1994) introduces"
-> "Singh, Jaakkola, and Jordan (1994) introduce"
   [I don't list other issues of this type.]

[155]
<- "to the reward an transition"
-> "to the reward and transition"

[157]
<- ".One"
-> ". One"

[165]
<- "The practical solving of a MDP, can [...]"
-> "The practical solving of an MDP can [...]"

[173-174] Where are the subject and verb of this sentence?

- I find using "let" without "us" or "me" quite unusual. But maybe that's valid.
  I am more worried about the cases where there is no verb following "let". For instance, I would add "be" in several cases.

- The authors may want to make it clear whether their abstract MDP (derived from a state aggregation) is different from previous work.
  Among other things, this would help me understand if pathologies may happen as described by Tagorti et al. ( https://inria.hal.science/hal-00907315/ ).


[217]
<- "Those value function are"
-> "Those value functions are"

- Definition 3: $\cal T$ should not be in $\cal T$. That's an operator, not a value function.

[239+347]
<- "theirs complexity"
-> "their complexity"
or "their complexities" ??

[247]
<- "contains"
-> "contain"

[279]
<- "those $Q$-value"
-> "those $Q$-values"
  
[305]
<- "if the optimal"
-> "is the optimal"

[380]
<- "of theorem 1"
-> "of Theorem 1"

[Proof of Theorem 1] It would be nice to point out references about these two "classical inequalities".

[432]
<- "PDQVI provide"
-> "PDQVI provides"

- Formulas after line 469: The infinite norms should be replaced by absolute values.

[493]
<- "one consider"
-> "one considers"

[507]
<- "the Proposition 6"
-> "Proposition 6"

[516]
<- "the Figure 1"
-> "Figure 1"

[528]
<- "are necessary"
-> "is necessary"

[531]
<- "Value Iteration algorithm"
-> "the Value Iteration algorithm"

<- "Bertsekas Adaptive Aggregation"
-> "Bertsekas' Adaptive Aggregation"

<- "Chen Adaptive Aggregation"
-> "Chen's Adaptive Aggregation"

[591]
<- "for each queue which [...]"
-> "for each queue, which [...]"

[616]
<- "coefficient"
-> "coefficients"

[617]
<- "which implies"
-> ", which implies"

[625]
<- "Note that, the partition [...]"
-> "Note that the partition [...]"

[650]
<- "As disaggregation methods faces [...]"
-> "As disaggregation methods face [...]"

[References]
- Please protect capital letters in title when needed, e.g., for "Markov" or "MDP", but don't protect all capital letters either (e.g., line 700).
questions: questions: 1. Is the abstract MDP derived from a state aggregation different from previous work? (e.g., from Abel et al.)

2. Definition 3: Do you confirm that $\cal T$ should not be in $\cal T$?

3. In PDPI, is the aggregation process restarted from scratch after each new policy improvement?
strength_weakness: strength_weakness: - Unclear about novelty and relationship to literature.

The study of state aggregation techniques for DP spans decades and I am still unclear what exactly are the novelties of this approach. In particular, the paper really lacks a more comprehensive analysis of existing methods and how they relate to their proposed policy and value iteration, as all concepts (include the projection) do closely relate to existing work. For example, the paper shares some relationship with some recent stream of state abstraction and options, aggregate-disaggregate methods, and even more classical literature on DPs such as the seminal work by Bean et al. (1987):

- Ciosek, Kamil, and David Silver. "Value iteration with options and state aggregation." arXiv preprint arXiv:1501.03959 (2015).
- Abel, David, et al. "Value preserving state-action abstractions." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.
- Bean, James C., John R. Birge, and Robert L. Smith. "Aggregation in dynamic programming." Operations Research 35.2 (1987): 215-220.
- Schweitzer, Paul J., Martin L. Puterman, and Kyle W. Kindle. "Iterative aggregation-disaggregation procedures for discounted semi-Markov reward processes." Operations Research 33.3 (1985): 589-605.

These are just a few examples. Even the work by Chen et al. 2022, while cited, has not been developed further in the text to establish its relationship with the proposed method. 



* Minor note: 
- The text is well written but several letters are not capitalized correctly throughout; e.g., optimal Error Bound --> Optimal.
questions: questions: Please kindly clarify the connection with the existing work.