Cyclophobic Reinforcement Learning
Authors: Stefan Sylvius Wagner
Peter Arndt
Jan Robine
Stefan Harmeling
Venue: Accepted by TMLR ()

Abstract: In environments with sparse rewards, finding a good inductive bias for exploration is crucial to the agent's success. However, there are two competing goals: novelty search and systematic exploration. While existing approaches such as curiosity-driven exploration find novelty, they sometimes do not systematically explore the whole state space, akin to depth-first-search vs breadth-first-search. In this paper, we propose a new intrinsic reward that is cyclophobic, i.e., it does not reward novelty, but punishes redundancy by avoiding cycles. Augmenting the cyclophobic intrinsic reward with a sequence of hierarchical representations based on the agent's  cropped observations we are able to achieve excellent results in the MiniGrid and MiniHack environments. Both are particularly hard, as they require complex  interactions with different objects in order to be solved. Detailed comparisons with previous approaches and thorough ablation studies show that our newly proposed cyclophobic reinforcement learning is more sample efficient than other state of the art methods in a variety of tasks.

Published in Transactions on Machine Learning Research (08/2023)
Cyclophobic Reinforcement Learning
Stefan Wagner' Peter Arndt Jan Robine² Stefan Harmeling"
Heinrich Heine University Düsseldorf 2 Technical University Dortmand (stefan.wagner,
wagner, peter arndtt) de {jan.robine, stefan. harfelinn @tt-dortmund.dee
Reviewed on OpenReview: https: // openreview. net/ not/forum? id- 83
Abstract
In environments with sparse rewards, finding good inductive bias for exploration is crucial to the agent's 's success. However, there are two competing goals: novelty search and systematic exploration. While existing approaches such as curiosity-driven exploration find novelty, they sometimes do not systematically explore the whole state space, akin to depth-first-searee search vs finutth-iiist-seachh In this paper, we propose a new intrinsic reward that is cyclophobic, i.., does not reward novelty, but punishes redundancy by avoiding cycles. Augmenting the cyclophobic intrinsic reward with sequence of hierarchical representations based on the agent's 's cropped observations MiniHack environments. Both are particularly hard, as they require complex interactions with different objects in order to be solved. Detailed comparisons with previous approaches and thorough ablation studies show that our newly proposed cyclophobie reinforcement learning is more sample efficient than other state of the art methods in a variety of tasks.
are able to achieve excellent results in the MiniGrid and
1 Introduction
Exploration is one of reinforcement learning's most important problems. Learning success largely depends on whether an agent is able to explore its environment efficiently. Random exploration explores all possibilities but at great costs, since possibly revisits states very often. More efficient approaches can use intrinsic rewards based novelty (Ostrovski et al.) 2017: Bellemare et al., 2016), where the occurrence of states is counted and some novelty metric is determined can be based curiosity where novelty in the represontations is determined (Pathak et al. 2017 Burda et al., 2018 Raileanu & Rocktäschel] 2020: Zhang et al. 2021 This often leads to great results, but at the price of possibly not exploring all corners of the environment systematically. The latter also paradoxically end up being less sample efficient, when alcatoric uncertainty in the observations not large enough to give an informative reward signal, such as in environments which are challenging from a combinatorial standpoint, but where the observations are simple (Parisi et al., 2022]] Especially in environments where the task is complex we would ideally pursue both goals: novelty search and systematical exploration.
How can we favor novelty while ensuring that the environment is systematically explored? To achieve this, we propose cyclophobic reinforcement learning which is based on the simple idea of avoiding cycles during exploration. More precisely, we define a negative intrinsic reward, i.c., the cyclophobic intrinsic reward that penalizes redundancy in the exploration history. With this we ensure two things: first, the agent receives immodiate feodback about which state-action pair to discourage. Sccond, by maximizing the agent's actions it is forced to take the next unexplored stale-action pair since already explored stale-action pairs will have a negative intrinsic reward. This approach is similar to optimistic initialization (Machado et al.) 2014] where the value function is initialized with high value and as the update rule is applied, the values will decrcase for subsequent visits, thus forcing the agent to take the next unexplored action with highest remaining value. In this sense, the cyclopohobie intrinsic reward can be seen as a count-based extension of optimistic initialization.
The cyclophobic intrinsic reward further enhanced by applying it several cropped observations of the environment which we call hierarchical state representations. Furthermore, we call the single cropped views,
1

---

Published in Transactions on Machine Learning Research (08/2023)
hierarchical views. The notion of redundancy can be defined relative to cropped views of the agent: while cycles in the global view induce cycles in a corresponding smaller view, the converse is not the case. Eig., a MiniGrid agent turning four times to the left produces a cycle in state space that we would like to avoid everywhere. This cycle occuris in the global view, but penalizing it only in the global view does not avoid it other locations. However, with a hierarchy of views, we record cycle in some smaller view as well, which allows us to transfer this knowledge to any other location of the environment and to hereby avoid further cycles for parts in the environment that look the same. Similarly, cycles on a hierarchical level reveal structural properties about the environment. An interesting object such as key, produces less cycles in a smaller view than some other object (since e.g. the key can be interacted with). Thus the probability of picking up the key increases, since other less interesting observations produce more cycles (e.g a wall). Overall, a hierarchy of cropped views is a state represenlation that is complementary to the cyclophobic intrinsic reward that does not require the learning of an inverse dynamics model as in other works (Pathak et al. 2017 Henaff et al. 2022). The approach of exploiting a prioproceptive inductive bias for the obscrvations can also be seen in Parisi al. (2021). where 360" panoramic view of the environment is created, which enhances the information the intrinisic reward gives about the environment. An important aspect of exploration and another desirable property of hierarchical views is that they are task-agnostic (Parisi et al. 2021p. That is, the cropped views of the environment can be transferred to other environments and are not task dependent. Thus, hierarchical state representations on one hand generalize cycles when learning about a task, but also represent lask-agnostic knowledge when transferring knowledge to other tasks.
Contributions:
1. We introduce cyclophobic reinforcement learning for efficient exploration in environments with extremely sparse rewards and large action spaces. It is based on cyclophobie intrinsic reward for systematic exploration applied to a hierarchy of views. Instead of rewarding novelty, we avoid redundancy by penalizing cycles, i.e., repeated state-action pairs in the exploration history. Our approach can be applied to any MDP for which a hicrarchy of views can be defined.
2. In the sparse-reward setting of the MiniGrid and MiniHack environments we thoroughly evaluate cyclophobic reinforcement learning and can show that it achieves excellent results compared to existing methods, both for tabula-rasa and transfer learning.
3. In an ablation study we provide deeper insights into the interplay of the cyclophobic intrinsic reward and the hierarchical state representations. We provide insight into the role of learning representations for exploration. We show that exploration and therefore learning success depend greatly on the function approximator learning appropriate invariances that reduce the complexity of the state space.
Notation: We define an MDP as a tuple (S,A,P,R, 7), where the agent and the environment interact contimuusly at discrete time steps t = 3,, We define the state an agent receives from the environment as a random variable 5. E 8, where 5. timestep t. From that state, we define a random variable for the agent selecting an action A, E A where A, = a is some action in the possible set of actions A for the agent at timestep This action is selected according to policy x(a s) TTs) if the policy is deterministic. One time step later as consequence of its action, the agent receives numerical reward which is a random variable Re41 E R. where R++1 = r is some numerical reward at timestep 1 1+1. Finally, the agent finds itself in a new state Se+1- Furthermore we define a POMDP (S, R, 7, as a generalization of an MDP in the case the true state space S is unknown. That is, the agent sees the state s E S through an observation o E O, where an observation function Z S + O maps the true state to the agent's observation.
some representation of the state from the set of states S
2 Building Blocks
We begin by first defining the cyclophobic intrinsic reward and hierarchical state representations as they are the building blocks of our method. Finally, we define a policy which combines the intrinsic and extrinsic rewards together with the hicrarchical state representations form a global policy which the agent acts upon.
2

---

Published in Transactions on Machine Learning Research (08/2023)
2.1 Cyclophobic Intrinsic Reward
For efficient exploration, redundancy must be avoided. A sign for redundancy is when states are repeatedly explored, with other words, when the agent encounters cycles in the state space instead of focusing on novel areas. To guide the exploration, we will penalize cycles using & cycle penalty, which we call cyclophobic intrinsic reward (a negative intrinsic reward). This avoids redundancy such that uninteresting parts of the state-action space are discarded quickly. For instance; an agents gets stuck in some area, typically, is facing numerous cycles. In such a situation we would like the agent to assign penalties to the repeating state-action pairs in order to focus on more promising parts of the state space that do not cause immediate repetition.
Formally, let us assume that we have per episode a history of previous state-action pairs Hepisodic {($1, a1), (82, a2),.... (st, {t)} and we are currently at the stale-action pair (#++1,0++1)) We say that we have encountered a cycle if the state in the current state-action pair appeared already in the history, ie. (S1+1, a(+1) E Hepisodie. For its first repeated occurrence, we will penalize the state-action pair (8t, 0e) (just before the cycle) by negative one,
(sycle a; Hepisodic) -1
(1)
Note that the cycle penalty as a function depends on the episodic history Hapisodie- If a cycle is encountered multiple times, c.g. I times, the overall cycle penalty for a state-action pair is -I. That is, during exploration the cycle penalty can penalize indefinitely. However, note that every single repeated encounter is penalized with- -1. For pairs (s. a) that have not created cycle, Teyele (s, a; Hepisodie) = 0.
Learning with cycle penalties. In principle, the cycle penalty be combined with any reinforcement learning algorithm. However, we explain how it can be built into the SARSA update rule, since the latter will propagate the penalty across the trajectory. This is important as we want the cycle discouragement to happen on-policy, i.e. the state-action pair before the cycle should be penalized. Eventually, through the SARSA updates this information will propagate other state-action pairs. To learn the Q-function, we are employing the standard SARSA update rule,
Q(s,a) + (1 (1-1) n) Q(s. + u()(ss + +*Q(s,a'))
(2)
with (s, a, Tex: s', aa) being a transition, 7 being step size and where the total reward r(s, a) for the state-action pair (s, a) the weighted sum of the extrinsic reward from the environment rex and the eyclophobic intrinsic reward Teycle defined above,
r(8, = p (8, + reyelo(8, a; Hepisodie)-
where p trades off extrinsic and intrinsic rewards.
2.2 Hierarchical State Representations
Besides penalizing cycles, the second key idea of this paper is to consider a hierarchy of state representations. For this, we repeatedly crop the agent's 's observations to induce additional partially observable Markov decision processes (POMDPs). In general, restricting the view leads to ignoring information about the environment, however in combination with the cyclophobic intrinsic reward we gain additional information about the structure of the environment as we get different Q-functions for different POMDP's. The relevant insight is that on limited views lower down the hierarchy, trajectories can contain cycles that have not been experienced views higher up the hierarchy. These cycles in smaller views represent transferable knowledge about the structure of the environment. E.g. in the MiniGrid environment (sce Section B.1 encountering wall in the smallest view will cause a cycle, capturing that running into a wall is counterproductiiv. On larger views this knowledge only available directly, we tried all walls everywhere. So, the smaller views capture relevant invariances that also apply to the larger views. Hicrarchical state representations also enable task-agnostic learning (Parisi et al.] 2021). That is, when learning an exploration policy we want to learn policy that together with its representations can be transferred to other environments. By definition, the hierarchical
3

---

Published in Transactions on Machine Learning Research (08/2023)
state reprosentations allow to transfer learned invariances in smaller views to other environments by simply keeping these views for transfer learning. In general MDPs, it might not be obvious how to define hierarchical state representations. Ideally, the agent has some sort of sense of "location" to allow cropped views to be meaningful. In general, for grid world-like environments, the hicrarchical state representations are easily definable, since the agent has a defined location that can be used to define smaller neighborhoods typically corresponding to limited views around the agent or from the agent's view.
V/
V/
(a)
Figure 1: Hierarchical views allow us to transfer relevant invariances about the environment. (a) The three different representations are obtained by cropping the observation for each state-action pair as, V1 the full view where the agent sees the whole environment or the largest portion of it. V/ is an intermodiate cropped representation of the agent's view that helps the agent gencralize by reusing familiar observations. V3 the most restricted view where the agent only sees what immediately in front it. (b) Through the views V1 to V& the amount of cycles continuously increases the observations in the higher views can be mapped multiple times to the same observation in the lower view. This naturally leads to each view being separate POMDP describing the true MDP.
To discuss the roles of the different views more precisely, let's consider three such cropped views which consist of the global view Vi, the intermediate view V22 and the smallest possible view V/3 (see Figure Tai. Each view gives a new, typically more limited, perspective of the true state. As shown in Figure 1b each view induces a different set of cycles, for instance a sequence of actions which do not lead to a cycle the full view Vi, might lead to cycle in a smaller view V3, because in the latter, more states are mapped the same observation. Thus, the different views provide different types of information which are useful for learning and allow the agent to focus on different, properties of the environment.
In general, we can have an arbitrary number of views. Each view V/2 induces a POMDP
Vi = (S, ,,,,,, 2
(4)
each having their own set of observations V4 and observation function 2V: S + ON, All POMDP's V1, V2.... operate on the same state space S, however they have different sets of observations O and corresponding observation functions. General POMDPs can have a probabilistic observation function. In our case, the observations are deterministic functions of the full view, e.g. the observations for the ith POMDP of state is
0% 2
which corresponds to the cropping for the view V4. Hereby create partial representations of the state space that allow us to identify invariances in the environment by looking at the same truc state s through different perspectives.
Note that, POMDPs are normally used to model uncertain observations. That is, they are generalization of MDPs where the true state not observable. Here, the POMDP idea is used to model different views of fully observable state space. Therefore, we do not seek to solve a POMDP problem, but rather we extend regular MDP to get redundant. hierarchical representations.
4

---

Published in Transactions on Machine Learning Research (08/2023)
2.3 A cyclophobic policy for hierarchical state representations
In the following, we describe how the cyclophobic intrinsic reward and the hierarchical state representations can be combined into policy that exploits the cyclophobic inductive bias. For this, we define several Q-functions along the views, and combine them as a weighted sum. The weights are determined by counts of the observations in each observation set O% which we explain next.
Mixing coefficients. Many strategies for defining mixing coefficients are possible. For concreteness, in this paper we follow simple schema, where we determine the weights from the obscrvation counts, which are obtained from the history of states visited throughout training,
Hall {11, 82,...;
(6)
Note that Hall contains all states that have been visited in the training so far, which is different from the states in the episodic history Hepisodie that was used in Sec. 2. to define cycles. Denoting the corresponding views of the history as of = (se); the counts for view V/2 are No (..,))
(7)
where N counts the number of times the observation of has been encountered. The raw counts are normalized by their maximum (maximum for simplicity, other normalizations are possible), because the smaller views have higher counts than the bigger views. The weights should be large for states that have been seen less often, so we subtract the normalized counts from one,
((
a (o (o%))=1 =1
(8)
(N ), (o ), ..... N(O
The previous formula allows us to compute the weights for cach respective view VÚ for a single state St,
(x)) = [o (2 (s)))..... o (s:)) = ( (o.)) (...,, a Va (o)))
(9)
where (81) is vector. Finally, the softmax operator turns these weights into vector of probabilities,
a(s)) softmax(a, (s:)) (c) (s)))
(10)
The entries of this vector are denoted by (x)))) and are used to define the cyclophobic Q-function in the next section. The definition a can be extended all state 8 by setting it to zero for unseen states, i.e. a(s)
(zero-vector) for s & Hall
In general, larger views in the hicrarchy will have bigger entrics in (ss)) the observations repeat less often than in the smaller views. Thus asx;) gives more weight to the larger views than the smaller ones. However, the converse is true for the cyclophobic intrinsic reward, since in the smaller views the cyclophobic penalty is given far more often than in the larger viows and thus the q-values in smaller views will be higher than in the larger views.
Cyclophobic Q-functoon. To combine all views into single global policy we define mixture over the different Q-functions learned with the cyclophobic intrinsic reward as defined in Section 2.1 For view V,, we define Q-function as
Q(0 + (1 n1) Q(ok,a) + m[r(o" (a) + 7Q(0" "a)))
(11)
This follows from our argumentation in Section 2.2 where we replace the state s in Equation 2 by the observations Ki in their respective views. Then we can define cyclophobic Q-function as the mixture of the Q-functions of each view,
Deycle = Q(2)))))))) Σ =a())) ((6)))
(12)
Note that the mixing coefficients as (s:) are only non-zero for states st that appeared in the global history Hall- Thus the cyclophobic Q-function is zero for states s & Hall not encountered.
5

---

Published in Transactions on Machine Learning Research (08/2023)
Cyclophobic policy. Finally, the cyclophobic policy is defined the greedy action for the eyclophobic Q-function, i.e.
(5) = arg max Qaycle (8, a) = arg max (a((s)((0),a))
(13)
Having normalized the counts within each view ensures comparability of the counts. This ensures that Q-values from rare i.e more salient observations have larger effect on deciding the action for the policy In ablation study in Section 3 we show that the combination of the cyclophobic intrinsic reward and hierarchical state representations is crucial to the method's d' success.
3
Experiments
Our experiments are inspired by Parisi al. (2021) and Sammelyan et al. (2021). We test in environments where the causal structure is complex and the binding problem (Greff et al. 2020), (van Steenkiste al.) 2019) arisos. That is, where some form of disentangled reprosentation of the environments plays an important role for efficiently finding solutions.
Environments:
We test our method on the MiniGrid and MiniHack environments:
et al. 2018 consists of series of procodurally generated environments where the agent has to interact with several objects to reach specific goal. The MiniGrid environments pose currently a benchmark for the sparse reward problem, since a reward is only given when reaching the final goal state.
The MiniGrid environment (Chevalier-Boistee
The MiniHack environment (Samvelyan al. 2021] is graphical version of the NotHack envi- ronment (Küttler et al. 2020). We select environments from the Navigation and Skill tasks. The MiniHack environment has richer observation space by containing more symbols than the MiniGrid environments and richer action space with up to 75 different actions. While not necessarily tailored to the sparse reward problem as the MiniGrid environment, the high state-action complexity makes it one of the most difficult environments for exploration.
choose five croppings of the original full view. The views V1, V2, Vg, V4, V/s are of grid size 9 x 9, 7 x 7, 5 5, 3 x 3 and 2 x 1. In principle we could also include the full view. However, in the experiments the performance was much better when we limit ourselves to the partial views. Furthermore, every part of the grid that behind of the wall from the agent's perspective is occluded (note that this is not the case in Figure Ia for visualization purposes). Intuitively, limiting the views allows the agent ignore irrelevant details that are far away.
State encoding: For both environments
Next, the views are mapped to hashcodes (we use the open source rzhash library). That is, have hash function g that maps observation of to hashcode n. = g(oV'). This helps to quickly check for cycles we only need to chock whether two hashcodes are equal. For the MiniHack environment, text prompt is an integral part of the current state. So, for MiniHack, the hashcode for a state is the concatenation of the hashcodes of the observation of and the text prompt m,, where m, E R is an encoding of a string of length k, i.e.
h, = g(o)) + gmm.)
('+' denoting concatenation)
(14)
Overall, while the observations in the MiniGrid and MiniHack environments are more simple than in for instance Atari [Bellemare et al.) 2012) or Habitat Savva et al.) (2019), the action-space and task that have to be solved are more complex in the MiniGrid and MiniHack envirouments.
Training sctup and basclines: We train each agent for three runs using different seeds for every run. For transfer learning, we use the "DoorKey-8x8" and ("iiiEnnMMMiRRooomNNV "KeyCoridorS3R3" "BlockedUnlock "inkckkkp setups for pretraining. For each environment pretrain for million steps. For the

---

Published in Transactions on Machine Learning Research (08/2023)
MultiEnv setup this means that pretrain for total of 15 millions steps which is less than Parisi et al. (2021)ss i 40 million steps. For transfer learning, during pretraining save the extrinsic rewards in a second separate Q-table in addition to the main Q-table which contains values of equation 2 These extrinsic rewards in the second Q-table are then used at the beginning of transfer learning for each environment, while we continue to use the cyclophobic intrinsic reward when doing transfer learning. The baselines for the MiniGrid experiments are provided by Parisi et al. (2021) and allow us compare our method to C-BET (Parisi et al, 20210, Random Network Distillation (Ostrovski et al., 2017), RIDE (Raileanu & Rocktäschel] 2020) and Curiosity-driven exploration (Pathak al. 2017). Furthermore,
also compare to NovelD /Zhang al. 22011. For the MiniHack environment we compare our results to the baselines presented by (Samvelyan et al.
[2021) which include IMPALA (Espeholt et al. 2018), RIDE (Raileanu & Rocktäschel] 2020) and Random
Network Distillation Burda et al. 2018). For the skill lasks the only available baseline is IMPALA Espeholt
et al. 2018
Evaluation metric: While during learning the intrinsic reward based on cyclophobia plays the essential role, the ultimate goal is to maximize the extrinsic reward that is provided by the environment. Thus for comparison, we have to plot the extrinsic reward the agent receives for each episode. The reward ranges from to
3.1 MiniGrid
unlock
DoozRay- -ax
36
unlookeioksp
oC www.kelddoor...ooooo
8.0
0.00
1.00
0.79
Eatrinaic Daward
025
2.5
14
688
24
43
48
1984
28
43
61
A3
1983
80
11
100
20
80
810
ObotroctedMMee 10th
Obst root AGNA 20th
GD 10 www... ze 201hb
000
1.00
0.00
0.55
102
25.
302
60
822
102
Dunber
Btogs (Millions)
Cyc Lpc
onlyl
We converge faster than C-BET Parisi et al. 2021 in many MiniGrid environments with and w/o pretraining. We also converge faster than NovelD Zhang et (2021) which we compare to the "no transfer" setting only. The hicrarchical state representations and cyclophobic intrinsic reward extremely quick to converge which shows efficient exploration and the usefulness of the cropped representations, since also able to transfer knowledge by pretraining other environments.
Figure 2: MiniGrid:

---

Published in Transactions on Machine Learning Research (08/2023)
To test our method in the MiniGrid environment choose the same training setup of Parisi et al. (2021 That is, we determine the performance of the agent with no pretraining and when pretraining from other environments as explained in the previous section. 2 shows the agent's performance when training from scratch (rows three and six) and when transferring knowledge from protrained environments (bottom three rows).
Learning from scratch (rows three and six): In three out of six environments, our proposed method converges much faster than the competitors, including C-BET (Parisi et al. 2021 and NovelD) Zhang et al. [2021). Only "KeyCorridorS3R33" "MultiRoom" and "ObstructedLMaze-21 pose significant challenges to our approach, because our method is tabular and thus cannot deal with loo many object variations in the environment (e.g. random color changes). This is discussed in Section 5.1. Furthermore, the "MultiRoom" environment proves challenging for all environments with only C-BET and NovelD managing to reach convergence, while we are able to fetch some rewards. This is due the large amount of observations the different corridors produce. Note that we were not able to reach convergence in DDbstruccedMMaxe2DDbb with NovelD. In Figure @ our approach also excels in the "KeyCorridorS3t3"" and more difficult environments once remove the colors, e.g. "KeyCorridoSS4R3", "KeyCorridorSR33" "KeyCoriidor6R33"
Transferring knowledge (rows one, two, four and five): Having trained environment can transfer knowledge to different one? In some environments the transfer even improved the results from the "no transfer" setup (see "Unlock", "Doorkey", "UnlockPickup", "BlockedUnlockPPicee "OistructeddMaas=1DDi and never deteriorated performance.
3.2
MiniHack
Room-Bandoor 15x15
Roca-Dark--150
ReyRoca--S
Biver-Barrow
1.0
GOT COTSISSAAR CARS
06
022
4.
10.00
120
Oysiophobicr
Number ot Steps (Millions)
Figure 3: MiniHack Navigation: The agent converges quicker in the Navigation task than the intrinsic curiosity baselines such as RIDE (Raleaauu Rocktäsche] 2020 and Random Network Distillation (Burda et al. 2018 This corroborates our hypothesis, that avoiding cycles essential for quick exploration.
WoD-Basy
Hear
LockedDoor: Pizeed
2.5
02
150 125
1688
100
15.0
280
250
36/0
20 4.
8.0
1660
180
150
203
250
3100
150 150
250 250 30.0
Cyclophhbb (Curs)
Iegala
Funber of Stepo [Ms11lonn)]
Figure MiniHack Skill: We converge quicker than IMPALA (Espeholt al. 2018 in the Skill task. The Skill task defines over 75 different actions the agent must learn to use making it one of the most difficult sets of environments of the MiniHack suite.
To push our approach to its limits, we also lackle some of the MiniHack environments which requires the agent to learn a large skill set.
Navigation task: For the simpler navigation tasks shown in Figure 3 our method converges quicker than intrinsic curiosity driven methods such as RIDE and RND. Especially, in the "River"
8

---

Published in Transactions on Machine Learning Research (08/2023)
environment, only our cyclophobic agent is able to converge and solve the environment. However, of course there are environments such as "RoomUltimate where our approach fails due to its tabular style, which limits the complexity of the environment.
For the Skill task the only available baseline is IMPALA which is not based on intrinsic curiosity. Here we are also vastly superior, even collecting extrinsic rewards when the bascline not ("Wear" and "LockedDoor-Fixel/
Skill task:
3.3 Ablation Study
We analyze several aspects of cyclophobic reinforcement learning in our ablation study, We first take a look at the impact of hicrarchical state representations the performance of cyclophobic reinforcement learning (see Figure 5). Purthermore, we study how observational complexity affects exploration by ablating a reward-independent observational feature in the observations, that is we reduce the number of different colors Finally, we also analyze how efficiently the cyclophobic intrinsic reward explores the environment by visualizing state visitation counts (see Figure
for objects in the "KeyCorridor" environment (see Figure G
Impact of hierarchical views: In Figure 5 we analyze the impact of the hierarchical state representations on the agent's performance. The training sctup is describod in section C.3 We ablate the hicrarchical views in ways. (i) In the first two figures we measure performance of cylophobic reinforcement learning and optimistic initialization with and without the hierarchical views. Both for optimistic initialization and for cyclophobic reinforcement learning the hicrarchical views improve performance. (ii) In the middle two figures we measure the effect of weighting the different views according to their visitation counts. We see that for "River" the performance is improved while for "UnlockPickup" both weighted and unweighted variants perform the same. Overall the effect of weighting the different views is not very pronounced. (iii) Finally in the last two figures we toggle the largest, intermediate and smallest views. Only using single views performs the worse. Combining the largest and smallest views improves performance, especially for "River". However, the best performance is achieved when combining largest, intermediate and smallest views together.
Comparison To optimistic Init
Weight Ablation
view Ablation
CnlockFiskup
LockkPickup
OnlockPickup
1.0
0.2
0.00
2.10
4.00
000
255
5,00
7:50
10.00
0.00
2.00
4.00
0.00
2.50
3.00
7.50
10:00
0:00
2.00
4:00
0.00
2:50
5.00
7.50
10.00
Number of Stage (Millions)
cyclopheace
optantncs apedlon-grendy
Enwaighoed
Vedghoed
List
Figure Hierarchical state representations ablation: Hierarchical state representations are crucial to performance in cyclophobic reinforcement learning. In the first. two figures we compare cyclophobic reinforcement learnign to optimistic initialization with and without hierarchal views and see that hierarchical views improve performance for both the optimisitic initialization and cyclophobic agent. In the two middle figures we measure the effect of weighting the different views. In the last two figures we toggle between the largest, intermediate and smallest views. We see that all types of views deliver the best performance.
Importance of state representations: We demonstrated the impact of learning imposing state representation for an agent with hicrarchical state representations. We now analyze how much of the success in exploration is due to the function approximator learning observational invariances as described in Section 5.1 In Figure (white), we fix the color of objects in the environment to only one color and compare our method to NovelD (Zhang et al., (021),, since it able to solve all MiniGrid environments. We see that "KeyCoridorS4R3" and "KeyCoridooSSR3" our method is more sample efficient than NovelD. Only in the "Key "Orr the large state space reduces performance (see Figure (pink left)). In general, we see

---

Published in Transactions on Machine Learning Research (08/2023)
that when the environment is observationally less complex (e.g by removing colors (see Figure 6 (pink right)), the cyclophobic agent is more sample efficient. than NovelD. However, soon as observational complexity increases NovelD takes the upper hand.
KCG:RR)10oooor
XCE4RD-1Color
AC9383-1000J0
XC3683 10blor
Overall-1Oolor
Color Ablation
Sycrinsis Ruvard
08
04
02
0.00
5.00
15:000
10.00
@ycloghoble;(burr)
WovelD
Nunber
(Millions)
complexity
Figure 6: Observational complexity ablation study (reducing colors): The cyclophobic agent can gather rewards successfully in large "KeyCorridor" environments when reducing colors, showing that the exploration mechanism is very strong. Generally, the more distinct i.e. complex the observations in the environment are, the more the learned invariances from the neural network matter.
Overall, we observe that exploration success is not necessarily due to the intrinsic reward itself, but can also largely be attributed to the learned representations. Thus, when complexity in the obscrvations increases, better performance in neural networks can be attributed to the learned invariances reducing observations complexity and not necessarily to a more efficient exploration strategy. This can be seen in the tabular cyclophobic agent as well, since the hicrarchical state representations are crucial solving the environments.
Spo 1loello-pee gooedy
Niezarchical
Counts
optizinit
Cyclophobie
Riezarchical Cyclophobic
40
50
50
30
30
50
20
20
20
20
20
Figure 7: Exploration eehaviour(visitatiie counts for "DoorKey-16x16") The cyclophobic Q- function explores the enviromment more efficiently than the optmistic initialization, count and ppsilon-greedy based counterparts. We record visitation counts for several variations of intrinsic reward and hierarchical state representations. Hierarchical state representations together with the cyclophobic intrinsic reward are the most efficient.
Exploration behavior: To show the effectiveness of the cyclophobic intrinsic reward and the hierarchical state representations, perform an ablation study. Figure 7 shows state counts heat map after 10,000 steps of training. We distinguish four cases: (i) epsilon-greedy. Plain epsilon greedy exploration fails to find the goal in the bottom right. (ii) hicrarchical & counts: We replace the cyclophobic intrinsic reward in equation (3) with a count-based intrinsic reward similar to Strehl & Littman (2008) defined by -o for view Vg. This improves the results but still fails. (iii) hierarchical
optimistic initialization: We use optimistic initialization let the agent try possible actions. We initialize the q-table with a value of two. Optimistic initialization manages enter the second room but just fails getting a reward within 10,000 steps. (iv) cyclophobic: Having eyclophobie intrinsie reward calculated only on the largest view finds the goal. (v) cyclophobic & hierarchical: The combination of hierarchical views and cyclophobic intrinsic rewards (as explained in Sec. 2.3) explores even more efficiently as can be seen in the left room where fewer steps are needed to leave it.
4 Related Work
Breadth-first-eearch vs depth-first-scard exploration: The way different exploration methods explore the state-action space important aspect of designing exploration methods. We characterize this by
10

---

Published in Transactions on Machine Learning Research (08/2023)
determining how an exploration method explores on the MDP-level. That is, the way the next action is chosen and the visited states-action pairs that result from the instrinsic reward. With count-based exploration (Ostrovski et al.) 2017 [ellemare et al. 2016) where instrinsic reward are usually inverse visitation counts N(of))) 2, the more a state is visited the less reward it will receive. In the short term, the agent will choose the same stale-action pair on its next visit (since has been given an intrinsic reward for being seen), until a random state-action pair is chosen. While this encourages the agent to revisit previously seen states, this also leads a depth first approach to exploring the MDP and other action are only considered after randomly being chosen by e-greedy. Another way to explore the environment is by exploiting prioproceptive information in the representations. Methods that use change based counts (Parisi et al. 2021 Zhang et al., 2021) or prediction error (Raileamu & Rocktäschel 2020; Pathak et al.) 2017: Burda et al. 2018 Henadf et al. 2022 as intrinsic reward give the highest intrinsic rewards to observations that are novel and have nol been seen before. In this case, the resulting exploration heuristic is based on pursuing the most novel state-action pairs. This may also be problematic when the stochasticity in the obscrvations is not necessarily aligned with the lask at hand. Overall, this also equales to a seethehfrst-searchh on the MDP-level, since the agent will be enticed to pursue the most novel transition instead of exploring other local options.
In contrast, optimistic initialization (Machado et al. 2014 Choshen et al 2018 systematically forces exploration on state-action pairs that have not been tried yet by the agent. The idea of optimistic initialization is to initialize the value function by a value larger than the expected reward. As the agent performs updates on the value function it will be forced to choose the next unexplored action since the falue-function update for other state-action pairs will have decreased their value. Methods like Never Give Up (NGU) (Puigdomênech Badia et al. 2020) try to combine both depth-first-search and bread-first-searchh NGU is composed of two networks where network will look for novel state transitions and another network trics to give an intrinsic reward when a similar state is visited again to encourage revisiting of states by doing a nearest-neighbor search. While NGU's focus is more based on mitigating the lack of breadth- wistttt-iis--epllrattio in prediction error based methods, cyclophobic reinforcement learning can be seen as an extension of optmistic initialization where we incorporate more depth-first-sean Other methods such as RAM (Seurin el al. 2021), also attempt. this by defining an instrinsic reward based on the saliency of actions in different states.
into optimistic initialization with the hierarchical state representation
Loop closure, generalization and transfer lcarning: Mirowski et al. (2016) define loop closure as an auxiliary loss for exploration in 3D mazes in addition to a depth measure. The authors detect loop closure by checking whether the agent has been near a previously visited position. To get position information the authors integrate velocity information over time. Furthermore, NovelD (Zhang et al., 2021) can also be seen as indirectly detecting loops as it part of its intrinsic reward is based on only rewarding states when they have not been visited before. Learning representations of the environment that are reusable and can be transferred has been explored previously. Learning successor representations (Barreto et al., 2016) requires learning local enviromment dynamics that can be reused when the environment, i.e. the original distribution, is changed. (Schaul et al.] 2015) use Singular Value Decomposition on the learned action-valle obtain a canonical representation of the environment which can be transferred to other situations. More recently, Parisi et al. (2021) learn an exploratory policy which is then combined with a task specific policy at transfer time. Our method likewise contains a lask-agnostic component given by the hierarchical state representations and a taek-specific component given by the cyclophobic intrinsic reward.
function to
5 Discussion
5.1 Limitations
In some environments with big number of different objects our method struggles to converge. The labular agent does not have the observational invariances that methods based on function approximation learn and exploit (e.g. with CNNs). For instance, for these environments learned invariances allow them to handle differently colored objects. While the tabular agent is able to avoid redundancy through the cyclophobic intrinsic reward and generalize this to other parts of the environment through the hicrarchical state representations, it does not learn the kind of observational invariances neural networks do, which
11

---

Published in Transactions on Machine Learning Research (08/2023)
are sometimes necessary. However, note that we can show that reducing the number of colors for the "KeyCorridor" environment improves our performance dramatically (see Figure 6 Also, preliminary results show a cyclophobic PPO agent (see Appendix A.1) solving "KeyCorridor", further supporting our theory. We explore this in our ablation study. An additional limitation that results from our tabular approach is that the entire observat ion history Hall has to be recorded. This however can be mitigated by using an unweighted sum of the q-values for all views as we show in the ablation study.
5.2 Contribution to existing literature
At a first glance, cyclophobic reinforcement learning can be seen another count-based method where equal states are counted as cycles. Then instead of giving an intrinsic reward which is the inverse of visitation counts, the intrinsic reward is a fixed penalty given everytime a cycle is encountered i.e. a state is counted. As explained in Section | the cycle penalty encourages an exploration behaviour that explores all actions within a state first instcad of pursuing the least visited, i.c., most novel states. This is inherently different from other count-based approaches. In this sense, the cyclophobic intrinsic reward behaves like optimistic initialization where the focus of exploration is placed the actions instead of the states. Moreover, the hierarchical state representations contrast the breadth-first exploration by learning multiple value functions which are expressive due to the different contents in the hierarchical views. Only few other works such as NGU have followed this approach of balancing breadth-first. and depth-first. exploration as described in Section 4
5.3 Extension to high-dimensional state spaces
So far we have tested cyclophobic reinforcement learning on the MiniGrid and MiniHack environments. While the state-action space of these environments is combinatorially complex to solve from exploration standpoint, the observations are simple compared to other environments such as Atari (Bellemare et al. 2012) or Habitat (Savva et al. 2019) where the exploration task may not be as complex, but the observations are Since cyclophobic reinforcement learning is a count-based method, we propose to exlend cyclophobic reinforcemnett learning to high dimensional observations by using density estimation techniques as in Ostrovski et al.
noisy and high-dimensionn
(2017); Bellemare et al. (2016). For the hierarchical state representations a PixeICNN (van den Oord et al.
2016 or VQ-VAE (van den Oord et al. 2017) could be used to estimate the density of the observations. With smaller views we expect these densities to get easier to estimate they contain less observational detail. For the cyclophobic penalty, pseudo count could be introduced as in (2016). Another approach would be to define an embedding network 2020 and scarching for nearest neighbors in the episodic history to detect cycles. Note that in NGU's case the embedding network used to revisit states while in our case it.
Ostrovski et al. (2017); Bellemare et al.
as in NGU (Puigdomènech Badia et al.
would be used to detect cycles in order discourage visiting these states. Overall, we leave the extension high-dimensional state spaces for future work.
5.4 Conclusion
Avoiding cycles allows the agent to quickly and systematically discard uninteresting state-action pairs which are repeated often. This makes our cyclophobic intrinsic reward a good inductive bias towards novelty that simultancously encourages systematic exploration. The ablation studies show that the cyclophobic intrinsic reward just for single view is already powerful enough to solve complex environments. Adding hierarchical state representations leads to even better performance, can be seen in the MiniGrid experiments. Moreover, the experiments in MiniGrid confirm the transferability of the learned bias to new environments. Here, the hicrarchical state representations are crucial since we detect cycles in smaller views that can be generalized to larger ones. In addition, the policy is task-agnostic since the cropped views can be easily transferred to other environments. Due to the tabular approach, environments with higher observational complexity lead to convergence problems with our method. Neural networks, learn invariances that reduce the complexity of the state space. To address the convergence problems, future work will therefore focus on incorporating cyclophobie reinforcement learning into neural network based architecture.
12

---

Published in Transactions on Machine Learning Research (08/2023)
References
André Barreto, Will Dabney, Rémi Munos, Jonathan J. Hunt, Tom Schaul, Hado van Hasselt, and David Silver. Successor Features for Transfer in Reinforcement Learning. arXiv e-prints, art. arXiv:1606.0531,, June 2016.
Mare G. Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The Arcade Learning Environment: An Evaluation Platform for General Agents. ar e-prints, art. arXiv:1207.4708, July 2012. doi: 10.48550/ 1448550/aXXiv.111.
Mare G. Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying Count-Based Exploration and Intrinsic Motivation. arXiv e-prints, art. arXiv:1606.01 June 2016.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by Random Network Distillation. arXiv e-prints, art. arXiv:1810.1294. October 2018.
Maxime Boissei, Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym.
2018.
Leshem Choshen, Lior Fox, and Yonatan Loewenstein. DORA The Explorer: Directed Outreaching Rein- forcement Action-Selection. arXiv e-prints, art arXiv:1804.04012, April 2018.
Lasse Espcholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, Shane Legg, and Koray Kavukcuoglu. IMPALA: Scalable Distribuled Deep-RL with Importance Weighted Learner Architectures. arXiv e-prints, art. arXiv:1802.01561, February 2018.
Klaus Greff, Sjoerd van Steenkiste, and Jürgen Schmidhuber. On the Binding Problem in Artificial Neural Networks. arXiv e-prints, art. arXiv:2012.05208, December 2020.
Mikael Henaff, Roberta Raileanu, Minqi Jiang, and Tim Rocktäschel. Exploration via Elliptical Episodic Bonuses. arXiv e-prints, art. arXiv:2210.05805, October 2022. doi:
Heinrich Küttler, Nantas Nardelli, Alexander H. Miller, Roberta Raileamu, Marco Selvatici, Edward Grefen- stette, and Tim Rocktäschel. The NetHack Learning Environment. arXiv e-prints, art. arXiv:2006.13760, June 2020.
Marlos C. Machado, Sriram Srinivasan, and Michael Bowling. Domain-Indopendent Optimistic Initialization for Reinforcement Learning. arXiv e-prints, art. arXiv:1410.4604, October 2014.
Piotr Mirowski, Razvan Pascanu, Fabio Viola, Hubert Soyer, Andrew J. Ballard, Andrea Banino, Misha Denil, Ross Goroshin, Laurent Sifre, Koray Kavukcuoglu, Dharshan Kumaran, and Raia Hadsell. Learning to Navigate in Complex Environments. arXiv e-prints, art. X61: 10111....000 1.03673, November 2016.
Georg Ostrovski, Mare G. Bellemare, Aaron van den Oord, and Remi Munos. Count-Based Exploration with
Neural Density Models. arXie e-prints, art. arXiv:1703.01310, March 2017.
Simone Parisi, Victoria Dean, Deepak Pathak, and Abhinav Gupta. Interesting Object, Curious Agent: Learning Task-Agnostic Exploration. arxiv e-prints, art arXiv:2111.13119, November 2021.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity-driven Exploration by Self-supervised Prediction. arXiv e-prints, art. arXiv:1705.05363, May 2017.
Adrià Puigdomenech Badia, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Ticleman, Martín Arjovsky, Alexander Pritzel, Andew Bolt, and Charles Blundel.. Never Give Up: Learning Directed Exploration Strategies. arxiv e-prints, art. arXiv:2002.06038, February 2020. doi:
10.48550/ air. www.:xivv.000.0000 2002.0608.
Roberta Raileanu and Tim Rocktäschel. RIDE: Rewarding Impact- Driven Exploration for Procedurally- Generated Environments. Xie e-prints, art arXiv:2002.1222 12292, February 2020.
13

---

Published in Transactions on Machine Learning Research (08/2023)
Mikayel Samvelyan, Robert Kirk, Vitaly Kurin, Jack Parker-Holder, Minqi Jiang, Eric Hambro, Fabio Petroni, Heinrich Küttler, Edward Grefenstette, and Tim Rocktäschel. MiniHack the Planet: A Sandbox for Open-Ended Reinforcement Learning Research. arXie e-prints, art. arXiv:2109.3202, September 2021.
Mikayel Samvelyan, Robert Kirk, Vitaly Kurin, Jack Parker-Holder, Minqi Jiang, Eric Hambro, Fabio Petroni, Heinrich Kuttler, Edward Grefenstette, and Tim Rocktäschel. Minihack the planet: A sandbox for open-ended reinforcement learning research. In Thirly-fith Conference Neural Information Processing Systems Datasets and Benchmarks Track (Round 1), 2021. URL https://openreviie wewparrrviee.nne/ooruueee net/formniid SkFwlyefRMJ
Manolis Savva, Abhishek Kadian, Oleksandr Maksymets, Yili Zhao, Erik Wijmans, Bhavana Jain, Julian Straub, Jia Liu, Vladlen Koltun, Jitendra Malik, Devi Parikh, and Dhruv Batra. Habitat: A Platform for Embodied AI Research. arXiv e-prints, art. arXiv:1904.01001, April 2019. doi:
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1312 1320, Lille, France, 07 09 Jul 2015. PMLR. URL httpps://proceedding/ mlr. atcess/v3//schaulle html
Mathieu Seurin, Florian Strub, Philippe Preux, and Olivier Pietquin. Don't Do What Doesn't Matter: Intrinsic Motivation with Action Usefulness. arXiv e-prints, art. arXiv:2105.0999,, May 2021.
Alexander L. Strehl and Michael L. Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciemces, 74(8) 1331, 2008. ISSN 0022-0000. doi: 200..0007..88000 1000
httpp::/www..ccaccccceee.e.cooes pa1/80002200008000755 Learning Theory 2005.
http:://too..rr//111011/1.1
Aaron van den Oord, Nal Kalchbrenner, Lasse Espeholt, koray kavukcuoglu, Oriol Vinyals, and Alex Graves. Conditional image generation with pixelenn decoders. D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29, Cur- Associates, Inc., 2016. URL https://prooeeddgg..eurrr wtw.errpps.cpppperrrriee http://ppppp..teee/pppp////////p 0330144reeffaacc4441110777726660
ppff
Aaron van den Oord, Oriol Vinyals, and koray kavukcuoglu. Neural discrete representation learn- ing. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https://proceeddiin www.:eeedddnnnn................. http://wwww...pppppppoaaaaap//pp fitps///////ppp/////////////// 7a98af
Sjoerd van Steenkiste, Klaus Greff, and Jürgen Schmidhuber. A Perspective on Objects and Systematic Generalization in Hosel-Based RI. ar e-prints, art. arXiv:1906.01035, June 2019.
Tianjun Zhang, Huazhe Xu, Xiaolong Wang, Yi Wu, Kurt Keutzer, Joseph E. Gonzalez, and Yuandong Tian. Noveld: simple yet effective exploration criterion. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vanghan (eds.), Advances Neural Information Processing Systems, 2021. URL
14

---

Published in Transactions on Machine Learning Research (08/2023)
A Further Ablation Studies
For all plots in the ablation studies we use the same setup as in the main experiments. We refer to section for this.
A.1
Preliminary results with PPO
id-Ddrid-Dn lock--
Mintärid-boordey--ttt-o
KiniGe Eo-roo Bloseeed--ayttrrrdeessssaa 1dor5333-v0
1.0
Extrinaic Revara
0.6
0.0
8.00
6.00
Number of Steps (MALlions)
cyelophobicc-PP0 gyclnghhbic-7nnbalrrriorrrr
RTDE
Nove1D
C-RR7
Figure Using PPO together with only the cyclophobic intrinsic reward also converges far quicker than C-BET. Moreover, we are able converge KeyCorridor33R3 confirming our theory in Section 5.1
We train a PPO agent using only the cyclophobic intrinsic reward. Figure g shows that for the given environments the PPO agent also explores more efficiently than C-BET. Furthermore, our thoory about observation complexity from 5.1 supported the PPO agent is able to solve the "KeyCorridor" environment. Note that these are preliminary results. In future work seek to implement the hierarchical state representations for the neural agent.
B Environment Details
B.1 MiniGrid Experiments
Unlock
DoorKey
KeyCoridor
UnlockPickup
BlackedUUnlockPicsup
MultiRoom-Ne Ni--oomm-----yy
M
ObstructedMMaze-100
ObstructedMasz-222
ObstructedMaaze-DDhhh
Figure 9: An overview of the MiniGrid environments used in this paper.
We test on some of the same enviromments Parisi et al. 2021 In the following we describe the environments as Parisi et al. (2021) and add our own comments where relevant.
Unlock: pick up the key and unlock the door. (288 steps per episode)
DoorKey-8x8: pick up the key, unlock the door, and go to green goal (640 steps per episode)
KeyCoriddo pick up the key, unlock the door, and pick up the ball (only the door before the ball is locked) (270 steps per episode).
15

---

Published in Transactions on Machine Learning Research (08/2023)
UnlockPickup: pick up the key, unlock the door, and open the box (288 steps per episode).
BlockeuUnnoockiccuupps pick up the ball in front of the door, drop it somewhere else, pick up the key, unlock the door, and open the box (576 steps per episode).
ObstructedMaze- 1D1h: open the box to reveal the key, pick up, unlock the door, and pick up the ball (288 steps per episode).
ObstructedMazze-DDlh: same as above, but with two doors to unlock (576 steps per episode).
ObstruuteedMaxe--DDllbb: same as above, but with two balls in front of the doors (like in Blocke- (UnblockPickup) (576 sleps per episode).
navigate through six rooms maximum size ten and go to the green goal (all doors are already unlocked) (120 steps per episode).
MultiRoom--N6:
MultiRoom-N12-910: navigate through twelve rooms maximum size ten and go to the green goal (all doors are already unlocked) (120 steps per episode).
B.2 MiniHack Experiments
Room-Random
Room-Dark
KayRoom-S5
River
Easy
Pray
LockedDoor
Figure 10: An overview the Minihack environments tested this paper. The top row shows the Navigation tasks, while the bottom row shows the Skill tasks.
We perform experiments inspired by the baselines from Sanvellan et al. 2021 Here, Samvelyan et al. 2021 define a set of navigation and skill acquisition tasks. The navigation tasks range from requiring the agent to navigate an empty room or maze, up to navigating environments with monsters and hazards. The skill acquisition tasks require the agent to perform a certain set of skills to be able to solve the environments.
B.2.1 Navigation tasks
In the following we describe the environments used from the navigation task.
150m-Raadom-15511:: This task in single square room, where the goal to reach the staircase down. In the random version of this task, the start and goal positions randomized.
Room-Darkk15x11: Same as Room-Randone but the agent only sees parts of the environment it has already discovered.
16

---

Published in Transactions on Machine Learning Research (08/2023)
KeyRoom-S5:
These tasks require agent to pick up key, navigate to door, and use the key to unlock the door, reaching the staircase down within the locked room. The locations of the door, key and starting position are randomized.
River:
The river environment requires the agent to cross river using boulders. When pushed into the water, they create a dry land to walk on, allowing the agent to cross it.
B.2.2 Skill tasks
The nature of commands Neck requires the agent to perform sequence of actions so that the initial action, which is meant for interaction with an object, has an effect. The exact sequence of subsequent can be inferred by the in-game message bar prompts. Overall, in each of the following tasks the agent has to perform sequence of actions that allow the agent to perform the required skill.
Eat: The agent has to navigate and eat an apple. Doing so requires a sequence of actions and confirming a prompt to eat the appe.
Pray: The agent has to pray on an altar. This is more complex than eating an apple as praying
requires the agent to confirm more prompts.
Wear: The agent has to wear armor. This more difficult task than the previous tasks.
LockedDoor-Fixdd: agent has to kick a locked door.
Wand of Death-Fasy: The agent starts with a wand of deatch in its inventory and has zap it. towards a sleeping monster. That is, the agent needs equip the wand of death walk to the monster and zap it.
In all of these enviromments the positions of the agent and of the object that has to be interacted with are randomised. Furthermore, the complexity is also increased by the confirmation prompts the agent has to answer in order to perform a certain action.
C Experimental Details
C.1 Hyperparameters
Common hyperparameters: In the following we present table with all hyperparametens used for training the environments. In general, our method has very few hyperparameters. In this case the only really tunable hyperparameters are the step size n,, the random action selection cocfficient for epsilon-greedy exploration and the discount 7
?
7
Num. views
0.2
0.99
5
In our case we determined experimentally that views is a good number of views for training an agent.
Epsilon-greedy parameter e: While learning with the cyclophobic intrinsic reward we still perform random action from time time by having an epsilon-greody action selection. That is, the agent samples a value n from a uniform distribution and selects a random action if this < e. These are the settings for for the respective environments:
17

---

Published in Transactions on Machine Learning Research (08/2023)
Environments
C
Unlock
0.1
DoorKey
0.1
KeyCorridor
0.1
UnlockPickup
0.3
MultiRoom--6
0.1
Multilooom-N12--100
0.1
BlockodUUnlockPickupp
0.3
ObstructeddMave-11110
0.3
ObstructeddMaze-2DIII
0.1
Obstrricteddazzz-IIDtth
0.3
All MiniHack
0.3
Intrinsic reward tradeoff pi The intrinsic reward tradcoff p has the effect that the extrinsic reward gets propagated more when the agent encounters it, which is necessary for more complex environments. p is hyperparancter that can be defined for each environment for best performance.
Environments
Unlock
1.0
DoorKey
1.0
KeyCorridor
1.0
UnlockPickup
2.0
MultiRoomm-N6
2.0
MultiRoom-NI2-S10
2.0
BlockedUnloockPiekup
5.0
ObstractedMMeze-IDDi
2.0
ObstructeddMaze-2JJl
5.0
ObstracteddMzze22Dlhh
5.0
River
5.0
WOD-Fasy
5.0
Eat
2.0
Pray
2.0
Rest of MiniHack
2.0
C.2 PPO Hyperparameters
GAE-lambda
0.95
?
0.99
Batch size
256
Learning rate
0.001
Entropy coefficient
0.01
Value loss coefficient
0.5
Max Grad Normt
0.5
Clipping-e
0.2
RMSProp-c
1e-8
RMSProp-a
0.99
C.3
Plot smoothing
For all 3 runs we show the mcan reward and standard deviation smoothed over a sliding window. For our and Sannellan al. [2021] 's experiments we use sliding window of 50000 steps. For the experiments Parisi et al. (2021) use sliding window of 96000 steps as per their experimental setup. The shaded areas are the standard deviation of the mean for 3 runs.
18


Reviews:
[{"review_id": "o8glZaf9vu", "reviewer": "Reviewer_oVTh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n- Investigates a straightforward approach to intrinsic reward learning in settings where multiple observational \"views\" can be defined.\n- The experiments give a decent amount of evidence about the approach's relative performance\n\n## Weaknesses\n### Writing ambiguity\n- P1 \"intrinsic rewards based on curiosity ... paradoxically being less sample efficient\". Please add citations.\n- P1 The definition of a \"view\" here is ambiguous, which makes the description of applying the intrinsic reward to cropped views ambiguous. Please make this precise.\n- Eq1. doesn't really convey much (it just says $r_{cycle}(s,a) = -1$). Perhaps it can be revised to connect to the decision criterion for when it is applied. I think this description could be made stronger if the intrinsic reward was defined simply to be $-l$, and $l=N(s)$ was defined in terms of in-episode visitation count.\n- \"In general, larger views in the hierarchy will have bigger entries in $\\alpha(s_t)$\" This didn't make sense -- $\\alpha(s_t)$ is defined in Eq. 11 as the softmax of the component $\\alpha$ across all views, so there isn't a separate $\\alpha(s_t)$ (no subscript) for the larger views than for the smaller views. \n- P5: \"$\\alpha(s_t)$ gives more weight to the larger views than the smaller ones. However, the converse is true for the cyclophobic intrinsic reward since in the smaller views the cyclophobic penalty is propagated far more often than in the larger views.\" This statement didn't make sense to me. Part of this is because it is unclear what it means for a cyclophobic penalty to \"propagate\", as mentioned a few times. The paper would be improved with a precise definition of propagation.\n- In a few places (P1, P9), the paper references \"learned representations\", yet there is no analysis of any learned representations, only analysis of the manually defined views of the state. I'd like to see references to learned representations removed, as they don't play a direct role in the experiments. \n- I think the limitations section (3.3) should mention the fact that the entire observation history is recorded (Eq. 6) as part of the approach.\n\n### Experimental weaknesses\n- The paper would be improved if it included empirical support for the designed state encodings (the chosen five croppings of the original full view). Without further analysis, we can't draw strong conclusions about the effect of the view design or make clear recommendations about how to design them.\n- The paper would be improved if it included empirical support for the Q-function mixing coefficient design. For example, run experiments in which the Q-value function weights are instead always 1, would give us more information about the importance of the weights.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes an exploration-incentivizing intrinsic reward that penalizes revisiting, within an episode, particular types of observations defined to be increasingly smaller subsets of an original observation. The motivation is to encourage within episode exploration at different scales -- by \"cropping\" out large parts of the original observation, the resulting observations are more likely to be equivalent. The approach creates a separate reward function and Q function for each of these views, and linearly combines the resulting Q function using weights that assign higher weight to the Q functions of less common observations. Experiments in the MiniGrid and MiniHack environments compare the approach to other approaches and find that the proposed approach is competitive with them. The paper also presents experiments in which the approach's performance improves when a reward-independent aspect of the observation is heuristically modified -- by replacing the color of objects with a single common color.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the writing and experimental weaknesses. I'm particularly concerned about the experimental weaknesses, as without broader analysis, I don't think readers can draw strong conclusions about this type of approach.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "LQNH4FaVOz", "reviewer": "Reviewer_JPfv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The general notion of avoiding loops in trajectories has certainly been in the literature for a while, though the particular form as proposed in this paper has not been thoroughly discussed. In this sense, the paper has certain level of novelty.\n\nMajor weaknesses of the paper include: it is not clear how generally applicable such a notion of cyclophobic reward is. The definition of the reward function requires checking if a certain state (view) has been visited twice, which seems intractable in general environment. It is not clear how such a method extends to non-grid world environments. The demonstration of empirical result is not convincing enough to showcase the general usefulness of the method. Discussions of certain baselines and prior work are missing.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes cyclophobic reward, a reward function that penalizes agents taking loops in its trajectories. Cyclophobic reward is used for encouraging exploratory behavior of RL agents and can be combined with function approximations as demonstrated in the paper.  The paper showcases the practical usefulness of such an exploration method compared to other baselines, using grid world environments.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Changes should be made based on the detailed comments below.\n\n### Definition of cyclophobic reward\n\nThe definition in Eqn 1 requires checking whether the same state is visited multiple times. This is difficult in general RL envs when the state space is high-d and real valued, and it is impossible to check for exact visitation. How do the authors propose we handle situations like this? A natural idea would be to combine with approximate counts methods such as discussed in [1,2]\n\n[1] Ostrovski et al, 2017, Count-Based Exploration with Neural Density Models\n\n[2] Bellemare et al, 2016, Unifying Count-Based Exploration and Intrinsic Motivation\n\n### Notation\n\nIt is confusing to write $r_\\text{cycle}(s,a)$ as if the reward function is just a function of $(s,a)$. The reward function is obviously a function of the entire history as we need to check whether the state is visited or not, hence requiring the reward to depend on the whole history in the past.\n\n### POMDP\n\nIn the POMDP case, the paper switches to a definition of the reward function based on how many times a certain view has been encountered (Eqn 7-8). This faces the similar intractable problem as defining the reward function since it is in general not possible to accurately count $N_i$ the number of times view $V_i$ has been seen. Combination with approximate methods [1,2] is necessary. \n\nAddressing the above issue is very important to scale such methods to general envs. Unfortunately in this paper, very little has been discussed in this regard. This hints at a major weakness of the paper.\n\n### Related work\n\nDiscussion on related work is missing. I like the fact that the authors have pointed out BFS vs. DFS style exploration in general RL literature, hence motivating this particular work. I think what's missing is to connect what's proposed here more tightly with BFS vs. DFS. Since we are avoiding loops, it feels more like DFS. However, what is the argument to make DFS or BFS better than the other method?\n\nRelated work in the space has discussed such points [3,4].\n\n[3] Badia et al, 2020, Never Give Up: Learning Directed Exploration Strategies\n\n[4] Guo et al, 2022, BYOL-Explore: Exploration by Bootstrapped Prediction\n\n### Typos\n\nMany obvious typos in the paper. For example, in the abstract \"we propose a new intrinsic reward that is cyclophobic, i.e. it does not reward novelty\".", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "RbtMdpzeyz", "reviewer": "Reviewer_c2LQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: the idea of reducing a fully observable state to a partially observable one is interesting (although not really novel, as for example used in \"Self-Attentional Credit Assignment for Transfer in Reinforcement Learning\").\n\nWeaknesses: the contribution arem in my opinion limited:\n- the cyclophobic reward is actually extremely close to a count-based reward. It is limited to tabular setup and the authors do not hint on how to make it usable in a non-tabular setting. The count-based baseline is not even present in the experiments.\n- the baselines (ICM, RND) were specifically designed to work in the non-tabular setting and I this is clearly an unfair comparison.\n- the \"main contribution\" is the hierarchical view but this contribution is even more limited as it is not clear at all how it will transfer to any en environment that is not agent-centric navigation.\n- learning separate Q-function will also poorly trasnfer to higher dimensional environements.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper tackles the exploration problem in reinforcement learning.\nBuilding upon the literature of intrinsic motivation, they propose an intrinsic reward called \"cyclophobic\" which is -1 if (s,a) has already been visited.\nWhat's more, they propose to actually use several reward function, r(V_i(s), a), with V_i a \"cropped\" view of the state (a partial observation). Their notion of \"cycle\" is thus more frequent for highly cropped observation. \nThey then propose to learn one Q-function per reward (per view), and to finally play the greedy policy with respect to a weighted sum of these Q-functions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "\n\nWhat is the rationale for learning separate Q-functions? Why not mixing rewards rather than Q-functions?\n\nPlease include tabular count-based methods in your baselines (you should also include it in an ablation where you run count+hierarchical views).\nPlease include a discussion on how you expect to transfer the hierarchical views to other environments. \nPlease include a discussion on how you expect to transfer the cyclophobic reward to other environments. Will it not reduce to RND or similar methods?\n\nIt would be good really valuable to have at least one non-tabular experiment.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: From my reading, this work introduces the cyclophobic reward and combines it with the hierarchical state representations to support transfer of learned invariances across domains.  Since the cyclophobic penalty would have different consequences at different observation scales, the the authors propose to learn Q-functions for each scale and combine them.  These two innovations are evaluated on sparse reward MiniGrid and MiniHack environments.  Via reasonable ablations, the authors characterize how much these innovations improve the rate of solving the task. 

Reviewer oVTh was satisfied by the author response and updates to the paper.  As noted above, Reviewer c2LQ was not satisfied with the revisions, in particular stating that "scope of the paper is extremely limited" and also raising concerns about the degree of novelty.  Reviewer JPfv similarly complained that the "paper itself leverages wisdom from prior literature, the very idea of avoiding loops in agent's trajectories is not extremely novel."  They also remarked that "Despite the authors' response which addresses some technical concerns, the paper still does not provide enough empirical evidence that showcases the usefulness of such an approach in practice (e.g. large-scale high-dimensional environment). An improvement direction for the paper would be to provide more evidence in this regard."

Ultimately, 2 of the 3 reviewers took issue with scope and originality of the paper.  However the TMLR guidelines state that a paper should be published "even if the contribution or significance of the work is modest", while a paper should not be published if they "incorrectly claim novelty over existing published work" or "merely re-implement an idea that has already been reproduced before".  

In my assessment, while this work is related to other work in the count-based exploration literature, it appears sufficiently distinct from previous published work (so far as I am aware) to avoid disqualification as a reimplementation.  Notwithstanding some of the larger concerns by two of the reviewers about broader utility of the innovations proposed, I believe this work passes the bar for acceptance, with the larger points beyond the scope of what the authors would be able to pursue in this paper.  I think section "5.2 Extension to high-dimensional state space" reasonably discusses some of the limitations raised in the reviews and provides a plan for future work.

I would recommend as a minor change to better satisfy the reviewers who raised concerns about novelty that the authors more explicitly clarify how this cyclophobic reward approach is distinct from other count-based approaches.  Basically, the authors should be able to assert that their approach does not reduce to an existing approach via some equivalence, to the best of their knowledge, and perhaps they can provide an intuition for what makes it distinct/novel.

Nit: "ICM (?)" -- missing ref
Decision: Accept (poster)