Optimistic Exploration in Reinforcement Learning Using Symbolic Model Estimates
Authors: Sarath Sreedharan
Michael Katz
Venue: NeurIPS 2023 poster (2023)
Keywords: Planning
Reinforcement Learning
Exploration

Abstract: There has been an increasing interest in using symbolic models along with reinforcement learning (RL) problems, where these coarser abstract models are used as a way to provide RL agents with higher level guidance. However, most of these works are inherently limited by their assumption of having an access to a symbolic approximation of the underlying problem. To address this issue, we introduce a new method for learning optimistic symbolic approximations of the underlying world model. We will see how these representations, coupled with fast diverse planners developed by the automated planning community, provide us with a new paradigm for optimistic exploration in sparse reward settings. We investigate the possibility of speeding up the learning process by generalizing learned model dynamics across similar actions with minimal human input. Finally, we evaluate the method, by testing it on multiple benchmark domains and compare it with other RL strategies.

Optimistic Exploration in Reinforcement Learning Using Symbolic Model Estimates
Sarath Sreedharan Department of Computer Science Colorado State University
Michael Katz
IBM T.J. Watson Research Center mi michael katzk0i 0m...00mmmm..m...mm...m.. com
ssreedh33@colostttee
Abstract
There has been an increasing interest in using symbolic models along with rein- forcement learning (RL.) problems, where these coarser abstract models are used way to provide RL agents with higher level guidance. However, most of these works are inherently limited by their assumption of having an access to a symbolic approximation of the underlying problem. To address this issue, introduce new method for learning optimistic symbolic approximations the underlying world model. We will see how these representations, coupled with fast diverse planners developed by the automated planning community, provide us with a new paradigm for optimistic exploration in sparse reward settings. We investigate the possibility speeding up the learning process by generalizing learned model dynamics across similar actions with minimal human input. Finally, evaluate the method, by testing it on multiple benchmark domains and compare it with other RL strategies.
Project Website: https: model -earn. Zearn.githul -itgggtth........ io/
Introduction
popular trend in recent years using symbolic planning models with reinforcement learning (RL) algorithms, Works have shown how these models could be used to provide guidance to RL agents [37 26 12). to provide explanations [33], and as an interface to receive guidance and advice from humans (II. Coupled with the fact that advances in automated planning has made available number robust tools that RL researchers could adapt directly to their problems (cf. [I] 31), these methods have the potential to help addressing many problems faced by state-of-the-an -f--t---tttttttto-- RL methods. However, a major hurdle to using these methods is the need to access a complete and correct symbolic model of the underlying the planning community to learn such models [99 38 most of those methods have focused on cases where the models synthesized from set of plan traces, hence corresponding to the traditional offline reinforcement learning setting. Interestingly, very few works have been done in synthesizing such models in the arguably more prominent RL paradigm, namely, online RL.
problems. While there have been efforts from
To fill this gap, in this paper propose novel algorithm to learn relevant fragments of symbolic models in an online fashion. show how could used to address one of the central problems within RI., namely effective exploration. We show how our method allows us to perform goal-directed optimistic exploration, while providing rigorous theoretical guarantees. The exploration mechanism leverages two distinct components: (a) representation that captures the most optimistic model that consistent with the set of observations received, and (b) the use of a fast and suboptimal diverse planner that generates multiple possible exploration paths, which are still goal-directed.
The idea of optimistic exploration is not new within the context of RL. The most prominent method being the RMax algorithm (5). RMax modifies the reward function to develop agents that are optimistic under uncertainty. Our use of symbolic models, however, allows us to maintain an optimistic hypothesis regarding the underlying transition function. Coupled with goal-directed planner, this lets us perform directed exploration in sparse reward settings, where we have clear
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

specification of the goal state but no intermediate rewards. As we show in this work, for finite state deterministic MDP our method is guaranteed generate goal-reaching policy. Additionally, we investigate the use of a structured form of generalization rule that leverages very simple intuition, namely the effects of an action don't depend on specífic object labels but only on object types. Commonly referred to as lifted representation in planning literature, we show this rule to speed up learning with minimal human input.
The rest of the paper is structured as follows. We start with related work in Section 2 Section 3 provides a formal definition of the exact problem we are investigating and Section 5
shows the empirical evaluation of our method against a set of baselines. Finally, Section 6 concludes the paper with discussion of the methods and possible future directions.
2 Related Work
As mentioned earlier, one of the foundational works in optimistic exploration in the context of reinforcement learning is R-max [5]. Even before the formulation in its current popular form, the idea of optimism under uncertainty has found several uses within the RL literature (ef. (20). R-max can be seen as an instance of a larger class of intrinsic reward based learning (2). but one where the reward is tied to state novelty. Other forms of intrinsic rewards incentivizes the agent to learn potentially useful skills and new knowledge. A context where model simplification has been used in areas related to RL is in the context of stochasticity, where methods like certainty equivalence and hindsight optimization has been applied [ 40). In Section 66] we will see how we can also apply our methods directly in settings with stochastic dynamics. In regards to the user of symbolic models, the most common use is in the context of hierarchical reinforcement learning. Many works [26 17 337 (27), have investigated the possibility of using the symbolic model to generate potential options and then using a monta-cnntrlller to learn policies over such options. While most of these work assume that the model in someway an approximation of the true model, all inferences performed at the symbolic level is performed over the original model provided as part of the problem. While in this work, we focused on cases where the symbolic model could in theory exactly capture the underlying model, the same techniques can also be applied to cases where the planning model may represent some abstraction of the true model. Another popular use of symbolic model is as source of reward shaping information (cf. [12). In this context, works have also looked at symbolic models as a vehicle to precisely specify their objective [16] [3]. In terms of learning symbolic models, interestingly the work has mostly focused on learning plans execution traces [38 19 6 9
In this context, it is worth noting and contrasting our proposed work with the ones focused on learning safe models [34 19 18 (28). Safe models are defined to guarantee to only generate valid plans. This an important theoretical guarantee to have if the learned model is the only source of information about the plans, or the cost of executing an invalid plan may be extremely high (e.g., because of dead-ends that might leave the Al agent stuck or if there are safety implications related to executing an incorrect action). In practice, this means learning pessimistic planning models, i.e., models that support only a subset of all possible valid plans. As we move from an offline setting to the more popular online one, such pessimism can become a burden rather than a strength. In the online setting, the agent is expected to have access to simulator of the world, or the agent allowed to make mistakes as part of its action execution without any irreversible damage. This means that the agent is free to try out different things until it finds a plan that works. Such methods naturally lend themselves to the use of optimistic planning model that supports super-set of possible plans.
In most of these works, the theoretical guarantee you aiming for is to generate more pessimistic models that are always guaranteed to work but may overlook plausible plans. This is completely antithetical to considerations one must employ when performing explorations in common online RL settings, where the agent is either operating in a safe environment or interacting with a simulator. To the best of our knowledge, all existing online methods to acquire symbolic models 7 24. focuses on extracting an exact representation of the true underlying model. Since our primary motivation for learning this model to drive the exploration process, we do not have that limitation. Instead, we focus on learning a (more permissive) optimistic approximation. Also, it is worth noting that, the assumption that the system will be provided action arguments (something we will leverage to generalize learned dynamics) is one commonly made by most of these works. There are also some works that are trying to automatically acquire abstract symbolic models from an underlying MDP (including potential symbols) like that by (2). This direction is orthogonal to our work, symbols
2

---

produced by them may be meaningless to the human and we are explicitly trying to leverage human's s intuitions about the problem.
3 Problem Setting
3.1 Deterministic MDP
The central problem we are interested in addressing is that of an RL. agent trying to come up with a policy for deterministic MDP with sparse reward. We specifically chose a setting, which forefronts the problems related to exploration, while placing less emphasis on other aspects of an RI. problem (though in Section 6 how one could easily apply this approach to other settings). In particular, the underlying model (which is unknown) is assumed to be of the form M = (S, T', A, I, H, 7). Under this definition, S is a finite set that represents the set of possible states that the agent could find itself in. We will assume that this set includes special absorbing state 1 E S, allowing to capture both abnormal and normal trace termination. Additionally, there is a subset of states S C S. which correspond to 'goal' states, which are desirable states for the agent. A is the set of possible actions and given the deterministic nature of the problem. the transition function is specified as T S x A x S + (1,0}. We will refer to the action that transitions from states in 5 to the absorbing state 1 as the goal action (a.), Given that we are interested in sparse reward setting, we will define the reward function as R(s, a ( = 1 if 8 E 5 and s' = 1 and 0 otherwise. Finally, Y is the discount factor. Note that our work can support cases where the discount factor is equal to one.
We will refer to the transition to . through a non goal action, as a failure transition. Now, I E S captures the initial state from which the agent starts. To enumerate the implications of the design choices we made in picking this model, consider the fact that reward is zero everywhere except for the goal. This means that any policy that can help reach the goal from the initial state, would be optimal for the agent (since the agent always starts from the initial state). Coupled with the fact that the transition function is deterministic, once the agent identifies a goal state, constructing an optimal policy is relatively easy they can just reuse the path taken by the exploration strategy. Now, this setting also renders most existing methods that may use intermediate value bootstrapping or generalization mostly ineffective there are no intermediate values use. So it makes sense to focus on tabular methods as the RL baseline, In fact, possibly the only effective methods in the mainstream RL repertoire we can use are curiosity driven or intrinsic reward based methods and we will use such a method as a baseline. One of the central components we will leverage are state action traces we can sample from the underlying model. In particular, we say that trace (50: 01 Qg. Sgy ak+1, Sk+1) is valid or equivalently goal-reaching if so = I, S E Sc, $k+1 = L. and for every 0 S i < l we have T(s a++1, $1+1)= O. The action a++1 is the goal action.
In the course of discussion, we will use the word 'original model' to refer to this true but unknown underlying MDP. The agent itself is expected to be either interacting with a generative simulator that encodes this MDP or is acting in the true environment provided that they can reset to the initial state at the end of each episode.
3.2 Symbolic Planning Models
For the symbolic model, we will be using an a representation scheme called Planning Domain Definition Language or PDDL. In particular, we will consider a version that will ignore object types [1]. Here, a planning task is defined in relational terms, i.e., states are described in terms of objects and relationships between objects and each action is described in terms of the objects involved in that action and how they may affect or be affected by the relationships between these objects. Such model is usually defined by the tuple MS O,, I, G), where L is first-order language, O finite set of action schemas, 7 and G are specifications of the initial state and the goal, respectively. The first order language describes the objects and the relationships between these objects (captured as predicates). Additionally, first order language allows specifying predicates over variables as well as actual objects. Formally, the first order language is specified as L (B, V, P), where B is the set of all objects, V are the variable names and P are the predicates. Each predicate p E P. will take a fixed number of arguments. For the purpose of discussion in this paper, we will either have cases where the arguments consist of only variables or only objects. We will refer to the former case as being the lifted representation of the predicate and the latter as grounded instance of the predicate (or ground predicate). In general, however, predicates can be partially grounded, with some of the arguments being actual objects while others being variables. States of the model correspond to truth assignments to ground predicates. Each ground predicate can take either true false value. Each
3

---

possible state for given model is captured by a specific instantiation of all ground predicates. Thus, possible states can be uniquely represented by sets of ground predicates that are true (assuming the rest to be false under the closed world assumption). In this representation, 7 denotes a set of ground predicates, capturing the unique initial state. For our purposes, G will be captured by a subset of ground predicates, denoting all states where all of these ground predicates (and possibly some more) are true. All such states will be considered valid goal states.
Each action schema o E O provides the basic structure shared by set of ground ac- tions that can be actually executed by the agent. Each action schema is defined as o = (params(o) (o), pre(o), (o), del(o)), where params(o) indicates the parameters of the action schema (variables and objects), the preconditions (o), the add-effects add(o), and the delete- effects del(o). The latter three are first-order formula over the language C, specifying the conditions that must be satisfied for the action to be executable in a state, as well as the change in state resulting from executing the action. Ground actions are obtained from the action schema by assigning objects to variables in the parameters. The agents are executing the ground actions and therefore it is common to describe the semantics of ground actions, henceforth simply referred to as actions. In this work we restrict ourselves to preconditions in disjunctive normal form. For ground actions these would be disjunctions of conjunctions of ground predicates. All states which the formula holds, the action is applicable. The add/delete effects are conjunctions of ground predicates, making these predicates true respectively false in the state resulting in successful action execution.
For a given action schema o, we will denote the grounded instance obtained by replacing the parameter with an object list θ using the function symbol (o, θ). We can also define an inverse mapping function X (oto, +) that retrieves the lifted model given a grounded instance (we can do this by replacing all instances of an object with a variable). This lifting function A well defined in all cases where we don't have repeating object in O In this particular work, we will only focus on applying such lifting functions in cases where they are well defined. Overloading the notations bit, we will also apply the functions I and Xt, to create grounded and lifted instances of predicates as well. Each planning problem can be represented equivalently in a grounded form as M2 = (F) A4, I, G), where F2 consists of all grounded predicates and A grounded actions. At most this model may have 2 Pill states. A solution for planning model is a plan π = {a1, .... an). which is sequence of action whose execution in initial state will lead to a goal state, i.c., (() 2 G
(where 7 (1) an (u....a, (I)))
3.3 Connecting the Symbolic Model to the MDP
For any given deterministic MDP M of the form defined in Section 3.1 there must exist a symbolic model that can exactly capture the MDP. In particular, there a surjective function (many-to-one mapping the (ground) actions in the symbolic model to MDP actions. Every plan under the symbolic model maps by this mapping to a valid trace of the MDP. The appendix include a proof that shows by construction how such a model will always exist. However, rather than creating an arbitrary mapping to a symbolic model, we are interested in creating one that leverages the expertise a human domain expert to creating a potentially more effective representation of the problem. In particular, we start by taking human input to learn how to symbolically represent the states of the MDP. In particular, we expect the human to specify a set of predicates and objects that they might associate with the given problem. We use the symbol Ff to capture the set of all ground predicate possible under this specification. Similar to previous explanatory works 33 32 21 that have tried to learn symbolic representations of RL problems, we use this to learn binary classifier that test whether ground predicate may be true in given MDP state. We can learn such classifiers by collecting positive and negative examples for each ground concept. Once the classifiers are available, we can construct the symbolic state corresponding to each MDP state, by testing each classifier on any given MDP
way to capture the mapping between the states. For potential actions, we assume that every symbolic ground action corresponds to exactly one action in the MDP. Overloading the notations bit, we use (a)( to represent the MDP action corresponding to the symbolic action a. As we will see later, the agent can also potentially leverage the human's ' intuitions about how they structure actions to further improve the effectiveness of our method. Finally, we expect the human to provide a specification of the goal states specified in terms of the ground predicates in Ff. We denote this goal specification by GC Additionally, we require that the initial state for the symbolic model corresponds to C(T) and for any goal state 8 E Sc. C(s) satisfies G (or, equivalently, there is symbolic goal action whose precondition meets this requirement).
state. We use the function C: S + 2

---

4 Our Approach
The basis of our approach is observation that every deterministic MDP has a precise symbolic representation. By precise representation, we mean that for the specific setting we consider here, there exists symbolic model that can exactly simulate the MDP: any transition possible under the sym- bolic model must correspond to non-zero proba- bility transition possible under the MDP and vice versa. However, as discussed, objective is not to learn such precise representation but rather only to learn an optimistic approximation. We start from trivially optimistic representation of the underlying model, which we iteratively refine towards the true representation. At each iteration, the current sym- bolic representation is used generate potential plans to the goal. These plans are then tested out in the environment and the observed outcomes of the execution of such action sequences are then used to refine our estimate towards the true representation. At every point of our model refinement process, we ensure that every subsequent model estimate generated is an optimistic one. By maintaining the optimistic nature of the representation, we ensure that potential valid solution is overlooked at any point in the learning process. So we will start the discussion of our approach by providing rigorous definition of what we mean by an optimistic repre- sentation. In particular, we interested in creating symbolic representations that allow all valid traces that are possible under the original MDP be pos- sible under the new representations. Formally, we define this requirement
Algorithm 1 Iteratively refine the model until a goal reaching trace is found
Inpur:Mo;
Outptt: An action sequence (a1...,ss az) that will
lead to the goal
Procedure:
Moure + Mb
Execution_statistiee < O). solvability flag True
while solvability_Alag is True do
PruneModel(MMaury execu- tion_statiin sta__sttissics)
Meuer <
<- DiversePlaner(MMeurn,
[ > Oten
for ã E i1 do
if leads to goal the environment then return
else
Meure, exccution_statisties UpdateModell
exccu-
tion statistics)
end if end for clse
solvability_ flag
False
end if
end while
return No policy with non-zero Value
Definition 1 For an MDP model M, a symbolic model M defined over symbol mapping C(-) is said to be an optimistic representation, for every action sequence {aI,..., az) such that there exists a valid trace (i.e. it reaches goal), there exists valid plan in M of the form π ={a (ai:..., "ci::..,.)))) ag)) such that C (a,) Og.-
For the given set of grounded actions A and a grounded set of predicates Ff. we can create a symbolic model that is guaranteed be optimistic for any MDP whose action set isomorphic to AC and the state space can be represented using Ff. In particular, the model will have empty preconditions and delete effect and the add effects would correspond to the set of all ground predicates. This means that every action is executable in every state and an execution of any action will satisfy the goal. We will denote this model as MM = (Pf, AÇ, 1 G.). More formally, every action E Aç will be defined as follows: a (preğ, add% dela), where preş del 0 and add; Ff. The fact that its an optimistic representation for any MDP possible in this context can be trivially proved (Proof is provided in the appendix).
4.1 Refining the Model
Now, of course, while all valid traces for the original model correspond plan in My. the symbolic model may also support plans that may not correspond to any valid trace in the original model. Our basic strategy would be use this model as a starting point to sample potential plans, simulate/execute them in the environment or simulator and use the outcomes (both successful and failed executions) to refine the current the current estimate. We will continue this process until we find a plan that leads us to the goal. Keeping this general approach in mind, the next step would be to define our model update rule. particular, let us assume that we receive the following observation from the environment (s, s"), such that s' * 1. Now we know this corresponds to the symbolic observation
5

---

(C(s), C(a),C(s)) Given this observation, we know that any changes made in the state must be the result of the action. We will use this information to update action's 's effects. For add effects, the estimate previously had hypothesized the action making predicate true, which doesn't 't hold in C(s') then it can be removed from the add effects. Similarly, if there was predicate that is made false in C(s) but was not part of the delete effects, it can be added to the set of delete effects. Formally, we can set the new estimate of the action as follows a = {pre add i+1: del;+1) 1). where pref+1 følØ E prej and S C(s)} and for effects we have add;++ 1 = add;; \\ (FF \ C(s) )) and deli+1 = det;; U
If the sampled transition corresponds to failure ((s, a, -)), we will only update the precondition. Specifically, we will remove any precondition clause that satisfies the state and replace it with a set of preconditions that includes one of the predicates that was false in the model (this follows from the fact that the action failed because some predicate part of the true underlying precondition wasn't 't true in the given state). More formally, for any Φ E pref, such that é C ((s), we remove o and add - = fo U flf E (Ff ((s))). The proof for why this update rules result in optimistic representations are provided in the appendix.
4.2 Overall Algorithm
presents the overall iterative algorithm we will be using to identify the action sequence that can lead to goal state. The algorithm starts with the initial estimate of the model. It iteratively generates plans for the model estimate, which will then be used to progressively refining the model until we get a plan that corresponds to a path to goal state. These plans are derived using a diverse planner that identifies a set of plans that are diverse in terms of the actions used. This is represented by the procedure DiversePlanner that takes the number of diverse plans to be generated an argument (x)). Readers can check [22) for a more detailed discussion of diverse planners. These plans are first tested on the underlying eivironment/simllaoo to check whether they lead to the goal from the initial state and if not the experiences sampled from their execution are used to refine the current model. Note that, given the optimistic nature of the model estimate, the planner would generally try to use actions that haven't It been previously executed successfully. However, each future use of the action would become progressively harder due the growing precondition set. With that said, one could further improve the planner behavior by being more careful about the actions being used as part of plans. If an action has been tested quite frequently, it would be better to de- ce-piooritize its usage until no better alternative has been found. Note that this is quite similar to the kind of exploration performed in the context of multi-arma select the action sets to be considered by the planner. This part of the algorithm is captured by the procedure Mrdne To keep our implementation of the approach simple, we will use a simple queue based system to identify the actions to be included. The exact procedure we use to control the selection of actions described in the appendix. The variable execution stttttiiootstttticssss keeps track of previous action trials and the frequency of success per action. The procedure UodateModel uses the rules described in Section 4.1 to use the sampled traces to update the given model estimate. One could also further improve the efficiency of the search by always testing all possible actions in every new state that is identified as part of the procedure.
Algorithm|
I
bandits (25). In fact, one could directly apply methods like UCB (3] to
Theorem Algoritium | will (a) terminate in finite number of steps and (b) identify path to goal (provided one exists); as long as the diverse planner used is complete (i.e., it will return a non-empty plan set as long as there exists a valid plan).
The proof for the theorem is provided in the appendix.
Leveraging the Exploration Strategy in the Context of RL algorithms: In the context of the overall RL learning process, this exploration method will be used as a way to update the Q values (and depending on the algorithm, structures like replay buffers). Specifically, we will first run this exploration procedure to find a valid trace to the goal. Once such a trace is found, we can update the Q values of all the states that part of that trace to more informed value. Once updated, we can employ traditional RI. algorithms to identify optimal policies. One could also leverage the proposed method in conjunction with other exploration strategies, during the learning process. It is important to note that any consecutive use of our approach for generating goal directed paths would be much more efficient, as the method will start from a more refined estimate of the model.
Leveraging Lifted Representation The algorithm described above tests each of the available actions to learn a symbolic model corresponding to the observed behavior. However, one of the important points to note here is the fact that this means that the testing and by extension learning of the

---

model occurs at the level of ground actions. As we had discussed earlier, a very common assumption made throughout symbolic models that of the existence of a lifted representation of actions. Namely, the fact that the nature of actions could be described independently of the exact objects it may be interacting with. This is very natural outcome that comes out of relational representations of tasks, where the state is represented in terms of objects and relationship between objects. Consider simple domain where a robot is tasked with stacking blocks on the table (popularly called blocksworld (35)). It is very easy to see that the outcome of picking up the red block should be quite similar to the case of picking up the green block of the same size. For example, if we observe that the execution of the action 'pick-up red block' results in the agent holding the red block in it's gripper; then it would be quite natural to assume that the execution of 'pick-up green block' should result in the agent holding the green block. We will leverage such symmetry by asking the human to provide some additional information about each action. Specifically, the human can provide us a basic annotation over what actions could share lifted structure and what objects each actions might interact with. Note that we are not asking the users to specify what the lifted structure may be, but just a grouping of actions and an ordered list of relevant objects. The order may reflect the different roles played by the objects participating in the action. For example, when an object is being placed on top of another, the annotation may list the destination object first and then the object being placed on top of it. The exact ordering wouldn't it matter provided they remain consistent through the annotations. Additionally, even if the grouping provided by the human may be a subset of the true possible grouping and the human provides a superset of the objects relevant to any given action, our generalization approach remains valid. The set of objects associated with each action could also be automatically extracted from natural language descriptions of actions, as performed by works like that by [10].
For a given set of actions that are marked as being grounded instances of the same lifted action, we will ensure that learned effects of all actions comply with the most refined action in the set. As discussed earlier, the effects of an action comprises of add and delete effects and for each component we can select the most refined set independent of each other. From the set of effect descriptions, we select the add effect set containing the minimum number of elements and the delete effect set containing the maximum number of clements. For each such set, we can create the lifted description using the X function described earlier. Let min __ndd be the lifted description corresponding to the smallest set of adds and max_ _del be the largest set of deletes for given set of actions corresponding to the same lifted action. Then we can simply replace the effect of every action with a grounding of these lifted actions. This will still result in an optimistic model description, as can show that the min add and max del are still optimistic estimates
Let Ā= (u., action at. Then min add must be a superset of add effects of al and max_ del a superset of deletes af where min_ add and max_ del are calculated for A
Proposition 1
um)) be a set of actions marked as being instances of single lifted
The proof for validity of this proposition is discussed in the appendix. This proposition now means that, once max_ del and min_ _dd are identified, then for every action a in the set of possible groundings we can replace add effects and delete effects with the corresponding grounding of the lifted effects, i.e, add = I't (min_ _ddd__dd____ θ*) and del" = I't (max del, θ*), where O is the object list corresponding to the action a. One can follow similar lines of reasoning to show that the lifted description of the maximal precondition description is guaranteed to entail the true preconditions.
Lifted Representation as a Basis for Curriculum Learning. While the above discussion focused on leveraging lifted representation speed up learning within a given planning problem, one could also use lifted representations as basis of transferring model information from one problem instance to another. Within classical planning problems, it is very common separate the domain information represented in lifted terms from specific problem instances. Each problem instance could differ in terms of the number and identities of objects involved, the initial and goal state. However, actions applicable in every instance share the same lifted definition. Even within RL, benchmarks consisting of various instances of the same problem domain are becoming more popular (Minigrid [8] being a popular example). When such a suite of problem instances are available, one could further speed up learning by using the smaller instance to learn as much of the lifted model as possible. Once such a partial lifted model is learned, it can then be used to refine the optimistic model in the target problem, where the normal learning process then takes over. Note that the access to a smaller problem instance doesn't obviate the need to perform learning in the true underlying model. After all, in the smaller problem there may be lifted actions that may not be executable in any of the reachable states, but needs to be used in the target problem to reach the goal.
7

---

5 X 5
6 X 6
8 X 8
16
16
Cumullative Reward: Gym MiniGrid DoorKey 5x5
Cumulative Reward: Gym MiniGrid Doorkey 6x6
G-Hearning-plarriigg
O-leaming-planring
Q-learning
Q-leaming
Cunulsive Rewerd
0.6
Cunulative Raward
0.6
0.4
0.2
0.0
0.0
Episade Numbar
Number
Cumulative Gym Doorkey
Gym MiniGrid DoorKey
0.5
O-learning-llaningg
Q-leaming planning
D-learning
leermin
0.4
0.6
0.3
Cumulativ
0.2
Cumulstive
0.1
0.0
0.0
-0.1
-0.2
450
Episode
Episode
Figure 1: Four minigrid maps considered and the cumulative rewards per episode comparing our method to vanilla RI. The values plotted along with their 95% confidence interval.
Evaluation
We perform our evaluation in four different domains. Three of these correspond traditional planning domains and one a more traditional reinforcement learning benchmark. The planning benchmarks include blocksworld, a simple gridworld type domain involving robot picking up objects and domain where the agent has to control elevator schedules. For the RL domain, we looked at two variants of minigrid problem. One was the version introduced by (26] (henceforth referred as Minigrid- Parll and the other being simplified version of the original minigrid testbed [8] We chose to use the Minigrid- since it provided us with annotations that allowed us to use hierarchical RI. methods. For the latter variant, we dropped the turn action and introduced directional movement, pick up, drop and toggle actions. This allowed us to use simpler PDDL formalisms to capture the domain. For each planning domain, we selected five different problems (the sizes are approximately listed in the tables in terms of the number grounded predicates) and two problems the minigrid domain. We created simulator wrapper around PDDL models for each of the problems, as it allowed us easy access to the annotation information for lifting. For the minigrid problems, we auto generated PDDL problem files from the simulator code for each specific environment. he code can be found at https:/ //ti thub. com/ htts//arrtheeeharrre wwwaaaaeoooeaarraaeeeee
5.1 Reaching Goal States
As first step, we are interested testing how our proposed method compares against standard exploration strategies used by RL algorithms. In particular, we compare our method against three baselines:
vanilla e-greedy exploration (as implemented by the SimpleRL framework [[] as part of the Q learning agent), R-max based exploration strategy (again taken from the SimpleRL. framework), which as we discussed form of intrinsic reward, and hierarchical RL. method that learns a policy over SMDP using PPO (as implemented by (26) on instances from Minigrid-PAN -PRR..

---

greedy
Our method
Our method
Problem Instance
(wlo lifting)
(with lifting)
Name
Size
solved
time
# samples
solved
time
samples
solved
time
samples
9164.2
19262
592
25
11.35
115136.8
399. .35
168859.6 ,6
31,96
56404.8
Blocks
M/
1.99
20702
18901.
5/5
4432.4
36
2966996.4
96152.8
32.99
191451 1.2
36
3135384
142605
33.93
138203.4
20
2045316.4
408.79
3394886..8 88
36.94
88108
2087898.2
3839K55.6
66507
Elevator
20
0/5
2062441.2 .2
2/5
401.85
3053364.2
5/5
21..25
88835
20
20894477.6
3099277.6
36.12
83296
20
208 1322
175866
36.57
87747.2
53929.8
77450.2
16523
25
151 19449
728.74
252954,4 4
23.17
308598.6 6
Gripper
25
1/5
2663695
83551.8 1.8
5/5
35.93
309964.8 8
36
2395119.2
55209. 88
43.31
308598.6 6
36
21 12899.6
37136.8
61.99
624489.6
Minigrid-PARL.
94
0/2
2743179.4
310033
1/2
86.41
342981 18
593
334535.2
2458.2
8217319.4
Table I: Our method w/wo lifting generalization vs. Q learning. Times are listed in seconds and only the average time and number of samples are reported (full data is in the Appendix).
Our interest is not only to see how well the current method performs, but also see how much is contributed by the action-level generalization provided by lifted representations. Our primary metrics of evaluation are going to be, (a) do the methods consistently reach the goals, (b) the number of samples collected from the environment as part of reaching the goal, and (c) the time taken by the method to reach the goal. This third aspect is important one to consider to make based exploration is given a fair chance when compared against planning based methods. After all, the planning methods reason over environment model, allowing them to perform less interactions with the environment. However, this adds a computational overhead, that might not be required for other method, such vanilla RL methods. We capture that tradeoff of one computation for another by measuring the time to reaching the goal. Additionally, we set a time limit on the exploration step, as for some of these problems the exploration might not be completed in a reasonable amount of time. For all planning based instances we set the time limit to 10 minutes, while for the minigrid instances we extended the time limit to 30 minutes. Every experiment is run five times, averaging the results to account for possible randomness in the learning process. All seed values were randomly assigned and kept constant through the all five runs. As the underlying diverse planner, we used FI (15), generating ten different plans at every step. Table presents the comparison of our method against Q learning for the planning benchmarks. Both R-max and SMDP time out on all tested instances, so we will skip reporting their values in the table. SMDP took 1 188416.8 and 106821.4 .4 samples each for the two minigrid problems. We see that apart from Blocksworld and minigrid domain, our vanilla method able to solve more problems and our method equipped with the application of lifting rule outperforms both by a wide margin. Neither R-Max or SMDP visited any of the goal state in the given time limit.
that the RL
5.2 Overall Learning Performance
With the initial results collected on how well our method is able reach goal. The next question we wanted to answer was how well RL algorithm augmented with our new exploration strategy is able to perform. For this question we focused on tabular Q learning and the minigrid environment. Specifically, we compared an instance of Q learning algorithm where Q values were initialized using the plan generated through our exploration process and a vanilla one that started with no such information Top row of Figure I provides a visualization of the maps considered for these experiments). Columns two and three of Table presents the time and samples taken to get such plan for each of the problem instance considered. The bottom two rows of Figure [ present how the total value per episode changes over episodes. As expected, the access to valid plan (which isn't 't necessarily optimal) ensures that our method starts from a higher value. For smaller instances, we see that the vanilla method eventually catches up or at least gets closer. However for the largest problem instance, even after 1000 episodes the RI agent is still unable to get positive reward since never reaches goal state.

---

Problem
with original PruneModel
with bootstrapping
w/ bootstrapping
time
# sampless
time
samples
time
samples
DoorKey-5 x 5
35.39
23977.2
N/A
N/A
N/A
N/A
Door 6e-666e-666
34.45
24418.4
42.14
27666.0
35.91
21531.8
DoorKey-8xh
54.63
260839.8
52.1
143223.4
92.78
367749.2
DoorKey- 16x16
1488.08
6705823.2
2353.63
11088198
Table 2: The results from our method (with lifting) applied to the second Minigrid variant. Includes the performance under our original PruneModel strategy and the results how bootstrapping helps learning under the new action selection strategy. The entries for DoorKey-16x 16 are skipped for w/o bootstrapping, since the method timed out after 90 minutes.
5.3 Curriculum Learning
The final question we were interested in investigating was whether having access to smaller problem instance had the potential of speeding up our learning process. We again went back to the minigrid problems and tested whether first learning a partial lifted model using the a problem of grid size 5 x 5, help speed up learning in larger problems. In particular, we stop learning in the smaller instance, as soon as we find a single solvable plan. We then use the lifted model information learned from the smaller instance to create more informed model of the target problem. Then we follow the same procedure as before, until all the plans returned by the diverse planner is valid. One of the things noticed was that bootstrapped models did significantly worse off under the original PruneModel method we used. We noticed that using a strategy based on failure count resulted in useful actions getting tested early and getting removed from consideration. So for this set of experiments we considered a different strategy that re-introduces actions more frequently. Last four columns of presents the results for the minigrid problems, where the problem were bootstrapped with a lifted model learned from a 5 x 5 grid. The method without bootstrapping timed out for the largest problem without finding a solution after 90 mins. Except for the smallest problem we see the bootstrapping giving a definite advantage.
6 Conclusions and Discussion
Our paper, presents a novel exploration paradigm for reinforcement learning algorithms. Our proposed method supports the learning and refinement of optimistic symbolic estimates of the underlying model for the given task. We show how we can start with a trivially optimistic model and then use diverse planner to drive both the lask-level exploration and the refinement of the model. Experiences generated from the execution of identified plans lead to better estimates of the task, which in turn leads to more informed plans. We additionally show how we can leverage lifted representations of the given task, to generalize any learned model information across various instances of the same lifted operators. We also use this mechanism to propose a novel curriculum learning paradigm for model learning. The effectiveness of our proposed method depends on three crucial factors: (a) the possibility of performing systematic refinements of our models while ensuring desirable properties, (b) the availability of fast, diverse planners, and (c) the ability to leverage human intuition about the task. The latter is of crucial importance: even if there were other model classes and planners we could exploit, the ability to tap into human knowledge gives significant advantage. Importantly, the same knowledge has been used by many of the other state-of-the- methods. Further, it only represents a small subset of the information usually provided as part of complete symbolic planning model. One of the aspects not discussed in the paper was the fact that instead of starting with an empty model, we could have started with a partially complete model. In such cases, the human could just provide whatever they know about the task, and the RI. agent can fill in the rest. We expect such settings to provide even more advantages to our method. For future work, promising direction is to support stochastic transitions. One possible way of using such methods in a stochastic setting would be by considering separate copy of an action for each possible transition, similar to the methods used by many probabilistic planners 39. The central challenge here would be to recognize the different transitions associated with the same action and to ensure that the estimate at any given point is still an optimistic estimate of the true model. Last, but by no means least, is the combination with RL methods that use function approximation, especially in settings where the symbolic model might be an abstraction of the true underlying model. Such settings are among the most practical ones from the real-world applications perspective, allowing our method to gradually generalize to fine-graines abstractions and eventually to the real world.
10

---

Acknowledgement
Sarath Sreedharan's 's research is supported in part by grant NSF 2303019.
References
[1] David Abel. simple_rl, Reproducible Reinforcement Learning in Python. In ICLR Workshop on Reproducibility in Machine Learning, 2019.
[2] Arthur Aubret, Laëtitia Matignon, and Salima Hassas. A survey intrinsic motivation in reinforcement learning. CoRR, hes/1908.069766 2019.
[3] Peter Auer. Using confidence bounds for exploitatonn-exploraiin trade-offs. J. Mach. Learn. Res., 3:397-422, 2002.
[4] Dimitri Bertsekas, Rollout, policy iteration, and distributed reinforcement learning. Athena Scientific, 2021.
[5] Ronen Brafman and Moshe Tennenholtz. R-MAX A general polynomial time algorithm for near-optimal reinforcement learning. J. Mach. Learn. Res., 3:213-231, 2002.
[6] Ethan Callanan, Rebecca De Venezia, Victoria Armstrong, Alison Paredes, Tathagata Chakraborti, and Christian Muise. MACQ: A holistic view of model acquisition techniques. CoRR, abs/2206.06530, 2022.
[7] Jaime G Carbonell and Yolanda Gil. Learning by experimentation: The operator refinement method. In Machine learning, pages 191-213. Elsevier, 1990.
[8] Maxime Chevalier- BBiisver,,, Lucas Willems, and Suman Pal. Minimalistic gridworld environ- ment for openai gym. htttss://githut wwt.///ii/cccamccaaccaaaaaaaa gtm: gyn-minigmmidid 2018.
[9] Stephen Cresswell, Thomas Leo McCluskey, and Margaret Mary West. Acquiring planning domain models using LOCM. Knowl. Eng. Rev, 28(2):195-213, 2013.
[10] Wenfeng Feng, Hankz Hankui Zhuo, and Subbarao Kambhampati. Extracting action sequences from texts based on deep reinforcement learning. In Proceedings of the Twenty-Sevente Seventh Inter- national Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pages 4064-4070 ijcai.org, 2018
[11] Guillem Francés, Miquel Ramirez, and Collaborators. Tarski: An Al planning modeling framework. https://gi thub. com/ coom/aig-upsa hamm//iguuf//aaaiii 2018.
[12] Clement Gehring, Masataro Asai, Rohan Chitnis, Tom Silver, Leslic Pack Kaelbling, Shirin Sohrabi, and Michael Katz. Reinforcement learning for classical planning: Viewing heuristics as dense reward generators. In Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling, ICAPS, pages 588-596 388-596. AAAI Press, 2022.
[13] Giuseppe De Giacomo, Luca locchi, Marco Favorito, and Fabio Patrizi. Foundations for restraining bolts: Reinforcement learning with Itff/dlff restraining specifications. In Proceedings of the Twenty-Ninth International Conference Automated Planning and Scheduling, ICAPS. pages 128-136 136. AAAI Press, 2019.
[14] Malte Helmert. Concise finite-domain representations for PDDL planning tasks. Artificial Intelligence, 173:503-535, 2009.
[15] IBM.
(FI) planner, 2022.
[16] Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila Mcllraith. Using reward machines for high-level task specification and decomposition in reinforcement learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 Proceedings of Machine Learning Research, pages 2107-2116. PMLR, 10-15 Jul 2018.

---

[17] León Illanes, Xi Yan, Rodrigo Toro Icarte, and Sheila A. Mcllraith. Symbolic plans as high-level instructions for reinforcement learning. In Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling, Nancy, France, October 26-30, 2020, pages 540-550. AAAI Press, 2020.
[18) Brendan Juba, Hai S Le, and Roni Stern. Safe learning of lifted action models. In 18th International Conference on Principles of Knowledge Representation and Reasoning. KR 2021, pages 379-389. International Joint Conferences Artificial Intelligence Organization 2021.
[19] Brendan Juba and Roni Stern. Learning probably approximately complete and safe action models for stochastic worlds. In Thirry-Sithh AAAI Conference on Artificial Intelligence, AAAI, pages 9795-9804. AAAI Press, 2022.
[20] Leslie Pack Kaelbling, Michael L. Littman, and Andrew W. Moore. Reinforcement learning: A survey, J. Artif. Intell. Res., 4:237-285, 1996.
[21] Subbarao Kambhampati, Sarath Sreedharan, Mudit Verma, Yantian Zha, and Lin Guan. Symbols as lingua franca for bridging suman-ai chasm for explainable and advisable AI systems. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI, pages 12262-12267. AAAI Press, 2022.
[22] Michael Katz and Shirin Sohrabi. Reshaping diverse planning. In The Thirty-Fourth AAAI Conference Artificial Intelligence, AAA/ 2020, pages 9892-9899. AAAI Press, 2020.
[23] George Dimitri Konidaris, Leslie Pack Kaelbling, and Tomás Lozano-Pérez. From skills to symbols: Learning symbolic representations for abstract high-level planning. Artif. Intell. Res., 61:215 289, 2018.
[24] Leonardo Lamanna, Alessandro Saetti, Luciano Serafini, Alfonso Gerevini, and Paolo Traverso. Online learning of action models for PDDL planning. In Proceedings of the Thirtieth Interna- tional Joint Conference on Artificial Intelligence IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 4112 -118. ijeai.org, 2021.
[25] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[26] Junkyu Lee, Michael Katz, Don Joven Agravante, Miao Liu, Tim Klinger, Murray Campbell, Shirin Sohrabi, and Gerald Tesauro. Al planning annotation for sample efficient reinforcement learning. CoRR, abs/2203.00665 2022.
[27] Daoming Lyu, Fangkai Yang, Bo Liu, and Steven Gustafson. SDRL: interpretable and data- efficient deep reinforcement learning leveraging symbolic planning. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI, pages 2970-2977. AAAI Press, 2019.
[28] Argaman Mordoch, Roni Stern, Enrico Scala, and Brendan Juba. Safe learning of pddl domains with conditional effects. In /C Workshop on Reliable Data-Driven Planning and Scheduling (RDDPS), 2023.
[29] Christian Muise, Florian Pommerening, Jendrik Seipp, and Michael Katz. Planutils: Bring- ing planning the masses. In 32nd International Conference on Automated Planning and Scheduling, System Demonstrations and Exhibits, 2022.
[30] Bernhard Nebel. On the compilability and expressive power of propositional planning for- malisms. J. Artif. Intell. Res., 12:271-315. 2000.
[31] Tom Silver and Rohan Chitnis. Pddlgym: Gym environments from PDDL problems. CoRR, abs/2002.064322, 2020.
[32] Sarath Sreedharan, Anagha Kulkarni, and Subbarao Kambhampati. Explainable human-ai interaction: A planning perspective. Synthesis Lectures on Artificial Intelligence and Machine Learning, 16(1):1-184, 2022.
12

---

[33] Sarath Sreedharan, Utkarsh Soni, Mudit Verma. Siddharth Srivastava, and Subbarao Kambham- pati. Bridging the gap: Providing post-hoc symbolic explanations for sequential decision making problems with inscrutable representations. In The Tenth International Conference on Learning Representations, ICLR. OpenReview.net, 2022.
[34] Roni Stern and Brendan Juba. Efficient, safe, and probably approximately complete learning of action models. In Carles Sierra, editor, Proceedings of the Twenty-Sixthh International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pages 4405-4411 1. ijcai.org. 2017.
[35] Terry Winograd. Procedures representation for data in computer program for understand- ing natural language. Technical report, MASSACHUSETIS INST OF TECH CAMBRIDGE PROJECT MAC, 1971.
[36] Danfei Xu, Roberto Martin-Martin, De-An Huang, Yuke Zhu, Silvio Savarese, and Li Fei-Fei. Regression planning networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 1317-1327, 2019.
[37] Fangkai Yang, Daoming Lyu, Bo Liu, and Steven Gustafson. PEORL: integrating symbolic planning and hierarchical reinforcement learning for robust decision-making In Proceedings of the Tivery-Seventh International Joint Conference Artificial Intelligence, IJCAL, pages 1860-4866 ijcai.org. 2018.
[38] Qiang Yang, Kangheng Wu, and Yunfei Jiang. Learning action models from plan examples using weighted MAX-SAT. Artificial Intelligence, 17102-3):107-433, 2007.
[39] Sung Wook Yoon, Alan Fern, and Robert Givan. Ff-replan: baseline for probabilistic planning. In Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling, ICAPS, page 352. AAAI, 2007.
[40] Sung Wook Yoon, Alan Fern, Robert Givan, and Subbarao Kambhampati. Probabilistic planning via determinization in hindsight. In Proceedings of the Twenty-Third AAAI Conference Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13-17, 2008, pages 1010-1016. AAAI Press, 2008.
13

---

A Appendix Overview
In this appendix, Section B will cover the formal statements and proof sketches for various theoretical results, Section [ will cover the implementation details including hyperparameters. Section E will cover the various assumptions made in the work and finally Section F provides an overview of how our approach is used in the context of Q learning.
B Theoretical Results
First result we are interested in establishing is the fact that for any given MDP of the form described in Section 3.1 in the main paper, there exists a corresponding symbolic model that meets the criteria discussed in Section 3.2 in the paper.
Proposition 2 For an MDP of the form M = A,, R), there exists a grounded symbolic model M4 (F,, A4, I)G), such that there exists
1. a mapping C. from the state S of M to the states of M,
2. a mapping C-1 from the actions A₁ of M, to the actions A of M, and
3. mapping from valid traces in M valid plans in Mr and vice-versa.
Proof Sketch: We can build such a model by adding one grounded predicate (each corresponding to a unique lifted predicate of arity 0) for each state other than 1 into FL. Now state in S maps (defined by C) exactly to the symbolic state where the corresponding predicate is true and none of the other fluents are true. Now for the action, we will start with an action definition that includes conditional effect, and then convert it to form assumed by the work. A conditional effect captures cases where an effect of an action only fires if the state meets certain criteria. Now we create one symbolic action for each MDP action. For each possible transition between states (other than L), we will add corresponding conditional effect that takes the predicate corresponding to source state as condition and as effect the predicate corresponding to the target state. We will keep as precondition of the actions a disjunctive list of all possible states where it will not fail. For the goal action, we will have corresponding symbolic goal action whose precondition corresponds to potential states in Sg and the effect is a goal predicate. The initial state consists of only the predicate corresponding to the state I and the goal corresponds to the goal predicate. Now we can convert the actions with conditional effects to ones with no conditional effect (cf. 30). Now the action mapping C-1, will map each of these new actions to the original MDP action from which it was defined. Now plan is only valid in this model, if there exists a sequence of transitions from initial state to goal with non-zero probability. Similarly, for every valid trace there must exist valid plan where each MDP action could be replaced by one of the potential symbolic actions that maps to it.
Next will talk about the optimism of the initial model estimate
Proposition 3 My = AF, 1,,G). More formally, every action E A will be defined as follows: (preğ, addz, delg), where preg delg 0 and add; FÇ is optimistic for any MDP model such that there exists a mapping C from MDP state to symbolic states and a function C-1 mapping symbolic actions to MDP actions.
This can be easily shown by the fact that every possible action sequence is a possible plan here.
Moving onto the update rule.
Proposition 4 Update rule as presented in Section 4.1 will only resull in an optimistic representation.
Proof Sketch: The important point to note that any point, the update rule only applied to an optimistic representation. So, in order for it to result in a non-optimistic model, it must have removed plan corresponding to a valid trace. Given our initial construction of Mt. we always ensure that in Mb the execution of an action at a state C(s) will result in symbolic state that is superset of C(s'), where T(s, a, s') = 1. Note that an application of an update rule will only extend the precondition if the corresponding MDP action fails and the preconditions are extended to exclude only the current state (though the list of excluded state, action pairs grows as the number of failed samples grows). Additionally, the effect is changed only to disallow impossible transitions. Since the transitions are deterministic, only one sample is needed to determine that no other transitions are possible from that state and action. This means that the above property (the fact that the resultant
14

---

symbolic state will be superset) will be preserved through updates. Which in turn means that any plan that previously corresponded to a valid trace can become invalid.
Now coming to the theorem
Theorem Algorithm (as referenced in the main paper) will (a) terminate in a finite number of steps and (b) identify path to a goal (provided one exists); as long as the diverse planner used is complete (i.e., it will return a non-empty plan set as long as there exists a valid plan).
Proof Sketch The validity of this theorem follows from the fact that the update rule will remove any plan that doesn't correspond to valid trace from consideration again. If the planner is complete then it will effectively iterate over all possible plans. Eventually finding one that corresponds path that goes the goal. This guaranteed to exit in finite steps, as the set of non-redundant plans is guaranteed to be finite when the state space is finite.
Now revisiting Proposition 1
Let À (a.,..., 0m) ) be a sel of actions marked as being instances of a sin- gle lifted action at. Then min add must be superset of add effects of al and max_ del a superset of deletes of a², where min_add add and max_ del are calculated for A
Proposition 1
Proof Sketch The validity is trivial. The update rule makes sure that every effect estimate will be optimistic estimate of the true ground action effects. In the case of add effects this estimate will be a superset and for delete effects it will be a subset. Thus, the lifted representation of each set must correspond to optimistic estimates of the true lifted representation of the effects.
C Implementation Details
All experiments were on laptop running Mac OS v 11.06, with 2 GHz Quad-Core Intel Core i5 and 16 GB 3733 MHz LPDDR4X. We did not use CUDA in any of the experiments. For the planner, we used the Fl-diverse-agl planner provided as part of the forbid iterative planner. As discussed we generated 10 plans in every planing query. The search was given maximum threshold of 1000 iterations, but we never reached that limit given our time limit. We stop an action from being considered if it fails 10 times in row. We will update this upperbound planner returns empty plan at any point. Since we found out that the planner was slowed down by the introduction of disjunetive preconditions, we replaced the disjunctions with set of actions (this is an equivalent compilation popular within planning). To control the growth of the precondition, we introduce upper bound on its size, set to 10 in our experiment. Note that the true size of the preconditions in all instances we consider here is significantly smaller than our bound. We could make the bound adaptive to a domain, but we do not expect all the RL baselines we used a discount factor of 7. For Q learning and R max, we used a maximum of 1000000 episodes with 200 steps per episode. For exploration, the and decay rates were set as the same as the one used by SimpleRL experiment scripts. For PPO, we used the same default values used by (26). The environment names for the two problems we tested in minigrid where where, MazeRooms--Bi Rooooooosss------oo Siby8-DoorKey-0O and MazeRooms-211 2by22 TwoKeys-vo v0. While creating the PDDL model for minigrid we combined the turn actions with the other actions (move, pickup, drop, etc.), to avoid potential conditional effects.
number of failures if the
make any significant difference. For
D
Additional Experiments
D.1 Comparison with a Symbolic Baseline
To see how our method compares against other methods for symbolic model acquisition, we look at how many samples are required by a popular model learning method (cf. (19) to generate a model that can produce a goal reaching plan. Since we don't 't have access to plan library, we will generate one through random walks on our simulator. We focused on the Blocksworld domain, and for each of the five problems, we look at the number of samples required to generate model that allows a potential plan to the goal. Since the method generates pessimistic approximation of the model, any plan generated by the model is guaranteed to be valid and thus the method no longer requires the use of diverse planners to generate potential plans. We placed an upper bound of 600000 on the number of samples originally collected from the simulator (this is nearly six times larger than the number
15

---

of samples required by our method), Out of the five problems, we found that only the method was only able to learn a model capable of generating valid plan in the case of the first problem instance. Even for that problem, we found that the method took on average 548287.8 88 samples.
D.2 Kitchen Domain
As an additional experiment, tested our method the symbolic part of the Kitchen Domain 36 We tested our method on the domain by creating a symbolic simulator that uses the descriptions provided in the appendix of the paper (specifically the enter-dependenciss listed in Figure 5). The purely symbolic domain consisted of one action for each high-level goal possible and the preconditions were built based on the relationships described in the paper. The exact domain consisted of 15 predictions and 13 actions. The goal was the same as the one described in the paper (i.e., both banana and cabbage is cooked, they are placed plates and the plates served). The lifted version of our method was able to identify a valid plan in 61.46 sec using 24727.2 22 time steps (averaged across five runs) and the non lifted version took 393.57 secs and used 140681 samples (again averaged across five runs). Now executing the plans in the true simulator would require an additional component an additional step to drive the simulated robot achieve each of these subgoal. However, as discussed in the paper, we can do that by using a motion level planner (like an RRT based planner).
E Assumptions Made
Here we explicitly mention all the theoretical assumptions we have made in the paper and how to relax them
Model dynamics:
Deterministic model our primary formulation and evaluation focus on deterministic domains. However, as discussed in the future works section, we can directly apply our method to stochastic environments by creating symbolic models that correspond so-called all outcome determinizations of the model (39
Observability:
We assume that the environment is fully observable. However, previous work have looked at how partial observability can be compiled into classical planning model. For optimistic estimates, we can make further simplification to assume that all unobservable facts are true, thus allowing to directly apply our methods in such settings.
Finite state and action space:
We assume that the underlying state and action space is finite and thus can be represented exactly using a finite symbolic models. For cases where this is not true, we can still employ our symbolic model to capture an abstraction of the true state and action space.
Symbolic observations:
We assume that noise-free classifiers for each symbolic fluent given. Previous work [32 have looked at the problem of learning such classifiers, which we can directly use in our scenario. If the classifiers are noisy, this corresponds to special case of partial observability. As discussed above, we therefore can extend our model to handle noisy classifiers.
F Overall Learning System
Here we provide an overview of the overall learning process. Figure presents diagrammatic representation of the learning process. As discussed before, we start with a trivially optimistic representation of the model. We then use diverse planner to potentially generate possible plans from that domain, which are then tested on the simulators. The experiences generated from the simulator are then used to update and refine our optimistic representation. Once a successful plan is identified, this information used to initialize the RL algorithm. For our experiments, we focused on Q learning; as such, the plans were used to initialize the Q values with more informative estimates. It is worth noticing that the problem of learning a useful refinement of an optimistic model involves solving an additional exploration-explootuuie problem. Specifically, this involves identifying what actions
16

---

Diverse plans
Successful plan used to bootstrap an RL algorithm
Simulator
Diverse Planner
Learning Algorithm
Samples
Update
Optimistic Representation
Model Pruner
Rules
Updated
model
Figure 2: A visualization of the overall learning process
the planner should try to include in the plans. While the use of diverse planners already provides us with mechanisms promote exploration, given the optimistic nature of the model estimates, there always possibility that the planner will try to use actions that have not yet been successfully executed (thereby updating its effect). In current implementation, we employ queuing strategy to prevent the planner from retrying the same actions too many times.
17


Reviews:
[{"review_id": "OEzoZjymon", "reviewer": "Reviewer_nfft", "summary": "The authors present a framework for learning symbolic representation of an underlying MDP that leverages key concepts of the planning community.\nSpecifically, they use the PDDL formalism to represent a planning problem that's acquired through agent interactions with an MDP. The authors show that this approach can lead to higher success rate in underlying planning problems that simply using standard Q-learning.", "questions": "- As a suggestion, it would have been extremely helpful to have a working example throughout the text or some visualization to explain concretely what the method is doing. What exactly is being collected to learn the binary classifier? What are the objects replacing the parameters?\n\n\n- What was the actual planer used in this evaluation? The text mentions several times \"diverse planners\", but what was actually used?", "limitations": "No clear mention of limitations, no concerns on societal issues.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "\n- The results show that the proposed method is able to learn a model that can be leverage by the planning agent. The authors show that they are able to learn a symbolic representation for the underlying MDP from the agent experience.", "weaknesses": "\n- The main weakness of this paper is its presentation and writing style. I found the text really confusing as it seems like the text is not self-contained. For example, line 155 \"denote grounded instance by replacing the parameter with an object list\", what objects? where is the list coming from?\nin line 178, \"... learn a  binary classifier that tests whether a ground truth predicate may be true in a given MDP state...\" What do you mean it is learned by collecting positive and negative examples for each ground concept?\nAlgorithm 1, what are the DiversePlanner, UpdateModel, and PuneModel functions? \n\n- It is not clear where the exploration is taking place. The title would lead me to think that it would be a central part of the paper, but in the main text, it appears to be just a comment on the use of the planners.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments; we will work on having a running example that better illustrates the various points made in the paper.\n\nQuestions:\nBinary classifier: We are using handcrafted classifiers in the experiments. As such we didn’t need to collect positive or negative examples. Our methods are completely agnostic of how the predicates are obtained. The specific passage the reviewer mentioned points to the fact that earlier works have shown that such predicates can automatically be learned from examples. To clarify, in this work, we assume the predicates to be provided (either hand-crafted or learned separately). Our methods are completely agnostic of how the predicates are obtained. The specific passage the reviewer mentioned points to the fact that earlier works have shown that such predicates can automatically be learned from examples.\n\nDiverse Planner: We used FI-diverse-agl planner provided as part of the ForbidIterative planner. The details are provided (along with other implementation details) in Section 2 of the main file in the supplementary folder.\n\n\nWeaknesses:\n\nObject: The notion of objects, as used in this paper, corresponds to a concept used within relational representations. This representation scheme makes the ontological commitment that the world can be represented as a set of objects and relationships between the objects. In theory, an object could be anything. However, in practice, they usually correspond to what people would consider to be objects. For example, in the case of the blocksworld domain described in the paper, the objects would be the various blocks that will be stacked on top of one another. The notation for objects is presented in lines 127-128.\n\nPredicates: Please see the answer to question 1.\n\nUpdateModel, and PruneModel - These processes are described in sections 4.1 (lines 242 - 255) and 4.2 of the paper (267 - 280), respectively.\n\nExploration: As with the case of Rmax, exploration here is automatically performed as part of the planning process. In our case, as the model estimate is refined through interaction, the planner automatically comes up with different paths it thinks will reach the goal. These plans are then tested on the simulator and then used to refine the model. The refined model then provides new plans. We provide a high-level discussion of the overall approach in lines 192 to 207.\n"}, {"review_id": "Buuyrovchg", "reviewer": "Reviewer_S1WD", "summary": "This paper follows a long line of recent work on trying to combine RL with symbolic reasoning. The main motivation for doing so in this paper is to improve exploration on sparse reward, goal-oriented tasks, similar to the \"taskable RL\" setting of Illanes et al. A major limitation of existing work is the need for a human expert to provide a symbolic model upfront. This paper aims to relax that assumption by removing the need to specify the transition logic (in RL parlance). The human still needs to specify how the states are represented symbolically, but an algorithm takes care of learning the model. In a nutshell, the way the algorithm works is by starting with the most permissive model possible, then iteratively asking the planner for a solution, attempting to execute it, and updating the model based on the sampled experience. The preconditions, additions and deletions are updated according to the least restrictive explanation of what just occurred, ensuring that the model remains \"optimistic\", i.e., any possible trace in the MDP remains possible under the planning model. This guarantees that the algorithm will eventually find a solution, provided one exists. The evaluation shows that approach learns quickly relative to some standard RL exploration strategies, and also shows that the approach can effectively bootstrap lifted representations learned from previous task instances when tackling new tasks.", "questions": "Could you please go into a bit more detail about what the main challenges would be in extending your approach to stochastic environments? For example, do you envisage learning transition probabilities and using a probabilistic planner, or would you consider something like FOND planning?", "limitations": "As mentioned in my comments above, I think the paper could do a better job of acknowledging the drawbacks of assuming a deterministic environment. This is very downplayed at the moment. It's promised early on that \"In Section 6, we will see how we can also apply our methods directly in settings with stochastic dynamics\", but then all that's actually given is a one-liner.\n\nI don't see any potential ethical concerns with this work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Overall, I thought this was a very interesting paper, based on an intuitive idea. The approach seems more similar to how humans tackle long-term, sparse reward tasks compared to the standard RL approach of intrinsic rewards. Generally, we humans don't possess a complete model of the environment, so we come up with a *plausible* plan, try it out, then update our models based on what happened. It always amazes me how complicated ideas like this sound when expressed in planning logic (I'm more of an RL person), but surprisingly I was able to follow most of the core technical details. Largely this is because the paper is very well-written -- unlike a lot of papers I've reviewed recently, this one is actually self-contained, with the authors going to great care to explain the preliminaries and problem setting properly. This was much appreciated as someone who needs to be reminded of all the planning lingo. The coverage of related work is good (the authors come across as being very knowledgeable across many subfields) as a far as I know the approach is original. The experiments are mostly compelling (with some caveats noted below), and I thought the curriculum learning experiment (Section 5.3) was particularly cool!", "weaknesses": "The main weakness of the paper is one that's already acknowledged by the authors; namely, the assumption that the environment is deterministic. This limits the applicability of the method quite a lot, and I'm not sold from the brief explanation in Section 6 that the method would work well if directly applied to stochastic environments. Moreover, assuming determinism greatly simplifies some aspects of the decision-making problem. This is partly discussed on page 3, but there are a lot of things that one can do to speed up learning that aren't mentioned. For example, rather than applying Q-learning with 1-step updates, you can calculate all possible n-step return estimates and backup from the largest one. Also, until a reward is found, all action-values will be tied at 0, so an e-greedy policy is actually just a uniform random policy until that point (assuming random tiebreaking), which seems woefully inefficient if you know that the environment is deterministic. It's trivial to learn the transition function in the deterministic setting, so you could adopt a simple strategy like maintaining a list of visited states with untried actions, and actively work towards ticking off that list. I'm not super familiar with R-MAX, but I understand that it's designed for stochastic environments, which also puts it at a disadvantage assumption-wise. I'm not suggesting that the authors derive a brand-new RL algorithm that perfectly exploits determinism just to baseline against (although I'd be very surprised if no-one has tackled this problem before), but I'd be more convinced by the experiments if the baselines were at least slightly optimised for this setting.\n\nMy only other (minor) criticism of the paper is that it clearly ran into issues with the NeurIPS page limit. Much of the writing has been packed into walls of text to address this, and Figure 1(b) has been compressed to the point where it's very hard to read. While there's little you can do about this (I can't think of anything major that's cuttable), I have to admit I groaned when I opened the paper and saw the formatting. I'd definitely recommend releasing a nicer, less compressed version of the paper as a supplemental sometime in the future, since I think the current format will put off some readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments; we will make sure to expand our discussion on how the method could be applied in stochastic settings.\n\nWeakness/Questions:\n\nEase of learning models in deterministic settings: We would like to point out that a brute force-based method will not scale well in the domains we consider, given the sheer state space sizes involved. A good demonstration of this fact is the symbolic model learning baseline provided in the appendix main pdf (Section 3), which relies on random walks to generate different traces.\n\nExtending the method to stochastic settings: Please note that central notions of the optimism considered in the paper carry over to stochastic settings. We can still start with a model with empty preconditions and add effects that contain all add effects. Now the challenge here is, of course, how does one refine the effects of this model when there are multiple effects possible. As alluded to in the paper, the conceptually most straightforward approach would be to treat each qualitatively different outcome one comes across as a new action and introduce it into the model. One can’t remove the old action copies directly as one is unsure if there might still be a yet undiscovered outcome of that action, which may produce that effect. However, our internal action prioritization system can be updated to ensure that the planner will not try to rely on those outcomes after a certain number of trials have passed. This would, in theory, correspond to learning effectively a determinization of the original model. Of course, one could combine the outcomes together to form a FOND-like representation of the model, and we could even associate probability estimates with each observed outcome.\n"}, {"review_id": "S4kUxfnfvM", "reviewer": "Reviewer_6i1K", "summary": "This paper studies reinforcement learning in deterministic MDPs in which a symbolic representation of the state space is assumed to exist. The method proposed in this paper learns a symbolic model of the environment, and it uses it to speed up the reinforcement learning process. The algorithm starts with an \"optimistic\" model in which all actions lead to the desirable goal state. The role of the algorithm is to refine the actions to make them more realistic by discovering the preconditions and the effects of actions. A few mathematical assertions are provided in the paper, and the empirical results compare the new method with the Q-learning algorithm.", "questions": "* What is the difference between online and offline RL in lines 24-25?\n* The sentence in line 81 criticizes [22], but the point made in that sentence is not clear to me.\n* Def. 1 is confusing to me. If the action sequence has k actions in the full symbolic model, the optimistic sequence may have only one action which would lead to the goal straight away. I am not sure why both sequences have the same length in the definition. Also, the definition itself is cryptic to me, and only the subsequent paragraph managed to explain the idea of this particular optimism to me.", "limitations": "* The discount factor gamma should be part of the MDP definition. This is part of the environment, not the algorithm. This would also make the paper clearer. For a moment, I thought that discount actor is 1, but then given only the goal reward, the length of the trajectory would not matter. But, line 104 indicates that gamma is 1 indeed because \"any\" trajectory is seen as optimal. There are some conflicting statements in the paper.\n\n* There are a few small typos and grammatical errors in various places. E.g. the exponent in line 163 or PDDL is written as pddl on p. 7.\n\n* Line 420: how where the Q-values initialized?\n\n* Appendix mentions Fig. 5, but the figure is missing.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* The paper studies an important problem of enhancing reinforcement learning through symbolic models from symbolic PPDDL-like planning\n* The contributions of the paper that are related  to symbolic planning are strong\n* The fact that the paper uses lifted inference is a great plus\n* The paper presents both empirical results and explains the method using theoretical arguments", "weaknesses": "* As said above, the contribution to the symbolic planning literature is clear and seems strong, but the link with reinforcement learning is unclear. For example, it is not clear to me how exactly the model being learned by Algorithm 1 interacts with Q-learning. A pseudo-code of a complete Q-learning algorithms with the new stuff would be very useful. Lines 285-294 are not sufficient to explain this integration.\n\n* Since the MDP is deterministic, there is no need for a full RL policy since the solution can be a single trajectory. This means that Q-learning may not be required. Perhaps it would be more appropriate to integrate and compare this method with LRTDP, which would have convenient properties in deterministic MDPs.\n\n* The authors were careful to acknowledge in the introduction that their models are optimistic with respect to the underlying transition function. But, the authors should also note that the word \"optimistic\" has a very special meaning in RL and in heuristics search or symbolic planning in general. Optimistic is often used as a synonym for admissible, and unfortunately the symbolic models studied in this paper are not optimistic nor admissible with respect to the expected rewards optimized by Q-learning. Note that one may have a very low-reward action that leads to the goal in 1 step, but such an action should never be chosen, when a longer trajectory can reach the goal at a much higher reward. The current approach will miss that. For that reason, I feel that the use of the word \"optimistic\" may confuse the readers in the future. Perhaps the authors could think about this. The authors should note that the R-max algorithm that the authors cited led to many other ways of using optimism in RL, e.g. https://icml.cc/Conferences/2010/papers/546.pdf or https://www.ifaamas.org/Proceedings/aamas2012/papers/1C_1.pdf or https://www.ifaamas.org/Proceedings/aamas2010/pdf/01%20Full%20Papers/06_06_FP_0313.pdf. The use of a diverse planner is good, but the point of the methods mentioned above is that they can do much better than a diferse planner which can go in a wrong direction and explore useless states.\n\n* It seems to me that the authors could survey the literature on symbolic planning in deterministic domains when the PDDL operators are learned from data. I am sure that there must exist papers in which this problem was studied. I think that some literature review on this would be useful in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments, and we will make sure to include a pseudo code for the updated Q-learning algorithm. We will make sure to include a more detailed discussion of the existing work in the space of learning symbolic models. We would also like to point out that the supplementary file includes a comparison to a popular symbolic model learning algorithm.\n\nWeaknesses: \n\nContributions to RL - In so far as planning is the problem of using fully defined models to generate a course of action and RL learning the best course of action from experience, we are solving an RL problem. Additionally, we show theoretically that assuming a symbolic structure provides a number of advantages. We empirically show that our method outperforms a state-of-the-art hierarchical reinforcement learning approach on popular RL benchmarks.\n\nLRTDP -- The LRTDP algorithm is intended for non-deterministic domains. On deterministic domains, it will perform many unnecessary computations. We are not aware of any evidence of why this particular algorithm would work better than the popular Q-learning. The more efficient planning algorithms that do not require action models would be Greedy Best-First Search (GBFS) with weak evaluators that do not require the action model, like goal-count heuristic or Best-First Width Search. However, these algorithms can benefit greatly from the knowledge of action models, and that is what most symbolic planners are doing, including the diverse planners used here. It is a very well-known fact within the planning community that these search algorithms perform much better when equipped with evaluators obtained from action models and therefore, we did not feel the need to perform such an experiment.\n\nOptimism -- Please note that in this paper, we are trying to formalize and learn an optimistic representation of the underlying model. As discussed in Definition 1, we define this optimism in terms of the number of traces allowed (i.e., has non-zero probability in the model). In the paper, we were careful to frame all our claims of optimality in terms of learning an optimal representation and not necessarily in terms of optimal policy identified on top of the learned model. We will make sure to update the paper to clarify any such confusion.\n\nFurther enhancements to the method: We really appreciate the links to the works that extend Rmax. Given the fact that the nature of the optimistic estimation process is drastically different from Rmax, it is unclear how we could map the intuitions from these works to our current approach. However, we agree this would make for an interesting next step for our work.\n\n\nQuestions: \n\nOffline vs. online RL in the context of symbolic model learning: The methods we referred to as belonging to offline RL assume access to a set of traces. On the other hand, the method we employ directly interacts with the environment (or a simulator).\n\nDefinition 1 - Please note that definition one doesn’t limit itself to just the optimal sequence possible under the model but rather considers all sequences with a non-zero probability. As such, the set of all traces (i.e., state action sequences with non-zero probability) under the learned approximation is guaranteed to be a superset of traces possible under the original model. We will work on updating the definition to make it easier to understand.\n\nAutomatic synthesis of symbols: Note that we are building models on top of symbols (predicates, objects, actions, etc.) that are provided by the user. As such, one would expect the user to be able to make direct sense of the learned model descriptions, or at the very least, we could expect these models to be used as inputs to existing explanation generation methods for symbolic models. However, with methods that directly synthesize the symbols as well, there is no guarantee that people can make sense of the learned model descriptions.\n\nDiscount Factor - Thank you for pointing out this typo; we will make sure to include the discount factor in the model definition. We would like to note that our method can support a discount factor of `1’. Given our focus on deterministic models, any policy that only generates finite paths to the goal will be considered optimal. Note that any policy that doesn’t end support a path to a goal state or includes a loop will not be optimal (as the loop will never terminate). We will update the discussion around line 104 to clarify that this is only true when the discount factor is 1.\n\nQ Value Initialization: They were initialized to zero.\n"}, {"review_id": "T6GM3Mncvk", "reviewer": "Reviewer_MX4H", "summary": "This paper proposes a new method for optimistic exploration in sparse reward settings for reinforcement learning problems.  The core of this method is learning optimistic symbolic approximations of the underlying world model. Such optimistic symbolic models can then be used with a diverse planner to generate plans for explorations, which could ultimately facilitates learning. The proposed method is tested in four benchmark domains with grid world type environments. The proposed method is compared with three baseline methods, including two exploration methods and one hierarchical RL method from prior work. With the same computational time limit, the proposed method is shown to outperform the baselines in number of problems solved (goal reached). The proposed method is also shown to be able to effectively leverage human input through lifted representations in the symbolic model.\n", "questions": "Given a higher time limit, how does the proposed method compare with R-max and SMDP baselines?\n", "limitations": "I did not see a discussion on the limitations. It might be helpful to discuss what is assumed to be provided for the symbolic model for the proposed method to work, and what can we do if these elements are not provided.  \n", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "- The proposed method of learning optimistic symbolic models and utilizing them for exploration is technically interesting and novel. \n- The paper is well-written and easy to follow.\n- Exploration in RL is a long-standing and important problem. Leveraging symbolic methods in RL is a promising direction. This paper makes an important step in this direction. \n- The experimental setting is sound: the proposed method is evaluated on four traditional benchmark domains and compared against three existing methods from prior work.  ", "weaknesses": "For experimental results, the author states that both R-max and SMDP timed out in all test instances under the time limit set in the paper, and therefore no result was reported in the paper on these two baselines. It would be helpful to report at least some results on these two baselines, otherwise it is not clear how the proposed method compare with these two baselines in different aspects. As an example, the author could set a very high time limit such that R-max and SMDP can finish running, then report the number of test cases solved as well as the average computational time used, and compare the proposed method with these two baselines in these statistics. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for their suggestions. Since most of the baseline methods considered, including Rmax and epsilon greedy visit all states in the limit, they will eventually find a goal state after a number of iterations. For planning tasks considered here, this number however can (and in many cases will) be prohibitively high. Having said that, we will make sure to update the paper with results for higher time limits. \n\nLimitations: We have included a discussion of the specific assumptions made in section 5 of the pdf included as part of the appendix.\n\n"}]

Author rebuttal:

Meta-review: The reviewers are split on the decision here. The two main criticisms put forward center around the presentation/clarity of the work, and the assumption that the underlying MDP is deterministic. In contrast, the reviewers in favor of the work praise the paper's novelty, intuitive appeal, logical flow, and compelling experiments (with an emphasis on the novelty of the work).

Following some discussion, one of the reviewers has made a compelling case for the paper to be accepted in light of the paper's strengths, while agreeing that the primary limitation of the work is the assumption that the MDP is deterministic. The reviewer noted that this limitation should not prevent the paper from publication as the resulting problem is still both difficult and interesting. Instead, it is reasonable to treat the relaxation of this assumption as an opportunity for future work, which I tend to agree with.

Overall, in light of the above discussion (and absent any major critiques of the work that should block publication), I recommend acceptance.
Decision: Accept (poster)