020010 2010 V. Lakshminarayanan S. Roy, Dayalbagh Educational Institute, Agra,
India. 020010

Live cell imaging using metallic nanoparticles as tags is an emerging
technique to visualize long and highly dynamic processes due to the lack of
photobleaching and high photon rate. However, the lack of excited states as
compared to fluorescent dyes prevents the use of resonance energy transfer and
recently developed super resolution methods to measure distances between
objects closer than the diffraction limit. In this work, we experimentally
demonstrate a technique to determine subdiffraction distances based on the
near field coupling of metallic nanoparticles. Due to the symmetry breaking in
the scattering cross section, not only distances but also relative
orientations can be measured. Single gold nanoparticles were prepared on
glass, statistically yielding a small fraction of dimers. The sample was
sequentially illuminated with two wavelengths to separate background from
nanoparticle scattering based on their spectral properties. A novel total
internal reflection illumination scheme in which the polarization can be
rotated was used to further minimize background contributions. In this way,
radii, distance and orientation were measured for each individual dimer, and
their statistical distributions were found to be in agreement with the
expected ones. We envision that this technique will allow fast and long term
tracking of relative distance and orientation in biological processes.

# Experimental determination of distance and orientation of metallic
nanodimers by polarization dependent plasmon coupling

H. E. Grecco  [inst1, inst2] O. E. Martínez[inst1] E-mail<EMAIL_ADDRESS>mail<EMAIL_ADDRESS>
($22$ April 2010; 2 December 2010)

††volume: 2

99 inst1 Laboratorio de Electrónica Cuántica, Universidad de Buenos Aires.
Buenos Aires, Argentina. inst2 Current address: Department of Systemic Cell
Biology Max Planck Institute of Molecular Physiology. Dortmund, Germany

##  1 Introduction

Microscopy is an example of the ongoing symbiotic relationship between physics
and biology: as early microscopes allowed fundamental discoveries like
microorganisms or DNA; the need to see smaller, faster and deeper has pushed
the development of a plethora of optical concepts and microscopy techniques.
Today, fluorescence microscopy is an essential tool in biology as it can
visualize the spatio-temporal dynamics of intracellular processes. However,
many important mechanisms, like protein interaction, clustering or
conformational changes, occur at length scales smaller than the resolution
limit of conventional microscopy and therefore cannot be assessed by standard
imaging. Unraveling the dynamics of such inter- and intramolecular mechanisms
that provides function richness to molecules and molecular complexes is
essential to understand key biological processes such as cellular signal
propagation.

Subdiffraction distances have been determined by exploiting quantum and near
field properties of the interaction between light and matter in the nanometer
scale. For example, Fluorescence/Förster Resonance Energy Transfer (FRET) [5,
6, 7, 14] has proven to be a valuable technique as it provides an optical
signal directly related to the proximity of the molecules. The desire to
extend this technique to other biological systems with different time and
length scales has been hindered by the inherent limitations of fluorescent
dyes (i.e. lack of photostability, low brightness and short range of
interaction). Super resolution techniques such as STED [23] or PALM [2] have
recently gained momentum to directly observe fluorescent molecules spaced
closer than the diffraction limit. Although much work has been done to
increase the total acquisition time and frame rate, these methods are still
limited by the lack of photostability and the need to image a single
resolvable structure per diffraction limited spot at a time.

In the past, it has been shown that scattering microscopy using metallic
nanoparticles can complement its fluorescence sibling as it uses an
everlasting tag with no rate-limited amount of photons [10]. Metallic
nanoparticles are stable, biocompatible and easy to synthesize and conjugate
to biological targets and thereby ideal as contrast agents. A landmark example
of the biological application of such techniques was the direct observation of
receptors hopping across previously unknown membrane domains. This provided
valuable insight into the spatial regulation of signaling complexes and closed
a 30-year controversy about the diffusion coefficients of membrane proteins
[21]. While previous experiments using fluorescent tags yielded a diffusion
coefficient in biological membranes much slower than the one observed in
synthetic membranes, the fast acquisition speed (40 103 frames per second)
enabled by scattering microscopy showed that this is the result of a fast
diffusion and a slow hopping rate between domains [9].

In addition, the presence of a plasmon, i.e. a collective oscillation of the
free electrons within the nanoparticle, converts metallic nanoparticles into
very effective scatterers when illuminated at their resonance optical
frequency. The resulting strong electromagnetic enhancement in the vicinity of
the particle provides a near field effect that can be used to sense
information about their surroundings such as the effective index of refraction
or the presence of other scatterers [8, 16]. For example, it has been
experimentally shown that the shift in the plasmon resonance can be used to
determine the length of DNA molecules attached to a metallic nanoparticle
[13]. Moreover, the coupling between two nanoparticles in close proximity
produces an alteration of the plasmon spectra. This alteration has been used
as a nanometric ruler to determine the distance between them [20, 19]. In a
previous work, [4] we theoretically showed that the coupling between two
nanoparticles is highly sensitive to the polarization of the external field.
The scattering cross section ($C_{sca}$) is maximum when the incident
polarization is parallel to the dimer orientation due to the reinforcement of
the external field by the induced dipoles [Fig. 1(a)]. As the coupling
decreases monotonically with the distance between nanoparticles, so does the
average $C_{sca}$ over all polarizations ($v_{m})$ [Fig. 1(b)] and the
anisotropy [Fig. 1(c)] defined as:

$\displaystyle\eta=\frac{C_{sca}^{\parallel}-C_{sca}^{\perp}}{C_{sca}^{\parallel}+C_{sca}^{\perp}}.$
(1)

We have proposed, in our previous work, that by measuring the scattering cross
section as a function of the incident polarization angle, the axis of the
dimer and the distance between nanoparticles could be determined. In this
work, we provide experimental evidence supporting this concept by measuring
gold nanodimers on a glass surface and we introduce a novel total internal
reflection experimental setup that provides polarized illumination with a high
NA objective.

Figure 1:  Conceptual idea of the technique. (a) Two metallic nanoparticles of
radii $a$ located at a distance $d$ are illuminated with a linearly polarized
electromagnetic field. (b) Theoretical results as a function of the
interparticle distance for the average $C_{sca}$ over all polarizations
($v_{m}$) and (c) the anisotropy. Parameters of the calculation: $a$ = 20 nm,
wavelength of the light: 532 nm.

##  2 Materials and methods

###  2.1 Sample preparation

Coverslips were cleaned by sonication at 50∘ for 20 minutes in Milli-Q water,
and then sequentially immersed for 5 seconds in HFL 5%, sodium bicarbonate and
acetone (analytic level). After the cleaning process, coverslips were dried
and stored in a chamber overpressurized with nitrogen until further use.
Before sample preparation, a Parafilm chamber was assembled on top of the
coverslip. To create a hydrophilic surface, bovine serum albumina (BSA) in
phosphate buffer solution (PBS) was incubated for 15 min and then rinsed with
PBS. Fluorescein-streptavidin in PBS (50 mg/ml) was then incubated for 30 min
and rinsed with PBS, to obtain an adsorbed layer that was verified using
confocal fluorescence microscopy. Finally, a solution of biotinylated gold
nanoparticles, nominal radius ($20\pm 5$) nm (GB-01-40. EY Laboratories, USA),
was incubated for 15 min and then rinsed by washing 5 times with PBS. The
concentration and incubation time where empirically chosen to provide a
concentration about 1 nanoparticle/10 $\mu$m2. As the particles are randomly
distributed, it is expected to find many monomers, some dimers, and very few
trimers and higher n-mers. A negative control sample was prepared in the same
way but omitting the incubation of gold nanoparticles.

###  2.2 Dual color scheme

Spurious reflections and scattering centers other than gold will produce
unwanted bright spots in the images. Even thresholding the image taken at the
resonance peak (532 nm) will result in many false positive regions. The
presence of a plasmon resonance in the scattering spectrum of gold
nanoparticles was used as a signature to distinguish them. The ratio between
the scattering cross section at 532 nm and 473 nm was found to be larger than
1.4 for gold monomers [Fig. 2(a), solid thin line] using Mie theory [3] and
even larger for dimers (dashed line) as calculated using GMMie, a
multiparticle extension of the Mie theory [11, 12]. In contrast, non metallic
scattering centers lack of a plasmon resonance and therefore yield a smaller
ratio between 532 nm and 473 nm $C_{sca}$ (solid thick line). Therefore, by
imaging at these two wavelengths and thresholding the ratio image above 1.4,
the pixels containing gold nanoparticles were further segmented.

Figure 2:  Experimental Setup. (a) Comparison of spectra averaging over all
polarizations. While the spectrum of dielectric particles (thick solid line)
decreases monotonically, the spectra of metallic monomers and dimers (thin
lines) show a plasmon resonance. (b) The polarization of the refracted wave is
dependent on the direction of the incident polarization with respect to the
displacement in the back focal plane (BFP) of the objective which defines the
plane of incidence. (c) The sample is illuminated in Total Internal Reflection
and imaged using a cooled CCD. Laser light is tightly focused off-center in
the back focal plane of the objective and the angle $\beta$ is moved using a
pair of galvanometer scanners moving in orthogonal directions.

###  2.3 Polarization control in Total Internal Reflection

We used Total Internal Reflection (TIR) microscopy [1] to restrict the
illumination to the surface of the coverslip using an evanescent wave. In
objective-based TIR, the beam is focused off-axis in the back focal plane
(BFP) of the objective to achieve critical illumination. The components of
evanescent field are defined by the angle of incidence ($\theta$) and the
incident polarization with respect to the plane of incidence. Indeed, rotating
the excitation polarization before entering the microscope does not produce a
constant intensity in the sample plane as the transmission efficiency for the
parallel polarization [Fig. 2(b), left] will be much smaller than for the
perpendicular one [Fig. 2(b), center]. A circularly polarized beam before the
objective results in an “elliptically”111The electromagnetic field in the
sample cannot be said to be strictly elliptically polarized as an evanescent
field (not a propagating beam) is generated after the interface. Nevertheless,
an elliptical rotation of the electric field is achieved. polarized field
which has the minor axis in the plane of incidence [Fig. 2(b), right]. The
ratio between the major and minor axis of this evanescent “elliptical” beam
depends on $\theta$ and if the plane of incidence is changed, the ellipse will
rotate with it. We therefore modified a wide-field inverted microscope (IX71.
Olympus, Japan) using a TIRF objective (Olympus TIRFM 63X/1.45 PlanApo Oil) to
allow rotating the plane of incidence [Fig. 2(c)] by changing the position in
which the beam is focused in the BFP. Two lasers were used: one near the gold
particle plasmon resonance (532 nm, Compass C315M. Coherent Inc., USA) and
another shifted towards shorter wavelengths (473 nm, VA-I-N-473. Viasho
Technology, China). The power of the lasers after the objective was 13 $\mu$W.
Circularly polarized light was achieved at the BFP by inserting a quarter and
a half wave plate in the beam path adjusted to precompensate for the
polarization dependent transmission of the beam splitter, filters and mirrors.
The beam was expanded and filtered to achieve a diffraction limited spot in
the BFP. In order to displace the beam in the BFP and therefore change the
plane of incidence, a pair of computer controlled galvanometer scanners
(SC2000 controller, Minisax amplifier and M2 galvanometer. GSI Group, USA)
were used. The polarization distortion due to the change in the angle of
incidence onto the mirrors of the scanners (while moving) was verified to be
negligible. Images of the sample were acquired using a cooled monochrome CCD
camera (Alta U32. Apogee Instruments, USA. $2148\times 1472$ pixels each
$6.8\times 6.8$ $\mu$m2) through a dichroic filter for the fluorescence sample
(XF2009 550DCLP. Chroma Technology, USA) or a 30/70 beam splitter for the gold
nanoparticles (21009. Chroma Technology, USA).

###  2.4 Intrinsic anisotropy determination

To assure a constant ratio between the two polarizations of the beam and a
uniform intensity, the beam needed to be moved on the BFP in a circle centered
in the optical axis. Failure to do this would have reduced the dynamic range
of the system by introducing an intrinsic anisotropy. To minimize this value,
the path of the beam was iteratively modified while measuring the anisotropy
(see below) of a diluted solution of Rhodamine 101. The emission of such a
sample is independent of the excitation polarization and thus the measured
anisotropy can be assigned only to the system. After optimization, the
obtained anisotropy for the 532 and 473 channels was 0.06 and 0.05 in a region
of $50\times 50$ $\mu$m2 ($440\times 440$ pixel2). It is worth noting than
these values are five times smaller than the expected anisotropy for a 20 nm
homodimer.

###  2.5 Image acquisition and processing

The acquisition process consisted in sequentially imaging at 473 nm and 532 nm
while changing the angle $\beta$ in 20 discrete steps over $2\pi$ to sample
different polarizations. An image with both lasers off was also acquired to
account for ambient light and dark counts of the camera. Each image was
background corrected and normalized by the excitation power and detection
efficiency at the corresponding wavelength. Mean images ($m_{473}$ and
$m_{532}$) were obtained by averaging over all polarizations and, from these,
the ratio image $m=m_{532}/m_{473}$ was calculated.

The scattering image at the resonance peak ($m_{532}$) was segmented by Otsu’s
thresholding and masked with the ratio image thresholded above 1.4 to detect
pixels containing gold. A connected region analysis was performed to keep only
those regions with area between 3 and 15 pixels. The upper bound was chosen to
be slightly bigger than the airy diffraction limited spot for the system, but
still much smaller than the mean distance between gold nanoparticles. Regions
containing single gold nanoparticles should have a constant intensity over the
stack of frames acquired for different polarization orientation, while dimers
should provide an oscillating signal with period $\pi$. Therefore, a Fourier
analysis [Eq. (2)] was performed. For each pixel, the following coefficients
were calculated:

$\displaystyle\tilde{c}_{2}$
$\displaystyle=\frac{2}{\sum_{\beta}I(\beta)}\sum_{\beta}I(\beta)cos(2\beta)$
(2a) $\displaystyle\tilde{s}_{2}$
$\displaystyle=\frac{2}{\sum_{\beta}I(\beta)}\sum_{\beta}I(\beta)sin(2\beta)$
(2b) $\displaystyle\eta$
$\displaystyle=\sqrt{\tilde{c}_{n}^{2}+\tilde{s}_{n}^{2}}$ (2c) $\displaystyle
tan(\delta)$ $\displaystyle=\frac{\tilde{s}_{2}}{\tilde{c}_{2}}$ (2d)

This was done for each wavelength obtaining values for the anisotropy
($\eta_{473}$ and $\eta_{532}$) and orientation ($\delta_{473}$ and
$\delta_{532}$) in each pixel. The acquisition and analysis process were
repeated for 30 and 10 fields of view of the sample and negative control
sample respectively. Retrieval uncertainty was estimated by performing the
same numerical analysis on simulated data calculated by adding two terms to
the theoretical response for different dimers. The first, an oscillating term
with $2\pi$ periodicity, emulated a small misalignment that produced a non-
constant illumination while rotating the beam in the BFP. The amplitude of
this term was obtained from the Rhodamine calibration. The second term
simulated coherent background and its values for each pixel were drawn from a
Gaussian distribution obtained from the control images.

Figure 3:  Experimental results (a) Representative images of a field of view
for single wavelength (left) and a ratio (right) imaging. Some points
(circles) are bright in both images (gold) while others squares faint in the
ratio image (not gold). Gold containing regions were segmented by finding
bright pixels in both images. Images size: 50x50 ${\mu m}^{2}$. 440x440
pixels. (b) Anisotropy vs. mean value. A strong correlation is observed
between anisotropy and mean value for both wavelengths as expected. The 473 nm
data shows a plateau due to the intrinsic anisotropy of the system.

##  3 Results and discussion

The need for a two color approach is evident when comparing single wavelength
with ratio images: while regions with and without nanoparticles [Fig. 3(a),
circles and squares respectively] were bright due to the high background in
the single channel image, only gold nanoparticles were above the threshold in
the ratio image. Importantly, in the negative control stack, no pixel was
found above the a priori defined threshold. For the 35 regions identified as
gold monomers/dimer, a strong correlation between anisotropy and mean value
was found as expected [Fig. 3(b)]. The variance over each region for all
values was below the corresponding retrieval uncertainty. A plateau was
observed for the 473 nm channel due to the intrinsic anisotropy of the system.
In this set of candidates for dimers, eight points presented an unexpected
high individual anisotropy and hence were rejected. Although the exact origin
of this eight scattering centers could not be established, it is worthwhile
noting that it is extremely relevant in a tracking experiment to avoid false
positives that would severely distort the retrieved information, and this
ability to reject scattering centers based on their response is an additional
advantage of the technique.

Figure 4:  Comparison between experimental data and homodimer model. The mean
value ratio is plotted against the anisotropy ratio for the regions segmented
from the images (blue dots). Theoretical calculations for different homodimers
are also plotted. The vertical lines show the results keeping constant the
surface to surface distance ($d_{ss}$) while changing the radii ($a$). The
opposite is shown in the horizontal lines. Remarkably, experimental data
distributed close to the curve for 20 nm homodimers (solid line) as expected
as this is in fact the mean radii of the particles used. Notice that this is
not a fit (no free parameters), but the predictions from the homodimer model
superimposed to the experimental data.

The recovered scattering parameters were compared with the expected results
for a homodimer configuration (Fig. 4) obtaining a good correspondence with
the nominal size of the nanoparticles used (20 nm). Indeed, the mesh shown in
Fig. 4 was calculated using only the photophysical and geometrical properties
of the dimer (no fitted parameters). The ability of the technique to blindly
recover the correct size of the particles was a cross-check for its
reliability.

The actual configuration of each dimer was obtained by fitting the theoretical
model to the experimental values. The in-plane orientation was directly
obtained as a weighted average of these values. To fit the radii of each
particle and the distance between them, the values of $\eta_{473}$,
$\eta_{532}$ and $m$ were used. The values were first fitted using the
analytical solution of a homodimer configuration in the dipole-dipole
approach, in which the induced dipole moment $\vec{p}$ of each particle in an
incident field $\vec{E}_{inc}$ can be expressed as:

$\displaystyle\vec{p}_{\parallel}=\frac{1}{1-\frac{\alpha}{2d^{3}\pi}}\epsilon_{m}\alpha\vec{E}_{inc}$
(3a)
$\displaystyle\vec{p}_{\perp}=\frac{1}{2+\frac{\alpha}{2d^{3}\pi}}\epsilon_{m}\alpha\vec{E}_{inc}$
(3b)

$\epsilon_{m}$ being the dielectric constant of the medium and $\alpha$ the
polarizability of the sphere which is proportional to the cube of its radius
[4, 3]. This homodimer configuration was used as an initial value in the time
consuming iterative process of finding a heterodimer configuration compatible
with the experimental data using GMMie calculation. The traveling wave
approximation of the evanescent field was used as the particles are small
compared to the decay length of the field [18, 22] and the collection
efficiency is much smaller for the dipole induced in the optical axis
orientation than for the one perpendicular to it.

In this way, the two radii, orientation and distance for each dimer were
obtained (Fig. 5). The distribution of radii was found to be centered in 20
nm, compatible with the nominal size of the particles. For the interparticle
distances, the distribution showed an increase as expected but then a decrease
for distances at which the anisotropy is close to the intrinsic anisotropy of
the system. This mismatch at larger distances is due to the conservative
criterion to separate dimers from monomers that fails to identify correctly
nanoparticles that couple weakly. The dimer orientation was uniformly
distributed between $-\pi$ and $\pi$, as expected. To further test this, we
compared the experimental and simulated distributions using a Kolmogorov-
Smirnov [15] statistical test. The level of significance set at the usual
value of 5%. The expected distributions (Fig. 5, right column) were obtained
from the nominal radius of the nanoparticles and Monte Carlo simulation of the
adsorption process. The experimental and simulated distributions for radii and
orientation were found in close agreement. For the interparticle distance, the
distributions were found compatible when compared up to 70 nm.

Figure 5:  Fit to a heterodimer configuration using GMMie. For each dimer
(left column, x axis), the radii (top), the distance (middle) and the angle
(bottom) were obtained. Experimental and simulated histograms are shown for
each magnitude (middle and right columns).

##  4 Conclusions

We have experimentally shown that distance between two nanoparticles, as well
as their individual radii, can be obtained by measuring the intensity of spot
as a function of the incident polarization. Additionally, the in-plane
orientation of the dimer was obtained with less than 10∘ uncertainty. The
presented method strongly exploits the particular spectroscopic properties of
metallic nanoparticles to sense their environment. It is worth noting that the
distance in which the technique is sensitive scales with the radii of the used
particles. By using nanoparticles with radius between 4 and 20 nm, the gap
between FRET and standard super-resolution techniques (10 nm to 50 nm) could
be bridged. This fact, together with the ability to recover orientation, makes
this approach unique.

A non-uniform anisotropic illumination is the major source of uncertainty as
it will mask the anisotropy of the dimers, specially for those in which the
distance is much larger than the radius of the particles. This should be
properly controlled by measuring an isotropic sample as it was done in this
work. Additionally, it is important to mention that various factors such as a
non-monodisperse or non-spherical population of particles will have an
incidence in the recovery of dimer distance, size and orientation from model
based fittings. However, having a multiparametric readout (i.e. $m_{532}$,
$m_{473}$, $\eta_{473}$ and $\eta_{532}$) with a non-trivial dependence of the
physical parameters (i.e. distance, size, shape) provides a way to control for
this and exclude points that do no match the expected relations between
photophysical properties. Such conservative criterion would be recommended for
tracking experiments where false negatives have minor impact as they only
reduce the amount of information gathered per frame. If the yield of dimers
can be raised and several dozens of dimers can be imaged in the same field of
view, we expect that the presented technique will be useful to add information
about the relative movement of the two particles to already existing tracking
assays. Numerical simulations showed that if coherent background can be
diminished, an order of magnitude (i.e. by the use of broader band excitation
source), distance and orientation could be tracked at 100 Hz. If just the
rotation and the movement of the center of mass is desired, the retrieval can
be performed much faster as only one wavelength (532 nm) would be necessary
after an initial identification of the dimers is made by the two color method.

As other scattering based techniques, the lack of photobleaching constitutes a
major advantage of this approach. Moreover, the absence of saturation in the
light scattering of metallic nanoparticles, as compared to the absorption of
fluorescent molecules, provides an acquisition rate only limited by the
detector speed. The combination of these two aspects means that scattering
based microscopy does not need to make compromises between experiment length
and temporal resolution.

We have also demonstrated that the use of two color imaging can provide an
efficient way to detect scattering centers that have plasmon resonances.
Recent work by Olk et al. [17] has shown that upon illumination with a
wideband light source, a modulation of the spectra due to far-field effects
can be observed as a function of the incident polarization. The combination of
the two techniques could lead to a more robust detection of both, orientation
and distance.

Finally, the novel illumination setup introduced in this work provides a
robust way to change the polarization in TIR, allowing the implementation of
anisotropy based techniques in fluorescence and scattering microscopy.
Additionally, the same scheme permits a fast switching between TIR and
standard wide-field as well as sweeping of multiple evanescent field
penetration depths.

###### Acknowledgements.

HEG was funded by the Universidad de Buenos Aires.

## References

  * [1] D Axelrod, T P Burghardt, N L Thompson,  Total internal reflection fluorescence,  Annu. Rev. Biophys. Bio. 13, 247 (1984).
  * [2] E Betzig, G H Patterson, R Sougrat, O W Lindwasser, S Olenych, J S Bonifacino, M W Davidson, J Lippincott-Schwartz, H F Hess,  Imaging intracellular fluorescent proteins at nanometer resolution,  Science 313, 1642 (2006).
  * [3] C F Bohren, D R Huffman,  Absorption and scattering of light by small particles,  Whiley (1983).
  * [4] H E Grecco, O E Martínez,  Distance and orientation measurement in the nanometric scale based on polarization anisotropy of metallic dimers,  Opt. Express 14, 8716 (2006).
  * [5] F G Haj, P J Verveer, A Squire, B G Neel, P I H Bastiaens,  Imaging sites of receptor dephosphorylation by PTP1B on the surface of the endoplasmic reticulum,  Science 295, 1708 (2002).
  * [6] E A Jares-Erijman, T M Jovin,  FRET imaging,  Nat. Biotechnol. 21, 1387 (2003).
  * [7] Z Kam, T Volberg, B Geiger,  Mapping of adherens junction components using microscopic resonance energy transfer imaging,  J. Cell Sci. 108, 1051 (1995).
  * [8] K L Kelly, E Coronado, L L Zhao, G C Schatz,  The optical properties of metal nanoparticles: The influence of size, shape, and dielectric environment,  J. Phys. Chem. B 107, 668 (2003).
  * [9] A Kusumi, C Nakada, K Ritchie, K Murase, K Suzuki, H Murakoshi, R S Kasai, J Kondo, T Fujiwara,  Paradigm shift of the plasma membrane concept from the two-dimensional continuum fluid to the partitioned fluid: High-speed single-molecule tracking of membrane molecules,  Annu. Rev. Bioph. Biom. 34, 351 (2005).
  * [10] D Lasne, G Blab, S Berciaud, M Heine, L Groc, D Choquet, L Cognet, B Lounis,  Single nanoparticle photothermal tracking (SNaPT) of 5-nm gold beads in live cells,  Biophys. J. 91, 4598 (2006).
  * [11] Y lin Xu,  Electromagnetic scattering by an aggregate of spheres,  Appl. Optics 34, 4573 (1995).
  * [12] Y lin Xu,  Electromagnetic scattering by an aggregate of spheres: Far field,  Appl. Optics 36, 9496 (1997).
  * [13] G L Liu, et al.,  A nanoplasmonic molecular ruler for measuring nuclease activity and dna footprinting,  Nat. Nanotechnol. 1, 47 (2006).
  * [14] N P Mahajan, K Linder, G Berry, G W Gordon, R Heim, B Herman,  Bcl-2 and bax interactions in mitochondria probed with green fluorescent protein and fluorescence resonance energy transfer,  Nat. Biotechnol. 16, 547 (1998).
  * [15] F J Massey,  The Kolmogorov–Smirnov test for goodness of fit,  J. Am. Stat. Assoc. 46, 68 (1951).
  * [16] A D McFarland, R P V Duyne,  Single silver nanoparticles as real-time optical sensors with zeptomole sensitivity,  Nano Lett. 3, 1057 (2003).
  * [17] P Olk, J Renger, M T Wenzel, L M Eng,  Distance dependent spectral tuning of two coupled metal nanoparticles,  Nano Lett. 8, 1174 (2008).
  * [18] M Quinten, A Pack, R Wannemacher,  Scattering and extinction of evanescent waves by small particles,  Appl. Phys. B: Lasers O. 68, 87 (1999).

  * [19] B M Reinhard, M Siu, H Agarwal, A P Alivisatos, J Liphardt,  Calibration of dynamic molecular rulers based on plasmon coupling between gold nanoparticles,  Nano Lett. 5, 2246 (2005).
  * [20] C Sönnichsen, B M Reinhard, J Liphardt, A P Alivisatos,  A molecular ruler based on plasmon coupling of single gold and silver nanoparticles,  Nature Biotech. 23, 741 (2005).
  * [21] K Suzuki, K Ritchie, E Kajikawa, T Fujiwara, A Kusumi,  Rapid hop diffusion of a g-protein-coupled receptor in the plasma membrane as revealed by single-molecule techniques,  Biophys. J. 88, 3659 (2005).
  * [22] R Wannemacher, A Pack, M Quinten,  Resonant absorption and scattering in evanescent fields,  Appl. Phys. B: Lasers O. 68, 225 (1999).
  * [23] V Westphal, S O Rizzoli, M A Lauterbach, D Kamin, R Jahn, S W Hell,  Video-rate far-field optical nanoscopy dissects synaptic vesicle movement,  Science 320, 246 (2008).


11institutetext: University of Groningen, Broerstraat 5, 9712 CP Groningen,
Netherlands 11email<EMAIL_ADDRESS>
11email<EMAIL_ADDRESS>
22institutetext: Queen Mary University of London, Mile End Road, London E1
4NS, UK
22email<EMAIL_ADDRESS>
# VDSC: Enhancing Exploration Timing with Value Discrepancy and State Counts

Marius Captari 11 Remo Sasso 22 Matthia Sabatelli 11

###### Abstract

Despite the considerable attention given to the questions of how much and how
to explore in deep reinforcement learning, the investigation into when to
explore remains relatively less researched. While more sophisticated
exploration strategies can excel in specific, often sparse reward
environments, existing simpler approaches, such as $\epsilon$-greedy, persist
in outperforming them across a broader spectrum of domains. The appeal of
these simpler strategies lies in their ease of implementation and generality
across a wide range of domains. The downside is that these methods are
essentially a blind switching mechanism, which completely disregards the
agent’s internal state. In this paper, we propose to leverage the agent’s
internal state to decide when to explore, addressing the shortcomings of blind
switching mechanisms. We present Value Discrepancy and State Counts through
homeostasis (VDSC), a novel approach for efficient exploration timing.
Experimental results on the Atari suite demonstrate the superiority of our
strategy over traditional methods such as $\epsilon$-greedy and Boltzmann, as
well as more sophisticated techniques like Noisy Nets.

###### Keywords:

Reinforcement Learning Deep Learning Exploration.

##  1 Introduction

Despite remarkable successes in deep reinforcement learning (DRL), the core
challenges of reinforcement learning (RL) are still restricting the
applicability to real-world scenarios due to severe data-inefficiency. Central
to these challenges is the exploration-exploitation trade-off [29]. Every
agent encounters this dilemma: should it rely on its current knowledge and
take actions that are known to yield good rewards (exploitation), or should it
try new actions, potentially discovering better strategies but risking lower
immediate rewards (exploration)?

In the domain of DRL, considerable effort has been directed towards
understanding the optimal balance of exploration (how much) and devising
techniques for executing exploratory actions (how). This encompasses studies
on modulating the exploration rate over time and optimizing action selection
strategies for better learning outcomes [1, 31, 19]. A rich body of work
explores various strategies, such as stochastic action selection, optimistic
initialization, and intrinsic motivation [23, 5, 4].

####  1.0.1 Contribution.

In this work, we primarily focus on the lesser researched, yet equally
important, when aspect of exploration. That is, we are interested in utilizing
internal information signals for ’triggering’ the agent to start exploring.
Introducing Value Discrepancy and State Counts (VDSC) as key information
triggers, we propose monitoring and combining them through a homeostasis
mechanism. The first trigger, Value Promise Discrepancy (VPD), is inspired by
insights from [24]. VPD is an online measure that initiates exploratory
actions by evaluating the discrepancy between an agent’s prior value estimate
of a state and the actual cumulative reward received over a certain period.
This assessment helps agents gauge the accuracy of their internal value
predictions, informing their decision to explore further or exploit current
knowledge. However, this trigger may not adequately address issues like
sparser reward environments, highly stochastic states, and perhaps most
importantly, information regarding the novelty of a state. To remedy this, we
introduce a second trigger for a richer exploration behavior. This second
trigger involves mapping states to hash codes using the SimHash algorithm [8],
allowing for the counting of individual hash occurrences [30]. The counts are
used to encourage the visitation of novel states, rather than frequently
visited states. However, unlike the original work, where an exploration bonus
is added as an external reward, we propose tracking this metric as an
additional trigger for exploration, preserving the original reward structure
and avoiding issues like reward distortion and novelty loops.

####  1.0.2 Paper Structure.

The remainder of this paper is structured as follows. Section 2 provides the
foundational background and concepts essential to our study. Section 3
presents an overview of a literature review of some of the main ideas relating
to exploration in DRL. Section 4 offers an overview of the two main triggers
being used, highlights potential limitations, and presents a way in which both
triggers are combined in VDSC. Section 5 presents the experiments and the
results obtained across various games from the Atari benchmark. Lastly,
Section 6 provides concluding remarks, summarizes key insights, and suggests
potential directions for future research.

##  2 Preliminaries

We formulate the RL problem as a Markov Decision Processes (MDP) formally
represented as a tuple
$\langle\mathcal{S},\mathcal{A},\mathcal{R},\mathcal{P},\gamma\rangle$. where
$\mathcal{S}$ denotes the state space, $\mathcal{A}$ represents the action
space,
$\mathcal{P}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$ is
the transition function indicating the probability of moving from state
$s\in\mathcal{S}$ to state $s^{\prime}$ in $\mathcal{S}$ given action
$a\in\mathcal{A}$, $\mathcal{R}:S\times A\rightarrow\mathbb{R}$ is the reward
function assigning a real-valued reward $r$ at time-step $t$ to each state-
action pair and $\gamma\in(0,1]$ is the discount factor balancing the
importance of immediate versus future rewards. The agent-environment
interaction is governed by the agent’s policy
$\pi:\mathcal{S}\rightarrow\mathcal{A}$ which allows us to define the value of
a state $s$ via the state-value function $V^{\pi}(s)$:

$V^{\pi}(s)=\mathbb{E}\Bigg{[}\sum_{k=0}^{\infty}\gamma^{k}r_{t+k}|s_{t}=s,\pi\Bigg{]},$

and the value of a state-action pair via the state-action value function

$Q^{\pi}(s,a)=\mathbb{E}\Bigg{[}\sum_{k=0}^{\infty}\gamma^{k}r_{t+k}|s_{t}=s,a_{t}=a,\pi\Bigg{]}.$

Both value functions play a crucial role when it comes to the exploration-
exploitation dilemma. The answer to whether it is better to explore or exploit
strongly depends on how precise the learned estimates of these value functions
are. In fact, in RL we are interested in finding a policy which maximizes the
aforementioned value functions, as this allows us to define the optimal policy
$\pi^{\star}$, the policy that realizes the optimal expected return
$V^{\star}(s)=\max_{\pi}V^{\pi}(s),\text{ for all }s\in\mathcal{S}$, and the
optimal state-action function $Q^{\star}(s,a)=\max_{\pi}Q^{\pi}(s,a),\text{
for all }s\in\mathcal{S}\text{ and }a\in\mathcal{A}$. It is well-known that if
an optimal value function is learned, e.g. $Q^{\star}(s,a)$, there is no need
for exploration, as the optimal policy can be easily derived as
$\pi^{\star}(s)=\underset{a\in\mathcal{A}}{\text{argmax}}\ Q^{\star}(s,a)\
\text{for all}\ s\in\mathcal{S}$.

##  3 Related Work

Despite the theoretical foundations of exploration methods being well-
documented in finite state-action spaces, with established sample complexity
bounds [10, 2], their practical applicability diminishes significantly when
confronted with large or continuous state spaces. These theoretical
constraints often stem from a focus on worst-case scenarios, rendering them
less effective when addressing real-world problems. Within DRL, hard
exploration problems pose significant challenges. In environments
characterized by sparse rewards, conventional random exploration methods
struggle to reach successful states. Games like Pitfall! and Montezuma’s
Revenge from the Atari-57 benchmark exemplify such hard exploration games [4],
sparking the development of more deliberate exploration strategies.

####  3.0.1 Intrinsic reward

methods are an emerging strategy that incentivizes diverse state visits and
behaviors by introducing additional rewards [27]. Prediction error methods,
for instance, compute intrinsic rewards based on prediction model errors when
revisiting previously encountered states [23, 6]. While these methods yield
substantial performance gains in hard exploration games, their theoretical
underpinnings remain relatively weaker. Furthermore, the introduction of
unpredictable random noise, such as the "Noisy-TV" problem [6], poses
challenges for intrinsic motivation methods, potentially leading agents into
novelty loops that impede task completion.

####  3.0.2 Count-based

methods offer another avenue for encouraging exploration by rewarding states
with low visit counts. However, directly counting states becomes impractical
in high-dimensional or continuous state spaces. To address this, density
models estimate pseudo-counts to approximate state visit frequencies [4, 34].
Hashing techniques, such as SimHash [8] or autoencoders, provide alternative
approaches to handle high-dimensional state spaces efficiently [30].

####  3.0.3 Probabilistic

methods offer an alternative by modeling uncertainty over transition, reward,
or value functions to guide exploration. Randomized value functions [19, 18,
20], inspired by Thompson sampling, rely on maintaining a distribution that
represents uncertainty over the optimal value function through an ensemble of
Q-functions to guide exploration by periodically sampling and greedily
following a value function. [26] show that modeling such uncertainty over the
transition and reward function through Bayesian Linear Regression instead
allows for substantially better exploration and sample efficiency.

####  3.0.4 Uncertainty

based approaches such as uncertainty Bellman equations, which connect the
uncertainty from the current time-step to the expected uncertainties at
subsequent time-steps [21], and Noisy Nets [12], which adds stochasticity
through parametric noise to the neural network weights, integrate learning and
exploration within a unified estimation framework, offering alternative
strategies for efficient exploration. Central to this paper is Value Promise
Discrepancy, which measures uncertainty by comparing value function
predictions with cumulative reward [24].

####  3.0.5 Goal-based

exploration methods like go-explore [11] operate by revisiting previously
encountered promising states and subsequently exploring from there, using a
reward state as a goal. This approach to exploration empowered agents to
achieve scores previously deemed unattainable in challenging games such as
Montezuma’s Revenge, all without any domain knowledge.

####  3.0.6 Dithering

methods such as $\epsilon$-greedy, despite all these advancements in
exploration techniques, remain prevalent in practice due to their ease of
implementation and full coverage of the state space. However, a notable issue
with this strategy is its limited capacity for persistent exploration,
hindering significant deviations from its current trajectory. Motivated by
this limitation, $\epsilon z$-greedy [9] preserves the simplicity of
$\epsilon$-greedy while enabling deviations through a mechanism that repeats
the last action for a random duration sampled from a long-tailed distribution.

#####

The methods discussed here represent only a fraction of the available
approaches, offering insight into the diverse ideas fueling exploration within
the field. Our work falls within a subset that focuses on using informed
triggers to guide the timing of exploration.

##  4 Methods

In this section, we start by introducing two existing measurements that can be
used to steer exploration as triggers. Trigger-based exploration involves
utilizing specific indicators to determine when to explore. These triggers can
be categorized as either blind, relying on predefined timers or probabilistic
mechanisms like $\epsilon$-greedy, or informed, considering internal states
relevant to the agent. Motivated by the limitations of these two metrics, we
propose a method to overcome them by combining both signals and dynamically
setting a threshold for triggering exploration through a homeostasis
mechanism.

###  4.1 Value Promise Discrepancy

One measurement that can effectively serve as a trigger for guiding
exploration is the Value Promise Discrepancy (VPD) [24]. VPD is an online
discrepancy measure between the value function’s predicted cumulative reward
$k$ steps ago for state $s_{t-k}$ to the actual rewards $r_{t-k,\ldots,t}$
obtained in that time frame. Naturally, the VPD is greater in areas that were
infrequently visited by the agent and therefore indicating a lack of
exploration. Formally, the VPD over a time interval from $t-k$ to $t$ is
defined as:

$VPD(t-k,t):=V(s_{t-k})-\sum_{i=0}^{k-1}\gamma^{i}r_{t-i}-\gamma^{k}V(s_{t}),$

where, as introduced in Section 2, $V(s)$ denotes the agent’s value estimate
at time-step $t$ for state $s$, reward $r$ and discount factor $\gamma$. By
investigating the difference between expected and achieved values, one can
gain insights into areas where the agent’s learning may be lagging or where it
may be over-optimistic about specific actions or states. This measurement can
serve as a proxy for the agent’s uncertainty, where a higher uncertainty value
should encourage the agent towards more exploration.

While the presented signals offer valuable insights into exploration, their
usage as triggers introduces several considerations. For instance, a high VPD
may suggest heightened uncertainty, yet this interpretation may oversimplify
the situation. Elevated VPD values could merely indicate the agent’s early
learning stage, where prediction errors are inherently high due to initial
value estimates deviating from optimality. Similarly, certain state spaces may
naturally exhibit higher volatility or unpredictability, resulting in elevated
VPD values. Moreover, VPD fails to capture nuances such as state novelty, a
metric that, as reviewed in Section 3, is crucial in exploration.
Consequently, relying solely on VPD might obscure underlying reasons for
prediction errors and overlook other crucial information.

###  4.2 Count-Based Exploration and SimHash

Count-based exploration is a foundational method in RL, leveraging the
frequency of state visits to guide the agent’s exploratory behavior. The idea
behind this approach is that states visited less frequently may offer greater
informational or reward opportunities, making them prime candidates for
exploration. This approach has seen varied applications, from simpler,
discrete state spaces to more complex and high-dimensional environments [28,
30, 22]. However, as most DRL agents typically operate in high-dimensional
spaces, traditional tabular methods for tracking state visits are infeasible.
Hence, approximation techniques, like hashing, are often employed to achieve
this goal [4].

The SimHash function encodes a state $s\in S$ as $\phi(s)=\text{sgn}(A\cdot
g(s))$, where $A$ is a $\kappa\times D$ matrix with entries from
$\mathcal{N}(0,1)$, and $g:S\rightarrow\mathbb{R}^{D}$ is an optional pre-
processing function. The parameter $\kappa$, essentially the number of bits of
the compressed state, influences collision likelihood and state
differentiation. The hashing process can be visualized in Figure 1.

Hashing$k=64$ bits

1111111111111111111111111111111111111111111111111111111111111111

Figure 1: Possible state hash conversion using $\kappa=64$ bits on an
8$\times$8 grid. Transition from a pre-processed Atari Pong game state (left)
to the corresponding hashed state (right).

The counts from the hash table can then be used to calculate a reward bonus,
which is added to the agent’s final reward at each time step. The reward bonus
$r^{+}$ is calculated according to the following formula:

$r^{+}(s)=\frac{\beta}{\sqrt{n(\phi(s))}},$

where $\beta\in\mathbb{R}_{>0}$ and $\phi$ is the chosen appropriate hash
function. The agent is then trained with the final reward $r$ returned by the
environment plus the exploration bonus $r^{+}$. The hashing mechanism
inherently clusters similar states, providing a more generalized count and
thereby smoothing the exploration landscape. Moreover, the hashing function
can be tailored to strike a delicate balance between generalization across
states and distinguishing between them.

Count-based approaches, such as the one just presented, also present
challenges and drawbacks. Directly augmenting enviroment rewards with bonuses
can distort the true environmental feedback, potentially impeding learning or
leading to sub-optimal policies [6]. Another concern pertains to the
utilization of an additional hyperparameter denoted as $\beta$, which scales
the provided bonus reward. Conventionally, a rule of thumb suggests employing
a reward bonus with an inverse-square-root dependence. However, research
indicates that adopting an inversely proportional relation can lead to faster
learning rates [16]. The scaling of this exploration bonus remains unresolved
within the context of DRL, representing another parameter requiring fine-
tuning.

###  4.3 Homeostasis

One challenge in determining when to explore based on incoming signals is
setting a threshold beyond which an exploratory action is triggered. In
practice, such signals can vary significantly not only across different
environments but also during training. To address this challenge, we present
an extended version of the homeostasis mechanism [32], as introduced in [24],
which we refer to as ’unified homeostasis.’ The homeostasis mechanism aims to
convert a series of numeric signals $x_{t}$ into binary decisions
$y_{t}\in{0,1}$, aiming for an average switching rate close to a target rate
$\rho$. Contextualizing this for our exploration problem, high values of the
tracked metric $x_{t}$ suggest a higher likelihood of exploring ($y_{t}=1$),
and the target rate $\rho$ refers to our desired exploration rate (similar to
$\epsilon$ in $\epsilon$-greedy). Note that the value of $y_{t}$ only refers
to the decision based on whether or not the agent should explore at timestep
$t$, that is, should it act greedily ($y_{t}=0$) or should it explore
($y_{t}=1$). As we are mainly interested in studying the question of when to
explore in this work, we set the exploratory action randomly.

Unified homeostasis integrates feedback from multiple signals (triggers) by
utilizing their respective moving averages to guide the timing of exploration.
During each step of the learning process, the method calculates exploration
probabilities for all triggers, averaging them to determine the overall
exploration probability $\overline{p}$. Subsequently, it samples the decision
of whether or not to explore from a Bernoulli distribution using
$\overline{p}$ as the parameter. To enhance adaptability, a time scale of
interest $\tau:=\min(t,\frac{5}{\rho})$ is established. This time scale acts
as a reference, dynamically adjusting the influence of recent observations.
Specifically, it controls the rate at which the moving averages update,
allowing the mechanism to respond effectively to changes in the environment.
By incorporating the time scale into the algorithm, the mechanism can balance
between capturing short-term fluctuations and maintaining stability over
longer periods. The detailed steps of this unified homeostasis mechanism are
elaborated in the provided pseudocode (Algorithm 1).

Algorithm 1 Unified Homeostasis

0: target rate $\rho$, trigger types = {VPD, Exploration Bonus}

1: Initialize mean $\overline{x}\leftarrow 0$
variance$,\overline{x^{2}}\leftarrow 0$, mean transformed
$\overline{x^{+}}\leftarrow 0$ for each trigger

2: for $t\in\\{1,...,T\\}$ do

3: Set time scale of interest $\tau\leftarrow\min(t,\frac{5}{\rho})$

4: Set weight of the latest observation $\alpha\leftarrow\frac{1}{\tau}$

5: for each trigger type $i$ do

6: Get next signal value $x_{t}$

7: $\text{Update }\overline{x}\leftarrow(1-\alpha)\overline{x}+\alpha x_{t}$

8: $\text{Update
}\overline{x^{2}}\leftarrow(1-\alpha)\overline{x^{2}}+\alpha(x_{t}-\overline{x})^{2}$

9: $\text{Standardize
}x_{t}\leftarrow\frac{x_{t}-\overline{x}}{\sqrt{\overline{x^{2}}}}$

10: $\text{Exponentiate }x^{+}\leftarrow\exp(x_{t})$

11: $\text{Update transformed average
}\overline{x^{+}}\leftarrow(1-\alpha)\overline{x^{+}}+\alpha x^{+}$

12: $\text{Compute exploration probability
}p_{i}\leftarrow\min(1,\rho\frac{x^{+}}{\overline{x^{+}}})$

13: end for

14: $\text{Average probabilities
}\overline{p}\leftarrow\frac{1}{n}\sum_{i=1}^{n}p_{i}$

15: $\text{Sample }y_{t}\sim\text{Bernoulli}(\overline{p})$

16: end for

###  4.4 Value Discrepancy and State Counts (VDSC)

Given the challenges inherent to each one of the discussed approaches, our
proposed approach integrates the agent’s value state prediction errors with
the exploration bonus derived from hashed state counts. This integration aims
to overcome the limitations associated with relying solely on either VPD or
count-based methods, presenting a novel approach to determining when to
explore.

Combining all of the aforementioned components together, we can summarize our
proposed exploration strategy, named VDSC, as the following integration of
methodologies that can enhance the decision-making process of DRL agents: The
first component involves calculating the VPD values, which act as a proxy for
uncertainty in the agent’s predictions. This signal evaluates the discrepancy
between the agent’s expected rewards and the actual outcomes, providing
insight into how well the agent’s predictions align with reality. The second
element is the computation of the exploration bonus, designed to encourage the
exploration of less-visited, and therefore more novel, states. This approach
assumes that exploring unfamiliar states can reveal new learning opportunities
and potentially rewarding experiences, crucial for the agent’s development and
adaptability. Finally, the strategy includes a process that translates raw
signal values - VPD and exploration bonus - into a concrete exploration
decision using a unified homeostasis mechanism. This decision-making process
aims to balance the need for exploration with exploitation efficiency,
ensuring that the agent’s actions are both exploratory and informed. The final
pseudocode detailing VDSC exploration is outlined in Algorithm 2.

By combining these components, our strategy aims to address the exploration-
exploitation timing dilemma in DRL more effectively. It leverages uncertainty
and state novelty to guide the agent toward a balanced and informed
exploration path. This approach is expected to enhance learning performance,
particularly in complex environments where traditional exploration methods may
prove inadequate.

Algorithm 2 VDSC exploration strategy

0: VPD history length $k$, SimHash bits $\kappa$, exploration rate $t$

1: Define state preprocessor $g:\mathcal{S}\rightarrow\mathbb{R}^{D}$

2: Initialize matrix $A\in\mathbb{R}^{\kappa\times D}$ with entries drawn
i.i.d from $\mathcal{N}(0,1)$

3: Initialize hash table with values $n(\cdot)\equiv 0$

4: Initialize unified homeostasis instance $\mathcal{H}$ with target
exploration rate $t$

5: for timestep $t\in\\{1,...,T\\}$ do

6: Get current observed state $s_{t}$

7: Calculate state hash $\phi(s_{t})=\text{sgn}(A\cdot g(s_{t}))$

8: Calculate exploration bonus $(s_{t})=\frac{1}{\sqrt{n(\phi(s_{t}))}}$

9: Update counts $n(\phi(s_{t}))\leftarrow n(\phi(s_{t}))+1$

10: Calculate
$VPD(t-k,t)=V(s_{t-k})-\sum_{i=0}^{k-1}\gamma^{i}r_{t-i}-\gamma^{k}V(s_{t})$

11: Store current $V(s_{t})$ and $r_{t}$

12: Update $\mathcal{H}$ with $VPD$ and exploration bonus

13: Act according to exploration decision from $\mathcal{H}$

14: end for

##  5 Experiments

We will now outline our experimental setup, covering the environment, agent,
baselines, and hyperparameters. We evaluate VDSC against baseline methods on a
subset of Atari games, presenting both quantitative and qualitative results.
Additionally, we analyze the impact of individual trigger signals and the
temporal structure in exploratory behavior imposed by VDSC.

###  5.1 Experimental Setup

####  5.1.1 Environments.

We conduct an experimental comparison between VDSC and alternative exploration
methods using a subset of games from the Atari Learning Environment (ALE) [3].
Our evaluation spans four games: Pong, Frostbite, Gravitar, and Freeway, using
3 seeds per game trained over 100M in game frames. The choice of these games
is motivated as follows: the latter three environments are well-known to be
classified as hard exploration games [4], whereas Pong serves as a simpler,
easy exploration alternative with dense rewards. In Figure 4 we provide
additional results across the entire Atari game suite. Standard Atari pre-
processing techniques are applied as in [17], with the exception of sticky
actions which is set to 0.25 and the disabling of termination on life loss, as
suggested in [15]. The final state observed by the agent is transformed from
an initial sequence of $210\times 160$ RGB images to a stack of four $84\times
84\times 4$ grayscale images.

####  5.1.2 Agents.

We utilize the state-of-the-art DRL agent Rainbow [14], provided by the
Dopamine framework [7], as the backbone for our experiments to evaluate the
performance of VDSC. Two main considerations drive the selection of the
Rainbow agent. Firstly, it introduces an additional exploration strategy
baseline, Noisy Nets [12], for comparative analysis. Secondly, Rainbow
incorporates the Dueling Architecture [33], which estimates $V^{\star}(s)$
alongside the advantages of each individual action
$A(s,a)=Q^{\star}(s,a)-V^{\star}(s)$. This architectural choice is crucial as
it aligns with our focus on the network’s value estimates for calculating the
VPD at each timestep 111Note that several other alternatives to the Dueling
Architecture that estimate $V^{\star}(s)$ exist [25][13], all of these can be
easily integrated with our proposed exploration strategy..

####  5.1.3 Baselines.

To benchmark the effectiveness of VDSC, we compare it against three other
exploration strategies: $\epsilon$-greedy, Boltzmann, and Noisy Nets. In
$\epsilon$-greedy the agent selects a random action at each time step with a
set probability $\epsilon\leq 1$, otherwise the action with the highest
Q-value is selected. In contrast, Boltzmann samples an action based on a
distribution determined by applying the softmax function to the output layer
of the network. Lastly, Noisy Nets introduce stochasticity directly into the
network weights for more consistent exploration:
$w=\mu+\sigma\odot\varepsilon$, where $w$ is the weight, $\mu$ and $\sigma$
are parameters, and $\varepsilon$ is sample noise.

####  5.1.4 Hyperparameters.

To maintain the focus of our work on the timing of exploration, we strive to
maintain a fixed overall proportion of exploration steps whenever feasible.
This involves setting the same initial values and decay schedules for key
parameters such as $\epsilon$ in $\epsilon$-greedy, the temperature parameter
$\tau$ in Boltzmann exploration, and the target exploration rate in the
homeostasis instance. Throughout all Atari games, these parameters are
initialized to the same value of $1$ and follow a linear decay schedule over
the first 1 million game frames to a final value of $0.01$. Regarding VDSC, a
history length of $k=5$ was used when calculating the VPD, and we set the size
of the binary code $\kappa=256$ for compressing the states (based on the
recommendation from [30]). For Noisy Nets, we kept the original hyperparameter
$\sigma_{0}=0.5$, as in [12]. We refer the reader to the Supplementary
Materials for complete information on the hyperparameters used.

###  5.2 Quantitative Results

We begin by examining the performance of VDSC compared to the selected
baseline methods across the discussed Atari games. Additionally, we conduct an
ablation study on the same four Atari games to assess the influence of
individual trigger signals and their combined effect.

####  5.2.1 Comparison to Baseline Methods.

Figure 2 displays a comparative analysis of VDSC against the chosen baselines.
Across harder exploration games, notably Frostbite and Gravitar, VDSC
consistently outperforms all other methods. This superiority underscores the
efficacy of VDSC in managing exploration timing, particularly leveraging
information about the agent’s internal state in challenging exploration
scenarios.

####  5.2.2 Ablation Study.

Figure 2 also provides a breakdown of performance by individual signals
compared to their combination in VDSC. While each signal demonstrates
competitiveness individually against the baseline methods, their synergy in
VDSC yields significant performance improvements, especially evident in
Frostbite and Gravitar. These findings indicate that the combined signals
enable the agent to make more effective exploratory decisions, leading to
accelerated learning even with a simplistic combination method.

Figure 2: Average episode returns comparing VDSC against baseline methods in
addition to each individual trigger in isolation. Shaded regions represent 95%
confidence intervals over 3 random seeds. Figure 3: Top: Detailed overview of
exploration timings over 20 consecutive training episodes. White vertical bars
represent steps in which the agent chose to explore. Bottom: Corresponding
average trigger values tracked over the same 20 episodes.

###  5.3 Qualitative Results

Given our study’s focus on the timing of exploration, we delve into additional
qualitative results to provide deeper insights into VDSC’s behavior. Figure 3
showcases an analysis conducted over 20 consecutive training episodes using
the game Frostbite, captured at approximately 50 million training steps.

Frostbite presents a game screen with moving ice floes, hazards like birds and
fish, and the partially built igloo. The action space is defined by the
agent’s ability to move in four directions: up, down, left, and right. Points
are gained by jumping on ice floes and completing the igloo, but penalties are
given if the character falls into the water or collides with enemies. The game
is considered a hard exploration environment, given the need for platforming
skills and strategic planning to successfully navigate the hazards and build
the igloo. Motivated by VDSC results on the game, we aim to investigate the
exploratory behavior during training further.

In the top plot of Figure 3, each horizontal bar represents an individual
episode. Blue segments denote exploitation phases, while white vertical bars
indicate exploratory actions taken by the agent. Examining the detailed
temporal structure within episodes (top), a discernible pattern emerges:
exploration peaks around the 250-1000 episode step count, with another surge
observed towards the episodes’ end. This observed behavior aligns with the
tracked average values over the same 20 episodes (bottom), where there is a
noticeable spike in VPD around the 250-500 step count, followed by a gradual
decline throughout the episode durations. Conversely, the average exploration
bonus remains relatively low for the majority of episodes, steadily increasing
as the episodes near their conclusion. This uptick suggests that the agent
encounters more novel states as it approaches losing conditions, prompting
more frequent exploration attempts. This strategic increase in exploration
endeavors aims to uncover potentially better-performing policies.

It is noteworthy that the overall observed exploration proportion closely
matches that of other baselines, such as $\epsilon$-greedy, hovering around
0.01. This observation indicates that a structured and purpose-driven approach
to exploration timing, as exemplified by VDSC, can indeed yield enhanced
performance, as corroborated by our findings.

##  6 Discussion and Conclusions

We have introduced a novel exploration strategy (VDSC) that combines the
agent’s value state prediction errors with counts of the current hashed state,
thus balancing long-term uncertainty and state-specific novelty to guide the
timing of exploration. The conducted experiments across different environments
highlighted the significant role of exploration timing in agent performance
and also a significant performance gain over existing traditional exploration
methods. Our key contribution is the development of a novel exploration
strategy that leverages two distinct signals and a framework for combining
them to produce relevant exploration triggers. This approach has demonstrated
its potential in complex environments, outperforming traditional methods,
particularly where a more refined exploration strategy is required.

This study focuses primarily on value-based methods and their applicability to
game environments such as Atari. Extending this exploration strategy to policy
gradient methods offers a promising research direction. In policy gradients,
exploration is typically governed by stochastic policy updates. By integrating
VPD and exploration bonus values into the policy update mechanism, agents can
be incentivized to explore more when these values are high, indicating
uncertainty or novelty in the environment. This could be achieved by modifying
the policy’s entropy. An increase in the entropy of the policy when
uncertainty is elevated (VPD) or novel states are encountered (high
exploration bonus), should encourage the policy to explore more diverse
actions. Such modifications would allow the policy to dynamically balance
exploration and exploitation based on the uncertainty and novelty of the state
space, potentially leading to more robust and efficient learning.

As it was presented in [24], another possible way to gauge the agent’s
uncertainty is to use an ensemble of networks and measure the discrepancy
between them. Furthermore, the usage of a learned domain-specific hash
function might lead to further improvements in encoding relevant state
information, as it has been shown by [30].

Lastly, the way in which the signals are combined is also an open question,
with some immediate candidates being taking the maximum probability value
instead of the average, or perhaps introducing some sort of linear combination
which is optimized by an external meta-controller.

## References

  * [1] Auer, P.: Using confidence bounds for exploitation-exploration trade-offs. In: Journal of Machine Learning Research. pp. 397–422 (2002)
  * [2] Azar, M.G., Osband, I., Munos, R.: Minimax regret bounds for reinforcement learning. In: International Conference on Machine Learning. pp. 263–272. PMLR (2017)
  * [3] Bellemare, M.G., Naddaf, Y., Veness, J., Bowling, M.: The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research 47, 253–279 (2013)
  * [4] Bellemare, M., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., Munos, R.: Unifying count-based exploration and intrinsic motivation. Advances in neural information processing systems 29 (2016)
  * [5] Burda, Y., Edwards, H., Pathak, D., Storkey, A., Darrell, T., Efros, A.A.: Large-scale study of curiosity-driven learning. In: International Conference on Learning Representations (2018)
  * [6] Burda, Y., Edwards, H., Storkey, A., Klimov, O.: Exploration by random network distillation (2018)
  * [7] Castro, P.S., Moitra, S., Gelada, C., Kumar, S., Bellemare, M.G.: Dopamine: A research framework for deep reinforcement learning. arXiv preprint arXiv:1812.06110 (2018)
  * [8] Charikar, M.S.: Similarity estimation techniques from rounding algorithms. In: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. pp. 380–388 (2002)
  * [9] Dabney, W., Ostrovski, G., Barreto, A.: Temporally-extended $\varepsilon$-greedy exploration. In: International Conference on Learning Representations (2020)
  * [10] Dann, C., Neumann, G., Peters, J., et al.: Policy evaluation with temporal differences: A survey and comparison. Journal of Machine Learning Research 15, 809–883 (2014)
  * [11] Ecoffet, A., Huizinga, J., Lehman, J., Stanley, K.O., Clune, J.: Go-explore: a new approach for hard-exploration problems (2021)
  * [12] Fortunato, M., Azar, M.G., Piot, B., Menick, J., Hessel, M., Osband, I., Graves, A., Mnih, V., Munos, R., Hassabis, D., Pietquin, O., Blundell, C., Legg, S.: Noisy networks for exploration. In: International Conference on Learning Representations (2018)
  * [13] Haarnoja, T., Zhou, A., Abbeel, P., Levine, S.: Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In: International conference on machine learning. pp. 1861–1870. PMLR (2018)
  * [14] Hessel, M., Modayil, J., Van Hasselt, H., Schaul, T., Ostrovski, G., Dabney, W., Horgan, D., Piot, B., Azar, M., Silver, D.: Rainbow: Combining improvements in deep reinforcement learning. In: Proceedings of the AAAI conference on artificial intelligence. vol. 32 (2018)
  * [15] Machado, M.C., Bellemare, M.G., Talvitie, E., Veness, J., Hausknecht, M., Bowling, M.: Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research 61, 523–562 (2018)
  * [16] Ménard, P., Domingues, O.D., Jonsson, A., Kaufmann, E., Leurent, E., Valko, M.: Fast active learning for pure exploration in reinforcement learning. In: International Conference on Machine Learning. pp. 7599–7608. PMLR (2021)
  * [17] Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A.A., Veness, J., Bellemare, M.G., Graves, A., Riedmiller, M., Fidjeland, A.K., Ostrovski, G., et al.: Human-level control through deep reinforcement learning. nature 518(7540), 529–533 (2015)
  * [18] Osband, I., Aslanides, J., Cassirer, A.: Randomized prior functions for deep reinforcement learning. Advances in Neural Information Processing Systems 31 (2018)
  * [19] Osband, I., Blundell, C., Pritzel, A., Van Roy, B.: Deep exploration via bootstrapped dqn. Advances in neural information processing systems 29 (2016)
  * [20] Osband, I., Van Roy, B., Russo, D.J., Wen, Z., et al.: Deep exploration via randomized value functions. J. Mach. Learn. Res. 20(124), 1–62 (2019)
  * [21] O’Donoghue, B., Osband, I., Munos, R., Mnih, V.: The uncertainty bellman equation and exploration. In: International Conference on Machine Learning. pp. 3836–3845 (2018)
  * [22] Parisi, S., Tateo, D., Hensel, M., D’eramo, C., Peters, J., Pajarinen, J.: Long-term visitation value for deep exploration in sparse-reward reinforcement learning. Algorithms 15(3), 81 (2022)
  * [23] Pathak, D., Agrawal, P., Efros, A.A., Darrell, T.: Curiosity-driven exploration by self-supervised prediction. In: International conference on machine learning. pp. 2778–2787. PMLR (2017)
  * [24] Pislar, M., Szepesvari, D., Ostrovski, G., Borsa, D.L., Schaul, T.: When should agents explore? In: International Conference on Learning Representations (2021)
  * [25] Sabatelli, M., Louppe, G., Geurts, P., Wiering, M.A.: The deep quality-value family of deep reinforcement learning algorithms. In: 2020 International Joint Conference on Neural Networks (IJCNN). pp. 1–8. IEEE (2020)
  * [26] Sasso, R., Conserva, M., Rauber, P.: Posterior sampling for deep reinforcement learning. In: International Conference on Machine Learning. pp. 30042–30061. PMLR (2023)
  * [27] Schmidhuber, J.: Formal theory of creativity, fun, and intrinsic motivation (1990–2010). IEEE transactions on autonomous mental development 2(3), 230–247 (2010)
  * [28] Strehl, A.L., Littman, M.L.: An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences 74(8), 1309–1331 (2008)
  * [29] Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. The MIT Press, Cambridge, MA (1998)
  * [30] Tang, H., Houthooft, R., Foote, D., Stooke, A., Xi Chen, O., Duan, Y., Schulman, J., DeTurck, F., Abbeel, P.: # exploration: A study of count-based exploration for deep reinforcement learning. Advances in neural information processing systems 30 (2017)
  * [31] Tokić, M.: Adaptive $\epsilon$-greedy exploration in reinforcement learning based on value differences. Annual Conference on Artificial Intelligence pp. 203–210 (2010)
  * [32] Turrigiano, G.G., Nelson, S.B.: Homeostatic plasticity in the developing nervous system. Nature reviews neuroscience 5(2), 97–107 (2004)
  * [33] Wang, Z., Schaul, T., Hessel, M., Hasselt, H., Lanctot, M., Freitas, N.: Dueling network architectures for deep reinforcement learning. In: International conference on machine learning. pp. 1995–2003. PMLR (2016)
  * [34] Zhao, R., Tresp, V.: Curiosity-driven experience prioritization via density estimation (2020)

Figure 4: Average episode returns for all Atari games. Shaded regions
represent 95% confidence intervals over 3 random seeds.