CT^{\kappa}\|v\|_{Y^{1}_{T}}^{p}\|v\|_{Y^{s}_{T}},\quad\kappa>0$

will be enough. Its proof follows by combining the following propositions. The
next statement is a slightly modified version of [7, Theorem 3].

######  Proposition 6.1.

For $s\geq 1$ there exists a constant $C>0$ such that

(6.2) $\|u^{p}\|_{X^{s-1,\frac{1}{2}}}\leq
C\|u\|_{Y^{s}}\,\|u\|_{Y^{1}}^{p-1}\,.$

We shall also need the following bilinear estimate.

######  Proposition 6.2.

For $s\geq 1$ there exists $C>0$ such that, for $T\in(0,1)$,

$\big{\|}\Pi(\Pi u_{1}\Pi u_{2})\|_{Z^{s}}\leq
CT^{\kappa}\big{(}\|u_{1}\|_{X^{s-1,\frac{1}{2}}_{T}}\|u_{2}\|_{X^{0,\frac{1}{2}}_{T}}+\|u_{1}\|_{X^{0,\frac{1}{2}}_{T}}\|u_{2}\|_{X^{s-1,\frac{1}{2}}_{T}}\big{)},\quad\kappa>0\,.$

Let us see how (6.1) is a consequence of both propositions: from Proposition
6.2 we get

$\big{\|}\Pi(\partial_{x}v\Pi
v^{p})\big{\|}_{Z^{s}}=\big{\|}\Pi(\Pi\partial_{x}v\Pi
v^{p})\big{\|}_{Z^{s}}\leq
CT^{\kappa}\big{(}\|v^{p}\|_{X^{s-1,\frac{1}{2}}}\|\partial_{x}v\|_{X^{0,\frac{1}{2}}}+\|v^{p}\|_{X^{0,\frac{1}{2}}}\|\partial_{x}v\|_{X^{s-1,\frac{1}{2}}}\big{)}.$

Next, using Proposition 6.1, we get

$\|v^{p}\|_{X^{s-1,\frac{1}{2}}}\leq
C\|v\|_{Y^{s}}\,\|v\|_{Y^{1}}^{p-1}\,,\quad\|v^{p}\|_{X^{0,\frac{1}{2}}}\leq
C\|v\|_{Y^{1}}^{p}\,$

and we get (6.1).

###### Proof of Proposition 6.1.

Write

(6.3)
${\mathcal{F}}(u^{p})(\tau,n)=\int_{\tau=\tau_{1}+\cdots+\tau_{p}}\,\,\,\sum_{n=n_{1}+\cdots+n_{p}}\,\,\prod_{k=1}^{p}\hat{u}(\tau_{k},n_{k})\,,$

where ${\mathcal{F}}$ and $\hat{u}$ denote the space time Fourier transform
(continuous in time and discrete in space).

(6.4)
$\|u^{p}\|_{X^{s-1,\frac{1}{2}}}^{2}=\int_{{\mathbb{R}}}\sum_{n\in{\mathbb{Z}}}\langle
n\rangle^{2(s-1)}\langle\tau+n^{3}\rangle\,|{\mathcal{F}}(u^{p})(\tau,n)|^{2}\,d\tau\,.$

Notice that the r.h.s. in (6.4) may be bounded with

(6.5) $\int_{{\mathbb{R}}}\sum_{n\in{\mathbb{Z}}}\langle
n\rangle^{2(s-1)}\langle\tau+n^{3}\rangle\big{(}\int_{\tau=\tau_{1}+\cdots+\tau_{p}}\,\,\sum_{n=n_{1}+\cdots+n_{p}}\,\,\prod_{k=1}^{p}|\widehat{u}(\tau_{k},n_{k})|\big{)}^{2}\,d\tau.$

Hence if we define $w(t,x)$ by $\hat{w}(\tau,n)=|\hat{u}(\tau,n)|$ we get
$\|u\|_{X^{s,b}}=\|w\|_{X^{s,b}}$, $\|u\|_{Y^{s}}=\|w\|_{Y^{s}}$, and we are
reduced to estimate

(6.6) $\int_{{\mathbb{R}}}\sum_{n\in{\mathbb{Z}}}\langle
n\rangle^{2(s-1)}\langle\tau+n^{3}\rangle\,\big{(}\int_{\tau=\tau_{1}+\cdots+\tau_{p}}\,\,\sum_{n=n_{1}+\cdots+n_{p}}\,\,\prod_{k=1}^{p}\widehat{w}(\tau_{k},n_{k})\big{)}^{2}d\tau\,\,\,.$

Next we split the domain of integration and we consider first the contribution
to (6.6) in the region

(6.7) $|\tau+n^{3}|\leq 10p|\tau_{1}+n_{1}^{3}|.$

If we define $w_{1}$ by
$\widehat{w_{1}}(\tau,n)=\langle\tau+n^{3}\rangle^{\frac{1}{2}}\,\widehat{w}(\tau,n)$,
then the contribution to (6.6) in the region (6.7) can be controlled in the
physical space variables as follows

$\displaystyle C\|w_{1}w^{p-1}\|_{L^{2}({\mathbb{R}};H^{s-1})}^{2}\leq$
$\displaystyle
C\big{(}\|w_{1}\|_{L^{2}({\mathbb{R}};H^{s-1})}^{2}\|w^{p-1}\|_{L^{\infty}({\mathbb{R}};L^{\infty})}^{2}+\|w_{1}\|_{L^{2}({\mathbb{R}};L^{\infty})}^{2}\|w^{p-1}\|_{L^{\infty}({\mathbb{R}};H^{s-1})}^{2}\big{)}$
$\displaystyle\leq$ $\displaystyle
C\big{(}\|w\|_{X^{s-1,\frac{1}{2}}}^{2}\|w\|_{L^{\infty}({\mathbb{R}};H^{1})}^{2(p-1)}+\|w_{1}\|_{L^{2}({\mathbb{R}};H^{1})}^{2}\|w\|_{L^{\infty}({\mathbb{R}};H^{s-1})}^{2}\|w\|_{L^{\infty}({\mathbb{R}};H^{1})}^{2(p-2)}\big{)}$

where we have used standard product rules and Sobolev embedding $H^{1}\subset
L^{\infty}$. We proceed with

$(\dots)\leq
C\big{(}\|w\|_{X^{s-1,\frac{1}{2}}}^{2}\|w\|_{Y^{1}}^{2(p-1)}+\|w_{1}\|_{X^{1,\frac{1}{2}}}^{2}\|w\|_{Y^{s-1}}^{2}\|w\|_{Y^{1}}^{2(p-2)}\big{)}$

where we used $Y^{1}\subset L^{\infty}({\mathbb{R}};H^{1})$, $Y^{s-1}\subset
L^{\infty}({\mathbb{R}};H^{s-1})$. Notice that we have a better estimate, when
compared with (6.2), in the region (6.7). Similarly, we can evaluate the
contributions to (6.6) of the regions

$|\tau+n^{3}|\leq 10p|\tau_{k}+n_{k}^{3}|,\quad 2\leq k\leq p\,.$

Therefore, we may assume that the summation and the integration in (6.6) is
performed in the region

(6.8) $\max_{1\leq k\leq
p}|\tau_{k}+n_{k}^{3}|\leq\frac{1}{10p}|\tau+n^{3}|\,.$

Write

$(\tau+n^{3})-\sum_{k=1}^{p}(\tau_{k}+n_{k}^{3})=\Big{(}\sum_{k=1}^{p}n_{k}\Big{)}^{3}-\sum_{k=1}^{p}n_{k}^{3}\,,$

therefore in the region (6.8) we have

$\Big{|}\Big{(}\sum_{k=1}^{p}n_{k}\Big{)}^{3}-\sum_{k=1}^{p}n_{k}^{3}\Big{|}\geq|\tau+n^{3}|-\sum_{k=1}^{p}|\tau_{k}+n_{k}^{3}|\geq\frac{9}{10}|\tau+n^{3}|$

hence

$\langle\tau+n^{3}\rangle\leq
C\Big{|}\Big{(}\sum_{k=1}^{p}n_{k}\Big{)}^{3}-\sum_{k=1}^{p}n_{k}^{3}\Big{|}\,.$

By symmetry we can assume $|n_{1}|\geq|n_{2}|\geq\cdots\geq|n_{k}|$ and by
using [7, Lemma 4.1], we obtain that

$\Big{|}\Big{(}\sum_{k=1}^{p}n_{k}\Big{)}^{3}-\sum_{k=1}^{p}n_{k}^{3}\Big{|}\leq
C|n_{1}|^{2}|n_{2}|.$

Consequently in the region (6.8) we get $\langle\tau+n^{3}\rangle\leq C\langle
n_{1}\rangle^{2}\langle n_{2}\rangle$, and the corresponding contribution to
(6.6) can be estimated as

(6.9)
$C\,\int_{{\mathbb{R}}}\sum_{n\in{\mathbb{Z}}}\,\big{(}\int_{\tau=\tau_{1}+\cdots+\tau_{p}}\,\,\sum_{n=n_{1}+\cdots+n_{p}}\,\langle
n_{1}\rangle^{s}\langle
n_{2}\rangle^{\frac{1}{2}}\,\prod_{k=1}^{p}(\widehat{w}(\tau_{k},n_{k})\big{)}^{2}\,d\tau$

If we define $w_{1}$, $w_{2}$ by $\widehat{w_{1}}(\tau,n)=\langle
n\rangle^{s}\widehat{w}(\tau,n)$, $\widehat{w_{2}}(\tau,n)=\langle
n\rangle^{\frac{1}{2}}\widehat{w}(\tau,n)$, going back to physical space
variables, we estimate (6.9) as

$\displaystyle C\|w_{1}w_{2}w^{p-2}\|_{L^{2}({\mathbb{R}};L^{2})}^{2}\leq$
$\displaystyle
C\|w_{1}\|_{L^{\infty}({\mathbb{R}};L^{2})}^{2}\|w_{2}\|_{L^{4}({\mathbb{R}};L^{\infty})}^{2}\|w\|_{L^{4}({\mathbb{R}};L^{\infty})}^{2}\|w\|_{L^{\infty}({\mathbb{R}};L^{\infty})}^{2(p-3)}$
$\displaystyle\leq$ $\displaystyle
C\|w\|_{L^{\infty}({\mathbb{R}};H^{s})}^{2}\|w_{2}\|_{L^{4}({\mathbb{R}};W^{\frac{1}{2},4})}^{2}\|w\|_{L^{4}({\mathbb{R}};W^{1,4})}^{2}\|w\|_{L^{\infty}({\mathbb{R}};H^{1})}^{2(p-3)}.$

Hence by using $Y^{1}\subset L^{\infty}({\mathbb{R}};H^{1})$ and $Y^{s}\subset
L^{\infty}({\mathbb{R}};H^{s})$, along with the estimate

(6.10) $\|u\|_{L^{4}({\mathbb{R}};L^{4})}\leq C\|u\|_{X^{0,\frac{1}{3}}}$

established in the fundamental work [1], we proceed with

$(\dots)\leq
C\|w\|_{Y^{s}}^{2}\|w\|_{X^{1,\frac{1}{3}}}^{2}\|w\|_{X^{1,\frac{1}{3}}}^{2}\|w\|_{Y^{1}}^{2(p-3)}$

and this concludes the proof. ∎

###### Proof of Proposition 6.2.

We start with proving

(6.11) $\big{\|}\Pi(\Pi u_{1}\Pi u_{2}))\|_{X^{s,-\frac{1}{2}}}\leq
CT^{\kappa}\big{(}\|u_{1}\|_{X^{s-1,\frac{1}{2}}_{T}}\|u_{2}\|_{X^{0,\frac{1}{2}}_{T}}+\|u_{1}\|_{X^{0,\frac{1}{2}}_{T}}\|u_{2}\|_{X^{s-1,\frac{1}{2}}_{T}}\big{)}.$

As a first step we prove an estimate for global in time functions:

(6.12) $\big{\|}\Pi(\Pi u_{1}\Pi u_{2}))\|_{X^{s,-\frac{1}{2}}}\leq
C\big{(}\|u_{1}\|_{X^{s-1,\frac{1}{2}}}\times\|u_{2}\|_{X^{0,\frac{1}{3}}}+\|u_{1}\|_{X^{s-1,\frac{1}{3}}}\times\|u_{2}\|_{X^{0,\frac{1}{2}}}\\\
+\|u_{1}\|_{X^{0,\frac{1}{3}}}\times\|u_{2}\|_{X^{s-1,\frac{1}{2}}}+\|u_{1}\|_{X^{0,\frac{1}{2}}}\times\|u_{2}\|_{X^{s-1,\frac{1}{3}}}\big{)}.$

Notice that by comparing (6.11) and (6.12) in the second estimate we gain
derivatives but we loose a positive power of the time $T$. We will prove
toward the end how to go from (6.12) to (6.11).

The square of the left hand-side of (6.12) may be written as

$\int_{{\mathbb{R}}}\sum_{n\neq 0}\langle
n\rangle^{2s}\langle\tau+n^{3}\rangle^{-1}|{\mathcal{F}}(\Pi u_{1}\Pi
u_{2})(\tau,n)|^{2}\,d\tau\,,$

and moreover we easily have

$|{\mathcal{F}}(\Pi u_{1}\Pi u_{2})(\tau,n)|\leq\sum_{n_{1}\neq
0,n}\int_{{\mathbb{R}}}|\hat{u}_{1}(\tau_{1},n_{1})||\hat{u}_{2}(\tau-\tau_{1},n-n_{1})|d\tau_{1}\,.$

For $j=1,2$, define $w_{j}(t,x)$ with
$\hat{w}_{j}(\tau,n)=|\hat{u}_{j}(\tau,n)|$. Then, we estimate the left hand-
side of (6.12) as

$\int_{{\mathbb{R}}}\sum_{n\neq 0}\frac{\langle
n\rangle^{2s}}{\langle\tau+n^{3}\rangle}\Big{(}\sum_{n_{1}\neq
0,n}\int_{{\mathbb{R}}}\hat{w}_{1}(\tau_{1},n_{1})\hat{w}_{2}(\tau-\tau_{1},n-n_{1})d\tau_{1}\Big{)}^{2}d\tau\,$

which in turn by a duality argument is bounded with

$\sup_{\|v\|_{L^{2}_{t,x}}\leq 1}\int_{\mathbb{R}}\sum_{n\neq 0}\frac{\langle
n\rangle^{s}}{\langle\tau+n^{3}\rangle^{\frac{1}{2}}}\sum_{n_{1}\neq
0,n}\int_{{\mathbb{R}}}\hat{w}_{1}(\tau_{1},n_{1})\hat{w}_{2}(\tau-\tau_{1},n-n_{1})|\hat{v}(\tau,n)|d\tau_{1}d\tau\,.$

For $n\neq 0$ and $n_{1}\neq 0,n$, we have $\langle n\rangle^{s}\leq
C|n_{1}|^{\frac{1}{2}}|n-n_{1}|^{\frac{1}{2}}|n|^{\frac{1}{2}}\big{(}\langle
n_{1}\rangle^{s-1}+\langle n-n_{1}\rangle^{s-1}\big{)}$. Therefore, by using a
symmetry argument, it suffices to evaluate

(6.13) $\sup_{\|u\|_{L^{2}_{t,x}}\leq 1}\int_{{\mathbb{R}}^{2}}\sum_{n\neq
0,n_{1}\neq
0,n}\frac{|n_{1}|^{\frac{1}{2}}|n-n_{1}|^{\frac{1}{2}}|n|^{\frac{1}{2}}}{\langle\tau+n^{3}\rangle^{\frac{1}{2}}}\,\big{(}\langle
n_{1}\rangle^{s-1}\hat{w}_{1}(\tau_{1},n_{1})\big{)}\hat{w}_{2}(\tau-\tau_{1},n-n_{1})|\hat{v}(\tau,n)|d\tau_{1}d\tau\,.$

The key property for smoothing is the elementary bound

$\max\Big{(}\langle\tau+n^{3}\rangle^{\frac{1}{2}},\langle\tau_{1}+n_{1}^{3}\rangle^{\frac{1}{2}},\langle\tau-\tau_{1}+(n-n_{1})^{3}\rangle^{\frac{1}{2}}\Big{)}\geq
C|n_{1}|^{\frac{1}{2}}|n-n_{1}|^{\frac{1}{2}}|n|^{\frac{1}{2}}\,.$

We will consider a splitting of the expression in (6.13) in three
contributions taking into account which term is the maximum in the above
elementary bound. Notice that the contribution of (6.13) in the following
region

(6.14) $\langle\tau+n^{3}\rangle^{\frac{1}{2}}\geq
C|n_{1}|^{\frac{1}{2}}|n-n_{1}|^{\frac{1}{2}}|n|^{\frac{1}{2}}\,$

may be estimated as

$C\|w_{2}\times v_{1}\times\langle
D_{x}\rangle^{s-1}w_{1}\|_{L^{1}({\mathbb{R}};L^{1})}\leq
C\|v\|_{L^{2}_{t,x}}\|\langle
D_{x}\rangle^{s-1}w_{1}\|_{L^{4}({\mathbb{R}};L^{4})}\|w_{2}\|_{L^{4}({\mathbb{R}};L^{4})}\,$

where $v_{1}(t,x)$ is defined with $\hat{v}_{1}(\tau,n)=|\hat{v}(\tau,n)|$.
Now, using (6.10), we write

$\displaystyle\|\langle
D_{x}\rangle^{s-1}w_{1}\|_{L^{4}({\mathbb{R}};L^{4})}\leq$ $\displaystyle
C\|w_{1}\|_{X^{s-1,\frac{1}{3}}}=C\|u_{1}\|_{X^{s-1,\frac{1}{3}}}$
$\displaystyle\|w_{1}\|_{L^{4}({\mathbb{R}};L^{4})}\leq$ $\displaystyle
C\|w_{1}\|_{X^{0,\frac{1}{3}}}=C\|u_{1}\|_{X^{0,\frac{1}{3}}}\,.$

Hence we can estimate the contribution to (6.13) in the region (6.14) by

$\|u_{1}\|_{X^{s-1,\frac{1}{3}}}\times\|u_{2}\|_{X^{0,\frac{1}{3}}}$

up to a multiplicative constant. Next we consider the contribution to (6.13)
in the region

(6.15) $\langle\tau_{1}+n_{1}^{3}\rangle^{\frac{1}{2}}\geq
C|n_{1}|^{\frac{1}{2}}|n-n_{1}|^{\frac{1}{2}}|n|^{\frac{1}{2}}\,.$

Let $v_{1}(t,x)$ be defined by

$\widehat{v}_{1}(\tau,n)=\langle\tau+n^{3}\rangle^{-\frac{1}{2}}|\hat{v}(\tau,n)|$

and let $w_{11}(t,x)$ be defined as

$\hat{w}_{11}(\tau,n)=\langle
n\rangle^{s-1}\langle\tau+n^{3}\rangle^{\frac{1}{2}}\hat{w}_{1}(\tau,n)\,,$

then we can estimate the contribution of(6.13) in the region (6.15) by

$C\|w_{11}\times w_{2}\times v_{1}\|_{L^{1}({\mathbb{R}};L^{1})}\leq
C\|w_{11}\|_{L^{2}({\mathbb{R}};L^{2})}\|w_{2}\|_{L^{4}({\mathbb{R}};L^{4})}\|v_{1}\|_{L^{4}({\mathbb{R}};L^{4})}$

Using again (6.10) we obtain that

$\displaystyle\|v_{1}\|_{L^{4}({\mathbb{R}};L^{4})}\leq$ $\displaystyle
C\|v\|_{X^{0,-\frac{1}{6}}}\leq C\|v\|_{L^{2}({\mathbb{R}};L^{2})}\,,$
$\displaystyle\|w_{2}\|_{L^{4}({\mathbb{R}};L^{4})}\leq$ $\displaystyle
C\|w_{2}\|_{X^{0,\frac{1}{3}}}\leq C\|u_{2}\|_{X^{0,\frac{1}{3}}}\,.$

Moreover we have

$\|w_{11}\|_{L^{2}({\mathbb{R}};L^{2})}=\|w_{1}\|_{X^{s-1,\frac{1}{2}}}=\|u_{1}\|_{X^{s-1,\frac{1}{2}}}$

and summarizing we control the contribution to (6.13) in the region (6.15) by
$\|u_{1}\|_{X^{s-1,\frac{1}{2}}}\times\|u_{2}\|_{X^{0,\frac{1}{3}}}$ up to a
multiplicative factor. Finally consider the contribution to (6.13) on the
third region

(6.16) $\langle\tau-\tau_{1}+(n-n_{1})^{3}\rangle^{\frac{1}{2}}\geq
C|n_{1}|^{\frac{1}{2}}|n-n_{1}|^{\frac{1}{2}}|n|^{\frac{1}{2}}\,.$

Retain $v_{1}(t,x)$ with
$\hat{v}_{1}(\tau,n)=\langle\tau+n^{3}\rangle^{-\frac{1}{2}}|\hat{v}(\tau,n)|$
and let $w_{21}(t,x)$ be defined with
$\hat{w}_{21}(\tau,n)=\langle\tau+n^{3}\rangle^{\frac{1}{2}}\hat{w}_{2}(\tau,n)$.
Then we can control the contribution to (6.13) in the region (6.16) by

$\displaystyle C\|w_{21}\times v_{1}\times\langle
D_{x}\rangle^{s-1}w_{1}\|_{L^{1}({\mathbb{R}};L^{1})}\leq$ $\displaystyle
C\|\langle
D_{x}\rangle^{s-1}w_{1}\|_{L^{4}({\mathbb{R}};L^{4})}\|w_{21}\|_{L^{2}({\mathbb{R}};L^{2})}\|v_{1}\|_{L^{4}({\mathbb{R}};L^{4})}\,$
$\displaystyle\leq$ $\displaystyle
C\|u_{1}\|_{X^{s-1,\frac{1}{3}}}\|u_{2}\|_{X^{0,\frac{1}{2}}}\|v\|_{X^{0,-\frac{1}{6}}}$

where we have used again (6.10). Hence the contribution of (6.13) in the
region (6.16) can be estimated, up to a multiplicative constant, by
$\|u_{1}\|_{X^{s-1,\frac{1}{3}}}\times\|u_{2}\|_{X^{0,\frac{1}{2}}}$.
Summarizing, we estimate (6.13) by

$\|u_{1}\|_{X^{s-1,\frac{1}{2}}}\times\|u_{2}\|_{X^{0,\frac{1}{3}}}+\|u_{1}\|_{X^{s-1,\frac{1}{3}}}\times\|u_{2}\|_{X^{0,\frac{1}{2}}}$

for functions $u_{1}$ and $u_{2}$ which are not localized in time. Recall that
by symmetry, in order to estimate the l.h.s. in (6.12), we need to add further
terms where the role of $u_{1}$ and $u_{2}$ has exchanged. Hence we have
established (6.12) which, as already said, in some sense is stronger than
(6.11), since less conormal derivatives of $u_{1}$ and $u_{2}$ are involved,
but it is weaker than (6.11) since no gain of positive power of $T$ has been
obtained in (6.12). We finally deal with this issue: as a consequence of [47,
Lemma 2.11] (see also [8, Lemma 3.2]) there exists $\kappa>0$ such that

$\|w\|_{X^{s-1,\frac{1}{3}}_{T}}\leq
CT^{\kappa}\|w\|_{X^{s-1,\frac{1}{2}}_{T}},\quad\|w\|_{X^{0,\frac{1}{3}}_{T}}\leq
CT^{\kappa}\|w\|_{X^{0,\frac{1}{2}}_{T}},$

and we complete the proof of (6.11) by combining the estimates above with
(6.12), along with a suitable choice of extensions for $u_{1}$ and $u_{2}$,
which a priori are defined on the strip of time $(-T,T)$, on the whole space
time with a global norm of the extension which is at most twice the
corresponding localized norm. ∎

## References

  * [1] J. Bourgain, Fourier restriction phenomena for certain lattice subsets and applications to nonlinear evolution equations, Parts I; II, Geometric Funct. Anal. 3(2) (1993) 107–156; 3(3) (1993) 209–262.
  * [2] J. Bourgain, On the Cauchy problem for periodic KdV-type equations, Proceedings of the Conference in honor of Jean-Pierre Kahane (Orsay, 1993), J. Fourier Anal. Appl. (1995) 17–86.
  * [3] J. Bourgain, Periodic nonlinear Schrödinger equation and invariant measures, Comm. Math. Phys., 166 (1994) 1–26.
  * [4] J. Bourgain, Invariant measures for the 2d-defocusing nonlinear Schrödinger equation, Comm. Math. Phys., 176 (1996) 421–445.
  * [5] J. Bourgain, On the growth in time of higher Sobolev norms of smooth solutions of Hamiltonian PDE, Internat. Math. Res. Notices, (1996) 6, 277–304.
  * [6] A. Chapouto, N. Kishimoto, Invariance of the Gibbs measures for periodic generalized Korteweg-de Vries equations, arXiv:2104.07382
  * [7] J. Colliander, M. Keel, G. Staffilani, H. Takaoka, T. Tao, Multilinear estimates for periodic KdV equations, and applications J. Funct. Anal. 211 (2004), 173–218.
  * [8] J. Colliander, T. Oh, Almost sure well-posedness of the cubic nonlinear Schrödinger equation below $L^{2}({\mathbb{T}})$. Duke Math. J. 161 (2012), 367–414.
  * [9] A. Debussche, Y. Tsustumi, Quasi-Invariance of Gaussian Measures Transported by the Cubic NLS with Third-Order Dispersion on ${\mathbb{T}}$, arXiv:2002.04899 (2020).
  * [10] Y. Deng, N. Tzvetkov, N. Visciglia, Invariant measures and long time behaviour for the Benjamin-Ono equation III, Comm. Math. Phys. 339 (2015), 815–857.
  * [11] J. Forlano, K. Seong, Transport of Gaussian measures under the flow of one-dimensional fractional nonlinear Schrödinger equations, arXiv:2102.13398 [math.AP] (2021).
  * [12] J. Forlano, W. Trenberth, On the transport of Gaussian measures under the one-dimensional fractional nonlinear Schrödinger equation, Ann. Inst. Henri Poincare, Anal. Non Lineaire, 36 (2019), 1987-2025.
  * [13] L. Friedlander, An invariant measure for the equation $u_{tt}-u_{xx}+u^{3}=0$, Comm. Math. Phys., 98 (1985) 1–16.
  * [14] G. Genovese, R. Lucà, N. Tzvetkov, Quasi-invariance of low regularity Gaussian measures under the gauge map of the periodic derivative NLS, arXiv:2008.10001v1 (2020).
  * [15] G. Genovese, R. Lucà, N. Tzvetkov, Transport of Gaussian measures with exponential cut-off for Hamiltonian PDEs, arXiv:2103.04408 [math.AP] (2021).
  * [16] G. Genovese, R. Lucà, D, Valeri, Invariant measures for the periodic derivative nonlinear Schrödinger equation, Mathematische Annalen 374 (3-4), 1075-1138, 2019.
  * [17] J. Ginibre, Y. Tsutsumi, G. Velo, On the Cauchy problem for the Zakharov system, J. Funct. Anal. 151 (1997), no. 2, 384–436.
  * [18] T. S. Gunaratnam, T. Oh, N. Tzvetkov, H. Weber, Quasi-invariant Gaussian measures for the nonlinear wave equation in three dimensions, arXiv:1808.03158 (2018).
  * [19] Z. Hani, B. Pausader, N. Tzvetkov, N. Visciglia, Modified scattering for the cubic Schrödinger equation on product spaces and applications, Forum Math. PI 3 (2015), e4, 63 pp.
  * [20] T. Kappeler, J. Pöschel, KdV and KAM, A Series of Modern Surveys in Mathematics , 45. Springer-Verlag, Berlin, 2003. xiv+279 pp.
  * [21] T. Kato, T On the Cauchy problem for the (generalized) Korteweg-de Vries equation, Advances in Math. Suppl. Stud., (1983), 93–128.
  * [22] C. Kenig, G. Ponce, L. Vega, On the (generalized) Korteweg-de Vries equation, Duke Math. J. 59 (1989) 585–610.
  * [23] C. Kenig, G. Ponce, L. Vega, Oscillatory integrals and regularity of dispersive equations, Indiana Univ. Math. J. 40 (1991) 33–69.
  * [24] C. Kenig, G. Ponce, L. Vega, Well-posedness and scattering results for the generalized Korteweg-de Vries equation via the contraction principle, Comm. Pure Appl. Math. 46 (1993) 527–620.
  * [25] J. Lebowitz, R. Rose, E. Speer, Statistical dynamics of the nonlinear Schrödinger equation, J. Stat. Physics, 50 (1988) 657–687.
  * [26] Y. Martel, Asymptotic N-soliton-like solutions of the subcritical and critical generalized Korteweg-de Vries equations, Amer. J. Math. 127 (2005), no. 5, 1103–1140.
  * [27] Y. Martel, F. Merle, P. Raphaël, Blow up for the critical generalized Korteweg?de Vries equation. I: Dynamics near the soliton, Acta Math. 212 (2014) 59–140.
  * [28] Y. Martel, F. Merle, P. Raphaël, Blow up for the critical gKdV equation. II: Minimal mass dynamics, J. Eur. Math. Soc. (JEMS) 17 (2015) 1855–1925.
  * [29] Y. Martel, F. Merle, P. Raphaël, Blow up for the critical gKdV equation III: exotic regimes, Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) 14 (2015), no. 2, 575–631.
  * [30] Y. Martel, D. Pilod, Finite point blowup for the critical generalized Korteweg-de Vries equation, arXiv:2107.00268 [math.AP]
  * [31] T. Oh, K. Seong, Quasi-invariant Gaussian measures for the cubic fourth order nonlinear Schrd̈inger equation in negative Sobolev spaces, arXiv:2012.06732 [math.AP] (2020).
  * [32] S. Oh, A. Stefanov, Smoothing and growth bound of periodic generalized Korteweg-de Vries equation, arXiv:2001.08984 [math.AP]
  * [33] T. Oh, G. Richards, L. Thomann, On invariant Gibbs measures for the generalized KdV equations, Dyn. Partial Differ. Equ. 13 (2016) 133–153.
  * [34] T. Oh, N. Tzvetkov, Quasi-invariant Gaussian measures for the cubic fourth order nonlinear Schrödinger equation, Probab. Theory Relat. Fields 169 (2017), 1121-1168.
  * [35] T. Oh, N. Tzvetkov, Quasi-invariant Gaussian measures for the two-dimensional defocusing cubic nonlinear wave equation, JEMS 22 (2020), no. 6, 1785–1826.
  * [36] T. Oh, P. Sosoe, N. Tzvetkov, An optimal regularity result on the quasi-invariant Gaussian measures for the cubic fourth order nonlinear Schrödinger equation, J. Ec. Polytechnique, Math., 5 (2018), 793-841.
  * [37] T. Oh, Y. Tsutsumi and N. Tzvetkov, Quasi-invariant Gaussian measures for the cubic nonlinear Schroedinger equation with third-order dispersion, C. R. Acad. Sci. Paris, Ser. I, 357 (2019), 366-381.
  * [38] F. Planchon, N. Tzvetkov and N. Visciglia, On the growth of Sobolev norms for NLS on 2- and 3-dimensional manifolds. Anal. PDE 10 (2017) 1123–1147.
  * [39] F. Planchon, N. Tzvetkov and N. Visciglia, Transport of Gaussian measures by the flow of the nonlinear Schrödinger equation, Math. Ann. 378 (2020) 389-423.
  * [40] G. Richards, Invariance of the Gibbs measure for the periodic quartic gKdV, Ann. Inst. H. Poincaré Anal. Non Linéaire 33 (2016) 699–766.
  * [41] J.C. Saut, Sur quelques généralisations de l’équation de Korteweg-de Vries, J. Math. Pures Appl. 58 (1979) 21–61.
  * [42] P. Schuur, Asymptotic analysis of soliton problems, Lect. Notes in Math., vol. 1232, Springer-Verlag, Berlin, 1986.
  * [43] P. Sosoe, W. J. Trenberth and T. Xiao, Quasi-invariance of fractional Gaussian fields by nonlinear wave equation with polynomial nonlinearity, arXiv:1906.02257v1 (2019).
  * [44] G. Staffilani, On solutions for periodic generalized KdV equations, IMRN 18 (1997) 899–917.
  * [45] G. Staffilani, On the growth of high Sobolev norms of solutions for KdV and Schrödinger equations, Duke Math. J. 86 (1997), 109–142.
  * [46] C. Sun, N. Tzvetkov, Gibbs measure dynamics of the fractional NLS, SIAM J. Math. Anal., 52(5), (2020) 4638-4704.
  * [47] T. Tao, Nonlinear dispersive equations. Local and global analysis, CBMS Regional Conference Series in Mathematics, 106. American Mathematical Society, Providence, RI, 2006. xvi+373 pp.
  * [48] N. Tzvetkov, Quasi-invariant Gaussian measures for one dimensional Hamiltonian PDEs, Forum Math. Sigma 3 (2015), e28, 35 pp.
  * [49] N. Tzvetkov, N. Visciglia, Gaussian measures associated to the higher order conservation laws of the Benjamin-Ono equation, Ann. Sci. ENS 46 (2013) 249–299 (2013).
  * [50] N. Tzvetkov, N. Visciglia, Invariant measures and long time behaviour for the Benjamin-Ono equation, Int. Math. Res. Not. 17 (2014) 4679–4614.
  * [51] N. Tzvetkov, N. Visciglia, Invariant measures and long time behaviour for the Benjamin-Ono equation II, J. Math. Pures Appl. 103 (2015), 102–141.
  * [52] N. Visciglia, The modified energy technique and applications,  Bollettino dell’ Unione Matematica Italiana 14(1) (2021), 3–16
  * [53] P. Zhidkov, Korteweg-de Vries and nonlinear Schrödinger equations: qualitative theory, Lecture Notes in Mathematics, 1756. Springer-Verlag, Berlin, 2001. vi+147 pp.


∎

11institutetext: Thuy Ngoc Nguyen 22institutetext: Duy Nhat Phan
33institutetext: Cleotilde Gonzalez 44institutetext: 5000 Forbes Ave.,
Pittsburgh, 15213 PA, USA
44email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
#  SpeedyIBL: A Solution to the Curse of Exponential Growth in Instance-Based
Learning Models of Decisions from Experience

Thuy Ngoc Nguyen  Duy Nhat Phan  Cleotilde Gonzalez *Corresponding author

###### Abstract

Computational cognitive modeling is a useful methodology to explore and
validate theories of human cognitive processes. Often cognitive models are
used to simulate the process by which humans perform a task or solve a problem
and to make predictions about human behavior. Cognitive models based on
Instance-Based Learning (IBL) Theory rely on a formal computational algorithm
for dynamic decision making and on a memory mechanism from a well-known
cognitive architecture, ACT-R. To advance the computational theory of human
decision making and to demonstrate the usefulness of cognitive models in
diverse domains, we must address a practical computational problem, the curse
of exponential growth, that emerges from memory-based tabular computations.
When more observations accumulate, there is an exponential growth of the
memory of instances that leads directly to an exponential slow down of the
computational time. In this paper, we propose a new Speedy IBL implementation
that innovate the mathematics of vectorization and parallel computation over
the traditional loop-based approach. Through the implementation of IBL models
in many decision games of increasing complexity, we demonstrate the
applicability of the regular IBL models and the advantages of their Speedy
implementation. Decision games vary in their complexity of decision features
and in the number of agents involved in the decision process. The results
clearly illustrate that Speedy IBL addresses the curse of exponential growth
of memory, reducing the computational time significantly, while maintaining
the same level of performance than the traditional implementation of IBL
models.

###### Keywords:

Instance-Based Learning Cognitive Models Efficient Computation

##  1 Introduction

A cognitive theory is a general postulation of mechanisms and processes that
are globally applicable to families of tasks and types of activities rather
than being dependent on a particular task. Cognitive models are very specific
representations of part or of all aspects of a cognitive theory that apply to
a particular task or activity gonzalez2017decision . Specifically, normative
and descriptive theories of choice often rely on utility theory Savage1954 ;
morgenstern1953theory  or aim at describing the psychological impact of
perceptions of probability and value on choice kahneman1979prospect ;
tversky1992advances . In contrast, models of decisions from experience (DfE)
are often dynamic computational representations of sequential choices that are
distributed over time and space and that are made under uncertainty
gonzalez2017dynamic .

Cognitive models of DfE can be used to simulate the interaction of theoretical
cognitive processes with the environment, representing a particular task.
These models can make predictions regarding how human choices are made in such
tasks. These predictions are often compared to data collected from human
participants in the same tasks using interactive tools. The explicit
comparison of cognitive models’ predictions to human actual behavior is a
common research approach in the cognitive sciences and in particular in the
study of decision making gonzalez2017decision . Cognitive models are dynamic
and adaptable computational representations of the cognitive structures and
mechanisms involved in decision making tasks such as DfE tasks under
conditions of partial knowledge and uncertainty. Moreover, cognitive models
are generative, in the sense that they actually make decisions in similar ways
like humans do, based on their own experience, rather than being data-driven
and requiring large training sets. In this regard, cognitive models differ
from purely statistical approaches, such as Machine Learning or Bayesian
models, that are often capable of evaluating stable, long-term sequential
dependencies from existing data but fail to account for the dynamics of human
cognition and human adaptation to novel situations.

There are many models of DfE as evidenced by past modeling competitions
erev2010choice ; erev2017anomalies . Most of these models often make broadly
disparate assumptions regarding the cognitive processes by which humans make
decisions erev2010choice . For example, the models submitted to these
competitions are often applicable to a particular task or choice paradigm
rather than presenting an integrated view of how the dynamic choice process
from experience is performed by humans. Associative learning models are a
class of models of DfE that conceptualize choice as a learning process that
stores behavior-outcome relationships and are contingent on the environment
hertwig2015 . Generally speaking, these kinds of models rely on learning from
reinforcement and the contingencies of the environment as in the Skinnerian
tradition skinner2014contingencies ; sutton1995theory . These models have
shown to be successful at representing human learning over time based on
feedback.

In contrast to many of the associative learning models, Instance-Based
Learning (IBL) models rely on a single decision theory: Instance-Based
Learning Theory GONZALEZ03 . IBLT emerged from the need to explain the process
of dynamic decision making, where a sequence of interdependent decisions were
made over time. IBLT provides a single general algorithm and mathematical
formulations of memory retrieval that rely on the ACT-R cognitive architecture
ANDERSON14 . The theory proposes a representation of decisions in the form of
instances, which are triplets involving state, action, and utilities; the
theory also provides a process of retrieval of past instances based on their
similarity to a current decision situation, and the generation of accumulated
value (from experience) based on a mechanism called Blending, which is a
function of the payoffs experienced and the probability of retrieving those
instances from memory LEJARRAGA12 ; GONZALEZ11 .

Many models have been developed based on IBLT. From its inception, the theory
was demonstrated in a highly complex, dynamic decision-making task
representing the complex process of dynamic allocation of limited resources
over time and under time constraints in a “water purification plant”
GONZALEZ03 . Since then, IBLT has been used to demonstrate human DfE in a
large diversity of contexts and domains, from simple and abstract binary
choice dynamics GONZALEZ11 ; LEJARRAGA12  to highly specialized and complex
tasks such as cyber defense aggarwal2020exploratory ; cranford2020toward  and
anti-phishing detection cranford2019modeling . Also, IBL models have been
created to account for group and network effects, where each individual in a
group is represented by an IBL agent gonzalez2015cognitive ; more recently,
this IBL algorithm has also been applied to multi-state gridworld tasks
NGUYEN20 ; NGUYEN2020ICCM ; Ngoc2021  in which the agents execute a sequence
of actions with delayed feedback.

The recent applications of IBL cognitive models have led to significantly more
complex and realistic tasks, where multi-dimensional state-action-utility
representations are required, where extended training is common, and where
multi-agents interact to solve such tasks. Such an increase in the task
complexities and the number of agents modeled with IBL leads to a practical
computational problem, the curse of exponential growth, (c.f.
bellman1957dynamic ) kuo2005lifting . The curse of exponential growth is a
common problem for every modeling approach that relies on the accumulation of
data over time and on tabular computation, such as reinforcement learning
models (RL) sutton2018reinforcement . Deep reinforcement learning, a
combination of RL and deep learning, enables to move from simple
representations to more realistic complex environments in games such as Atari,
Go, Starcraft mnih2013playing ; silver2016mastering ; vinyals2019alphastar .
However, as summarized in a recent overview of the challenges in multi-agent
RL models, these algorithms become less efficient with the increase in the
dimensions of the state-action space, and as the number of agents increases
wong2021multiagent . The problem becomes even more complex under nonstationary
environments and under uncertainty where information is incomplete. Dynamic
conditions significantly increase the diversity and number of states as it is
needed for every dynamic decision making task gonzalez2017dynamic .

In this paper, we propose a solution to the curse of exponential growth by
innovating the mathematics of vectorization and parallel computation over the
traditional loop-based approach larsen2000exploiting . We propose this new
method in a new Speedy IBL implementation. Importantly, we demonstrate how
SpeedyIBL is increasingly more efficient than traditional IBL model
implementations (PyIBL for Python-IBL, MorrisonGonzalez ), as the
dimensionality and dynamics of the problems increase. The costs of computation
in the PyIBL implementation grow exponentially as the dimensions of the
representation increase and the number of agents and their interactions
increase. The benefits of SpeedyIBL over regular PyIBL models, therefore,
increase also exponentially.

##  2 Instance based Learning Theory

The general decision process proposed in IBLT is illustrated in Figure 1, and
the mechanisms are made mathematically concrete in Algorithm 1 GONZALEZ03 .
The process starts with the observation of the environmental state, and the
determination of whether there are past experiences (i.e., instances) that are
similar to the current environmental state (i.e., Recognition). Whether there
are similar past instances will determine the process used to generate the
expected utility of a decision alternative (i.e., Judgment). If there are past
experiences that are similar to the current environmental state, the expected
utility of such an alternative is calculated via a process of Blending past
instances, but if there are no similar past instances, then the theory
suggests that a heuristic is used instead. After Judgment, the option with the
highest expected utility is maintained in memory and a decision is made as to
whether to stop the exploration of additional alternatives and execute the
current best decision (e.g., Choice). When the exploration process ends, a
choice is implemented, which changes the environment (i.e., Execution).
Feedback (e.g., reward) is received at any time from the environment, with or
without delay from the execution of a choice. Such feedback is used to update
past experiences since the last time feedback was received through a credit
assignment mechanism.

Figure 1: IBLT algorithm from GONZALEZ03

In IBLT, an “instance” is a memory unit that results from the potential
alternatives evaluated. These memory representations consist of three elements
which are constructed over time: a situation state $s$ which is composed of a
set of features $f$; a decision or action $a$ taken corresponding to an
alternative in state $s$; and an expected utility or experienced outcome $x$
of the action taken in a state.

Each instance in memory has an Activation value, which represents how readily
available that information is in memory, and it is determined by the
similarity to past situations, recency, frequency, and noise according to the
Activation equation in ACT-R ANDERSON14 . Activation of an instance is used to
determine the probability of retrieval of an instance from memory which is a
function of its activation relative to the activation of all instances
corresponding the same state in memory. The expected utility of a choice
option is calculated by blending past outcomes. This blending mechanism for
choice has its origins in a more general blending formulation
lebiere1999dynamics , but a simplification of this mechanism is often used in
models with discrete choice options, defined as the sum of all past
experienced outcomes weighted by their probability of retrieval GONZALEZ11 ;
LEJARRAGA12 . This formulation of blending represents the general idea of an
expected value in decision making, where the probability is a cognitive
probability, a function of the activation equation in ACT-R. Algorithm 1
provides a formal representation of the general IBL process.

1

Input: default utility $x_{0}$, a memory dictionary $\mathcal{M}=\\{\\}$,
global counter $t=1$, step limit $L$, a flag $delayed$ to indicate whether
feedback is delayed.

2 repeat

3 Initialize a counter (i.e., step) $l=0$ and observe state $s_{l}$

4 while  _$s_{l}$ is not terminal and $l<L$_ do

5 Execution Loop  __

6 Exploration Loop  _$a\in A$_ do

7 Compute activation values $\Lambda_{i(s_{l}^{i},a)t}$ of instances
$((s_{l}^{i},a),x_{i(s_{l}^{i},a)t},T_{i(s_{l}^{i},a)t})$ by (1)

8

9 Compute retrieval probabilities $P_{i(s_{l}^{i},a)t}$ by (2)

10 Compute blended values $V_{(s_{l},a)t}$ corresponding to $(s_{l},a)$ by (3)

11

12 end

13 Choose an action $a_{l}\in\arg\max_{a\in A}V_{(s_{l},a)t}$

14 end

15 Take action $a_{l}$, move to state $s_{l+1}$, observe $s_{l+1}$, and
receive outcome $x_{l+1}$

16 Store $t$ into instance corresponding to selecting $(s_{l},a_{l})$ and
achieving outcome $x_{l+1}$ in $\mathcal{M}$

17 If $delayed$ is true, update outcomes using a credit assignment mechanism

18 $l\leftarrow l+1$ and $t\leftarrow t+1$

19

20 end while

21

22until  _task stopping condition_

Algorithm 1 Pseudo Code of Instance-based Learning process

Concretely, for an agent, an option $k=(s,a)$ is defined by taking action $a$
after observing state $s$. At time $t$, assume that there are $n_{kt}$
different considered instances $(k_{i},x_{ik_{i}t})$ for $i=1,...,n_{kt}$,
associated with $k$. Each instance $i$ in memory has an Activation value,
which represents how readily available that information is in memory and
expressed as follows ANDERSON14 :

$\begin{array}[]{l}\Lambda_{ik_{i}t}=\ln{\left(\sum\limits_{t^{\prime}\in
T_{ik_{i}t}}(t-t^{\prime})^{-d}\right)}+\alpha\sum\limits_{j}Sim_{j}(f^{k}_{j},f^{k_{i}}_{j})+\sigma\ln{\frac{1-\xi_{ik_{i}t}}{\xi_{ik_{i}t}}},\end{array}$
(1)

where $d$, $\alpha$, and $\sigma$ are the decay, mismatch penalty, and noise
parameters, respectively, and $T_{ik_{i}t}\subset\\{0,...,t-1\\}$ is the set
of the previous timestamps in which the instance $i$ was observed, $f_{j}^{k}$
is the $j$-th attribute of the state $s$, and $Sim_{j}$ is a similarity
function associated with the $j$-th attribute. The second term is a partial
matching process reflecting the similarity between the current state $s$ and
the state of the option $k_{i}$. The rightmost term represents a noise for
capturing individual variation in activation, and $\xi_{ik_{i}t}$ is a random
number drawn from a uniform distribution $U(0,1)$ at each timestep and for
each instance and option.

Activation of an instance $i$ is used to determine the probability of
retrieval of an instance from memory. The probability of an instance $i$ is
defined by a soft-max function as follows

$P_{ik_{i}t}=\frac{e^{\Lambda_{ik_{i}t}/\tau}}{\sum_{j=1}^{n_{kt}}e^{\Lambda_{jk_{j}t}/\tau}},$
(2)

where $\tau$ is the Boltzmann constant (i.e., the “temperature”) in the
Boltzmann distribution. For simplicity, $\tau$ is often defined as a function
of the same $\sigma$ used in the activation equation $\tau=\sigma\sqrt{2}$.

The expected utility of option $k$ is calculated based on Blending as
specified in choice tasks LEJARRAGA12 ; GONZALEZ11 :

$V_{kt}=\sum_{i=1}^{n_{kt}}P_{ik_{i}t}x_{ik_{i}t}.$ (3)

The choice rule is to select the option that corresponds to the maximum
blended value. In particular, at the $l$-th step of an episode, the agent
selects the option $(s_{l},a_{l})$ with

$a_{l}=\arg\max_{a\in A}V_{(s_{l},a),t}$ (4)

The flag $delayed$ on line 1 of Algorithm 1 is true when the agent knows the
real outcome after making a sequence of decision without feedback. In such
case, the agent updates outcomes by using one of the credit assignment
mechanisms Nguyen21 . It is worth noting that when the flag $delayed$ is true
depends on a specific task. For instance, $delayed$ can be set to true when
the agent reaches the terminal state, or when the agent receives a positive
reward.

##  3 SpeedyIBL Implementation

From the IBL algorithm 1, we observe that its computational cost revolves
around the computations on lines 1 (Eq. 1), 1 (Eq. 2), 1 (Eq. 3), and the
storage of instances with their associated time stamps on line 1. Clearly,
when the number of states and action variables (dimensions) grow, or the
number of IBL agent objects increases, the execution of steps 1 to 3) in
algorithm 1 will directly increase the execution time. The “speedy” version of
IBL (i.e., SpeedyIBL) is a library focused on dealing with these computations
more efficiently.

SpeedyIBL algorithm is the same as that in Algorithm 1. The innovation is in
the Mathematics. Equations 1, 2 and 3 are replaced with Equations 6, 7 and 8,
respectively (as explained below). Our idea is to take advantage of
vectorization, which typically refers to the process of applying a single
instruction to a set of values (vector) in parallel, instead of executing a
single instruction on a single value at a time. In general, this idea can be
implemented in any programming language. We particularly implemented these in
Python, since that is how PyIBL is implemented MorrisonGonzalez .

Technically, the memory in an IBL model is stored by using a dictionary
$\mathcal{M}$ that, at time $t$, represented as follows:

$\mathcal{M}=\biggl{\\{}k_{i}:\\{x_{ik_{i}t}:T_{ik_{i}t},...\\},...\biggr{\\}},$
(5)

where $(k_{i},x_{ik_{i}t},T_{ik_{i}t})$ is an instance $i$ that corresponds to
selecting option $k_{i}$ and achieving outcome $x_{ik_{i}t}$ with
$T_{ik_{i}t}$ being the set of the previous timestamps in which the instance
$i$ is observed.

To vectorize the codes, we convert $T_{ik_{i}t}$ to a
NumPy111https://numpy.org/doc/stable/ array on which we can use standard
mathematical functions with built-in Numpy functions for fast operations on
entire arrays of data without having to write loops.

After the conversion, we consider $T_{ik_{i}t}$ as a NumPy array. In addition,
since we may use a common similarity function for several attributes, we
assume that $f$ is partitioned into $J$ non-overlapping groups
$f_{[1]},...,f_{[J]}$ with respect to the distinct similarity functions
$Sim_{1},...,Sim_{J}$, i.e., $f_{[j]}$ contains attributes that use the same
similarity function $Sim_{j}$. We denote $S(f^{k},f^{k_{i}})$ the second term
of (1) computed by:

set $S(f^{k},f^{k_{i}})$ = 0

for $j=1$ to $J$ do

$S(f^{k},f^{k_{i}})\ +=\texttt{sum}((Sim_{j}(f_{[j]}^{k},f_{[j]}^{k_{i}}))$

end for

Hence, the activation value (see Equation 1) can be fast and efficiently
computed as follows:

$\Lambda_{ik_{i}t}=\texttt{math.log}(\texttt{sum}(\texttt{pow}(t-T_{ik_{i}t},-d)))+\alpha*S(f^{k},f^{k_{i}})+\sigma*\texttt{math.log}((1-\xi_{ik_{i}t})/\xi_{ik_{i}t}).$
(6)

With the vectorization, the operation such as pow can be performed on multiple
elements of the array at once, rather than looping through and executing them
one at a time. Similarly, the retrieval probability (see Equation 2) is now
computed by:

$P_{kt}:=[P_{1k_{1}t},...,P_{n_{kt}k_{n_{kt}}t}]=v/\texttt{sum}(v),$ (7)

where
$v=\texttt{math.exp}([\Lambda_{1k_{1}t},...,\Lambda_{n_{kt}k_{n_{kt}}t}]/\tau)$.
The blended value (see Equation 3) is now computed by:

$V_{kt}=\texttt{sum}(x_{kt}*P_{kt}),$ (8)

where $x_{kt}:=[x_{1k_{1}t},...,x_{n_{kt}k_{n_{kt}}t}]$ is a NumPy array that
contains all the outcomes associated with the option $k$.

##  4 Experiments: Demonstration of the Curse of Exponential Growth and
SpeedyIBL solution

To demonstrate the efficiency of SpeedyIBL, we evaluate its performance
against a regular implementation of the IBL algorithm (Algorithm 1) in Python
(PyIBL PyIBL ), in six different tasks that were selected to represent
different dimensions of complexity in dynamic decision making tasks
gonzalez2005use . The codes are available at
https://github.com/nhatpd/SpeedyIBL.

###  4.1 General Simulation Methods

The parameter values configured in the IBL models with SpeedyIBL and PyIBL
implementations were identical. In particular, we used the decay $d=0.5$ and
noise $\sigma=0.25$. The default utility values generally set to be higher
than the maximum value obtained in the task, to create exploration as
suggested in LEJARRAGA12  (see the task descriptions below for specific
values), and they were set the same for PyIBL and SpeedyIBL.

For each of the six tasks, we compared the performance of PyIBL and SpeedyIBL
implementations in terms of (i) running time measured in seconds and (ii)
performance. The performance measure is identified within each task.

We conducted 1000 runs of the models and each run performed 100 episodes for
the Binary choice and Insider attack. Given the running time required for
PyIBL, we only ran 100 runs of 100 episodes for the remaining tasks. We note
that an episode of the Binary choice and Insider attack tasks has one step
(trial) while the remaining tasks have $2500$ steps within each episode.

The credit assignment mechanisms in IBL are being studied in NGUYEN20 . In
this paper we used an equal credit assignment mechanism for all tasks. This
mechanism updates the current outcome for all the actions that took place from
the current state to the last state where the agent started or the flag
$delayed$ was true.

###  4.2 Tasks

Table 1 provides an overview of the dimensions of the tasks with respect to
the number of agents, actions, states, partial matching mechanism, feedback
delays, and number of choice options. There are 4 single agent tasks, one task
with two agents, and one task with 3 agents. The tasks have between 2 to 9
potential actions and the number of states and choice options also vary from
just a few to a significant large number. We also include a task to illustrate
the partial matching (similarity) process of equations 1 and 6, and a task
with no feedback delay.

We start with a repeated Binary choice task that has only one state and two
options, followed by an Insider attack two-stage game in which players choose
one of six targets after observing their features to advance. We then scale up
to a larger number of states and actions in significantly more complex tasks.
A Minimap task involving a search and rescue mission and Ms. Pac-man task have
a larger number of the discrete state-action variables. Next, we scale up to
two multi-agent tasks: the Fireman task has two agents and four actions, and a
Cooperative Navigation task in which three agents navigate and cooperate to
accomplish a goal. The number of agents increases the memory computation,
since each of those agents adds their own variables to the joint state-action
space. Importantly, all these demonstrations use the same IBL algorithm 1, and
the implementation of such algorithm with the Speedy equations described in
Section 3. Details for each task follow below. Based on these dimensions of
increasing complexity, we expect that SpeedyIBL’s benefits over PyIBL will be
larger with increasing complexity of the task.

Task | # Agents | # Actions | # States | # Options | Partial | Delayed
---|---|---|---|---|---|---
Matching | Feedback
Binary choice | 1 | 2 | 1 | 2 | No | No
Insider attack game | 1 | 6 | 4 | 24 | Yes | Yes
Minimap | 1 | 4 | $\approx 10^{41}$ | $\approx 4\times 10^{41}$ | No | Yes
Ms.Pac-man | 1 | 9 | $\approx 10^{347}$ | $\approx 9\times 10^{347}$ | No | Yes
Fireman | 2 | 4 | $\approx 10^{15}$ | $\approx 4\times 10^{15}$ | No | Yes
Cooperative navigation | 3 | 4 | $\approx 10^{7}$ | $\approx 4\times 10^{7}$ | No | Yes
Table 1: Task Summary

####  4.2.1 Binary choice

In each trial, the agent is required to choose one of two options: Option A or
Option B. A numerical outcome drawn from a distribution after the selection,
is the immediate feedback of the task. This is a well-studied problem in the
literature of risky choice task Hertwig2004 , where individuals make decisions
under uncertainty. Unknown to the agent is that the options A and B are
assigned to draw the outcome from a predefined distribution. One option is
safe and it yields a fixed medium outcome (i.e., $3$) every time it is chosen.
The other option is risky, and it yields a high outcome ($4$) with some
probability $0.8$, and a low outcome ($0$) with the complementary probability
$0.2$.

An IBL model of this task has been created and reported in various past
studies, including GONZALEZ11 ; LEJARRAGA12 . Here, we conducted the
simulations of 1000 runs of 100 trials. We also run the experiment with 5000
trials to more clearly highlight the difference between PyIBL and SpeedyIBL.
The default utility $x_{0}$ was set to $4.4$. For each option $s$, where $s$
is either A or B, we consider all the generated instances taking the form of
$(s,x)$, where $x$ is an outcome. The performance is determined by the average
proportion of the maximum reward expectation choice (PMax).

Figure 2: Binary choice

####  4.2.2 Insider attack game

The insider attack game is an interactive task designed to study the effect of
signaling algorithms in cyber deception experiments (e.g., Cranford18 ).
Figure 3 illustrates the interface of the task, including a representation of
the agent (insider attacker) and the information of 6 computers. Each of the
six computers is “protected” with some probability (designed by a defense
algorithm). Each computer displays the monitoring probability and potential
outcomes and the information of the signal. When the agent selects one of the
six computers, a signal is presented to the agent (based on the defense
signaling strategy); which informs the agent whether the computer is monitored
or not. The agent then makes a second decision after the signal: whether to
continue or withdraw the attack on the pre-selected computer. If the agent
attacks a computer that is monitored, the player loses points, but if the
computer is not monitored, the agent wins points. The signals are, therefore,
truthful or deceptive. If the agent withdraws the attack, it earns zero
points.

Figure 3: Insider Attack game

In each trial, the agent must decide which of the 6 computers to attack, and
whether to continue or withdraw the attack after receiving a signal. An IBL
model of this task has been created and reported in past studies (e.g.,
cranford2019modeling ; Cranford2021Towards ). We perform the simulations of
1000 runs of 100 episodes. For each option $(s,a)$, where the sate $s$ is the
features of computers including reward, penalty and the probability that the
computers is being monitored (see cranford2019modeling  for more details), and
$a\in\\{1,...,6\\}$ is an index of computers, we consider all the generated
instances taking the form of $(s^{\prime},a,x)$ with $s^{\prime}$ being a
state and $x$ being an outcome. The performance is determined by the average
collected reward.

####  4.2.3 Search and rescue in Minimap

The Minimap task is inspired by a search and rescue scenario, which involves
an agent being placed in a building with multiple rooms and tasked with
rescuing victims Nguyen21b . Victims have been scattered across the building
and their injuries have different degrees of severity with some needing more
urgent care than others. In particular, there are 34 victims grouped into two
categories (24 green victims and 10 yellow victims). There are many obstacles
(walls) placed in the path forcing the agent to look for alternative routes.
The agent’s goal is to rescue as many victims as possible. The task is
simulated as a $93\times 50$ grid of cells which represents one floor of this
building. Each cell is either empty, an obstacle, or a victim. The agent can
choose to move left, right, up, or down, and only move one cell at a time.

Figure 4: Search and rescue map. The empty cells are white and the walls are
black. The yellow and green cells represent the locations of the yellow and
green victims respectively. The cell with the red color represents the start
location of the agent.

The agent receives a reward of 0.75 and 0.25 for rescuing a yellow victim and
a green victim, respectively. Moving into an obstacle or an empty cell is
penalized by 0.05 or 0.01 accordingly. Since the agent might have to make a
sequence of decisions to rescue a victim, we update the previous instances by
a positive outcome that once the agent receives.

An IBL model of this task has been created and reported in past studies
Gulati2021Task . Here we created the SpeedyIBL implementation of this model to
perform the simulation of 100 runs of 100 episodes. An episode terminates when
a $2500$-trial limit is reached or when the agent successfully rescues all the
victims. After each episode, all rescued victims are placed back at the
location where they were rescued from and the agent restarts from the pre-
defined start position.

In this task, a state $s$ is represented by a gray-scale image (array) with
the same map size. We use the following pixel values to represent the entities
in the map: $s[x][y]$ = 240 if the agent locates at the coordinate $(x,y)$,
150 if a yellow victim locates at the coordinate $(x,y)$, 200 if a green
victim locates at the coordinate $(x,y)$, 100 if an obstacle locates at the
coordinate $(x,y)$, and 0 otherwise. For each option $(s,a)$, where $s$ is a
state and $a$ is an action, we consider all the generated instances taking the
form of $(s,a,x)$ with $x$ being an outcome. The default utility was set to
$0.1$. The flag $delayed$ is set to true if the agent rescues a victim,
otherwise false. The performance is determined by the average collected
reward.

####  4.2.4 Ms. Pac-man

The next task considered in the experiment is Ms. Pac-man game, a benchmark
for evaluating agents in machine learning, e.g. Hasselt2016Deep . The agent
maneuvers Pac-Man in a maze while Pac-Man eats the dots (see Fig. 5).

Figure 5: Mis.Pac-man game

In this particular maze, there are 174 dots, each one is worth 10 points. A
level is finished when all dots are eaten. To make things more difficult,
there are also four ghosts in the maze who try to catch Pac-Man, and if they
succeed, Pac-Man loses a life. Initially, she has three lives and gets an
extra life after reaching $10,000$ points. There are four power-up items in
the corners of the maze, called power dots (worth 40 points). After Pac-Man
eats a power dot, the ghosts turn blue for a short period, they slow down and
try to escape from Pac-Man. During this time, Pac-Man is able to eat them,
which is worth 200, 400, 800, and 1600 points, consecutively. The point values
are reset to 200 each time another power dot is eaten, so the agent would want
to eat all four ghosts per power dot. If a ghost is eaten, his remains hurry
back to the center of the maze where the ghost is reborn. At certain
intervals, a fruit appears near the center of the maze and remains there for a
while. Eating this fruit is worth 100 points.

We use the MsPacman-v0 environment developed by Gym
OpenAI222https://gym.openai.com/envs/MsPacman-v0/, where a state is
represented by a color image. Here, we developed an IBL model for this task
and created the SpeedyIBL implementation of this model to perform the
simulation of 100 runs of 100 episodes. An episode terminates when either a
$2500$-step limit is reached or when Pac-man successfully eats all the dots or
loses three lives. Like in the Minimap task, for each option $(s,a)$, where
$s$ is a state and $a$ is an action, we consider all the generated instances
taking the form of $(s,a,x)$ with $x$ being an outcome. The parameter
$delayed$ is set to true if Pac-man receives a positive reward, otherwise it
is set to false. The performance is determined by the average collected
reward.

####  4.2.5 Fireman

The Fireman task replicates the coordination in firefighting service wherein
agents need to pick up matching items for extinguishing fire. This task was
used for examining deep reinforcement learning agents Palmer2019Negative . In
the experiment, the task is simulated in a gridworld of size $11\times 14$, as
illustrated in Fig. 6. Two agents A1 and A2 located within the gridworld are
tasked with locating an equipment pickup area and choosing one of the
firefight items. Afterwards, they need to navigate and find the location of
the fire (F) to extinguish it. The task is fully cooperative as both agents
are required to extinguish one fire. More importantly, the location of the
fire is dynamic in every episode.

Figure 6: Fireman game

The agents receive the collective reward according to the match between their
selected firefighting items, which is determined by the payoff matrix in Table
2. The matrix is derived from a partial stochastic climbing game MatignonLF12
that has a stochastic reward. If they both select the equipment E2, they get
14 points with the probability 0.5, and 0 otherwise. This Fireman task has
both stochastic and dynamic properties.

| Agent 2
---|---
| E1 | E2 | E3
Agent 1 | E1 | 11 | -30 | 0
E2 | -30 | 14/0 | 6
E3 | 0 | 0 | 5
Table 2: Payoff matrix.

Here we developed an IBL model for this task. We created the SpeedyIBL
implementation of this model to perform the simulations of 100 runs of 100
episodes. An episode terminates when a $2500$-trial limit is reached or when
the agents successfully extinguish the fire. After each episode, the fire is
replaced in a random location and the agents restart from the pre-defined
start positions.

Like in the search and rescue Minimap task, a state $s$ of the agent A1 (resp.
A2) is represented by a gray-scale image with the same gridworld size using
the following pixel values to represent the entities in the gridworld:
$s[x][y]$ = 240 (resp. 200) if the agent A1 (resp. A2) locates at the
coordinate $(x,y)$, 55 if the fire locates at the coordinate $(x,y)$, 40 if
equipment E1 locates at the coordinate $(x,y)$, 50 if equipment E2 locates at
the coordinate $(x,y)$, 60 if equipment E3 locates at the coordinate $(x,y)$,
100 if an obstacle locates at the coordinate $(x,y)$, 0 otherwise. Moreover,
we assume that the agents cannot observe the relative positions of the other,
and hence, their states do not include the pixel values of the other agent.
For each option $(s,a)$, where $s$ is a state and $a$ is an action, we
consider all the generated instances taking the form of $(s,a,x)$ with $x$
being an outcome. The flag $delayed$ is set to true if the agents finish the
task, otherwise false. The performance is determined by the average collected
reward.

####  4.2.6 Cooperative Navigation

In this task, three agents (A1, A2 and A3) must cooperate through physical
actions to reach a set of three landmarks (L1, L2 and L3) shown in Fig. 7, see
Lowe2017Multi . The agents can observe the relative positions of other agents
and landmarks, and are collectively rewarded based on the number of the
landmarks that they cover. For instance, if all the agents cover only one
landmark L2, they receive one point. By contrast, if they all can cover the
three landmarks, they get the maximum of three points. Simply put, the agents
want to cover all landmarks, so they need to learn to coordinate the landmark
they must cover.

Figure 7: Cooperative navigation

Here we developed an IBL model for this task. We created the SpeedyIBL
implementation of this model to perform the simulations of 100 runs of 100
episodes. An episode terminates when a $2500$-trial limit is reached or when
each of the agents covers one landmark. After each episode, the fire is
replaced in a random location and the agents restart from the pre-defined
start positions.

In this task, a state $s$ is also represented by a gray-scale image with the
same gridworld size using the following pixel values to represent the entities
in the environment: $s[x][y]$ = 240 if the agent A1 locates at the coordinate
$(x,y)$, 200 if the agent A2 locates at the coordinate $(x,y)$, 150 if the
agent A3 locates at the coordinate $(x,y)$, 40 if the landmark L1 locates at
the coordinate $(x,y)$, 50 if the landmark L2 locates at the coordinate
$(x,y)$, 60 if the landmark L3 locates at the coordinate $(x,y)$, 0 otherwise.
For each option $(s,a)$, where $s$ is a state and $a$ is an action, we
consider all the generated instances taking the form of $(s,a,x)$ with $x$
being an outcome. The flag $delayed$ is set to true if the agents receive a
positive reward, otherwise false. The performance is determined by the average
collective reward.

##  5 Results

In this section, we present the results of the SpeedyIBL and PyIBL models
across all the considered tasks. The comparison is provided in terms of the
average running time and performance.

###  5.1 Average Running time and Performance

Table 3 shows the overall average of computational time and Table 4 the
average performance across the runs and 100 episodes. The Ratio in Table 3
indicates the speed improvement from running the model in SpeedyIBL over
PyIBL.

Task | PyIBL | SpeedyIBL | Ratio
---|---|---|---
Binary choice | 0.0087 | 0.0076 | 1.14
Insider Attack Game | 0.1411 | 0.0652 | 2.2
Minimap | 21951.88 ($\approx$ 365 mins $\approx$ 6 hours) | 78.4 ($\approx$ 1.3 mins) | 279
Ms.Pac-man | 162372.58 ($\approx$ 2706.2 mins $\approx$ 45 hours) | 111.98 ($\approx$ 1.86 mins) | 1450
Fireman | 23 743.36 ($\approx$ 395.72 mins $\approx$ 6.6 hours) | 37.72 ($\approx$ 0.62 mins) | 629
Cooperative Navigation | 9741.37 ($\approx$ 162 mins $\approx$ 2.7 hours) | 2.59 ($\approx$ 0.04 mins) | 3754
Table 3: Average running time in seconds of a run

The ratio of PyIBL running time to SpeedyIBL running time in Table 3 shows
that the benefit of SpeedyIBL over PyIBL increases significantly with the
complexity of the task. In a simple task such as binary choice, SpeedyIBL
performs 1.14 faster than PyIBL. However, the speed-up ratio increases with
the higher dimensional state space tasks; for example, in Minimap SpeedyIBL
was 279 times faster than PyIBL; and in Ms. Pac-man SpeedyIBL was 1450 times
faster than PyIBL.

Furthermore, the multi-agent tasks exhibit the largest ratio benefit of
SpeedyIBL over PyIBL. For example, in the Cooperative Navigation task, PyIBL
took about 2.7 hours to finish a run, but SpeedyIBL only takes 2.59 seconds to
accomplish a run.

In all tasks, we observe that the computational time of SpeedyIBL is
significantly shorter than running the same task in PyIBL; we also observe
that there is no significant difference in the performance of SpeedyIBL and
PyIBL ($p>0.05)$. These results suggest that SpeedyIBL is able to greatly
reduce the execution time of an IBL model without compromising its
performance.

Task | Metric | PyIBL | SpeedyIBL |  $t$-test
---|---|---|---|---
Binary choice | PMax | 0.8333 | 0.8275 | $t=-0.83,p=0.4>0.05$
Insider Attack Game | Average Reward | 1.3828 | 1.3751 | $t=-0.38,p=0.69>0.05$
Minimap | Average Reward | 4.1021 | 4.2641 | $t=0.87,p=0.38>0.05$
Ms.Pac-man | Average Reward | 228.357 | 228.464 | $t=0.72,p=0.47>0.05$
Fireman | Average Reward | 4.7825 | 4.9456 | $t=1.07,p=0.28>0.05$
Cooperative Navigation | Average Reward | 2.7049 | 2.7261 | $t=0.69,p=0.48>0.05$
Table 4: Average performance of a run

###  5.2 Learning curves

Figure 8 shows the comparison of average running time (middle column) and
average performance (right column) between PyIBL (Blue) and SpeedyIBL (Green)
across episodes for all the six tasks.

(a) Binary Choice

(b) Insider Attack

(c) Minimap

(d) Ms.Pac-man

(e) Fireman

(f) Cooperative Navigation

Figure 8: The comparison between SpeedyIBL (Green line) and PyIBL (Blue line)
over time in the considered tasks.

In the Binary choice task, it is observed that there is a small difference in
the execution time before 100 episodes; where SpeedyIBL performs slightly
faster than PyIBL. To illustrate how the benefit of SpeedyIBL over PyIBL
implementation increases significantly as the number of episodes increase, we
ran these models over 5000 episodes. Figure 9 illustrates the curse of
exponential growth very clearly, where PyIBL exponentially increases the
execution time with more episodes. The benefit of SpeedyIBL over PyIBL
implementation is clear with increased episodes. The PMax of SpeedyIBL and
PyIBL overlap, suggesting the same performance.

Figure 9: The comparison between SpeedyIBL and PyIBL in 5000 playing episodes
of binary choice task.

In the Insider Attack game as shown Figure 8(b), the relation between
SpeedyIBL and PyIBL in terms of computational time shows again, an increased
benefit with increased number of episodes. We see that their running time is
indistinguishable initially, but then the difference becomes distinct in the
last 60 episodes. Regarding the performance (i.e., average reward), again,
their performance over time is nearly identical. Learning in this task was
more difficult, given the design of this task, and we do not observe a clear
upward trend in the learning curve due to the presence of stochastic elements
in the task.

In all the rest of the tasks, the Minimap, Mis.Pac-man, Fireman, and
Cooperative Navigation, given the multi-dimensionality of these tasks
representations and the number of agents involved in Fireman, and Cooperative
Navigation tasks, the curse of exponential growth is observed from early on,
as shown in Figure 8(c). The processing time of PyIBL grows nearly
exponentially over time in all cases. The curve of SpeedyIBL also increases,
but it appears to be constant in relation to the exponential growth of PyIBL
given the significant difference between the two, when plotted in the same
scale.

The performance over time is again indistinguishable between PyIBL and
SpeedyIBL. Depending on the task, the dynamics, and strochastic elements of
the task, the models’ learning curves appear to fluctuate over time (e.g.
Mis.Pac-man), but when the scenarios are consistent over time, the models show
similar learning curves for both, PyIBL and SpeedyIBL.

##  6 Discussion and Conclusions

The curse of exponential growth is an important computational problem that
emerges in many modeling approaches involving tabular and loop computations:
as more observations accumulate and the dimensions of a task and the number of
agents modeled in a task increase, the execution time of such a model will
also increase. Models slow down with the increased number of computations that
need to be done in a model.

In this paper, we demonstrate the curse of exponential growth problem and
propose a solution to that problem. We demonstrate the problem and solutions
within cognitive models, in particular Instance-Based Learning models
GONZALEZ03 . We chose IBL models because it is possible to demonstrate how
models constructed in agreement with the same theory can demonstrate different
behaviors according to the complexity, number of agents, and hyper-
dimensionality of the decision tasks.

We propose a a new implementation for IBL models in SpeedyIBL, a Python
library that allows to create multiple IBL agents with fast processing and
response time without compromising the performance. SpeedyIBL relies on the
same IBL algorithm GONZALEZ03  but innovates the PyIBL implementation of this
algorithm PyIBL  with the mathematics of vectorization and parallel
computation larsen2000exploiting . The underlying idea of the SpeedyIBL
implementation is to speed up the performance by using a data structure to
store memory more efficiently and by leveraging vectorization in computation.

We have demonstrated the robustness of SpeedyIBL by comparing it with PyIBL, a
widely used Python implementation of IBLT, on a wide range of tasks that vary
in their increased complexity. We demonstrate how SpeedyIBL model
implementation, based on the same theory can be exponentially beneficial
compared to the traditional PyIBL implementation. We demonstrate tasks that
range from a single-agent, single-state, to single-agent multi-state, and to
multi-agent multi-state settings. The results show that SpeedyIBL is able to
perform significantly faster than PyIBL while keeping the performance as good
as PyIBL. Moreover, the difference in the running time of the SpeedyIBL and
PyIBL becomes large, especially in multi-agent domains and high-dimensional
state spaces.

With the fast processing time, SpeedyIBL can not only be used in simulation
experiments, but also can be integrated into a browser-based application in
which IBL agents can interact with human subjects. Given that research on
human–machine behavioral has attracted much attention lately, we are convinced
that the implementation of SpeedyIBL will bring real benefits to researchers
in the area.

###### Acknowledgements.

This research was partly sponsored by the Defense Advanced Research Projects
Agency and was accomplished under Grant Number W911NF-20-1-0006 and by AFRL
Award FA8650-20-F-6212 subaward number 1990692 to Cleotilde Gonzalez.

## References

  * (1) Aggarwal, P., Thakoor, O., Mate, A., Tambe, M., Cranford, E.A., Lebiere, C., Gonzalez, C.: An exploratory study of a masking strategy of cyberdeception using cybervan.  In: Proceedings of the Human Factors and Ergonomics Society Annual Meeting, vol. 64, pp. 446–450. SAGE Publications Sage CA: Los Angeles, CA (2020)
  * (2) Anderson, J.R., Lebiere, C.J.: The atomic components of thought.  Psychology Press (2014)
  * (3) Bellman, R.: Dynamic programming, princeton univ.  Press Princeton, New Jersey (1957)
  * (4) Cranford, E.A., Gonzalez, C., Aggarwal, P., Cooney, S., Tambe, M., Lebiere, C.: Toward personalized deceptive signaling for cyber defense using cognitive models.  Topics in Cognitive Science 12(3), 992–1011 (2020)
  * (5) Cranford, E.A., Gonzalez, C., Aggarwal, P., Tambe, M., Cooney, S., Lebiere, C.: Towards a cognitive theory of cyber deception.  Cognitive Science 45(7) (2021)
  * (6) Cranford, E.A., Lebiere, C., Gonzalez, C., Cooney, S., Vayanos, P., Tambe, M.: Learning about cyber deception through simulations: Predictions of human decision making with deceptive signals in stackelberg security games.  In: C. Kalish, M.A. Rau, X.J. Zhu, T.T. Rogers (eds.) Proceedings of the 40th Annual Meeting of the Cognitive Science Society, CogSci 2018, Madison, WI, USA, July 25-28, 2018 (2018)
  * (7) Cranford, E.A., Lebiere, C., Rajivan, P., Aggarwal, P., Gonzalez, C.: Modeling cognitive dynamics in (end)-user response to phishing emails.  Proceedings of the 17th ICCM (2019)
  * (8) Erev, I., Ert, E., Plonsky, O., Cohen, D., Cohen, O.: From anomalies to forecasts: Toward a descriptive model of decisions under risk, under ambiguity, and from experience.  Psychological review 124(4), 369 (2017)
  * (9) Erev, I., Ert, E., Roth, A.E., Haruvy, E., Herzog, S.M., Hau, R., Hertwig, R., Stewart, T., West, R., Lebiere, C.: A choice prediction competition: Choices from experience and from description.  Journal of Behavioral Decision Making 23(1), 15–47 (2010)
  * (10) Gonzalez, C.: Decision-making: a cognitive science perspective.  The Oxford handbook of cognitive science 1, 1–27 (2017)
  * (11) Gonzalez, C., Ben-Asher, N., Martin, J.M., Dutt, V.: A cognitive model of dynamic cooperation with varied interdependency information.  Cognitive science 39(3), 457–495 (2015)
  * (12) Gonzalez, C., Dutt, V.: Instance-based learning: Integrating decisions from experience in sampling and repeated choice paradigms.  Psychological Review 118(4), 523–51 (2011)
  * (13) Gonzalez, C., Fakhari, P., Busemeyer, J.: Dynamic decision making: Learning processes and new research directions.  Human factors 59(5), 713–721 (2017)
  * (14) Gonzalez, C., Lerch, J.F., Lebiere, C.: Instance-based learning in dynamic decision making.  Cognitive Science 27(4), 591–635 (2003)
  * (15) Gonzalez, C., Vanyukov, P., Martin, M.K.: The use of microworlds to study dynamic decision making.  Computers in human behavior 21(2), 273–286 (2005)
  * (16) Gulati, A., Nguyen, T.N., Gonzalez, C.: Task complexity and performance in individuals and groups without communication.  In: AAAI Fall Symposium on Theory of Mind for Teams (2021)
  * (17) Hasselt, H.v., Guez, A., Silver, D.: Deep reinforcement learning with double q-learning.  In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI’16, p. 2094–2100. AAAI Press (2016)
  * (18) Hertwig, R.: Decisions from experience.  The Wiley Blackwell handbook of judgment and decision making 1, 240–267 (2015)
  * (19) Hertwig, R., Barron, G., Weber, E.U., Erev, I.: Decisions from experience and the effect of rare events in risky choice.  Psychological Science 15(8), 534–539 (2004)
  * (20) Kahneman, D., Tversky, A.: The dynamics of cognition: An act-r model of cognitive arithmetic.  Kognitionswissenschaft 8, 5–19 (1979)
  * (21) Kahneman, D., Tversky, A.: Prospect theory: An analysis of decision under risk.  Econometrica 47(2), 363–391 (1979)
  * (22) Kuo, F.Y., Sloan, I.H.: Lifting the curse of dimensionality.  Notices of the AMS 52(11), 1320–1328 (2005)
  * (23) Larsen, S., Amarasinghe, S.: Exploiting superword level parallelism with multimedia instruction sets.  ACM SIGPLAN Notices 35(5), 145–156 (2000)
  * (24) Lejarraga, T., Dutt, V., Gonzalez, C.: Instance-based learning: A general model of repeated binary choice.  Journal of Behavioral Decision Making 25(2), 143–153 (2012)
  * (25) Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, P., Mordatch, I.: Multi-agent actor-critic for mixed cooperative-competitive environments.  In: Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, p. 6382–6393. Curran Associates Inc., Red Hook, NY, USA (2017)
  * (26) Matignon, L., Laurent, G.J., Fort-Piat, N.L.: Independent reinforcement learners in cooperative markov games: a survey regarding coordination problems.  Knowl. Eng. Rev. 27(1), 1–31 (2012).  DOI 10.1017/S0269888912000057.  URL https://doi.org/10.1017/S0269888912000057
  * (27) Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., Riedmiller, M.: Playing atari with deep reinforcement learning.  arXiv preprint arXiv:1312.5602 (2013)
  * (28) Morgenstern, O., Von Neumann, J.: Theory of games and economic behavior.  Princeton university press (1953)
  * (29) Morrison, D., Gonzalez, C.: Pyibl: A python implementation of iblt.  https://www.cmu.edu/dietrich/sds/ddmlab/downloads.html.  Accessed: 2021-09-27
  * (30) Morrison, D., Gonzalez, C.: Pyibl python implementation of ibl.  URL http://pyibl.ddmlab.com/.  Version 4.1
  * (31) Nguyen, T.N., Gonzalez, C.: Cognitive machine theory of mind.  In: Proceedings of CogSci (2020)
  * (32) Nguyen, T.N., Gonzalez, C.: Effects of decision complexity in goal-seeking gridworlds: A comparison of instance-based learning and reinforcement learning agents.  In: Proceedings of the 18th intl. conf. on cognitive modelling (2020)
  * (33) Nguyen, T.N., Gonzalez, C.: Minimap: A dynamic decision making interactive tool for search and rescue missions.  Tech. rep., Carnegie Mellon University (2021)
  * (34) Nguyen, T.N., Gonzalez, C.: Theory of mind from observation in cognitive models and humans.  Topics in Cognitive Science (2021).  DOI https://doi.org/10.1111/tops.12553.  URL https://onlinelibrary.wiley.com/doi/abs/10.1111/tops.12553
  * (35) Nguyen, T.N., McDonald, C., Gonzalez, C.: Credit assignment: Challenges and opportunities in developing human-like ai agents.  Tech. rep., Carnegie Mellon University (2021)
  * (36) Palmer, G., Savani, R., Tuyls, K.: Negative update intervals in deep multi-agent reinforcement learning.  In: E. Elkind, M. Veloso, N. Agmon, M.E. Taylor (eds.) Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’19, Montreal, QC, Canada, May 13-17, 2019, pp. 43–51. International Foundation for Autonomous Agents and Multiagent Systems (2019)
  * (37) Savage, L.J.: The foundations of statistics.  Naval Research Logistics Quarterly (1954)
  * (38) Silver, D., Huang, A., Maddison, C.J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al.: Mastering the game of go with deep neural networks and tree search.  nature 529(7587), 484–489 (2016)
  * (39) Skinner, B.F.: Contingencies of reinforcement: A theoretical analysis, vol. 3.  BF Skinner Foundation (2014)
  * (40) Sutton, R.I., Staw, B.M.: What theory is not.  Administrative science quarterly pp. 371–384 (1995)
  * (41) Sutton, R.S., Barto, A.G.: Reinforcement learning: An introduction.  MIT press (2018)
  * (42) Tversky, A., Kahneman, D.: Advances in prospect theory: Cumulative representation of uncertainty.  Journal of Risk and uncertainty 5(4), 297–323 (1992)
  * (43) Vinyals, O., Babuschkin, I., Chung, J., Mathieu, M., Jaderberg, M., Czarnecki, W.M., Dudzik, A., Huang, A., Georgiev, P., Powell, R., et al.: Alphastar: Mastering the real-time strategy game starcraft ii.  DeepMind blog 2 (2019)
  * (44) Wong, A., Bäck, T., Kononova, A.V., Plaat, A.: Multiagent deep reinforcement learning: Challenges and directions towards human-like approaches.  arXiv preprint arXiv:2106.15691 (2021)