Skill-Driven Neurosymbolic State Abstractions
Authors: Alper Ahmetoglu
Steven James
Cameron Allen
Sam Lobel
David Abel
George Konidaris
Venue: NeurIPS 2025 poster ()
Keywords: state abstraction
reinforcement learning
Primary area: reinforcement_learning

Abstract: We consider how to construct state abstractions compatible with a given set of abstract actions, to obtain a well-formed abstract Markov decision process (MDP). We show that the Bellman equation suggests that abstract states should represent distributions over states in the ground MDP; we characterize the conditions under which the resulting process is Markov and approximately model-preserving, derive algorithms for constructing and planning with the abstract MDP, and apply them to a visual maze task. We generalize these results to the factored actions case, characterizing the conditions that result in factored abstract states and apply the resulting algorithm to Montezuma's Revenge. These results provide a powerful and principled framework for constructing neurosymbolic abstract Markov decision processes.

Skill-Driven Neurosymbolic State Abstractions
Alper Ahmetoglu" Brown University
Steven James University of the Witwatersrand
Cameron Allen UC Berkeley
Sam Lobel
David Abel University of Edinburgh
George Konidaris Brown University
Brown University
Abstract
We consider how construct state abstractions compatible with given of abstract actions, to obtain a well-formed abstract Markov decision process (MDP). We show that the Bellman equation suggests that abstract states should represent distributions over states in the ground MDP; we characterize the conditions under which the resulting process is Markov and approximately model-preserving, derive an algorithm for constructing the abstract MDP, and apply it to visual chain and maze tasks. We generalize these results to the factored actions case, characterize the conditions that lead to factored abstract states, and apply the resulting algorithm to a visual grid and Montezuma's Revenge. These results provide principled, powerful framework for learning neurosymbolic abstract Markov decision processes.
Introduction
[62] has achieved remarkable success solving tasks with complex However, learning and planning the pixel and motor level, while necessary, must eventually be insufficient: the complexity of real-world tasks such cooking meal, inter-city travel, and fixing a car is such that they can only be feasible decision-makinn makiinn occurs at an abstract level and the low-level details are abstracted away. This is especially true when a single agent must perform all these tasks, necessitating a sensorimotor space complex enough to cover all of them. Linking abstract reasoning to low-level action and perception, to enable fast decision-mait makinng grounded real sensorimotor interaction, therefore critical for general intelligence 22 38
Reinforcement learning (RL)
sensorimotor spaces 48 43
Hicrarchical RL (HRL) [14] addresses this problem via high-level abstract actions, but does not create correspondingly abstract states, leaving the agent in its original low-level state space. would be far preferable to combine both types of abstractions to construct an entirely abstract decision process [8) which requires mutually compatible state and action abstractions: those that result in new, more compact decision process that is Markov and supports near-optimal policies over the abstract actions in the original MDP. Following earlier work in robotics [4), we adopt an action-first strategy, constructing state abstractions compatible with a pre-existing set of abstract actions.
We first focus building abstract MDP from ground MDP augmented with given set of abstract actions, where the Bellman equation suggests that abstract states should represent distributions over ground states. We use this insight to build an abstract decision process, and identify the conditions under which it is Markov and approximately model-preserving [44] I We develop algorithms for constructing the abstraction from data and for planning with and apply them visual chainwalk and maze tasks. We then generalize these results to factored actions, which modify only some state variables in the ground MDP. We characterize the conditions under which this generates factored
"Correspondence to Alper Ahmetoglu aahmetogecs. brown. edu and George Konidaris gdkkbrown edu. Extended results are available at mlnersyymblllc--eo mdps git.bb.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

abstract states, provide an algorithm that constructs the corresponding abstraction, and apply it to visual gridworld and Montezuma's Revenge, long-horizon Atari task [T]] These results provide a powerful and principled framework for learning neurosymbolic abstract decision processes.
2 Background
RL problems are typically formalized as Markov decision processes (MDPs) 62 given by tuple M = (S, A. R. 7), where S is a set of states; A is set of actions, with A(s) A denoting the actions available at state s; R(s, a, s') is the reward received when executing action a E A(s) in state s and transitioning to state s T's'|s, a) is the probability of entering state s' upon execution action a in state s; and E [0. 1J is a discount factor. A decision process is Markov when: 1) State s is sufficient for determining which actions are executable; i.e., A(s) is only a function of s. 2) State and action a are sufficient for determining the probability of transitioning to state s'; i.e., the distribution [ss' [s. a) is conditionally independent of all other variables. 3) State s, action a, and successive state s' determine reward, so R(s, a, 8') depends on no other variables. The state space of a task must therefore support Markov reward (R), transition (7), and available action (A) functions.
We focus on the multi-task RL setting where the agent must solve several MDPs drawn from a task distribution. We model this as fixed ground MDP to which absorbing goal states (with corresponding rewards) are superimposed to create new tasks. We define the ground MDP Mo as: My (Sa, Ag. Ry, To. 7), with state space Sp, action space Ag, transition function To, discount factor 7 and background reward function Ro. Any individual task T ~ P(T) is given by goal state ser G, and an additional goal reward function R,, that is non zer-zero only for transitions entering G,.
Action Abstraction
Temporal or action abstractions are constructed over the primitive action set Ao 14] Although other formalizations exist 22
49) (see Klissarov et al. (36) for comprehensive overview), we adopt the options framework (64), where the agent has a collection of options O, where each O is tuple (7,,3,, no). The initiation set, I, S, is the set of states from which may be invoked. It is often defined as classifier Lo : + {0, 1}. To refer to the availability of all options at given state, we define 1o S + {0, 1] 11101 to be a vector with entry set to I,.s). Instances of the initiation vector are written as I. Similarly, the termination condition, 3o S - [0. 1], is the probability of option termination when entering s. Bo S - [0, 1]|01 is the termination vector: a vector of every option's 's termination probability at state s. Finally, option policy, To : S + A, controls option execution, which begins from a state in Lo, follows To, and terminates with probability
(s() at each state $t.
Replacing the primitive actions of an MDP with options results in semi-Markov decision process (or SMDP) M = O, R,, 7), where now O is a set of options, with (ss) = {o E Ols E Io} denoting the options available in state 8; R(s, o, s') returns the expected summed discounted reward received when executing option o E O(s) at state E S and exiting in s' E S: T(s', 4/8, o) describes probability of arriving in s' S, f time steps after executing E O(s) from S. The expected- length option model [3] represents these quantities separately, using transition function T(s'|s, and discount model 7(s, o) y², where the expected transition length. An option model for consists of initiation set lo. reward model it transition model T, and discount model 7. This representation is sufficient for model-based planning 64
57 63 and can be substantially faster than low-level planning when options shorten the effective solution depth [60] 50). An agent not given a collection of options must discover them itself. Skill discovery algorithms- an active area of research [27] typically identify 3, and then learn the remaining components to successfully reach it. Our framework is intentionally agnostic the origin of the agent's 's available options.
State Abstraction State abstraction 44 attempts to reduce the state space size by discarding irrelevant information or compressing the state space. Previous work has largely defined state abstraction using an abstraction function: Φ S + 5 mapping each state in the original state space S to a state in a new abstract state space S. This approach is often called state aggregation [44). Although there has been some work on
state abstractions for efficient option policy learning [32 39 19), the two abstraction types are typically considered separately.

---

3 Skill-Driven Abstract MDPs
Given ground MDP M A, (S, A, 7)) The core assumption behind almost all HRL is that A is set of options defined over M but typically 5 S, missing the opportunity build completely abstract MDP.
our goal to construct an abstract MDP M
While we could attempt state and action abstraction independently and hope that the resulting MDP is well-formed, that seems unlikely succeed, so type of abstraction must be constructed to support the other Although the reverse is certainly possible (see Section (). consider the properties that make state Markov: it must support determining which actions can be executed, the distribution over successor states given an action, and the reward. An observation space qualifies as a state space solely by virlue of supporting these functions, which all model the operations of actions, and an abstract state space that satisfies these properties for a given option set leads to well-formed MDP. Our approach therefore constructs the state abstraction to support the action abstraction.
3.1 The Semantics of Abstract States
One important question that must be answered when constructing an abstract state space is one of semanticx: what relationship should hold between an abstract state and the ground MDP? Previous work categorizes state abstraction types according to which properties they ensure hold in the ground MDP 44 Instead, we adopt a constructive approach 40 by defining target computation and then designing abstraction that supports it by construction. To support wide range of learning algorithms as possible, we target the Bellman equation [16] tte basis of virtually all value-function- based RL algorithms-whin for evaluating policy (over options) at state gives:
the
V(s) Σ T (r ~ EF (E|R(s, + E
x(als) (B [R(s, 8')] (+VV(()'))
(I)
where expectations are over s' and given (s,a), and the approximation is the expected- length model 3. Notice that the last equation is primarily composed of expectations over distributions of states.
If we refer to distribution over states using bar (e.g. 8). the corresponding expected value and rewards are: (s)) {s)) R(s, a. 8') E[R(s, a. s')], and R(5, a. 8') = [[[E[((s, 7, s']]]
Using these definitions, Equation
V(s) ~ (alss)s a, +
where + = E [T] and 3' = T(s' (iss|s,a) a). Later, we will pursue desirable properties by decomposing (or refining) (s'ls. s. a) into a mixture distribution, i.e., weighted sum of component distributions. Figure visualizes such a refinement.
execute
execute
P1
5
S
S
S
(a)
(b)
Figure 1: The outcome of executing option a from 8 is described by distribution over states (a). 8' can be refined into mixture of component distributions & and 82 with corresponding probabilities P1 and p2, such that 5' p1 + p2522 and p1 + P2 = 1 (b).
Refining into component distributions 8/, i.e., T(s' s a) = Pi8 where Σ.p: = 1, obtains:
V(s) Ta)s) E, [M(s, (+))
Equation is reminiscent of the Bellman equation but contains states of two types: individual states (s) on the left side and distributions over states (5;) on the right. We next extend the left side of Equation refer distribution states, computing V (3) for distribution s, which required to
"That does not mean that one process completely precedes the other in time: rather, one logically precedes the other- type of abstraction is designed match some property of the other.

---

This is strict generalization since any state can be viewed as Dirac delta distribution. Substituting the definition (S):
recursively compute the right side of Equation 2
V( ~ E E.=(ass P. (7,78, + 7
This resemblance to the original Bellman equation suggests that we should choose abstract states that correspond to distributions over ground states. If we choose to do then an abstract policy मे is a function rather than s, so we can shift it out of the expectation to obtain:
(3)) E= T(a Σ, [R(5, 81) + (+())
Equation B is the original Bellman equation applied to abstract states and actions, and is the sole equation necessary for computing Bellman updates. In other words, the Bellman equation for a given set of options can therefore be naturally rewritten as Bellman equation between abstract states, provided each abstract state refers to distribution over ground states. It remains to determine how to refine these state distributions so that the Markov property holds (that is, the model is an MDP), and गt operates with minimal value loss over M.
3.2 Satisfying the Markov Property
The three Markov properties we seek are: the abstract transition probability and discount models can be written as s 77) and y(5, Ø); 2) the abstract reward function can be written as R(s, a. s'); and 3) the options executable at an abstract state can be written as A(s). The first two hold by construction but the third does not, because the distribution over states resulting from option execution may contain states from which different options are executable. Therefore, preserving the Markov property in the abstract MDP requires that state distributions be refined (at Ieast) into component distributions from which a consistent set of options can be executed. Figure 2 gives an example distribution and initiation set combination where this occurs and the refinement that resolves If the initiation sets are known exactly the component distributions do not overlap:
csocato
1x
Lx
Ln.
Figure 2: Option execution where the distribution over next states cannot specify which options are available next. (a) Executing a from distribution leads to state distribution s'. Some states in s' are in initiation set la some in Tag. some in both and some neither. Therefore s' is not a Markov state as it does not specify available actions. (b) s' can be refined into distributions 81-8, (occurring with probability p1-P4), each over states with the same available options-onle ā can be executed in 51.
both a and 02 can be executed in 82, only T2 in 83, and neither in 84.
when initiation executable), they may have overlapping support. In either case, each component distribution now states conditioned
uncertain (i.e., only have probabilistic estimate of when option is
represents the distribution so the semantics of abstract states are:
specific initiation set vector being observed,
Definition 1. abstract state s a tuple (p, T), where p(s T) is distribution over ground states conditioned observed initiation vector 1. We define a grounding function for each component: (5,) = p: and (5:) = I,.
We can now form an abstract MDP M (3, constructed over ground MDP M follows. The actions A are a set of options over M, and the state set 3 is all abstract states over S: = [3 Ep, (8( (3) = 1}. The transition function is:
P(s T(8' (0 a) = P(I (. i3) P(s' 3,0.1' and (3) = 1'.
otherwise,
where P(T 8, is the expected probability of observing initiation vector I' after executing from (3), and P(s' 3, 1') is the expected distribution over s' after executing ß from

---

Gp(3) and observing I' The transition function expresses the probability that executing an option from abstract state will lead various abstract states s', each representing a distribution over states conditioned on specific initiation vector post-execution. Similarly the discount is 7 a) = Eg-0,(s)
hrss a)] and the reward function is: R(s,, a, 8') = Ea-op(e) (Er~ [R(s, a, $))]
3.3 Building a Model-Preserving Abstract MDP
The above MDP is Markov by construction and supports computing the exact expected-length value of any start state distribution- cetribution-bbecuse Equations [ and 3 are equal two caveats: there is no obvious way to build the uncountably infinite state space, and only abstract policies π (a]s) are supported, when further refinement might do better. Approximately model-preserving abstractions []] support computing approximately optimal policies the multi-task setting. An abstract MDP is approximately model preserving if:
[ (T as (s'' ((s'|ss, a)) ds' cr and R(s.a,8) R(s, a, 8')l
S CR.
any option a, pair 33,3"), ground state s ~ 8, and ER, ET 0. Since an approximately model- preserving abstraction is also approximately value- and volicy-preserving 45, the optimal policy computed an abstract MDP that obeys these conditions also good approximation to the optimal policy over the options in the ground MDP; indeed:
Theorem 3.1. v3, a. S + A. and s 3, Jf T(s' 3. a) - T(s' s, s, ds' S and [R(3,T) R(, a) ER. then (Q= ("(,,T)) VMNTE (Proof in the Appendix.) 1-7
States for which this property does not hold can be refined until they do, formalized by Algorithm which first constructs an abstract MDP with abstract states for the general state distribution (5o.,) and every option i's outcome distribution (8igg), partitioned by initiation vectors Ij. States from which transition exceeds an error threshold are identified and iteratively refined. The abstract transition and reward functions computed from data by taking weighted average of samples after the abstract states are constructed, The abstraction finite, Markov, and transition peetareeeeeeenneee model when no such states remain and is sufficient for planning, after modification for given plan query (see details in Appendix E)
Algorithm 1 Constructing and Refining an Abstract MDP
1: Given: transitions {st, I, ā, ra, s% (,, 6
2:
3: Partition transitions by initiation vector.
4: 80.j + {8; =,), VI, T&) Vj, T
5: 3j,A T) j.
6: "j,,,ta + mean(r,, t. = -. 1x)
7:
8: & Construct outgoing edges for executable actions.
9: for 3, where s. true do
T(3 (. (/3 Em mm)
A(s, si,n) < Ti,n, (5, a, si,m) t- fiin
12: end for
13: S (b,, A [Vi
14:
Repeatedly refine states with high-error transitions.
16: while 33, 7, s.t. model error(5, a, s') 2 (e,, ex) do
17: refine_state($ A, R,TR 3,3,3)
18: end while
19: return M = A, R
3.4 Examples of Learned Abstract MDPs
We demonstrate our approach using a high-dimensional chainwalk domain of length 6 (Figure 3p).
The agent is equipped with actions to move left right to adjacent states, but with 5% probability,
5

---

the subsequent state is selected uniformly at random. At each state, the agent observes a sampled 28 28 MNIST digit 42 (see Appendix A.I for more detail).
B, 1.00
0.24
R. 0.004
I 9:44
0.69
0.0.23
K. 0.83
0.24
1:00
L, 0.2
L, 0.44
0.68
0.76
Ba Mi
(a)
(b)
Figure 3: Learned state abstractions for the MNIST chainwalk. (a) Abstract decision process with three states prior to any refinement. Edges indicate actions with their most likely transitions. Each abstract state is sufficient to determine what actions are executable, and are depicted by their average low-level observations, while grounded samples are shown below. (b) Post-refinement abstract MDP, where the the six underlying discrete states have been recovered.
Algorithm| first constructs abstraction based on the initation vectors (lines 4-13), resulting in decision process with three abstract states (Figureß)) the first abstract state grounds to low-level states where only the right action is available, the second to states where both actions are available, and the last to those where only left is executable. Lines 15-18 then iteratively refine these abstract states to recover 6-state decision process that supports the Markov property (Figure Bp). Model errors are computed using a classifier two-sample test [46], while refinement is achieved by clustering. Implementation details are provided in the appendix.
simple Gaussian mixture model clustering algorithm is sufficient to refine abstract states in the chainwalk example, but naively clustering more complex observations can be difficult. A com- mon approach in these cases is to first transform the observed data into a more compact form, either by using the features extracted from pretrained neural network, or explicitly learning latent space using reconstruction-bun based objectives. However, such methods do not preserve the Markov property. We therefore use Markov State Abstractions (MSAs) [6), neural method which approximates provably sufficient conditions to recover Markov representations. A transforma- tion ó that preserves the Markov property should satisfy the following conditions: the ground and abstract (1) inverse models (a | o(s'), o(s) = (a | ss and (2) their density ratios p" (é(s') d(s))/p((ss)) p" (s' ((())/pp (s') equal. MSAs trained with raw observations output a compressed representation that is approximately Markov, to which Algorithm | can be applied.
We apply the resulting neurosymbolic algorithm to a visual Miniworld 17 maze domain. The maze consists of five rooms connected by hallways, and the agent is equipped with options to navigate from the center of rooms to connecting hallways, and vice versa. The north most room contains a gold block that the agent low-level state is given by a 60 x 80 x 3 image of the agent's point of view (Figure (4a top right). We apply MSA to learn 8-dimensional representation of the state space, and then apply Algorithm T Figure 4a shows the learned abstractions after the refinement, with our approach correctly recovering the underlying abstract graph structure of the environment.
approach and pickup. The walls of each room have a unique texture, and the
Planning can then take place over this graph using any compatible planner; we ran value iteration on the abstract MDP to compute the goal-conditioned policy.
The planner successfully navigates the agent west and then north, passing through three hallways, before collecting the gold. We further compare the planning performance of the learned abstract MDP with the cond-iondtio Deep Q-Network (DQN) (88 using the Stable Baselines 3 implementation
51 Figure 4b shows that the abstract MDP achieves better performance with far fewer samples than DON. In Figure 4cc we increased the observation resolution from x 80 pixels to 120 x 160 and 180 x 240 pixels, while keeping the sample size fixed. As an additional complication, we added random portraits on the wall for the highest resolution indicated with (P). Although these changes increase both the dimensionality and the complexity of the input space, the underlying decision
'Mos RL libraries assume that every action is available in every state. To make a fair comparison with SB3's DQN implementation, used the same initiation vector for all ground states during abstract MDP construction.

---

$14
0.6
Abvernet
$0
DON
0.0
16
2K
34
others unchanged (after 4K 5K 7K
8K
1
Number of compiec
511
88
(b)
52
$7
$22
59
Succes
0.2
HDP
DON
0.0
60x50
120c150
100K240
180K240
Nesolution
(a)
(c)
Figure 4: Application of Algorithm with MSA the visual maze domain. The first abstract MDP constructed by aggregating states with the same initiation vector. Abstract states are then iteratively refined until there is no improvement on the transition error. (a) Learned abstract MDP consisting of 14 abstract states after the refinement process. Each abstract state is assigned to its own color, while insets show the average ground state various locations in the domain. The planning performance of methods trained with varying (b) number of samples and (c) resolutions averaged over 20 runs. Shaded regions denote two standard errors around the mean, and the median is marked with cross.
process remains the same-the the correct abstract model should be invariant to the resolution and to the distractor portraits. The results in Figure scow that the abstract MDP's performance is not affected by these modifications, whereas the DQN's performance steadily declines with the increasing input complexity. This supports the objective of abstraction: retain only the information that necessary for effective decision-making.
Factored Skills Generate Factored MDPs
The above formulation assumes that option execution always changes every element of the low-level state vector. In practice, agents often have options that change Such factored options are common high-dimensional domains like robotics, and we now show that factored options with subgoal property lead to factored abstract states. Since abstract states ground to distributions over low-level states, we formalize a factored option as one where execution changes state variables, but leaves the distribution
state variables but not others.
the distribution over marginalizing out the modified variables). Formally:
Definition 2. An option o is factored with mask m from distribution उ = (()[m], 8(m)] 1o) T(s'ls ~ 3, o, 16) P(s [m]]s 3, o, 1.))) P(s[TT]] Io), where m are the masked state variables. 77 are those not in and s[m] and s [77) are the corresponding components of s.
Executing factored option o from & with mask m differs its effects on the masked and unchanged state variables. The new distribution masked variables depends the start state (drawn from 3) and post-execution initiation vector l'- The distribution over the unchanged variable is simply with masked variables marginalized out. These distributions independent; the variables m are unchanged by o so s' and 1'2 do not inform their distribution, while those in m already depend on s, so s(7i) redundant. This definition can be naturally extended to multiple possible factored outcomes, each with their own mask m.:
Definition 3. An outcome is tuple (m, Ty P(s(m])), where is mask, To is an observed initiation vector, and [[s[m]) is a distribution over the state variables the mask. Outcome w; results from executing option from distribution when: only the state variables in change; the

---

agent observes subsequent initiation vector fo: and P(s(ml) describes the subsequent distribution over the modified state variables, i.e., P(s'(nnss [ml] o, 0,3.
The condition supporting model-preservingg discrete abstract state space also generalizes naturally factors that the distribution over modified variables depends on but not low-level state
Definition 4. A factored option with mask m is factored subgoal option from distribution
3 = P(s Io) if: [(s(m]]
3, o, I'o) = [ms(m]] | 3,),
4.1 Defining a Factored Abstract MDP
The abstract MDP for the factored case must be built out of the masked distributions Pi(s' [m;] s, o. Ioo)) that result from factored subgoal option execution. These distributions are only defined over a subset m, of state variables in the ground MDP, and fulfilling any of the Markov properties requires representing distribution over all state variables. We must therefore model how each factored subgoal option modifies subset of the low-level state variables, while representing a distribution over all of them. We achieve this by grouping the low-level state variables into factors, where an abstract state assigns factor value every factor and grounds to distribution over all low-level state variables, but option execution changes only some of these values.
Definition 5. An atomic factor f S is a group of low-level state variables that either unmodified by option execution or are all modified together, i.c., (m, n f + 0) = f C m. for all outcome masks m, Let
.... } be the set of all such factors for a low-level MDP.
An outcome "sets" some of these factors-those inside its mask-to an abstract value representing its masked distribution. We therefore represent each factor as an abstract state variable that can be assigned one of a set of factor values representing an outcome wi that includes that factor.
Definition factor Jj has a factor value éj.a for each outcome w; for which ʃj S m, i.e., for each outcome that changes the variables in the factor.
An abstract state is then an assignment of values to every factor, representing distribution over every low-level state variable and an observed initiation vector.
Definition 7. Given a ground MDP with factored subgoal options and n factors, an abstract state 8 is an assignment of exactly one factor value ej E Fg each factor ʃn: 8 (e,,--. and an initiation vector 5 lo. The abstract state space S is the set of all such assignments.
Transitions in the abstract MDP set the factors overlapping the relevant outcome's 's mask to the factor values representing its effect; other factor values remain unchanged. The remaining decision process ionstruction-whicl satisfies all three Markov properties-follows straightforwardly, as does the learning algorithm (both are detailed in the Appendix). Abstract states are grounded as:
The state distribution grounding of factored abstract state is the product of the subgoal distributions for each outcome with effects present 8, after the factors belonging to each outcome absent in have been integrated out. Formally:
Definition 8.
9p(3) = (L)) [ (-.Jaaa
(elui.)) P.(s(mal)dd de(
where w33) = {w) Ej sljl = e, ew(w) is the collection of outcomes with an effect value in 5, and E(w,, 3) = {e, (w:) s & ej (wi)} are all of w; 's effect values that are not present in 5. The initiation set grounding is simply the available initiation vector: 97 (5) = 8g.
Theorem 4.1. Given abstract factored option ā and abstract state with grounding Gp(3), 3(5' grounds to the distribution over states resulting from executing a from a state drawn from Gp(3). (Proof in the Appendix.)
4.2 Examples of Learned Factored Abstract MDPs
Figure 55 shows the resulting factored abstract MDP on gridwalk domain, an extension of chainwalk where there are two integers representing the underlying state in each axis, and actions are the cardinal
directions that change the state only in one axis. As a result, the learned abstract states, {s1..... .., 836) now defined as the assignment of factor value to each factor, 3 [e1,1s e2, over six different
8

---

1.0
0.8
Succiss F300
0.6
0.4
Abstract MDP
DQN
1K 2K
3K 4K
5K
6K 7K
8K 9K 10K
Number of samples
(a)
(b)
Figure 5: Learned factored abstract MDP on MNIST gridwalk. (a) Abstract states correspond to factored distributions over two factors. Observations are a concatenation of two 28 x 28 sized digit images, representing the state in each axis. (h) Planning performance for varying number of samples. Shaded regions denote two standard errors around the mean, and the median is marked with cross.
values for each factor. Similar to the previous experiment, we compare the planning performance with the goal-conditioned DQN with hindsight experience replay [8] for varying number of samples. We trained an MSA network with 2-dimensional representations on which we can apply Algorithm I We added auxiliary loss to the original MSA objective to minimize the mutual information between hidden units, estimated separately with InfoNCE [67], which allows us to approximate the hidden units factors. Figure shows that the abstract MDP performs better with fewer samples when compared with DQN. The high variance in abstract MDP performance is due to suboptimal factorization of the MSA embedding space in some runs, which leads to poor refinements. Note that the median values are close to the upper bound of the two standard error bars, suggesting that the factored refinement works well only when the embedding space is properly factored. As such, learning a Markov representation that is factored with respect to the abstract actions would directly improve the task performance 52
We next apply the algorithm to the challenging Atari game Montezuma's 's Revenge [5]. The state space is given by the annotated RAM states (7] corresponding to 14 factors 16 variables, while the agent is equipped with a set of factored subgoal options, such as climbing down ladders (see the expert policy
appendix for the full list), which change only a subset of the RAM variables. We that completes the first room 10% the time, and otherwise deviates from the plan and executes random actions. This privileged process can be replaced by exploration module that visits abstract states with fewer samples (or higher transition errors) to expand the frontier of the abstract MDP by further refinement, which we leave future work. Figure 6 shows visualizations for factored distributions arising from the learned abstraction. After the final refinement, there are 116 factor values over factors that resulted in 1816 abstract states. We then apply value iteration the resulting abstraction, with the agent learning policy capable of collecting the key and exiting the room. Figure 6 shows the trajectory of the policy's execution.
of the
Related Work
Our work builds constructive approaches in robotics 440 29 for learning classical planning representations. That work does not result in Markov representations and can only reason about open-loop, straight-line plans. Others have learned object-centric classical planning representations from pixels using deep networks [65] 66 5 10 but without any formal guarantees, or using program synthesis 30 25 58). which faces scaling challenges. Earlier work in hierarchical RL 220 34 22
employed abstract states with hierarchical actions, but they primarily focused on learning policies within fixed hierarchies rather than learning the abstractions themselves.
Aggregation state abstractions can be organized into a hierarchy based on whether they preserve specific properties ranging from optimal policies to rewards and transition dynamics for all policies

---

S1447
183
DumpRight
X
X ....
X
X X..X
ey23
escore,
e,,2
ecooee
Figure 6: Examples of factored distributions on Montezuma's Revenge. Each abstract state (in blue) is an assignment of one factor value (in gray). A factored subgoal option changes some of these factor assignments while leaving the others unmodified. In this example. JumpRight action changes factors that correspond to the agent's ss and location and the skull's x location. The execution of the simulated plan that maximizes the reward by applying value iteration is shown on the right.
The strictest class of abstractions is commonly called podeel-preservtionn or bisimulation [21] provides bounds for (ó. O&) state state-action abstractions, one of which similar Theorem Our main difference from these previous works is that we define abstract states as distributions over ground states, as opposed to sets. Even though soft state-aggrggttionbaan
44
Abel
3.1
methods [59 allow defining distributions, because their abstraction is a function from the ground state to the abstract, supports of different abstract states cannot overlap. Furthermore, these abstractions are not tied to any specific semanties of the ground MDP, and thus, can arbitrarily fail to take into account the shape of the ground distribution. Defining abstract states as distributions over ground states-as the recursive computation of the Bellman equation over the abstract
the primary structure-suppen policy. State groundings can overlap and have different density functions. This difference abstract state semantics is fundamentally different direction in state abstraction.
There rich line of work that uses neural networks to learn state abstractions independently from action abstraction, typically by converting intuitively desirable properties into loss functions. These include compression 477, next-state prediction [68], inverse dynamics modeling [8] successor
features [13] robotic priors (31), contrastive learning [67], combinations of these 4 [6 26].
Allen 6 surveys these techniques and characterizes the specific combination that guarantees the Markov property. The result is MSA, which is compressed but not abstract or skill-driven.
few works have constructed abstract actions based on abstract states, typically partitioning low-level states using graph-based based clustering and constructing options to transition between adjacent clusters
24 These approaches assume that options can always be constructed between adjacent generated abstract states. That assumption fails in many tasks because options are subject environment dynamics whereas state abstractions are not. Finally, two recent approaches perform skill-driven state abstraction. Bagaria et al. graph and uses the nodes as abstract states. Shah et (53) use an option's value function evaluated at low-level state an abstract state variable. Neither approach guarantees the Markov property or value preservation.
37 69
61 55
[12 11 construct options to form connected
Conclusion
Hierarchical RL has always focused on abstract actions avoid the complexity of generating very long sequences of low-level actions. But fully realizing the promise of hierarchy requires combining state and action abstractions, to reformulate a complex agent-level MDP into a entirely new, and potentially much simpler, abstract MDP. Such task-level abstraction is promising approach to realiz- which must necessarily have very complex sensorimotor spaces, and mimics the human ability to form and exploit abstract task representations [28]. Our work combines principled theoretical approaches with the power neural networks to provide powerful framework for constructing abstract MDPs.
ing generally-intelligen agents (23 38
10

---

Acknowledgments
This research was supported by the ONR under REPRISM MURI N00014-24-1-2603 and grant N00014-22-1-2592, and in part by the NSF Graduate Research Fellowship (Grant No. 2040433). Cameron Allen was supported by a gift from Open Philanthropy to the Center for Hluman-Compann Al at UC Berkeley, and an AI2050 Senior Fellowship for Stuart Russell from the Schmidt Fund for Strategic Innovation. Part of this research was conducted using computational resources and services at the Center for Computation and Visualization, Brown University.
References
[1] D. Abel, D.E. Hershkowitz, and M.L. Littman. Near optimal behavior via approximate state abstraction. In Proceedings of The 33rd International Conference Machine Learning, pages 2915-2923, 2016.
[2] D. Abel, N. Umbanhowar, K. Khetarpal, D. Arumugam, D. Precup, and M. Littman. Value preserving state-action abstractions. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 1639-1650, 2020.
[3] D. Abel, J. Winder, M. desJardins, and M.L. Littman. The expected-lengthy model of options. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, pages 1951-1958, 2019.
[4] P. Agrawal, A. Nair, P. Abbeel, J. Malik, and S. Levine. Learning to poke by poking: Experiential learning of intuitive physics. Advances in Neural Information Processing Systems 29, pages 5074-5082, 2016.
[5] A. Ahmetoglu, M.Y. Seker, J. Piater, E. Oztop, and E. Ugur. DeepSym: Deep symbol generation and rule learning for planning from unsupervised robot interaction. Journal of Artificial Intelligence Research, 75:709-745, 2022.
[6] C. Allen, N. Parikh, O. Gotresman, and G.D. Konidaris. Learning Markov state abstractions for deep reinforcement learning. In Advances in Neural Information Processing Systems 34, pages 2021.
[7] A. Anand, E. Racah, S. Ozair, Y. Bengio, M-A. Côté, and R.D. Hjelm. Unsupervised state representation learning in Atari. In Advances in Neural Information Processing Systems 32, pages 8769-8782 2019.
[8] M. Andrychowiez. F. Wolski, A. Ray, J. Schneider, R. Fong, P. Welinder, B. McGrew, J. Tobin, Abbeel, and W. Zaremba. Hindsight experience replay. In Advances in Neural Information Processing Systems, volume 30, 2017.
[9] K. Asadi, D. Abel, and M.I. Littmn. Learning state abstractions for transfer in continuous control. 22Xiv:2002.055122 2020.
[10] M. Asai, H. Kajino, A. Fukunaga, and C. Muise. Classical planning in deep latent space. Journal of Artificial Intelligence Research, 74:1599-1686, 2022.
[11] A. Bagaria, A. de Mello Koch, Rodriguez--anchezz Lobel, and G. Konidaris. Intrinsically motivated discovery of temporally abstract craph-based models of the world. Reinforcement Learning Journal, 6:2115-215 2134.... 2025.
[12] A. Bagaria, J. Senthil, and G.D. Konidaris. Skill discovery for exploration and planning using deep skill graphs. In Proceedings of the Thirty-Eighth International Conference on Machine Learning, pages 521-531, 2021.
[13] A. Barreto, W. Dabney, R. Munos, JJJ. Hunt, Schaul, H. van Hasselt, and Silver. Successor features for transfer in reinforcement learning. In Advances in Neural Information Processing Systems 30, pages 4055 4065, 2017.
[14] A.G. Barto and Mahadevan. Recent advances in hierarchical reinforcement learning. Discrete Event Dynamic Systems, 13:41-77, 2003.

---

[15] M.G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling, The Arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, 2013.
[16] R. Bellman. The theory of dynamic programming. Bulletin of the American Mathematical Society, 60(6):503-55 515, 1954.
[17] M. Chevalier-Boisse Castro, and J. Terry. Minigrid & Miniworld: Modular & customizable reinforcement learning environments for goal-oriented tasks. arXiv:2306. 13331, 2023.
B. Dai, M. Towers, de Lazcano, L. Willems, S. Lahlou, S. Pal, P.S.
[18] Christiano, Z. Shah, Mordatch, Schneider, Blackwell, Tobin, Abbeel, and W. Zaremba. Transfer from simulation to real world through learning deep inverse dynamics model. arXiv:/610.035// 2016.
[19] L.C. Cobo, K. Subramanian, C.L.. Isbell, A.D. Lanterman, and A.L. Thomaz. Abstraction from demonstration for efficient reinforcement learning in high-dimensional domains. Artificial Intelligence, 216: 103:103- 2014.
[20] Dayan and G.E. Hinton. Feudal reinforcement learning. In Advances in Neural Information Processing Systems V, 1992.
[21] T. Dean and R. Givan. Model minimization in Markov decision processes. In Proceedings of the Fourteenth National Conference on Artificial Intelligence, pages 106-111, 1997.
[22] T.G. Dietterich, Hierarchical reinforcement learning with the MAXQ value function decompo- sition. Journal of Artificial Intelligence Research, 13:227-303, 2000.
[23] S. Doncieux, D. Filliat, N. Díaz- Rodrígzzd, T. Hospedales, R. Duro, A. Coninx, D.M. Roijers, B. Girard, N. Perrin, and O. Sigaud. Open-ended learning: conceptual framework based on representational redescription. Frontiers in Neurorobotics, 12:59, 2018.
[24] J.B. Evans and Ö. Şimşek. Creating multi-level skill hierarchies in reinforcement learning. In Advances in Neural Information Processing Systems 36, pages 48472-48484, 2023.
[25] C.R. Garrett, R. Chitnis, R. Holladay, Kim, Silver, L.P. Kaelbling, and T. Lozano-Perez. Integrated task and motion planning. Annual Review of control, Robotics, and Autonomous Systems, 4:265-293, 2021.
[26] D. Ha and Schmidhuber. World models. arXiv::803. 10122, 2018
[27] B. Hengst. Hierarchical approaches. In M. Wiering and M. van Otterlo, editors, Reinforcement Learning, Adaptation, Learning, and Optimization, chapter 12, pages 293-323. Springer Berlin Heidelberg, 2012.
[28] M.K. Ho, D. Abel, C.G. Correa, M.I. Littman, J.D. Cohen, and T.L. Griffiths. People construct simplified mental representations to plan. Nature, 606(7912):129-13)) 2022.
[29] S. James, B. Rosman, and G.D. Konidaris. Autonomous learning of object-centric abstractions for high-level planning. In Proceedings of the Tenth International Conference on Learning Representations, 2022.
[30] N. Jetchev, T. Lang, and M. Toussaint. Learning grounded relational symbols from continuous data for abstract reasoning. In Proceedings of the 2013 ICRA Workshop on Autonomous Learning, 2013.
[31] R. Jonschkowski and O. Brock. Learning state representations with robotic priors. Autoromous Robots, 39:407-428, 2015.
[32] A. Jonsson and A.G. Barto. Automated state abstraction for options using the U-Tree algorithm.
In Advances in Neural Information Processing Systems 13, pages 1054-1060, 2001.
[33] K. Jothimurugan, O. Bastani, and R. Alur. Abstract value iteration for hierarchical reinforcement learning. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, pages 1162-1170, 2021.
12

---

[34] L.P. Kaelbling. Hierarchical learning in stochastic domains: Preliminary results. In Proceedings of the Tenth International Conference on Machine Learning, pages 167-173, 1993.
[35] M. Kearns and S. Singh, Near-optimal reinforcement learning in polynomial time. Machine Learning, 49:209-232, 2002.
[36] M. Klissarov, A. Bagaria, Z. Luo, G. Konidaris, D. Precup, and M.C. Machado. Discover- ing temporal structure: An overview of hierarchical reinforcement learning. arXiv preprini arXiv:2506.14045, 2025.
[37] M.J. Kochenderfer. Adaptive Modelling and Planning for Learning Intelligent Behaviour. PhD thesis, University of Edinburgh, 2006.
[38] G. Konidaris. On the necessity of abstraction. Current Opinion in Behavioral Sciences, 29:1-7, 2019.
[39] G.D. Konidaris and A.G. Barto. Efficient skill learning using abstraction selection. In Pro- ceedings of the Twenty First International Joint Conference Artificial Intelligence, pages 1107-1112, July 2009.
[40] G.D. Konidaris, L.P. Kaelbling, and T. Lozano-Perez. From skills symbols: Learning symbolic representations for abstract high-level planning. Journal of Artificial Intelligence Research, 61:215-289, January 2018.
[41] A.S. Lakshminarayanan, R. Krishnamurthy, P. Kumar, and B. Ravindran. Option discovery in hierarchical reinforcement learning using spatio-temporal clustering, 1605v:660.0053:3 2020.
[42] Y. LeCun. The MNIST database of handwritten digits. http::/yann.. wtw.:aaa..ecccccco/ee//eeo//oo com/exdb/ mnist/ 1998.
[43] S. Levine, C. Finn, T. Darrell, and P. Abbeel. End-to-end training of deep visuomotor policies. Journal of Machine Learning Research, (11):1133-1373, 2016.
[44] L. Li, TJJ. Walsh, and M.I. Littman. Towards unified theory of state abstraction for MDPs. In Proceedings of the Ninth International Symposium on Artificial Intelligence and Mathematics, 2006.
[45] S. Lobel and R. Parr. An optimal tightness bound for the simulation lemma. Reinforcement Learning Journal, 2:785-797, 2024.
[46] D. Lopez-Paz and M. Oquab. Revisiting classifier two-sample tests. In Proceedings of the Fifth International Conference Learning Representations, 2017.
[47] J. Mattner, S. Lange, and M. Riedmiller. Learn to swing up and balance a real pole based on raw visual input data. In Proceedings of the 19th International Conference Neural Information Processing, pages 126-133, 2012.
[48] V. Mnih, K. Kavukcuoglu, D. Silver, A.A. Rusu, J. Veness, M.G. Bellemare, A. Graves, M. Ried- miller, A.K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, S. Legg, and D. Hassabis. Human-level control through deep reinforcement learning. Nature, 5 518:529-553 533, 2015.
[49] R. Parr and S. Russell. Reinforcement learning with hierarchies of machines. In Advances in Neural Information Processing Systems 10, pages 1043-1049, 1997.
[50] E.J. Powley, D. Whitehouse, and P.I. Cowling. Monte Carlo tree search with macro-actions and heuristic route planning for the physical travelling salesman problem. In Proceedings of the 2012 IEEE Conference on Computational Intelligence and Games, pages 234-241, 2012.
[51] A. Raffin, A. Hill, A. Gleave, A. Kanervisto, M. Ernestus, and N. Dormano. Stable-baselines3: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22(268):1-8, 2021.
13

---

[52] R. Rodriguez- Sanchez, C. Allen, and G. Konidaris. From pixels to factors: Learning indepen- dently controllable state variables for reinforcement learning. arXiv preprint arXiv:2510.0288, 2025.
Sannche,
[53] Shah, P. Xu, Lu, T. Xiao, A.T. Toshev, S. Levine, and B. Ichter. Value function spaces: Skill- centric state abstractions for long-horizon reasoning. In Proceedings of the Tenth International Conference Learning Representations, 2022.
[54] N. Shah, J. Nagpal, and S. Srivastava. From real world to logic and back: Learning generalizable relational concepts for long horizon robot planning. In Proceedings of the 9th Annual Conference on Robot Learning, 2025.
[55] N. Shah and S. Srivastava. Using deep learning to bootstrap abstractions for hierarchical robot planning. In Proceedings of the 2 International Conference on Autonomous Agents and Multiagent Systems, page 1 1183 1191, 2022.
[56] E. Shelhamer, P. Mahmoudieh, M. Argus, and T. Darrell. Loss is its own reward: Self- 2016.
supervision for reinforcement learning, arXiv:
[57] D. Silver and K. Ciosek. Compositional planning using optimal option models. In Proceedings of the Twenty-Ning International Conference on Machine Learning, pages 1267-1274 2012.
[58] T. Silver, R. Chitnis, N. Kumar, W. McCLinton, T. Lozano-Perez, L.P. Kaelbling, and J. Tenen- baum. Predicate invention for bilevel planning. In Proceedings of the 2023 AAAI Conference on Artificial Intelligence, pages 12120-12129, 2023.
[59] S. Singh, T. Jaakkola, and M. Jordan. Reinforcement learning with soft state aggregation. In Advances Neural Information Processing Systems 7, pages 361-368, 1994.
[60] Sorg and S. Singh. Linear options. In Proceedings of the Ninth International Conference on Autonomous Systems and Multiagent Systems, pages 31-38, 2010.
[61] L. Steccanella, S. Totaro, and A. Jonsson. Hierarchical representation learning for Markov decision processes. In Proceedings of the IJCAI 202/ Workshop on Generalization in Planning, 2021.
[62] R.S. Sutton and A.G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 1998.
[63] R.S. Sutton, M.C. Machado, G.Z. Holland, D. Szepesvari, F. Timbers, B. Tanner, and A. White. Reward-respecting subtasks for model-based reinforcement learning. Artificial Intelligence. 324: 124:10 2023.
[64] R.S. Sutton, D. Precup, and S.P. Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence. 1 112(1-2):181-211 1999.
[65] E. Ugur and J. Piater. Bottom-up learning of object categories, action effects and logical rules: From continuous manipulative exploration to symbolic planning. In Proceedings of the IEEE International Conference on Robotics and Automation, pages 2627-2633. IEEE, 2015.
[66] E. Ugur and J. Piater. Refining discovered symbols with multi-step interaction experience. In Proceedings of the 15th IEEE-RAS International Conference on Humanoid Robots, pages 1007-1012, 2015.
[67] A. van den Oord, Y. Li, and O. Vinyals. Representation learning with contrastive predictive coding. 10XXv:/807.0:77 2018
[68] M. Watter, Springenberg. J. Boedecker, and M. Riedmiller. Embed to control: A locally linear latent dynamics model for control from raw images. In Advances in Neural Information Processing Systems 28, pages 2746-2754, 2015.
[69] A. Zhang, S. Sukhbaatar, A. Lerer, A. Szlam, and R. Fergus. Composable planning with attributes. In Proceedings of the 35th International Conference Machine Learning, pages 5842-5851, 2018.
14

---

A Environment Details
A.1 Visual Chainwalk
The visual chainwalk domain consists of six underlying states. Unlike the standard environment, in which the state representation of the agent is single integer, here the state is visual image representation of the integer, ranging from to 5. At a given state, the agent receives a 28 x 28 greyscale image sampled from the labelled set of MNIST images 422 At each step, new image is sampled uniformly at random and flattened into a 784 dimensional vector.
The agent has two options (which are equivalent to its low-level actions, owing to the simplicity of the domain): moving left and right. These options are executable everywhere, except at boundary states where the agent deterministic and the agent transitions to the adjacent state. However, with probability 0.05, the next state is sampled uniformly at random. For each action, the agent receives reward of 1 if it arrives at the goal state, and () otherwise.
only move right or left appropriately. With probability 0.95, option execution is
A.2 Visual Maze
The visual maze domain is built in the Miniworld 17 hallways connecting the rooms. Fillutraelss the layout of the maze from top down perspective, along with the 60 x 80 x 3 image of the agent's 's point of view, which represents the state.
framework and consists of five rooms with
14.00. 5.00, 5.00. 07g 88
Figure 7: A view of the vault environment, showing the layout of the five rooms and the connecting hallways from a top-down perspective. The agent represented by red triangle, and there gold block in the north-most room. The state is given by the agent's ' egocentric view (top right), while additional information such as its exact location is also specified. Note that the state space is only egocentric pixel observation; no other privileged information is provided to the agent.
Each room has walls with different textures (cardboard, brick, wood, rock and tile) to ensure that the egocentric observation is still Markov. The agent is equipped with five noisy options:
"Walk to center". This is only executable when the agent standing room's hallway. The option terminates when the agent is in the center of the room.
"Walk to clockwise hallway". This executable everywhere, except when the agent is in the north-most room. The option terminates when the agent reaches the hallway closest in the clockwise direction.
"Walk to anticlockwise hallway". This is executable everywhere, except when the agent is in the north-most room. The option terminates when the agent reaches the hallway closest in the anticlockwise direction.
"alk to north hallway". This is only executable when the agent is standing in the center of the room connected the north-most room. The option terminates when the agent reaches the hallway leading to the room with the gold block.
"Pickup gold". This only executable when the agent standing in the north-most room. The option terminates when the agent has walked to the gold block and picked it up.
15

---

The agent receives a constant negative reward for each step taken in the domain, and an episode terminates when the gold block collected.
A.3 Visual Gridworld
The visual gridworld is an extension to the chainwalk domain. Here, the state is represented by two MNIST digits, and the agent's actions (options) are each of the cardinal directions (except at boundary states). The two digits represent the underlying s7y-coordinate on the grid; when the agent transitions to a new state, the image of the unchanged coordinate remains fixed. such, the state space is of dimension 1568 with are two factors: one for state variables with indices [O...., 783), and the other for indices [784,... 1567].
A.4 Montezuma's Revenge
We use the Atari video game Montezuma's 's Revenge an example of a challenging RL domain. Here, the state space is represented by the underlying 16 bytes that make up the subset of the RAM state that controls the game particular time 77. The domain is otherwise standard, except we equip the agent with the following set options:
RunLeftSkill: the agent runs left until it reaches the end a platform or wall.
RunRightSkilll the agent runs right until reaches the end of a platform or wall.
ClinboonnRopeSS:11l the agent climbs down the rope until it reaches the ground.
ClimbUpRopeSSt111: the agent climbs up the rope until reaches the ground.
DropFromRopeskilll:: the agent jumps off the rope the ground.
Cimbboownaadderrki111::1 the agent climbs down the ladder until it reaches the ground.
Cl imbbppladder::::1ll the agent climbs up the ladder until it reaches the ground.
JumpInPPaaceSk:lll; the agent jumps vertically.
JumpLeftSkill: the agent jumps left.
JumpRightSkill1:th the agent jumps right.
WaitfrosshallMoorinnooraadd the agent stands in place until the skull starts moving towards it.
WaitForskullMMvingkrr the agent stands in place until the skull starts moving away from it.
the agent waits in place and the jumps when MustForrumsStullMMooinnoooo
skull is moving towards it.
WaitForJumpSkul htwp:///sulMMMovinaaooo 1MovingAway: the agent waits in place and the jumps when the skull is moving away from
PassTooLoffOt the agent moves left away from the skull.
SfgFTRRigghtOffumpSSSi the agent moves right away from the skull.
ChargeEnemyLeft: the agent runs left towards the skull.
ChargeEnenyRight: the agent runs right towards the skull.
B Algorithms for Computing the Model Error and Refinement
B.1 Using Classifier Two-Sample Test
We compute surrogate value for ey by using a classifier two-sample test (C2ST) 46), which is popular metric to evaluate generative models that produce distributions over high-dimensional vectors such as natural images. Here, we essentially want to evaluate the discrepancy between T(s' 8, a) and T(s' 8, ū), which is equivalent to the discrepancy between the joint probability p(s', s) and the product of marginals p(s') (()))(s)) under the expectation of 8. We fit k-nearest neighbor classifier with (s, s') as positive examples and their shuffled version (3, s') the negative ones. We measure
16

---

the deviation from 50% accuracy, at which and s' are independent from each other and that the classifier cannot differentiate (s, s') from (5, We summarize this procedure in Algorithm 2 During refinement, we sum values of all abstract states to come up with cumulative transition error metric TTon for the whole abstract state space. We then compute <T m times and make t-test to measure the significance of the refinement and accept those that are below a certain value.
Algorithm 2 Compute State Error
Given: 8, transition tuples {s, a, 5 corresponding to s, factor fi, number of tests n,
number of nearest neighbors k
2:
3: eT,En" (-
4:
for each available option a; do
5:
(Sa,&,, <- initer_transitions crranitions_by_ottiiiiiee pyy_option(), (.)
6:
m + fa.vaiabllss
7:
Ho 4- (}
8:
Ha f (
9:
for i = to do
10:
Zground f- (Sa, s [ml]
11:
Tabstract +- (s 5, [m])
12:
2n + (shufflc(sa) S [m])
13:
Ho Ho U knn aww.aaccccccccc. (T Fground: 30, k:)
14:
Ha f Ha U knn__cccurru (Tabutrat FD, 1:)
15:
end for
16:
1o. To + compute_stee saanut___sttstticsHHHH
May
compute__tatisteee (H.))
18:
êT f- ET + p (-log[ttest__-valee/ne On, May oa, 11)
ER E- ER + p * var(r)
20:
end for
return ET: ER
B.2 Refinement
We wish to decompose abstract state into smaller components, and then recompute the appropriate transition dynamics for each of them (both for incoming and outgoing transitions). Since an abstract state represents distribution over ground states, there combinatorially many ways the state could be refined. In practice, we adopt a clustering approach, with each resulting cluster representing component distribution. We find that two components is sufficient for the domains presented here, but the refinement process is agnostic to this. Earlier version of this work used k-means with & 2 that have similar results. We later adopted GMMs to accommodate overlapping supports. Algorithm Billustrates Algoritmmlllllltttnt given abstract state.
Gaussian mixture model with
the procedure for refining a
Algorithm 3 refine state _tate
1: Given: S,A.T, T.,TAAD R, 3,3, transition tuples D, clustering algorithm C
2:
3: (s,ä, +-
4: C.fi((s)
5: labels, t- C.predict(s))
6: labels,/ + C.predict(s')
7: Create new abstract states Snew based on unique labels from labels, and labels,
8: Assign each transition (s, a, s') to the corresponding abstract states in Snow
9: 5 5 SUI new {3)
Recompute abstract transitions T based updated transitions
17

---

B.3 Using MSA Density Ratio Loss
We used InfoNCE 677
objective to approximate the density ratio objective MSA. This objective
pushes the model to create a contrast between real transition tuples (s, 8') and their shuffled version (8, 8"). Since this objective provides lower bound to the mutual information T(x, 8'), can be directly used proxy for detecting states with high mutual information. Such states can be selected as candidates for refinement.
C Proof for Theorem 3.1
Let abstract states 8 represent distributions over ground states, defined by Pr(s|3). Let T ss. a) and [[5, a) be a transition and reward functions defined over abstract states, Thus, we define T(''13, a) Es T a) Pr(s'(3),, and similarly define π (āāss) = S. (r(s()))(a(s) Additionally let R(s a) 2 O. VMAX represents the maximum value obtained either the ground or abstract MDP: VMAX = max (max, V (s), max, (3)). For conciseness, we define T = =Ts''ss,)) a).
Theorem C.1. For all 8, for any û. for any policy : S + A, and any E fxr E S: P(x ~ 8) > 0}.
if
[ T('' (3, 1(,')1,,)) T(s'' |8,0] ds' Ser,
(4)
[R(5,a) - R(ss, a)) SER.
(5)
then
CR + VMAXeT (s=(s,)) (s).aa)
(6)
Theorem This result is closely related to the simulation lemma 45 351. generalized to apply to abstract state and action spaces. Without loss of generality, we present the proof for the case of Q (s, a) 2 Q* a). The same arguments hold for Q" @) I (" a). We begin by proving that bound on Q differences implies the same bound on V differences, in expectation.
Lemma C.2. Let AQ be the maximum discrepancy for any 8, a, and any E P 0}:
max (= (5, 8,0,808
Then
E ESN (s)] (3) < AQ
(8)
Proof of Lemma C.2
E E
V
VT())
(9)
Pr((|()
(s, Pr(als)Q (3,
(10)
[ Pr(s|s)
Pr(āls) (s, a)däds
Ptal))) aada
(11)
Pr(s
(r(s))) Pr(als) (Q - (², dads
(12)
= Eyws Eaas (2" (s,a))
(13)
< Eans max (Q" (=(
(14)
E [V*(s)) (* = AQ
(15)
18

---

Now, using the Bellman Equation for both Q"(s, and Q (²,5a), we set up recurrence relation in order to prove our bound.
Proof of Recursive Relationship.
-"(s,a)-Q**
(16)
-( + +7" / Pe..VVE ()(3)))) -7" Σ T (3(
R(3,a)
(17)
-((s,d) - R(5,a)+t)
-7" Σ T V (8')
(18)
SER
S SCt Pu.. 7²t Ta.a,
V V*(8')
(19)
EE [V (+*) (Lemmo
sentp Tos.. VT (s')d'' 77) To.
Pr(('(s')
(V*(5') (V*)))))))))))))))))))))))))))
AQ) ds
(20)
ER + V* -1/ /
T Pr(s'(s' - AQ) ds
(21)
8
=Thin
= ER +1 / (rs.assT (s')dd' -77 -7 / Taad (V*(s') -Q) ds'
(22)
en + x AQ t S (Trodd- -T (s'dd'
(23)
SCR DQ tx
Toaad' T
V (s') ds'
(24)
<VMAX
SET
SER + VM
(25)
SRR + AA + VMAX
(26)
Since this holds for all this implies that
AQ SER + TET VMAX + +7A0
(27)
CR +
AQ S
(28)
1-7
Thus completes our proof.
D Proof for Theorem 4.1
To first define the abstraction transition function, we observe that transitions in the abstract MDP modify the factors contained in the relevant outcome's mask, causing the values of factors in the mask be changed the factor values representing its effect. All other factor values remain unchanged.
The corresponding abstract transition function is:
P:
if 3f e
f(we) and 8'1fA] 8fll & f(w:) and
T(
g 10=
(29)
0
otherwise,
where the outcome wi with mask my and initiation vector To: occurs with probability p; (possibly 1) when executing action à from 5.
19

---

Theorem D.1. Given an abstract factored option à and an abstract state 3 with grounding (3(3), then ( (, a) computed by Equation 29 accurately represents the distribution over states which the agent may find itself after executing from a state drawn from gp(3).
Proof of Theorem
D.1
Given that abstract state has grounding:
( Pi(s(m,])dd- de(w).))
(p(5) P(s To) (w)(w())
(30)
J(wwe.8)
we seek to prove that the abstract transition function grounds to the distribution over states the agent
may find itself after executing action from state drawn from (8))). By combining multiple
factored outcomes and factored subgoal options in Definitions B and with Definition we arrive at:
T(s' 8, 8, 1o) -E [mm( 8, Toi) x P(s[m:] To)],
We
where there are outcomes. The abstract transition function has a similar form, via Equation T(s' a) Σ, p. therefore suffices show that:
29
(5() Ps(s [mm]]
f'rs) P(s ((s.m.) [o),
(31)
for each outcome w/. We begin by applying the grounding definition (Definition 8 to state s% which gives:
(3)3 Ha EW(R))
()(() Loy) da(ws,
where ((.) is the set of outcomes with factor values present in 8, and ((w), 88) is the set of factors that are in Wj's 's mask but have factor values in 5%. One outcome present in 8/ wi itself, which we know by Equation 29 has every relevant factor value set in 8;;
${ (wi) Vfz f(wi),
and hence E(wY, 5 is empty, so:
- P3(s(my) lo,)d de(
(p(3,) = P3 (smm(mm) Toi) x Ew))
(32)
Comparing equations 31 and 32 see that the left components of the product are the same; remains to show that the right portions are equal. Specifically, we must show that:
P(s[ma] To) IT, (wn)
(e(u, (s(s(m)] Toj)d. de(wyaa)
Since neither term is a function of any variables mi we can freely introduce additional integrals over m. We must therefore prove:
P(s[me] To) To)= fo)== f- (.m, TT, Tw,
[/... (eww,,.) (5(((mg) Iog)d l..) detur, dim.)-
(mi)
Next, we note that (33) \w; C Cw) i.e., that every outcome in ((3') ) \w is also in w()). Additionally, outcomes in (s) but not w(8)) ('')) wi can only functions of m, and so can included in the product on the right hand side because they will subsequently be integrated out. We must therefore now prove that:
P(s|m.] 10) I.. 1w Ew(())
[/...
Jalas,ar) Ps(m|m loj)d-.-daae da(ws,sr) d(mi)-
(m²)
Finally, we can replace e(wj, 8') above with ē(wy, 8) because these terms can only differ via factors in m, which are subsequently integrated out. Hence it remains to prove that:
P(s[me]] 1o) = f (m;)
[/. I/J. - Ps(s|m,] los)d .- -e(eee demi)
=f.. I Gr((3) d(m):
(m))
which is its definition.
20

---

E Planning using An Abstract MDP
An abstract MDP M is sufficient for planning, after modification for a given plan query:
Definition 9. A plan query on the ground MDP is a tuple Q, = (Br G,, R2), where (s) is start state distribution, G, C S is set of terminal goal states, and R. G. - IR is the reward for entering states in G..
M must be modified as follows: first, execution should cease when the agent enters a state in Gy, with terminating reward given by R, Any abstract state that overlaps G, must therefore be refined into a terminating abstract state contained in Gy, and possibly a state representing 3's remaining support. This process is depicted in Figure g The resulting goal states are grouped into goal set G.
De N
Sc
9AS)
9,55c
(a)
(h)
Figure 8: (a) Abstract state 3 with grounding distribution Gp(3) that overlaps grounded goal set G, S. (b) z must be refined into a goal state that grounds to the portion of (p(3) overlapping G (with probability Pc), and 77. which grounds to the remainder of Gp(3) (probability - pa). Sc terminating with expected goal reward rG. while 8द has the same reward and outgoing transitions as 5. Incoming transitions to s are distributed according to pG-
Second, the agent must collect into start state set all states with non-empty grounding overlap with B,, These need not be refined because the abstraction is approximately value preserving. Any planning algorithm can then used compute an optimal policy leading from any state B to any in G.
F Limitations
In this work, we derive an algorithm to build an abstract MDP that can be iteratively refined to reduce the transition and reward error arbitrary value. Our implementation uses GMMs for such refinements. While partitioning an abstract state essentially decrease its size, and therefore makes more likely improve the model, is possible hit the local minima with the iterative clustering, and fail to refine further. On the other hand, our method is agnostic to the choice of the clustering approach used, and thus, we believe that this should not pose serious limitation.
Our experiments Montezuma's Revenge uses annotated RAM variables, While it is possible to train necessarily factored,
an MSA network on the RGB observations, the learned representations which makes it hard to show how the algorithm operates. While this is not directly limitation of the method-as focus is how learn factored abstract representations from ground variables from given factors-it can be regarded as the limitation of the paper.
Currently, A works in batched fashion on set of environment interactions. Ideally, it should iteratively collect data from states that are not visited frequently to expand its frontier. As we interested in constructing the abstract MDP given enough data, we have used an expert policy in 10% of the transitions Montezuma' 's Revenge, and deviate from the expert policy otherwise.
21

---

G
Network Details
MSAFlat(
(encoder): Sequential(
(0): Linear fi__ out_features=64, bias-True)
(1): ReLU()
(2) Linear (in_ out aut_features=64, bias=True)
(3) ReLU()
(4): Linear (in_features=56) out out_feattures=NNLATEMM bias=True)
(inverse_fc):
(0): Sequential(
out_features=64, bias=True)
(1): ReLU()
(2) Linear (in_featuree=64, out_features=66, bias-True)
(3): ReLU()
(4): Linear
out fut_features=5, bias=True)
(density_fc)) Sequential(
(0): Linear (in_faarrrn, out_features=64, bias=True)
(1): ReLU()
(2): Linear (in_faarn_
out_features=-1,, bias=True)
(3): ReLU()
(4): Linear (in_ featureess,, out fea_ueeeu,s--1, bias=True)
(decoder): Sequential(
(0): Linear fin_ out fut_features=-4, bias=True)
(1): ReLU()
(2) Linear 6i,,tetueet,,,, out_features=64, bias=True)
(3): ReLU()
(4): Linear fi__eeatuues:=66, out_features=1568, bias=True)
(mi): : Sequential
(0): Linear fin_feature==44 out_features-64, bias=True)
(1) ReLU()
(2) : Linear (in_features=64, out_features=64, bias-True)
(3) ReLU()
(4) Linear 6i,, out fut_feeaures=1, bias=True)
)
We used two-layered multi-layer perceptron (MLP) with 64 hidden units and ReLU activations for the MSA encoder. The output dimensionality of the MSA encoder is set to 8 for Visual Maze domain, and to 2 for MNIST gridwalk domain. inverse. fc and density modules compute the inverse model and the density ratio losses, respectively. mi trained seperately (with seperate optimizer) to estimate the mutual information between two hidden units, and the main MSA model backpropagates through this estimate to minimize it. Lastly, we use the decoder only for visualization purposes and do not backpropagate any error through which would otherwise make it reconstruction-basse embedding.
QNetwork(
Linear (en_features1156,, out fut_features=6,, (q_net): Sequential(
bias=True)
(0): Linear (in_ fet_u_eeatures4704,,, out_features=64, bias=True)
(1): ReLU()
(2) Linear fit_features= out out_features:64, bias=True)
(3) : ReLU()
(4): Linear (in_ (in_features=64, out fut_featu,:::4, bias=True)
22

---

We used the default structure of the DQN model that is provided in stable- basble-bsellins.." [51] with the only difference in the output dimensionality that depends on the number of actions the domain. Also, we used the same feature extractor to process the observation and the desired goal, which considerably increased the performance, as opposed to plain concatenation of them. Note that the encoder of MSA and the Q network of the DQN has the same number of layers and hidden units.
H Hyperparameters
We used the default hyperparameters of the DQN model in sable-baseliiee with the only change of train frequency from four to one, on which the model was performing better (Table 3). As we are using the conditondt DQN, we experimented with hindsight experience replay [8] and found that while it helped in MNIST gridwalk domain, it made the results worse for the Visual Maze domain. For MSA training, we only did an informal search of frequently used hyperparameter values (Table
Table 1: MSA hyperparameters
Table 2: Alg. hyperparameters
Parameter
Value
Parameter
Value
Batch size Validation split Optimizer
Minimum transition error éT
0.1
MNIST chain
0.1
Adam
MNIST grid
0.1
Learning rate
0.001
Visual Maze
None
81
0,9
Montezuma's Revenge
0.1
B2
0.999
Minimum ΑeT for refinement
10-8
MNIST chain
0.5
Negative sampling rate Inverse loss coeff.
10
MNIST grid
0.5
1.0
Visual Maze
0.0
Density ratio loss coeff. Smoothness coeff.
1.0
Montezuma's Revenge
0.5
1.0
Minimum reward error n.
None
Mutual information reg. coeff,
1.0
Minimum n for refinement n. cluster trials
None
Maximum number of epochs
200
10
Early stopping patience
Min. samples for refinement
10
The main hyperparameters Algorithm (Table 2 are minimum transition and reward errors, eT, ER, and their relative improvements after refinement, Aer, Aeg. Using the transition error sufficed in our domains. éy and ÉR define thresholds to consider an abstract state as a candidate for refinement. We used Aer and AER to check whether the clustering decreased the cumulative transition and reward errors. In that sense, e values set the granularity level of the abstract MDP whereas Ac values filter out refinements that does not improve the score due to poor clustering.
In this paper, we focus on the theoretical construction of the framework, and provide an implementa- tion of this idea. We note that this is one specific instantiation. Many parts-ranging from refinement to independence rests-can be realized with various methods. As such, hyperparameters both this approach and in the compared baseline is open to further optimization for better performance.
I Compute Resources
The algorithm presented the paper first trains an MSA network and builds an abstract MDP on top of the trained embeddings. The training time of the MSA network depends on the dataset size and the available chip configuration. The construction of the abstract MDP consists of iterative clustering and independence test steps. We profiled the current implementation to understand the main bottlenecks. Two components that contributed to the overall time complexity the most are (I) torch.cdist, that computes the Euclidean distance between each pair of vectors in two tensors to estimate er using k-nearest neighbor based independence test, and (2) the assignment of each ground sample to the abstract states after clustering. We believe these processes can be further optimized with sampling
https://stable basel ines3 www.dheedcs.ss.e.. htt.a///oocc..ooo/////sssrr/////
23

---

Table 3: DQN hyperparameters
Parameter
Value
Batch size
32
Learning start step
100
Optimizer
Adam
Learning rate
0.0001
81
0.9
B2
0.999
10-8
Soft update coeff. (r)
1.0
Discount factor (?)
0.99
Train frequency (every & step)
1
Gradient steps (every & rollout)
Replay Buffer
HER
g
Number sampled goals
Target update steps
10000
Exploration fraction
0.1
Exploration initial
1.0
Exploration final c
0.05
Maximum gradient norm
10.0
approximations and with special data structures like k-d trees to reduce the time spent on finding nearest neighbors.
We used a GPU cluster to train multiple MSA networks in batch and build the abstract MDP locally on laptop with Apple M1 Pro chip and 16 GB of unified memory. DQN models are trained locally on this same laptop and another with NVIDIA RTX 4070 GPU and Intel Core Ultra Processor 185H. It is difficult to give accurate numbers the training times GPUs on the cluster shared accross multiple users. Trainings on the MNIST domain are completed within minutes whereas trainings on the Visual Maze took around 5 to 10 minutes 80 60 resolution, and 30 to 50 minutes higher resolutions.
J MSA Embedding Visualizations
We visualized the learned embedding spaces in different domains for varying samples sizes in Figures and
24

---

21
118
(a) 1000 samples, Seed 0
(b) 1000 samples, Seed
(c) 5000 samples, Seed
(d) 5000 samples, Seed
7v=10
-0.9
10000 samples, Seed
ii) 10000 samples. Seed
Figure 9: Learned MSA embedding spaces in the Visual Maze domain for different numbers of samples. 2-dimensional positions are the MSA encodings of input images. Frame colors represent the underlying high-level states.
25

---

0.5
Z2
21 1.1
Figure 10: Learned MSA embedding space in the Visual Maze domain at 160 x 120 pixels.
26

---

Z2 0.6
Z1 1.1
Figure 11: Learned MSA embedding space in the Visual Maze domain 240 x 180 pixels.
27

---

22 =.3
= 0.1
Figure 12: Learned MSA embedding space in the Visual Maze domain at 240 x 180 pixels with random portraits on the wall.
28

---

03
0
64
0
0
(a) 1000 samples, Sced 0
(b) 1000 samples, Seed
6 a
6 G
A1
0
01
15.3
0.3
5
DS
6
23
0
0203
03
D +
0
S
2: 0.11
21 = 1.
(c) 5000 samples, Seed 0
(d) 5000 samples, Seed
LO
0
0
D.D
0.0
(e) 10000 samples, Seed
(I) 10000 samples, Seed
Figure 13: Learned MSA embedding spaces in the MNIST grid domain for different numbers of samples. 2-dimensional positions are the MSA encodings of input images.
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We show why the Bellman equation suggests that abstract states should be distributions over ground states, provide an algorithm to build an abstract MDP with neural and symbolic components, and apply on different domains.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We put limitations in the appendix due to the space constraints.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
30

---

Answer:
[Yes]
Justification:
Proofs for theoretical results are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Some of the details provided in the main text, and others reported in the appendix. We also provided pscudocodes for the important parts of the algorithm.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
31

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The source code is provided in the supplementary material with sufficient explanation to reproduce the results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc
Gholicc/guddes/Coddeullissssss www.sssinnooiiiylo for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wwtps/cccpbllcggiiiieeeee Ciaeee//CSSSuSbisSS..S.. www.sssoiccgyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Hyperparameter details are provided in the supplementary material together with the source code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We provide two standard errors of sample means which correspond a 96% confidence interval.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
32

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We report the compute resources that are used throughout the experiments in the supplementary file.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http::
Answer: [Yes]
Justification: This paper does not contain any experiments involving human subjects, and the domains use in the experiments are common reinforcement learning environments that does not have any of the data-related concerns mentioned the link.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: While there might be many potential societal consequences of our work, none which we feel must be specifically highlighted here as the proposed work a preliminary stage.
33

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We reference the domains and datasets that are used in the manuscript.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
34

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Important parts of the source code are explained a README file. Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
35

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy httppe///earrrpccccc///oeeeerrre for what should or should not be described.
36


Reviews:
[{"review_id": "kGTFjhNcEB", "reviewer": "Reviewer_KwY7", "summary": "The paper proposes an approach for building a fully abstract MDP from a ground MDP while previous works either focus on action abstraction or on state abstraction only. To cope with this difficult task the authors propose to focus on a strategy that constructs a state abstraction from an action abstraction, for which a number of approaches have been proposed. They generalize their results to the case of factored actions and factored abstract states. Building such MDPs may be viewed as a step towards powerful reasoning machines.\nThe work is validated on a number of tasks that seem to be built for this evaluation so that comparative results have likely been gained with state of the art strategies run (for instance DQN) on the same tasks. Experimental results show significant improvement of the proposed method over the baselines it is compared to.", "questions": "As far as I understand, the peer focuses on the case where one gets a ground MDP and aims at constructing an abstract MDP. Is there any method to directly cope with the construction of an abstract MDP? \n\nShouldn’t the experimental section compare the proposed method with an alternative method (DQN is not such an alternative)?\n\nA number of elements in the method look ad-hoc. How far one needs to instantiate the method to a particular case to get a relevant result?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper deals with a difficult task and does a great job at arguing the choices the authors made to achieve their work and at explaining the method in its details. The paper is very well written and structured. Still some parts remain unclear to me but it is likely because I am not an MDP expert. As far as I understand the peer focuses on the case where one gets a ground MDP and aim at constructing an abstract MDP. Is there any method to directly cope with the construction of an abstract MDP? \n\nThe experimental section does show clear superiority of the method over baseline on a few tasks on evaluation measure but it does not compare to alternate methods for building an abstract MDP. Shouldn’t the experimental section compare the proposed method with an alternative method (DQN is not such an alternative)?\n\nPart of the contributions are actually described in the Appendix. This is the case for instance of Algorithm 1 which nevertheless looks as a main component of the method. Moreover a number of elements in the method look ad-hoc and need to be chosen by hand by the designer. \nFor instance the use of Kmeans (section 3.4) and the use of an auxiliary loss in section 4.2. How far is this true, how far one needs to instantiate the method to a particular case to get a relevant result?\n\nIn appendix C.1 when you detail the use of a classifier two-sample test, is the k-means what you call the classifier? Couldn’t you use a true classifier, i mean a model learned to discriminate?\n\nI am not sure to understand what is given as input to the method in the examples of section 3.4. As far as i understand from the inputs of the algorithm in Appendix (Algorithme 1), all transitions s_i, I_i, \\bar{a}_i, r_i etc are given, meaning the ground MDP?\n\nIn Appendix A.3 are all options defined by hand ? \n\nCan you define what “approximately model-preserving” mean? It is mentioned in the paper (for instance page 1 in the introduction).", "was_revised": true, "final_justification": "I have read the reviewers' reviews and the authors' responses to all the reviews. I'm satisfied with the responses to my comments and those of the other reviewers, which seem convincing to me.\nReading all the reviews/replies, it seems to me that one of the main problems lies in the writing of the paper, with some messages not necessarily sufficiently explicit, and some ambiguities about the notations and the nature of certain variables, which complicate the understanding of the paper. Taking into account all the reviewers' comments according to the authors' answers should significantly improve the paper and this convinced me to increas my score.", "rebuttal": "Thank you for your comments.\n\n**Directly constructing an abstract MDP**\n\nWe understand your question to be about whether it’s possible to construct an abstract MDP without using the ground MDP, specifically, the $(S, A, T, R)$ tuple. It’s worth noting that our method assumes having access to samples from the ground MDP, not the ground MDP itself. As such, the agent does not have access to the explicit forms of the transition and the reward function—they are rather computed from data by taking a weighted average after the abstract states are constructed. We’ll make this point explicit in the paper, thank you.\n\n**Comparison with an alternative method**\n\nTo our knowledge, there is no prior work on constructing an abstract state space that is provably compatible with a given set of action abstractions. As such, there are no similar methods to compare against. The comparison with the de facto value-based RL method, DQN, gives an idea of the overall feasibility and the applicability of the method.\n\n**Some elements in the method look ad-hoc**\n\nWe provided a principled method for building abstract states that are *approximately model-preserving* (see below for the newly added definition). Algorithm 1 sketches this construction with two high-level functions `model_error` and `refine_state`. Our method specifies what these functions should do, but is agnostic to how that is accomplished; any suitable independence test for `model_error` or clustering for `refine_state` will do. Any improvement on the components will improve the overall performance of the algorithm. Though you are right; it would be better to include Algorithm 1 in the main text and we’ll try to squeeze it in in the updated version.\n\n**The use of classifier two-sample test**\n\nWe used the independence test as a proxy for estimating the model error. Any other method can be used as an independence test, including using a learned discriminator as you suggested. We picked k-NN as it happens to be sample efficient and robust, which was also performing better than trained neural nets for estimating the quality of GAN-generated samples in Lopez-Paz and Oquab (2017). Indeed, as mentioned in Appendix C.3, one can use the density loss of the trained MSA network to detect candidate states for refinement, instead of the classifier two-sample test.\n\n**Input to the method**\n\nAlgorithm 1 is for computing $\\bar{s}$ from samples collected by executing options $\\bar{a} \\in \\bar{A}$ on the ground MDP. Therefore, the input to the algorithm is these sample transitions, $(s, \\bar{a}, r, s’, \\tau, I, I’)$, where $\\tau$ is the number of steps taken in executing option $o$, and $I$ and $I’$ are the available actions at states $s$ and $s’$, respectively. Moving Algorithm 1 to the main text per your recommendation will make this point clearer. Thank you.\n\n**Options defined by hand**\n\nIn the paper, options are constructed by hand, but the method would also apply as-is to learned options. We have deliberately chosen to be agnostic as to how the options are obtained, to make our method compatible with any option discovery method—from hand-coded options to skills learned from demonstration to options obtained from unsupervised RL. After reviewer comments, we realized that it would be better to give a further emphasis on this earlier in the text.\n\n**Approximately model-preserving**\n\nIn a model-preserving abstraction, if two ground states $s_1$ and $s_2$ map to the same abstract value, $\\phi(s_1)=\\phi(s_2)$, then their transition distribution $p(s’ \\mid \\phi(s_1), a)=p(s’ \\mid \\phi(s_2), a)$ and rewards $R(s_1, a, s’)=R(s_2, a, s’)$ are equal. In our setting, these are approximately equal up to the errors $\\epsilon_t$ and $\\epsilon_r$. Note that this definition is not original to our work, it is from Li et al. (2006) and Abel et al. (2016). We’ll define this in the updated text. Thank you.\n\n**References**\n\nD. Lopez-Paz and M. Oquab. Revisiting classifier two-sample tests. In *Proceedings of the Fifth International Conference on Learning Representations*, 2017.\n\nL. Li, T.J. Walsh, and M.L. Littman. Towards a unified theory of state abstraction for MDPs. In\n*Proceedings of the Ninth International Symposium on Artificial Intelligence and Mathematics*,\n2006.\n\nD. Abel, D. Hershkowitz, and M. Littman. Near optimal behavior via approximate state abstraction. In *International Conference on Machine Learning*, 2016."}, {"review_id": "ObwIzCefXp", "reviewer": "Reviewer_JuNa", "summary": "The authors propose an approach to construct state abstractions which are then combined with action-abstraction (options) framework in a hierarchical reinforcement learning (HRL) algorithm. The authors provide some empirical evidence of the effectiveness of their approach.", "questions": "What it would take to scale this method up to learning from scratch on Atari?", "limitations": "The method does not seem to be scalable yet.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n* A novel approach for state abstraction which is combined with action abstraction approach in a theoretically justified way\n* Some experimental evidence demonstrating the efficiency of the proposed approach\n\nWeaknesses:\n* Regarding experimental efficiency, it is not fully clear whether this approach actually learns well from scratch on Atari Montezuma Revenge, the authors did not provide any learning curves and comparisons with DQNs. I think generally making options-based agents learning efficiently from scratch is a challenging task.\n* At the moment, state abstraction seems to be using k-means to come up with these, which is quite similar to [1]. I think this hurts the novelty of the proposed approach.\n\nMinor suggestions:\n* I find the notation \\bar{s}' quite confusing, in the text between eq.1 and eq.2. From what I read, `\\bar{s}'_i` is a probability of s' under mixture component i. Maybe you can change  `\\bar{s}'_i` to actually reflect that it is a probability?\n\nReferences:\n[1] Reinforcement Learning with Soft State Aggregation, Satinder P. Singh, Tommi Jaakkola, Michael I. Jordan, NeurIPS 1994", "was_revised": true, "final_justification": "Strong paper. I think the result-wise, the method could benefit from scaling it up, but it already provides a very solid piece of work. Scaling it up could be viewed as a follow-up.", "rebuttal": "Thank you for your comments.\n\n**Scaling up to learn from scratch on Atari**\n\nIn this work, we focused on building a principled state abstraction method and showed in the experiments that it can be scaled up to a 180x240x3 dimensional image-based observations. In *Montezuma’s Revenge*, we are given a set of factored options, and show that the algorithm can build the required abstractions to get the agent out of the first room. You are correct that options-based methods require those options to be given, and that learning them from scratch is challenging. Our method would work better if it was combined with a carefully designed exploration algorithm for learning hierarchical abstractions, which is necessary for any sample-efficient RL algorithm, but we leave that to future work. We believe that such a method would reach the end of Montezuma’s Revenge given the options.\n\n**Similarity to soft state-aggregation-based methods**\n\nWe differ from soft state-aggregation-based works in three main points.\n\nFirst, because their abstraction is a function from the ground state to the abstract, supports of different abstract states cannot overlap. For instance, in a platformer game like Montezuma’s Revenge, jumping to a rope from different sides might result in effect distributions with overlapping supports (in this case, the overlapping part is the agent being on the rope), but the shape of the distribution would be different—it’s more probable that the agent will end up on the rope when it’s jumping from a nearby platform. This is not an edge case that’s specific to the domain but rather a general property that the effects of options would be distributions, and that there is no restriction that would disallow these distributions to overlap.\n\nSecond, their learned abstractions are not tied to any specific semantics of the ground MDP, and thus, can arbitrarily fail to take into account the shape of the ground distribution.\n\nThird, those works are primarily theoretical and do not scale to anything like the 10,000-dimensional state domains we have shown here.\n\nDefining abstract states as distributions over ground states immediately allows the recursive computation of the Bellman equation over the abstract policy. State groundings can overlap and have different density functions. This puts our method in a fundamentally new direction in state abstraction.\n\nBut we agree that Singh et al. (1994) should definitely have been included in Related Work, and will add a citation. Thank you for noticing this.\n\n**Confusion about $\\bar{s}’_i$**\n\nWe realized that there is indeed some confusion as to whether to interpret $\\bar{s}_i’$ as a distribution or a scalar probability, also noted by Reviewer buUR in a different form. We will make this point clear. Thank you for your suggestion.\n\n**References**\n\nS. Singh, T. Jaakkola, and M. Jordan. Reinforcement learning with soft state aggregation. *Advances in Neural Information Processing Systems*, 7, 1994."}, {"review_id": "gBJ3C0Dj79", "reviewer": "Reviewer_zE5e", "summary": "The paper presents an approach for learning neurosymbolic abstract Markov decision processes, develops the mathematical foundations and theory of the approach, applies it to both simple and more complex RL problems in synthetic environments, and shows the advantages over vanilla (purely neural) deep reinforcement learning, as in DQN.", "questions": "Any further information the authors could give that addresses the weaknesses above would be appreciated!", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper is well motivated and clear, but I am not an expert in RL and so I did not even attempt to follow all the technical details.  It appears technically strong, and a solid implementation of a compelling concept.   The results are reasonable. \n\nWeaknesses:  I am not an expert in the paper's area and so I can't really judge the novelty or level of contribution.  But I'm not sure how it fundamentally advances on earlier work such as https://arxiv.org/abs/2002.05518.   To my naive eye, both the present paper and that earlier work learn a distribution-based representation for abstract states.  The present paper adds an extension to consider learning abstract representations defined by options, but I can't tell how much of a fundamental advance that is. \n\nThe paper is strong on theory, but the applications are both quite simple.  The double digit MNIST example is helpful pedagogically but rather contrived; what problems in the real world have such a simple factorization?  The Montezuma's revenge example is more representative of a real world long-horizon planning, but it is still quite simple and the proposed system doesn't solve the whole game from scratch; it starts from a problematic expert policy, and improves it, and it considers only the first room of a long game. The visual maze example is nice, but is still simplified from the real problems of navigation, in ways that play to the algorithm's strength and make it unclear how success there will generalize. \n\nI would also like to understand better how this approach relates to and in practice improves upon other more symbolic ways of learning abstract state and action representations for planning, such as the learned bilevel planners of Silver et al. (AAAI 2022).  That work is briefly mentioned and dismissed here as facing scaling challenges, but it seems that both that work and the present RL-based framework face scaling challenges albeit possibly different ones. \n\nI have to admit that as a non-RL person, I share some of the biases that many people have: RL is nice in theory but just is not a viable approach to building real agents that work in the real world, with reasonable resources.  This paper is elegant but doesn't change my view on this fundamental question, and in some sense only hardens it: we have all this beautiful math, but what does it really buy us?  I recognize this objection may feel unfair to the authors because it targets the whole field of RL, but given the elegance of the work, I feel the authors might be well positioned to answer it.", "was_revised": true, "final_justification": "The rebuttal usefully addresses my comments and I'm happy to raise my score to 5.", "rebuttal": "Thank you for your comments.\n\n**Comments regarding the domains**\n\nThe point of learning neurosymbolic abstractions is to convert an unnecessarily complex representation of a task into a (much simpler) representation that captures the task’s natural complexity. This is what we do with the MNIST grid and Visual Maze: the intrinsic task dimensionality is only a 6 by 6 grid, but we represent it with two 28 x 28 hand-written digits that change at each step, and likewise for the Maze, the most difficult setting is with 180 x 240 colored images (129,600 features) as observations together with distractor portraits hanging on the wall. In each of these domains, our method recovers the simple natural structure of the task and disregards any additional information. We used domains in which that simple structure is obvious to best convey the idea.\n\n**Difference from Asadi, Abel, and Littman (2020) and other soft state-aggregation-based methods**\n\nThey use soft state aggregation (Singh et al., 1995) formulation for the state abstraction and use a neural net to learn these soft weights. We differ from that work in three main points.\n\nFirst, because their abstraction is a function from the ground state to the abstract, supports of different abstract states cannot overlap. For instance, in a platformer game like Montezuma’s Revenge, jumping to a rope from different sides might result in effect distributions with overlapping supports (in this case, the overlapping part is the agent being on the rope), but the shape of the distribution would be different—it’s more probable that the agent will end up on the rope when it’s jumping from a nearby platform. This is not an edge case that’s specific to the domain but rather a general property that the effects of options would be distributions, and that there is no restriction that would disallow these distributions to overlap.\n\nSecond, their learned abstractions are not tied to any specific semantics of the ground MDP, and thus, can arbitrarily fail to take into account the shape of the ground distribution.\n\nThird, those works are primarily theoretical and do not scale to anything like the 10,000-dimensional state domains we have shown here.\n\nDefining abstract states as distributions over ground states immediately allows the recursive computation of the Bellman equation over the abstract policy. State groundings can overlap and have different density functions. This puts our method in a fundamentally new direction in state abstraction.\n\nBoth Singh et al. (1994) and Asadi, Abel, and Littman (2020) are quite related, and we will add them to the related work. Thank you for pointing this out.\n\n**Relation to other symbolic approaches; bilevel planning**\n\nThe abstract state space in the bilevel planning line of works (Silver et al. 2023) is defined over a fixed grammar, and abstractions are learned through program synthesis, i.e., by a search over the language defined by the grammar. As such, this search requires a set of primitives, which can be pre-defined predicates (Silver et al. 2023) or VLM operations (Liang et al. 2025), which is ultimately a heuristic decision on the structure of abstract states and do not provide any formal guarantees to match the ground MDP. On the other hand, our method does not introduce any such inductive biases on the structure of the abstract states while having theoretical guarantees to match the ground MDP. Finally, our method produces a decision process with the Markov property, which supports the Bellman operator, whereas theirs does not have the Markov property and supports only straight-line planning.\n\n**General RL feedback**\n\nThank you for sharing your opinion on this. It’s always nice to have such conversations.\n\nWe agree that naive reinforcement learning is quite sample-inefficient, which is the motivating reason to learn abstractions. Naively training a DQN agent requires too many interactions, and is simply not a viable approach with reasonable resources, as you also noted.\n\nOn the other hand, much of the problem that these methods have arises from the lack of a correct representation. Consider the domains used in the paper. They are simple decision-making problems *once the correct representation is available to the agent*, and this is where our approach kicks in. Now, once you have the action abstractions, you can learn the state abstractions, the form of which aligns with the requirements of value-based RL methods, while using neural nets and still having guarantees on the approximation. This is the first of many papers on this line of work. The only remaining thing would then be learning the action abstractions, which is at least simpler than learning the whole thing from scratch end-to-end. Once this is done, we would have a complete model for planning, effectively converting the RL problem to a model-based planning problem.\n\nDerivations in the paper quantify the degree from which an abstract policy deviates from the ground policy if we were to use these abstractions. It’s reassuring to know that this is bounded by some value, which can be reduced arbitrarily by running the refinement procedure (or with better independence tests and density estimators). In other words, it gives us a way to measure whether the provided abstractions are sufficient. Other derivations verify that we model the correct dynamics in the factored setting. Overall, this type of work gives confidence on the learned representations, helps quantify the error, and makes it easier to figure out the limiting factor.\n\n**References**\n\nS. Singh, T. Jaakkola, and M. Jordan. Reinforcement learning with soft state aggregation. *Advances in Neural Information Processing Systems*, 7, 1994.\n\nK. Asadi, D. Abel, and M. L. Littman. Learning state abstractions for transfer in continuous control. *arXiv:2002.05518*, 2020.\n\nY. Liang et al. VisualPredicator: Learning Abstract World Models with Neuro-Symbolic Predicates for Robot Planning. In *The Thirteenth International Conference on Learning Representations*, 2025."}, {"review_id": "FA4okcG12p", "reviewer": "Reviewer_buUR", "summary": "This paper attempts to formalize the connection between state abstraction and action abstraction, using probability as a language. More specifically, it discusses the conditions under which, given temporal abstraction (i.e., options), one can find a good state abstraction that aligns with the temporal abstraction.", "questions": "Major Concerns:\n- The title, introduction, and abstract do not clearly communicate that by “skill-driven,” the authors assume that options (and their associated initiation sets) are given rather than learned. This is a crucial assumption and limitation. It would be helpful to state this more explicitly in the abstract and introduction, so readers can better understand the setting. Similarly, while the current title uses appealing terminology, it does not set the correct expectations for the paper.\n- Lines 20–21: I disagree with the claim that current HRL does not address state abstraction. For instance, Leslie Kaelbling’s work on task and motion planning includes a hierarchical structure that clearly resembles state abstraction. Similarly, Peter Dayan’s feudal reinforcement learning explicitly tackles state abstraction. Interestingly, in state-abstraction-oriented work, temporal abstraction is often implicitly assumed through the use of macro actions. However, the reverse is not generally true—i.e., options do not necessarily address state abstraction. It’s valuable that this paper explores ways to bridge that gap.\n- It would be enjoyable to see a deeper discussion of the relationship among state abstraction, temporal abstraction, and action abstraction, as the connection is both subtle and important.\n- Line 129: I find point 3 confusing. It seems possible to slightly augment the MDP definition to resolve the issue: assume all options are executable everywhere, but selecting an option outside its initiation set returns a huge cost of -100 and consumes no time. Under this formulation, the learned optimal policy should remain the same. Therefore, I do not fully understand why point 3 must hold in order for the process to be Markovian.\n- Definition 1: The functions p and I depend on the policy in the previous state. This policy dependency could introduce complications, but it appears under-discussed in the paper. Does this dependency play an essential role?\n- Figure 4: I’m confused as to why DQN with hindsight experience replay fails to improve. Its performance seems unchanged from 1K to 10K steps. Why?\n\nMinor Concerns:\n- It’s a bit confusing that Equation 1 uses “≈” while Equations 2 and 3 use “=.”\n- In Section 3.1, it took me some time to realize that S is being treated as a distribution, which is a shift from how it is handled in Section 2. Although this is mentioned later in the text, it may be helpful to introduce this point earlier—perhaps around line 108—so that readers are better prepared for the formulation that follows.\n- Definition 1: I initially interpreted p as a scalar, likely due to the presentation in Figure 2b. But just to confirm—it’s a density, correct?\n- Figure 3b: Why do some of the distributions in the middle appear multimodal?", "limitations": "Yes, but in the appendix. Also, I think some of the theoretical downside (e.g., the connection between state abstraction, temporal abstraction, and action abstraction) is not discussed in detail.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Bridging the option framework to state abstraction is an important goal that has not yet been fully achieved. The approach in this paper is original, and the use of probabilistic state representation is very interesting. It makes a significant and original contribution, and I enjoyed reading it.\n\nMost of my concerns are related to clarity. I’ve outlined them in the Questions section below.", "was_revised": true, "final_justification": "I think it’s a good paper. My score remains unchanged.", "rebuttal": "Thank you for your comments.\n\n**Title, abstract, and intro do not clearly communicate that skill-driven means given options**\n\nWe stated in the abstract and the introduction that we consider constructing state abstractions compatible with a given set of abstract actions, though we might have failed to convey the idea that this approach is fundamentally predicated on the availability of such options, or the importance of this point. We’ll further emphasize this in the introduction.\n\n**Re: Lines 20-21, disagreement with our claim that current HRL does not address state abstraction**\n\nYou are right that some earlier hierarchical RL methods (Dayan and Hinton, 1992; Kaelbling 1993; Dietterich 1999) consider a set of state abstractions together with hierarchical actions. While these works also do not focus on learning those state abstractions, our original intention was to refer to works that discover options but do not utilize them for state abstraction (Bacon et al. 2017; Barreto et al. 2019; Machado et al. 2018; Bagaria et al. 2019). Though, re-reading the text, we agree that it is understood as there were no such works, and that we forgot to mention those earlier works as well. We’ll rephrase this statement and explicitly reference them.\n\n**Discussion on the connection between state and action abstraction**\n\nIt would definitely be on point to discuss the connection between state and action abstractions in detail. We had to cut off some parts to squeeze in the figures, but we plan to discuss this in the final version. In general, our approach is motivated by the intuition that options are necessarily more constrained than state abstractions—options have a closed-loop interaction with the environment, whereas an agent can hypothesize any state abstraction it wishes—and that combined state-action abstraction should therefore be driven by the properties of its options, with the more flexible state abstraction constructed to match. We will discuss this in more detail in the final version.\n\n**Line 129, point 3, availability of actions everywhere**\n\nIn the most general definition, actions might not be available everywhere. From Reinforcement Learning 2nd ed. Sutton and Barto (2018), pg 48:\n\n> Footnote 3. To simplify notation, we sometimes assume the special case in which the action set is the same in all states and write it simply as $\\mathcal{A}$.\n\nsuggesting $A(s)$ as the general case. That is why we start with $A(s)$ as one of our three target properties. However, the formulation works in the special case where actions are executable everywhere since the refinement process can take care of that (and your suggestion of negative rewards would probably make it easier to work by introducing $\\epsilon_r>0$ for those states)—and actually, the experiments in the MNIST grid and the Visual Maze assumed that actions are available everywhere for a fair comparison with the Stable Baselines 3 implementation, which we’ll mention in the updated text. There, the initial abstract MDP consists of a single abstract state that subsumes all states and is refined until a certain threshold is met. Thank you for your suggestion.\n\n**Groundings depend on the policy in Def. 1**\n\nThe learned groundings definitely depend on the given options, and in a setting where we learn action abstractions and state abstractions in turns, this would indeed create a complexity. As such, we stand in the position that action abstractions should precede state abstractions.\n\nRegarding the high-level policy (i.e., the exploration policy), we do not think, barring small-sample effects, that it would affect the groundings directly since the termination distribution of the options would stay the same. However, depending on the implementation of Algorithm 1, especially `model_error` and `refine_state`, some abstract states might be of poor quality, or not learned, if they have low visitation counts. Thank you for pointing this out; we’ll clarify it. \n\n**Why DQN with HER fails to improve**\n\nIt’s possible that DQN would improve with a better hyperparameter configuration. We didn’t make an extensive hyperparameter search apart from trying some variations with an educated guess. Upon this comment, we re-run the script with more samples, and DQN achieves around 0.5 with 15K samples, and around 0.6 with 20K samples, which is two times longer on the x-axis than our current graph.\n\n**Minor concerns**\n\nRe: Using = in Equations 2 and 3\n\nYou are right, Equations 2 and 3 are actually approximations due to the expected-length model (Abel et al., 2019). We’ll fix this. Thank you.\n\nRe: S treated as distribution in Section 3.1\n\nAfter re-reading the text, we realized that there is some ambiguity to whether we refer to a single probability or a density. For instance, $T(s’ | s, \\bar{a})$ can be interpreted as a single scalar referring to the probability of transitioning to a certain $s’$ or a density of $s’$, which might be related to the confusion on Def. 1 as well. Thank you for pointing this out; we’ll make a thorough pass on the used symbols.\n\nRe: p scalar or density in Def. 1\n\nYou are correct that $p_i$ in $\\mathcal{G}_(\\bar{s}_i) = p_i$ is a density whereas $p$s in Figure 2b are scalars, showing how a single distribution can be dissected into a mixture of multiple distributions. We’ll clarify this, thank you.\n\nRe: Figure 3b: multimodal distributions\n\nWhile the ground distribution is over 28x28 sized images, we visualize them a bit differently. Each sample is assigned with a position equal to its digit plus some noise. Then, to visualize each abstract state, we fit distributions to those position values. While we thought about visualization alternatives that are more faithful to the original semantics of abstract states (e.g., t-SNE), we picked this one as it’s the most pedagogical one. We’ll update the caption accordingly or find some other way to visualize them.\n\n**References**\n\nP. Dayan and G. E. Hinton. Feudal reinforcement learning. *Advances in Neural Information Processing Systems*, 5, 1992.\n\nL. P. Kaelbling. Hierarchical learning in stochastic domains: Preliminary results. In *Proceedings of the Tenth International Conference on Machine Learning*, 951, 1993.\n\nT. Dietterich. State abstraction in MAXQ hierarchical reinforcement learning. *Advances in Neural Information Processing Systems*, 12, 1999.\n\nP. L. Bacon, J. Harb, and D. Precup. The option-critic architecture. In *Proceedings of the AAAI Conference on Artificial Intelligence*, 31, 2017.\n\nM. C. Machado et al. Eigenoption Discovery through the Deep Successor Representation. In *International Conference on Learning Representations*, 2018.\n\nA. Barreto et al. The option keyboard: Combining skills in reinforcement learning. *Advances in Neural Information Processing Systems*, 32, 2019.\n\nA. Bagaria and G. Konidaris. Option discovery using deep skill chaining. In *International Conference on Learning Representations*, 2019."}]

Author rebuttal:

Meta-review: The reviewers all agreed that this work is interesting, technically novel, well-written and that it addresses an important problem (constructing abstract MDPs). It seems to fill a gap in the existing literature, which is to learn state abstractions while being given abstract actions. The empirical results, while not impactful or interesting per se, serve to at least somewhat validate the central claims.

The reviewers have done a good job of highlighting several weaknesses in the paper, many of which the authors have addressed in the rebuttal/discussion.

Overall, the combination of a strong algorithmic contribution combined with a well-executed scholarship lead me to recommend acceptance.
Decision: Accept (poster)