Clustered Reinforcement Learning
Authors: Xiao Ma
Shen-Yi Zhao
Zhao-Heng Yin
Wu-Jun Li
Venue:  (2020)

Abstract: Exploration strategy design is one of the challenging problems in reinforcement learning~(RL), especially when the environment contains a large state space or sparse rewards. During exploration, the agent tries to discover novel areas or high reward~(quality) areas. In most existing methods, the novelty and quality in the neighboring area of the current state are not well utilized to guide the exploration of the agent. To tackle this problem, we propose a novel RL framework, called \underline{c}lustered \underline{r}einforcement \underline{l}earning~(CRL), for efficient exploration in RL. CRL adopts clustering to divide the collected states into several clusters, based on which a bonus reward reflecting both novelty and quality in the neighboring area~(cluster) of the current state is given to the agent. Experiments on several continuous control tasks and several Atari-2600 games show that CRL can outperform other state-of-the-art methods to achieve the best performance in most cases.

Under review as a conference paper at ICLR 2020
CLUSTERED REINFORCEMENT LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Exploration strategy design is one of the challenging problems reinforcement learning (RL., especially when the environment contains large state space sparse rewards. During exploration, the agent tries to discover novel areas or high reward (quality) areas. In most existing methods, the novelty and quality in the neighboring area of the current state are not well utilized to guide the explo- ration of the agent. To tackle this problem, we propose a novel RL framework, called clustered reinforcement learning (CRL), for efficient exploration in RL. CRL adopts clustering to divide the collected states into several clusters, based which a bonus reward reflecting both novelty and quality in the neighboring area (cluster) of the current state given to the agent. Experiments on several continuous control tasks and several Atari-2600 games show that CRL can out- perform other state-of-the-an methods to achieve the best performance in most cases.
INTRODUCTION
Reinforcement learning (RI.) (Sutton & Barto 1998) studies how an agent can maximize its cumu- lative reward in an unknown environment, by learning through exploration and exploitation. A key challenge in RL is to balance the relationship between exploration and exploitation. If the agent explores novel states excessively, it might never find rewards to guide the learning direction. Other- wise, if the agent exploits rewards too intensely, it might converge to suboptimal behaviors and have fewer opportunities discover more rewards from exploration.
Although reinforcement learning, especially deep RI. (DRI.), has recently attracted much attention and achieved significant performance in a variety of applications, such as game playing (Mnih al., 2015 Silver et al. 2016) and robot navigation (Zhang et al., (016]] exploration techniques in RI. are far from satisfactory in many cases. Exploration strategy design is still one of the challenging problems in RL, especially when the environment contains a large state space or sparse rewards. Hence, it has become a hot research topic to design exploration strategy, and many exploration methods have been proposed in recent years.
Some heuristic methods for exploration, such as e-greedy (Silver et al. 2016; Sutton Barto 1998). uniform sampling (Mnih al. 2015) and i.i. Gaussian noise (Lillicrap al., 2016 Schulman et al., 2015), try to directly obtain more different experiences during exploration. For hard applications games, these heuristic methods are insufficient enough and the agent needs exploration techniques that can incorporate meaningful information about the environment.
In recent years, some exploration strategies try discover novel state areas for exploring. The di- rect way to measure novelty is to count the visited experiences. In (Bellemare et al.) 2016 Ostrovski al. 2017). pseudo-counts are estimated from a density model. Hash-based method (Tang al., 2017 counts the hash codes of states. There also exist some work using the counts of state-action pairs to design their exploration techniques, such as explicit explore or exploit (F3) (Kearns & Singh 2002). R-Max Bratmann & Tennenholtz (2002), UCRL (Auer & Ortner 2006). UCAGG Orrt- ner 2013). Besides, the state novelty can also be measured by empowerment (Klyubin al. 2005). the agent's belief of environment dynamics (Houthooft et al. 22166), prediction error of the system dynamics model (Pathak et al. 2017] Stadie et al.] 2015). prediction by exemplar model (Fu et al, 2017). and the error of predicting features of states (Burda et al.) 2018). All the above methods perform exploration mainly based on the novelty of states without considering the quality of states. Furthermore, there some methods to estimate the quality of states. Kernel-based reinforcement

---

Under review as a conference paper at ICLR 2020
learning (Ormoneit & Sen. 2002 uses locally weighted averaging to estimate the quality (value) of states. UCRL (Auer & Ortner 2006) and UCAGG (Ortner 2013) compute average rewards for choosing optimistic values. The average reward can be regarded as estimation of the quality of states to guide the exploring direction, but there are no methods using the quality of states as an exploration technique. Furthermore, in most existing methods, the novelty and quality in the neighboring area of the current state are not well utilized to guide the exploration of the agent.
To tackle this problem, we propose novel RL framework, called clustered reinforcement learning (CRL), for efficient exploration in RL. The contributions of CRL are briefly outlined as follows:
CRL adopts clustering to divide the collected states into several clusters. The states from the same cluster have similar features. Hence, the clustered results CRL provide a pos- sibility to share meaningful information among different states from the same cluster.
CRL proposes a novel bonus reward, which reflects both novelty and quality in the neigh- boring area of the current state. Here, the neighboring area is defined by the states which share the same cluster with the current state. This bonus reward can guide the agent to perform efficient exploration, by seamlessly integrating novelty and quality of states.
Experiments on several continuous control tasks with sparse rewards and several hard ex- ploratory Atari-2600 games (Bellemare et al. 2013) show that CRL can outperform other state-of-the-ard methods to achieve the best performance in most cases. In particular, on several games known to hard for heuristic exploration strategies, CRL achieves signifi- cantly improvement over baselines.
2 RELATED WORK
Recently, there some exploration strategies used to discover novel state areas. The direct way to measure the novelty of states is to count the visited experiences, which has been applied in several methods. In the tabular setting and finite Markov decision processes (MDPs), the number of state- action pairs is finite which can be counted directly, such as model-basee jnterval estimation with exploratory bonus (MBIE-EB) (Strehl Littman 2008), explicit explore or exploit (E*) (Kearns & Singh/ 2002) and R-Max (Brafman & Tennenholtz] 2002). MBIE-EB adds the reciprocal of square root of counts of state-action pairs as the bonus reward to the augmented Bellman equation for exploring less visited ones with theoretical guarantee. E determines the action based on the counts of state-actions pairs. If the state has never been visited, the action is chosen randomly and the state has been visited for some times, the agent takes the action that has been tried the fewest times before. R-Max uses counts of states as a way to check for known states.
In the continuous and high- -ich-immnnsioall space, the number of states is too large to be counted di- rectly (Bellemare et al.) 2016]] Ostrovski et al.] 2017 Tang et al.) 2017 Abel et al. 2016). [Blleemare] density model estimate the state pseudo-count quan- tity, which is used to design the exploration bonus reward. TTng et al. (017) counts the number of states by using the hash function to encode states and then explores by using the reciprocal of visits as a form of reward bonus, which performs well on some hard exploration Atari-2600 games. Abel al. (2066) records the number of cluster center and action pairs and makes use of it to select an action from the Gibbs distribution. These count-based methods encourage the agent to explore by making use of the novelty of states and do not take quality into consideration.
al. (2016) Ostrovski et al. (201))
Furthermore, there are some methods to estimate the quality of states. Average reward, in kernel-based reinforcement learning (Ormoneit Sen, 2002), UCRL (Auer Ortner (006) and UCAGG (Ortner) 2013), can be regarded as the quality of states. Kernel-based reinforcement learning (Ormoneit & Sen 2002) is proposed to solve the stability problem of TD-leamning by us- ing locally weighted averaging to estimate the value of state. UCRL (Auer & Ortner 2006) and UCAGG (Ortner 2013) use average reward to choose optimistic values. Besides, the value of clus- ter space can also indicate the quality of states. Singh et al. (1994) uses the value of cluster space with Q-learning and TD( by soft state aggregation and provides convergence results. But these methods do not use the quality of states explore more areas.
2

---

Under review as a conference paper at ICLR 2020
To the best of our knowledge, the novelty and quality in the neighboring area of the current state have not been well utilized to guide the exploration of the agent in existing methods, especially in the high dimensional state space. This motivates the work of this paper.
NOTATION
In this paper, we adopt similar notations as those in (Tang et al. 2017). More specifically, we model the RL problem defined by tuple (S, (S, A, Po. T). Here, S E Id denotes the state space, A E R denotes the action space, P: Ax I denotes a transition probability distribution, A + R denotes a reward function, Po is an initial state distribution, 7 E (0, is discount factor, and T denotes the horizon time. this paper, we assume r 2 0. For cases with negative rewards. can transform them to cases without negative rewards. The goal of RL is maximize Ex,P 7 at) which is the total expected discounted reward over a policy π.
knite-horizon discounted Markov decision process (MDP), which can be
4 CLUSTERED REINFORCEMENT LEARNING
This section presents the details of proposed RL framework, called clustered reinforcement learning (CRL.). The key idea of CRL is to adopt clustering to divide the collected states into several clusters, and then design novel cluster-based bonus reward for exploration.
4.1 CLUSTERING
Intuitively, both novelty and quality are useful for exploration strategy design. the agent only cares about novelty, it might explore intensively in some unexplored areas without any reward. If the agent only cares about quality, might converge to suboptimal behaviors and have low opportunity to discover unexplored areas with higher rewards. Hence, it is better to integrate both novelty and quality into the same exploration strategy.
We find that clustering can provide the possibility to integrate both novelty and quality together. Intuitively, a cluster states can be treated as an area. The number of collected states in a cluster reflects the count (novelty) information of that area. The average reward of the collected states in a cluster reflects the quality of that area. Hence, based on the clustered results, we can design an exploration strategy considering both novelty and quality. Furthermore, the states from the same cluster have similar features, and hence the clustered results provide a possibility to share meaningful information among different states from the same cluster. The details of exploration strategy design based on clustering will be left to the following subsection. Here, we only describe the clustering algorithm.
In CRL, we perform clustering on states. Assume the number of clusters is K, and we have collected N state-action samples {(s;, a;, N with some policy. We need to cluster the collected states (s:) into K clusters by using some clustering algorithm C is the center of the i-th cluster. We can use any clustering algorithm in the CRL framework. Although more sophisticated clustering algorithms might be able to achieve better performance, in this paper we just choose k-means algorithm (Coates & Ng. 2012). K-means is one of the simplest clustering algorithms with wide applications. The detail of k-means is omitted here, and readers can find it in most machine learning textbooks.
C, where C {Ca J and
4.2 CLUSTERING-BASEE BONUS REWARD
As stated above, clustering can provide the possibility of integrating both novelty and quality to- gether for exploration. Here, we propose a novel clustering- based bonus reward, based on which many policy updating algorithms be adopted to get an exploration strategy considering both novelty and quality.
Given state 8;, it will be allocated the nearest cluster by the cluster assignment function (i(s) arg minl|a 8 - Cbll. Here, 1 & lo & K and ||s Cxll denotes the distance between and the k-th
3

---

Under review as a conference paper at ICLR 2020
cluster center Ck. The sum of rewards in the k-th cluster is denoted as Rg, which can be computed as follows:
RR E (((((( k),
(1)
where II()) is an indicator function. Rg is also called cluster reward of cluster this paper. The number of states in the k-th cluster is denoted as Nk. which can be computed as follows:
N& II(o(s)) = =k).
Intuitively, larger N& typically means that the area corresponding to cluster l has visits (ex- ploration), which implies the novelty of this area is lower. Hence, the bonus reward should be in- versely proportional to N2. The average reward of cluster k. denoted as N2" the quality of the corresponding area cluster k. Hence, the bonus reward should be proportional Rs. to No
Re can be used to represent
With the above intuition, we propose a clustering- bbased bonus reward + R to integrate both
novelty and quality of the neighboring area of the current state which is defined as follows:
max 17, Ra(ss)
b(s) B
No(e)
where A E IR+ is the bonus coefficient and 1) E R+ is the count (novelty) coefficient. Typically, is set to small number relative to a true reward
In general, long as there exist one or two states with positive rewards in cluster ((s), Re(e)) will larger than 17. Hence, if b(s) Note)" reward. Hence, when Rø(s) 0 which means rewards have been got for cluster ((s), the bonus reward should be determined by the count of the cluster. From Equation result smaller bonus reward b(s). This will guide the agent explore novel area corresponding to clusters with less visits (cxploration), which is reasonable. For two clusters with the same cluster reward, the cluster with smaller number of states (higher novelty) will be more likely to be explored, which is reasonable. For two clusters with the same number of states, the cluster with higher cluster reward (higher quality) will be more likely to be explored, which is also reasonable.
8n it is highly possible that all states in cluster d(s) have zero
larger Noçs) will
Hence, the clustering buased based bonus reward function defined in Equation 3) is intuitively reasonable, and it can seamlessly integrate both novelty and quality into the same bonus function. Finally, the agent will adopt {(si, di, r; + b update the policy (perform exploration). Many policy updating algorithms, such as trust region policy optimization (TRPO) (Schulman et 2015). can be adopted.
Algorithm Driiety presents the learning framework of CRL. We can see that CRL is actually a gen- eral framework, and can get different RL variants by taking different clustering algorithms and different policy updating algorithms. Please note that r; + b, is only used for training Algorithm [ But the performance evaluation (test) measured without b,, which can be directly compared with existing RL methods without extra bonus reward.
EXPERIMENTS
We use several continuous control tasks and several Atari-2600 games to evaluate CRL and base- lines. We want to investigate and answer the following research questions:
Is the count-based exploration sufficient to encourage the agent achieve the final goal of tasks?
Can CRL improve performance significantly across different tasks compared with other methods?
In experiments, the rewards are either zero or positive integers.
4

---

Under review as a conference paper at ICLR 2020
Algorithm Framework of Clustered Reinforcement Learning (CRL)
Initialize the number of clusters K, bonus coefficient B, count coefficient for iteration j = - do
Collect set of sate-action samples {(st, a4 (;) with policy Ty; Cluster the state samples with f S C, where {Ci) and f is some clustering
algoritiu;;
Compute the cluster assignment for each state ((s;) = arg min||s: C&ll, W: <i< k:
1<ke K;
Compute sum of rewards Rg using Equation T and the number of states N₂ using Equa-
tion 2 yk 1 & k & K;
Compute the bonus b(ss) using Equation 3
Update the policy xj using rewards (ri + b(s,) i=1 with some policy updating algorithm;
end for
(a) MountainCar
(b) CartpoleSwingup
Figure 1: Snapshots of two MuJoCo games.
5.1 EXPERIMENTAL SETUP
5.1.1 ENVIRONMENTS
MuJoCo. The rllab benchmark (Duan et al. 2016) consists of various continuous control tasks to test RL algorithms. We select MountainCar and CarnpoleSwingup compare our methods with other baselines. The experimental setups of MountainCar and CartPoleSwingup using sparse rewards can be found in Houthooff et al. (2016). In MountainCar, S S 3R3
R The agent receives a reward
of +1 when the car escapes the valley from the right side, otherwise the agent receives reward of CartpoleSwingup. S C R4, C RR. The agent receives reward pole angle is larger than 0.8, otherwise the agent receives zero return at other positions. Figure shows one snapshot for each task.
when the cosine of
Arcade Learning Environment. The Arcade Learning Environment (ALE) (Bellemare et al. 2013) a commonly used benchmark for RL algorithms because of its high-dimensional state space and wide variety of video games. We select subset of Atari game Freeway, Frostbite, Gravitar, Solaris and Venture. Figure shows a snapshot for each game. For example, in Freeway, the agent need to avoid the traffic, cross the road and get the reward. These games classified into hard exploration category, according to the taxonomy in (Bellemare et al. 2016).
5.1.2 BASELINES
CRL is a general framework which can adopt many different policy updating (optimization) al- gorithms get different variants. In this paper, only adopt trust region policy optimiza-
"The Montezuma game evaluated in Tang et al. 2017) is not adopted in this paper for evaluation, because this paper only uses raw pixels which are not enough for learning effective policy on Montezuma game for most methods including CRI and other haselines. We can use advanced feature to learn effective policy, but this is the focus of this paper.

---

Under review as a conference paper at ICLR 2020
0.5
CIS
(a) Freeway
(b) Frostbite
(c) Gravitar
(d) Solaris
(c) Venture
Figure 2: Snapshots of five hard exploration Atari-2600 games.
tion (TRPO) (Schulman al. 2015) the policy updating algorithm for CRL., and leave other variants of CRL for future work. We will denote our method as CRLTRPO in the following content. The baselines for comparison include TRPO and TRPO-Hash (Tang et 2017). For continuous control problem, we choose VIME as a baseline.
TRPO SShulman et al. 2015 is classic policy gradient method, which uses trust region guaran- tee stable improvement of policy and can handle both discrete and continuous action space. Further- more, this method is not too sensitive as heuristic exploration strategy.
syper-parameters TRPO adopts Gaussian control noise
TRPO-Has (Tang et al. 2017) is hash-based method, which is generalization of classic count- based method for high-dimensional and continuous state spaces. The main idea is to use locality- sensitive hashing (LSH) (Andoni Indyk (006)) encode continuous and high-dimense into hash codes, like 1 Here, h is the length of hash codes. TRPO-Hash has several variants in (Tang et al., (017). For fair comparison, we choose SimHash (Charikar 2002) (TRPO-Hash) as the hash function and pixels inputs for ERPO-Hash in this paper, because CRL also adopts pixels rather than advanced features as inputs. TRPO-Hare is trained by using the code provided by its authors.
data
VIME (Houthooft et al., 2016) is curiosity-driven exploration strategy, which seeks out unexplored state-action region by maximizing the information gain of agent's belief of environments. VIME is also trained by using the code provided by its authors. Here, we select VIME to compare with method in continuous control problem because this method only supports continuous state and action space.
5.2 PERFORMANCE ON MuJoCo
Figure shows the results of TRPO, TRPO-Hash, VIME and CRLTAro in MountainCar and Cart- poleSwingup We can find that our CRLTRPO achieves the best performance both MountainCar and CartpoleSwingup. good policy. Our method outperforms all other methods with large margin. The goal of TRPO- Hash is to help the agent explore more novel states. But TRPO-Hash might go through all states until reaching the goal state, which is the disadvantage of count (novelty) based exploration. We find that at the end of training, TRPO-Hash fails to achieve the goal that our method and VIME have achieved. The reason why TRPO-Hash fails is that the novelty of states diverts the agent's attention. The worst case is that the agent collects all states until finds the goal. This disadvantage of count-based methods might become more serious the high-dimensional state space since impossible to through all states in the high-dimensional state space. Therefore, strategies with only count-based exploration are insufficient.
MountainCar, our method the first one to reach the goal state and master
5.3 PERFORMANCE ON ATARI-2600
For the video games of Atari-2600, compare CRLTRPO with other baselines. The agent is trained for 500 iterations in all experiments with each iteration consisting of 0.4M frames. The agent selects an action every 4 frames, every iteration consists of M. steps (0.4M frames). The

---

Under review as a conference paper at ICLR 2020
12
CRL
CALmro
TRPG
Mban Average Rotum
TRPO-Hesh VIME
Meen Average Retuum
TRPO-Hfash
1000
244
100
0.2
10
20
400
800
Boration
Banation
(a) MountainCar
(b) CartpoleSwingup
Mean average return of different algorithms MountainCar and CartpoleSwingup over 5 random seeds. solid line represents the mean average return and shaded area represents one standard deviation.
Figure 3:
Table 1: The mean average undiscounted return after training for 50M time steps (200M frames).
Freeway
Frostbite
Gravitar
Solaris
Venture
TRPO
17.55
1229.66
500.33
2110.22
283.48
TRPO-Hash
22.29
2954.10
577.47
2619.32
299.61
CRLTAPO
26.68
4558.52
541.72
2976.23
723.94
Dou
33.3
1683
412
3068
98.0
Dueling network
0.0
4672
588
2251
497
+3C+
27.3
507
246
2175
0
pseudo-count
29.2
1450
369
last frames of every frames are used for clustering and counting. The performance is evaluated over 5 random seeds. The seeds for evaluation are the same for all methods.
We summarize all results Table 1 Please note that TRPO and TRPO-Hash are trained with code provided by the authors of TRPO-Hare All hyper-parametts parameters reported in the supple- mentary material. We also compare our methods to double-DQN (van Hasselt et al.) 2016), dueling network (Wang et al. 2016), A3C+ (Bellemare et al., 2016), double DQN with pseudo-count (Belle-) mare et al. 2016), the results of which are from (Tang et al. 2017). Furthermore, we show the training curves of our methods, TRPO and TRPO-Hash in Figure
CRLTRPO achieves significantly improvement over TRPO and TRPO-Hash on Freeway, Frostbite, Solaris and Venture. Please note that DQN-based methods reuse off-policy experience. Hence, DQN-based methods have better performance than TRPO without any exploration techniques in most cases. But our methods can still outperform DQN- methods most cases.
CONCLUSION
In this paper, we propose novel RL framework, called clustered reinforcement learning (CRL), for efficient exploration. By using clustering, CRL provides a general framework to adopt both novelty and quality in the neighboring area of the current state for exploration. Experiments several continuous control tasks and several hard exploration Atari-2600 games show that CRL can outperform other sate-of-the-ar methods to achieve the best performance in most cases.

---

Under review as a conference paper at ICLR 2020
20
16
CR 2ro TRPO-RSSh
CR
Hach
790
CiLiree TR-0 Harhh TRnO
TEPO
TaPo
Maan Zueraze Retum
800
20
500
13
4200
400
2300
300
200
300
100
100
Freeway
(b) Frostbite
(c) Gravitar
CRiowe
Gilawo
6000
TAPO Hach
1000
TRPO
Noth Redrage Return
T3PO
TEPO
1000
1000
602
2000
2000
.800
100
(d) Solaris
(c) Venture
Figure 4: Mean average of different algorithms Atari-2600 random seeds. The solid line represents mean average return the shaded area represents one standard deviation.
A APPENDIX
A.1
SETTING MuJoCo
In MuloCo, the hyper-parameter setting of TRPO, TRPO-Hash, CRLTRPO is shown in Table The hyper-parameter setting of VIME can be found in (Houthooft et al. (016)) The performance evaluated over 5 random seeds. The seeds for evaluation are the same for all methods.
Table 2: Hyper- paremmeer setting in MuJoCo.
TRPO
TRPO-Hash
CRLTAPO
TRPO batchsize
5000
TRPO stepsize
0.01
Discount factor
0.99
Policy hidden units
(32, 32)
Baseline function
Linear
Iteration
30
Max length of path
500
Bonus coefficient
0.01
Others
Simhash dimension: 32
#cluster centers: 16
1) 0.1
A.2 HYPER-PARAMETER SETTING ATARI-2600
The hyper-paramen parameter settings in TRPO, TRPO-Hast and CRLTRPO are shown in Table B The performance evaluated over 5 random seeds. The seeds for evaluation are the same for methods.
8

---

Under review as a conference paper at ICLR 2020
Table 3: Hyper-parameter setting of Atari-2600 in Table T
TRPO
TRPO-Hash
CRLTRPO
TRPO batchsize
100K
TRPO stepsize
0.001
Discount factor
0.99
Iteration
500
Max length of path Policy structure
4500
16 cony filters of size x 8, stride 4
32 conv filters of size x 4, stride 2 fully-connect layer with 256 units
linear transform and softmax output action probabilities
Input pre-processing
grayscale; downsampled to 42 x 42
each pixel rescaled to 1-,,
previous frames are concatenated to form the input state
Bonus coefficient
0.01
0.01
Others
SimHash dimension: 64
Number of clusters: 16
7) = 0.1
REFERENCES
David Abel, Alekh Agarwal, Fernando Diaz, Akshay Krishnamurthy, and Robert Schapire. Exploratory gradient boosting for reinforcement learning in complex domains. CoRR, hbs//603.00119/ 2016
Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neigh- bor in high dimensions. FOCS, pp. 459-468, 2006.
Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. NeurlPS, pp. 49-56, 2006.
Mare G. Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning envi- ronment: An evaluation platform for general agents. JAIR, 47:253-279, 2013.
Mare G. Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Rémi Munos. Unifying count-based exploration and intrinsic motivation. In NeurlPS, pp. 1471-1479, 2016.
Ronen I. Brafman and Moshe Tennenholtz. R-MAX A general polynomial time algorithm for near-optimal reinforcement learning. JMLR, 3:213-231, 2002.
Yuri Burda, Harrison Edwards, Amos J. Storkey, and Oleg Klimov. Exploration by random network distillation. CoRR, abs/1810. 12894, 2018.
Moses Charikar. Similarity estimation techniques from rounding algorithms. In STOC, pp. 380-388, 2002.
Adam Coates and Andrew Y. Ng. Learning feature representations with k-means. Neural Net- works: Tricks of the Trade Second Edition, pp. 561-580. 2012.
Yan Duan, Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In ICML, pp. 1329-1338, 2016.
Justin Fu, John D. Co-Reyes, and Sergey Levine. EX2: exploration with exemplar models for deep reinforcement learning. In NeurlPS, pp. 2574-2584, 2017.

---

Under review as a conference paper at ICLR 2020
Rein Houthooft, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. VIME: variational information maximizing exploration. In NeurlPS, pp. 1109-1117, 2016.
Michael J. Kearns and Satinder P. Singh. Near-optimal reinforcement learning in polynomial time. Machine Learning, 49(2-3):09--322 2002.
Alexander S. Klyubin, Daniel Polani, and Chrystopher L. Nehaniv. Empowerment: universal agent-centric measure of control. In CEC, pp. 128-135, 2005.
Timothy P. Lillicrap. Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning, ICLR, 2016.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529-53333 2015.
Dirk Ormoneit and Saunak Sen. Kernel-based reinforcement learning. Machine Learning, 49(2-3)
161-178, 2002.
Ronald Ortner. Adaptive aggregation for reinforcement learning in average reward markov decision processes. Annals OR, 203(1)33,,-336, 2013.
Georg Ostrovski, Marc G. Bellemare, Aäron van den Oord, and Rémi Munos. Count-based explo- ration with neural density models. In ICML, pp. 2721-22222222 2730, 2017.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In ICML, pp. 2778-2787,
John Schulman, Sergey Levine, Pieter Abbeel, Michael I. Jordan, and Philipp Moritz. Trust region policy optimization. In ICML, pp. 1889-1897, 2015.
David Silver. Aja Huang, Chris J. Maddison. Arthur Guez, Laurent Sifre, George van den Driess- che, Julian Schrittwieser, loannis Antonoglou. Vedavyas Pannecrshelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016.
Satinder P. Singh, Tommi S. Jaakkola, and Michael I. Jordan. Reinforcement learning with soft state aggregation. In NewrlPS, pp. 361-368, 1994.
Bradly C. Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. CoRR, abs/1507.008 2015.
Alexander L. Strehl and Michael L. Littman. An analysis of model- interval estimation for markov decision processes. JCSS, 74(8):1309-133) 1131, 2008.
Richard S. Sutton and Andrew G. Barto. Reinforcement learning an introduction. Adaptive com- putation and machine learning. MIT Press, 1998.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. #exploration: A study of count-based exploration for deep reinforcement learning. In NeurIPS, pp. 2750-2759, 2017.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. AAAI, pp. 2094-2100, 2016.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado van Hasselt, Mare Lanetot, and Nando de Freitas. Dueling network architectures for deep reinforcement learning. In ICML, pp. 1995-2003, 2016.
Marvin Zhang, Zoe McCarthy, Chelsea Finn, Sergey Levine, and Pieter Abbeel. Learning deep neural network policies with continuous memory states. In ICRA, pp. 520-527, 2016.
10


Reviews:
[{"review_id": "ryl70K8hYB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a new reinforcement learning framework named clustered reinforcement learning. The proposed method employs the clustering method to explore the novelty and quality in the neighboring area. Some suggestions are as below:\n\n1. The method adopts the k-means for clustering. How about other clustering methods, like Spectral Clustering and other recent deep clustering methods? It's expected to give the experiment comparison results with other clustering methods. Is the method senstive to the used clustering method. \n2. Usually in the clustering tasks, how to decide the cluster number K is a crucial problem for many applications. And for this method, the clustering is employed in the exploration stage to cluster neighboring areas, how to determine the value of K. Are there any specifical information could be used? Moreover, could the clustering part be jointly trained in the framework? It' required to investigate the influence of K theoretically and experimentally.\n3. As the author claimed, the novelty and quality are both important for exploration in RL, the key question is thus how to balance and utilize them carefully in the exploration stage. The contribution of this paper is about the state clustering for exploration in RL which can further reflect the novelty and quality. How to utilize and balance the novelty and quality is still unsolved in this paper. \n\nIn summary, I ack that the idea is effective but seems straightforward. It would be better to present some theoretical analysis. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "rkgyvJ3_uS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a clear approach to improve the exploration strategy in reinforcement learning, which is named clustered reinforcement learning. The approach tries to push the agent to explore more states with high novelty and quality.  It is done by adding a bonus reward shown in Eq. (3) to the reward function. The author first cluster states into clusters using the k-means algorithm. The bonus reward will return a high value for a state if the corresponding cluster has a high average reward. When the total reward in a cluster is smaller than a certain threshold, the bonus reward will consider the number of states explored. In the experiments, the authors test different models on two MuJoCo tasks and five Atari games. TRPO, TRPO-Hash, VIME are selected as baselines to compare with. Results show that the proposed bonus reward reaches faster convergence and the highest return in both MuJoCo tasks. In those five Atari games, the proposed method achieves the highest or second-highest average returns.\n\nAlthough the paper is generally easy to follow and the motivations of the equations are clear,  the analysis of the results is missing and thus the paper provides very limited insights on the behavior of the proposed method. As a result, my opinion on this paper leans to a rejection. As ICLR recommends paper length to be 8 pages, the authors can and should use the remaining space to give more details. For example, the authors can show the mean reward and number of states in all clusters to see whether the agent is efficiently exploring different clusters. And as the number of clusters K is an important hyper-parameter, the reader will also be curious about the resultant performance of the method with different K.\n\nSome questions:\n1) In Eq. (3), you have two hyper-parameters in the bonus reward, and for MuJoCo and Atari games, you are using different settings for the first coefficient. How do you choose the hyper-parameter settings? Do you perform grid search with another environment or a set of environments to determine the hyper-parameters?\n\n3) In the algorithm, the method has to learn new cluster assignments in each iteration. Does it significantly slow down the training of the agent? \n\n4) In the experiments, the authors compare with other methods on only five Atari games. However, there should be more environments available.  What is the reason for choosing these five games? Unless it is difficult to gather the scores on more environments, I believe the authors shall provide results with more Atari environments.\n\n5) The conclusion (Section 6) is extremely short and it claims that \"CRL can outperform other SOTA methods in most cases\". However, for the five Atari games, the only game that CRL achieves the best performance among seven methods is Venture, according to Table 1. \nSuch a claim will confuse readers as it is not in line with the results.\n\nAll in all, I believe this paper can be significantly improved if more details and analyses are provided.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "SklciHXTKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a clustering based algorithm to improve the exploration performance in reinforcement learning. Similar to the count based approaches, the novelty of a new state was computed based on the statistics of the corresponding clusters. This exploration bonus was then combined with the TRPO algorithm to obtain the policy. The experimental results showed some improvement, compare with its competitors.\n\nAlthough the proposed method is somewhat similar to the earlier hash based approaches, I think it is still interesting by using the clustering, instead of computing the hash code with neural networks. On the other hand, the motivation and explanation of this method are not well presented. I also have some concern regarding the fairness of the comparison in experiments. The English usage could be improved as well. My detailed comments and questions are as follows.\n1. The new proposal for the exploration bonus is provided in Equation (3). The denominator there is essentially the count, which is consistent with previous count based approaches (though not with the square root). For the numerator, I am a bit confused about the choice, as if \"N\" is small, the accumulated \"R\" could be small as well, which may offset the bonus based on count. I also didn't understand the author's claim that \"...it is highly possible that all states in cluster \\phi (s) have zero reward\", just below Equation (3). Unless the authors provide more details, I am not convinced that the enumerator could be a good choice.\n2. Given the proposed bonus, I am wondering how sensitive could it be to the choice of hyperparameters, especially w.r.t \\eta. The authors may need to provide more ablation studies on their effect.\n3. Another concern is regarding the scalability of the proposed method. Algorithm 1 implies that k-means needs to be conducted in every iteration, which could be very slow. So how about the running time of the proposed method, when compared with baselines?\n4. In the experiments, the authors claimed that the code for TRPO-Hash is provided by its authors. However, the scores for TRPO-Hash were much worse than the numbers in the TRPO-Hash paper (see their Table 1). Do you have any explanation? \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper discusses a simple but apparently effective clustering technique to improve exploration. There are no theoretical results, hence the reader relies fully on the experiments to evaluate the method. Unfortunately, an in-dept analysis of the results is missing making it hard to properly evaluate the strength and weaknesses. Furthermore, the authors have not provided any rebuttal to the reviewers' concerns.
Decision: Reject