REVIEW 2 major objections 6 minor 55 references
Novelty Search in Representational Space for Sample Efficient Exploration
T0 review · 2 major / 6 minor · reviewed 2026-08-27 · deepseek-v4-flash
Pith's one-line read The paper claims that measuring novelty as the average Euclidean distance to a state's k nearest neighbors in a low-dimensional, information-bottleneck-shaped representation space makes an RL agent explore sparse-reward environments in…
desk verdict A genuinely interesting exploration idea whose headline sample-efficiency claim is undercut by uneven baseline compute; worth refereeing, but only after the comparisons are redone fairly. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the pair consisting of the representation-learning losses and the k-nearest-neighbor novelty score. The encoder is trained with a transition loss that aligns encoded next states, a uniformity loss minimizing expected pairwise Gaussian potential between encoded states, and a soft constraint $L_{\mathrm{csc}}=\max(\|\hat e(s_1)-\hat e(s_2)\|_2-\omega,0)$ that keeps consecutive encoded states at a distance around $\omega$. The novelty reward is $\hat\rho_X(x)=\frac{1}{k}\sum_{i=1}^{k} d(x,x_i)$ over the $k$ nearest neighbors of the encoded state $x$ in the visitation history; the training losses are meant to make the Euclidean distance in this space track dynamics-relevant novelty rather than pixel similarity. This score is what carries the argument, because it is proportional to the inverse of a k-NN density estimate, so rewarding it pushes the agent toward under-visited regions.
What would settle it
In a tabular maze where true visitation counts are known, compute the rank correlation between the novelty score and the true inverse visitation density across all states; if it is not strongly positive, or if a genuinely unvisited state maps to a small k-nearest-neighbor distance, the intrinsic reward misdirects exploration and the sample-efficiency claim collapses.
Extended reading notes
Core claim
The central claim is that encoding states into a low-dimensional abstract space with an information-bottleneck-style objective—minimizing encoding rate while maximizing the mutual information between the encoded state plus action and the next encoded state—yields a space in which the average Euclidean distance to a state's k nearest neighbors is a valid novelty signal. The paper argues that this score is proportional to the inverse of a classical k-nearest-neighbor density estimate, hence to inverse visitation density, and then uses it as an intrinsic reward. Action selection combines a learned transition model with a learned Q-function in a depth-limited rollout that maximizes intrinsic reward, capped by an epsilon-greedy policy. On an open 21x21 labyrinth, a four-room labyrinth, a pixel-input Acrobot, and a multi-step key-door maze, the agent reaches the goal in fewer environment steps than the compared baselines, with statistical significance reported via a two-sample t-test.
Load-bearing premise
The method stands or falls on the assumption that the average Euclidean distance to a state's k nearest neighbors in the learned low-dimensional space is a faithful stand-in for how rarely that state has been visited, so that larger distance reliably means more novel.
Editorial extensions
If this is right
- In the open labyrinth the agent reaches about 80% of the 361 reachable states in roughly 500 environment steps and all of them in roughly 800 steps, outperforming random and count-based baselines.
- In the four-room labyrinth the method again explores a larger share of states than the baselines, with the epsilon-greedy policy compensating for occasional over-generalization of walls.
- In Acrobot from four stacked pixel frames with a four-dimensional representation, the method reaches the goal in fewer steps than all four baselines (576 versus 592.5 for the strongest baseline).
- In the multi-step key-door maze, the method reaches the goal in 524.6 steps on average, fewer than the best baseline's 658.8 steps.
- The learned representations are interpretable: maze positions are preserved in the low-dimensional space and key/no-key states form separated clusters.
Reading between the lines
- Since the novelty score's validity depends only on the metric geometry of the embedding, a testable extension is to replace the information-bottleneck losses with any representation objective that enforces alignment and uniformity, such as contrastive learning, and measure whether sample efficiency survives.
- The training scheme runs many gradient steps per environment step, so the reported sample-efficiency gain may be partly a compute-for-samples trade; a comparison that fixes total compute would reveal where the advantage actually comes from.
- One could test the mechanism directly in a tabular maze where true visitation counts are known by checking whether the novelty score ranks genuinely under-visited states ahead of well-visited ones.
- The hand-tuned representation dimension and the $\omega$ spacing parameter suggest an extension that adapts them online, since over-generalization to a too-small dimension is identified in the paper as a source of failure.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes NSRS (Novelty Search in Representational Space), an exploration method that assigns an intrinsic reward equal to the average Euclidean distance from an encoded state to its k nearest neighbors in a learned low-dimensional representation. The representation is trained with losses motivated by the information bottleneck: a transition loss, a uniformity (pairwise Gaussian potential) loss, and a soft constraint on consecutive-state distances. The agent combines Q-learning with model predictive rollouts in representational space, and the intrinsic reward is used to drive exploration. Experiments on two labyrinth environments, Acrobot, and a multi-step maze compare the method against random, count-based, prediction-error, hash-count, RND, and BDQN baselines, reporting improved sample efficiency. The paper also includes ablations, a theorem on asymptotic convergence of the novelty score, and visualizations of learned abstract representations.
Significance. If the sample-efficiency improvements hold under fair comparison, the paper would make a useful contribution: it shows that a simple k-NN distance novelty signal in a dynamics-shaped low-dimensional representation can guide exploration more efficiently than several strong baselines, and the learned representations are interpretable. Strengths include the release of code, the inclusion of ablations, and the clean tabular labyrinth experiments with count-based baselines. However, the central empirical claim is currently weakened by unequal training budgets across baselines, and the theoretical link between the novelty heuristic and recoding probability is not rigorously established. The favorable labyrinth results are encouraging, but they do not by themselves validate the comparisons against deep RL baselines in the control and maze settings.
major comments (2)
- [Table 1 and Appendices J.3-J.4] The sample-efficiency claim is confounded by unequal compute budgets across methods. Algorithm 1 performs up to niters training iterations every nfreq environment steps, so a higher niters means more gradient updates per environment sample. Appendix J.3 states that in Acrobot, RND and the prediction-error baseline were trained with niters = 3000 while Novelty and BDQN used niters = 50000, and Appendix J.4 states that in the multi-step maze, model-free baselines used niters = 30000 with learning rate 0.00025 while methods with a model-based component used niters = 50000 with learning rate 0.000025. The significant maze comparisons therefore do not isolate the exploration mechanism from a compute and data-reuse advantage. The only strong baseline with matched niters, BDQN in Acrobot, is not significantly better or worse than Novelty (576.0 vs 592.5, p = 0.85). To support the abstract's claim, the authors should provide compute-matched or update-matched comparisons, or demonstrate that the baselines' performance is insensitive to the training budget.
- [Appendix D] The derivation claiming that the novelty heuristic \hat{\rho}_X(x) is inversely proportional to the recoding probability is dimensionally invalid. The k-NN density estimate uses the volume V_{x,x_k} of a ball in R^{n_X}, which scales as r^{n_X}, not as r. Replacing V_{x,x_i} with the distance d(x,x_i) changes the estimator's units and functional form, so the stated proportionality does not follow from the presented equations. Since Section 4.1 explicitly relies on this inverse-probability interpretation, the authors should either provide a valid derivation (for example, showing that distance to the kth neighbor is a monotone function of local density under a uniformity assumption) or explicitly describe the novelty score as a heuristic and temper the corresponding claim.
minor comments (6)
- [Eq. (4) and Appendix J] The uniformity loss L_d1 depends on the hyperparameter C_d1, but Appendix J, which lists the hyperparameters kept constant across experiments, does not specify a value for C_d1; please add it.
- [Section 5.2] Random Network Distillation is cited as "Osband et al., 2017" in the list of baselines; the correct reference is Burda et al. (2018b), while Osband et al. (2017) is a different method.
- [References] The reference list contains two entries for Stadie et al. (2015); one is redundant and should be removed.
- [Algorithm 1] Line 10 recomputes intrinsic rewards for all buffer transitions using the current encoder, but the text does not explain that the reward signal is non-stationary as the encoder and buffer evolve; adding a clarifying sentence would help readers understand the training dynamics.
- [Section 5.2.1] The text says "We use a 4-dimensional abstract representation of our state" immediately after describing 4 stacked pixel frames as input; it should be explicit that the abstract representation dimension is 4 while the input is 4 stacked frames.
- [Figure 1] The caption references "Figures 7a and 7b," but Figure 7 is composed of two panels labeled left and right; please update the cross-reference.
Circularity Check
No significant circularity: the sample-efficiency claim rests on external benchmark comparisons, and the k-NN novelty heuristic is a direct design choice rather than a fitted input renamed as a prediction.
full rationale
The central claim is empirical and externally evaluated: Table 1 reports environment steps to reach goal states, with the intrinsic reward defined directly in Eq. 7 as average Euclidean distance to k nearest neighbours. The representation is shaped by the losses in Eqs. 3-6, but that shaping is a stated algorithmic design, not an inversion of the evaluation metric; the agent is not fit to the benchmark outcome and then reported as predicting it. The self-citation to Francois-Lavet et al. (2018) supports the general intuition that dynamics-similar states map nearby, but the paper specifies and optimizes its own losses, so the citation is not load-bearing in the sense of importing an unverified uniqueness or ansatz. Appendix D's substitution of neighborhood volume by raw distance is mathematically unsound (volume grows as r^d, not r), and Appendices J.3-J.4 reveal unequal training iterations between Novelty and some baselines; both are validity concerns about the empirical comparison and theoretical justification, but neither makes the derivation circular. No equation is defined in terms of the claimed conclusion, no fitted parameter is relabelled as a prediction, and no self-citation chain forces the result. The finding is therefore no significant circularity.
Assumptions & free parameters
free parameters (5)
- Representation dimension nX =
2 (labyrinths), 4 (Acrobot), 3 (multi-step maze)
- omega (minimum consecutive-state distance) =
0.5
- delta (slack ratio) =
12
- k (number of nearest neighbors) =
5
- niters and nfreq =
niters=30000 or 50000; nfreq=1 or 3
assumptions (4)
- domain assumption The transition function is deterministic (Section 2).
- ad hoc to paper The losses Ltau, Ld1, and Lcsc jointly maximize I[X';{X,A}] and minimize I[S';X'] approximately (Section 3.2).
- ad hoc to paper The novelty heuristic is inversely proportional to recoding probability (Appendix D).
- standard math Finite state space and communicating MDP for Theorem 1 (Section 4.2).
Cite this review
Pith. "Pith review of Novelty Search in Representational Space for Sample Efficient Exploration." pith.science (2026). https://pith.science/paper/F5BHXBMS
@misc{pith2026200913579,
author = {Pith},
title = {Pith review of: Novelty Search in Representational Space for Sample Efficient Exploration},
year = {2026},
howpublished = {\url{https://pith.science/paper/F5BHXBMS}},
note = {Machine review of arXiv:2009.13579}
}
read the original abstract
We present a new approach for efficient exploration which leverages a low-dimensional encoding of the environment learned with a combination of model-based and model-free objectives. Our approach uses intrinsic rewards that are based on the distance of nearest neighbors in the low dimensional representational space to gauge novelty. We then leverage these intrinsic rewards for sample-efficient exploration with planning routines in representational space for hard exploration tasks with sparse rewards. One key element of our approach is the use of information theoretic principles to shape our representations in a way so that our novelty reward goes beyond pixel similarity. We test our approach on a number of maze tasks, as well as a control problem and show that our exploration approach is more sample-efficient compared to strong baselines.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[1]
Abel, D., Salvatier, J., Stuhlm \"u ller, A., and Evans, O. (2017). Agent-agnostic human-in-the-loop reinforcement learning. arXiv preprint arXiv:1701.04079
work page Pith review arXiv 2017
-
[2]
Surprise-Based Intrinsic Motivation for Deep Reinforcement Learning
Achiam , J. and Sastry , S. (2017). Surprise-Based Intrinsic Motivation for Deep Reinforcement Learning . arXiv e-prints , page arXiv:1703.01732
work page Pith review arXiv 2017
-
[3]
Unifying Count-Based Exploration and Intrinsic Motivation
Bellemare, M. G., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., and Munos, R. (2016). Unifying count-based exploration and intrinsic motivation. arXiv preprint arXiv:1606.01868
work page Pith review arXiv 2016
-
[4]
Borodachov, S., Hardin, D., and Saff, E. (2019). Discrete Energy on Rectifiable Sets
work page 2019
-
[5]
Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W. (2016). Openai gym
work page 2016
-
[6]
Burda , Y., Edwards , H., Pathak , D., Storkey , A., Darrell , T., and Efros , A. A. (2018a). Large-Scale Study of Curiosity-Driven Learning . arXiv e-prints , page arXiv:1808.04355
work page Pith review arXiv 2018
-
[7]
Burda , Y., Edwards , H., Storkey , A., and Klimov , O. (2018b). Exploration by Random Network Distillation . arXiv e-prints , page arXiv:1810.12894
work page Pith review arXiv 2018
-
[8]
Chebotar, Y., Hausman, K., Zhang, M., Sukhatme, G., Schaal, S., and Levine, S. (2017). Combining model-based and model-free updates for trajectory-centric reinforcement learning
work page 2017
Show all 55 references
-
[9]
G., and Singh, S
Chentanez, N., Barto, A. G., and Singh, S. P. (2005). Intrinsically motivated reinforcement learning. In Saul, L. K., Weiss, Y., and Bottou, L., editors, Advances in Neural Information Processing Systems 17 , pages 1281--1288. MIT Press
2005
-
[10]
Chiappa, S., Racaniere, S., Wierstra, D., and Mohamed, S. (2017). Recurrent environment simulators. arXiv preprint arXiv:1704.02254
2017 arXiv
-
[11]
and Thomas, J
Cover, T. and Thomas, J. (2012). Elements of Information Theory . Wiley
2012
-
[12]
Dayan, P. (1993). Improving generalization for temporal difference learning: The successor representation. Neural Computation , 5(4):613--624
1993
-
[13]
de Bruin, T., Kober, J., Tuyls, K., and Babu s ka, R. (2018). Integrating state representation learning into deep reinforcement learning. IEEE Robotics and Automation Letters , 3(3):1394--1401
2018
-
[14]
Fran c ois - Lavet, V., Bengio, Y., Precup, D., and Pineau, J. (2018). Combined reinforcement learning via abstract representations. CoRR , abs/1809.04506
2018 arXiv
-
[15]
E., Prett, D
Garcia, C. E., Prett, D. M., and Morari, M. (1989). Model predictive control: Theory and practice - a survey. Autom. , 25:335--348
1989
-
[16]
and Fern\' a ndez, F
Garc\' a, J. and Fern\' a ndez, F. (2015). A comprehensive survey on safe reinforcement learning. J. Mach. Learn. Res. , 16(1):1437–1480
2015
-
[17]
Gelada, C., Kumar, S., Buckman, J., Nachum, O., and Bellemare, M. G. (2019). Deepmdp: Learning continuous latent space models for representation learning. arXiv preprint arXiv:1906.02736
2019 arXiv
-
[18]
J., and Wierstra, D
Gregor, K., Rezende, D. J., and Wierstra, D. (2016). Variational intrinsic control. arXiv preprint arXiv:1611.07507
2016 arXiv
-
[19]
and Schmidhuber , J
Ha , D. and Schmidhuber , J. (2018). Recurrent World Models Facilitate Policy Evolution . arXiv e-prints , page arXiv:1809.01999
2018 arXiv
-
[20]
Haber, N., Mrowca, D., Fei-Fei, L., and Yamins, D. L. (2018). Learning to play with intrinsically-motivated self-aware agents. arXiv preprint arXiv:1802.07442
2018 arXiv
-
[21]
Hafner , D., Lillicrap , T., Fischer , I., Villegas , R., Ha , D., Lee , H., and Davidson , J. (2018). Learning Latent Dynamics for Planning from Pixels . arXiv e-prints , page arXiv:1811.04551
2018 arXiv
-
[22]
and Stone, P
Hester, T. and Stone, P. (2012). Intrinsically motivated model learning for a developing curious agent. 2012 IEEE International Conference on Development and Learning and Epigenetic Robotics (ICDL) , pages 1--6
2012
-
[23]
Houthooft, R., Chen, X., Duan, Y., Schulman, J., De Turck, F., and Abbeel, P. (2016). Vime: Variational information maximizing exploration. In Advances in Neural Information Processing Systems , pages 1109--1117
2016
-
[24]
P., Littman, M
Kaelbling, L. P., Littman, M. L., and Cassandra, A. R. (1998). Planning and acting in partially observable stochastic domains. Artificial Intelligence , 101(1):99 -- 134
1998
-
[25]
and Stanley, K
Lehman, J. and Stanley, K. O. (2011). Abandoning objectives: Evolution through the search for novelty alone. Evolutionary Computation , 19(2):189--223. PMID: 20868264
2011
-
[26]
Loftsgaarden, D. O. and Quesenberry, C. P. (1965). A nonparametric estimate of a multivariate density function. Ann. Math. Statist. , 36(3):1049--1051
1965
-
[27]
Mandel, T., Liu, Y.-E., Brunskill, E., and Popovi \'c , Z. (2017). Where to add actions in human-in-the-loop reinforcement learning. In Thirty-First AAAI Conference on Artificial Intelligence
2017
-
[28]
and Rezende, D
Mohamed, S. and Rezende, D. J. (2015). Variational information maximisation for intrinsically motivated reinforcement learning. In Advances in neural information processing systems , pages 2125--2133
2015
-
[29]
Oh, J., Singh, S., and Lee, H. (2017). Value prediction network. In Advances in Neural Information Processing Systems , pages 6118--6128
2017
-
[30]
Osband , I., Blundell , C., Pritzel , A., and Van Roy , B. (2016). Deep Exploration via Bootstrapped DQN . arXiv e-prints , page arXiv:1602.04621
2016 arXiv
-
[31]
Osband , I., Van Roy , B., Russo , D., and Wen , Z. (2017). Deep Exploration via Randomized Value Functions . arXiv e-prints , page arXiv:1703.07608
2017 arXiv
-
[32]
G., Oord, A
Ostrovski, G., Bellemare, M. G., Oord, A. v. d., and Munos, R. (2017). Count-based exploration with neural density models. arXiv preprint arXiv:1703.01310
2017 arXiv
-
[33]
A., and Darrell, T
Pathak, D., Agrawal, P., Efros, A. A., and Darrell, T. (2017). Curiosity-driven exploration by self-supervised prediction. In International Conference on Machine Learning (ICML) , volume 2017
2017
-
[34]
Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming . John Wiley & Sons, Inc., New York, NY, USA, 1st edition
1994
-
[35]
Salge, C., Glackin, C., and Polani, D. (2014). Changing the environment based on empowerment as intrinsic motivation. Entropy , 16(5):2789--2819
2014
-
[36]
Savinov, N., Raichuk, A., Marinier, R., Vincent, D., Pollefeys, M., Lillicrap, T., and Gelly, S. (2018). Episodic curiosity through reachability. arXiv preprint arXiv:1810.02274
2018 arXiv
-
[37]
Schmidhuber, J. (1990). A possibility for implementing curiosity and boredom in model-building neural controllers. In Proceedings of the First International Conference on Simulation of Adaptive Behavior on From Animals to Animats , pages 222--227, Cambridge, MA, USA. MIT Press
1990
-
[38]
Schmidhuber, J. (2010). Formal theory of creativity, fun, and intrinsic motivation (1990--2010). IEEE Transactions on Autonomous Mental Development , 2(3):230--247
2010
-
[39]
Shyam , P., Ja \'s kowski , W., and Gomez , F. (2018). Model-Based Active Exploration . arXiv e-prints , page arXiv:1810.12162
2018 arXiv
-
[40]
Silver , D., van Hasselt , H., Hessel , M., Schaul , T., Guez , A., Harley , T., Dulac-Arnold , G., Reichert , D., Rabinowitz , N., Barreto , A., and Degris , T. (2016). The Predictron: End-To-End Learning and Planning . arXiv e-prints , page arXiv:1612.08810
2016 arXiv
-
[42]
C., Levine , S., and Abbeel , P
Stadie , B. C., Levine , S., and Abbeel , P. (2015). Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models . arXiv e-prints , page arXiv:1507.00814
2015 arXiv
-
[43]
Stepleton, T. (2017). The pycolab game engine. https://github.com/deepmind/pycolab
2017
-
[44]
Still, S. (2009). Information-theoretic approach to interactive learning. EPL (Europhysics Letters) , 85:28005
2009
-
[45]
S., Precup, D., and Singh, S
Sutton, R. S., Precup, D., and Singh, S. (1999). Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artif. Intell. , 112(1–2):181–211
1999
-
[46]
A., Fedus, W., Machado, M
Taiga, A. A., Fedus, W., Machado, M. C., Courville, A., and Bellemare, M. G. (2020). On bonus based exploration methods in the arcade learning environment. In International Conference on Learning Representations
2020
-
[47]
Tamar, A., Levine, S., Abbeel, P., WU, Y., and Thomas, G. (2016). Value iteration networks. In Advances in Neural Information Processing Systems , pages 2146--2154
2016
-
[48]
Tang , H., Houthooft , R., Foote , D., Stooke , A., Chen , X., Duan , Y., Schulman , J., De Turck , F., and Abbeel , P. (2016). \#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning . arXiv e-prints , page arXiv:1611.04717
2016 arXiv
-
[49]
Thrun, S. B. (1992). Efficient exploration in reinforcement learning
1992
-
[50]
C., and Bialek , W
Tishby , N., Pereira , F. C., and Bialek , W. (2000). The information bottleneck method . arXiv e-prints , page physics/0004057
2000 arXiv
-
[51]
and Hinton, G
van der Maaten, L. and Hinton, G. (2008). Viualizing data using t-sne. Journal of Machine Learning Research , 9:2579--2605
2008
-
[52]
van Hasselt , H., Guez , A., and Silver , D. (2015). Deep Reinforcement Learning with Double Q-learning . arXiv e-prints , page arXiv:1509.06461
2015 arXiv
-
[53]
and Isola, P
Wang, T. and Isola, P. (2020). Understanding contrastive representation learning through alignment and uniformity on the hypersphere
2020
-
[54]
@esa (Ref
\@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should ...
-
[55]
\@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@firs...
-
[56]
L u D ` ̬ l0 0QcccKKե ,G&
@open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibset...
2020
Reviewed August 27, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.