LEARNING DYNAMIC ABSTRACT REPRESENTATIONS FOR SAMPLE-EFFICIENT REINFORCEMENT LEARNING
Authors: Mehdi Dadvar
Rashmeet Kaur Nayyar
Siddharth Srivastava
Venue: Submitted to ICLR 2023 (2023)
Keywords: Sequential Decision-Making
Reinforcement Learning
Learning Abstract Representations

Abstract: In many real-world problems, the learning agent needs to learn a problem’s abstractions and solution simultaneously. However, most such abstractions need to be designed and refined by hand for different problems and domains of application. This paper presents a novel top-down approach for constructing state abstractions while carrying out reinforcement learning. Starting with state variables and a simulator, it presents a novel domain-independent approach for dynamically computing an abstraction based on the dispersion of Q-values in abstract states as the agent continues acting and learning. Extensive empirical evaluation on multiple domains and problems shows that this approach automatically learns abstractions that are finely-tuned to the problem, yield powerful sample efficiency, and result in the RL agent significantly outperforming existing approaches.

Under review as a conference paper at ICLR 2023
LEARNING DYNAMIC ABSTRACT REPRESENTATIONS FOR SAMPLE-EFFICIENT REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
In many real-world problems, the learning agent needs to learn a problem's ab- stractions and solution simultaneously. However, most such abstractions need be designed and refined by hand for different problems and domains of applica- tion. This paper presents novel top-down approach for constructing state abstrac- tions while carrying out reinforcement learning. Starting with state variables and a simulator, presents a novel bommin-independent approach for dynamically com- puting abstraction based on the dispersion of Q-values in abstract states the agent continues acting and learning. Extensive empirical evaluation on multiple domains and problems shows that this approach automatically learns abstractions that are finely-tuned to the problem, yield powerful sample efficiency, and result in the RL agent significantly outperforming existing approaches.
INTRODUCTION
It is well known that good abstract representations can play vital role in improving the scalability
and efficiency of reinforcement learning (RL. (Sutton & Barto 2018 Yu 2018: Konidaris (019). However, it is not very clear how good abstract representations could be efficiently learned without extensive hand-coding. Several authors have investigated methods for aggregating concrete states based on similarities in value functions but this approach be difficult to scale as the number of concrete states or the transition graph grows.
This paper presents novel approach for top-down construction and refinement of abstractions for sample efficient reinforcement learning. Rather than aggregating concrete states based on the agent's s experience, our approach starts with a default, auto-generated coarse abstraction that collapses the domain of each state variable (e.g., the location of each taxi and each passenger in the classic taxi world) to one or two abstract values. This eliminates the need to consider concrete states individ- ually, although this initial abstraction is likely to be too coarse for most practical problems. The overall algorithm proceeds by interleaving the process refining this abstraction with learning and evaluation of policies, and results in automatically generated, problem and reward-function specific abstractions that aid learning. This process not only helps in creating a succinct representation of cu- mulative value functions, but it also makes learning more sample efficient by using the abstraction to locally transfer states' values and cleaving abstract states only when it is observed that an abstract state contains states featuring large spread in their value functions.
This approach is related to research on abstraction for reinforcement learning and on abstraction refinement for model checking Dams & Grumberg (2018); Clarke et al. (2000) detailed survey of related work is presented in the next section). However, unlike existing streams of work, we develop a process that automatically generates conditional abstractions, where the final abstraction on the set of values of variable can depend on the specific values of other variables. For instance, Fig. I displays a taxi world where for different values of the state variables (destination and passengers locations), meaningful conditional abstractions are constructed for the taxi location. A meaning- ful abstraction provides greater details in the taxi-location variable around the passenger location when the taxi needs to pick up a passenger (Fig. | (middle)). When the taxi has the passenger, the abstraction should show greater details around the destination (Fig. rightt).. Furthermore, our ap- proach goes beyond the concept of counter-example driven abstraction refinement to consider the reward function as well as stochastic dynamics, and it uses measures of dispersion such as the stan- dard deviation of Q-values to drive the refinement process. The main contributions of this paper

---

Under review as a conference paper at ICLR 2023
mechanisms for building conditional abstraction trees that help compute and represent such ab- stractions, and the process of interleaving RL episodes with phases of abstraction and refinement. Although this process could be adapted to numerous RL algorithms, focus developing and investigating it with Q-learning in this paper.
The presented approach for dynamic ab- stractions for RL. (DAR+RL) can be thought of a dynamic abstraction scheme because the refinement is tied to the dispersion of Q-values based on the agent's s evolving policy during learning. It provides adjustable degrees of compres- sion (Abel et al. 2016) where the aggres- siveness of abstraction can be controlled by tuning the definition of variation in the dispersion of Q-values. Extensive empir- ical evaluation multiple domains and problems shows that this approach auto- matically learns abstract representations that effectively draw out similarities across the state space, and yield powerful sample efficiency learning. Comparative evaluation shows that Q-learning based RL agents enhanced with our approach outperform statc-of-the-arr RL approaches in both discrete and continuous domains while learning meaningful abstract representations.
Figure 1: Consider classic taxi world with two passengers and building as the drop-off location where the green area is impassable (left). Meaningful conditional abstractions can be constructed, for example. for situations where both passen- gers are at their pickup locations (middle), or one passenger has already been picked-up (right).
The rest of this paper is organized as follows. Sec. summarizes the related work followed by discussion on the necessary backgrounds in Sec. Sec. presents our dynamic abstraction learning method for sample-efficient RL. The empirical evaluations are demonstrated in Sec. followed by the conclusions Sec.6.
RELATED WORK
Offline State Abstraction. Most early studies focus on action-specific (Dietterich 1999) and option-specific (Jonsson & Barto 2000) state abstraction. Further, Givan al. (2003) introduced the notion of state equivalence to possibly reduce the state space size by which two states can be aggregated into one abstract state if applying a mutual action leads to equivalence states with similar rewards. Later on, Ravindran & Barto (2044) relaxed this definition of state equivalence by allowing the actions to be different there is a valid mapping between them. Offline state abstraction has
further been studied for generalization and transfer in RL (Karia & Srivastava 2022) and planning
Srivastava et al. 2012).
State Abstraction. Mannor al. (2004) developed graph-theoree theoretic state ab- straction approach that utilizes the topological similarities state transition graph (STG) to ag- gregate states in online manner. Mannor's definition of state abstraction follows Givan's notion of equivalence states except they update the partial STG iteratively to find the abstractions. Another comparable method proposed by Chiu & Sool (2010) carries out spectral graph analysis on STG to decompose the graph into multiple sub-graphs. However, most graph-theoretic analyses on STG, such computing the eigenvectors in Chiu & Soo's work, can become infeasible for problems with large-scale state space.
Tree Search (MCTS). MCTS approaches offer viable and tractable algorithms for large state-space Markovian decision problems (Kocsis & Szepesvári] 2006). Jiang et al. (2014) demonstrated that proper abstraction effectively enhances performance of MCTS algorithms. However, their clustering-basee state abstraction approach is limited to the states enumerated by their algorithm within the partially expanded tree, which makes it ineffectual when limited samples are available to the planning/learning agent. Anand et al. (2015) advanced Jiang's method by com- prehensively aggregating states and state-action pairs aiming to uncover more symmetries in the do- main. Owing to their novel state-action pair abstraction extending Givan and Ravindran's 's notions of abstractions, Anand Anand et al.]s method results in higher quality policies compared to other approaches based MCTS. However, their bottom-up abstraction scheme makes their method computation-
Monte-Carlo
2

---

Under review as a conference paper at ICLR 2023
ally vulnerable to problems with significantly larger state space size. Moreover, their proposed state abstraction method is limited to the explored states since it applies to the partially expanded tree.
Counterexample Guided Abstraction Refinement (CEGAR). CEGAR is model checking methodology that initially assumes a coarse abstract model and then validates or refines the initial abstraction to eliminate spurious counterexamples to the property that needs to be verified (Clarke eet al.] 2000). While most work in this direction focuses on deterministic systems, research on the topic also considers the problem of defining the appropriate notion for a "counterexample" in stochastic settings. E.g.. Chadha & Viswanathan (2010) propose that a counterexample can be considered as a small MDP that violates the desired property. However, searching for such coun- terexamples can be difficult in the RL setting where the transition function of the MDP is not avail- able. SSipp & Helmert (2018) developed algorithms for planning in deterministic environments that invoke the CEGAR loop iteratively on the same original task to obtain more efficient abstraction refinement. These methods do not consider the problem of building abstractions for stochastic plan- ning reinforcement learning.
3 BACKGROUND
Markov decision Processes (MDPs) (Bellman 1957 Puterman 2014) are defined as tuple (S, A. T. R,,1 7), where S and A denote the state and action spaces respectively, Generally, a con- crete state E S can be defined as set of n state variables such that V = {u,li 1, 1,..., nt. In this paper, we focus on problems where the state is defined using a set of variables. An extension to par- tially observable settings where the agent receives image of the state is a promising direction for future work. T S A S + [0, 1] is transition probability function, R: S x A -> is a reward function, and 7 is the discount factor. The unknown policy и is the solution an MDP, denoted as : S + A. We consider the RL settings where an agent needs to interact with an environment that can be modeled as an MDP with unknown T. The objective is to learn an optimal policy for this MDP.
When the size of the space state increases significantly, most of the RL algorithms fail to solve the given MDP due to the curse of dimensionality. Abstraction is dimension reduction mecha- nism by which the original problem representation maps to new reduced problem representation (Giunchiglia & Walsh 1992). We adopt the general definition of state abstraction proposed by Li ctt al. (006)).
Definition Let M (S.A.T, be the ground MDP from which the abstract MDP M (S, A, R,y) can be derived via state abstraction function o S + S, where the abstract state mapped to concrete state s is denoted as ((8) E S and d (-) is the set of concrete states associated to 8 E S. Further, a weighting function over concrete states is denoted as w(s) with s E S s.t. for each š E S, Eeso 188, w(s) = 1, where w(s) E [0, 1]. Accordingly, the abstract transition probability function T and reward function R are defined as follows:
R(5,a)=
Σ (s)), 8E6-1(8)
T(),a,5)=
Σ Σ w(s)T(s, 366-1(3)
When it comes to the decision-making in an abstract MDP, all concrete states associated with an abstract state E S are perceived identically. Accordingly, the relation between abstract policy π : + A and the concrete policy क + A can be defined as T(s) = #(((s)) for all s E S. Further, the value functions for an abstract MDP are denoted as V* (S). (*(S), Q*(S.a). and
Q' a). For more on RL and value functions see Sutton & Barto 2018). for MDPs, see (Bellman
1957 Puterman 2014). and for more on the notion of abstraction, refer Giunchiglia & Walsh 1992);
Li al. (2006).
4
OUR APPROACH
4.1
OVERVIEW
Starting with state variables and simulator, we develop domain-independee approcach for dynam- ically computing an abstraction based on the dispersion of Q-values in abstract states. The idea of dynamic abstraction is to learn problem's solution and abstractions simultaneously. We propose
3

---

Under review as a conference paper at ICLR 2023
top-down abstraction refinement mechanism by which the learning agent effectively refines initial coarse abstraction through acting and learning. We illustrate this mechanism with an example.
Example Consider a 4x4 Wumpus world consisting of a pit at (2,2) and a goal at (4,4). In this domain, every movement has reward -I. Reaching the goal results in positive reward 10 and the agents receive a negative reward -10 for falling into the pit. The goal and the pit are the terminal states of the domain. The agent's actions include moving non-diagonal adjacent cells at each time step S.I. A = {up, down, left, right).
Considering Example Fig. (left) shows a potential initial coarse abstraction in which the domain of each state variable (here horizontal and vertical locations) is split into two abstract values and S1 and S₃ contain the pitfall and goal location respectively. As result, when learning, the agent will observe a high standard deviation on the values of Q(S, right). r(ght))ght) QSS, down), Q(S4, right), and Q(S4, down) because of the presence of terminal states with large negative or positive rewards. Guided by this dispersion of Q-values, the initial coarse abstraction should be refined resolve the observed variations. Fig. 2 (right) exemplifies an effective abstraction refinement for Example demonstrated as heatmap of Q-values. Notice that the desired abstraction is a heterogeneous abstraction on the domains of state variable values where the abstraction on a variable depends the value of the other variables: let æ and be the horizontal and vertical locations of the agent in Example respectively and their domain be (1, 2, 3, 4). When y > 2, the domain of (originally {1, 2, 3, 4,) abstracted into sets {1,2), (3), and {4), but when y S 2, the domain of x abstracted into sets {1). (2]. and (3, 4).
Refined Abstraction
Abstraction
2
3
4
R
2 3
Figure 2: An example of dynamic heterogeneous abstrac- tion refinement for Wumpus world.
The next section (Sec. 4.2 presents our novel approach for automatically computing such abstrac- tions while carrying out RL.
4.2 CONDITIONAL ABSTRACTION TREES
The value of state variable v, inherently falls within a known range. Partitioning these ranges is one way to construct state abstractions. However, in practice, the abstraction of one state variable conditioned on a specific range of any other state variables. Accordingly, we need to maintain and update such conditional abstractions via structures that we call Conditional Abstraction Trees (CATs) while constructing the state abstractions.
Fig. (right) exemplifies partially expanded CAT for the problem Ex- ample ! This problem can be rep- resented by two state variables, ic. agent's 's horizontal and vertical loca- tion denoted as x and respectively. The tree's root node contains the global ranges (The first range refers the horizontal location and the second range refers to the vertical lo- cation y) for both of these state vari- ables representing an initial coarse abstraction (in white). The annota- tions visualize how this initial ab- straction can be further refined w.n.t state variable resulting in new con- ditional abstractions (symmetric an- notations not shown for the sake of readability). The refinement proce- dure of the Wumpus world associated to each level of the tree is also displayed in Fig. (left).
Oee
refine on
1.2
refine on
3,4
refine on
2
1.2 3.4
B.4 1.21
refine o
3.4 (3.4]
e
0
potential abstractions for further refinement
Figure 3: This figure illustrates Conditional Abstraction Tree (CAT) Example [ Ranges written inside the nodes represent O, E e. Each node represents a conditional abstraction.
4

---

Under review as a conference paper at ICLR 2023
Given the of state variables V. we define abstract state using the set of partitions, for each variable Uss where each partition 0g is an interval of the form [4,, h,]. Thus, a 2-D abstract state for Example [ could be defined by 01 [1. 4] and 82 [1. 2]. An abstraction is defined as @ = {0.]i E n. where n = M In fact, CAT is a hierarchical abstraction tree starting with initial abstraction init that represents the original range for each state variable v; E s
iiiit = {0,l E [1, ni and 4 = ei and ha = uy J. where en and of denote the lower and upper bounds on the range v; respectively. In Example [ there are two state variables so the initial abstraction is init abstraction since the range for each state variable suggests that all values for all state variables is compressed into one abstract state.
{11, 4], [1, 4]}. The initial abstraction also induces the starting coarse
This initial coarse abstraction induced by the initial abstraction Oinit needs to be further refined so that the learning agent can improve its performance through a more fined representation of the problem. We define a refinement function 8(0, i. f) that splits the range of partition 6, O of state variable o; into f equal ranges resulting in new abstractions. Now, we formally define the refinement function f)
Definition 2
Let θ = (0I,..., On) be an abstract state for a domain with variables U1,... Un- We define the f-split refinement of Q w.r.f. variable
8(0, i) = (O',...,'') where all O are the same as & on 0% for k # i. 0, = [1.h] is partitioned with new boundaries at least ||0l/f values apart: L, 11,, (1,122...... ................................ 11, h where L = I+ x [[(h- f)/
Next, we need to define the relation between two given abstractions in the form of θ in order to determine if one is obtained by refining the other one.
Definition 3 Let Ye be the set containing all possible abstractions. Given Oa. O, L say O, is obtained by refining On denoted as O > Oa. iff (Vi E [1) S. 0g). Moreover, O₂ b On = Qa a Db, Although this definition determines an ancestral relation between On and Ob, we need to know the factor f by which O has been refined to determine if O is the direct result of refining O.. We say Oo is obtained directly by refining O.. denoted as O₁ O iff 3 i (0) C 0f), (tlke E [1, (6) =g) and 10%1 x -1%
With these definitions in hand, we can now formally define CAT as an undirected tree construct and maintain the hierarchy of the conditional partitions. Conditional Abstraction Tree (CAT), de- noted as Ç. represents tree structure specifying the topology between conditional abstractions in the form of θ.
Definition 4 A conditional abstraction tree (CAT) is defined as & {N, E}, where N is the set of nodes and E is the set of edges. Each node in N corresponds to an abstraction G, s.t. N = {Oml m [1. ngl}. where nig is the cardinality of CAT, and Oroot - where Oroot is the root mode of the tree. Every parent Op and child θ, nodes in & are connected via an edge eg s.i. eg + Oe D. Op. Additionally, Lę = ( (AAk E [L, (0m) & θx)) is defined as the set leaf nodes. Lg represents the set of abstract states in E.
Given CAT & and the value of a concrete state 8, the mapping d(s) S + S can be done via a level-order tree search starting from Oroot- The correspond- ing abstract state is in the node θ found iff Vi [1, n] o E <0. ofound (inclusion condition) and θ Found is a leaf node, i.e. θ Found E L. Alg. computes the
Algorithm 1: State Abstraction
FindAbstract (CAT &, Ostart, s):
1:
if (Ve, E s) E Optart) then 0 E Lg then
2:
ó S + S mapping for a given concrete state s under CAT &, starting from CAT's root node Oroat- FindAbstract Sstart, s) starts the level-order
3: return Ostart
4:
else
chvidren Children (hildren(Ostarr)) 6: for O E children do
search from θ Ostart and always finds the corre- sponding abstract state when Ostart = Oroot- This algorithm checks the inclusion condition first for Sstart (Line Alg. [T. If @ is not leaf node, the algorithm checks the inclusion condition for children of A (Line 7 in Alg. T and if a child satisfies the condition, F FindAbst gets invoked recursively (Line 8 in Alg.
if (V4, S)(v, E gehsidy then FindAbstract (c. Oobad- s)
8:
5

---

Under review as a conference paper at ICLR 2023
Any state abstraction under given CAT & induces abstract representation of the underlying concrete MDP M. Thus, an MDP M can have two abstract representations Ma and My under two CATs &a and & respectively. We define relational operation to decide which abstract MDP is finer.
Definition Given MDPs Ma and M, abstracted under ça and Eb. we say Ma is strictly finer than Ms. denoted as Ma mh, vff've" E Lg. =0" E Lg, (Go D -6") We also say Ma is finer than Mb. denoted as Ma ž Ma if''v0" Lea 70t E Le, (O" & v -
4.3 LEARNING DYNAMIC ABSTRACTIONS
Definition formalizes the abstraction tree by which the mapping x(s) : - S can be performed 2 explains how a node of CAT can be refined with respect to a state variable e; through the refinement function 8(O, i, f). However, our objective is to interleave RL episodes with phases of abstraction refinement leading to an enhanced abstract policy ह for given concrete MDP M. We need to develop mechanism that 1) observes dispersion of Q-values while the RL agent is acting and learning through the abstract MDP M, and 2) refines unstable abstract states w.r.t state variable.
using level-order search (see Alg. []. while Definition
Therefore, our approach, Dynamic Abstractions for RL (DAR+RL), consists of three phases: the RL agent performs Q-learning over the abstract state space S defined by leaves of the current CAT and learns an abstract policy म; 2) the RL agent continues interacting with the environment via the abstract policy Nे and DAR+RL evaluates the computed abstraction by observing the dispersion of Q-values; and 3) DAR+RL refines the current abstraction by finding unstable abstract states in &. One needs to blame state variable t; for each unstable state since the refinement can be conducted w.r.t to one state variable as defined in Definition 2
Let (, denote the evaluation function which is simply RL routine where the learning agent interacts with an MDP M through a fixed policy स under the abstraction computed by & for one single episode; Throughout one episode of evaluation, the observed dispersion of Q-values is defined as D = {dm |m E [1, [step]]- The observed dispersion D is the set of observed Q* @*(S,ar values for one episode (up Natep steps) of evaluation.
To obtain better exploration abstract states, the evaluation function 3(M, E, #) needs Neval > 1 episodes. That being said, I denotes all observed dispersion obtained by executing the evaluation function for neval episodes, where r {Dm i m E [1, newat denote a function that finds the set of unstable states the form of θ based the dispersion of Q-values in Besides, Unst UnstableVar θ) denotes function that finds the accountable state variable for each unstable state, given the dispersion log r. Altogether, within the DAR+RL learning, evaluation, and refine- phases, the learning agent learns the solution to the MDP M while learning the dynamic abstractions.
the
Algorithm 2: Learning Dynamic Abstractions
be executed for
Input: M.
Output: a
1: initialize Oinit, &, and Q
2: for episode Nepi do
3: s r ()
Let SinatableStaten
4: for sleps in episode do
5:
3 + FindAbstract(f Oinas s)
6:
a + =(5)
7:
8'. F, done + step(extend(a))
8:
FindAbstract(s Pinit
9:
+ (3,3"
10:
8, 8 + 8',5'
11:
if M needs refinement then
12:
for = 1, Reval do Tappend(evaluutteMMM... unstable +- Unstablestate(]
13:
14:
15:
for each θ in unstable do
4.4 DAR+RL ALGORITHM
16:
i Unstabbeeear .) nodes refine + Upedttteeeeee,,, θ, nodes)
Alg. 2 illustrates the procedure by which the agent learns an MDP's solution and abstrac- tions simultaneously through learning, eval- uation, and refinement phases explained in Sec. 4.3 First, the initial coarse abstraction needs be automatically constructed through initializ- ing imits based on the known ranges for each state variable vú and constructing CAT with only the root node (Line in Alg. 2). The initial & induces abstract MDP M for the given MDP M.
18:
return M,C,5

---

Under review as a conference paper at ICLR 2023
Then, the learning phase of DAR+RL starts by employing the Q-learning routine (Lines 10 in
Alg. 2 In other words, throughout the learning phase (lines 2 2 Alg. 2 implement the vanilla Q-learning abstract states computed from the CAT. In this phase, induced by the computed state abstraction, extended actions (taking a concrete action repeatedly until the agent reaches a new abstract state, blockage, or a terminal concrete state) are applied the environment instead of the concrete actions (Line / in Alg. (2. As the result, the agent enhances the abstract policy मे to learn the solution the abstract MDP M.
Since the initial abstraction is likely to be too coarse, DAR+RL checks the refinement condition (Line I in Alg. 2 the end of each learning episode to initiate an evaluation phase followed by a refinement phase. We set DAR+RL to check the recent success rate of the RL agent every Recheck episodes where the refinement condition evaluate true if the success rate is below some threshold. The choice of the refinement condition introduces trade-off. On one hand, we want to obtain a near optimal abstraction that enables the agent to learn the solution effectively. On the other hand, the abstract policy म should be trained enough to be used in the evaluation phase for refinement purposes. When the refinement condition is true, the algorithm runs the evaluation function 3 (a standard Q-learning routine with fixed policy) for neval episodes (Line 13 in Alg. 2). During the evaluation phase, it is likely to encounter an abstract state multiple times. Since the policy is fixed in this phase, comparing different Q-values for the same pair of state-action (5, i(a)) exposes potential inconsistencies in the abstract state 8. To capture such inconsistencies, for all observed abstract states, DAR+RL logs different computed Q-values and store them in r. Then. for each abstract state in I, DAR+RL calculates the normalized standard deviation of all logged ((5, म (a)) (Line 14 in Alg 2p. Considering these calculated values, anstabblStateel states (abstract states with high variations) using clustering techniques. Finally, the unstable states are refined and the abstraction tree is updated accordingly in Lines [5 to 18
finds the unstable
5 EMPIRICAL EVALUATIONS
To assess the performance of DAR+RL, we conducted empirical analysis on three discrete domains: Office World adapted from Iearte et al. (2018), Wumpus World derived from Russell & Norvig 2020), Taxi World adapted from the OpenAl Gym environment Taxi-v3 http:://www.gymlibbt m//enviroommets/toyy ttxtt/////tottttt/taii/// and introduced by Dietterich| (2000), and one continuous domain: Water World based on Karpathy (2015); cearte et (218). All of the domains used are stochastic continuous/discrete problems with varying dimensionality (from 2 to 14). All the details regarding the domains and task descriptions are included in the supplementary document. We aim to investi- gate the following:
* Does DAR+RL improve the sample efficiency of vanilla Q-learning without any expert knowledge?
Is DAR+RL scalable to high-dimensional tasks?
* Does DAR+RL recognize similar abstractions for similar sub- cebb-roblemss in a larger task?
For the comparative study, we selected the following baselines: (1) Option-critic Bacon (201)). (2) JIRP Xu et al. (2020), (3) tabular Q-learning Watkins & Dayan (1922). (4) DQN Mnih et al. 2013).
(5) A2C MnCh et al. (016). and (5) PPOTSchulmal al. (2017). Option-critic is a Hier- archical RL (HRL) approach that discovers options autonomously while learning option policies simultaneously. JIRP automatically infers reward machines and policies for RL. We chose these state-of-the-ar methods as baselines as they do not require expert knowledge as input. We also com- pared with deep RI methods: DQN, A2C, and PPO. The details of parameters and hyperparameters are included in the supplementary document.
For each domain, we executed 10 independent runs for each algorithm and report the mean success rates averaged over last 100 training episodes along with the standard deviations. We also report normalized cumulative reward for each domain and method obtained by evaluating the agent on 10 simulation runs, after stopping training intervals of 10 episodes. We use implementation of DQN, A2C, and PPO from the Stable- Basellies by Raffin et al. (2019). Our code included in the supplementary material. We now discuss our results and analysis in detail below.
7

---

Under review as a conference paper at ICLR 2023
(ours)
Q-learning
JIRP
Option-critic
DQN
Wumnuus
World
1.0
0.4
0.2
2K
20K
2K
10K
Normalized Cumulative Reward
0.6
0.4
Au
1K
2K
3K SK
7K
10K
10
2K
5K
7K 10K
2K
5K
7K
10K
Episodes
Figure 4: (Top) Success rates (mean and standard deviation) for 10 independent runs averaged over last 100 training episodes for all the methods, and (Bottom) normalized cumulative reward for 10 simulation runs ob- tained every 10 training episodes for DAR+RL (ours) and the second-best performing baseline for Office World (36x36), Wumpus World (64x64), Taxi World (30x30), and Water World (300x300) domains.
5.1 RESULTS
Fig. (Top) shows comparison among success rates achieved by all the methods on all the domains. In Office world, DAR+RL outperforms all the baselines and almost converges to success rate of in around 2000 episodes, whereas, PPO reaches an approximate success rate of 0.8 in 2500 episodes and has a high standard deviation. DQN reaches success rate of only 0.65 within 3000 episodes and rest of the baselines struggle to learn and are stuck below 0.2 success rate. In Wumpus world, DAR+RL converges to success rate of within 4000 episodes and significantly outperform all the baselines which stuck below success rate of only 0.2. In Taxi world, DAR+RL achieves success rate almost 1.0 within 12000 episodes of training, while Q-learning and Option-critic perform better than other baselines achieving approximate success rates of O. 0.75 and 0.4 respectively within 20000 episodes. Even the continuous Water world domain, DAR+RL learns slightly faster than PPO while all other baselines perform poorly and are stuck below a success rate of 0.4. We performed further evaluation on DAR+RL and the second-best performing baseline on each domain shown in the Fig- (Bottom) evaluating the policies learned by the agent. In Office and Water worlds, DAR+RL outperforms PPO, and in Wumpus world, DAR+RL gains significantly higher cumulative reward than Q-learning.
5.2 ANALYSIS
Sample efficiency in the absence input expert knowledge. The results presented in Section 5.1 demonstrate that DAR+RL's performance is superior to all baselines in both discrete and continuous domains. This is categorically the effect of the learned conditional abstractions by DAR+RL made available to the vanilla Q-learning algorithm. This effect can be perceived from two perspectives: 1) the meaningful conditional abstractions that are automatically constructed by DAR+RL spotlight the most informative aspects of the state space, leading to more cample-efficiemt learning; and 2) the Q-learning agent benefits from significantly higher levels of exploration over state and action spaces due to the nature of abstraction. This intense exploration cause more penalization of the agent
8

---

Under review as a conference paper at ICLR 2023
at the early stages of learning (see cumulative rewards of DAR+RL in taxi and office world) but eventually leads to faster learning and superior performance reflected the success rate.
Scalability to nigh-ddmennsonal tasks. RL algorithms that learn policy from concrete MDP M suffer from the curse of dimensionality as the size of the state space increases. This explains why most of the baselines fail to learn the Wumpus world, increases drastically, as shown in Fig. In contrast, the top-down abstraction refinement scheme of DAR+RL scales effectively
basic domain, when the size of the grid
problems with relatively larger state space. As result, the ab- stract representations learned by DAR+RL empowered vanilla Q-Learning algorithm to learn those problems relatively fast and efficiently. We conducted further experiments on scalability and com- putational complexity of DAR+RL and baselines and the results are presented in the supplementary document.
Abstractions learned in similar sub-problems. One im- portant property DAR+RL's framework is to construct identical abstractions across the state space for similar sub-problems. This capability DAR+RL is critically beneficial in large problems where options can be gen- eralized across identically constructed abstractions. Fig. 5 demonstrates two constructed conditional abstractions by DAR+RL. for an 8x8 taxi world. In Fig. 5 (middle), the passenger is located top-left and the destination is located at the bottom-left of the map. Besides, in Fig. 5 (right), the passenger is in the taxi and the destination located at the top-left. In both cases, the agent should reach the top-left cell of the map which implies similarity. DAR+RL discovered this similarity automatically as seen from the generated identical abstractions (highlighted area) for both the cases.
G
Figure 5: Drawing out similarities across state space of 8x8 taxi world via DAR+RL's automatic abstraction.
CONCLUSION
We presented a novel approach (DAR+RL) for simultaneously learning dynamic abstract representa- tions along with the solution to problems formulated as an MDP. The overall algorithm of DAR+RL proceeds by interleaving the process of refining a coarse initial abstraction with learning and eval- uation of policies for the underlying RL agent (Q-learning). Besides, we introduced conditional abstraction trees compute and represent such refined abstractions throughout the DAR+RL proce- dure. Extensive empirical evaluation on multiple domains of problems demonstrated that DAR+RL effectively enables vanilla Q-learning algorithm learn the solution large discrete and tinuous problems, with dynamic representations, where state-of-the-art RL algorithms are outper- formed. This superior performance of vanilla Q-learning compared neural-network-basse architecture such as PPO and A2C is due to DAR+RL's 's scalable abstraction construction scheme that effectively draws out similarities across the state space and yields pow- erful sample efficiency in learning. Future work will consider automatic discovery of generalizable options utilizing the constructed conditional abstract representations by DAR+RL.
algorithms with complex
REFERENCES
David Abel, David Hershkowitz, and Michael Littman. Near optimal behavior via approximate state abstraction. In International Conference on Machine Learning, pp. 2915-2923. PMLR, 2016.
Ankit Anand, Aditya Grover, Parag Singla, and Mausam. Asap-uct: Abstraction of state-action pairs in uct. In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
Pierre-Laa Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Richard Bellman. markovian decision process. Journal of mathematics and mechanics, pp. 679
684, 1957.
Rohit Chadha and Mahesh Viswanathan. A coumterexample-guieee abstraction-refinena frame- work for markov decision processes. ACM Transactions on Computational Logic (TOCL), 12(1): 1-49, 2010.

---

Under review as a conference paper at ICLR 2023
Chung- Cheng Chiu and Von-Wun Soo. Automatic complexity reduction in reinforcement learning. Computational Intelligence. 26(1):1-25, 2010.
Edmund Clarke, Oma Grumberg, Somesh Jha, Yuan Lu, and Helmut Veith. Counterexample- abstraction refinement. In International Conference Computer Aided Verification, pp. 159-169. Springer, 2000.
Dennis Dams and Omn Grumberg. Abstraction and abstraction refinement. In Handbook of Model Checking, pp. 385-419. Springer, 2018.
Thomas Dietterich. State abstraction in maxq hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 12, 1999.
Thomas G. Dietterich. Hierarchical reinforcement learning with the maxq value function decompo- sition. Journal of artificial intelligence research, 13:227-303, 2000.
Fausto Giunchiglia and Toby Walsh. A theory of abstraction. Artificial intelligence, 57(2-3):323- 389, 1992.
Robert Givan, Thomas Dean, and Matthew Greig. Equivalence notions and model minimization in markov decision processes. Artificial Intelligence, 147(1-2):163322)) 2003.
Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila Mcllraith. Using reward ma- chines for high-level task specification and decomposition in reinforcement learning. In Interna- fional Conference on Machine Learning, pp. 2107-2116. PMIR, 2018
Nan Jiang, Satinder Singh, and Richard Lewis. Improving uct planning via approximate homo- morphisms. In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems, pp. 1289-1296, 2014.
Anders Jonsson and Andrew Barto. Automated state abstraction for options using the u-tree algo- rithm. Advances in neural information processing systems, 13, 2000.
Rushang Karia and Siddharth Srivastava. Relational Abstractions for Generalized Reinforcement Learning on Symbolic Problems. arXiv preprint arXiv:2204. 12665, 2022.
Andrej Karpathy. Reinforcejs: Waterworld demo, 2015. URL hup://cs. stanford. edu/people/karpa- flyfreinfforeisvvaeeewwrdd html, 2015.
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pp. 282-293. Springer, 2006.
George Konidaris. On the necessity of abstraction. Current opinion in behavioral sciences, 19:1-7, 2019.
Lihong Li. Thomas J Walsh, and Michael L Littman. Towards unified theory of state abstraction for mdps. In AI&M, 2006.
Shie Mannor, Ishai Menache, Amit Hoze, and Uri Klein. Dynamic abstraction in reinforcement learning via clustering. In Proceedings of the twenty-first international conference on Machine learning, pp. 71, 2004.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv: 2013.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference machine learning, pp.
PMLR, 2016.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Antonin Raffin, Ashley Hill, Maximilian Ernestus, Adam Gleave, Anssi Kanervisto, and Noah Dor- mann. Stable baselines3, 2019.
10

---

Under review as a conference paper at ICLR 2023
Balaraman Ravindran and Andrew G Barto. Approximate homomorphisms: A framework for non- exact minimization markov decision processes. 2004.
Stuart J. Russell and Peter Norvig, Artificial Intelligence: A Modern Approach Fourth Edition, 2020.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: NXXV::7777006447 2017.
Jendrik Seipp and Malte Helmert. Counterexampl--guided cartesian abstraction refinement for clas- sical planning. Journal of Artificial Intelligence Research, 62:535-577, 2018.
Siddharth Srivastava, Neil Immerman, and Shlomo Zilberstein. Applicability conditions for plans with loops: Computability results and algorithms. Artificial Intelligence, 191:1-19, 2012.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3):299-292, 1992.
Zhe Xu, Ivan Gavran, Yousef Ahmad, Rupak Majumdar, Daniel Neider, Ufuk Topcu, and Bo Wu. Joint inference reward machines and policies for reinforcement learning. Proceedings of the International Conference Automated Planning and Scheduling, volume 30, pp. 590-598, 2020.
Yang Yu. Towards sample efficient reinforcement learning. In ICAI, pp. 5739-5743, 2018.


Reviews:
[{"review_id": "qpChYU_LTn", "reviewer": "Reviewer_6Ztx", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose an approach to abstraction in reinforcement learning. The proposed approach starts with a coarse state abstraction and iteratively refines it. The basis for the refinement is the dispersion in the Q-values as the agent continues to learn. The approach is empirically evaluated in three grid-based domains (Office World, Taxi World, Wumpus World) and one domain with continuous state variables (Water World).\n", "summary_of_the_review": "The paper presents a plausible approach to an important problem in reinforcement learning. However, important algorithmic components are not fully specified. Furthermore, the experimental evaluation is narrow in scope, both in the types of domains tested and in the analyses conducted in each domain. As a result, the strengths and weaknesses of the algorithm are not adequately understood. ", "strength_and_weaknesses": "Strengths: Abstraction in reinforcement learning is an important area of research; the general approach explored here (iterative course-to-fine refinement of the state space) is plausible.\n\nWeaknesses:\n\n-- Some critical parts of the algorithms are not fully specified. These include how to determine whether M needs refinement (line 11 in Algorithm 2), how to determine whether a state is unstable (the authors note that this is \"based on the dispersion of Q-values\"), and how to determine which variables are accountable for the unstable state. These issues are very briefly discussed at the end of Section 4 but are not fully specified. \n\n-- The experimental results do little more than present performance metrics. Furthermore, they treat the proposed algorithm as a monolithic structure, without any exploration of its individual components, of the impact of specific algorithmic choices (versus plausible alternatives), and the sensitivity to any parameters. \n\n-- While experimental results are presented in four different domains, three of these domains are very similar to each other (grid-based environments with additional variables). \n\n-- The computational complexity of the approach has not been explored.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "qPgH-WVQjdq", "reviewer": "Reviewer_4Xkd", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a method which divides the state space into discrete “abstractions”, based on variance of the state action values.  They compare their method to several baselines.\n", "summary_of_the_review": "This paper is very well-written.  However, despite all the notation, its contribution is entirely empirical, and I have concerns about the quality of the empirical work.\n", "strength_and_weaknesses": "Minor nitpick: in the definition of \\mathcal V, doesn’t the notation i \\in [1, n] imply that i takes a continuous range of real values in that range?  Wouldn’t it be more correct to write {1, 2, …, n}?  (Please ignore this if I’m incorrect.)\n\nDefinition 5: I think there may be a few errors here.  After the first “denoted as”, there are two a’s (shouldn’t there be an “a” and a “b”?).  Also, are l_a and l_b defined?  I’m aware of the definition above where they are a scalar lower bound of an interval for a theta_i, but that does not seem their usage in this definition.\n\nStrengths:\n- This paper was exceptionally clear and well-written.\n- The included code is a nice addition; it appears to be well-organized.\n\nWeaknesses:\n1. Minor weakness: I believe the paper overstates the general utility of this approach.  For example, consider a task in a 3-D world where the observation is pixel input.  Clearly, the authors’ approach will not be helpful in this case, since DAR+RL will attempt to divide the world up based on uninformative ranges of individual pixels.  This concern is not limited to pixel input.  This is not to say that this approach is not a valuable contribution, but I wonder whether many real-world problems with high-dimensional state spaces can be made more tractable by this approach.  Weakness 4 below is closely related to this. I am concerned that the authors are overselling their approach and sweeping its limitations under the rug.  Instead, I’d advise frankly discussing these limitations, discussing future work which might allow one to overcome them, and evaluating on more diverse environments (again, see weakness 4).\n    - Of course, DAR+RL will be more effective if the state/observation is designed to be more suitable to it (e.g., use x/y coordinates rather than pixel inputs), but hand-designing the state/observation like this defeats the intended purpose of DAR+RL.\n2. Minor weakness: Given the well-known high variance between RL runs, 10 trials is not ideal to demonstrate the claims being made.  However, I am not overly concerned about this in this case, given the plots (which seem to show clear trends) and the more pressing concerns below.\n3. Major weakness: Not all hyperparameters are included (particularly the architectures’ hyperparameters, but also details about the optimizers, etc.).  This is closely related to weakness 5.\n4. Major weakness: All domains are some variety of 2-D gridworlds.  This limits the convincingness of the empirical work and is closely related to weaknesses 1 and 5.  It also makes the paper’s claims about “high-dimensional tasks” unconvincing, since these environments all seem to have 1-2 dozen state dimensions at most, while a large proportion of modern RL focuses on tasks with hundreds or thousands of state or observation dimensions.  One fix for a future submission would be to include higher-dimensional (non-gridworld) tasks such as mujoco domains to the experiments.\n5. Major weakness: Some important details about the baselines are unclear to me.  Particularly, the details of the architectures used are missing.  I’m not sure any of the baselines are fair because:\n    - The tabular Q-learning approach will, of course, not perform well given so many possible states.\n    - The following bullet points assume that the other methods all took real-valued x and y inputs to the neural nets (the same type of inputs that DAR+RL received), and used some standard deep architecture from stablebaselines3.  I believe all baselines other than tabular Q-learning fall into this category.  If this is not the case, the situation could be better or worse, depending on the details:\n        - The deep RL approaches will not perform well without hyperparameter tuning (which seems to have been done for DAR+RL, but not the baselines).\n        - Worse, these architectures are designed for much more complex environments, and so will perform relatively poorly in terms of data efficiency compared to a “quasi-tabular” approach such as DAR+RL, since their networks are excessively large and overparameterized for these type of problems.  Better baselines might be linear function approximators (see the Sutton and Barto book, 2nd edition, for a good list of effective ones) or perhaps very small neural networks, since these approaches can be expected to learn these these simple environments, with their relatively-small-number-of “continuous” state dimensions (most are not truly continuous, but the agents observe continuous values), more efficiently than large deep nets.\n6. Minor weakness: I do not believe the details of the UnstableState function (line 14 of algorithm 2) used in the experiments were given.  These details, including relevant hyperparameters, should be provided.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "3mxFIuZxALS", "reviewer": "Reviewer_3y7Q", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper aims at iteratively computing an abstraction based on the dispersion of Q-values for states that have been aggregated together.  The paper describes the algorithm with a formalization and some pseudo-codes. The algorithm is tested on different discrete and deterministic grid-world environements.", "summary_of_the_review": "I have two main concerns. \n- The writing of the paper and the lack of clarity with respect to some of the key components.\n- I have doubts about the actual procedure that the paper describes (the formalization and the pseudo code do not provide enough details).", "strength_and_weaknesses": "Strengths:\n- The paper makes use of simple examples to motivate the approach.\n\nI have two main concerns. \n- My first concern is related to the writing of the paper and the lack of clarity with respect to some of the key components.\n- Second, I have doubts about the actual procedure that the paper describes.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject