summaries: This paper has developed a framework for contrastive learning through time (CLTT). Instead of using augmentation operations to create positive pairs for contrastive learning, this paper creates several datasets with a near-photorealistic training environment by changing different view directions. The temporally close video frames of the new data are thus similar and should align in representation, which can naturally be considered as positive data.

summaries: The authors propose to perform self-supervised learning (SSL) by enforcing temporal consistency (as opposed to augmentation consistency in most recent efforts). They do this by adapting existing SSL approaches (SimCLR, RELIC and BYOL) to leverage video frames that are close in time as opposed to different augmentations of a given image (akin to a temporal augmentation). In addition, the authors introduce two new datasets which they use to train and study the learnt representations in detail, showing promising results.

summaries: In this paper, author introduce an image-based contrastive learning framework which substitutes traditional data argumentation by using successive images along with the temporal dimension. A new dataset is also generated in this paper for better studying the topic. Extensive experiments demonstrate that the proposed method is able to learn as good feature representation as supervised learning  in some datasets.

summaries: The paper proposes a new method to select positive pairs for contrastive learning: using adjacent frames in a sequence, referred to as Contrastive Learning Through Time (CLTT). This is relevant since CL approaches have been shown to depend a lot on what kind of augmentation is used. The method is integrated with a number of well-known CL approaches, and evaluated on three different datasets, two of which are novel --the method is shown to approach fully supervised results. The paper also provides a valuable discussion on how the notion of time can help representation learning. The method is also tested for latent representation similarity when one object or pattern is systematically shown after another, something which has been studied in the field of biological learning, and a similar trend is found here as well.

abstractText: Human infants learn to recognize objects largely without supervision. In machine learning, contrastive learning has emerged as a powerful form of unsupervised representation learning. The utility of learned representations for downstream tasks depends strongly on the chosen augmentation operations. Taking inspiration from biology, we here study a framework for unsupervised learning of object representations we call Contrastive Learning Through Time (CLTT). CLTT simulates viewing sequences as they might be experienced by an infant while interacting with objects and avoids arbitrary augmentation operations. Instead, positive pairs are formed by successive views in such unsegmented viewing sequences. Generating viewing sequences procedurally, rather than using natural videos, gives us perfect control over the temporal structure of the input and allows us to ask the following two questions. First, can CLTT approach the performance of fully supervised learning? Second, if so, what are the required conditions on the temporal structure of the input? To answer these questions, we develop a new data set using a near-photorealistic training environment based on ThreeDWorld (TDW). We consider several state-of-the-art contrastive learning methods and demonstrate that CLTT allows linear classification performance that approaches that of the fully supervised setting if subsequent views are sufficiently likely to stem from the same object. We also consider the effect of one object being seen systematically before or after another object. We show that this leads to increased representational similarity between these objects, reminiscent of classic neurobiological findings. The data sets, code and pre-trained models for this paper can be downloaded at: (link will be added in the final version).

authors:
Sven Bambach
David Crandall
Linda Smith
Chen Yu

title: Toddler-inspired visual object learning

venue: Advances in Neural Information Processing Systems,

authors:
Ting Chen
Simon Kornblith
Mohammad Norouzi
Geoffrey Hinton

title: A simple framework for contrastive learning of visual representations

venue: In International conference on machine learning,

authors:
Xinlei Chen
Haoqi Fan
Ross Girshick
Kaiming He

title: Improved baselines with momentum contrastive learning

venue: arXiv preprint arXiv:2003.04297,

authors:
Jia Deng
Wei Dong
Richard Socher
Li-Jia Li
Kai Li
Li Fei-Fei

title: Imagenet: A large-scale hierarchical image database

venue: IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Christoph Feichtenhofer
Haoqi Fan
Bo Xiong
Ross Girshick
Kaiming He

title: A large-scale study on unsupervised spatiotemporal representation learning

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR),

title: Learning invariance from transformation sequences

venue: Neural computation,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Joshua Knights
Ben Harwood
Daniel Ward
Anthony Vanderkop
Olivia Mackenzie-Ross
Peyman Moghadam

title: Temporally coherent embeddings for self-supervised video representation learning

venue: In 2020 25th International Conference on Pattern Recognition (ICPR),

authors:
Alexander LaTourrette
Sandra R Waxman

title: A little labeling goes a long way: Semi-supervised learning in infancy

venue: Developmental science,

authors:
David Lipshutz
Charles Windolf
Siavash Golkar
Dmitri Chklovskii

title: A biologically plausible neural network for slow feature analysis

authors:
Ilya Loshchilov
Frank Hutter

title: Decoupled weight decay regularization

venue: In International Conference on Learning Representations,

authors:
Jovana Mitrovic
Brian McWilliams
Jacob C Walker
Lars Holger Buesing
Charles Blundell

title: Representation learning via invariant causal mechanisms

title: Neuronal correlate of visual associative long-term memory in the primate temporal cortex

authors:
Yasushi Miyashita
Sei-Ichi Higuchi
Kuniyoshi Sakai
Naohiko Masui

title: Generation of fractal patterns for probing the visual memory

venue: Neuroscience Research,

authors:
Hossein Mobahi
Ronan Collobert
Jason Weston

title: Deep learning from temporal coherence in video

venue: In Proceedings of the 26th Annual International Conference on Machine Learning,

authors:
Sameer A Nene
Shree K Nayar
Hiroshi Murase

title: Columbia object image library (coil-100)

venue: Technical report,

authors:
Emin Orhan
Vaibhav Gupta
Brenden M Lake

title: Self-supervised learning through the eyes of a child

authors:
Tian Pan
Yibing Song
Tianyu Yang
Wenhao Jiang
Wei Liu

title: Videomoco: Contrastive video representation learning with temporally adversarial examples

authors:
Edmund T Rolls
T Milward

title: A model of invariant object recognition in the visual system: learning rules, activation functions, lateral inhibition, and information-based performance measures

authors:
Stefan Stojanov
Samarth Mishra
Ngoc Anh Thai
Nikhil Dhanda
Ahmad Humayun
Chen Yu
Linda B Smith
James M Rehg

title: Incremental object learning from contiguous views

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Jessica Sullivan
Michelle Mei
Andrew Perfors
Erica Wojcik
Michael C Frank

title: Saycam: A large, longitudinal audiovisual dataset recorded from the infant’s perspective

venue: Open Mind, pp

authors:
Xiaolong Wang
Abhinav Gupta

title: Unsupervised learning of visual representations using videos

venue: In Proceedings of the IEEE International Conference on Computer Vision (ICCV),

authors:
Yingfan Wang
Haiyang Huang
Cynthia Rudin
Yaron Shaposhnik

title: Understanding how dimension reduction tools work: An empirical approach to deciphering t-sne, umap, trimap, and pacmap for data visualization

venue: Journal of Machine Learning Research,

authors:
Laurenz Wiskott
Terrence J Sejnowski

title: Slow feature analysis: Unsupervised learning of invariances

heading: 1 INTRODUCTION

text:
A hallmark of biological organisms is their ability to learn to understand the world around them in a largely autonomous fashion. Consider learning about visual objects. A human infant is not exposed to object views sampled i.i.d. from some fixed distribution and conveniently labeled image by image, but forms representations of objects and categories during extended interactions with individual objects (Bambach et al., 2018) and requires hardly any (verbal) labels for this (LaTourrette & Waxman, 2019). Mimicking such learning abilities in artificial systems would represent a giant leap forward for artificial intelligence.
Self-supervised learning has emerged as a promising alternative to fully supervised approaches. In the domain of visual object recognition, recent contrastive learning approaches have obtained strong results on standard object recognition benchmarks (Chen et al., 2020a;b; Mitrovic et al., 2021; Grill et al., 2020). These approaches rely on a range of so-called augmentation operations. The basic idea is that an image is transformed through a number of operations (e.g., scaling, flipping, cropping, rotating, blurring, color distortions, pixel noise, ...) that change its appearance but not its meaning (e.g., “cat”). The key mechanism of contrastive learning is to form a representation where such augmented versions of an image are mapped on to close-by latent representations, while at the same time avoiding a “collapse” of the representation, i.e., making sure the network does not simply map all inputs to the same point in the latent space. Not surprisingly, the quality of the learned representations for downstream tasks strongly depends on the chosen augmentation operations (Grill et al., 2020).
Theories of biological learning have also addressed the requirement to learn object representations without (or with only few) labels. The classic theory of how biological organisms learn invariant
representations uses the notion of time to substitute for explicit labeling (Földiák, 1991; Rolls & Milward, 2000; Wiskott & Sejnowski, 2002). Biological organisms (including the human infant mentioned above) experience objects across time, typically seeing a sequence of different views of the same object before directing their attention elsewhere (Fig. 1A). Thus, by learning a representation such that subsequent views are mapped onto close-by latent codes (Fig. 1B), a representation should emerge that maps different views of the same object onto similar latent codes, thereby establishing (partial) invariance. While this idea has a long history in biological theorizing, it has only recently been explored in a contrastive learning context. The basic idea is to replace the augmentation operations in contrastive learning with natural appearance variation occurring during object interactions. To systematically study this approach, we propose a new Contrastive Learning Through Time (CLTT) framework that permits perfect control over the generated viewing sequences. For our experiments, we utilize the ThreeDWorld (TDW) virtual environment (Gan et al., 2021), which allows near-photorealistic rendering. We also simulate classic biological experiments by Miyashita (1988), demonstrating that objects form similar latent representations in the brain when they are systematically seen one after the other, even if they are visually dissimilar (Miyashita, 1988). We summarize our contributions as follows:
• We develop the CLTT framework using state-of-the-art contrastive learning methods.
• We introduce novel data sets to study CLTT under controlled conditions.
• We systematically analyze the conditions for CLTT to be successful and demonstrate that it approaches fully supervised learning.
• We show that CLTT maps objects that are systematically seen in temporal succession on similar latent representations, reminiscent of classic neurobiological findings.

heading: 2 RELATED WORK

text:
An early demonstration that the temporal structure of visual inputs shapes object representations in primate visual cortex was given by Miyashita (1988). He showed 97 images of fractal-like objects to monkeys in always the same order. As the monkeys learned to represent these images in their visual cortices, Miyashita’s observations suggested that the representations of objects which were neighbors in the sequence became aligned — even if these objects were visually dissimilar. This
effect extended over a few objects, i.e., the representations of objects six steps apart in the sequence were still more similar than the average similarity.
In part motivated by such findings, there is a long history of neural network and machine learning models exploiting temporal structure for unsupervised representation learning. Földiák (1991) introduced so-called trace learning rules to explain how neurons in the mammalian visual system learn invariance properties, setting a starting point for later models considering multi-layered network architectures (Rolls & Milward, 2000). Another line of research introduced by Wiskott & Sejnowski (2002) explicitly considers the objective of extracting components from an input stream that are slowly changing. A recent variant attempts to do so in a biologically plausible fashion (Lipshutz et al., 2020).
The use of temporal learning objectives in contrastive learning has received increasing attention recently. Among the first, Mobahi et al. (2009) have proposed a method for learning object representations that combines supervised learning and unsupervised learning based on temporal coherence using a siamese neural network architecture. Subsequently, Wang & Gupta (2015) used tracking of patches in videos for unsupervised pre-training, by learning an embedding that keeps patches from the same track close in the embedding space.
An approach more closely related to ours has recently been proposed by Orhan et al. (2020). They consider learning on a longitudinal headcam video set from three developing children (Sullivan et al., 2020). They focus on a temporal classification approach, where they divide the videos into a finite number of contiguous segments of the same length that they call temporal classes. The learning objective is to predict from which of the classes a particular video frame originates. They also consider a temporal contrastive learning objective with the MoCo contrastive learning implementation of Chen et al. (2020b). This objective also aims to make the latent representations of adjacent video frames similar. However, the use of uncontrolled headcam video does not permit determining the required the temporal statistics of the visual input for the approach to work. Another related approach is that of Knights et al. (2021), who learn embeddings of video clips. Their learning objective makes latent codes of adjacent frames within a video clip similar, while making them distinct from latent codes of frames from other video clips. Note that this setup requires the video clips to be segmented, i.e., the system has access to the information where each video starts and ends rather than being exposed to an unlabeled continuous video stream as in Orhan et al. (2020) and CLTT. The same holds true for the recent approach of Feichtenhofer et al. (2021) and also Pan et al. (2021). Yet, they don’t make the connection between continuous time frames and biologically-inspired vision. Finally, the interesting work of Stojanov et al. (2019) has modeled continual infant-like learning of object representations from unsegmented input streams, but they did not consider a contrastive learning approach.

heading: 3 METHODS

heading: 3.1 SAMPLING SEQUENCES OF OBJECT VIEWS IN CLTT

text:
CLTT aims to mimic the stream of object views that an infant may experience during natural interactions with objects, while giving precise control over the statistical properties of this view sequence. Specifically, an object is always viewed for Nfix fixations before another object comes into view. Importantly, the learner does not have access to the information when a new object comes into view, making the approach fully unsupervised. Generating these view sequences involves two sampling procedures. The first describes how the next view of the same object is sampled during the Nfix fixations on the same object. We refer to this as view sampling. The second describes how the identity of the next object is determined at the end of the Nfix fixations on the same object, which we refer to as object sampling.
For the view sampling, we distinguish two sampling methods. Our default method is the random walk view sampling. Here, the next view of an object is a “neighbor” of the previous view. For example, in the TDW data set (see below) this corresponds to changing azimuth or elevation by 10◦ or viewing distance by 10 cm. This procedure mimics the infant gradually turning an object or moving around an object while fixating it. The second method is the uniform view sampling. Here, the next view is picked uniformly at random. While this does not mimic infants’ viewing sequences, it provides more diversity among successive views, which is expected to aid learning.
For the object sampling we also distinguish two methods. Our default method is the random order method. Here, the order of the objects is a new random permutation during each training cycle. This corresponds to the case that the infant encounters objects randomly. The second method uses a fixed order of objects, i.e., object A is always followed by object B, etc. in all training cycles. This situation matches the neurobiological experiments by Miyashita (1988) and is expected to lead to an alignment of the latent codes of objects that are consistently seen in succession.
Training occurs in cycles. In every cycle each of the Nobj objects will be chosen exactly once — the order depending on the chosen object sampling method. Thus, a cycle consists of a total of Nobj × Nfix object views. The Nfix views for each object are determined by the chosen view sampling procedure. Several cycles of Nobj×Nfix views are stored in a buffer. For our experiments we use a batch size of 256. During learning, batches of pairs of subsequent views are sampled uniformly from the buffer. This leads to a probability 1/Nfix of sampling inter-class transitions and a probability of (Nfix−1)/Nfix of sampling intra-class transitions (compare Fig. 1). We consider an epoch to be a full run through the buffer, which is chosen to be of equal size as the underlying data set. That means that on average, every image of the data set is presented once during each epoch.

heading: 3.1.1 CONTRASTIVE LEARNING ALGORITHMS FOR CLTT

text:
The sampled sequences can be fed into a wide range of contrastive learning methods. Here we consider SimCLR (Chen et al., 2020a) and RELIC (Mitrovic et al., 2021) in which for every positive pair, all the other pairs in the batch are considered negative pairs. We also experiment with BYOL (Grill et al., 2020), that uses only positive pairs. We refer to the CLTT versions of these algorithms as SimCLR-TT, RELIC-TT, and BYOL-TT, respectively. In all cases, we use a ResNet-18 architecture (He et al., 2016) to transform the input images into 128-dimensional latent representations, which is followed by a single layer as the projection head for RELIC-TT and SimCLR-TT. For BYOL-TT we use a two layer projection head with batch normalization after the hidden layer.
SimCLR-TT. SimCLR (Chen et al., 2020a) is an effective contrastive learning approach for visual representation learning. By defining a wide range of augmentation operations and treating differently augmented images as positive samples, SimCLR has achieved state-of-the-art performance. Its groundbreaking success has triggered a surge of interest in augmentation-based self-supervised learning. For SimCLR-TT we replace the traditional augmentations with successive views as pairs defined in the previous subsection. For each positive pair, all remaining pairs in the batch are considered negative samples. The loss of SimCLR-TT is then defined as follows:
L (zi) = − log exp (sim (zi, z ′ i) /τ)∑NB
k=1,k ̸=i [exp (sim (zi, zk)) + exp (sim (zi, z ′ k))] /τ
, (1)
where zi and z′i are the latent codes of a sampled view pair, and NB is the number of pairs in a batch. Specifically, we use the cosine similarity as the similarity function sim (u, v) = u
⊤v ∥u∥∥v∥ .
For simplicity, we set the temperature parameter τ in the original SimCLR loss to be 1. In all our experiments, we use the AdamW optimizer (Loshchilov & Hutter, 2019) with a starting learning rate of 10−3, which decays by a factor of 0.3 after every 10 epochs. The batch size for training is 256 and the buffer size is determined by the size of the data set.
RELIC-TT. RELIC (Mitrovic et al., 2021) is an approach that uses an additional penalty loss compared to SimCLR. It obtains state-of-the-art results by keeping the similarity distribution of one sample invariant against differently augmented views of other samples. Incorporating this notion into the CLTT approach, we derive RELIC-TT by adding another loss term that. The loss can be described as follows:
Lp (zi) = KL (p (Y | zi) , p (Y | z′i)) , (2)
where KL is the Kullback-Leibler divergence and
p (Y = j | zi) = exp
( sim ( zi, z ′ j ))∑NB k=1 exp (sim (zi, z ′ k)) . (3)
In the definition above, zi and z′i are the latent codes of the first view and the second view of the sampled view pair. The similarities between zi and all the second views in every pair are calculated and passed to a Softmax function as shown in equation 3. The same computation is done for the second view z′i for all the other first views, resulting in totally two probability distributions denoted as p (Y | zi) and p (Y | z′i) that resembles a classification task of predicting the label Y out of totally NB classes. And then those two distributions are pulled together by minimizing the KL divergence between them. The training configuration is the same as used in SimCLR-TT.
BYOL-TT. BYOL-TT builds on the Bootstrap Your Own Latent (BYOL) architecture by (Grill et al., 2020). BYOL has been shown to outperform other contrastive learning architectures like SimCLR (Chen et al., 2020a) or MoCov2 (Chen et al., 2020b) on the ImageNet data set (Deng et al., 2009). A key advantage of the BYOL architecture is that it works without negative pairs, which sets it apart from other contrastive learning algorithms. Instead, it uses a second so-called target network. The target network receives an augmented version of the input data like the online network. It will produce a target projection and the online network tries to predict this target projection. The loss function minimizes the similarity between the target projection and the prediction of the online network. In our BYOL-TT implementation, we use the AdamW optimizer with a learning rate of 2× 10−4 which decays by a factor of 0.3 after every 30 epochs and a batch size of 256. The loss is given by:
Lθ,ξ = 2− 2 · ⟨qθ(zθ), z′ξ⟩
||qθ(zθ)||2 · ||z′ξ||2 , (4)
where qθ(zθ) is the prediction of the online network of z′ξ. θ corresponds to the weights of the online network and ξ represent the weights of the target network. The optimization will be performed with respect to θ, the weights ξ of the target network will be updated using an exponential moving average of the online network. Here we choose τ = 0.99 as target decay rate. In the original BYOL architecture, an input image x produces two augmented views v and v′ which are then shown to the target and online network. In our case no augmentations are applied to the input image, positive pairs are formed by images next to each other in the presented data timeline. Two consecutive images in this timeline will then be used as views v and v′.

heading: 3.2 DATA SETS

text:
ThreeDWorld data set. This data set was created with the ThreeDWorld (TDW) software (Gan et al., 2021). TDW was chosen, because it enables near-photorealistic rendering including depthof-field effects and the possibility of simulating physical interaction with objects (which we plan to utilize in the future). Our data set comprises twelve high quality 3D models of common household objects such as a hair brush, a hammer or scissors (compare Fig. 2A). They are arranged in a 4× 3 grid on a white floor. To simulate viewing sequences that an infant may experience while interacting with an object such as turning an object in hand or moving relative to an object while fixating it, we
render object views from different directions and distances. The individual images of the data set can then be arranged into videos simulating different viewing sequences, where an object is seen from different directions and distances. Specifically, to create the different views, we define a spherical coordinate system around the center of each object. Different views are created by changing viewing direction in terms of azimuth (from 0◦ to 350◦ in 10◦ steps), elevation (from 10◦ to 70◦ in 10◦ steps), and distance (0.3 cm to 0.6 cm in 10 cm steps). This gives rise to 1,008 views per object and a total of 12,096 images, which are down-sampled to the size of 64 by 64 pixels. We also created a test set with distinct viewing directions by shifting the azimuth and elevation by 5◦ (from 15◦ to 75◦ and from 5◦ to 355◦ in 10◦ steps). This procedure resulted in a second data set with 12,096 images. Note that due to the varying distances from the objects, sometimes not all parts of an object are visible inside the image and sometimes (parts of) other objects may be present. These appear blurry due to the simulated depth-of-field effect. By sampling different paths through this object, azimuth, elevation and distance space, we generate different viewing sequences that form the input to the CLTT algorithms presented above.
Miyashita-style data set. The Miyashita-style data set draws inspiration from the neuroscience experiments from Miyashita (1988). We adhered to the generation procedure described in (Miyashita et al., 1991) and wrote python code to generate 100 different fractals of size 64 × 64. Each of those fractals is unique and highly distinguishable from all others. For our experiments, we give each fractal its own class label and allow for a certain degree of variability to simulate fixation inaccuracies during viewing of the images. Each fixation applies a transformation with a random rotation between −10 and +10 degrees, a random rescaling between 90 and 100 % and a random translation of up to 15 % in x- and y-direction (compare Fig. 2B). The fractals are used exclusively with the fixed order procedure, i.e., there is a predefined order of fractals that is repeatedly shown to the network.
COIL-100 data set. To validate the CLTT approach on real images, we employ the Columbia Object Image Library (COIL-100) database (Nene et al., 1996). It is composed of color images of 100 objects, each viewed from 72 different directions by placing the objects on a motorized turntable making a total of 7,200 images. The objects are seen against a homogeneous black background (compare Fig. 2C).

heading: 4 RESULTS

heading: 4.1 CLTT APPROACHES REPRESENTATION QUALITY OF SUPERVISED LEARNING

text:
Results with ThreeDWorld data set. We evaluate the proposed family of CLTT methods, namely SimCLR-TT, RELIC-TT, BYOL-TT on the novel ThreeDWorld data set (Fig. 3). We also add a supervised method as baseline, which has access to the true label of each image. We focus on the random walk sampling of views and the random sequence procedure for sampling objects. We train the network for 100 epochs and vary Nfix to study its effect. In order to evaluate the quality of learned representations, we use a Linear Least Squares (LLS) classifier to test linear separability. In general, a good representation, like that resulting from supervised learning, should be linearly separable and have high LLS classification accuracy. In Fig. 3A we show the LLS classification accuracy for Nfix = 5 as a function of training epoch. Both SimCLR-TT and RELIC-TT achieve the same or even slightly better performance than the supervised approach. Figure 3B shows the final LLS classification accuracy after 100 training epochs for different values of Nfix. Noticeably, SimCLR-TT and RELIC-TT perform on par with the supervised approach with Nfix ≥ 5, while BYOL-TT achieves the best score at Nfix = 5 and larger Nfix seems to have no positive effect on BYOL-TT. Figure 3C depicts a PacMAP (Wang et al., 2021) visualization of the latent space resulting from training with RELIC-TT for 100 epochs using Nfix = 30. The objects form well separated clusters.
Results with COIL-100 data set. To evaluate CLTT on real (rather than computer rendered) images and a data set with a larger number of objects, we use the classic COIL-100 data set. Note that the COIL-100 data set does not have separate validation and test sets, thus we evaluated performance on the training set in the following experiments. This approach may have led to some over-fitting in the supervised setting, but this effect would only make it harder for our unsupervised method to
match the performance of the supervised counterpart. We compare performance of SimCLR-TT, RELIC-TT, and supervised methods for different values of Nfix. We also compare the two sampling strategies: random walk sampling where successive views are generated via a random walk in the space of viewing directions and uniform sampling where successive views are picked uniformly at random across all possible viewing directions. Figure 4A shows the LLS accuracy of the different algorithms and sampling strategies as a function of the number of training epochs for Nfix = 30. The SimCLR-TT method outperforms RELIC-TT. Furthermore, we observe that the uniform sampling leads to better results than the random walk sampling. This is not surprising, as it creates more diversity in the training data by allowing for very different views of an object to be grouped as a positive pair during contrastive learning. Also, although learning is somewhat slower, the performance of SimCLR-TT and RELIC-TT with uniform sampling approaches that of fully supervised learning. Figure 4B compares the final LLS classification accuracy of the algorithms after 50 training epochs for different values of Nfix. The performance improves monotonically with Nfix as expected and approaches that of the fully supervised setting. Figure 4C visualizes the clustering of latent representations with PacMAP for RELIC-TT with Nfix = 30 and the random walk sampling procedure. The 100 different objects have formed distinct clusters in the latent space. Finally, in Appendix A.1, we compare uniform sampling and random walk sampling for the three methods with Nfix = 2 and Nfix = 10. As expected, the results show that uniform sampling achieves better performance.

heading: 4.2 CLTT ALIGNS LATENT CODES OF SUCCESSIVELY VIEWED OBJECTS

text:
Results with Miyashita-style data set. To relate our framework to biological findings we use the Miyashita-style data set combined with our SimCLR-TT approach. We train the network for 106 stimuli presentations (100 epochs, buffer size = 10,000) and vary Nfix. Here, the buffer-size is larger than the number of fractals, because the data set is dynamically generated using the aforementioned fixations. In line with results from neuroscience, fractals that were presented in succession evoke more similar activations in the latent space than fractals that are far apart in the predefined sequence. Fig. 5A depicts the mean cosine similarity between a fractal’s latent representation and that of its two n-th nearest neighbors along the sequence (in the positive and negative time direction). Note that neighbor zero has a similarity of one, as it is de-facto the same activation pattern. The curves for all values of Nfix display the property of a downward slope that is clearly separated from the baseline (dashed lines). This indicates that over time not only immediate neighbors, but also more distant fractals become associated. In fact for Nfix = 2 we see significant deviations (p < .01, twosided Kolmogorov-Smirnov two-sample test) for the nine next neighbors before merging with the baseline. The number of deviating neighbors shrinks with increasing Nfix, but significant effects still can be observed. This experiment illustrates a fundamental property of CLTT that can be directly
related to biological findings. We also compare our results to supervised learning, which can solve the classification of 100 fractals, but the resulting latent representations do not display any structure of temporal associations and thus do not differ significantly from its baseline (not shown).
Results with ThreeDWorld data set. We tested if the alignment of latent representations of objects that are consistently shown in succession could also be observed with the TDW data set. For this we sampled objects using the fixed order procedure, i.e., the objects were always seen in the same sequence order. We focused on SimCLR-TT for this experiment. Figure 5B replicates the effect from the Fractals data set (compare Fig. 5A). Figure 5C shows the equivalent experiment for the COIL-100 data set. The fixed order aids classification and SimCLR-TT achieves excellent classification performance for different values of Nfix. Thus, the network is able to learn good representations of the input data even with low values of Nfix when the order in which the objects are shown to the network is fixed.

heading: 5 DISCUSSION

text:
We have developed a general framework for contrastive learning through time (CLTT). CLTT emulates viewing sequences as may be experienced by infants and uses a temporal contrastive loss that maps subsequent inputs occurring during such interactions onto close-by latent representations (“close in time, will align”). To systematically investigate this approach, we have created a new data set using the ThreeDWorld environment (Gan et al., 2021), allowing us to flexibly simulate different kinds of viewing scenarios in a near photo-realistic fashion. We also validated our approach using a new fractal-like data set inspired by biological experiments and the classic COIL-100 computer vision data set. We have demonstrated that CLTT can approach the quality of representations learned using full supervision. For this it is important that intra-object transitions (successive fixations fall on the same object) dominate over inter-object transitions (successive fixations fall on different objects). We have also shown that CLTT produces effects reminiscent of classic biological findings showing that inputs that occur close in time are mapped onto close-by latent representations by the brain.
Our work has a number of limitations. First, while the use of TDW gives us perfect control over all parameters of viewing sequences including scene geometry, sequence of views, lighting conditions, etc., the approach needs to be validated in the real world. Using the COIL-100 data set has been a first step in this direction. To address this more thoroughly, future work could consider first person videos from infants wearing head-mounted cameras (Bambach et al., 2018; Orhan et al., 2020). Second, we have assumed well-separated objects without major occlusions in front of uniform backgrounds. Learning in a cluttered environment is expected to be harder, but it may benefit from foveated vision and additional attentional and figure-ground separation mechanisms, which we plan to incorporate in future work. Third, our eye movement model, which kept gaze on the same object for a certain number of fixations before redirecting it elsewhere, is overly simplistic. In the future, it will be interesting to use more refined models that better reflect (measured) gaze sequences of children and adults. Indeed, it is an interesting question what gaze sequences are particularly beneficial for learning and if and how infants and artificial vision systems can optimize viewing sequences to maximize their own learning progress. This links CLTT to research on intrinsic motivation and (artificial) curiosity. Exploring these issues will bring us closer to building artificial vision systems that can learn truly autonomously.

heading: ACKNOWLEDGMENTS

text: Removed for double blind review.

heading: A APPENDIX

text:
A.1 COIL-100: ADDITIONAL EXPERIMENTAL RESULTS
In this section, we supply additional results on the COIL-100 data set. Figure A.1. compares the two view sampling methods for the different algorithms for Nfix = 2 and Nfix = 10. It shows improved LSS accuracy for the uniform sampling strategy. This is not suprising, since it creates more diverse views than the random walk sampling strategy. It also shows that Nfix has a larger influence on the random walk sampling.

title: CONTRASTIVE LEARNING THROUGH TIME


summaries: The paper addresses multi-goal reinforcement learning. It presents empirical results with a variation of an existing algorithm, Hindsight Experience Replay (HER). Specifically, the paper uses HER alongside AlphaZero.

summaries: This paper presents AlphaZeroHER, an extension of the AlphaZero learning-informed Monte Carlo Tree Search algorithm in which the ideas of Hindsight Experience Replay (HER) are applied to augment training and therefore better support goal-directed planning tasks. Consistent with the general HER procedure, the approach generates new data under the assumption that the goal was one of a set of sampled "subgoals", requiring that that the reward and target policy be recomputed. The target policy is chosen to be the empirical policy achieved during the episode, for though it is not optimal for the new goal, it did indeed reach the subgoal. The authors demonstrate performance on a handful of goal-directed planning tasks—including BitFlip, navigation, and a quantum compiling task—on which they show improved performance over AlphaZero without the addition of HER.

summaries: The authors discuss the impact of Monte Carlo Tree Search (MCTS) algorithms.  MCTS allows us to roll out trajectories using state value estimates to determine local actions, however computational cost can be high. This means that the approach is prohibitive for large problem spaces.  RL seeks to learn a control policy that generalizes well over the state space. This can be challenging and MCTS algorithms can help with this.  In goal reaching problems the agent takes as input the current state of the env as well as the goals state.  The only trajectories that confer positive reward are those where the goal is reached. RL can struggle here as the rewards are sparse due to the success criteria.  More informative reward functions can be used (e.g. distance to goal) but this isn't always possible.  Hindsight Experience Replay (HER) is applied to offline RL algorithms to improve sample efficiency where a replay buffer is maintained over retained trajectories and a set of sub-goals are defined over visited states with returns applied accordingly.  The authors propose to apply HER to AlphaZero to solve goal directed tasks and thereby avoid computationally intense tasks. They evaluate the approach against a set of simulated environments and compare to AlphaZero, including a novel Quantum compiling environment.  Much of the challenge in solving games like Go and Chess comes down to the size of the state space.  AlphaZeroHER works by sampling new sub-goals from already visited states and thus avoiding both the high computational cost involved in tree re-weighting and also the problem of sparse rewards.   This is done by retracing episodes and sample M subgoals from a trajectory of length T and training the policy and value networks on these hindsight inferred goals.  Since AlphaZero is on on-policy the policies used during play are retained when computing updates from the sub-goal rollouts which alleviates the computational burden.  The authors show that AlphaZeroHER outperforms AlphaZero over a number of simulated environments where the latter often fails to achieve learning much while the former achieves strong results.

summaries: For the AlphaZero approach, the rewards of goal-directed planning environments are too sparse to learn efficiently. To solve this problem, the authors proposed the AlphaZeroHER method by combining AlphaZero with Hindsight Experience Replay(HER) to enable AlphaZero agents to learn in goal-directed environments. The experiments showed that AlphaZeroHER is better than AlphaZero on BitFlip, 2D Navigation Task, 2D Maze and Quantum Compiler environments.

abstractText: We consider the problem of goal-directed planning under a deterministic transition model. Monte Carlo Tree Search has shown remarkable performance in solving deterministic control problems. By using function approximators to bias the search of the tree, MCTS has been extended to complex continuous domains, resulting in the AlphaZero family of algorithms. Nonetheless, these algorithms still struggle with control problems with sparse rewards such as goal-directed domains, where a positive reward is awarded only when reaching a goal state. In this work, we extend AlphaZero with Hindsight Experience Replay to tackle complex goal-directed planning tasks. We demonstrate the effectiveness of the proposed approach through an extensive empirical evaluation in several simulated domains, including a novel application to a quantum compiling domain.

authors:
Marcin Andrychowicz
Filip Wolski
Alex Ray
Jonas Schneider
Rachel Fong
Peter Welinder
Bob McGrew
Josh Tobin
OpenAI Pieter Abbeel
Wojciech Zaremba

title: Hindsight experience replay

venue: Advances in Neural Information Processing Systems,

authors:
Peter Auer
Nicolò Cesa-Bianchi
Paul Fischer

title: Finite-time analysis of the multiarmed bandit problem

venue: Mach. Learn.,

authors:
C.B. Browne
E. Powley
D. Whitehouse
S.M. Lucas
P.I. Cowling
P. Rohlfshagen
S. Tavener
D. Perez
S. Samothrakis
S. Colton

title: A survey of monte carlo tree search methods

venue: IEEE Transactions on Computational Intelligence and AI in Games,

title: Multitask learning

authors:
Shantanu Debnath
Norbert M Linke
Caroline Figgatt
Kevin A Landsman
Kevin Wright
Christopher Monroe

title: Demonstration of a small programmable quantum computer with atomic qubits

authors:
Vikas Dhiman
Shurjo Banerjee
Jeffrey Mark Siskind
Jason J. Corso

title: Floyd-warshall reinforcement learning learning from past experiences to reach new goals

authors:
M. Enzenberger
M. Müller
B. Arneson
R. Segal

title: Fuego—an open-source framework for board games and go engine based on monte carlo tree search

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: Proceedings of the 34th International Conference on Machine Learning,

authors:
Chelsea Finn
Kelvin Xu
Sergey Levine

title: Probabilistic model-agnostic meta-learning

authors:
Ronan Fruit
Matteo Pirotta
Alessandro Lazaric
Emma Brunskill

title: Regret minimization in mdps with options without prior knowledge

authors:
Dibya Ghosh
Abhishek Gupta
Sergey Levine

title: Learning actionable representations with goal-conditioned policies

authors:
Marek Grzes
Daniel Kudenko

title: Theoretical and empirical analysis of reward shaping in reinforcement learning

venue: In 2009 International Conference on Machine Learning and Applications,

authors:
Nozomu Ikehata
Takeshi Ito

title: Monte-carlo tree search in ms. pac-man

venue: IEEE Conference on Computational Intelligence and Games (CIG’11),

authors:
Tom Jurgenson
Or Avner
Edward Groshev
Aviv Tamar

title: Sub-goal trees - a framework for goal-based reinforcement learning

authors:
Levente Kocsis
Csaba Szepesvári

title: Bandit based monte-carlo planning

venue: In In: ECML-06. Number 4212 in LNCS,

authors:
D Leibfried
E Knill
Christian Ospelkaus
David J Wineland

title: Transport quantum logic gates for trapped ions

venue: Physical Review A,

authors:
Norbert M Linke
Dmitri Maslov
Martin Roetteler
Shantanu Debnath
Caroline Figgatt
Kevin A Landsman
Kenneth Wright
Christopher Monroe

title: Experimental comparison of two quantum computing architectures

venue: Proceedings of the National Academy of Sciences,

title: Basic circuit compilation techniques for an ion-trap quantum machine

venue: New Journal of Physics,

authors:
Stephen McAleer
Forest Agostinelli
Alexander Shmakov
Pierre Baldi

title: Solving the rubik’s cube with approximate policy iteration

authors:
Lorenzo Moro
Matteo G.A. Paris
Marcello Restelli
Enrico Prati

title: Quantum compiling by deep reinforcement learning

venue: Communications Physics,

authors:
Soroush Nasiriany
Vitchyr Pong
Steven Lin
Sergey Levine

title: Planning with goalconditioned policies

title: A simple formula for the average gate fidelity of a quantum dynamical operation

venue: Physics Letters A,

authors:
Michael A Nielsen
Isaac Chuang

title: Quantum computation and quantum information

authors:
Giambattista Parascandolo
Lars Buesing
Josh Merel
Leonard Hasenclever
John Aslanides
Jessica B. Hamrick
Nicolas Heess
Alexander Neitz
Theophane Weber

title: Divide-andconquer monte carlo tree search for goal-directed planning

authors:
Lerrel Pinto
Abhinav Gupta

title: Learning to push by grasping: Using multiple tasks for effective learning

title: Multi-armed bandits with episode context

venue: Annals of Mathematics and Artificial Intelligence,

authors:
Nicholas J Russell
Levon Chakhmakhchyan
Jeremy L O’Brien
Anthony Laing

title: Direct dialling of haar random unitary matrices

authors:
Tom Schaul
Daniel Horgan
Karol Gregor
David Silver

title: Universal value function approximators

venue: Proceedings of the 32nd International Conference on Machine Learning,

title: Evolutionary principles in self-referential learning. on learning now to learn: The meta-meta-meta...-hook

venue: Diploma thesis, Technische Universitat Munchen, Germany,

title: Optimal ordered problem solver

title: Gödel Machines: Fully Self-referential Optimal Universal Self-improvers, pages 199–226

authors:
David Silver
Thomas Hubert
Julian Schrittwieser
Ioannis Antonoglou
Matthew Lai
Arthur Guez
Marc Lanctot
Laurent Sifre
Dharshan Kumaran
Thore Graepel
Timothy P. Lillicrap
Karen Simonyan
Demis Hassabis

title: Mastering chess and shogi by self-play with a general reinforcement learning

authors:
David Silver
Julian Schrittwieser
Karen Simonyan
Ioannis Antonoglou
Aja Huang
Arthur Guez
Thomas Hubert
Lucas Baker
Matthew Lai
Adrian Bolton
Yutian Chen
Timothy Lillicrap
Fan Hui
Laurent Sifre
George van den Driessche
Thore Graepel
Demis Hassabis

title: Mastering the game of go without human knowledge

authors:
Richard S Sutton
Andrew G Barto

title: Reinforcement learning: An introduction

venue: MIT press,

authors:
Emanuel Todorov
Tom Erez
Yuval Tassa

title: Mujoco: A physics engine for model-based control

venue: In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems,

heading: 1 Introduction

text:
Monte Carlo Tree Search (MCTS) (Browne et al., 2012) algorithms have shown outstanding results in solving sequential decision-making problems, especially in deterministic transition tasks, such as games. MCTS planners use a forward environment model to build a search tree, estimate the value of each action in the current state, and execute the best-estimated one, respectively. Such a procedure allows finding a “local” solution to the decision problem in every decision step by sampling trajectories of possible future policies using the forward model. Although providing local solutions is advantageous in some contexts, it comes at a high computational cost since acting in the environment requires interleaved planning phases and possibly large search trees. These high computational costs have been a barrier in applying MCTS to larger problems, especially those with long planning horizons and huge tree branching factors (number of actions). However, MCTS does not require a training phase and can be deployed immediately.
Reinforcement Learning (RL) (Sutton et al., 1998), on the other hand, aims to find a global solution to the control problem by learning a policy that performs adequately in the whole state space. While this may seem a more desirable outcome, it can often be hard to produce a policy that generalizes satisfactorily across different state regions. For this reason, MCTS algorithms have achieved tremendous success in a wide range of tasks (Borsboom et al.; Enzenberger et al., 2010; Ikehata and Ito, 2011). The AlphaZero (Silver et al., 2016) family of algorithms made it possible to use sequential planners like MCTS in more challenging environments, such as the game of Go, where the AlphaGo agent defeated the world champion, achieving super-human performance. AlphaGo was in turn defeated by the AlphaZero, a version of the algorithm without any heuristic related to the game of Go. AlphaZero combines MCTS with the ability of RL algorithms to generalize across the state-action space by keeping a parametrized policy and value network. Specifically, the policy network biases the exploration during the tree search, and the value network estimates the value of the states corresponding to the search tree leaves, replacing the trajectory-based evaluation usually performed with an ad-hoc evaluation policy called rollout policy. On the other hand, the MCTS algorithm acts as a policy improvement step. It takes as input the current state, as well as the policy and value networks, therefore improving the parametrized policy and generating the samples used to train the networks in a supervised manner. Although a tree search is still required, the deployment is cheaper since it usually requires a humbler
planning budget, thanks to the policy and value networks which bias the search by making it more efficient. The algorithm has been successfully applied to different games such as Go, Chess, and Shogi (Silver et al., 2017a) without game-specific heuristics. However, despite its success, the algorithm suffers from a high sample complexity, especially prominent in tasks with sparse reward functions, such as goal-directed planning.
In goal-directed tasks, the agent aims to reach a goal state, and in general, the policies take both the current state of the environment and the goal state as input. Usually, the actual reward function in these problems is zero for any transition except the one to the goal state, which gives a positive reward. RL algorithms struggle to optimize sparse reward functions since it might be hard to reach goal states, or even practically impossible during exploration if the task is quite challenging. Therefore, there is not a reward signal to guide the exploration. While in practice, in specific tasks, it is possible to use more informative reward functions, such as a distance from the goal state, such a choice is not possible for every task. Furthermore, it might also lead to sub-optimal solutions since a reward function based on a state distance might generate local-optima in the policy space (Grzes and Kudenko, 2009). Hindsight Experience Replay (HER) (Andrychowicz et al., 2017) is a straightforward method to tackle the problem of sparse-reward functions in goal-directed tasks. HER can be used with any off-policy RL algorithm to extend the training dataset for the value networks. Practically, whenever the goal state is not reached during a training episode, the states visited during the episode are used as alternative goal states and are fed to the network during training. It allows reward signals to be given to the value networks and generalize them to reach the input goal state.
In this work, we consider the problem of applying HER to AlphaZero to tackle goal-directed tasks. We provide a scheme that does not involve computationally heavy tree re-weighting procedures or high additional computational costs. Finally, we benchmark the method with simulated environments, and we show a novel application to quantum compiling, where it is extremely hard to find unitary gate sequences from a set to approximate arbitrary single-qubit unitary operators.

heading: 2 Preliminaries

heading: 2.1 Goal-Directed Reinforcement Learning

text:
In this work, we focus on goal-directed Reinforcement Learning problems. In such setting, an autonomous agent interacts with an environment to maximize the sum of observed reward signals. Formally, in deterministic transition models, the environment consists of a state space S, a set of goal states G (that can also be equal to S), an action space A, a goal-state dependent reward function r : S × A × G → R, a transition model P : S × A → S, a probability distribution over S for the initial state s0 ∼ µ, and a probability distribution over G for the goal state sg ∼ ν. The behavior of the agent is described by a Markovian stationary goal-dependent policy, π : S×G → ∆(A), which takes as input the current state s and the goal state sg, and outputs a probability distribution over the actions in A. At the beginning of each episode, an initial state s0 ∼ µ and a goal state sg ∼ ν are sampled. Then, at time step t, the agent observes the current state st, selects an action at ∼ π(st, sg), observes the next state st+1 = P(st, at) and it gets the reward signal rt = r(st, at, sg).
The goal of the agent is to maximize the expected return E[Rt] defined as the expectation of the discounted sum of future rewards Rt = ∑∞ i=t γ
i−tri taken over the initial state and goal state. Given a policy π, the value of each state is encoded by the value function V π(s, sg) = Eat∼π[R0|s0 = s]. Similarly, the action-value function is defined for each stateaction pair, conditioning on the first action of the trajectories, Qπ(s, a, sg) = Eat∼π[R0|s0 = s, a0 = a]. The goal of maximizing the return can be expressed as finding an optimal policy, π∗ = argmaxπ V π(s, sg), ∀(s, sg) ∈ S × G.

heading: 2.2 Monte Carlo Tree Search

text:
We briefly introduce the Monte Carlo Tree Search (MCTS) family of algorithms, which combine tree-search algorithms with Monte Carlo sampling to build a search tree iteratively. We focus on the most popular algorithm in the MCTS family, i.e., the upper confidence bound for trees (UCT) (Kocsis and Szepesvári, 2006). More precisely the general MCTS algorithm consists of four stages (Browne et al., 2012):
Selection. In the selection stage, the selection policy is applied from the root of the search tree recursively until an unexpanded leaf node is reached.
Expansion. In the expansion stage, one or more successors to the previously-found unexpanded node are generated according to the actions available in the node.
Evaluation. The newly generated nodes are evaluated, generally through a simulation (rollout) using a default policy.
Backpropagation. In the last stage, the rewards collected during the selection and evaluation phase are backed up following the previously visited tree branch.
UCT performs the selection phase using the Upper Confidence Bound (UCB1) (Auer et al., 2002) bandit algorithm. Specifically, each node of the search tree maintains statistics related to the future value of each action, including the number of visits, the number of times an action is performed, and the total sum of the returns observed, used to estimate the mean return. Using such statistics UCB1 chooses the next action to perform, an, according to
an = argmax i=1..K B(ai) = Ri,Ti(n−1) + C
√ 2 log n
Ti(n− 1) , (1)
where K is the number of actions, C is a constant that regulates the exploration-exploitation trade-off, Ti(n− 1) is the number of times action i has been played up to time n− 1 and Ri,Ti(n−1) is the average payoff observed from arm i. UCT recursively updates the values of the nodes from the leaf to the root of the tree, during the backup phase. The algorithm is proved to be consistent, i.e., it converges to the optimal policy in the limit, and asymmetric, which means that it iteratively builds the search tree by favoring the most promising regions of the tree while still giving a probability of selection to all branches. Such propriety is paramount in some applications where the search tree is extremely large.

heading: 2.3 AlphaZero

text:
AlphaZero (Silver et al., 2017a) bridges the gap between RL and MCTS by maintaining a parametric policy, πθ and value function vρ. The policy and value networks are provided as input to the MCTS algorithm to bias the tree search. In contrast, the visit counts in the tree’s root are used to build the targets for the supervised training of the policy network.
Compared to general MCTS, the selection and evaluation phases are modified. The former phase uses the policy πθ, to bias the exploration according to the policy recommendations. Furthermore, AlphaZero replaces the classic UCT algorithm with PUCT (Rosin, 2011) and performs the selection according to:
an = argmax i=1..K B(ai) = Ri,Ti(n−1) + Cπθ(s, ai)
√ n
1 + Ti(n− 1) . (2)
By multiplying the PUCT confidence interval with the probability given to ai by πθ, AlphaZero initially prefers actions with high probability and a low visit count but asymptotically prefers actions with high values. In the latter phase, AlphaZero evaluates the leaf nodes using the estimate provided by the value network vρ, instead of performing expensive simulations with a default rollout policy. The training targets of the value network are the actual returns collected during acting. More formally, at each time step t, AlphaZero performs M search iterations of MCTS, starting from the current environment state st and using πθ during the selection phase, and vρ during the evaluation of the leaves. After the search phase, the policy targets pt are constructed using the visit counts at the root of the tree:
pt(ai) = Nt,i∑ j Nt,j ∀i = 1, . . . ,K, (3)
where Nt,i is the visit count of the i-th action in the search tree at step t, and K is the number of actions. Then at is sampled according to pt and is executed observing the next state st+1 and the reward signal rt. In practice, pt is often constructed as a greedy policy over the action counts, only executing the most explored one. At the end of each episode, the collected rewards are used to build the value network targets Rt. The triples (st,pt, Rt) are added to a replay buffer D used during training of the networks. In the original AlphaZero paper, the policy and value networks share the parameter vector θ and AlphaZero minimizes:
E (s,p,R)∼D
[ (R− vθ(s))2 − pT log πθ(s) + c∥θ∥2 ] , (4)
where c controls the amount of L2 regularization.

heading: 2.4 Hindsight Experience Replay

text: Hindsight Experience Replay (Andrychowicz et al., 2017) is a method of extending off-policy RL algorithms to improve sample efficiency even in the presence of sparse reward functions. HER requires parameterizing the reward, policy, and value as a function of the current and the goal state. The basic idea behind HER is to extend the replay buffer B after each episode {s0, s1, . . . , sT } with the returns calculated based on a set of subgoals. While the main goal influences the agent’s actions during training, it does not influence the state transitions. Consequently, we can generate additional training samples by considering a subset of the states visited during the episode as subgoals. This is extremely beneficial in cases with sparse rewards, such as a reward function of the type r(st, at, sg) = 1(st+1 = sg), where reward signals would be null until the goal state is visited by chance. However, HER enables the reward signals to be generalized across the state space.

heading: 3 AlphaZero with Hindsight Experience Replay

text: This section describes the AlphaZeroHER algorithm. AlphaZero has been successfully applied to challenging games such as Go and Chess with outstanding results. The complexity of these games stands in the vast state-action spaces and the highly sparse reward function, since the agents will only know at the end of the game whether they have won (a reward of +1), lost (a reward of −1) or drawn (a reward of 0). Although in the context of Temporal Difference (TD) (Sutton et al., 1998) algorithms, Chess and Go fall under the definition of sparse reward, when considering returns observed at the end of the episode (Monte Carlo returns), such games have a clear reward function: the game’s result is either a win, a loss or a draw. This reason may give the impression that AlphaZero doesn’t suffer in sparse reward setting. However, in goal-directed planning, the Monte Carlo returns are often sparse, in the sense that the whole episode might finish without a reward signal. This problem was also mitigated in the original AlphaGo Zero paper (Silver et al., 2017b), where the authors employed ad-hoc board evaluators to compute the Monte Carlo returns when episodes of Go were interrupted because they were too long. Due to the criticality of sparse rewards, we extend AlphaZero with HER to tackle goal-directed tasks.

heading: 3.1 AlphaZeroHER

text:
The basic idea of AlphaZeroHER, is to extend AlphaZero by using a goal-directed policy and value network and injecting HER into such a setting. Exploiting a goal-directed policy and value network in AlphaZero is effortless since the experience samples also include the goal state sg. However, AlphaZero is not an off-policy algorithm since the value network is trained with the returns collected while playing the MCTS augmented policy. Moreover, it is not straightforward how to evaluate the new policy when considering a new goal st ≠ sg without introducing additional prohibitive computational costs and tree re-weighting procedures. Ideally, we aim at estimating a new policy conditioned on a subgoal st ̸= sg. However, estimating such a policy requires building an additional tree since the policy targets in AlphaZero are a function of the action counts in the tree’s root node, and this with an obvious additional computational cost. An alternative approach could keep the original goal’s search tree and re-weight the statistics in the nodes conditioned on the reward function for
the new goal st. However, such a procedure would require at least traversing the whole tree once, which would be computationally prohibitive for a large search-tree. Such problems represent the main obstacle toward introducing HER.
We propose a procedure that extends AlphaZero with HER without adding high computational costs. The basic idea is to neglect its on-policy nature generating additional training samples at the end of each episode by sampling additional subgoals from the visited states. In fact, even though the MCTS augmented policy of AlphaZero did not reach the goal state, it successfully reached all the states visited during the episode. More precisely, we employ HER after finishing an episode of length T and having generated the sequence of states, reward and policies, {st,pt, rt}Tt=1. The episode is retraced so that at each state st, M subgoals are sampled from future visited states, {si}Ti=t+1. After selecting the subgoals states for state st, we need to compute these states’ policy and value targets. This task is not straightforward since AlphaZero is an on-policy algorithm. If we computed, in some way, a different policy target from the actual policy played pt, these would generate a different sequence of state and rewards after timestep t, which are not available. We could use the built tree to evaluate these returns related to the subgoals, but these would come with heavy tree-reweighting schemes for an already computationally heavy algorithm as AlphaZero. For this reason, we select as additional policy targets the policies played during the episode pt since, although these are not the optimal policies that the MCTS agent would have played if the subgoal states were the goal during the search, they successfully reached the alternative goal states. Therefore, these samples still represent an improvement over the current policy pθ, which can be used as policy improvement steps. Finally, we compute the new returns based on the states visited only by computing the new reward signals for each new subgoal. Such procedure is done once for each episode and involves negligible additional computation. We call this method AlphaZeroHER. Algorithm 1 in the appendix shows the pseudocode of the proposed procedure.

heading: 3.2 Motivating Example

text:
To highlight the AlphaZero criticality in sparse reward environments, we consider a simple BitFlip domain from (Andrychowicz et al., 2017), described in detail in Section 5. In this domain, the goal is to modify a long series of n bits to reach the desired bit configuration. While it might be easy to achieve the goal configuration by applying a random policy when considering few bits only, it is practically impossible reaching the goal state if the bit length is increased.
Figure 1 shows the performance of plain AlphaZero in the bit-flip environment, where we have plotted the expected return and the percentage of solved episodes as a function of the training epochs for three different scenarios. While AlphaZero can consistently solve an “easy” scenario of 10 bits achieving almost perfect performance, it struggles with a modest increase in the number of bits, dramatically failing to solve the task with 18 bits.

heading: 4 Related Works

text:
Goal-Directed Reinforcement Learning has been extensively studied over the years. The optimization of multiple goals has been largely investigated in multi-goal policy optimization, curriculum learning, goal-directed planning, and multiple-task off-policy learning.
In the context of universal value function approximators, in (Schaul et al., 2015) the authors consider the problem of approximating multiple value functions in a single architecture. In this line of work, various works study the problem of compact representations of multiple tasks (Dhiman et al., 2018; Ghosh et al., 2018). In such context, the use of sub-goals (intermediate states between the current state and the goal state) have been studied to accelerate learning and generalize over the state-space (Nasiriany et al., 2019; Jurgenson et al., 2020). In (Parascandolo et al., 2020), the authors move the problem of goal-directed planning from the space of possible policies to the problem of finding suitable sub-goals. While this has some advantages in certain situations, it cannot be applied in large state spaces since the complexity of the algorithm scales linearly with the number of states. Approximate value iteration has also been used with great results to solve the Rubic’s cube with a goal-directed framework in (McAleer et al., 2019)
In the context of policy search, (Pinto and Gupta, 2016) and (Caruana, 1997) aim to learn policies to solve multiple tasks simultaneously. Meta-learning has also been extensively studied in recent years and can be seen as closely related to multi-task learning. In metalearning, a meta-learner is trained to learn swiftly in ever-changing tasks to adapt to learning in new untested tasks quickly. While meta-learning has been investigated early in the literature (Schmidhuber, 1987; 2007), recent work has shown impressive results in the context of Deep RL (Finn et al., 2017; 2018). Hierarchical Reinforcement Learning is also closely related to meta-learning (and our work). Here the goal is to (automatically) learn to perform multiple tasks by splitting the main problem into sub-tasks (Schmidhuber, 2002; Fruit et al., 2017). This is also closely related to the options framework.

heading: 5 Experiments

text: In this section, we provide an experimental evaluation of AlphaZeroHER on simulated domains, including a novel application on a quantum compiling task, modeled as a deterministic goal-directed MDP. We ran each experiment in a single multi-core machine, with no GPUs. In the following, “search iteration” refers to a single application of the 4 MCTS phases. Details on the hyperparameters employed are given in Appendix B.1 together with some additional experiments including a comparison with DQN+HER.

heading: 5.1 BitFlip

text: We consider a BitFlip environment where the individual bits of a long series of n bits are changed to reach a desired final configuration. More precisely, the state space is S = {0, 1}n, as well as the goal space G. The action space A = {0, 1, . . . , n − 1} specifies which bit of the current state changes from 0 to 1 or vice-versa. At the beginning of each episode, the starting bits and goal state are set randomly with uniform measures over the state space. We use a “sparse” reward of −1 for each transition, unless the goal state is reached. We tested such an environment as a motivating example for the application of HER in AlphaZero and a benchmark test since increasing the number of bits can vary the task’s difficulty sensibly. In all the runs in BitFlip, we use 20 neurons for the shared layer, 8 neurons for the policy layer and 4 for the value layer. The network hyper-parameters were not optimized. Figure 2 reports the performance of AlphaZeroHER in the scenario of 70 bits for different number of subgoals sampled (0 subgoals refers to plain AlphaZero). While AlphaZero struggles with 12 bits and fails with 18 bits, AlphaZeroHER manages to achieve great results in the case of 70 bits. Moreover, the agent achieves better performance by increasing the number of additional goals, getting perfect performance by using 4 subgoals only.

heading: 5.2 2D Navigation Task

text:
In this section, we consider a 2D navigation task built on top of the Mujoco (Todorov et al., 2012) robotics simulator, called Point. The purpose of this experiment is to observe the performance of AlphaZero and AlphaZeroHER in a more challenging task, that requires a fair amount of exploration. More precisely, the agent’s goal (orange ball) has to reach the goal state highlighted by the green rectangle as shown in Figure 4. The task is made more challenging by the presence of a wall in the center of the environment. At the beginning of each episode, the starting state and the goal state are sampled on the left and right sides of the wall, respectively. The agent observes its current position and its current velocities in both directions and the coordinates of the goal state, while the action space is represented as control over two actuators of the agent. Although the original action space is continuous over the domain [−1, 1]2, we restricted the space to 9 discrete actions, representing the center (no action) and 8 points on the circle centered at action (0, 0) with radius 1. The reward function is −1 at each step, making the optimal policy the shortest path that reaches the green rectangle while circumventing the wall.
We use a simple MLP with 20 neurons for the shared layer, 10 neurons for the policy layer and 4 for the value layer. Figure 3 shows the results of the experiments in this domain. We use a large horizon of 200 steps, after which we interrupt if the goal state was not reached. While AlphaZero fails to solve the environment, only reaching the goal state in 10% of the episodes, by applying HER we manage to solve most of the episodes, with only sampling 2 additional goals each episode of experience.

heading: 5.3 2D Maze

text:
This section considers an environment of 2D procedurally generated mazes whose structure changes at each episode, as shown in Figure 4. This experiment aims to test the algorithm’s performance in a challenging image task, where Convolutional Neural Networks represent the policy and value space. At each episode, the agent is spawned on a free cell (shown in red) and moves to reach the goal cell (shown in green). The action space consists of four
directional movements, which move the agent to one of the adjacent cells. However, if the action points towards a wall, the agent does not move. The reward function employed in this environment is a constant reward of −1, prompting the agent to find the shortest path to the goal. The state-space corresponds to a 2D image of the complete maze.
We employ the same network architecture in all the experiments, consisting of a 3-Layer CNN, with a kernel size of 3, a Layer Normalization after each convolutional layer, and strides of [1,1,2]. The policy and value network heads have two additional fully connected layers of 128 and 64 neurons each. We run experiments in 10x10 mazes, using an horizon of 60 steps, after which we interrupt if the goal state was not reached. Figure 5 shows the results of the experiments in this domain. We can see that AlphaZeroHER clearly outperforms plain AlphaZero in this environment, although it does not itself achieve a perfect score. We attribute this low general performance to the fact that the hyperparameters of the training process were not optimized, and in an image based task, with CNNs as policy and value space, the architecture and training procedure is crucial. Nonetheless, AlphaZeroHER manages to substantially clearly improve over plain AlphaZero with only 2 additional goals.

heading: 5.4 Quantum Compiler Environment

text:
Gate-model quantum computers achieve quantum computation by applying quantum transformations on quantum physical systems called qubits (Nielsen and Chuang, 2002). Due to hardware constraints and quantum disturbances (Linke et al., 2017; Maslov, 2017; Leibfried et al., 2007; Debnath et al., 2016), quantum computers require compilers to approximate any quantum transformations as ordered sequences of quantum gates that can be applied on the hardware. In this work, we employ AlphaZeroHER to address the problem of quantum compilation. We consider a Quantum Compiler (QC) environment consisting of a sequence Un = ∏n j=1 Aj of quantum gates Aj that starts empty at the beginning of each episode, as fully described in Moro et al. (2021). Such sequence is built incrementally at each time-step by the agent, choosing from a finite set of quantum gates B corresponding to
the action space. More specifically, we chose the base composed of six finite rotations, i.e B = ( Rx̂(± π128 ), Rŷ(± π 128 ), Rẑ(± π 128 ) ) .
The goal of the agent consists to approximate a single-qubit unitary transformation U that is chosen at each episode from Haar matrices. Pictorially, sampling Haar unitary matrices can be seen as choosing a number from a uniform distribution (Russell et al., 2017). The observation used as input at time-step t corresponds to the vector of the real and imaginary parts of the elements of the matrix On, where U = Un ·On. Such representation encodes all the useful information required to achieve the task, i.e the unitary transformation to approximate U and the current sequence of gates. We exploited average gate fidelity (AGF) (Nielsen, 2002) as a metric to evaluate the distance between the target gate U and the current sequence of gates Un. The task is solved whenever the agent reaches a distance equal to or greater than 0.99 AGF. The base of gates B allows defining a distance-based reward, which allows solving the problem with relative ease, although it leads to sub-optimal solutions as shown in Moro et al. (2021). However, in this work, we employ a sparse reward equal to −1 regardless of the action performed by the agent. For such reason, the task is very challenging since a high number of steps are required to approximate Haar unitary targets on average.
In all the experiments, we use the same network architecture, consisting of a simple MLP with one initial layers of 16 hidden neurons. The policy and value network heads have an additional layer of 8 and 4 hidden neurons respectively. Figure 6 shows the results of the experiments in the QC task. In this task, the planning horizon is substantially longer than in previous environments. We interrupted the episodes at 300 steps since a perfect policy achieves an average episode length of 180 steps, and 95% of the solution can be achieved using less than 200 steps (Moro et al., 2021). AlphaZero shows a slow performance improvement, but after 100 training epochs it fails to learn the optimal policy. On the other hand, AlphaZeroHER consistently improves the performance and achieves almost perfect resolution of the problem.

heading: 6 Conclusions

text: We introduced a novel algorithm for goal-directed planning, consisting of the extension of AlphaZero with the Hindsight Experience Replay (HER) method to overcome the issues caused by sparse reward functions typical of goal-directed planning. We provide a straightforward procedure that does not involve high computational costs by sampling other goals from the visited states and addressing the intrinsic on-policy nature of AlphaZero. The proposed approach outperforms AlphaZero in several test domains, including a novel application to quantum compiling, with negligible additional computation compared to plain AlphaZero. In the future, we aim to apply the proposed method to more challenging goal-directed tasks, including tasks with stochastic transition models, which were not considered in this work.

heading: A Additional Description of AlphaZeroHER

text:
In this appendix, we present the pseudocode of AlphaZeroHERO in Algorithm 1. We notice that the main loop of AlphaZero, where target values are generated from the policy targets given from MCTS and the Monte Carlo returns observed during the episodes, are extended with a set of additional experiences, based on the secondary goal states. In our implementation, the goal states are sampled uniformly from the states visited during each episode. Algorithm 1: AlphaZeroHER Initialize memory buffer B Initialize policy πθ and value network vθ for epoch = 1, · · · , N do
for episode = 1, · · · ,M do experiences ← {} st ∼ µ // Sample initial state while not done do
pt, at ← MCTS(st, πθ, vθ) st+1, rt, done ← applyAction(at) experiences ← experiences ⋃ (st,pt, rt)
st ← st+1 end Store every experience (st,pt, zt) in B, where zt = ∑T i=t γ
i−tri for t in episode experiences do // Generate new experiences
G← Sample k goals from future visited states sj where j > t for g in G do
rgt ← r(st, at, g) end Store every (st,pt, z g t ) in B, where z g t = ∑T i=t γ
i−trgi end update πθ, vθ according to Equation 4
end end

heading: B Experimental Appendix

text:
B.1 Reproducibility Details
In this section, we provide the hyper-parameters employed in the experiments presented in this work. Table 1 and Table 2 provide a list of hyperparameters employed for both AlphaZero and AlphaZeroHER, without being optimized.
B.2 Varying the number of subgoals sampled
In this section, we study the effect of increasing the number of sampled subgoals in AlphaZeroHER. Figure 7 and Figure 8 show the results of varying the number of subgoal in the BitFlip and quantum compiling environments respectively. We can see that in both enviroments the performance increases as we increase the number of subgoals k, until we
reach a (problem dependend) threshold after which the performance starts falling until it reaches the lower levels when we use as subgoals, all the available ones (label All). This is in line with the results presented in the original HER paper (Andrychowicz et al., 2017).
B.3 Comparison with DQN + HER
In this section, we compared the proposed AlphaZeroHER with DQN+HER used in the original HER paper. The goal of this experiment is to answer whether using HER in a MCTS method like AlphaZero was needed, or using “more traditional” HER implementations, like DQN was enough to solve the considered environments. We use the implementation
of DQN and HER given from stable-baselines 1. To make the comparison fair, we first employed the same network architecture used by our agents. However, except for the bitflip domains of less than 20 bits, the DQN agents could not solve any of the domains. For this reason, in the following results, we have employed a more complex network architecture for all domains (except Maze where we use the same CNN), namely an MLP with a single hidden layer of 128 neurons. We optimized the DQN hyperparameters using hyperopt2. The best hyperparameters used in all domains are listed in Table 3. It is worth noting that the hyperparameters for AlphaZero and AlphaZeroHer presented in Section 5 were not tuned.
Figure 9 shows the results of DQN+HER in the Bitflip domain for different numbers of bits. We used four additional subgoals like in the AlphaZero case but a more complex network architecture. We can reproduce the results presented in the HER paper, as the top-performing policies solve the problems 100% of the time. When comparing the average performance, though, DQN+HER still performs worse than AlphaZeroHER, only solving on average 80% of the episodes up to 60 bits, and even less when increasing to 70 bits.
1https://github.com/hill-a/stable-baselines 2http://hyperopt.github.io/hyperopt/
We also achieved satisfactory results in the quantum compiling domain, solving around 80% of the episodes within the given horizon, yet still less than the 95% achieved from the AlphaZeroHER agent presented in Section 5. Figure 10 shows the performance in this domain. There, a more complex network structure was needed to achieve this performance too. DQN+HER starts to fail in the 2D navigation task. Figure 11 presents the results in this domain. Even after tuning the DQN parameters, we only can achieve around 5% of solved episodes on average, in contrast to the 80% achieved by AlphaZeroHER. Finally, in the Maze domain, even after tuning, DQN+HER could not resolve a single episode of the task against the 60% solve rate of AlphaZeroHER.

title: Goal-Directed Planning via Hindsight Expe- rience Replay