# Strong slowing down of the thermalization process of solids
interacting in extreme near-field regime

M. Reina  R. Messina  P. Ben-Abdallah<EMAIL_ADDRESS>Laboratoire
Charles Fabry, UMR 8501, Institut d’Optique, CNRS, Université Paris-Saclay, 2
Avenue Augustin Fresnel, 91127 Palaiseau Cedex, France.

(August 27, 2024)

###### Abstract

When two solids at different temperatures are separated by a vacuum gap they
relax toward their equilibrium state by exchanging heat either by radiation,
phonon or electron tunneling, depending on their separation distance and on
the nature of materials. The interplay between this exchange of energy and its
spreading through each solid entirely drives the relaxation dynamics. Here we
highlight a significant slowing down of this process in the extreme near-field
regime at distances where the heat flux exchanged between the two solids is
comparable or even dominates over the flux carried by conduction inside each
solid. This mechanism, leading to a strong effective increase of the system
thermal inertia, should play an important role in the temporal evolution of
thermal state of interacting solids systems at nanometric and subnanometric
scales.

The relaxation of bodies in mutal interaction which are initially prepared in
two different thermal states is an important problem in physics both on a
fundamental Evans ; Schuster ; Prigogine ; Jin ; Reid ; MessinaPRB2013 ;
superdiff1 ; superdiff2 ; eigen ; phonon  and practical point of view Guha ;
logic ; refrige ; Yu ; Transi ; Bhatia . When these bodies are separated by a
vacuum gap this relaxation is mediated by radiative heat exchange or by
tunneling of heat carriers (phonons, electrons, excitons…). Usually the system
evolves toward a state of equipartition of energy and uniform temperature by
maximizing its entropy Kubo . This corresponds to an evolution of all
particles inside the system toward the same average energy through various
interaction mechanisms even if their initial energies are very different. This
evolution is well described for classical systems by the Boltzmnan equation
for the probability density of particles, over all their possible states in
the phase space.

In this Letter we investigate the relaxation dynamics of systems exchanging
heat in a strong-interaction regime. To explore this thermalization process we
consider two solids out of thermal equilibrium which exchange heat through a
nanometric or subnanometric vacuum gap in the transition domain between the
radiative and the conductive regime Chen ; Reddy ; Kittel  also called extreme
near-field regime. In this range of separation distance energy exchange
competes or even dominates Messina2016 ; Reina2020  with respect to the
conductive heat transport within the bodies themselves. In this regime of
strong interaction we demonstrate that counterintuitively the relaxation time
of the system is dramatically extended compared to a weak-coupling situation
and demonstrate that the relaxation time of the system towards thermal
equilibrium is dramatically extended.

Figure 1: Sketch of system. Two solid films out of thermal equilibrium having
temperatures $T_{1}(z,t)$ and $T_{2}(z,t)$ are separated by a vacuum gap of
thickness $d$. They relax by exchanging heat either by radiation, phonon or
electron tunneling depending on the separation distance and the nature of the
materials. This transmitted energy is spreaded out through the films thanks to
a diffusion process.

To address this problem let us consider two identical solid films as sketched
in Fig. 1. When the heat transport inside these films is governed by a simple
diffusion process the spatio-temporal evolution of the films temperature can
be obtained by solving the energy balance equation

$\rho C\;\frac{\partial T_{k}(z,t)}{\partial t}=-\nabla\cdot[\kappa\nabla
T_{k}(z,t)]+P^{j\rightarrow k}(z,t),$ (1)

where $\rho$ denotes the mass density of the films, $C$ their specific heat
capacity, $\kappa$ their thermal conductivity and $P^{j\rightarrow k}(z,t)$
the power density received locally by one film from the opposite one, This
power density, as expected, depends implicitly on the entire temperature
profiles $T_{k}(z,t)$ at each time $t$. It is clear that the time evolution of
the temperature depends on the interplay between the inner transport mechanism
and the heat exchange between the two films. When the flux carried by
conduction within the films dominates with respect to the flux exchanged
between the two films, the temperature profiles stay uniform at any time
within each film and then the two temperatures obey the following equation

$\rho C\frac{dT_{k}}{dt}=P^{j\rightarrow k}[T_{j}(t),T_{k}(t)],$ (2)

where now $P^{j\rightarrow k}[T_{j}(t),T_{k}(t)]$ corresponds to the total
power (per unit volume) transferred from film $j$ to film $k$, function of the
two temperatures $T_{j}$ and $T_{k}$ at time $t$. Close to thermal equilibrium
the RHS of this equation can be expressed in terms of the radiative thermal
conductance

$G=\lim_{\Delta T\rightarrow 0}\frac{\phi^{j\rightarrow k}[T_{k}(t)+\Delta
T,T_{k}(t)]}{\Delta T},$ (3)

where $\phi^{j\rightarrow k}$ is the net flux (per surface unit) received by
the film $k$. This allows us to recast Eq. (2) under the form

$\rho CL\frac{dT_{k}}{dt}=-G[T_{k}(t)-T_{j}(t)].\\\ $ (4)

If we assume (see Fig. 1) that body 2 is in contact with a thermostat at
constant temperature $T_{2}$, the only temperature varying in time is $T_{1}$,
which simply evolves as

$T_{1}(t)=T_{1}(0)\exp(-t/\tau).$ (5)

where $T_{1}(0)$ is the initial value of the temperature of slab 1, and
$\tau=\rho CL/G$ denotes the relaxation time. Hence we see that one way to
slow down the thermalization process consists in reducing the coupling
strength between the two films, encoded in the conductance $G$. In the
following, we show that a strong slowing down of relaxation process can also
be observed in some situations when the energy exchange between the two films
is strongly coupled to the conduction mechanism within each one of them.

To demonstrate this result let us first consider the relaxation of two polar
films separated by a gap of nanometric thickness. At such separation distance
the films interact only by radiation through the tunneling of evanescent
photons Polder1973 . The radiative power density $P_{r}^{j\rightarrow k}$
dissipated in the film $k$ at point $z$ and associated with the sources in the
other body can be calculated from the average monochromatic flux of the
Poynting vector at this point
$\langle\mathbf{S}^{k}(z,\omega)\rangle=2\,\text{Re}\langle\mathbf{E}^{k}(z,\omega)\times\mathbf{H}^{k*}(z,\omega)\rangle$
as

$P_{r}^{j\rightarrow
k}(z)=-\int_{0}^{\infty}d\omega\,\nabla\cdot\langle\mathbf{S}^{k}(z,\omega)\rangle,$
(6)

where $\langle.\rangle$ denotes the statistical averaging. According to
fluctuational-electrodynamics theory RytovBook1989 , for isotropic media and
neglecting non-local effects, the Poynting vector reads

$\begin{split}\langle
S^{k}_{n}&(z,\omega)\rangle=i\frac{\omega^{2}}{c^{2}}\eta_{njl}\\\
&\,\times\int_{\text{sources}}dz^{\prime}\epsilon^{\prime\prime}(z^{\prime},\omega)\Theta[T(z^{\prime}),\omega]\mathds{G}^{EE}_{j,l}\mathds{G}^{HE*}_{n,l},\end{split}$
(7)

where the integral extends over all sources points. In Eq. (7), $\eta_{njl}$
denotes the ${njl}$ component of Levi-Civita tensor ,
$\Theta(T,\omega)=\hbar\omega/[e^{\frac{\hbar\omega}{k_{B}T}}-1]$ is the mean
energy of a Planck oscillator at temperature $T$, $\epsilon^{\prime\prime}$
the imaginary part of the permittivity in the emitting body while
$\mathds{G}^{EE}=\mathds{G}^{EE}(z,z^{\prime})$ and
$\mathds{G}^{HE}=\mathds{G}^{HE}(z,z^{\prime})$ are the full electric-electric
and electric-magnetic dyadic Green tensors Tomas  at frequency $\omega$,
taking into account all scattering events within the system between the
emitter and the point where energy is dissipated.

As recently established Reina2020  the radiative power dissipated through a
polar film from its surface is typically reduced by one order of magnitude
through a distance of few nanometers from the vacuum gap, so that the
radiative transfer can reasonably be assumed to be purely surfacic. In this
case, by assuming the thermal conductivity independent of the position and the
temperature, and by introducing the auxiliary functions
$F_{k}(z,t)=T_{k}(z,t)-T_{2}$, the energy balance equation can be recast into
the form

$\rho CL\frac{\partial F_{k}(z,t)}{\partial
t}=-\kappa\>L\frac{\partial^{2}F_{k}(z,t)}{\partial z^{2}}+G_{r}\>F_{k}(z,t),$
(8)

where in this scenario the conductance between the two films reduces to the
radiative conductance $G_{r}$ defined as

$G_{r}=\int\limits_{0}^{\infty}\frac{\mathrm{d}\omega}{2\pi}\frac{d\Theta}{dT}(\omega,T)\sum_{p}\int\limits_{0}^{\infty}\frac{\mathrm{d}\kappa}{2\pi}\kappa\,\mathcal{T}_{p}(\omega,\kappa,d),$
(9)

where $\kappa$ is the modulus of the component of the wavector parallel to the
exchange surface and $p$ is the state of polarization. Here
$\mathcal{T}_{p}(\omega,\kappa,d)$ denotes the energy transmission coefficient
for the mode $(\omega,\kappa)$ in polarization $p$ between the films, which
can be expressed in terms of reflection and transmission coefficients $r_{ip}$
and $t_{ip}$ of the two slabs as Polder1973

$\mathcal{T}_{p}(\omega,k,d)=\begin{cases}\frac{(1-|r_{1p}|^{2}-|t_{1p}|^{2})(1-|r_{2p}|^{2}-|t_{2p}|^{2})}{|D_{p}|^{2}},&c\kappa<\omega,\\\
\frac{4\,\text{Im}(r_{1p})\text{Im}(r_{2p})e^{-2|k_{z}|d}}{|D_{p}|^{2}},&c\kappa>\omega,\end{cases}$
(10)

$k_{z}$ being the $z$ component of the wavevector
and$D_{p}=1-r_{1p}r_{2p}e^{2ik_{z}d}$ the Fabry-Pérot factor of the cavity.

As for the initial conditions, we impose $F_{1}(z,0)=\Delta T$ and
$F_{2}(z,0)=0$, which correspond to the fact the initial temperature profiles
in the two slabs are uniform [$T_{1}(z,0)=T_{2}+\Delta T$ and
$T_{2}(z,0)=T_{2}$]. Concerning the boundary conditions, we set
$F_{2}(L+d,t)=0$ fixing the temperature at $T_{2}$ for the edge of the right
slab in contact with the thermostat, while $\partial_{z}F_{1}(-L,t)=0$
imposing a vanishing flux at each instant at the left end of the first slab
(adiabatic boundary condition). Notice that this condition is based on the
fact that the interactions in the far-field regime with the bath are
negligible when the distance $d$ between the slabs is in the near-field
regime. Moreover, we impose the two further boundary conditions
$\partial_{z}F_{1}(0,t)=-G_{r}/\kappa[F_{1}(0,t)-F_{2}(d,t)]$ and
$\partial_{z}F_{2}(d,t)=-G_{r}/\kappa[F_{1}(0,t)-F_{2}(d,t)]$ ensuring the
flux continuity between the two slabs. The solution of the partial
differential equations (8) reads

$\begin{split}F_{1}(z,t)&=8\Delta T\sum_{n=1}^{\infty}\frac{\sin
x_{n}\cos^{2}x_{n}}{4x_{n}+\sin(4x_{n})}\\\
&\times\cos\Bigl{[}\frac{x_{n}(z+L)}{L}\Bigr{]}\exp\Bigl{[}-\frac{x_{n}^{2}\kappa}{\rho
CL^{2}}t\Bigr{]},\\\ F_{2}(z,t)&=-8\Delta
T\sum_{n=1}^{\infty}\frac{\sin^{2}x_{n}\cos x_{n}}{4x_{n}+\sin(4x_{n})}\\\
&\times\sin\Bigl{(}\frac{x_{n}z}{L}\Bigr{)}\exp\Bigl{[}-\frac{x_{n}^{2}\kappa}{\rho
CL^{2}}t\Bigr{]},\end{split}$ (11)

where $x_{n}$ are the solutions of the transcendental equation $x\tan
2x=G_{r}L/\kappa$. We can associate each term with a partial relaxation time
$\tau_{n}=\rho CL^{2}/(x^{2}_{n}\kappa)$. It can be easily shown that
$x_{1}<x_{n}$ and thus $\tau_{1}>\tau_{n}$ for all $n\geq 2$, so that the
first term in these series is the dominant one for large $t$.

Figure 2: Time evolution of the average temperature of the hot film in a
system made of two coupled polar films of thickness $L=100\,\mu$m separated by
a vacuum gap of thickness $d=1\,$nm. The black (red) solid curve shows the
evolution for SiO2 (SiC) coupled films. The black (red) dashed curves show the
evolution predicted by the PvH theory (perfectly conducting solids). The
intial temperature of the cold film is $T_{2}=300\,$K and the initial
temperature difference is $\Delta T=100\,$K. The mass density, the specific
heat and the thermal conductivity of SiC and SiO2 are
$\rho_{\text{SiC}}=3200\,$kg$\cdot$m-3,
$C_{\text{SiC}}=600\,$J$\cdot$kg${}^{-1}\cdot$K-1,
$\rho_{\text{SiO}_{2}}=2650\,$kg$\cdot$m-3,
$C_{\text{SiO}_{2}}=680\,$J$\cdot$kg${}^{-1}\cdot$K-1,
$\kappa_{\text{SiC}}=120\,$W$\cdot$m${}^{-1}\cdot$K-1 and
$\kappa_{\text{SiO}_{2}}=1.2\,$W$\cdot$m${}^{-1}\cdot$K-1.

The ratio $GL/\kappa$ quantifies the relative importance of the radiative and
conductive transport [for two silicon carbide (SiC) films this ratio is 1.1,
while it grows up to 312.5 for two silica (SiO2) films]. The appearance of the
ratio $GL/\kappa$ as a key parameters allows us to anticipate a reduction of
the effect when reducing the slab thickness $L$ or when increasing the
separation distance $d$ (coupling strength) between them SupplMat .

When the heat transport by conduction is much more efficient than the
transport by radiation, the temperature within each film is almost uniform at
any time. In this case the solution of Eq. (8) is similar to that of Eq. (4)
and the temperature profile is the same as the one predicted by the Polder and
van Hove (PvH) theory of radiative heat transfer between perfectly conducting
solids. However, the situation radically changes when the magnitude of
radiative heat transfer is comparable or even larger than the heat transfer by
conduction within the films. In Fig. 2 we compare the time evolution of the
mean temperature $\overline{T}_{1}(t)=(1/L)\int T_{1}(z,t)dz$ inside the left
(hot) slab obtained by solving Eq. (1) by means of a finite-difference method
SupplMat  to the predictions from the PvH theory for SiC and SiO2 films. It
can be noticed that the deviation between the two temperatures profiles is
more pronounced for two SiO2 slabs compared to SiC slabs. As anticipated
previously, this is due to the fact that the thermal conductivities of SiC and
SiO2 samples are strongly different. The relatively small conductivity of SiO2
leads to a strong deviation from the PvH predictions. Moreover, as shown in
the inset of Fig. 2, we see that the time evolution of
$\overline{T}_{1}-T_{2}\,$ is exponentially decaying as predicted by the
analytical solution (11) and the decay rate of the temperature corresponds to
the relaxation time $\tau_{1}$. Notice also that the comparaison in the inset
of the solution of Eq. (8) with the exact solution of Eq. (1) obtained using a
finite-difference method demontrates that the near-field radiative transfer is
indeed a surface phenomenon. As shown in the inset of Fig. 2, the relaxation
dynamics is more than one order of magnitude slower when the near-field heat
transfer is comparable to the conductive transfer inside the films, showing
that the coupling acts as an additional source of thermal inertia.

Figure 3: Temperature profile as a function of time in the hot film of a
system made of two coupled polar films of thickness $L=100\,\mu$m. The dashed
lines correspond to the temperature predicted by the PvH theory. (a) SiC films
separated by a $1\,$nm-thick vacuum gap. (b) Same configuration with SiO2
films.

As far as the temperature profile is concerned, we see in Fig. 3 that it
differs from the uniform profile especially when the radiative transfer
dominates with respect to the conductive transport, as in the configuration of
coupled SiO2 films. As we can see, a non-negligible temperature profile
appears through the slab because of the diffusion process in both materials.
Althougth the heat spreads inside the films by conduction, the temperature
profiles are, of course, not linear because of the interplay between the
diffusion process and the near-field heat transfer. For SiC films we also show
(dashed lines) the value $T_{\text{PvH}}$ of the (uniform) temperature
predicted by the PvH model at the same moments, while for SiO2 this comparison
has been omitted since in this case the two relaxation processes take place at
two very different time scales, as shown in Fig. 2. Indeed in this case, after
only $0.2\,$ms the hot film is already thermalized according to the
predictions of PvH theory, while a hundred-fold larger time is required when
the near-field radiative heat exchange is competing with the diffusion
process.

Figure 4: Time evolution of the average temperature of the hot film in a
system made of two coupled gold films of thickness $L=100\,\mu$m at
subnanometric distances and comparison with the temperature evolution (dashed
curves) without coupling. The intial temperature of the cold film is
$T_{2}=120\,$K and the initial temperature difference is $\Delta T=160\,$K.
The gold mass density is $\rho=19300\,$kg$\cdot$m-3 and its specific heat
capacity is $C=128\,$J$\cdot$kg${}^{-1}\cdot$K-1 .

So far we limited ourselves to a transfer between the two solids mediated by
photon tunneling. We now consider the thermalization process in the case of
two metallic films interacting through electrons tunneling. In fact, it has
been recently shown messina_heat_2018  that in this scenario the flux carried
by electrons at subnanometric distances surpasses by several orders of
magnitude the flux carried by photons and can therefore surpass the conductive
(phononic) flux inside the metals. The electronic thermal conductance due to
electron tunneling can be easily calculated using the effective potential
barrier associated with the vacuum gap between the two metals. For two
identical metals without bias voltage applied through the system the effective
potential is a simple rectangular barrier and the transmission probability
$\mathcal{T}(E_{z},d)$ at distance $d$ of electrons of normal energy $E_{z}$
through this barrier reads Tannoudji

$\mathcal{T}(E_{z},d)=\frac{4E_{z}(E_{z}-V)}{4E_{z}(E_{z}-V)+V^{2}\sin^{2}\bigl{(}k_{2z}(E_{z},V)d\bigr{)}},$
(12)

where $k_{2z}(E_{z},V)=\sqrt{2m_{e}(E_{z}-V)}/\hbar$ denotes the normal
components of wavector inside the gap ($m_{e}$ being the electron mass) and
the barrier height is written here as $V(d)=V_{\text{eV}}(d)+E_{F}$, $E_{F}$
being the Fermi energy ($E_{F}=5.53\,$eV for gold) and $V_{\text{eV}}$ a
distant dependent function for which the data taken from Kiejna  have been
fitted from DFT calculations with the log-scale law
$V_{\text{eV}}(d)=V_{0}\ln(1+d/1\text{\AA})$ ($V_{0}=1.25\,$eV for gold). It
follows that the heat flux carried by electrons by tunneling effect can be
calculated by summing over all energies $E_{z}$ in the direction normal to the
surface. This allows us to define the electronic heat conductance as

$G_{e}=\int_{0}^{\infty}dE_{z}E_{z}\frac{\partial N(E_{z},T)}{\partial
T}\mathcal{T}(E_{z},d),$ (13)

where $N(E_{z},T)dE_{z}$, with
$N(E_{z},T)=\frac{m_{e}k_{B}T}{2\pi^{2}\hbar^{3}}\ln[1+\exp(-(E_{z}-E_{F})/k_{B}T)]$,
denotes the number of electrons in the metal at temperature $T$ with a normal
energy between $E_{z}$ and $E_{z}+dE_{z}$ across a unit area per unit time.

This conductance can reach values about six orders of magnitude larger than
$G_{r}$ for gold films at separation distances of few Angstroms
messina_heat_2018 . In the presence of electron tunneling, the energy-balance
equation (8) remains valid, provided that the permutation
$G_{r}\leftrightarrow G_{e}$ is made. For two gold films, the ratio
$G_{e}L/\kappa$ equals 2.1, 306.5 and 871 for separation distances
$d=5\text{\AA}$, $d=2\text{\AA}$ and $d=1\text{\AA}$, respectively. This
suggests a strong effect of coupling mechanism on the relaxation dynamics. In
Fig. 4 we compare the time evolution of the average temperature profile for
the hot film in a system of two gold films with and without coupling between
heat conduction and heat transfer by electron tunneling. Unlike polar films
interacting by radiation, here the relaxation process toward thermal
equilibrium is much faster by two orders of magnitude. But more interesting is
the impact of coupling on the relaxation time. At a distance $d=5\text{\AA}$
($G_{e}L/\kappa=2.1$) this difference between the scenarios with and without
coupling is relatively modest and the coupling slows down the thermalization
process by approximatly a factor 2. On the other hand, at closer separation
distances this slowdown becomes remarkable, reaching about three orders of
magnitude. Notice that for these distances the temporal evolutions of the
average temperatures are almost indistinguishable (red and black solid curves)
since the $x_{n}$ in the solution (11) of the energy-balance equation (8) are
really close to the asymptotic value (i.e. large value of $G_{e}L/\kappa$).

In conclusion we have demonstrated a strong impact of the interplay between
the heat transfer in extreme near-field regime between two solids and the heat
spreading mechanism by conduction inside these media. When the thermal
conductance of heat exchange through the separation gap is comparable or
dominates over the conductance associated with the diffusive process inside
the solids, the thermalization of these media is strongly slowed down. In this
case the relaxation time can be larger even by several orders of magnitude
than in the classical situation where conduction is the dominant mechanism.
This effect should play an important role in the fields of active thermal
management at nanoscale, pyroelectric energy conversion in extreme near-field
regime, nanoscale heat-engines or for the Boolean treatment of information
with heat at nanoscale.

###### Acknowledgements.

P. B.-A. acknowledges discussions with S.-A. Biehs from Carl von Ossietzky
Universität, Germany.

## References

  * (1) D. J. Evans, D. J. Searles, and S. R. Williams, _Dissipation and the relaxation to equilibrium_ , J. Stat. Mech.: Theory Exp. P07029 (2009).
  * (2) H. G. Schuster, _Deterministic Chaos: An Introduction_ (Wiley, New York, 1995).
  * (3) I. Prigogine, _From Being to Becoming: Time and Complexity in the Physical Sciences_ , (Freeman, San Franciscom, 1980).
  * (4) F. Jin et al., _Equilibration and thermalization of classical systems_ , New J. Phys. 15, 033009 (2013).
  * (5) J. C. Reid, D. J. Evans, and D. J. Searles, _Beyond Boltzmann’s H-theorem: demonstration of the relaxation theorem for a non-monotonic approach to equilibrium_ , J. Chem. Phys. 136, 021101 (2012).
  * (6) R. Messina, M. Tschikin, S.-A.Biehs, and P. Ben-Abdallah, _Fluctuation-electrodynamic theory and dynamics of heat transfer in systems of multiple dipoles_ , Phys. Rev. B 88, 104307 (2013).
  * (7) P. Ben-Abdallah, R. Messina, S.-A. Biehs, M. Tschikin, K. Joulain, and C. Henkel, _Heat Superdiffusion in Plasmonic Nanostructure Networks_ , Phys. Rev. Lett. 111, 174301 (2013).
  * (8) I.Latella et al., _Ballistic near-field heat transport in dense many-body systems_ , Phys. Rev. B 97, 035423 (2018).
  * (9) S. Sanders et al., _Near-Field Radiative Heat Transfer Eigenmodes_ , Phys. Rev. Lett. 126, 193601 (2021).
  * (10) S. Sadasivam, M. K. Y. Chan, and P. Darancet, _Theory of Thermal Relaxation of Electrons in Semiconductors_ , Phys. Rev. Lett. 119, 136602 (2017).
  * (11) B. Guha et al., _Near-Field Radiative Cooling of Nanostructures_ , Nano Lett. 12, 4546 (2012).
  * (12) P. Ben-Abdallah and S.-A. Biehs, _Towards Boolean operations with thermal photons_ , Phys. Rev. B 94, 241401(R) (2016).
  * (13) K. Chen, P. Santhanam, and S. Fan, _Near-Field Enhanced Negative Luminescent Refrigeration_ , Phys. Rev. Appl. 6, 024014 (2016).
  * (14) R. Yu, A. Manjavacas, and F. J. García de Abajo, _Ultrafast radiative heat transfer_ , Nat. Commun. 8, 1 (2017).
  * (15) I. Latella et al., _Dynamical Response of a Radiative Thermal Transistor Based on Suspended Insulator-Metal-Transition Membranes_ , Phys. Rev. Appl. 11, 024004 (2019).
  * (16) B. Bhatia, H. Cho, J. Karthik, J. Choi, D. G. Cahill, L. W. Martin and W. P. King, _High Power Density Pyroelectric Energy Conversion in Nanometer-Thick BaTiO 3 Films_, Nanoscale and Microscale Thermophys. Eng. 20, 137 (2016).
  * (17) R. Kubo, M. Toda, and N. Hashitsume, _Statistical Physics II: Nonequilibrium Statistical Mechanics_ , vol 31, Springer Series in Solid–State Science, (Springer, New York, 1985).
  * (18) V. Chiloyan, J. Garg, K. Esfarjani, and G. Chen, _Transition from near-field thermal radiation to phonon heat conduction at sub-nanometre gaps_ , Nat. Commun. 6, 6755 (2015).
  * (19) K. Kim et al.,_Radiative heat transfer in the extreme near field_ , Nature 528, 387 (2015).
  * (20) K. Kloppstech et al.,_Giant heat transfer in the crossover regime between conduction and radiation_ , Nat. Commun. 8, 14475 (2017).
  * (21) R. Messina, W. Jin, and A. W. Rodriguez, _Strongly coupled near-field radiative and conductive heat transfer between planar bodies_ , Phys. Rev. B 94, 121410(R) (2016).
  * (22) M. Reina, R. Messina, and P. Ben-Abdallah, _Conduction-radiation coupling between two closely-separated solids_ , Phys. Rev. Lett. 125, 224302 (2021).
  * (23) D. Polder and M. van Hove, _Theory of Radiative Heat Transfer between Closely Spaced Bodies_ , Phys. Rev. B 4, 3303 (1971).
  * (24) S. M. Rytov, Y. A. Kravtsov, and V. I. Tatarskii, _Principles of Statistical Radiophysics_ , Vol. 3 (Springer, New York, 1989).
  * (25) M. S. Tomaš, _Green function for multilayers: Light scattering in planar cavities_ , Phys. Rev. A 51, 2545 (1995).
  * (26) See EPAPS Document No. [number will be inserted by publisher] for a description of the finite-difference method used to solve Eq. (1) and of the dependence of the mean temperature of films on their separation distance and on their thickness.
  * (27) R. Messina, S.-A. Biehs, T. Ziehm, A. Kittel, and P. Ben-Abdallah, Heat transfer between two metals through subnanometric vacuum gaps, arXiv:1810.02628 (2018).
  * (28) C. Cohen-Tannoudji, J. Dupont-Roc, and G. Grynberg, _Atom-photon interactions_ (Wiley, New York, 1992).
  * (29) A. Kiejna, _Potential barrier for the metal-vacuum-metal tunneling electrons_ , Ultramicroscopy 42, 231 (1992).
  * (30) P. Zhang, _Scaling for quantum tunneling current in nano- and subnano-scale plasmonic junctions_ , Sci. Rep. 5, 9826 (2015).
  * (31) J. Marschall and A. Majumdar, _Charge and energy transport by tunneling thermoelectric effect_ , J. Appl. Phys. 74, 4000 (1993).


#  Motion Planning for Identification of Linear Classifiers

Aneesh Raghavan and Karl Henrik Johansson *Research supported by the Swedish
Research Council (VR), Swedish Foundation for Strategic Research (SSF), and
the Knut and Alice Wallenberg Foundation. The authors are with the Division of
Decision and Control Systems, Royal Institute of Technology, KTH, Stockholm.
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

A given region in 2-D Euclidean space is divided by a unknown linear
classifier in to two sets each carrying a label. The objective of an agent
with known dynamics traversing the region is to identify the true classifier
while paying a control cost across its trajectory. We consider two scenarios:
(i) the agent is able to measure the true label perfectly; (ii) the observed
label is the true label multiplied by noise. We present the following: (i) the
classifier identification problem formulated as a control problem; (ii)
geometric interpretation of the control problem resulting in one step modified
control problems; (iii) control algorithms that result in data sets which are
used to identify the true classifier with accuracy; (iv) convergence of
estimated classifier to the true classifier when the observed label is not
corrupted by noise; (iv) numerical example demonstrating the utility of the
control algorithms.

##  I Introduction

###  I-A Motivation

Duality between control and learning (in a broad sense, including estimation
and inference problems) has been well studied in the literature. In [1],
duality between estimation and control is studied for general stochastic
control problems. In [2], exploration vs exploitation has been studied through
the control of a meta- parameter in reinforcement learning problems. [3]
studies dual control problems where knowledge gained through control actions
is explicitly defined. In [4], dual control techniques have been applied to
approximate the intractable aspects of Bayesian RL, leading to structured
exploration strategies that differ from standard RL. In [5], stochastic model
predictive control is presented in the dual control paradigm. More recently
dual control has been applied to active uncertainty learning in human robot
interaction, [6]. In all these problems there, is uncertainty in the model or
the cost function that is being actively learnt through control actions.

Parallels between model predictive control and algorithms in A.I have been
drawn, [7]. Learning theory has been extensively applied to control problems;
special neural networks and deep networks have been used extensively in system
identification and to approximate solutions to control problems, [8], [9],
[10]. Systems and control theory however has not been applied to its full
potential to learning theory. A hypothesis that is being explored currently
is, learning problems could benefit from being formulated as control problems
by channelizing feedback to reduce the quantity of data required to solve the
learning problem efficiently and accurately.

Adaptive sampling is closely related to the field of active learning, however
the former operates in the context supervised learning while the latter is
associated with semi-supervised learning. Adaptive sampling for classification
has been studied in [11], [12], [13], where sequential sampling algorithms are
presented to enhance the learning process. In [14], adaptive sampling has been
applied to hyperspectral image classification leading to improvement from
state of the art. Learning unknown environment is a crucial part of marine
robotics. Adaptive sampling methods have been used to survey and learn about
algal bloom, water quality models, etc in [15], [16], [17], and [18].

Given the above context, the problem that we consider is the identification of
certain aspects of an agents environment that is unkown. Unlike traditional
dual control which deals with uncertainty in the system or the cost functions
and learning the same, we consider learning of the environment. The problem
considered has potential application in marine robotics as well, as described
above. In our previous work, [19] we considered path planning for
identification of functions in an agents surroundings.

###  I-B Problem Considered

The problem considered is as follows. A given region in two dimensional space
is divided into two regions by a straight line, Figure 1. The true classifier
divides the state space into two sets, $\mathcal{X}$, where the true label is
$1$ and, $\mathcal{X}^{c}$, where the true label is $-1$. Every point in the
region “orange” carries the label $1$ while every point in the alternate
region “blue” carries the label $-1$. Every point on the straight line that
divides the region carries the label $0$. Four points, $p_{1},p_{2},p_{3}$,
and $p_{4}$, with their true labels are given by an oracle. In Figure 1, the
true labels of $p_{1}$ and $p_{4}$ are $1$ while that of $p_{2}$ and $p_{3}$
are $-1$. The true classifier is parameterized by its slope, $\rho^{*}$, and
intercept, $c^{*}$. An agent with known dynamics traverses the region by
paying a control cost. We consider two measurement models: (i) the agent is
able to measure the true label perfectly (deterministic) (ii) the measurement
gets corrupted by noise; the measured label is the true label flipped ($1$ to
$-1$ and $-1$ to $1$) with a certain probability (stochastic). Given the
measurement model, the objective of the agent starting at the point $p_{1}$ is
to follow a trajectory during which it collects $m$ data points which are
optimal for the identification of the classifier while simultaneously
minimizing its control costs.

One possible path that could be taken by the agent is depicted in Figure 1.
The agent collects $6$ data points, apart from the $4$ given, $3$ of each
label. The $10$ data points would subsequently be used to estimate the
classifier. The four initial points provided by the oracle are assumed to be
“far” apart from each other. They provide an initial estimate of the
classifier and a region of the $2-D$ space to be explored by the agent to
refine the estimate and identify the classifier more accurately. The key idea
that we would like to explore is that rather than collecting large number of
data samples from both regions for accurate estimation, is it possible to
strategically sample few data points which leads to the same accurate
estimation as the large data set. Thus, problem considered here can be
interpreted as an adaptive sampling problem which is restricted by the agent’s
dynamics.

Figure 1: Schematic for the motion planning problem

###  I-C Contributions

We formulate the identification problem of the true classifier as described
above has a control problem in both the deterministic and stochastic
scenarios. For the latter, we present an explicit construction of the
probability space. The formulated control problems are analyzed and the
associated challenges and drawbacks are presented. We present a geometric
interpretation of the problem using 2D analytic geometry. Utilizing the
geometric ideas, we formulate one step control problems which can be solved in
a numerically efficient manner. For the stochastic scenario, we derive the
equations for propagation of the probability that the true parameters
characterizing the true classifier belongs to a given set in the parameter
space. We present separate control algorithms (a “greedy” approach) for
noiseless and noisy data to solve the identification problem which involves
solving the one step control problems formulated before. The data set obtained
by executing the control algorithm is used to identify the classifier. In the
deterministic case, we prove that the classifier identified converges to the
true classifier, i.e., the estimated parameters of the classifier converges to
the true classifier. In stochastic case, the data collected results in sets to
which the true parameters belongs to with high probability. We present an
example for both cases illustrating the control algorithms and the resulting
classifiers.

###  I-D Outline

In Section II, we present the formulation of the identification problem as a
control problem. In Section III, we present the geometric interpretation of
the identification problem and the associated one step control problems. In
section IV, we present the control algorithms and the proof of convergence to
true classifier in the deterministic scenario. In Section V, we present a
numerical example for both scenarios which demonstrates the application of the
control algorithm. In Section VI, we summarize the work presented in the paper
and discuss future work. Given a collection of sets $\mathfrak{B}$, we denote
the smallest $\sigma$ algebra generated by it as $\sigma(\mathfrak{B})$.

##  II Problem Formulation

In this section, we present the abstraction of the problem discussed in
subsection I-B .

###  II-A Deterministic Scenario: Abstraction

####  II-A1 Identification of the Classifier

By executing a control policy and following the corresponding path, the
positions at which measurements are collected by the agent is denoted by
$\\{x_{j},z_{j}\\}^{m}_{j=1}$. The true labels of these positions is denoted
by $\\{y_{j}\\}^{m}_{j=1}$. If the true classifier is denoted by the straight
line $z=\rho^{*}x+c^{*}$, then
$y_{j}=\text{sgn}(z_{j}-\rho^{*}x_{j}-c^{*}),j=1,\ldots,m$. Given the data
points, the classification problem can be formulated as,

$\displaystyle\underset{\rho\in\mathbb{R},c\in\mathbb{R}}{\min}\sum^{m}_{j=1}y_{j}\text{sgn}(z_{j}-\rho
x_{j}-c).$

The optimization problem is to choose parameters $\rho$ and $c$ so that the
resulting line classifies as many data points as possible correctly. This
formulation does not yield to computationally effective solutions. The
classical reformulation, [20], [21], of the problem is to identify a line
which (i) maximizes the minimum distance of the data points from the line;
(ii) ensures that the points are classified correctly. Given a possible
classifier, $z-\rho x-c=0$, the distance of the point $(x_{k},z_{k})$ is given
by $\frac{|z_{k}-\rho x_{k}-c|}{\rho^{2}}$. Through suitable re-normalization,
it can be ensured that $|z_{j^{*}}-\rho x_{j^{*}}-c|=1$ for atleast one of the
data points,$(x_{j^{*}},z_{j^{*}},y_{j^{*}})$, while $|z_{j}-\rho x_{j}-c|\geq
1$ for all other data points. The classification problem can be reformulated
as,

$\displaystyle\underset{\rho\in\mathbb{R},c\in\mathbb{R}}{\min}\;\;\frac{\rho^{2}}{2}\;\;\text{s.t}\;\;y_{j}(z_{j}-\rho
x_{j}-c)\geq 1,j=1,\ldots,m.$

The above optimization problem is a convex optimization problem which can be
solved effectively by considering the dual problem, [21].

####  II-A2 Control Problem

The state space of the agent is $\mathbb{R}^{2}$, while the set of actions
(action space) that it can take is denoted by $\mathcal{U}$. The state of the
system at time $t$ is denoted by $\zeta(t)=[x(t),z(t)]$ while the action is
denoted by $u(t)$. Along with the full state information at $t$, the
observation of the system at $t$ is the true label at that state which is
denoted by $y(t)$. Thus, $y(t)=\text{sgn}(z(t)-\rho^{*}x(t)-c^{*})$ where
$\rho^{*}$ and $c^{*}$ the parameters corresponding to the true classifier and
are unknown. The observation $y(t)$ is available to the agent and is used to
estimate $\rho^{*}$ and $c^{*}$. The initial state of agent is the point
$p_{1}$ which we denote as $(\bar{x}_{1},\bar{z}_{1},-1)$. For the
deterministic case, we do not consider process noise or measurement noise. The
agent is modeled as a discrete time system with known dynamics,

$\displaystyle\zeta(t+1)=\phi(\zeta(t),u(t)),\;\bar{y}(t)=[\zeta(t),y(t)],\;\bar{y}(0)=[\bar{x}_{1},\bar{z}_{1},$
$\displaystyle-1],\;y(t)=\text{sgn}(z(t)-\rho^{*}x(t)-c^{*}),t=0,\ldots m-1.$

The learning problem formulated as a control problem is to find a control
policy, $\\{\Upsilon_{j}\\}^{m-1}_{j=0}$, where
$\Upsilon_{j}:\mathbb{R}^{2^{j+1}}\times\\{-1,0,1\\}^{j+1}\to\mathcal{U}$,
which minimizes the control cost while ensuring that the data points collected
yield a suitable classifier. The optimization problem is,

$\displaystyle\underset{\\{\Upsilon_{t}\\}^{m-1}_{t=0},\\{\rho,c\\}\subset\mathbb{R}}{\min}\frac{\rho^{2}}{2}+\sum^{m-1}_{t=0}\Big{|}\Big{|}\Upsilon_{t}\Big{(}\\{\bar{y}(j)\\}^{t-1}_{j=0}\Big{)}\Big{|}\Big{|}^{2},\;\text{s.t},\;$
$\displaystyle\ y(t)(z(t)-\rho x(t)-c)\geq
1,t=1,\ldots,m,\;|\sum^{m}_{t=0}y(t)|\leq 1,$
$\displaystyle(\bar{z}_{j}-\rho\bar{x}_{j}-c)\leq
1,j=1,4,(\bar{z}_{j}-\rho\bar{x}_{j}-c)\geq 1,j=2,3,$
$\displaystyle\zeta(t+1)=\phi\Big{(}\zeta(t),\Upsilon_{t}\Big{(}\\{\bar{y}(j)\\}^{t-1}_{j=0}\Big{)}\Big{)},t=0,\ldots
m-1,y(t)$
$\displaystyle=\text{sgn}(z(t)-\rho^{*}x(t)-c^{*}),\bar{y}(t)=[\zeta(t),y(t)],t=0,\ldots
m.$

In the constraints of the above optimization problem, in the second line, the
constraints are to ensure that the four given points are classified correctly.
The constraint, $|\sum^{m}_{t=0}y(t)|\leq 1$, has been included to ensure that
equal number points are visited in both regions or at most one additional
point is visited in one of the regions.

###  II-B Stochastic Scenario: Abstraction

####  II-B1 The Noise Model

First, we describe the noise model. In the region close to the true
classifier, the measured labels are equal to true labels with probability $p$
(noise = $1$) and get flipped to the other label with probability $1-p$ (noise
= $-1$). In the region far away from the true classifier, the measured label
equals the true label with probability $1$. Given the parameters of the true
classifier, $\rho^{*}$ and $c^{*}$, and some $\bar{c}>0$, large enough, define
the set $\hat{E}$, as
$\hat{E}=\\{(x,z)\in\mathbb{R}^{2}:z-\rho^{*}x-c^{*}+\bar{c}\geq
0\;\text{and}\;z-\rho^{*}x-c^{*}-\bar{c}\leq 0\\}$. The region has been
depicted in Figure 2. Then, one possible model for noise is

$\displaystyle\varepsilon(x,z)=\begin{cases}1&\text{with probability $p$ if
$(x,z)\in\hat{E}$}\\\ -1&\text{with probability $1-p$ if $(x,z)\in\hat{E}$}\\\
1&\text{with probability 1 if
$(x,z)\in\mathbb{R}^{2}\sim\hat{E}$}\end{cases}.$

Figure 2: Schematic for the motion planning problem with noisy data

The region $\hat{E}\cap\mathcal{X}$ carries the true label $1$ (indicated in
red). However, due to noise some of the observed labels are $-1$. There are
four data points whose true label is $1$ while the observed label is $-1$. In
the region, $\hat{E}\cap\mathcal{X}^{c}$ the true label is $-1$. There are $3$
data points whose true label is $-1$ while the observed label is $1$. Note
that this model for noise requires the knowledge about the true classifier
which is unknown and hence cannot be used. Since it is difficult to define the
regions “close to” and “far off” with out invoking the definition of the true
classifier, we consider an alternate noise model. We assume that we are given
a sequence (or a large set) of points, $\\{p_{j}\\}_{j\geq
1}(\\{p_{j}\\}^{I}_{j=1})$, such that a subsequence (r a subset) of which lies
in the region with label $1$ while the complement subsequence (subset) lies in
the region with label $-1$. Around each point, $p_{j}=(x_{j},z_{j})$, there
exists a region , $B_{r}(p_{j})=\\{(x,z):||(x,z)-(x_{j},z_{j})||\leq r\\}$,
where the measured label equals the true label with probability 1. For the
remaining state space, the noise takes values $1$ and $-1$ with probability
$p$ and $1-p$ respectively. Stating the same precisely, let
$\bar{E}=\underset{j\geq 1}{\bigcup}B_{r}(p_{j})$, then,

$\displaystyle\varepsilon(x,z)=\begin{cases}1&\text{with probability 1 if
$(x,z)\in\bar{E}$}\\\ 1&\text{with probaility $p$ if
$(x,z)\in\mathbb{R}^{2}\sim\bar{E}$}\\\ -1&\text{with probaility $1-p$ if
$(x,z)\in\mathbb{R}^{2}\sim\bar{E}$}\end{cases}.$

$\displaystyle\bar{\mathbb{P}}_{0}((X(0),Z(0))\in
E,Y(0)=1)=\bar{\mathbb{P}}_{0}((X(0),Z(0))\in
E\cap\mathcal{X},Y(0)=1)=\bar{\mathbb{P}}_{0}(X(0),Z(0)\in E\cap\mathcal{X}),$
$\displaystyle\bar{\mathbb{P}}_{0}((X(0),Z(0))\in
E,Y(0)=-1)=\bar{\mathbb{P}}_{0}((X(0),Z(0))\in
E\cap\mathcal{X}^{c},Y(0)=-1)=\bar{\mathbb{P}}_{0}(X(0),Z(0)\in
E\cap\mathcal{X}^{c}).$ (1) $\displaystyle\mathbb{P}_{0}((\zeta(0),Y(0))\in
E,U(0)\in
F)=\int_{E}\int_{F}\bigg{[}d\Gamma_{0}(x_{0},z_{0},y_{0})[u]\bigg{]}d\bar{\mathbb{P}}_{0}(x_{0},z_{0},y_{0})=\Gamma_{0}(E)[U(0)\in
F]\bar{\mathbb{P}}_{0}((\zeta(0),Y(0)\in E)$ (2)
$\displaystyle\hat{\mathbb{P}}_{n-1}(\zeta(n)\in
E)=\mathbb{P}_{n-1}\Big{(}\Big{(}\zeta(0),Y(0),\\{U(j)\\}^{n-1}_{j=0},\\{\varepsilon(j)\\}^{n-1}_{j=1}\Big{)}:\phi^{n}(\zeta(0),\\{U(j)\\}^{n-1}_{j=0})\in
E\\},E\in\mathcal{B}(\mathbb{R}^{2})$ (3)
$\displaystyle\bar{\mathbb{P}}_{n}\Big{(}\Big{(}X(0),Z(0),Y(0),\\{U(j)\\}^{n-1}_{j=0},\\{\varepsilon(j)\\}^{n-1}_{j=1}\Big{)}\in
E,\varepsilon(n)=1\Big{)}=p\hat{\mathbb{P}}_{n-1}(\zeta(t)\in\phi^{n}(E)\cap\mathbb{R}^{2}\sim\bar{E})+\hat{\mathbb{P}}_{n-1}(\zeta(t)\in\phi^{n}(E)$
$\displaystyle\cap\bar{E}),\;\bar{\mathbb{P}}_{n}\Big{(}\Big{(}X(0),Z(0),Y(0),\\{U(j)\\}^{n-1}_{j=0},\\{\varepsilon(j)\\}^{n-1}_{j=1}\Big{)}\in
E,\varepsilon(n)=-1\Big{)}=(1-p)\hat{\mathbb{P}}_{n-1}(\zeta(t)\in\phi^{n}(E)\cap\mathbb{R}^{2}\sim\bar{E})$
(4)

####  II-B2 The Probability Space

Given the above noise model, we construct the probability space for the
stochastic control problem as follows. Sample Space and $\sigma$ Algebra: Let
$\Omega=\mathbb{R}^{2}\times\\{-1,1\\}\times\mathcal{U}^{\mathbb{Z}_{+}}\times\\{-1,1\\}^{\mathbb{N}}$.
The sample space is the product set of the set of all possible values that can
be taken by the initial states $X(0,\cdot),Z(0,\cdot)$, the initial
observation $Y(0,\cdot)$, the control trajectory $\\{U(t,\cdot)\\}_{t\geq 0}$
and the sequence of noise variables $\\{\varepsilon(t,\cdot)\\}_{t\geq 1}$. By
considering the Borel $\sigma$ algebra on $\mathcal{U}$,
$\mathcal{B}(\mathcal{U})$, the Borel $\sigma$ algebra on $\mathbb{R}^{2}$,
$\mathcal{B}(\mathbb{R}^{2})$, and the algebra
$\mathcal{B}(\\{-1,1\\})=\\{\\{1\\},\\{-1\\},\\{-1,1\\},\emptyset\\}$ on
$\\{-1,1\\}$, we define

$\displaystyle\mathfrak{B}_{0}=\\{F\subset\mathbb{R}^{2}\times\\{-1,1\\}\times\mathcal{U}:\;F=E_{1}\times
E_{2}\times E_{3},$ $\displaystyle\hskip
36.98866pt\text{where}\;E_{1}\in\mathcal{B}(\mathbb{R}^{2}),E_{2}\in\mathcal{B}(\\{-1,1\\}),E_{3}\in\mathcal{B}(\mathcal{U})\\}$
$\displaystyle\mathfrak{B}=\\{F\subset\mathcal{U}\times\\{-1,1\\}:F=E_{1}\times
E_{2},\;\text{where}$ $\displaystyle\hskip
118.07875ptE_{1}\in\mathcal{B}(\mathcal{U}),E_{2}\in\mathcal{B}(\\{-1,1\\})\\}.$

We define the collection of cylindrical subsets of $\Omega$ as,

$\displaystyle\bar{\mathfrak{B}}=$
$\displaystyle\\{\bar{\omega}\in\Omega:\bar{\omega}(0)\in
E_{0},\bar{\omega}(1)\in E_{1},\ldots,\bar{\omega}(n)\in E_{n},$
$\displaystyle\text{where}\;E_{0}\in\sigma(\mathfrak{B}_{0}),\\{E_{j}\\}^{n}_{j=1}\in\sigma(\mathfrak{B}),n\in\mathbb{Z}_{+}\\}$

Let $\mathcal{F}$ be the smallest $\sigma$ algebra generated by
$\bar{\mathfrak{B}}$. We note that $\bar{\omega}(t)$ is a 4-tuple at $t=0$
which we denote as $\bar{\omega}(0)=[x_{0},z_{0},y_{0},u_{0}]$ and is a
2-tuple for $t\geq 1$ which we denote as $\bar{\omega}(t)=[u_{t},e_{t}]$. For
any trajectory $\omega\in\Omega$, $U(t,\omega)=u_{t}$ and
$\varepsilon(t,\omega)=e_{t}$, i.e., the components corresponding to the
control and noise.

Hence, given a measurable mapping $\phi(\cdot)$ corresponding to the dynamics
of the agent, the sequence $\\{\zeta(t,\cdot)\\}_{t\geq 0}$, generated as
$\zeta(t+1,\omega)=\phi(\zeta(t,\omega),U(t,\omega))$ is a stochastic process
on $(\Omega,\mathcal{F})$. We denote the two components of $\zeta(t,\cdot)$ as
$\zeta(t,\cdot)=[X(t,\cdot),Z(t,\cdot)]$. The sequence of true labels at the
states $\\{\zeta(t,\cdot)\\}_{t\geq 0}$, $\\{Y(t,\cdot)\\}_{t\geq 0}$
generated as $Y(t,\omega)=\text{sgn}(Z(t,\omega)-\rho^{*}X(t,\omega))-c^{*}$
is also a stochastic process on $(\Omega,\mathcal{F})$, where $\rho^{*}$ and
$c^{*}$ are the parameters of the true classifier. The sequence of observed
labels, $\\{\bar{Y}(t,\cdot)\\}_{t\geq 0}$ generated as
$\bar{Y}(t,\omega)=Y(t,\omega)\varepsilon(t,\omega)$ is a stochastic processes
on $(\Omega,\mathcal{F})$.

The Probability Measure: We construct the measure on $(\Omega,\mathcal{F})$ as
follows. The distribution of the initial state, $\zeta(0)$,
$\bar{\mathbb{P}}_{0}(X(0),Z(0))$ is assumed to be known and the joint
distribution with the initial observation is defined in Equations 1. The
measure $\bar{\mathbb{P}}_{0}$ is then extended to the $\sigma$ algebra,
$\sigma(\bar{\mathfrak{B}}_{0})$, where
$\bar{\mathfrak{B}}_{0}=\\{F\subset\mathbb{R}^{2}\times\\{-1,1\\}:F=E_{1}\times
E_{2}\;\text{where}\;E_{1}\in\mathcal{B}(\mathbb{R}^{2}),E_{2}\in\mathcal{B}(\\{-1,1\\})\\}$.
The equations essentially state that
$\bar{\mathbb{P}}_{0}(Y(0)=1|(X(0),Z(0))\in E\cap\mathcal{X})=1$ and
$\bar{\mathbb{P}}_{0}(Y(0)=-1|(X(0),Z(0))\in E\cap\mathcal{X}^{c})=1$ for
$E\in\mathcal{B}(\mathbb{R}^{2})$. This states that the label at the initial
state is known perfectly. Hence, it is reasonable to assume that the
distribution of the initial states is concentrated in a region far away from
the true classifier or in the set $\bar{E}$ (defined in the noise model) where
the true label is known with probability 1.

The control policy at $t=0$,
$\Gamma_{0}:\sigma(\bar{\mathfrak{B}}_{0})\to\mathcal{P}(\mathcal{U},\mathcal{B}(\mathcal{U}))$
is to be found, where $\mathcal{P}(\mathcal{U},\mathcal{B}(\mathcal{U}))$ is
the set of probability measures on the Borel $\sigma$ algebra of
$\mathcal{U}$. Given the control policy at $t=0$, the measure at stage $t=0$
is defined for
$E\in\sigma(\bar{\mathfrak{B}}_{0}),F\in\mathcal{B}(\mathcal{U})$ in Equation
2. The measure is then extended to the $\sigma$ algebra,
$\sigma(\\{F\subset\mathbb{R}^{2}\times\\{-1,1\\}\times\mathcal{U}:F=E_{1}\times
E_{2},E_{1}\in\sigma(\bar{\mathfrak{B}}_{0}),E_{2}\in\mathcal{B}(\mathcal{U})\\})=\sigma(\mathfrak{B}_{0})\overset{\Delta}{=}\mathcal{F}_{0}$.

For any $n\in\mathbb{N}$, the distribution of state $\zeta(n)$ is defined in
Equation 3. We note that given the sets to which $\zeta(0)$ and
$\\{U_{j}\\}^{n-1}_{j=0}$ belong, we can precisely state the set to which
$\zeta(n)$ belongs. However, to find the probability that $\zeta(n)$ belongs
to a measurable set, the probability of events like $U(j)\in E$ is needed. We
note that probability of $U(j)\in E$ depends on
$\Big{(}\zeta(0),Y(0),\\{U_{k}\\}^{j-1}_{k=0},\\{\varepsilon(k)\\}^{j}_{k=1}\Big{)}$,
i.e, not only on the initial state and the past control values but also on the
initial observation and the noise random variables. Hence, in Equation 3 the
random variables, $Y(0),\\{\varepsilon(j)\\}^{n-1}_{j=1}$, have also been
included while finding the distribution of $\zeta(n)$. The distribution of the
observation $Y(n)$ is given by,
$\hat{\mathbb{P}}_{t-1}(Y(t)=1)=\hat{\mathbb{P}}_{t-1}(\zeta(t)\in\mathcal{X}),\;\hat{\mathbb{P}}_{t-1}(Y(t)=-1)=\hat{\mathbb{P}}_{t-1}(\zeta(t)\in\mathcal{X}^{c})$.
Similarly, the joint distribution of $\zeta(t)$ and $Y(t)$ can be found.

$\displaystyle\mathbb{P}_{n}\Big{(}\Big{(}\zeta(0),Y(0),\\{U(j)\\}^{n-1}_{j=0},\\{\varepsilon(j)\\}^{n}_{j=1}\Big{)}\in
E,U(n)\in F\Big{)}=$ $\displaystyle\hskip 113.81102pt\Gamma_{n}(E)[U(n)\in
F]\bar{\mathbb{P}}_{n}\Big{(}\Big{(}\zeta(0),Y(0),\\{U(j)\\}^{n-1}_{j=0},\\{\varepsilon(j)\\}^{n}_{j=1}\Big{)}\in
E\Big{)},E\in\mathcal{F}_{n-1},F\in\mathcal{B}(\mathcal{U})$ (5)
$\displaystyle\mathbb{P}_{n}\Big{(}\Big{(}\zeta(0),Y(0),\\{U(j)\\}^{n-1}_{j=0},\\{\varepsilon(j)\\}^{n-1}_{j=1}\Big{)}\in
E,\varepsilon(n)\in\\{-1,1\\},U(n)\in\mathcal{U}\Big{)}=\Gamma_{n}(E\times(\\{-1,1\\})[U(n)\in\mathcal{U}]\times\bar{\mathbb{P}}_{n}\Big{(}\Big{(}\zeta(0),$
$\displaystyle
Y(0),\\{U(j)\\}^{n-1}_{j=0},\\{\varepsilon(j)\\}^{n-1}_{j=1}\Big{)}\in
E,\varepsilon(n)\in\\{-1,1\\}\Big{)}=p\hat{\mathbb{P}}_{n-1}(\zeta(t)\in\phi^{n}(E)\cap\mathbb{R}^{2}\sim\bar{E})+\hat{\mathbb{P}}_{n-1}(\zeta(t)\in\phi^{n}(E)\cap\bar{E})+$
$\displaystyle(1-p)\hat{\mathbb{P}}_{n-1}(\zeta(t)\in\phi^{n}(E)\cap\mathbb{R}^{2}\sim\bar{E})=\hat{\mathbb{P}}_{n-1}(\zeta(t)\in\phi^{n}(E))=\mathbb{P}_{n-1}\Big{(}\Big{(}\zeta(0),Y(0),\\{U(j)\\}^{n-1}_{j=0},\\{\varepsilon(j)\\}^{n-1}_{j=1}\Big{)}\in
E\Big{)}$ (6)
$\displaystyle\frac{p\hat{\mathbb{P}}_{n-1}(\zeta(t)\in\phi^{n}(\tilde{E}_{1})\cap\bar{E}^{c})+\hat{\mathbb{P}}_{n-1}(\zeta(t)\in\phi^{n}(\tilde{E}_{1})\cap\bar{E})}{\hat{\mathbb{P}}_{n-1}(\zeta(t)\in\phi^{n}(\tilde{E}_{1}))}\neq\frac{p\hat{\mathbb{P}}_{n-1}(\zeta(t)\in\phi^{n}(E_{1})\cap\bar{E}^{c})+\hat{\mathbb{P}}_{n-1}(\zeta(t)\in\phi^{n}(E_{1})\cap\bar{E})}{\hat{\mathbb{P}}_{n-1}(\zeta(t)\in\phi^{n}(E_{1}))},$
(7)

Given $\mathbb{P}_{n-1}$ on $(\Omega_{n-1},\mathcal{F}_{n-1})$,
$\mathbb{P}_{n}$ is inductively defined as follows. $\bar{\mathbb{P}}_{n-1}$
is defined for $E\in\mathcal{F}_{n-1}$ and $F\in\mathcal{B}(\\{-1,1\\})$ in
Equation 4. It is then extended to
$\sigma(\mathcal{F}_{n-1}\times\mathcal{B}(\\{-1,1\\}))$. Because of the joint
distribution when $\varepsilon(n)=1$ in Equation 4, following conditional
independence does not hold:

$\displaystyle\mathbb{P}_{n}(\varepsilon(n)\in F|\zeta(n)\in
E_{1},\\{\varepsilon(j)$ $\displaystyle\\}^{n-1}_{j=1}\in E_{2})$
$\displaystyle\neq\mathbb{P}_{n}(\varepsilon(n)\in F|\zeta(n)\in E_{1}),$

$F\in\mathcal{B}(\\{-1,1\\})$, $E_{1}\in\mathcal{B}(\mathbb{R}^{2})$, and
$E_{2}\in\mathcal{B}(\\{-1,1\\}^{n-1})$. This is because event $E_{2}$
interferes with event $E_{1}$ causing a change in the set of states which we
denote by $\tilde{E}_{1}$,

$\displaystyle\Big{(}\zeta(0),Y(0),\\{U(j)\\}^{n-1}_{j=0},\\{\varepsilon(j)\\}^{n-1}_{j=1}\Big{)}\in
E_{1}\Big{)}\bigcap\Big{(}\\{\varepsilon(j)\\}^{n-1}_{j=1}$ $\displaystyle\in
E_{2})\overset{\Delta}{=}\Big{(}X(0),Z(0),Y(0),\\{U(j)\\}^{n-1}_{j=0},\\{\varepsilon(j)\\}^{n-1}_{j=1}\Big{)}\in\tilde{E}_{1}.$

The expressions for the L.H.S and R.H.S are mentioned in Inequality 7, where
$\bar{E}^{c}=\mathbb{R}^{2}\sim\bar{E}$. Due to the noise model, a change in
set of states leads to different conditional probabilities violating the
equality required for conditional independence. In Equation 4, $\phi^{n}(E)$,
denotes the set of states that can be reached when the random variables
$\Big{(}\zeta(0),Y(0),\\{U(j)\\}^{n-1}_{j=0},\\{\varepsilon(j)\\}^{n-1}_{j=1}\Big{)}$
belong to $E$. Note that $\\{Y(0),\\{\varepsilon(j)\\}^{n-1}_{j=1}\\}$ impacts
$\\{U(j)\\}^{n-1}_{j=0}$ and hence the state $\zeta(n)$ itself. That is, if we
consider only the realizations of $\zeta(0)$ and $\\{U(j)\\}^{n-1}_{j=0}$ form
the set $E$, then valid $\zeta(n)$ could be found. However it is possible that
certain realizations of $\\{U(j)\\}^{n-1}_{j=0}$ do not occur, i.e, has
measure zero given the noise $\\{\varepsilon(j)\\}^{n-1}_{j=1}$ and thus the
corresponding realizations of $\zeta(n)$ do not occur. Hence, we need to
include $\\{Y(0),\\{\varepsilon(j)\\}^{n-1}_{j=1}\\}$ while finding valid
realizations of $\zeta(n)$. Given the control policy at stage $n$,
$\Gamma_{n}:\sigma(\mathcal{F}_{n-1}\times\mathcal{B}(\\{-1,1\\}))\to\mathcal{P}(\mathcal{U},\mathcal{B}(\mathcal{U}))$,
the measure defined in Equation 5 for can be extended to
$\mathcal{F}_{n}=\sigma(\sigma(\mathcal{F}_{n-1}\times\mathcal{B}(\\{-1,1\\}))\times\mathcal{B}(\mathcal{U}))$.
Equation 6, proves that the sequence of measures $\\{\mathbb{P}_{n}\\}_{n\geq
0}$ is a sequence of consistent measures on
$\\{(\Omega_{n},\mathcal{F}_{n})\\}_{n\geq 0}$ where $\Omega_{n}$ is suitably
defined. By Kolmogorov’s Consistency Theorem, there exists a measure
$\mathbb{P}$ on $(\Omega,\mathcal{F})$ such that
$\mathbb{P}(E)=\mathbb{P}_{n}(E)\forall E\in\mathcal{F}_{n}\forall
n\in\mathbb{Z}_{+}$

####  II-B3 Identification of the Classifier

Along a random path, $\\{\zeta(t,\omega)\\}_{t\geq 0}$, followed by the agent,
consider the first $m$ data points, $\\{\bar{Y}(t,\omega)\\}^{m}_{t=1}$,
collected by the agent at the positions,
$\\{X(t,\omega),Z(t,\omega)\\}^{m}_{t=1}$. For e.g. in Figure 2, the path
executed by the agent results in 27 data points being collected. Due to noise,
the labels at many of the data points gets flipped as indicated in the figure.
Given the noisy data set, the classification problem can be formulated as
follows. Let $L^{1}(\Omega_{m-1},\mathcal{F}_{m-1},\mathbb{P}_{m-1})$ be the
space of integrable random variables on the associated probability space. The
classification problem is then,

$\displaystyle\underset{\begin{subarray}{c}\hskip 10.0pt\\\ \rho,c\in
L^{1}(\Omega_{m-1},\mathcal{F}_{m-1},\mathbb{P}_{m-1})\end{subarray}}{\min}\mathbb{E}_{\mathbb{P}_{m-1}}\Big{[}\sum^{m}_{j=1}Y(j)\text{sgn}(Z(j)-\rho
X(j)-c)\Big{]}.$

The SVM reformulation of the classification problem is

$\displaystyle\underset{\begin{subarray}{c}\hskip 10.0pt\\\ \rho,c\in
L^{1}(\Omega_{m-1},\mathcal{F}_{m-1},\mathbb{P}_{m-1})\end{subarray}}{\min}\;\;\mathbb{E}_{\mathbb{P}_{m-1}}\Big{[}\frac{\rho^{2}}{2}\Big{]}$
$\displaystyle\text{s.t}\;\;\mathbb{E}_{\mathbb{P}_{m-1}}\Big{[}$
$\displaystyle Y(j)(Z_{(}j)-\rho X(j)-c)\Big{]}\geq 1,j=1,\ldots,m.$

####  II-B4 The Control Problem

Taking into account the identification cost, the control cost, and optimizing
over control policies, the control problem is

$\displaystyle\underset{\\{\Gamma_{j}\\}^{m-1}_{j=0},\rho,c\in
L^{1}(\ldots)}{\min}$
$\displaystyle\mathbb{E}_{\mathbb{P}_{m-1}}\Big{[}\sum^{m}_{j=0}Y(j)\text{sgn}(Z(j)-\rho
X(j)-c)\Big{]}$ $\displaystyle\hskip
78.24507pt+\mathbb{E}_{\mathbb{P}_{m-1}}\Big{[}\sum^{m-1}_{j=0}||U(j)||^{2}\Big{]}$
$\displaystyle\text{s.t}\;\;X(t+1,\omega)$
$\displaystyle=\phi(X(t,\omega),U(t,\omega)),t=0,\ldots,m-1,$ $\displaystyle
Y(t,\omega)=\text{sgn}($ $\displaystyle
Z(t,\omega)-\rho^{*}X(t,\omega))-c^{*}),t=0,\ldots,m,$
$\displaystyle\bar{Y}(t,\omega)$
$\displaystyle=Y(t,\omega)\varepsilon(t,\omega),t=1,\ldots,m.$

We note that the control policies, $\\{\Gamma_{j}\\}^{m-1}_{j=0}$, are
embedded in the measure $\mathbb{P}_{m-1}$ and hence do not appear explicitly
in the cost function.

##  III Analysis of the problem

###  III-A Deterministic Scenario

We begin this section with some observations on the control problem formulated
in subsection II-A2. Let us consider a dynamic programming approach to solve
the problem. The learning cost is not evidently decomposable into a learning
cost for each stage. At stage $m$, there is no control cost. Given the data
points $\\{x_{j},z_{j},y_{j}\\}^{m}_{j=1}$, the problem is to solve the
classification problem which can done using quadratic programming as mentioned
before. At stage $m-1$, given the $m-1$ points visited by the agent, the
objective is to chose the final data point so that classification can be
performed on the resulting data set. The objective of the classification
problem is to find $(\rho,c)$ such that the minimum distance of the data
points from the classifier is maximized. Suppose, the true classifier was
known. If the control strategy at $m-1$ were to aid this objective, the
control action would move the agent to a point where the label is opposite to
the current label and whose distance is equal to the minimum distance of the
given $m-1$ points from the classifier. I

If the same argument were to be repeated at stages $j$, $0\leq j\leq m-2$, the
control strategy would move the agent to points which are roughly in the
neighborhood of the initial points which is not useful for the identification
of the true classifier. If the learning cost is changed to
$\sum^{m}_{t=1}y(t)\text{sgn}(z(t)-\rho x(t)-c)$, it also does not enforce the
same. This is because, given any $m$ data points with true labels the data set
is linearly separable and hence the minimum cost is always zero even though
the estimated classifier is not close to the true classifier. It appears as
though the cost function for the identification problem is not utilizing the
state information and the corresponding label at every stage to enhance the
learning process. We explore this idea further in the following.

Figure 3: Region of certainty from the four given points

We consider the scenario in depicted in Figure 3 as a canonical case. The
slope of the true classifier is positive and the $z$ intercept is positive as
well. Other cases are : slope positive , intercept negative; slope negative
intercept positive; slope negative intercept negative. The other three cases
are obtained through translation and rotation of the scenario considered.
Hence, the following arguments are applicable to other cases as well. The
lines $l_{13},l_{14},l_{23},l_{24}$ are defined as
$l_{ij}=\\{(x,z)\in\mathbb{R}^{2}:z-\rho_{ij}x-c_{ij}=0\\},\;i=1,2,j=3,4$.
These lines are obtained from the four given points. Each of these lines are
“bounds” for the true classifier is the following sense.

Consider $l_{23}$ and the region
$\\{(x,z)\in\mathbb{R}^{2}:z-\rho_{23}x-c_{23}\geq 0\\}$. In this region
consider any point whose $x$ co-ordinate lies between that of $p_{2}$ and
$p_{3}$. The label of such a point is $1$. This is because, if there is a
point with label $-1$, linear separability of data gets violated, i.e., there
does no exist a linear classifier that separates $p_{1},p_{2},p_{3},p_{4}$ and
the point with label $-1$. However, we are unable to comment on the region
$\\{(x,z)\in\mathbb{R}^{2}:z-\rho_{23}x-c_{23}\leq 0\\}$ as there is not
enough information. Further, there are two points on $l_{23}$ with label $1$.
Hence it is not the true classifier, but a “bound” for the true one. The line
$l_{13}$ is also a bound for the true classifier, since a line with slope
slightly greater than slope of $l_{13}$ and intercept slightly less than
$c_{13}$ which is in fact negative, does not separate
$p_{1},p_{2},p_{3},p_{4}$. By the same argument $l_{24}$ is also a bound for
the true classifier. If either of them is the true classifier, then the
corresponding set $\\{(x,z)\in\mathbb{R}^{2}:z-\rho_{24}x-c_{24}\geq 0\\}$ or
$\\{(x,z)\in\mathbb{R}^{2}:z-\rho_{13}x-c_{13}\leq 0\\}$ carries the label
$1$. Taking the intersection of the three sets, we obtain a Region of
Certainty, a set where the true label is $1$ given the four points. Using the
same arguments with $l_{14},l_{13}$, and $l_{24}$, we obtain a region of
certainty with label $-1$.

The slopes and intercepts of the four lines provide bounds on the slope and
intercept of the true line. Considering the range of $\arctan$ to be
$(-\frac{\pi}{2},\frac{\pi}{2})$, let $\theta_{ij}=\arctan(\rho_{ij})$. In
Figure 3, we observe that $\theta_{13}>0,\theta_{23}\geq 0$,
$\theta_{13}>\theta_{23}$ while $\theta_{14}<0,\theta_{24}<0$ and
$\theta_{24}<\theta_{14}$. From the linear separability arguments presented
above, we conclude that the slope of the true classifier belongs to
$[\theta_{24},\theta_{14}]\cup[\theta_{23},\theta_{13}]$. The intercept of the
true line belongs to $[c_{\min},c_{\max}]$ where
$c_{\max}=\max(c_{13},c_{14},c_{23},c_{24})$ and
$c_{\min}=\min(c_{13},c_{14},c_{23},c_{24})$. In Figure 3, $c_{\max}=c_{24}$
and $c_{\min}=c_{13}$.

Figure 4: Region of certainty from new four points obtained by Agent

Consider the scenario depicted in Figure 4, where the distance between pairs
$p_{1},p_{2}$ and $p_{3},p_{4}$ which have opposite labels has reduced while
the distance between $p_{1},p_{4}$ and $p_{2},p_{3}$ which carry the same
label has increased. In Figure 4, we observe that
$\theta_{13}>0,\theta_{23}>0,\theta_{23}<\theta_{13}$ while
$\theta_{14}>0,\theta_{24}<0$. The slope of the true classifier thus lies
between $[\theta_{24},0]\cup[\min(\theta_{23},\theta_{14}),\theta_{13}]$ while
its intercept lies between $[c_{24},c_{13}]$. We note that the bounds for the
true slope and intercept in scenario of Figure 4 is a strict subset of the
bounds in the scenario of Figure 3 which leads to an “increase” in the region
of certainty of both labels.

Given the above reasoning, the control problem is to be formulated is such a
away the region of certainty eventually matches with the entire regions
carrying the true label. We consider one step control problems with the
objective of pruning the bounds of the slope and intercept of the true
classifier so that the set to which the true parameters belong eventually
collapses to singletons, i.e., the true value of the parameters. To meet this
objective, at a given position, in one step, the agent could either (i) move
to a position of opposite label whose distance is less than the distance of
the previous point with opposite label from current position (ii) move to a
position of same label in the current region of uncertainty which is farther
way from current position. For (i), given the current position and label,
$(x(t),z(t),y(t))$, the control problem is formulated as:

$\displaystyle\min_{u\in\mathcal{U}}||$
$\displaystyle\zeta(t+1)-\zeta(t)||^{2}+\varrho||u||^{2},\;\text{s.t}\;\;\zeta(t+1)=\phi(\zeta(t),u),$
$\displaystyle y(t)\text{sgn}(z(t+1)-\rho^{*}x(t+1)-c^{*})\leq 0$

The above problem has two issues. (i) $\rho^{*}$ and $c^{*}$ are unknown and
(ii) even if the true parameters were known, the constraint may not be
feasible in one step due to the limited control actions that the agent can
take. Let $\mathcal{X}_{t}$ denote the region of certainty for label $1$ at
stage $t$ and let $\mathcal{X}^{c}_{t}$ denote the region of certainty for
label $-1$ at stage $t$. Let $E_{\rho,t}$ denote the bounds for the slope of
the true classifier at stage $t$. We consider the following alternate
formulation.

$\displaystyle P1:\hskip 28.45274pt$
$\displaystyle\max_{u\in\mathcal{U}}||\zeta(t+1)-\zeta(t)||^{2}-\varrho||u||^{2}$
$\displaystyle\text{s.t}\;\;\zeta(t+1)$
$\displaystyle=\phi(\zeta(t),u),\zeta(t+1)\notin\mathcal{X}^{c}_{t},\zeta(t+1)\notin\mathcal{X}_{t}$
$\displaystyle\arctan(\frac{z(t+1)-z(t)}{x(t+1)-x(t)})\notin E_{\rho,t}$

This formulation pushes the agent away to a point which is far away from its
current position while not entering the regions of certainty and ensuring that
the control cost is small enough. The regions of certainty can be expressed as
the intersection of a set of halfspaces. Hence, the above problem can be
solved numerically. The constraint in third line is included to ensure that
the agent does not end up traveling parallel to the true classifier in which
case it cannot reach a point of opposite label. By moving in any direction not
in set $E_{\rho,t}$, the agent is guaranteed to reach a point of opposite
label though it might take multiple steps. In implementation, it is possible
to restrict the angles further, for e.g. the agent could be restricted to
track the direction of the vector $\overrightarrow{p_{1}p_{2}}$ or the
“bisector” of $E_{\rho,t}$. For the agent to move to point with same label as
current label, however farther away the following problem is solved.

$\displaystyle P2:\hskip 28.45274pt$
$\displaystyle\max_{u\in\mathcal{U}}||\zeta(t+1)-\zeta(t)||^{2}-\varrho||u||^{2}$
$\displaystyle\text{s.t}\;\;\zeta(t+1)$
$\displaystyle=\phi(\zeta(t),u),\zeta(t+1)\notin\mathcal{X}^{c}_{t},\zeta(t+1)\notin\mathcal{X}_{t}$
$\displaystyle\arctan(\frac{z(t+1)-z(t)}{x(t+1)-x(t)})\in E_{\rho,t}$

In the above the agent could travel in a direction which is parallel to the
true classifier, which is in fact good as it meets the objective. However for
all other directions, the agent could move to a point which has a opposite
label to the label of its current position.

Problems $P1$ and $P2$ are reformulations of the identification problem
considered in subsection II-A2. The reformulation was necessary to incorporate
feedback into the classifier identification problem. The drawback of $P1$ and
$P2$ is that the control cost of the entire trajectory is not optimized but
gets optimized at every stage, which may be not be optimal for entire
trajectory, i.e., it is not the outcome or “stage” optimization problem of a
dynamic programming problem.

###  III-B Stochastic Scenario

Consider the scenario depicted in Figure 2 / Figure 5. The scenario was
generated by a predetermined path, i.e., no feedback involved, which was
tracked by the agent. Observations were collected at $27$ positions. The
labels at many of the positions are flipped as depicted in the figure. The
collected data set is not linearly separable. Hence, the arguments used in the
previous section are not applicable here. Given this data set there are many
candidates for the true classifier. In Figure 5, we have plotted $3$ of the
possible candidates. For candidate $l_{1}$ there are $6$ violations, i.e, $6$
of the observed labels are not classified correctly. For candidates $l_{2}$
and $L_{3}$ there are $7$ and $6$ violations respectively. When the last SVM
algorithm was run with this data set, the resulting classifier was $l_{3}$ as
it maximized the minimum distance from the classifier. Hence, executing a
predetermined path and treating the noisy data as ”deterministic” data is not
helpful.

Figure 5: Possible classifiers with noisy data set

Let $\\{\hat{\mathcal{F}}_{t}\\}_{t\geq 0}$ be the $\sigma$ algebra generated
by $\\{\\{\zeta(j)\\}^{t}_{j=0},Y(0),\\{\bar{Y}(j)\\}^{t}_{j=1}\\}$. If we
consider a dynamic programming approach to solve the stochastic control
problem formulated in subsection II-B4, our first observation is that the
total identification cost is decomposable in to identification cost at every
stage. An ”estimated” label at $(X(j),Z(j))$ could be assigned through
threshold policies which are functions of
$\mathbb{E}_{\mathbb{P}_{j-1}}[Y(j)|\hat{\mathcal{F}}_{j}]$. However, the
computation of this conditional expectation would require the knowledge of
$\mathcal{X},\mathcal{X}^{c}$, i.e., the parameters of the true classifier
which is not available. In the following we consider an alternate approach
where the computation of this conditional expectation is not needed.

Given the four initial points with the true label known, we can find a region
of certainty for either label. When the agent moves to a new point in the
state space and collects an observation,i.e., corrupted label at a point in
the state space, the new data point leads to an “increase” in the region of
certainity but with a certain probability. As more data points are collected
the region of certainty for both labels increases but with a distribution on
the region. Equivalently, the four initial points gives us a set (union of
disjoint intervals), $E_{\theta,0}$ to which the true slope
$\theta^{*}=\arctan(\rho^{*})$ belongs and an interval, $I_{c,0}$, to which
$c^{*}$ belongs. Every sequence of data points, generates a finite collection
of subsets of $E_{\theta,0}/I_{c,0}$ to which $\theta^{*}/c^{*}$ belongs with
a certain probability. Hence, the data points collected build a distribution
on the set of values that the slope and the intercept can take. Our objective
is to choose the data points that enhances the identification process.

At step $t$, let $E_{\theta,t}$ denote the finite collection of subsets of
$E_{\theta,0}$ generated by the data points collected until $t$ to which
$\theta^{*}$ belongs. Each $E_{\theta,t,j}\in E_{\theta,t}$ is the disjoint
union of two intervals or an interval by itself. $\theta^{*}$ belongs to one
of the sets, $E_{\theta,t,j}$. We would like to quantify the probability with
which $\theta^{*}\in E_{\theta,t,j}$. There are $2^{t}$ possibilities for
$\\{Y(j)\\}^{t}_{j=1}$, some of which leads to a subset $E_{\theta,t,j}\in
E_{\theta,t}$. From the definition of $\bar{Y}(j,\omega)$,
$Y(j,\omega)=\bar{Y}(j,\omega)\varepsilon(j,\omega)$. Given
$\\{\bar{Y}(j,\omega)\\}^{t}_{j=1}=\\{y_{j}\\}^{t}_{j=1}$, every
$\\{\varepsilon(j,\omega)\\}^{t}_{j=1}=\\{e_{j}\\}^{t}_{j=1}$ generates a
possible true label sequence,
$\\{Y(j,\omega)\\}^{t}_{j=1}=\\{y_{j}\\}^{t}_{j=1}$, as
$y_{j}=\bar{y}_{j}e_{j},\;j=1,\ldots t$. It is not necessary that every
sequence $\\{Y(j,\omega)\\}^{t}_{j=1}=\\{y_{j}\\}^{t}_{j=1}$ can be used to
find a subset of $E_{\theta,0}$ to which $\theta^{*}$ belongs. Only the
sequences that lead to linearly separable data set, i.e.,
$\\{\zeta(t,\omega),Y(t,\omega)\\}\cup\\{(p_{1},-1),(p_{2},1),(p_{3},1),(p_{4},-1)\\}$
is linearly separable, are considered as valid sequences. We define
$E_{t}(\cdot)$ as

$\displaystyle
E_{t}(\\{\bar{Y}(j)\\}^{t}_{j=1})=\\{\\{\varepsilon(j)\\}^{t}_{j=1}:\\{\zeta(j),\bar{Y}(j)\varepsilon(j)\\}^{t}_{j=1}\cup$
$\displaystyle\\{\zeta(0),Y(0)\\}\cup\\{(p_{1},-1),(p_{2},1),(p_{3},1),(p_{4},-1)\\}\\}$

is linearly separable and $\bar{E}_{t}(\cdot)$ as

$\displaystyle\bar{E}_{t}(\\{Y(j)\\}^{t}_{j=1}$
$\displaystyle|\\{\bar{Y}(j)\\}^{t}_{j=1})=$
$\displaystyle\\{\\{\varepsilon(j)\\}^{t}_{j=1}:Y(j)=\bar{Y}(j)\varepsilon(j),\;j=1,\ldots
t\\}.$

We note that if $\\{\varepsilon(j)=e_{j}\\}^{t-1}_{j=1}\notin
E_{t-1}(\\{\bar{Y}(j)\\}^{t-1}_{j=1})$, then
$\\{\varepsilon(j)=e_{j}\\}^{t-1}_{j=1}\cup\\{\varepsilon(t)=e_{t}\\}\notin
E_{t}(\\{\bar{Y}(j)\\}^{t}_{j=1})$ for $e_{t}=1/-1$. Given
$\\{\bar{Y}(j)\\}^{t}_{j=1}$, let $\\{\varepsilon(j)\\}^{t}_{j=1}\in
E_{t}(\\{\bar{Y}(j)\\}^{t}_{j=1})$. For
$\\{Y(j)=\bar{Y}(j)\varepsilon(j)\\}^{t}_{j=1}$, we define,

$\displaystyle\bar{\mathbb{P}}_{t}\Big{(}\\{Y(j)\\}^{t}_{j=1}\Big{|}\\{\zeta(j)\\}^{t}_{j=0},Y(0),\\{\bar{Y}(j)\\}^{t}_{j=1},E_{t}(\\{\bar{Y}(j)\\}^{t}_{j=1})\Big{)}$
$\displaystyle\overset{\Delta}{=}\bar{\mathbb{P}}_{t}\Big{(}\bar{E}_{t}(\\{Y(j)\\}^{t}_{j=1}|\\{\bar{Y}(j)\\}^{t}_{j=1})\Big{|}\\{\zeta(j)\\}^{t}_{j=0},Y(0),E_{t}(\cdot)\Big{)}.$

The expression for this conditional probability has been stated in Equation 8.
Some observations about the conditional probability are as follows. The
numerator and every term in the denominator gets multiplied by
$\bar{\mathbb{P}}_{t-1}(E_{z,t-1})$ but does not appear in the equation as it
is a common factor. It might appear that the conditional probability does not
depend on the probability of the events, $\\{\zeta(j)\in
F_{j}\\}^{t-1}_{j=0},Y(0)\in\bar{F},\\{\varepsilon(j)\in
E_{j}\\}^{t-1}_{j=1}$. However on the contrary, the probability associated
with theses events is hidden in the conditional distribution associated with
the control policy, $\\{\Gamma_{j}\\}^{t-1}_{j=0}$.

$\displaystyle\bar{\mathbb{P}}_{t}\Big{(}\\{\varepsilon(j)\in
E_{j}\\}^{t}_{j=1}\Big{|}\Big{(}\\{\zeta(j)\in
F_{j}\\}^{t}_{j=0},Y(0)\in\bar{F}\Big{)},E_{t}(\cdot)\Big{)}=\frac{\bar{\mathbb{P}}_{t}\Big{(}\\{\varepsilon(j)\in
E_{j}\\}^{t}_{j=1},\Big{(}\\{\zeta(j)\in
F_{j}\\}^{t}_{j=1},Y(0)\in\bar{F}\Big{)},E_{t}(\cdot)\Big{)}}{\bar{\mathbb{P}}_{t}\Big{(}\Big{(}\\{\zeta(j)\in
F_{j}\\}^{t}_{j=0},Y(0)\in\bar{F}\Big{)},E_{t}(\cdot)\Big{)}}$
$\displaystyle=\dfrac{\Big{(}\chi_{E_{t}}(1)\big{(}p\Gamma_{t-1}[E_{z,t-1}](U\in
E_{u,1,t})+\Gamma_{t-1}[E_{z,t-1}](U\in
E_{u,2,t})\big{)}+\chi_{E_{j}}(-1)(1-p)\Gamma_{t-1}[E_{z,t-1}](U\in
E_{u,1,t})\Big{)}}{\underset{\begin{subarray}{c}\hskip 25.0pt\\\ \hskip
12.0ptE_{t}(\\{\bar{Y}(j)\\}^{t}_{j=1})\end{subarray}}{\sum}\Big{(}\chi_{E_{t}}(1)\big{(}p\Gamma_{t-1}[E_{z,t-1}](U\in
E_{u,1,t})+\Gamma_{t-1}[E_{z,t-1}](U\in
E_{u,2,t})\big{)}+\chi_{E_{j}}(-1)(1-p)\Gamma_{t-1}[E_{z,t-1}](U\in
E_{u,1,t})\Big{)}}$ (8) $\displaystyle E_{z,t-1}=\\{\\{\zeta(j)\in
F_{j}\\}^{t-1}_{j=0},Y(0)\in\bar{F},\\{\varepsilon(j)\in
E_{j}\\}^{t-1}_{j=1},\\{\varepsilon(j)\\}^{t-1}_{j=1}\in
E_{t-1}(\\{\bar{Y}(j)\\}^{t-1}_{j=1})\\},\;E_{u,1,t}(F_{t-1})=\\{U\in\mathcal{U}:$
$\displaystyle\phi(\zeta(t-1),U)\in
F_{t}\cap\mathbb{R}^{2}\sim\bar{E},\zeta(t-1)\in
F_{t-1}\\},\;E_{u,2,t}(F_{t-1})=\\{U\in\mathcal{U}:\phi(\zeta(t-1),U)\in
F_{t}\cap\bar{E},\zeta(t-1)\in F_{t-1}\\}.$
$\displaystyle\mathbb{P}_{t}(\zeta(t+1)\in
F_{t+1}|\mathcal{I}_{t})=\frac{\mathbb{P}_{t}(\zeta(t+1)\in
F_{t+1}\cap\mathcal{I}_{t})}{\mathbb{P}_{t}(\mathcal{I}_{t})}=\frac{\sum_{\\{e_{j}\\}^{t}_{j=1}}\mathbb{P}_{t}(\\{\varepsilon(j)=e_{j}\\}^{t}_{j=1}\cap\zeta(t+1)\in
F_{t+1}\cap\mathcal{I}_{t})}{\mathbb{P}_{t}(\mathcal{I}_{t})}$
$\displaystyle=\frac{\sum_{\\{e_{j}\\}^{t}_{j=1}}\Gamma_{t}[E_{\mathcal{I}_{t}}](U\in
E_{u,t}(F_{t},F_{t+1}))\mathbb{P}_{t}(E_{\mathcal{I}_{t}})}{\mathbb{P}_{t}(\mathcal{I}_{t})}=\sum_{\\{e_{j}\\}^{t}_{j=1}}\Gamma_{t}[E_{\mathcal{I}_{t}}](U\in
E_{u,t}(F_{t},F_{t+1}))\bar{\mathbb{P}}_{t}(\\{\varepsilon(j)=e_{j}\\}^{t}_{j=1}|\mathcal{I}_{t}),$
$\displaystyle\;\text{where},\;E_{\mathcal{I}_{t}}=E_{z,t}=\\{\\{\varepsilon(j)=e_{j}\\}^{t}_{j=1}\cap\mathcal{I}_{t}\\}\;\text{and}\;E_{u,t}(F_{t},F_{t+1})=\\{U\in\mathcal{U}:\phi(\zeta(t),U)\in
F_{t+1},\zeta(t)\in F_{t}\\}.$ (9)

We note that conditioning on the event
$\\{E_{t}(\\{\bar{Y}(j)\\}^{t}_{j=1})\\}$ not only changes the normalization
term, i.e, the denominator in Equation 8 but also the event corresponding to
the control policy, $\Gamma_{j}[\cdot]$.

Every valid true label sequence$,\\{Y_{j}\\}^{t}_{j=0}$, i.e., a sequence
which is linearly separable, generates a subset $E_{\theta,t,j}$ of
$E_{\theta,0}$ to which $\theta^{*}$ belongs. We note that $E_{\theta,t,j}$
obtained from the data set need not be a subset of $E_{\theta,0}$, however
letting $E_{\theta,t,j}=E_{\theta,t,j}\cap E_{\theta,0}$ since $\theta^{*}\in
E_{\theta,0}$ Similarly, the same true label sequence generates a subset
$I_{c,t,j}$ of $I_{c,0}$ to which $c^{*}$ belongs. The conditional probability
with which $\theta^{*}$ and $c^{*}$ belongs to the sets $E_{\theta,t,j}$ and
$I_{c,t,j}$ respectively is defined as the conditional probability of the
corresponding true label sequence, i.e,

$\displaystyle\mathbb{P}_{t}(\theta^{*}\in
E_{\theta,t,j}|\mathcal{I}_{t})=\mathbb{P}_{t}(c^{*}\in
I_{c,t,j}|\mathcal{I}_{t})\overset{\Delta}{=}\bar{\mathbb{P}}_{t}\Big{(}\\{Y(j)\\}^{t}_{j=1}\Big{|}\mathcal{I}_{t}\Big{)},$

where
$\mathcal{I}_{t}=\\{\\{\zeta(j)\\}^{t}_{j=0},Y(0),\\{\bar{Y}(j)\\}^{t}_{j=1},E_{t}(\\{\bar{Y}(j)\\}^{t}_{j=1})\\}$.

The objective of the control problem is to steer this distribution to the
“true” distribution of $\theta^{*}$ quickly. The true distribution of
$\theta^{*}$ is that it belongs to a singleton set with probability $1$. To
find this singleton set, the sets $E_{\theta,t,j}$ need to be pruned as $t$
increases and the probability with which $\theta^{*}\in E_{\theta,t,j}$ needs
to increase. To achieve the same we consider the following control problems.
At stage $t$,

$\displaystyle P3:\hskip 28.45274pt$
$\displaystyle\max_{\Gamma_{t}}\mathbb{E}_{\mathbb{P}_{t}}\Big{[}||\zeta(t+1)-\zeta(t)||^{2}-\varrho||u||^{2}\Big{|}\mathcal{I}_{t}\Big{]}$
$\displaystyle\text{s.t}\;\;\zeta(t+1)$
$\displaystyle=\phi(\zeta(t),u),\zeta(t+1)\notin\mathcal{X}^{c}_{0},\zeta(t+1)\notin\mathcal{X}_{0}$
$\displaystyle\mathbb{E}_{\mathbb{P}_{t}}\Bigg{[}\arctan$
$\displaystyle(\frac{z(t+1)-z(t)}{x(t+1)-x(t)})|\mathcal{I}_{t}\Bigg{]}\notin
E_{\theta,t,j},\;\forall E_{\theta,t,j}\in E_{\theta,t}.$

The objective of the above control problem is move the agents in new
directions, directions which are not candidates for the slope of the true
line. By exploring the state space, the agent is able to get more pairs of
points which are close and are of opposite label. Through this step the
control problem is aiding the pruning of the sets $E_{\theta,t,j}$. Consider
the following control problem:

$\displaystyle P4:\hskip 28.45274pt$
$\displaystyle\max_{\Gamma_{t}}\mathbb{E}_{\mathbb{P}_{t}}\Big{[}||\zeta(t+1)-\zeta(t)||^{2}-\varrho||u||^{2}\Big{|}\mathcal{I}_{t}\Big{]}$
$\displaystyle\text{s.t}\;\;\zeta(t+1)$
$\displaystyle=\phi(\zeta(t),u),\zeta(t+1)\notin\mathcal{X}^{c}_{0},\zeta(t+1)\notin\mathcal{X}_{0}$
$\displaystyle\exists E_{\theta,t,j}\in E_{\theta,t}\;$
$\displaystyle\text{s.t}\;\mathbb{E}_{\mathbb{P}_{t}}\Bigg{[}\arctan(\frac{z(t+1)-z(t)}{x(t+1)-x(t)})|\mathcal{I}_{t}\Bigg{]}\in
E_{\theta,t,j}.$

The objective of the above control problem is to ensure that agent visits
regions of state space that will enhance its belief about the set to which
$\theta^{*}$ belongs, i.e, increase or reduce the conditional probability with
which $\theta^{*}$ belongs to a set $E_{\theta,t,j}$. The objective is to
reduce the entropy of the distribution
$\bar{\mathbb{P}}_{t}\Big{(}\\{Y(j)\\}^{t}_{j=1}\Big{|}\mathcal{I}_{t}\Big{)}$.
i.e., reduce the uncertainty in the distribution. This is achieved by moving
in directions which are possible candidates to the true slope. If the observed
data points are as expected, then conditional probability $\theta^{*}$ belongs
to the set of current direction is expected to increase. The solution to this
problem could also lead to pruning of the sets to which $\theta^{*}$ belongs.
From Equation 9, solving $(P3/P4)$ invokes
$\bar{\mathbb{P}}_{t}(\\{\varepsilon(j)\in
E_{j}\\}^{t}_{j=1}|\mathcal{I}_{t})$, results in the control policy
$\Gamma_{t}(E_{z,t})$, which is then invoked to calculate
$\bar{\mathbb{P}}_{t+1}(\\{\varepsilon(j)\in
E_{j}\\}^{t+1}_{j=1}|\mathcal{I}_{t+1})$. From Equations 8 and 9, we conclude
that at any stage $t$, by solving $P3$ and $P4$ we are manipulating
$\bar{\mathbb{P}}_{t+1}(\\{\varepsilon(j)\in
E_{j}\\}^{t+1}_{j=1}|\mathcal{I}_{t+1})$ through optimization of
$\mathbb{P}_{t+1}(\zeta(t+1)\in F_{t+1}|\mathcal{I}_{t})$. $P3$ and $P4$ are
stochastic analogs to $P1$ and $P2$ respectively.

##  IV Algorithms

In this section, we present control algorithms to solve the problem presented
in subsection I-B. We present both deterministic and stochastic scenarios.

###  IV-A Deterministic Scenario

The control algorithm executed by the agent is presented in Algorithm 1. In
this algorithm, at any given position if the agent has seen a label flip from
its past position through execution of $P1$ at its past position, the agent
solves $P2$ and moves to a new position. At the new position, the agent solves
$P1$ and moves to new positions until it observers a label flip. The objective
of $P1$ is to obtain points which are close to each other but of opposite
label; hence executed multiple times until the objective is achieved. The
objective of $P2$ is to obtain points which are of the same label but far from
each other. It is executed only once as even if the objective is not met, it
results in points with opposite labels which are far from each other. At
$t=0$, the agent begins by solving $P1$ and repeats the same until a label
flip is observed.

Given the data set after $m$ stages, $\\{x(j),z(j),y_{j}\\}^{m}_{=1}$, the
distance between pairs with opposite labels is found. Of all the pairs, two
pairs which have the shortest distance between them are chosen. Let the four
points be $(p_{1,m},-1)$, $(p_{2,m},1)$, $(p_{3,m},1)$ $(p_{4,m},-1)$.
Consider then quadrilateral formed by $(p_{1,m},p_{2,m},p_{3,m},p_{4,m})$ and
let the diagonals intersect at $p_{m}$. Consider the angle formed by
$p_{1,m},p_{m},p_{2,m}$. The line that bisects this angle whose slope is
$\rho_{m}$ and intercept is $c_{m}$ is declared as the estimate of the true
classifier.

Algorithm 1 Control for classification

1:procedure CFC

2: Given $(p_{1},-1),(p_{2},1),(p_{3},1),(p_{4},-1)$, $\phi(\cdot)$, and
$\mathcal{U}$.

3: $\zeta(0)\leftarrow p_{1},y(0)\leftarrow-1$

4: $j\leftarrow 0,Label\leftarrow-1,Counter\leftarrow 0$

5: while $j\leq m-1$ do

6: if $Counter\mod 2=0$ then

7: Solve $P1$ to obtain $U(j)$.

8: Agent moves to $\zeta(j+1)\leftarrow\phi(\zeta(j),U(j))$

9: $j\leftarrow j+1$, collect observation $Y(j)$.

10: if $Y(j)\times Label=-1$ then

11: $Label\leftarrow Y(j)$

12: $Counter\leftarrow Counter+1$

13: else

14: Solve $P2$ to obtain $U(j)$.

15: Agent moves to $\zeta(j+1)\leftarrow\phi(\zeta(j),U(j))$

16: $j\leftarrow j+1$, collect observation $Y(j)$.

17: $Counter\leftarrow Counter+1$

######  Proposition IV.1.

As the number of data points increases, estimated classifier converges to the
true classifier, i.e., $\underset{m\to\infty}{\lim}\rho_{m}=\rho^{*}$ and
$\underset{m\to\infty}{\lim}c_{m}=c^{*}$.

###### Proof.

From the constraints of the optimization problems $(P1)$ and $(P2)$, we note
that a given point in the state space is not visited twice. This is because
once the agent visits a point and the true label at that point is known, that
point becomes a part of the region of certainty associated with that label.
Further, a point in the region of certainty at stage $m$ is not visited by the
agent at any time $n$, $n\geq m+1$. Hence, a given point is not visited twice.
From earlier arguments, we note that the region of certainty for both labels
is a strictly monotonic sequence of sets,
$\mathcal{X}_{m}\subset\mathcal{X}_{m+1}$ and
$\mathcal{X}^{c}_{m}\subset\mathcal{X}^{c}_{m+1},\;\forall m$. Since
$\mathcal{X}_{m}\subset\mathcal{X}$ and
$\mathcal{X}^{c}_{m}\subset\mathcal{X}^{c}$ for all $m$,
$\underset{m\to\infty}{\lim}\mathcal{X}_{m}=\mathcal{X}$ and
$\underset{m\to\infty}{\lim}\mathcal{X}^{c}_{m}=\mathcal{X}^{c}$. The
monotonicity of sequences $\\{\mathcal{X}_{t}\\}$ and
$\\{\mathcal{X}^{c}_{t}\\}$ implies that for any $\epsilon>0$ there exists
$p_{1,\epsilon}$, $p_{2,\epsilon}$ such
$d(p_{1,\epsilon},p_{2,\epsilon})<\epsilon$ with opposite labels. Thus, there
exists a sequence of pairs of points, $\\{p_{1,n},p_{2,n}\\}$, such that
$label(p_{1,n})\times label(p_{2,n})=-1$ and the distance between the points,
$d(p_{1,n},p_{2,n})$ converges to zero.

Figure 6: Analysis of the problem using analytical geometry

Invoking the radial co-ordinates of the points as indicated in Figure 6, we
note that

$\displaystyle d(p_{1,\epsilon},p_{2,\epsilon})=$
$\displaystyle\sqrt{(r_{2}\cos(\theta_{2})-r_{1}\cos(\theta_{1}))^{2}+(r_{2}\sin(\theta_{2})-r_{1}\sin(\theta_{1}))^{2}}$

Hence as $d(p_{1,\epsilon},p_{2,\epsilon})$ converges to $0$,
$\theta_{2}-\theta_{1}\to 0$ and $r_{2}-r_{1}\to 0$, i.e., the points collapse
to a point on the true classifier. Hence, the control algorithm generates
points which are arbitrarily close to the true classifier. By considering 2
pairs, $p_{1,\epsilon},p_{2,\epsilon}$ and $p_{3,\epsilon},p_{4,\epsilon}$
such that $d(p_{1,\epsilon},p_{2,\epsilon})<\epsilon$ and
$d(p_{3,\epsilon},p_{4,\epsilon})<\epsilon$ while
$d(p_{1,\epsilon},p_{4,\epsilon})>\delta$ or
$d(p_{2,\epsilon},p_{3,\epsilon})>\delta$, the estimated classifier obtained
is then arbitrarily close to true classifier in the sense of parameter norm,
$|\rho_{\epsilon}-\rho^{*}|<\epsilon,|c_{\epsilon}-c^{*}|<\epsilon$. Letting
$\epsilon\to 0$, we obtain the result of the proposition. ∎

###  IV-B Stochastic Scenario

The control algorithm for the stochastic scenario is described in Algorithm 2.
The agent solves $P1$ at all even time steps (including $0$) and $P2$ at all
odd time steps. The most likely action from the resulting conditional
distributions, $\Gamma_{j}$, is chosen at every time step. After $m$ stages,
the finite collections of sets $\\{E_{\theta,m,k}\\}$ and$\\{I_{c,m,k}\\}$ and
their associated conditional probabilities
$\bar{\mathbb{P}}_{t}(\\{\varepsilon(k)\in
E_{k}\\}^{j}_{k=1}|\mathcal{I}_{j})$ are considered. The outcome of the
algorithm are the sets $E_{\theta,m,k^{*}}$ and $I_{c,m,k^{*}}$ which have the
highest conditional probability,
$\bar{\mathbb{P}}_{m}(\\{\varepsilon(k)=e^{*}_{k}\\}^{m}_{k=1}|\mathcal{I}_{m})$,
i.e, $\theta^{*}\in E_{\theta,m,k^{*}},c^{*}\in I_{c,m,k^{*}}$ with
conditional probability
$\bar{\mathbb{P}}_{m}(\\{\varepsilon(k)=e^{*}_{k}\\}^{m}_{k=1}|\mathcal{I}_{m})$.

Algorithm 2 Stochastic Control for classification

1:procedure SCC

2: Given $(p_{1},-1),(p_{2},1),(p_{3},1),(p_{4},-1)$, $\phi(\cdot)$, and
$\mathcal{U}$.

3: Given $p\in[0,1]$, $\zeta(0)\leftarrow p_{1},y(0)\leftarrow-1$,
$j\leftarrow 0$

4: while $j\leq m-1$ do

5: if $j\mod 2=0$ then

6: Solve $P1$ to obtain $\Gamma_{j}$.

7: else

8: Solve $P2$ to obtain $\Gamma_{j}$.

9:
$U(j)=\underset{u\in\mathcal{U}}{\operatorname*{arg\,max}}\;\;\Gamma_{j}[E_{j,z}](u)$.

10: Agent moves to $\zeta(j+1)\leftarrow\phi(\zeta(j),U(j))$

11: $j\leftarrow j+1$, collect observation $Y(j)$

12: Update $\\{E_{\theta,j,k}\\}$, $\\{I_{c,j,k}\\}$

13: Update $\bar{\mathbb{P}}_{j}(\\{\varepsilon(k)\in
E_{k}\\}^{j}_{k=1}|\mathcal{I}_{j})$

Further investigation is needed to prove the convergence of the above
algorithm to the true classifier.

##  V Examples

Figure 7: Path of the Agent with unicycle model and noiseless observations

In this section, we present an example illustrating the implementation of each
of the control algorithms described in the previous section. We consider a
$20m\times 20m$ region in $\mathbb{R}^{2}$. We are given four initial points
with their true labels as indicated in Figure 7. We consider a unicycle model
for the agent:

$\displaystyle x(t+1)=x(t)+v(t)\cos(\theta(t+1)),$ $\displaystyle
z(t+1)=z(t)+v(t)\sin(\theta(t+1)),$
$\displaystyle\theta(t+1)=\theta(t)+w(t),\;\text{where}\;U=[v,w].$

In the above model, each time step is a two step processes. First, $\theta$
gets updated using the angular velocity. Following this step, once the
direction of travel gets fixed, the positions get updated using velocity. With
this model problem $P1$ (and similarly $P2$) gets modified to,

$\displaystyle P1:\;\;$
$\displaystyle\max_{u\in\mathcal{U}}||v(t)||^{2}-\varrho(||v(t)||^{2}+||w(t)||^{2})$
$\displaystyle\text{s.t}\;\;\zeta(t+1)=\phi(\zeta(t),u),\zeta(t+1)\notin\mathcal{X}^{c}_{t},$
$\displaystyle\zeta(t+1)\notin\mathcal{X}_{t},\;\theta(t+1)\notin E_{\rho,t}$

We consider $v(\cdot)\in\\{0,0.1,0.2,\ldots,2\\}$ with unit, m/ unit time. We
consider
$w(\cdot)\in\\{-\frac{\pi}{2},\ldots,-0.01,0.0,0.01,\ldots,\frac{\pi}{2}\\}$
with unit, rad/ unit time. $\varrho$ was set to $0.1$, thus enabling the agent
to utilize higher values of $w$ resulting in quick change of orientation. With
this setup, Algorithm 1 was run for $10$ steps. The path followed by the agent
is indicated in Figure 7. The $10$ data points gathered were utilized to
estimate the classifier. The parameters corresponding to the estimated
classifier were $\rho_{10}=0.38/\theta_{10}=0.36\;rad\;=20.8^{\circ}\deg$ and
$c_{10}=3.6$ while corresponding values of the true classifier where
$\rho^{*}=0.41/\theta^{*}=0.389\;rad\;=22.29^{\circ}\deg$ and $c_{10}=3.5$.
Thus, in this example the classifier was estimated with high accuracy. With
the same setup, simulations were run in the stochastic setting with the
probability of not flipping equal to $0.7$. The simulation was run for $10$
steps. The trajectory followed by the agent has been plotted in Figure 8. The
outcome of running Algorithm 2 was that, it was estimated that
$\theta^{*}\in[18.42,25.81]^{\circ}\deg$ and $c^{*}\in[3.12,3.76]$ with
probability $0.84$. The estimated region of the state space to which the true
classifier belongs after $10$ steps has been marked in Figure 8. The region is
bounded by lines $l_{1}$ and $l_{2}$. Further investigation is needed, to
prove that this region can be shrunk to the true classifier with high
probability.

Figure 8: Path of the Agent with unicycle model and noisy observations

##  VI Conclusion and Future Work

To summarize, we considered the problem of identification of a linear
classifier by an agent with noiseless and noisy data. We presented geometric
interpretation of the problem which was then utilized to develop efficient
control algorithms. Data obtained as a result of the control algorithms was
used to identify the classifier. When the data is noiseless, we prove the
convergence of the estimated classifier to the true classifier. When the data
was noisy, the identification process resulted in sets to which the parameters
of the true classifier belongs with high probability.

As future work, we are interested in understanding the control problems which
when analyzed using dynamic programming would result in value functions which
are obtained through optimization problems similar to the one step control
problems formulated in this paper. We would like to investigate the
convergence of the estimated classifier to the true classifier in the
stochastic case in suitable topology. Formal connections to dual control and
adaptive sampling are to be established.

## References

  * [1] E. Todorov, “General duality between optimal control and estimation,” in _2008 47th IEEE conference on decision and control_. IEEE, 2008, pp. 4286–4292.
  * [2] S. Ishii, W. Yoshida, and J. Yoshimoto, “Control of exploitation–exploration meta-parameter in reinforcement learning,” _Neural networks_ , vol. 15, no. 4-6, pp. 665–687, 2002.
  * [3] T. Alpcan and I. Shames, “An information-based learning approach to dual control,” _IEEE transactions on neural networks and learning systems_ , vol. 26, no. 11, pp. 2736–2748, 2015.
  * [4] E. D. Klenske and P. Hennig, “Dual control for approximate bayesian reinforcement learning,” _Journal of Machine Learning Research_ , vol. 17, no. 127, pp. 1–30, 2016.
  * [5] A. Mesbah, “Stochastic model predictive control with active uncertainty learning: A survey on dual control,” _Annual Reviews in Control_ , vol. 45, pp. 107–117, 2018.
  * [6] H. Hu and J. F. Fisac, “Active uncertainty reduction for human-robot interaction: An implicit dual control approach,” in _International Workshop on the Algorithmic Foundations of Robotics_. Springer, 2022, pp. 385–401.
  * [7] Y. LeCun, “A path towards autonomous machine intelligence version 0.9. 2, 2022-06-27,” _Open Review_ , vol. 62, no. 1, 2022.
  * [8] Y. Becerikli, A. F. Konar, and T. Samad, “Intelligent optimal control with dynamic neural networks,” _Neural networks_ , vol. 16, no. 2, pp. 251–259, 2003.
  * [9] J. Sabouri, S. Effati, and M. Pakdaman, “A neural network approach for solving a class of fractional optimal control problems,” _Neural Processing Letters_ , vol. 45, pp. 59–74, 2017.
  * [10] C. Sánchez-Sánchez and D. Izzo, “Real-time optimal control via deep neural networks: study on landing problems,” _Journal of Guidance, Control, and Dynamics_ , vol. 41, no. 5, pp. 1122–1135, 2018.
  * [11] K. Djouzi, K. Beghdad-Bey, and A. Amamra, “A new adaptive sampling algorithm for big data classification,” _Journal of Computational Science_ , vol. 61, p. 101653, 2022.
  * [12] P. Singh, J. v. d. Herten, D. Deschrijver, I. Couckuyt, and T. Dhaene, “A sequential sampling strategy for adaptive classification of computationally expensive data,” _Structural and Multidisciplinary Optimization_ , vol. 55, pp. 1425–1438, 2017.
  * [13] S. Shekhar, G. Fields, M. Ghavamzadeh, and T. Javidi, “Adaptive sampling for minimax fair classification,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 24 535–24 544, 2021.
  * [14] Y. Ding, J. Feng, Y. Chong, S. Pan, and X. Sun, “Adaptive sampling toward a dynamic graph convolutional network for hyperspectral image classification,” _IEEE Transactions on Geoscience and Remote Sensing_ , vol. 60, pp. 1–17, 2021.
  * [15] B. Zhang and G. S. Sukhatme, “Adaptive sampling for estimating a scalar field using a robotic boat and a sensor network,” in _Proceedings 2007 IEEE International Conference on Robotics and Automation_. IEEE, 2007, pp. 3673–3680.
  * [16] M. Bernstein, R. Graham, D. Cline, J. M. Dolan, and K. Rajan, “Learning-based event response for marine robotics,” in _2013 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2013, pp. 3362–3367.
  * [17] P. Stankiewicz, Y. T. Tan, and M. Kobilarov, “Adaptive sampling with an autonomous underwater vehicle in static marine environments,” _Journal of Field Robotics_ , vol. 38, no. 4, pp. 572–597, 2021.
  * [18] T. O. Fossum, J. Ryan, T. Mukerji, J. Eidsvik, T. Maughan, M. Ludvigsen, and K. Rajan, “Compact models for adaptive sampling in marine robotics,” _The International Journal of Robotics Research_ , vol. 39, no. 1, pp. 127–142, 2020.
  * [19] A. Raghavan, G. Sartori, and K. H. Johansson, “Motion planning for the estimation of functions,” in _2023 62nd IEEE Conference on Decision and Control (CDC)_. IEEE, 2023, pp. 7150–7155.
  * [20] V. I. Paulsen and M. Raghupathi, _An introduction to the theory of reproducing kernel Hilbert spaces_. Cambridge university press, 2016, vol. 152.
  * [21] T. Hofmann, B. Schölkopf, and A. J. Smola, “Kernel methods in machine learning,” _The annals of statistics_ , vol. 36, no. 3, pp. 1171–1220, 2008\.


# Kleene Star of the Primes is not Regular in Any Base

Jason Yuen
School of Computer Science
University of Waterloo
Waterloo, ON N2L 3G1
Canada
<EMAIL_ADDRESS>
###### Abstract

Let $P_{b}$ denote the primes expressed in base-$b$. In this note, we prove
that $P_{b}^{*}$ is not regular. This strengthens a classical result that
$P_{b}$ is not regular, due to Minsky and Papert in 1966.

##  1 Introduction

Let $P_{b}$ be the language of primes expressed in base $b\geq 2$, using the
most significant digit first, and disallowing leading zeroes. Minsky and
Papert [2] proved in 1966 that $P_{b}$ is not regular. Furthermore, Shallit
[4] proved in 1996 that any finite automaton that correctly recognizes primes
up to $N$ must have $\Omega(N^{1/43})$ states. Hartmanis and Shank [1], and,
independently, Schützenberger [3] proved in 1968 that the primes are not
context-free.

We show a new result that $P_{b}^{*}$ is not regular. Firstly, assume
$P_{b}^{*}$ is regular. Using number theory, we find a prime of the form
$K\times b^{n}+1$ where $K$ is sufficiently large, and $k\times b^{n}+1$ is
composite for all $k<K$. Using the classical pumping lemma for regular
languages, $P_{b}^{*}$ contains $k\times b^{n}+1$ for some $k<K$. This leads
to a contradiction.

##  2 The main theorem

######  Theorem 1 (Dirichlet).

Let $a,d\geq 1$ be coprime. Then there are infinitely many primes of the form
$a+kd$ where $k\geq 1$.

######  Definition 2.

For each $b\geq 2$, define $f_{b}:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ as follows.
For each $n$, let $f_{b}(n)$ be the smallest $k$ such that $k\times b^{n}+1$
is prime. By Dirichlet’s Theorem with $(a,d)=(1,b^{n})$, there are infinitely
many primes of the form $k\times b^{n}+1$ with $k\geq 1$, thus $f_{b}(n)$ is
well-defined.

######  Proposition 3.

Let $b\geq 2$ and $K\geq 1$. There exists $N\geq 2$ such that $f_{b}(N)>K$.

###### Proof.

Let $N=(bK)!+1$. Note that $N\geq 2!+1>2$. It remains to show $f_{b}(N)>K$.

Let $1\leq k\leq K$. We show that $bk+1$ is a factor of $k\times b^{N}+1$.
Firstly, consider $\operatorname{ord}(b)$ in $\mathbb{Z}_{bk+1}$. Since
$\gcd(b,bk+1)=1$, we have $b\in\mathbb{Z}_{bk+1}^{*}$ and
$\operatorname{ord}(b)\leq bk\leq bK$. Therefore, $b^{(bK)!}\equiv
1\pmod{bk+1}$. Compute $k\times b^{N}+1$ in $\mathbb{Z}_{bk+1}$:

$k\times b^{N}+1\equiv bk\times b^{(bK)!}+1\equiv bk\times 1+1\equiv
0\pmod{bk+1}$

Therefore, $bk+1\mid k\times b^{N}+1$. Firstly, $bk+1\geq 2+1>1$. Secondly,
$N\geq 2$ implies $bk+1<k\times b^{N}+1$. Therefore, $k\times b^{N}+1$ is
composite. It follows that $f_{b}(N)>K$. ∎

######  Definition 4.

For $b\geq 2$ and $n\geq 0$, let $(n)_{b}$ be $n$ expressed in base $b$, with
the most significant digit first, and with no leading zeroes.

######  Lemma 5.

Let $b\geq 2$ and $n\geq 1$. Let $1\leq k<f_{b}(n)$. Then $(k\times
b^{n}+1)_{b}\notin P_{b}^{*}$.

###### Proof.

Let $x=(k\times b^{n}+1)_{b}=(k)_{b}0^{n-1}1$. For the sake of contradiction,
suppose $x\in P_{b}^{*}$. Therefore, there is a suffix $z$ such that $x=yz$
and $z\in P_{b}$. Consider the cases for the first index of $z$.

If $z$ starts with $0$ then $z\notin P_{b}$. If $z=1$ then $z\notin P_{b}$.
Lastly, suppose the first index of $z$ is in $(k)_{b}$. Then $z$ represents
$k^{\prime}\times b^{n}+1$ where $1\leq k^{\prime}\leq k$. Since $1\leq
k^{\prime}\leq k<f_{b}(n)$, $k^{\prime}\times b^{n}+1$ is not prime, so
$z\notin P_{b}$. Contradiction. ∎

######  Theorem 6.

Let $b\geq 2$. $P_{b}^{*}$ is not regular.

###### Proof.

For the sake of contradiction, suppose $P_{b}^{*}$ is regular. Let $p\geq 1$
be the pumping length of $P_{b}^{*}$. By Proposition 3, let $N\geq 2$ such
that $f_{b}(N)>b^{p}$. Consider the string:

$s=(f_{b}(N)\times b^{N}+1)_{b}=(f_{b}(N))_{b}0^{N-1}1$

Note that $f_{b}(N)\times b^{N}+1$ is prime. Therefore, $s\in P_{b}$ and $s\in
P_{b}^{*}$.

Since $f_{b}(N)>b^{p}$, we have $|(f_{b}(N))_{b}|\geq|(b^{p})_{b}|=p+1$.

By the pumping lemma, there exists a decomposition $s=xyz$ where $|y|\geq 1$,
$|xy|\leq p$, and $xy^{i}z\in P_{b}^{*}$ for all $i\geq 0$. Consider $xz\in
P_{b}^{*}$. Since $|xy|<|(f_{b}(N))_{b}|$, $y$ is a subword of
$(f_{b}(N))_{b}$. Therefore, $xz$ represents $k\times b^{N}+1$ for some $0\leq
k<f_{b}(N)$. We reject $k=0$ because $xz$ cannot start with $0$. We reject
$1\leq k<f_{b}(N)$ because Lemma 5 implies $xz\notin P_{b}^{*}$.
Contradiction. ∎

######  Corollary 7.

Let $b\geq 2$. $P_{b}$ is not regular.

###### Proof.

We can now recover the result by Minsky and Papert. If $L$ is a regular
language, then $L^{*}$ is regular. From Theorem 6, it follows that $P_{b}$ is
not regular. ∎

##  3 Acknowledgment

I thank Jeffrey Shallit for telling me about this problem.

## References

  * [1] J. Hartmanis and H. Shank.  On the recognition of primes by automata.  J. Assoc. Comput. Mach. 15 (1968), 382–389.
  * [2] M. Minsky and S. Papert.  Unrecognizable sets of numbers.  J. Assoc. Comput. Mach. 13 (1966), 281–286.
  * [3] M. P. Schützenberger.  A remark on acceptable sets of numbers.  J. Assoc. Comput. Mach. 15 (1968), 300–303.
  * [4] J. Shallit.  Automaticity IV: Sequences, sets, and diversity.  J. Théorie Nombres Bordeaux 8 (1996), 347–367.