\section{Introduction}\label{sec1}\setcounter{equation}{0}

In the present paper we continue the line of research in \cite{Ki06} and \cite{Ki07} approximating
game options whose stocks evolutions are described by multidimensional diffusion processes. This is
done constructing first strong approximations of the diffusion by a sequence of discrete time processes
estimating $L^2$ errors of these approximations. These processes are discrete time processes obtained
recursively for $n=0,1,...,N-1$ by
\[
X_N((n+1)/N)=X_N(n/N)+N^{-1/2}{\sigma}(X_N(n/N))\xi(n+1)+N^{-1}b(X_N(n/N)),
\]
where $X_N(0)=x_0$, ${\sigma}$ and $b$ is a matrix and a vector functions, respectively and
$\xi(n),\, n\geq 1$ is a sequence of i.i.d. random vectors with $E\xi(1)=0$. The strong approximation
method enables us to redefine both the sequence $\xi(n),\, n\geq 1$ and the limiting diffusion
$d\Xi(t)={\sigma}(\Xi(t))dW(t)+b(\Xi(t))dt$ preserving their distributions on a same sufficiently rich
probability space so that the $L^2$-distance between them have the order $N^{-{\delta}}$ for some ${\delta}>0$.
In the second step we compare fair prices of options with payoffs
based on these discrete approximations with the fair price of the option with the diffusion asset
evolution. This is not straightforward since this prices are given by values of the corresponding
Dynkin games which depend on sets of stopping times involved and the latter are different for the
approximations and for the limiting diffusion.
The payoffs of the above game options are supposed
to be path dependent, and so free boundary partial differential equations methods cannot help here and
discrete time approximations is the only possible approach in this situation to fair prace computations
taking into account that in the discrete time case we can employ the dynamical programming (backward
recursion) algorithm.

The setup of this paper is the special case of a more general discrete time setup in our recent paper
\cite{Ki20+} but the latter paper provides a detailed proof mostly in the continuous time averaging setup while here we deal with the more specific discrete time setup which can be described in the more
transparent way. The motivation both for \cite{Ki20+} and for the present paper comes, in particular,
from the series of papers \cite{Kha}, \cite{Bor}, \cite{BF} and \cite{CE} on the weak diffusion limit
in averaging and from the series of papers \cite{BP}, \cite{KP}, \cite{MP1} and \cite{DP}  on strong approximations (see \cite{Ki20+} for more detailes). The former papers yielded only weak convergence
 results while the latter dealt only with approximations of the Brownian motion. We observe that in
 the one dimensional case it is still possible to use an extended version of the Skorokhod embedding
 into martingales which also yields error estimates for approximations (see \cite{BDG}).
 Approximation similar to ours appeared previously in \cite{He} but only the weak convergence to a
 diffusion was established there which, in principle, could not provide any error estimates. The reader
 may compare our approach with the well known Euler--Maruyama approximation of solutions of stochastic
 differential equations (see, for instance, \cite{Mao}) where $\xi(n)$'s are increments of the Brownian
 motion. In our setup $\xi(n)$'s are quite general and, in particular, we can take i.i.d. random vectors
 taking on only few values which can be useful in applications since they are easier to simulate and compute
 than Gaussian random vectors.

 \section{Preliminaries and main results}\label{sec2}\setcounter{equation}{0}

We start with a complete probability space $({\Omega},\,{\mathcal F},\, P)$, a sequence of independent identically
distributed (i.i.d.) random vectors $\xi(n),\, n\geq 1$ and a diffusion process $\Xi$ solving the
stochastic differential equation
\begin{equation}\label{2.1}
d\Xi(t)={\sigma}(\Xi(t))dW(t)+b(\Xi(t))dt
\end{equation}
where $W$ is the $d$-dimensional continuous Brownian motion while ${\sigma}$ and $b$ are bounded
Lipschitz continuous
$d\times d$ matrix and $d$-dimensional vector functions, respectively. Namely, we assume that for
some constant $L\geq 1$ and all $x,y\in{\mathbb R}^d$,
\begin{equation}\label{2.2}
|{\sigma}(x)|\leq L,\, |b(x)|\leq L,\, |{\sigma}(x)-{\sigma}(y)|\leq L|x-y|,\, |b(x)-b(y)|\leq L|x-y|
\end{equation}
where $|\cdot |$ denotes the Euclidean norm of a vector or of a matrix. We assume also that
\begin{equation}\label{2.3}
E\xi(1)=0,\,E(\xi_i(1)\xi_j(1))={\delta}_{ij}\,\,\mbox{and}\,\, |\xi(1)|\leq L\,\,\mbox{almost surely
 (a.s.)}
 \end{equation}
 where $\xi(n)=(\xi_1(n),...,\xi_d(n))$ and ${\delta}_{ij}$ is the Kronecker delta. Next, we consider
 the sequence of discrete time processes $X_N,\, N\geq 1$ on ${\mathbb R}^d$ defined recursively for
  $n=0,1,...,N-1$ by
 \begin{equation}\label{2.4}
X_N((n+1)/N)=X_N(n/N)+N^{-1/2}{\sigma}(X_N(n/N))\xi(n+1)+N^{-1}b(X_N(n/N))
\end{equation}
where $X_N(0)=\Xi(0)=x_0$ is fixed. We extend $X_N$ to the continuous time setting
\begin{equation}\label{2.5}
X_N(t)=X_N(n/N)\quad\mbox{if}\quad n/N\leq t<(n+1)/N
\end{equation}
and without loss of generality we will assume that all our processes evolve on the time interval
$[0,1]$ so that $n$ runs in (\ref{2.5}) from 0 to $N$. The following result will be proved in
Sections \ref{sec3} and \ref{sec4}.

\begin{theorem}\label{thm2.1} Suppose that the conditions  (\ref{2.2}) and
(\ref{2.3}) hold true and that the probability space $({\Omega},\,{\mathcal F},\, P)$ is rich enough so that
there exist a sequence of i.i.d. uniformly distributed random variables defined on it. Then for
each integer $N\geq N_0=((10^8d)^{24d}+1)^4$ there exists a $d$-dimensional Brownian motion
$W=W_N$ such that the strong
solution $\Xi=\Xi_N$ of the stochastic differential equation (\ref{2.1}) with such $W$ and the
initial condition $X_N(0)=\Xi(0)=x_0$ satisfies
\begin{equation}\label{2.6}
E\sup_{0\leq t\leq 1}|X_N(t)-\Xi(t)|^{2}\leq C_0[N^{\frac 14}]^{-\frac 1{50d}}
\end{equation}
where $C_0=C_3e^{C_4}+2L^2(L^2+1)+40L^2$ with $C_3$ and $C_4$ defined at the end of Section \ref{sec4}.   In particular, the Prokhorov distance between the path distributions of $X_N$ and of $\Xi$ is
bounded by $C^{1/3}_0[N^{\frac 14}]^{-\frac 1{150d}}$.
\end{theorem}
We observe that though we may have to redefine the Brownian motion $W$ for each $N$ separately the path
distribution of the diffusion $\Xi$ remains the same since it is continuous and the coefficients of the
 stochastic differential equation (\ref{2.1}) do not change, and so we have all the time the same
 Kolmogorov equation and the same martingale problem (see \cite{SV}). Clearly, the estimate (\ref{2.6})
 is meaningful only for large $N$ and we provide it for all $N\geq N_0$ though, of course, an explicit
 estimate in (\ref{2.6}) can be obtained also when $1\leq N\leq N_0$ taking into account that then
 $|X_N(t)|\leq L(\sqrt {N_0}L+1)$ and $E\sup_{0\leq t\leq 1}|\Xi(t)|^{2}\leq 5L^2$. Theorem \ref{thm2.1}
 can also be derived under some moment boundedness conditions rather than the uniform bounds in (\ref{2.2})
 which are assumed to reduce technicalities in our exposition. Observe also that if we
 consider time dependent coefficients ${\sigma}(t,x)$ and $b(t,x)$ Lipschitz continuous in both variables and
 take ${\sigma}(n/N,X_N(n/N))$ and $b(n/N,X_N(n/N))$ in (\ref{2.4}) in place of ${\sigma}(X_N(n/N))$ and $b(X_N(n/N))$,
 then we will obtain $X_N(t)$ which approximates a time inhomogeneous diffusion with coefficients ${\sigma}(t,x)$
 and $b(t,x)$ having essentially the same error estimates as in (\ref{2.6}).

  Next, we will describe an application of our results to computations of values of Dynkin's optimal
   stopping games and fair prices of game options with the payoff function having the form
  \begin{equation}\label{2.7}
  R^\Xi(s,t)=G_s(\Xi){\mathbb I}_{s<t}+F_t(\Xi){\mathbb I}_{t\leq s}
  \end{equation}
  where $\Xi$ is a diffusion solving the stochastic differential equation (\ref{2.1}). Here, $G_t\geq
  F_t$ and both are functionals on paths for the time interval $[0,t]$ satisfying
  certain regularity conditions specified below. Thus, if the first player stops at the time $s$ and
  the second one at the time $t$ then the former pays to the latter the amount $R^\Xi(s,t)$. The game
  runs until the termination time 1 when the game stops automatically, if it was not stopped
  before, and then the first player pays to the second one the amount $G_1(\Xi)=F_1(\Xi)$. Clearly,
  the first player tries to minimize the payment while the second one tries to maximize it. Under the
  conditions below this game has the value (see, for instance, Section 6.2.2 in \cite{Ki20}),
  \begin{equation}\label{2.8}
  V^{\Xi}=\inf_{{\sigma}\in{\mathcal T}_{01}^\Xi}\sup_{\tau\in{\mathcal T}_{01}^{\Xi}}ER^{\Xi}({\sigma},\tau)
  \end{equation}
  where ${\mathcal T}^\Xi_{01}$ is the set of all stopping times $0\leq\tau\leq 1$  with respect to the
  filtration ${\mathcal F}_t^\Xi,\, t\geq 0$ generated by the diffusion $\Xi$ or, which is the same, generated
  by the Brownian motion $W$.

  When we are talking about asset prices then usually
  it is assumed that they are nonnegative, and so a diffusion with bounded coefficients maybe not a
  good model for a description of evolution of these prices. It maybe more appropriate to assume that
  the asset prices evolve according to the vector process described by exponents $(\exp(\Xi^{(i)}(t)),
  \, i=1,...,d)$ where $\Xi^{(1)},...,\Xi^{(d)}$ are components of the vector $\Xi$. Nevertheless, it will
  be more convenient for us to speak about the diffusion $\Xi$ itself and to impose conditions on the
  payoff functionals $F$ and $G$ such that exponential functionals will be allowed which will amount to
  the same effect as exponents describing the evolution of asset prices. Another important point that
  the fair price of a game option equals the value of the corresponding Dynkin optimal stopping game
  considered with respect to the equivalent martingale measure, i.e. with respect to the probability for which the assets evolution is described by a martingale (see \cite{Ki20}) provided that the
   interest rate is supposed to be zero. When the asset prices are given by the above exponential
   formula the probability $P$ itself will be a martingale measure provided $b_i(x)=
   -\frac 12\sum_{j=1}^d{\sigma}^2_{ij}(x)$, $i=1,...,d$ for each $x\in{\mathbb R}^d$. Otherwise, we have to
   perform all estimates with respect to a martingale measure $Q$ and, in particular, $\xi(1),\xi(2),...$ in (\ref{2.4}) should be an i.i.d. sequence satisfying (\ref{2.3}) with respect
   to the probability $Q$. According to the Girsanov theorem (see, for instance, Section 7.4.3
   in \cite{Ki20}),
   \[
   \frac {dQ}{dP}={\Lambda}\,\,\mbox{where}\,\,{\Lambda}=\exp(-\int_0^1\langle\zeta(s),dW(s)\rangle-\frac 12
   \int_0^1|\zeta(s)|^2ds)
   \]
   where $\langle\cdot,\cdot\rangle$ is the inner product and the vector process $\zeta(s)$ satisfies
   \[
   {\sigma}(\Xi(s))\zeta(s)=b(\Xi(s))+\frac 12\eta(\Xi(s))\,\,\mbox{and}\,\,\eta=(\eta_1,...,\eta_d),\,
   \eta_i(x)=\sum_{i=1}^d{\sigma}^2_{ij}(x).
   \]
   Since our estimates do not depend explicitly on the probability measure once the setup above is
   preserved and since there is no one preferable stock evolution model here, we will not discuss this
   point further, and so, strictly speaking, we will deal with the approximation of the Dynkin game value $V^{\Xi}$ and not of the fair price of the corresponding game option, i.e. we will make estimates with respect to the probability $P$ and not with respect to an equivalent martingale measure which depends on a choice of the stock evolution model.

    We assume that $F_t$ and $G_t,\, t\in[0,1]$ are continuous functionals on the space $M_d[0,t]$ of
  bounded Borel measurable maps from $[0,t]$ to ${\mathbb R}^d$  considered with the uniform metric
   $d_{0t}({\upsilon},\tilde{\upsilon})=\sup_{0\leq s\leq t}|{\upsilon}_s-\tilde{\upsilon}_s|$ and there exists a constant $K>0$
   such that
    \begin{eqnarray}\label{2.9}
  & |F_t({\upsilon})-F_t(\tilde{\upsilon})|+|G_t({\upsilon})-G_t(\tilde{\upsilon})|\\
  &\leq K(d_{0t}({\upsilon},\tilde{\upsilon})+{\mathbb I}_{\sup_{0\leq
    u\leq t}|{\upsilon}_u-\tilde{\upsilon}_s|>1})\exp(K\sup_{0\leq u\leq t}(|{\upsilon}_u|+|\tilde{\upsilon}_u|))\nonumber
   \end{eqnarray}
   and
   \begin{equation}\label{2.10}
   |F_t({\upsilon})-F_s({\upsilon})|+|G_t({\upsilon})-G_s({\upsilon})|\leq K(|t-s|+\sup_{u\in[s,t]}|{\upsilon}_u-{\upsilon}_s|)\exp(K\sup_{0\leq
    u\leq t}|{\upsilon}_u|).
   \end{equation}

 Next, we will consider Dynkin's games with payoffs based on the process $X_N$,
  \begin{equation}\label{2.11}
  R_N(s,t)=G_s(X_N){\mathbb I}_{s<t}+F_t(X_N){\mathbb I}_{t\leq s}.
  \end{equation}
 Denote by ${\mathcal F}^\xi_{mn},\, m\leq n$ the ${\sigma}$-algebra generated by $\xi(m),...,\xi(n)$ and let
 ${\mathcal T}^\xi_{mn}$ be the set of all stopping times with respect to the filtration ${\mathcal F}^\xi_{0k},\,
  k\geq 0$ taking on values
 $m,m+1,...,n$. We allow also any stopping time to take on the value $\infty$, i.e. we allow players
 not to stop the game at all, but anyway the game is stopped automatically at the termination time 1
  and then the first player pays to the second one the amount $G_1(X_N)=F_1(X_N)$.
 Now the game value of the Dynkin game in this setup is given by
 \begin{equation}\label{2.12}
 V_N=\inf_{\zeta\in{\mathcal T}^\xi_{0N}}\sup_{\eta\in{\mathcal T}^\xi_{0N}}ER_N(\zeta/N,\,\eta/N).
 \end{equation}

 \begin{theorem}\label{thm2.2} Suppose that the conditions (\ref{2.9}) and (\ref{2.10}) as well as
  the conditions of Theorem \ref{thm2.1} hold true. Then for each ${\delta}>0$ there exists $C_{\delta}>0$
   such that for any integer $N\geq N_0$,
 \begin{equation}\label{2.13}
 |V^\Xi-V_N|\leq C_{\delta}[N^{\frac 14}]^{{\delta}-\frac 1{100d}}
 \end{equation}
 where $C_{\delta}$ does not depend on $N$ and for each ${\delta}$ it can be estimated explicitly from
 the proof in Section \ref{sec5}.
 \end{theorem}

 Since we use in Theorem \ref{thm2.2} a specific construction of the diffusion $\Xi$ from Theorem
 \ref{thm2.1} it is important to note that the game value $V^\Xi$ depends only on the path distribution
 of $\Xi$, i.e. only on the diffusion coefficients ${\sigma}$ and $b$, and not on a choice of the Brownian
 motion in the stochastic differential equation (\ref{2.1}) (see \cite{Dol}).
 We observe also that the main advantage in computation $V_N$ in comparison to $V^\Xi$ is the
 possibility to use the dynamical programming (backward recursion) algorithm. Namely, set
 $V_{NN}=F_{1}(X_N)$ and recursively for $n=N-1,...,1,0$,
 \begin{equation}\label{2.14}
 V_{Nn}=\min\big(G_{n/N}(X_N),\,\max(F_{n/N}(X_N),\, E(V_{N,n+1}|{\mathcal F}^\xi_{0,n}))\big).
 \end{equation}
 Then $V_{N0}=V_N$ (see, for instance, Section 6.2.2 in \cite{Ki20}). Of course, the computation of conditional expectations above becomes complicated if the ${\sigma}$-algebras ${\mathcal F}^\xi_{0n}$ are big
 but if we choose independent random vectors $\xi(n)$ in (\ref{2.4}) taking on only few values then these
  ${\sigma}$-algebras contain not so many sets and the conditional expectations can be computed easily.
  Observe also that in the particular case when the diffusion $\Xi$ is just a multidimensional Brownian
   motion, a result similar to Theorem \ref{thm2.2} was obtained in \cite{Ki07} where it was
   sufficient to consider the standard normalized sums of random vectors $\xi(n)$ rather than the
   more subtle case of difference equations (\ref{2.4}).

   \section{Auxiliary estimates }\label{sec3}\setcounter{equation}{0}
Set $n_k=k[N^{\frac 14}],\, k=0,1,...,k_N$ where $k_N=[N/[N^{\frac 14}]]$ where $[\cdot]$ denotes
the integral part. Define
\begin{eqnarray}\label{3.1}
&\hat X_N(t)=x_0+N^{-1/2}\sum_{0\leq k\leq k_N(t)}\big({\sigma}(X_N(\frac {n_k}N))\sum_{n_k<l\leq
n_{k+1}\wedge[Nt]}\xi(l)\\
&+N^{-1/2}b(X_N(\frac {n_k}N))(n_{k+1}\wedge [Nt]-n_k)\big)\nonumber
\end{eqnarray}
where $k_N(t)=\max\{ k:\, n_k\leq Nt\}$.

\begin{lemma}\label{lem3.1} For any $N\geq 1$,
\begin{equation}\label{3.2}
E\sup_{0\leq t\leq 1}|X_N(t)-\hat X_N(t)|^2\leq 136L^8N^{-1/2}.
\end{equation}
\end{lemma}
\begin{proof}
First, we write
\begin{equation}\label{3.3}
|X_N(t)-\hat X_N(t)|^2\leq 2|M(t)|^2+2|J(t)|^2
\end{equation}
where
\[
M(t)=N^{-1/2}\sum_{0\leq k\leq k_N(t)}\sum_{n_k<l\leq
n_{k+1}\wedge[Nt]}\big({\sigma}(X_N(\frac {l}N))-{\sigma}(X_N(\frac {n_k}N))\big)\xi(l+1)
\]
and
\[
J(t)=N^{-1}\sum_{0\leq k\leq k_N(t)}\sum_{n_k<l\leq
n_{k+1}\wedge[Nt]}(b(X_N(\frac {l}N))-b(X_N(\frac {n_k}N))).
\]

Recall that if $h=h(x,y)$ is a bounded Borel function, ${\mathcal G}\subset{\mathcal F}$ is a ${\sigma}$-algebra and
$Y,Z$ are random variables such that $Y$ is ${\mathcal G}$-measurable and $Z$ is independent of ${\mathcal G}$, then
$E(h(Y,Z)|{\mathcal G})=g(Y)$ where $g(x)=Eh(x,Z)$. It follows from here and from (\ref{2.3}) that $M(t),\,
0\leq t\leq 1$ is a martingale. Hence, by (\ref{2.3}) and the Doob martingale inequality (see,
for instance, Section 6.1.2 in \cite{Ki20}),
\begin{eqnarray}\label{3.4}
&E\sup_{0\leq t\leq 1}|M(t)|^2\leq 4E|M(1)|^2\\
&=4N^{-1}\sum_{0\leq k\leq k_N(t)}\sum_{n_k<l\leq n_{k+1}\wedge[Nt]}E|\big({\sigma}(X_N(\frac {l}N))-{\sigma}(X_N(\frac {n_k}N))\big)\xi(l+1)|^2.\nonumber
\end{eqnarray}
By (\ref{2.2})--(\ref{2.4}) for $n_k<l\leq n_{k+1}$,
\begin{eqnarray}\label{3.5}
&E|\big({\sigma}(X_N(\frac {l}N))-{\sigma}(X_N(\frac {n_k}N))\big)\xi(l+1)|^2
\leq L^4E|X_N(\frac {l}N)-X_N(\frac {n_k}N)|^2\\
&\leq 2L^4\big(N^{-1}E|\sum_{n_k\leq m<l}
{\sigma}(X_N(m/N))\xi(m+1)|^2\nonumber\\
&+N^{-2}E|\sum_{n_k\leq m<l}b(X_N(m/N))\xi(m+1)|^2\big)\leq 16L^8N^{-1/2}.\nonumber
\end{eqnarray}

Now, by (\ref{2.2}) and (\ref{2.3}),
\[
E\sup_{0\leq t\leq 1}|J(t)|^2\leq\sum_{0\leq k\leq k_N}\sum_{n_k<l\leq n_{k+1}\wedge N}E|X_N(\frac {l}N)-X_N(\frac {n_k}N)|^2
\]
and for $n_k<l\leq n_{k+1}$,
\[
|X_N(\frac {l}N)-X_N(\frac {n_k}N)|\leq N^{-1/2}(L^2+N^{-1/2}L)[N^{\frac 14}]\leq
2L^2N^{-\frac 14}.
\]
These together with (\ref{3.3})--(\ref{3.5}) yield (\ref{3.2}).
\end{proof}

Next, we estimate the characteristic function of a sum of independent random vectors which is well
known but for completeness and in order to provide explicit constants we provide the details.
\begin{lemma}\label{lem3.2} For any integer $n \geq 1$ and $x\in{\mathbb R}^d$,
 \begin{equation}\label{3.6}
 |f_n(x,w)-\exp(-\frac 12\langle A(x)w,w\rangle)|\leq C_1n^{-\wp}
 \end{equation}
 for all $w\in{\mathbb R}^d$ with $|w|\leq n^{\wp/2}$ where $A(x)={\sigma}(x){\sigma}^*(x)$,
 \[
 f_n(x,w)=E\exp(i\langle w,\, n^{-1/2}{\sigma}(x)\sum_{0<l\leq n}\xi(l)\rangle),
 \]
 $\wp=1/6$ and $C_1=\frac 32L^6$.
 \end{lemma}
 \begin{proof}
 Set $m_j=j[\sqrt n],\, j=0,1,...,m(n)$, $m(n)=\max\{ j:\, j[\sqrt n]\leq n\}$, $y_j=
 {\sigma}(x)\sum_{m_j<l\leq m_{j+1}\wedge n}\xi(l)$ and $\eta_j=\langle w,\, n^{-1/2}y_j\rangle$.
 Now we have
 \begin{equation}\label{3.7}
 |f_n(x,w)-\exp(-\frac 12\langle A(x)w,w\rangle)|\leq I_1+I_2
 \end{equation}
 where
  \begin{equation}\label{3.8}
  I_1=|E\exp(i\sum_{0\leq j\leq m(n)}\eta_j)-\prod_{0\leq j\leq m(n)}Ee^{i\eta_j}|=0,
  \end{equation}
  since $\eta_j,\, j=1,...,m(n)+1$ are independent random variables, and
  \begin{eqnarray}\label{3.9}
  &I_2=|\prod_{0\leq j\leq m(n)}Ee^{i\eta_j}-\exp(-\frac 12\langle A(x)w,w\rangle)|\\
  &\leq \sum_{0\leq j\leq m(n)}|Ee^{i\eta_j}-\exp(-\frac {(m_{j+1}\wedge n-m_j)}{2n}\langle A(x)w,w\rangle)|\nonumber
  \end{eqnarray}
  where we use that
  \[
  |\prod_{1\leq j\leq l}a_j-\prod_{1\leq j\leq l}b_j|\leq\sum_{1\leq j\leq l}|a_j-b_j|
  \]
  whenever $0\leq |a_j|, |b_j|\leq 1,\, j=1,...,l$.

  Using (\ref{2.3}) and the inequalities
  \[
 |e^{ia}-1-ia+\frac {a^2}2|\leq |a|^3\,\,\mbox{and}\,\, |e^{-a}-1+a|\leq a^2\,\,\mbox{if}\,\, a\geq 0,
 \]
 we obtain that
 \begin{eqnarray}\label{3.10}
 &|Ee^{i\eta_k}-\exp(-\frac {(m_{j+1}\wedge n-m_j)}{2n}\langle A(x)w,w\rangle)|\\
 &\leq\frac 12|E\eta^2_j-\frac {(m_{j+1}\wedge n-m_j)}{n}\langle A(x)w,w\rangle|+E|\eta_j|^3+
 \frac 1{4n}|\langle A(x)w,w\rangle|^2.\nonumber
 \end{eqnarray}
 Now, by (\ref{2.3}) and the independency of $\xi(l)$'s,
 \begin{equation}\label{3.11}
 E\eta_j^2=n^{-1}\sum_{m_j<l\leq m_{j+1}\wedge n}E\langle w,{\sigma}(x)\xi(l)\rangle^2=n^{-1}
 (m_{j+1}\wedge n-m_j)\langle A(x)w,w\rangle.
 \end{equation}
 Hence,
 \[
 I_2\leq(\sqrt n+1)(n^{-3/2}L^6|w|^6+\frac 14n^{-1}L^4|w|^4)
 \]
 and (\ref{3.6}) follows.
  \end{proof}

  Set $Y_{N,k}(x)={\sigma}(x)\sum_{n_k<l\leq n_{k+1}}\xi(l)$ for $k=0,1,...,k_N-1$ and $Y_{N,k_N}(x)=
  {\sigma}(x)\sum_{n_{k_N}<l\leq N}\xi(l)$. As a corollary of Lemma \ref{lem3.2} we obtain
  \begin{lemma}\label{lem3.3} For any integer $N\geq 1$ and $k=0,1,...,k_N-1$,
  \begin{equation}\label{3.12}
  |E\big(\exp(i\langle w,\,(n_{k+1}-n_k)^{-1/2}Y_{N,k}(X_N(\frac {n_k}N))\rangle)|{\mathcal F}_{0n_k}^\xi\big)-
  g_{X_N(\frac {n_k}N)}(w)|\leq C_1(n_{k+1}-n_k)^{-\wp}
  \end{equation}
  for all $w\in{\mathbb R}^d$ with $|w|\leq (n_{k+1}-n_k)^{\wp/2}$,
  where $g_x(w)=\exp(-\frac 12\langle A(x)w,w\rangle)$ and, recall, ${\mathcal F}_{0n}^\xi={\sigma}\{\xi(1),...,\xi(n)\}$.
  \end{lemma}
  \begin{proof}
  Since $X_N(\frac {n_k}N)$ is ${\mathcal F}_{0n_k}^\xi$-measurable and $\sum_{n_k<j\leq n_{k+1}}\xi(l)$
  is independent of ${\mathcal F}_{0n_k}^\xi$, it follows that
  \[
  E\big(\exp(i\langle w,\,(n_{k+1}-n_k)^{-1/2}Y_{N,k}(X_N(\frac {n_k}N))\rangle|{\mathcal F}_{0n_k}^\xi\big)=
  f_{n_{k+1}-n_k}(X_N(\frac {n_k}N),w),
  \]
  where $f_n(x,w)$ was defined in Lemma \ref{lem3.2}, and so (\ref{3.12}) follows from (\ref{3.6}).
   \end{proof}

   \section{Strong approximation }\label{sec4}\setcounter{equation}{0}
The strong approximations here will be based on the following result which is a slight variation of
Theorem 3 and Remark 2.6 from \cite{MP1} with the additional feature from Theorem 4.6 of \cite{DP}
that we enrich the probability space by a sequence of i.i.d. uniformly distributed random variables
and not just by one such random variable and this result follows by essentially the same proofs as in
the cited above papers.
\begin{theorem}\label{thm4.1}
Let $\{ V_m,\, m\geq 1\}$ be a sequence of random vectors with values in ${\mathbb R}^d$ defined on some
probability space $({\Omega},{\mathcal F},P)$ and such that $V_m$ is measurable with respect to ${\mathcal F}_m$, $m=1,2,...$
where ${\mathcal F}_m,\, m\geq 1$ is a filtration of sub-${\sigma}$-algebras of ${\mathcal F}$. Let ${\mathcal G}_m$ and ${\mathcal H}_m$,
$m=0,1,...$ be two increasing sequences of countably generated sub-${\sigma}$-algebras of ${\mathcal F}$ such that
${\mathcal H}_m\subset{\mathcal G}_m\subset{\mathcal F}_m$ for each $m\geq 1$. Assume that the probability space is rich enough
so that there exists on it a sequence of uniformly distributed on $[0,1]$ independent random variables
 $U_m,\, m\geq 1$ independent of $\vee_{m\geq 0}{\mathcal G}_m$. For each $m\geq 1$, let $G_m(\cdot|{\mathcal H}_{m-1})$
 be a regular conditional distribution on ${\mathbb R}^d$, measurable with respect to ${\mathcal H}_{m-1}$ and with
 the conditional characteristic function
 \[
 g_m(w|{\mathcal H}_{m-1})=\int_{{\mathbb R}^d}\exp(i\langle w,x\rangle)G_m(dx|{\mathcal H}_{m-1}),\,\, w\in{\mathbb R}^d.
 \]
 Suppose that for some non-negative numbers $\nu_m,{\delta}_m$ and $K_m\geq 10^8d$,
 \begin{equation}\label{4.1}
 \int_{|w|\leq K_m}E\big\vert E(\exp(\langle w,V_m\rangle)|{\mathcal G}_{m-1})-g_m(w|{\mathcal H}_{m-1})\big\vert dw
 \leq\nu_m(2K_m)^d
 \end{equation}
 and that
 \begin{equation}\label{4.2}
 E\big(G_m(\{ x:\, |x|\geq\frac 12K_m\}|{\mathcal H}_{m-1})\big)<{\delta}_m.
 \end{equation}
 Then there exists a sequence $\{ W_m,\, m\geq 1\}$ of ${\mathbb R}^d$-valued random vectors defined on
 $({\Omega},{\mathcal F},P)$ with the properties

 (i) $W_m$ is ${\mathcal G}_m\vee{\sigma}\{U_m\}$-measurable for each $m\geq 1$;

 (ii) $G_m(\cdot |{\mathcal H}_{m-1})$ is conditional distribution of $W_m$ given ${\sigma}\{ U_1,...,U_{m-1}\}\vee
 {\mathcal G}_{m-1}$, in particular, $W_m$ is conditionally independent of ${\sigma}\{ U_1,...,U_{m-1}\}\vee
 {\mathcal G}_{m-1}$ (and so also of $W_1,...,W_{m-1})$ given ${\mathcal H}_{m-1},\, m\geq 1$;

 (iii) Let ${\varrho}_m=16K^{-1}_m\log K_m+2\nu_m^{1/2}K_m^d+2{\delta}_m^{1/2}$. Then
 \begin{equation}\label{4.3}
 P\{ |V_m-W_m|\geq{\varrho}_m\}\leq{\varrho}_m
 \end{equation}
 and, in particular, the Prokhorov distance between the distributions ${\mathcal L}(V_m)$ and ${\mathcal L}(W_m)$
 of $V_m$ and $W_m$, respectively, does not exceed ${\varrho}_m$.
 \end{theorem}

Now, in the notations of Theorem \ref{thm4.1} we set $V_k=(n_k-n_{k-1})^{-1/2}Y_{N,k-1}(X_N(
\frac {n_{k-1}}N))$,  ${\mathcal F}_k={\mathcal G}_k={\mathcal F}^\xi_{0n_k}$, ${\mathcal H}_k={\sigma}\{ X_N(\frac {n_k}N)\}$ and
$g_k(w|{\mathcal H}_{k-1})=g_{X_N(\frac {n_{k-1}}N)}(w)$ where $g_x$ was defined in Lemma \ref{lem3.3}.
Thus, $G_k(\cdot|{\mathcal H}_{k-1})=G_{X_N(\frac {n_{k-1}}N)}(\cdot)$ where $G_x$ is the mean zero $d$-dimensional Gaussian distribution with the covariance matrix $A(x)$ and the characteristic
function $g_x$. By Lemma \ref{lem3.3},
 \begin{eqnarray}\label{4.4}
 &\quad\int_{|w|\leq K_{k}}E\big\vert E\big(\exp(i\langle w,V_{k}\rangle)|
 {\mathcal G}_{k-1}\big)-g_{k}(w|{\mathcal H}_{k-1})\big\vert dw\\
 &\leq C_1(n_k-n_{k-1})^{-\wp}(2K_k)^d\leq 2^dC_1[N^{\frac 14}]^{-1/8}\nonumber
 \end{eqnarray}
 where we take $K_k=[N^{\frac 14}]^{\frac 1{24d}}<(n_k-n_{k-1})^{\wp/2}$. Next, for each
 $x\in{\mathbb R}^d$ let ${\Theta}_x$ be a mean zero Gaussian random variable with the
covariance matrix $A(x)$. Then by (\ref{2.2}) and the Chebyshev inequality,
\begin{eqnarray}\label{4.5}
&E\big( G_{k}(\{ y\in{\mathbb R}^d:\, |y|\geq\frac 12K_k\}|{\mathcal H}_{k-1})\big)\\
&\leq\sup_{y\in{\mathbb R}^d}P\{|{\Theta}_y| \geq\frac 12[N^{\frac 14}]^{\frac 1{24d}}\}\leq 4L^2d
[N^{\frac 14}]^{-\frac 1{12d}}.\nonumber
\end{eqnarray}

In order to use Theorem \ref{thm4.1} we need that $K_k\geq 10^8d$ and this will hold true if
 $N\geq N_0=((10^8d)^{24d}+1)^4$ which is the assumption of Theorem \ref{thm2.1}.
Now, Theorem \ref{thm4.1} provides us with random vectors $\{ W_k,\, k\geq 1\}$ satisfying
the properties
(i)--(iii), in particular, given $X_{N}(\frac {n_{k-1}}N)$, the random vector $W_{k}$ has the mean zero
 Gaussian distribution with the covariance matrix $A(X_{N}(\frac {n_{k-1}}N))$ and it is conditionally
  independent of ${\mathcal G}_{k-1}$ and of $W_1,...,W_{k-1}$ while in view of (\ref{4.4}) and (\ref{4.5}) the
 property (iii) holds true with
 \begin{eqnarray}\label{4.6}
 &{\varrho}_{k}=\frac 2{3d}[N^{\frac 14}]^{-\frac 1{24d}}\log([N^{\frac 14}])+
 2\sqrt {C_1}[N^{\frac 14}]^{-\frac 1{24}}\\
 &+4L\sqrt d[N^{\frac 14}]^{-\frac 1{24d}}\leq [N^{\frac 14}]^{-\frac 1{24d}}(\log N
 +2\sqrt {C_1}+4L\sqrt d).\nonumber
 \end{eqnarray}

 Next, we obtain the uniform $L^2$-bound for the difference between the sums of
  $(n_k-n_{k-1})^{1/2}V_k$'s and  of $(n_k-n_{k-1})^{1/2}W_k$'s. Set
 \[
 I(t)=\sum_{0\leq k\leq k_N(t)}(n_k-n_{k-1})^{1/2}(V_k-W_k).
 \]
 \begin{lemma}\label{lem4.2} For any integer $N\geq N_0$,
 \begin{equation}\label{4.7}
 E\max_{0\leq t\leq 1}|I(t)|^2\leq C_2N[N^{\frac 14}]^{-\frac 1{50d}}
 \end{equation}
 where
 \[
 C_2=\sup_{N\geq 1}([N^{\frac 14}]^{-\frac 1{480d}}\sqrt {\log N})(1+4L^2(L^2+ d)+2L^2d)
 (1+\sqrt {2\sqrt {C_1}}+2\sqrt {L\sqrt d} .
 \]
 \end{lemma}
 \begin{proof} Set
 \[
 M_k=\sum_{0\leq l\leq k}(n_l-n_{l-1})^{1/2}(V_l-W_l).
 \]
 Then
 \[
 \max_{0\leq t\leq 1}|I(t)|^2=\max_{1\leq k\leq k_N}|M_k|^2
 \]
 and by the properties (i) and (ii) of Theorem \ref{thm4.1} together with the conditional independence of each $V_l-W_l$ of ${\mathcal F}_{l-1}\vee{\sigma}\{ U_1,...,U_{l-1}\}$ given $X_N(\frac {n_{l-1}}N)$,
 it is easy to see that $M_k,\, k=1,2,...,k_N$ is a martingale
 with respect to the filtration ${\mathcal F}_{k}\vee{\sigma}\{ U_1,...,U_k\},\, k=1,...,k_N$. Hence, by the Doob martingale inequality
 \begin{equation}\label{4.8}
 E\max_{1\leq k\leq k_N}|M_k|^2\leq 4E|M_{k_N}|^2=4[N^{\frac 14}]\sum_{1\leq k\leq k_N}E|V_k-W_k|^2
 \end{equation}
 where we use also that $(V_k-W_k)$, $k=1,...,k_N$ are uncorrelated for different $k$'s.

 Next, by the Cauchy-Schwarz inequality
 \begin{eqnarray}\label{4.9}
 &E|V_k-W_k|^{2}=E(|V_k-W_k|^{2}{\mathbb I}_{|V_k-W_k|\leq{\varrho}_k})\\
 &+E(|V_k-W_k|^{2}{\mathbb I}_{|V_k-W_k|>{\varrho}_k})\nonumber\\
 &\leq{\varrho}^{2}_k+(E|V_k-W_k|^{4})^{1/2}(P\{|V_k-W_k|>{\varrho}_k\})^{\frac 12}\nonumber\\
 &\leq{\varrho}^{2}_k+4{\varrho}^{\frac 12}_k((E|V_k|^{4})^{1/2}+(E|W_k|^{4})^{1/2}).\nonumber
 \end{eqnarray}
 Now, by (\ref{2.2}) and (\ref{2.3}),
 \begin{eqnarray}\label{4.10}
 &E|V|^4\leq [N^{\frac 14}]^{-2}L^4E|\sum_{n_{k-1}<l\leq n_k}\xi(l)|^4\\
 &\leq [N^{\frac 14}]^{-2}L^4\big([N^{\frac 14}]E|\xi(1)|^4+[N^{\frac 14}]^2
 (E|\xi(1)|)^2\big)\leq L^4(L^2+d^2).\nonumber
\end{eqnarray}
 Since $W_k$ is distributed as ${\sigma}(X_N(\frac {n_{k-1}}N)){\mathcal N}$, where ${\mathcal N}$ is the $d$-dimensional
 Gaussian random vector with the identity covariance matrix, we obtain that
 \begin{equation}\label{4.11}
 E|W_k|^4\leq 3L^4d^2.
 \end{equation}
 Finally, (\ref{4.7}) follows from (\ref{4.8})--(\ref{4.11}).
 \end{proof}

 Next, let $W(t),\, t\geq 0$ be a $d$-dimensional Brownian motion such that the
increments $W(n_k)-W(n_{k-1})$ are independent of $X_N(\frac {n_{k-1}}N)$ for any $k=1,...,k_N$.
Then, given $X_N(\frac {n_{k-1}}N)$, the sequences of random vectors $\tilde W_k ={\sigma}(X_N(\frac {n_{k-1}}N))(W(n_k)-W(n_{k-1}))$
and $(n_{k}-n_{k-1})^{1/2}W_{k},\, k=1,...,k_N$ have the same distributions. Moreover, we can
redefine the process $\xi(n),\, 1\leq n<\infty$ and choose a Brownian motion $W(s),\, s\geq 0$
preserving their distributions so that the joint distribution of the sequences of pairs $(V_{k},
W_{k})$ and of $(V_{k}, \tilde W_{k})$ will be the same and, in particular, that
 (\ref{4.7}) will hold true with $\tilde W_{k}$ in place of $ W_{k}$. Indeed, by the Kolmogorov extension theorem (see, for instance, \cite{SV}) such pair of processes
 exists if we impose consistent restrictions on their joint finite dimensional distributions. But since
 the pair of processes $\xi$ and $W_{k},\, 1\leq k\leq k_N$ satisfying
 our conditions exist by Theorem \ref{thm4.1} and Lemma \ref{lem4.2}, these restrictions are
 consistent and the required pair of processes exists. From now on we will drop tilde and denote
${\sigma}(X_N(\frac {n_{k-1}}N))(W(n_{k})-W(n_{k-1}))$ by $W_{k}$ which is supposed to satisfy (\ref{4.7}).

Now, using the Brownian motion $W(t),\, t\geq 0$ constructed above we consider the
new Brownian motion $W_N(t)=N^{-1/2} W(tN),\, 0\leq t\leq 1$ and introduce the diffusion process
 $\Xi_N(t),\, t\geq 0$ solving the stochastic differential equation (\ref{2.1}) which we write now
  with $W_N$,
\[
d\Xi_N(t)={\sigma}(\Xi_N(t))dW_N(t)+b(\Xi_N(t))dt,\,\, \Xi_N(0)=x_0.
\]
 Now, we introduce the auxiliary process $\hat\Xi_N$ with coefficients frozen at times $n_k$,
\begin{eqnarray*}
&\hat\Xi_N(t)=x_0+\sum_{1\leq k\leq k_N(tN)}\big({\sigma}(\Xi_N(\frac {n_{k-1}}N))
(W_N(\frac {n_{k}}N)-W_N(\frac {n_{k-1}}N))\\
&+N^{-1}b(\Xi_N(\frac {n_{k-1}}N))(n_{k}-n_{k-1})\big).
\end{eqnarray*}

\begin{lemma}\label{lem4.3} For any integer $N\geq 1$,
\begin{equation}\label{4.12}
E\max_{0\leq k\leq k_N}|\Xi_N(n_k/N)-\hat\Xi_N(n_k/N)|^{2}\leq 32{\Delta}(N)
\end{equation}
where ${\Delta}(N)=N^{-1}[N^{\frac 14}]$.
\end{lemma}
\begin{proof}
First, we write
\begin{eqnarray}\label{4.13}
&E\max_{0\leq k\leq k_N}|\Xi_N(n_k/N)-\hat\Xi_N(n_k/N)|^{2}\\
&\leq 2(E\max_{0\leq k\leq k_N}|J_1(n_k/N)|^{2}+E\max_{0\leq k\leq k_N}|J_2(n_k/N)|^{2})\nonumber
\end{eqnarray}
where
\[
J_1(t)=\int_{0}^{t}\big({\sigma}(\Xi_N(s))-{\sigma}(\Xi_N([s/{\Delta}(N)]{\Delta}(N)))\big)dW_N(s)
\]
and
\begin{equation*}
J_2(t)=\int_{0}^{t}\big(b(\Xi_N(s))-b(\Xi_N([s/{\Delta}(N)]{\Delta}(N)))\big)ds.
\end{equation*}
 By the Doob martingale inequality and the It\^ o isometry for stochastic integrals
 (see, for instance, \cite{Ki20}, Sections 6.1.2 and 7.2.1),
\begin{eqnarray}\label{4.14}
&E\max_{0\leq k\leq k_N)}|J_1(n_k/N)|^{2}\\
&\leq 4\int_{0}^{[T/{\Delta}(N)]{\Delta}(N)}E|{\sigma}(\Xi_N(s))
-{\sigma}(\Xi_N([s/{\Delta}(N)]{\Delta}(N)))|^{2}ds\nonumber\\
&\leq 4L^{2}\sum_{1\leq k\leq k_N} \int_{n_{k-1}/N}^{n_{k}/N}E|\Xi_N(s)-\Xi_N(n_{k-1}/N)|^{2}ds.
\nonumber\end{eqnarray}

By (\ref{2.2}) and the Cauchy--Schwarz inequality,
\begin{equation}\label{4.15}
E\max_{0\leq k\leq k_N}|J_2(n_k/N)|^{2}\leq L^2\int_{0}^{1}|\Xi_N(s)-\Xi_N([s/{\Delta}(N)]{\Delta}(N))|^2ds.
\end{equation}
Again, by (\ref{2.2}), (\ref{2.3}) and the moment inequalities for stochastic integrals
\begin{eqnarray}\label{4.16}
&E|\Xi_N(s)-\Xi_N(n_{k-1}/N)|^{2}\leq 2\big(E|\int_{n_{k-1}/N}^s{\sigma}(\Xi_N(u))dW_N(u)|^{2}\\
&+L^{2}(s-n_{k-1}/N)^{2}\big)\leq 2L^{2}{\Delta}(N)(1+{\Delta}(N))\leq 4L^2{\Delta}(N)\nonumber
\end{eqnarray}
since $s\in[n_{k-1}/N,n_k/N]$ here, and so $s-n_{k-1}/N\leq {\Delta}(N)$. Now, (\ref{4.12}) follows
 from (\ref{4.13})--(\ref{4.16}).
\end{proof}

 Next, we introduce another auxiliary process $\Xi_N^X$ defined by,
\begin{eqnarray*}
&\Xi_N^X(t)=x_0+\sum_{1\leq k\leq k_N(t)}\big({\sigma}(X_N(\frac {n_{k-1}}N))
(W_N(\frac {n_{k}}N)-W_N(\frac {n_{k-1}}N))\\
&+N^{-1}b(X_N(\frac {n_{k-1}}N))(n_{k}-n_{k-1})\big).
\end{eqnarray*}
Then we can write
\begin{eqnarray}\label{4.17}
& E\sup_{0\leq s\leq 1}|\hat X_N(s)-\hat\Xi_N(s)|^{2}=E\max_{0\leq k<k_N(TN)}|
\hat X_N(n_k/N)\\
&-\hat\Xi_N(n_k/N)|^{2}\leq 2(E\max_{0\leq k<k_N(TN)}|\hat X_N(n_k/N)-\Xi^X_N(n_k/N)|^{2}
\nonumber\\
&+E\max_{0\leq k<k_N(T)}|\Xi^X_N(n_k/N)-\hat\Xi_N(n_k/N)|^{2})\nonumber.
\end{eqnarray}
By Lemma \ref{lem4.2},
\begin{eqnarray}\label{4.18}
&E\max_{0\leq k\leq n}|\hat X_N(n_k/N)-\Xi^X_N(n_k/N)|^{2}=E\max_{0\leq k\leq n}\\
&\big\vert\sum_{0\leq l\leq k}{\sigma}(X_N(\frac {n_l}N))\big(N^{-\frac 12}\sum_{n_l<m\leq n_{l+1}}\xi(m)-(W_N(\frac {n_{l+1}}N)-W_N(\frac {n_l}N))\big)\big\vert^{2}\nonumber\\
&\leq N^{-1}E\sup_{0\leq t\leq 1}|I(t)|^{2}\leq C_2[N^{\frac 14}]^{-\frac 1{50d}}.\nonumber
\end{eqnarray}

In order to estimate the second term in the right hand side of (\ref{4.17}) introduce the
${\sigma}$-algebras ${\mathcal Q}_n={\mathcal F}_{0n}\vee{\sigma}\{ W(u),\, 0\leq u\leq n\}$ and observe that
by our construction for each $k$ the increment $W(n_{k+1})-W(n_k)$ is independent of ${\mathcal Q}_{n_k}$.
 On the other hand, for any $k\geq n$ both $X_N(n_k/N)$ and $\Xi_N(n_k/N)$ are
 ${\mathcal Q}_{n_k}$-measurable. Hence,
 \begin{equation*}
 {\mathcal I}_1(n_k)=\sum_{0\leq l\leq k-1}\big({\sigma}(X_N(\frac {n_{l}}N))-{\sigma}(\Xi_N(\frac {n_{l}}N))\big)
 (W_N(\frac {n_{l+1}}N)-W_N(\frac {n_l}N))
 \end{equation*}
 is a martingale in $k$ with respect to the filtration ${\mathcal Q}_k, k=1,2,...,k_N-1$. Thus, by (\ref{2.2})
 and the Doob martingale inequality,
 \begin{eqnarray}\label{4.19}
 &E\max_{1\leq k\leq m}|{\mathcal I}_1(n_k)|^{2}\leq 4 E|{\mathcal I}_1(n_m)|^{2}\\
 &\leq 4\sum_{0\leq l\leq m-1}E|({\sigma}(X_N(\frac {n_{l}}N))-{\sigma}(\Xi_N(\frac {n_{l}}N)))
 (W_N(\frac {n_{l+1}}N)-W_N(\frac {n_l}N))|^2\nonumber\\
 &\leq 4dL^2{\Delta}(N)\sum_{0\leq l<m}E|X_N(\frac {n_l}N)-\Xi_N(\frac {n_l}N)|^2.\nonumber
 \end{eqnarray}

Next, observe that
\begin{eqnarray}\label{4.20}
&\max_{0\leq k\leq k_N}|\Xi_N(n_k/N)-\hat\Xi_N(n_k/n)|^{2}\\
&\leq 2(E\max_{0\leq k\leq k_N}|{\mathcal I}_1(n_k)|^{2}+E\max_{0\leq k\leq k_N}|{\mathcal I}_2(n_k)|^{2})
\nonumber\end{eqnarray}
where
\begin{eqnarray*}
&{\mathcal I}_2(n_k)=N^{-1}\sum_{0\leq l\leq k-1}\big(b(X_N(n_{l}))-b(\Xi_N(n_{l}))\big)(n_{l+1}-n_l).
\end{eqnarray*}
By (\ref{2.2}) we have
\begin{eqnarray}\label{4.21}
&|{\mathcal I}_2(n_k)|^{2}\leq L^2({\Delta}(N))^2(\sum_{0\leq l<k}|X_N(\frac {n_l}N)-\Xi_N(\frac {n_l}N)|)^2\\
&\leq  L^2({\Delta}(N))^2k\sum_{0\leq l<k}|X_N(\frac {n_l}N)-\Xi_N(\frac {n_l}N)|^2\nonumber\\
&\leq  L^2{\Delta}(N)\sum_{0\leq l<k}|X_N(\frac {n_l}N)-\Xi_N(\frac {n_l}N)|^2.\nonumber
\end{eqnarray}

Now denote
\[
Q_k=E\max_{0\leq l\leq k}|X_N(n_l/N)-\Xi_N(n_l/N)|^{2}.
\]
Then we obtain from (\ref{3.2}), (\ref{4.12}) and (\ref{4.17})--(\ref{4.21}) that
for $n\leq k_N$,
\begin{equation}\label{4.22}
Q_n\leq C_3[N^{\frac 14}]^{-\frac 1{50d}}+C_4{\Delta}(N)\sum_{0\leq k\leq n-1}Q_k
\end{equation}
where $C_3=408L^8+6C_2+96$ and $C_4=L^2(16d+4)$. By the discrete (time) Gronwall inequality (see, for instance, \cite{Cla}),
\begin{equation}\label{4.23}
Q_{k_N}\leq C_3[N^{\frac 14}]^{-\frac 1{50d}}\exp(C_{4}).
\end{equation}

It remains to estimate deviations of our continuous time processes within intervals of time
$(n_k/N,n_{k+1}/N)$ which where not taken into account in previous estimates,
i.e. we have to deal now with
\begin{eqnarray*}
&{\mathcal J}_1=E\sup_{0\leq t\leq 1}|X_N(t)-X_N(n_{k_N(tN)})|^{2}\\
&\mbox{and}\,\,\, {\mathcal J}_2=E\sup_{0\leq t\leq 1}|\Xi_N(t)-\Xi_N(n_{k_N(tN)})|^{2}.
\end{eqnarray*}
By the straightforward estimates using (\ref{2.2}) and (\ref{2.4}) we obtain
\begin{equation}\label{4.25}
{\mathcal J}_1\leq 2{\Delta}(N)L^2(L^2+1)
\end{equation}
and
\begin{equation}\label{4.26}
{\mathcal J}_2\leq 4({\mathcal J}_3+(2L)^{2}({\Delta}(N))^{2})
\end{equation}
where
\[
{\mathcal J}_3=E\max_{0\leq k\leq k_N}\sup_{0\leq s\leq{\Delta}(N)}|\int_{n_k/N}^{N^{-1}n_k+s}
{\sigma}(\Xi_N(u))dW_N(u)|^{2}.
\]

By the Jensen (or Cauchy-Schwarz) inequality and the uniform moment estimates for stochastic
integrals
\begin{eqnarray}\label{4.27}
&{\mathcal J}_3\leq\big( E\max_{0\leq k\leq k_N}\sup_{0\leq s\leq{\Delta}(N)}|\int_{n_k/N}^{N^{-1}n_k+s}
{\sigma}(\Xi_N(u))dW_N(u)|^{4}\big)^{1/2}\\
&\leq\big( \sum_{0\leq k\leq k_N}E\sup_{0\leq s\leq{\Delta}(N)}|\int_{n_k/N}^{N^{-1}n_k+s}
{\sigma}(\Xi_N(u))dW_N(u)|^{4}\big)^{1/2}\nonumber\\
&\leq(\frac {4}{3})^{2}\big( \sum_{0\leq k\leq k_N}E|\int_{n_k/N}^{N^{-1}n_{k+1}}
{\sigma}(\Xi_N(u))dW_N(u)|^{4}\big)^{1/2}\nonumber\\
&\leq 6L^2({\Delta}(N))^{1/2}.\nonumber
\end{eqnarray}
 Combining (\ref{4.23})--(\ref{4.27}) we complete the proof of Theorem \ref{thm2.1}.
 \qed

 \section{Dynkin games }\label{sec5}\setcounter{equation}{0}

In view of the form of our regularity conditions (\ref{2.9}) and (\ref{2.10})  on the payoff
 functionals $F$ and $G$ we will need the following exponential estimates.

 \begin{lemma}\label{lem5.0} (i) For any $M>0$ and an integer $N\geq 1$,
 \begin{equation}\label{5.1.1}
 \max_{0\leq n\leq N}E\exp(M|X_N(n/N)|)\leq D^X_Me^{M|x|}
 \end{equation}
 and
 \begin{equation}\label{5.1.2}
 \max_{0\leq n\leq N}E\exp(M|\hat X_N(n/N)|)\leq D^X_Me^{M|x|}
 \end{equation}
 where $x=X_N(0)=\hat X_N(0)$ and $D^X_M=2d\exp(\frac 12d^4L^4+L+\frac 16M^3d^6L^6e^{Md^2L^2})$
 does not depend on $N$;

 (ii) For any ${\delta},M>0$ and an integer $N\geq 1$,
 \begin{equation}\label{5.1.3}
 E\exp(M\max_{0\leq n\leq N}|X_N(n/N)|)\leq D^X_Me^{M|x|}N^{\delta}
 \end{equation}
 and
 \begin{equation}\label{5.1.4}
 \max_{0\leq n\leq N}E\exp(M|\hat X_N(n/N)|)\leq D^X_{M,{\delta}}e^{M|x|}N^{\delta}
 \end{equation}
 where $D^X_{M,{\delta}}=1+(D^X_{2M/{\delta}}D^X_{2M})^{1/2}$ also does not depend on $N$;

 (iii) For any $M>0$,
 \begin{equation}\label{5.1.5}
 E\exp(M\sup_{0\leq t\leq 1}|\Xi(t)|)\leq D^\Xi_Me^{M|x|}\,\,\mbox{and}\,\,
 E\exp(M\sup_{0\leq t\leq 1}|\hat \Xi_N(t)|)\leq D^\Xi_Me^{M|x|}
 \end{equation}
 where $x=\Xi(0)$ and $D^\Xi_M=2\exp(L+\frac 12ML^2d^2)$.
 \end{lemma}
\begin{proof}
(i) Writing
\[
X_N(n/N)=x+\sum_{k=0}^{n-1}\big(N^{-1/2}{\sigma}(X_N(k/N))\xi(k+1)+N^{-1}b(X_N(k/N))\big)
\]
we obtain
\begin{eqnarray}\label{5.1.6}
&E\exp(M|X_N(n/N)|)\\
&\leq e^{M(|x|+L)}E\exp(MN^{-1/2}|\sum_{k=0}^{n-1}{\sigma}(X_N(k/N))\xi(k+1)|)\nonumber\\
&\leq E\max_{1\leq i\leq d}\exp(MdN^{-1/2}|\sum_{k=0}^{n-1}\sum_{j=1}^d{\sigma}_{ij}(X_N(k/N))\xi_j(k+1)|)
\nonumber\\
&\leq\sum_{1\leq i\leq d}\big( E\exp(MdN^{-1/2}\sum_{k=0}^{n-1}\sum_{j=1}^d{\sigma}_{ij}(X_N(k/N))\xi_j(k+1))
\nonumber\\
&+ E\exp(-MdN^{-1/2}\sum_{k=0}^{n-1}\sum_{j=1}^d{\sigma}_{ij}(X_N(k/N))\xi_j(k+1))\big).\nonumber
\end{eqnarray}

To shorten a bit notations we set for this proof $g(x)=(g_1(x),...,g_d(x))$ where
$g_j(x)=\pm Md{\sigma}_{ij}(x)$. Then we have to estimate
\begin{eqnarray}\label{5.1.7}
& E\exp\big(N^{-1/2}\sum_{k=0}^{n-1}\langle g(X_N(k/N)),\,\xi(k+1)\rangle\big)\\
&=E\big(\exp(N^{-1/2}\sum_{k=0}^{n-2}\langle g(X_N(k/N)),\,\xi(k+1)\rangle)\nonumber\\
&\times E\big(\exp(N^{-1/2}\langle g(X_N(n-1/N)),\,\xi(n)\rangle)|{\mathcal F}^\xi_{0,n-1}\big)\big).\nonumber
\end{eqnarray}
Since $|g_j(x)|\leq MdL,\, j=1,...,d$, it follows that
\begin{eqnarray}\label{5.1.8}
&\quad|\exp(N^{-1/2}\langle g(X_N(n-1/N)),\,\xi(n)\rangle)-1-N^{-1/2}\langle g(X_N(n-1/N)),\,\xi(n)\rangle\\
&-\frac 12N^{-1}\langle g(X_N(n-1/N)),\,\xi(n)\rangle^2|\leq\sum_{l=3}^\infty \frac {(Md^2L^2)^l}
{N^{l/2}\l!}\leq \tilde DN^{-3/2}\nonumber
\end{eqnarray}
where $\tilde D=\frac 16M^3d^6L^6e^{Md^2L^2}$. Hence,
\begin{eqnarray}\label{5.1.9}
&E\big(\exp(N^{-1/2}\langle g(X_N(n-1/N)),\,\xi(n)\rangle)|{\mathcal F}_{0,n-1}\big)\\
&\leq 1+\frac 12N^{-1}\langle g(X_N(n-1/N)),\,\xi(n)\rangle^2\leq 1+\frac 12N^{-1}d^4L^4+
\tilde DN^{-3/2}\nonumber
\end{eqnarray}
where we used that $E(\xi(n)|{\mathcal F}_{0,n-1})=E\xi(n)=0$. Continuing in the same way with the sums in
the exponent till $n-2,n-3,...,1$ we obtain that
\begin{eqnarray}\label{5.1.10}
& E\exp\big(N^{-1/2}\sum_{k=0}^{n-1}\langle g(X_N(k/N)),\,\xi(k+1)\rangle\big)\\
&\leq (1+\frac 12N^{-1}d^4L^4+N^{-3/2}\tilde D)^N\nonumber\\
&\leq(1+\frac 12N^{-1}d^4L^4)^N(1+\tilde DN^{-3/2})^N
\leq\exp(\tilde D+\frac 12d^4L^4)\nonumber
\end{eqnarray}
proving (\ref{5.1.1}) while (\ref{5.1.2}) follows in the same way.

(ii) Set ${\Gamma}(y)=\{|X_N(n/N)-x|\geq y\}$. By (i) and the exponential Chebyshev inequality
for any $n\leq N,\, y\geq 0$ and ${\delta}>0$,
\[
P\{{\Gamma}(\frac {{\delta} y}{2M})\}\leq D_{\frac {2M}{\delta}}e^{-y}.
\]
Then, taking $y=2\log N$ we have
\begin{eqnarray}\label{5.1.11}
&E\exp(M\max_{0\leq n\leq N}|X_N(n/N)|)\\
&\leq e^{M|x|}E\exp(M\max_{1\leq n\leq N}|X_N(n/N)-x|)\nonumber\\
&\leq e^{M|x|}\big(N^{\delta}+\sum_{n=1}^NE({\mathbb I}_{{\Gamma}_n(\frac {\delta} M\log N)}\exp(M|X_N(n/N)-x|))\big)
\nonumber\\
&\leq e^{M|x|}\big(N^{\delta}+\sum_{n=1}^N\big(P\{{\Gamma}_n(\frac {\delta} M\log N)\}\big)^{1/2}
\big(E\exp(2M|X_N(n/N)-x|))\big)^{1/2}\nonumber\\
&\leq e^{M|x|}\big(N^{\delta}+(D_{2M/{\delta}}D_{2M})^{1/2})\nonumber
\end{eqnarray}
proving (\ref{5.1.3}) while (\ref{5.1.4}) follows in the same way.

For (iii) we have
\begin{eqnarray}\label{5.1.12}
&E\exp(M\sup_{0\leq t\leq 1}|\Xi(t)|)\\
&\leq e^{(M(|x|+L)}E\exp(M\sup_{0\leq t\leq 1}|\int_0^t\sigma(\Xi(s))dW(s)|)\nonumber\\
&\leq e^{(M(|x|+L)}\sum_{i=1}^d\big(E\sup_{0\leq t\leq 1}\exp(Md\sum_{j=1}^d\int_0^t\sigma_{ij}(\Xi(s))dW_j(s))\nonumber\\
&+E\sup_{0\leq t\leq 1}\exp(-Md\sum_{j=1}^d\int_0^t\sigma_{ij}(\Xi(s))dW_j(s))\nonumber.
\end{eqnarray}
Since
\[
\exp\big(\pm Md\sum_{j=1}^d\int_0^t\sigma_{ij}(\Xi(s))dW_j(s)-\frac {M^2d^2}2\int_0^t
\sum_{j=1}^d{\sigma}_{ij}^2(\Xi(s))ds\big)\]
is a martingale with the expectation equal one, it follows from (\ref{2.2}) and the Doob martingale
inequality that
\[
E\sup_{0\leq t\leq 1}\exp(\pm Md\sum_{j=1}^d\int_0^t\sigma_{ij}(\Xi(s))dW_j(s)) \leq
e^{\frac 12M^2L^2d^2},
\]
and so the first inequality in (\ref{5.1.5}) follows while we obtain the second one in the same way.
\end{proof}

Let ${\mathcal T}^{{\Delta}}$ be the set of all stopping times with respect
to the filtration ${\mathcal F}^\xi_{0,n_k},\, k\geq 0$ taking on values $n_k,\, k=0,1,...,k_{\max}$
 where $k_{\max}=k_N$ if $k_N=N/[N^{\frac 14}]$ and $k_{\max}=k_N+1$ and $n_{k_{\max}}=N$
if $n_{k_N}<N$. Denote by ${\mathcal Q}_{n_k}$ the ${\sigma}$-algebra ${\mathcal F}^\xi_{0,n_k}\vee{\sigma}\{ U_i,\, 1\leq i\leq k\}$ where, recall, $U_1,U_2,...$ is a sequence of i.i.d. uniformly distributed
random variables appearing in Theorem \ref{thm4.1}.  Let ${\mathcal T}^{\mathcal Q}$ be the
 set of all stopping times with respect to the filtration ${\mathcal Q}_{n_k},\, k\geq 0$ taking on values
 $n_k,\, k=0,1,...,k_{\max}$. Next, introduce the payoffs based on $\hat X_N$ (the same as
 in Lemma \ref{lem3.1}),
 \[
 \hat R_N(s,t)=G_s(\hat X_N){\mathbb I}_{s<t}+F_t(\hat X_N){\mathbb I}_{t\leq s}
 \]
 and the Dynkin game values corresponding to the sets of stopping times ${\mathcal T}^{\Delta}$ and ${\mathcal T}^{\mathcal Q}$,
 \[
 V_N^{\Delta}=\inf_{{\sigma}\in{\mathcal T}^{\Delta}}\sup_{\tau\in{\mathcal T}^{\Delta}}ER_N({\sigma}/N,\tau/N),
 \]
 \[
 \hat V_N^{\Delta}=\inf_{{\sigma}\in{\mathcal T}^{\Delta}}\sup_{\tau\in{\mathcal T}^{\Delta}}E\hat R_N({\sigma}/N,\tau/N),
 \]
 \[
 \mbox{and}\,\,\,\hat V_N^{\mathcal Q}=\inf_{{\sigma}\in{\mathcal T}^{\mathcal Q}}\sup_{\tau\in{\mathcal T}^{\mathcal Q}}E
 \hat R_N({\sigma}/N,\tau/N).
 \]

 \begin{lemma}\label{lem5.1} For any ${\delta}>0$ and an integer $N\geq 1$,
 \begin{equation}\label{5.1}
 |V_N-V_N^{\Delta}|\leq D^X_{K,{\delta}}Ke^{K|x|}N^{{\delta}-\frac 14}(1+L+L^2),
 \end{equation}
 where $x=X_N(0)$, and
  \begin{equation}\label{5.2}
 |V_N^{\Delta}-\hat V_N^{\Delta}|\leq 24\sqrt {D^X_{4K,{\delta}}}e^{K|x|}L^4N^{\frac 12({\delta}-\frac 12)}.
 \end{equation}
 \end{lemma}
 \begin{proof} For any $\zeta\in{\mathcal T}^\xi_{0N}$ set $\zeta^{\Delta}=\min\{ n_k:\, n_k\geq\zeta\}$
 which defines a stopping time from ${\mathcal T}^{\Delta}$ satisfying
 \begin{equation}\label{5.3}
 N^{-1}\zeta+{\Delta}(N)\geq N^{-1}\zeta^{\Delta}\geq N^{-1}\zeta.
 \end{equation}
 Since ${\mathcal T}^\xi_{0N}\supset{\mathcal T}^{\Delta}$ we see that
 \[
 V_N\geq\inf_{\zeta\in{\mathcal T}^\xi_{0N}}\sup_{\eta\in{\mathcal T}^{\Delta}}ER(\zeta/N,\eta/N).
 \]
 Then for any ${\vartheta}>0$ there exists $\zeta_{\vartheta}\in{\mathcal T}^\xi_{0N}$ such that
 \[
 V_N\geq\sup_{\eta\in{\mathcal T}^{\Delta}}ER_N(\zeta_{\vartheta}/N,\eta/N)-{\vartheta},
 \]
 and so
 \begin{eqnarray}\label{5.4}
 &V_N\geq\sup_{\eta\in{\mathcal T}^{\Delta}}ER_N(\zeta_{\vartheta}^{\Delta}/N,\eta/N)-{\vartheta}\\
 &-\sup_{\eta\in{\mathcal T}^{\Delta}}E(R_N(\zeta_{\vartheta}^{\Delta}/N,\eta/N)-R_N(\zeta_{\vartheta}/N,\eta/N))\nonumber\\
 &\geq V_N^{\Delta}-{\vartheta}-\sup_{\eta\in{\mathcal T}^{\Delta}}J_1(\zeta_{\vartheta}/N,\eta/N)\nonumber
 \end{eqnarray}
 where for any $\zeta\in{\mathcal T}^\xi_{0N}$ and $\eta\in{\mathcal T}^{\Delta}$,
 \[
 J_1(\zeta/N,\eta/N)=E(R_N(\zeta^{\Delta}/N,\eta/N)-R_N(\zeta/N,\eta/N)).
 \]

 Since $\zeta^{\Delta}\geq\zeta$,
 \[
 R_N(\zeta/N,\eta/N)=G_{\zeta/N}(X_N)\,\,\mbox{whenever}\,\, R_N(\zeta^{\Delta}/N,
 \eta/N)=G_{\zeta^{\Delta}/N}(X_N).
 \]
 Hence, by (\ref{2.10}) and (\ref{5.3}),
 \begin{eqnarray}\label{5.5}
& R_N(\zeta^{\Delta}/N,\eta/N)-R_N(\zeta/N,\eta/N)\leq\max\big( |G_{\zeta^{\Delta}/N}(X_N)
-G_{\zeta/N}(X_N)|,\\
& |F_{\zeta^{\Delta}/N}(X_N)-F_{\zeta/N}(X_N)|\big)\nonumber\\
&\leq K\big({\Delta}(N)(1+L)
+N^{-1/2}\max_{0\leq k\leq k_{\max}}\max_{1\leq l\leq N^{\frac 14}}\nonumber\\
&|\sum_{n_k+l\leq j\leq n_{k+1}}{\sigma}(X_N(j/N)\xi(j)|\big)\exp(K\max_{0\leq n\leq N}|X_N(n/N)|)
\nonumber\\
&\leq K({\Delta}(N)(1+L)+L^2N^{-1/4})\exp(K\max_{0\leq n\leq N}|X_N(n/N)|).\nonumber
\end{eqnarray}
Taking here $\zeta_{\vartheta}$ in place of $\zeta$ we obtain from (\ref{5.4}), (\ref{5.5}) and Lemma
\ref{lem5.0}(ii) that
\[
V_N\geq V_N^{\Delta}-{\vartheta}-D^X_{K,{\delta}}Ke^{K|x|}N^{{\delta}-\frac 14}(1+L+L^2)
\]
and since ${\vartheta}>0$ is arbitrary we have that
\begin{equation}\label{5.6}
V_N\geq V_N^{\Delta}-D^X_{K,{\delta}}Ke^{K|x|}N^{{\delta}-\frac 14}(1+L+L^2).
\end{equation}

On the other hand, since the Dynkin game here has a value (see, for instance, \cite{Ki20}, Section
6.2.2) we can write also that
\begin{equation}\label{5.7}
V_N=\sup_{\eta\in{\mathcal T}^\xi_{0N}}\inf_{\zeta\in{\mathcal T}^\xi_{0N}}ER_N(\zeta/N,\eta/N)\leq\inf_{\zeta\in{\mathcal T}^{\Delta}}
ER(\zeta/N,\eta_{\vartheta}/N)+{\vartheta}
\end{equation}
for each ${\vartheta}>0$ and some $\eta_{\vartheta}\in{\mathcal T}^\xi_{0N}$. Introducing $\eta_{\vartheta}^{\Delta}$ and arguing as
above we obtain that
\[
V_N\leq V_N^{\Delta}+D^X_{K,{\delta}}Ke^{K|x|}N^{{\delta}-\frac 14}(1+L+L^2)
\]
which together with (\ref{5.6}) completes the proof of (\ref{5.1}).

In order to prove (\ref{5.2}) we observe that by (\ref{2.9}), Lemma \ref{lem3.1}, Lemma \ref{lem5.0}(ii), the Chebyshev and the Cauchy-Schwarz inequalities
\begin{eqnarray}\label{5.8}
&|V_N^{\Delta}-\hat V_N^{\Delta}|\leq\sup_{\zeta\in{\mathcal T}^{\Delta}}\sup_{\eta\in{\mathcal T}^{\Delta}}E|R_N(\zeta/N,
\eta/N)-\hat R_N(\zeta/N,\eta/N)|\\
&\leq\max\big(E\sup_{0\leq t\leq 1}|F_t(X_N)-F_t(\hat X_N)|,\,|G_t(X_N)-
G_t(\hat X_N)|\big)\nonumber\\
&\leq KE\big(\big(\sup_{0\leq t\leq 1}|X_N(t)-\hat X_N(t)|+{\mathbb I}_{\sup_{0\leq t\leq 1}|X_N(t)-\hat X_N(t)|>1}\big)\nonumber\\
&\times\exp(K\sup_{0\leq t\leq 1}(|X_N(t)|+|\hat X_N(t)|))\big)\nonumber\\
&\leq 2K\big(E\sup_{0\leq t\leq 1}|X_N(t)-\hat X_N(t)|^2\big)^{1/2}\nonumber\\
&\times\big( E\exp(4K\sup_{0\leq t\leq 1}|X_N(t)|)\big)^{1/4}\big(E\exp(4K\sup_{0\leq t\leq 1}|\hat X_N(t)|)\big)
^{1/4}\nonumber\\
&\leq 24\sqrt {D^X_{4K,{\delta}}}e^{K|x|}L^4N^{\frac 12({\delta}-\frac 12)}.\nonumber
\end{eqnarray}
yielding (\ref{5.2}).
  \end{proof}

\begin{lemma}\label{lem5.2} For any integer $N\geq 1$,
\begin{equation}\label{5.9}
\hat V_N^{\Delta}=\hat V_N^{\mathcal Q}.
\end{equation}
\end{lemma}
\begin{proof}
We prove (\ref{5.9}) obtaining both $\hat V_N^{\Delta}$ and $\hat V_N^{\mathcal Q}$ by the standard dynamical
programming (backward recursion) procedure (see, for instance, Section 1.3.2 in \cite{Ki20}).
Namely, we have $\hat V_N^{\Delta}=\hat V_{N,0}^{\Delta}$ and $\hat V_N^{\mathcal Q}=\hat V_{N,0}^{\mathcal Q}$ where
\begin{equation}\label{5.10}
\hat V_{N,k_{\max}}^{\Delta}=F_T(\hat X)=\hat V_{N,k_{\max}}^{\mathcal Q}
\end{equation}
proceeding recursively
\[
\hat V_{N,k}^{\Delta}=\min\big(G_{n_k/N}(\hat X_N),\,\max(F_{n_k/N}(\hat X_N),\,
E(\hat V_{N,k+1}^{\Delta}|{\mathcal F}^\xi_{0,n_k}))\big)
\]
and
\[
\hat V_{N,k}^{\mathcal Q}=\min\big(G_{n_k/N}(\hat X_N),\,\max(F_{n_k/N}(\hat X_N),\,
E(\hat V_{N,k+1}^{\mathcal Q}|{\mathcal Q}_{n_k}))\big).
\]

Since each ${\sigma}$-algebra ${\sigma}\{ U_1,...,U_k\}$ is independent of $\xi_1,\xi_2,...$ by the
construction, i.e. it is independent of all ${\sigma}$-algebras ${\mathcal F}^\xi_{0,l},\, l=0,\pm 1,...$,
and so it is independent of $X_N$, it follows (see, for instance, \cite{Chu}, p.323
or \cite{Ki07}, Remark 4.3) that
\[
E(\hat V_{N,k+1}^{\Delta}|{\mathcal F}^\xi_{0,n_k})=E(\hat V_{N,k+1}^{\Delta}|{\mathcal Q}_{n_k}),
\]
and so starting from (\ref{5.10}) we proceed recursively to $\hat V_{N,0}^{\Delta}=
\hat V_{N,0}^{\mathcal Q}$
proving (\ref{5.9}).
\end{proof}

Next, we turn our attention to the diffusion $\Xi$ constructed in Theorem \ref{thm2.1} and
consider the corresponding Dynkin game value $V^\Xi$ given by (\ref{2.8}). Set
${\mathcal G}^\Xi_{n_k}={\sigma}\{ W_N(u/N):\, u\leq n_k\}$ and observe that by the construction
\begin{equation}\label{5.11}
{\mathcal G}^\Xi_{n_k}\subset{\mathcal Q}_{n_k}={\mathcal F}^\xi_{0,n_k}\vee{\sigma}\{ U_i,\, 1\leq i\leq k\}
\end{equation}
where $W_N$ is the Brownian motion constructed in Section \ref{sec4}.
 Let ${\mathcal T}_{\Delta}^\Xi$ be the set of all stopping times with respect to
the filtration ${\mathcal G}^\Xi_{n_k},\, k\geq 0$ and ${\mathcal T}_{{\Delta}}^{\mathcal Q}$ be the set of all stopping times
with respect to the filtration ${\mathcal Q}_{n_k},\, k\geq 0$, both taking values $n_k$ when $k$ runs from
0 to $k_{\max}$. Set
\[
\hat R^\Xi(s,t)=G_s(\hat\Xi){\mathbb I}_{s<t}+F_t(\hat\Xi){\mathbb I}_{t\leq s}
\]
where the process $\hat\Xi$ is the same as in Lemma \ref{lem4.3}. Set
 \[
 V^\Xi_{\Delta}=\inf_{\zeta\in{\mathcal T}^\Xi_{\Delta}}\sup_{\eta\in{\mathcal T}^\Xi_{\Delta}}ER^\Xi(\zeta/N,\eta/N),
 \]
 \[
 \hat V^\Xi_{\Delta}=\inf_{\zeta\in{\mathcal T}^\Xi_{\Delta}}\sup_{\eta\in{\mathcal T}^\Xi_{\Delta}}E
 \hat R^\Xi(\zeta/N,\eta/N)
 \]
 and
 \[
 \hat V^\Xi_{\mathcal Q}=\inf_{\zeta\in{\mathcal T}^{\mathcal Q}}\sup_{\eta\in{\mathcal T}^{\mathcal Q}}E\hat R^\Xi(\zeta/N,\eta/N).
 \]

\begin{lemma}\label{lem5.3} For any integer $N\geq 1$,
\begin{equation}\label{5.12}
|V^\Xi-V^\Xi_{\Delta}|\leq K({\Delta}(N)D_K^\Xi+18L)\sqrt {2D^\Xi_{2K}})
\sqrt {{\Delta}(N)},
\end{equation}
where $x=\Xi(0)$, and
\begin{equation}\label{5.13}
|V^\Xi_{\Delta}-\hat V^\Xi_{\Delta}|\leq (4\sqrt {2}+2L)Ke^{K|x|}\sqrt {D^\Xi_{4K}}\sqrt {{\Delta}(N)}.
\end{equation}
\end{lemma}
\begin{proof}
The proof is similar to Lemma \ref{lem5.1} but here in place of estimates for $X_N$ we have
to use moment estimates for diffusions. Set ${\mathcal T}_{01}^{\Xi,N}=\{\zeta:\,\zeta/N\in{\mathcal T}_{01}^\Xi\}$
where, recall, ${\mathcal T}^\Xi_{01}$ is the set of stopping times with respect to the filtration ${\mathcal F}_t^\Xi=
{\sigma}\{ W_N(s),\, s\leq t\}$ having values in $[0,1]$. For any $\xi\in{\mathcal T}_{01}^{\Xi,N}$ define
$\zeta^{\Delta}=\min\{ n_k:\, n_k\geq\zeta\}$ which yields a stopping time from ${\mathcal T}^\Xi_{\Delta}$ satisfying
(\ref{5.3}). Since ${\mathcal T}_{\Delta}^\Xi\subset{\mathcal T}_{0,1}^{\Xi,N}$ we have that
\[
V^\Xi\geq\inf_{\zeta\in{\mathcal T}_{01}^{\Xi,N}}\sup_{\eta\in{\mathcal T}_{{\Delta}}^{\Xi}}ER^\Xi(\zeta/N,\eta/N).
\]
In the same way as in (\ref{5.4}) we obtain that for some $\zeta_{\vartheta}\in{\mathcal T}_{01}^{\Xi,N}$,
\begin{equation}\label{5.14}
V^\Xi\geq V^\Xi_{\Delta}-{\vartheta}-\sup_{\eta\in{\mathcal T}_{\Delta}^\Xi}J_2(\zeta_{\vartheta}/N,\eta/N)
\end{equation}
where for any $\zeta\in{\mathcal T}_{01}^{\Xi,N}$ and $\eta\in{\mathcal T}_{{\Delta}}^\Xi$,
\[
J_2(\zeta/N,\eta/N)=E(R^\Xi(\zeta^{\Delta}/N,\eta/N)-R^\Xi(\zeta/N,\eta/N)).
\]

As in (\ref{5.5}) we obtain from (\ref{2.10}) and (\ref{5.3}) that
\begin{eqnarray}\label{5.15}
&R^\Xi(\zeta^{\Delta}/N,\eta/N)-R^\Xi(\zeta/N,\eta/N)\leq K\big({\Delta}(N)\\
&+\max_{0\leq k\leq k_{\max}}\sup_{n_k/N\leq s\leq n_{k+1}/N}|\Xi(n_{k+1}/N)-\Xi(s)|\big)\nonumber\\
&\times\exp(K\sup_{0\leq t\leq 1}|\Xi(t)|).\nonumber
\end{eqnarray}
By the Cauchy-Schwarz inequality,
\begin{eqnarray}\label{5.16}
&|E(R^\Xi(\zeta^{\Delta}/N,\eta/N)-R^\Xi(\zeta/N,\eta/N))|\\
&\leq K{\Delta}(N)E\exp(K\sup_{0\leq t\leq 1}|\Xi(t)|)\nonumber\\
&+K\big(E\max_{0\leq k\leq k_{\max}}\sup_{n_k/N\leq s\leq n_{k+1}/N}|\Xi(n_{k+1}/N)-\Xi(s)|^2\big)^{1/2}
\nonumber\\
&\times(E\exp(2K\sup_{0\leq t\leq 1}|\Xi(t)|))^{1/2}.\nonumber
\end{eqnarray}

Next, we write
\begin{eqnarray}\label{5.17}
&\big(E\max_{1\leq k\leq k_{\max}}\sup_{n_{k+1}/N\geq s\geq n_k/N}|\Xi(n_{k+1}/N)-\Xi(s)|^2\big)^{1/2}\\
&\leq(\sum_{1\leq k\leq k_{\max}}E\sup_{n_{k+1}/N\geq s\geq n_k/N}|\Xi(n_{k+1}/N)-\Xi(s)|^4)^{1/4}\nonumber
\end{eqnarray}
and
\begin{eqnarray}\label{5.18}
&E\sup_{n_{k+1}/N\geq s\geq n_k/N}|\Xi(n_{k+1}/N)-\Xi(s)|^4\\
&\leq 8E|\Xi(n_{k+1}/N)-\Xi(n_k/N)|^4+8E\sup_{n_{k+1}/N\geq s\geq n_k/N}|\Xi(s)-\Xi(n_{k}/N)|^4.\nonumber
\end{eqnarray}
By the standard moment estimates for stochastic integrals
\begin{eqnarray}\label{5.19}
&E|\Xi(n_{k+1}/N)-\Xi(n_k)/N|^4\leq 8E|\int_{n_k/N}^{n_{k+1}/N}{\sigma}(\Xi(u))dW_N(u)|^4\\
&+8E(\int_{n_k/N}^{n_{k+1}/N}b(\Xi(u))du)^4\leq 288{\Delta}(N)\int_{n_k/N}^{n_{k+1}/n}E|{\sigma}(\Xi(u))|^4du\nonumber\\
&+8L^4({\Delta}(N))^4\leq 8L^4({\Delta}(N))^2(36+({\Delta}(N))^2)\nonumber
\end{eqnarray}
and
\begin{eqnarray}\label{5.20}
&E\sup_{n_{k+1}/N\geq s\geq n_k/N}|\Xi(s)-\Xi(n_{k}/N)|^4\\
&\leq 8(4/3)^4E|\int_{n_k/N}^{n_{k+1}/N}{\sigma}(\Xi(u))dW_N(u)|^4\nonumber\\
&+8E(\int_{n_k/N}^{n_{k+1}/N}b(\Xi(u))du)^4\leq 8L^4({\Delta}(N))^2(36(4/3)^4+({\Delta}(N))^2).\nonumber
\end{eqnarray}

Combining (\ref{5.14})--(\ref{5.20}) together with Lemma \ref{lem5.0}(iii)we obtain the
required lower bound for $V^\Xi-V^\Xi_{\Delta}$
taking into account that ${\vartheta}>0$ is arbitrary. On the other hand, since the Dynkin game has a
value under our conditions (see, for instance, \cite{Ki20}, Section 6.2.2) we can write that
\[
V^\Xi=\sup_{\eta\in{\mathcal T}_{01}^{\Xi,N}}\inf_{\zeta\in{\mathcal T}_{01}^{\Xi,N}}ER^\Xi(\zeta/N,\eta/N)
\leq\inf_{\zeta\in{\mathcal T}_{{\Delta}}^{\Xi}}ER^\Xi(\zeta/N,\eta_{\vartheta}/N)+{\vartheta}
\]
for any ${\vartheta}>0$ and some $\eta_{\vartheta}\in{\mathcal T}_{01}^{\Xi,N}$. Introducing $\eta_{\vartheta}^{\Delta}$ and relying
on the same arguments as above we obtain the corresponding upper bound for $V^\Xi-V^\Xi_{\Delta}$ and
complete the proof of (\ref{5.12}).

Next, we obtain (\ref{5.13}) by (\ref{2.9}), Lemma \ref{lem4.3}, Lemma \ref{lem5.0}(iii), the
Chebyshev and the Cauchy-Schwarz inequalities,
\begin{eqnarray}\label{5.21}
&|V^\Xi_{\Delta}-\hat V^\Xi_{\Delta}|\leq\sup_{\zeta\in{\mathcal T}_{\Delta}^\Xi}\sup_{\eta\in{\mathcal T}_{\Delta}^\Xi}
E|R^\Xi(\zeta/N,\eta/N)-\hat R^\Xi(\zeta/N,\eta/N)|\\
&\leq K\big(E(\max_{0\leq k\leq k_{\max}}|\Xi(k/N)-\hat\Xi(k/N)|+{\mathbb I}_{\max_{0\leq k\leq k_{\max}}|\Xi(k/N)-\hat\Xi(k/N)|>1})^2\big)^{1/2}\nonumber\\
&\times\big(E\exp(4K\max_{0\leq k\leq k_{\max}}|\Xi(k/N)|\big)^{1/4}\big(E\exp(4K\max_{0\leq k\leq k_{\max}}|\hat \Xi(k/N)|\big)^{1/4}\nonumber\\
&\leq 2K\sqrt {D^\Xi_{4K}}\big(E\max_{0\leq k\leq k_{N}}|\Xi(k/N)-\hat\Xi(k/N)|^2+E|\Xi(1)-\Xi(k_N/N)|^2\big)^{1/2}\nonumber\\
&\leq (4\sqrt {2}+2L)Ke^{K|x|}\sqrt {D^\Xi_{4K}}\sqrt {{\Delta}(N)}\nonumber
\end{eqnarray}
completing the proof of the lemma.
\end{proof}

Next, we introduce the new process $\Psi_N$, first recursively at the times $N^{-1}n_k$ and then
extending it for all $t\in[0,T]$ in the piece-wise constant fashion. Namely, we set $\Psi_N(0)=x$ and
(with $n_0=0$),
\begin{eqnarray*}
&\Psi_N(N^{-1}n_{k+1})=\Psi_N(N^{-1}n_k)+{\sigma}(\Psi_N(N^{-1}n_{k}))(W_N(N^{-1}n_{k+1})-W_N(N^{-1}n_k))\\
&+N^{-1}b(\Psi_N(N^{-1}n_{k}))(n_{k+1}-n_k)
\end{eqnarray*}
for $k=0,1,...,k_{\max}-1$. Set also $\Psi_N(t)=\Psi_N(N^{-1}n_k)$ if $N^{-1}n_k\leq t<N^{-1}n_{k+1}$.

\begin{lemma}\label{lem5.4} For any integer $N\geq 1$,
\begin{equation}\label{5.22}
E\max_{0\leq k\leq k_{\max}}|\Xi(N^{-1}n_k)-\Psi_N(N^{-1}n_k)|^2\leq 96{\Delta}(N)\exp(24L^2d).
\end{equation}
\end{lemma}
\begin{proof} We have
\begin{eqnarray*}
&|\Xi(N^{-1}n_k)-\Psi_N(N^{-1}n_k)|^2\leq 3\big(|\Xi(N^{-1}n_k)-\hat\Xi(N^{-1}n_k)|^2\\
&+\big\vert\sum_{0\leq l<k}({\sigma}(\Xi(N^{-1}n_{l}))-{\sigma}(\Psi_N(N^{-1}n_{l})))(W_N(N^{-1}n_{l+1})
-W_N(N^{-1}n_{l}))\big\vert^2\\
&+(N^{-1}\sum_{0\leq l<k}|b(\Xi(N^{-1}n_{l}))-b(\Psi_N(N^{-1}n_{l}))|(n_{l+1}-n_l))^2\big),
\end{eqnarray*}
and so
\begin{eqnarray}\label{5.23}
&\quad\quad\max_{0\leq k\leq n}|\Xi(N^{-1}n_k)-\Psi_N(N^{-1}n_k)|^2\\
&\leq 3\big(\max_{0\leq k\leq n}|\Xi(N^{-1}n_k)-\hat\Xi(N^{-1}n_k)|^2
+\max_{0\leq k\leq n}|M_k|^2\nonumber\\
&+4k_{\max}({\Delta}(N))^2\sum_{0\leq l<n}|b(\Xi(N^{-1}n_{l}))-
b(\Psi_N(N^{-1}n_{l}))|^2\nonumber
\end{eqnarray}
where
\[
M_k=\sum_{0\leq l<k}({\sigma}(\Xi(N^{-1}n_{l}))-{\sigma}(\Psi_N(N^{-1}n_{l})))(W_N(N^{-1}n_{l+1})
-W_N(N^{-1}n_{l}))
\]
is a martingale with respect to the filtration $\{ {\mathcal G}^\Xi_{n_k},\, k\geq 0\}$ since
 ${\sigma}(\Xi(N^{-1}n_{l}))-{\sigma}(\Psi_N(N^{-1}n_{l}))$ is ${\mathcal G}_{n_{l}}^\Xi$-measurable while
$W_N(N^{-1}n_{l+1})-W_N(N^{-1}n_{l})$ is independent of ${\mathcal G}_{n_l}^\Xi$.

Hence, by the Doob martingale moment inequality and by the Lipschitz continuity of ${\sigma}$ (with
the constant $L$),
\begin{equation}\label{5.24}
E\max_{0\leq k\leq n}|M_k|^2\leq 4E|M_n|^2\leq 4L^2dN^{-1}\sum_{0\leq k< n}Q_k(n_{k+1}-n_k)
\end{equation}
where
\[
Q_n=E\max_{0\leq k\leq n}|\Xi(N^{-1}n_k)-\Psi_N(N^{-1}n_k)|^2.
\]
By (\ref{5.23}), (\ref{5.24}) and Lemma \ref{lem4.3} we obtain that
\[
Q_n\leq 96{\Delta}(N)+24L^2d{\Delta}(N)\sum_{0\leq k<n}Q_k.
\]
Thus, by the discrete (time) Gronwall inequality (see \cite{Cla}),
\[
Q_n\leq 96{\Delta}(N)\exp(24L^2d{\Delta}(N)n)
\]
and since $n\leq k_{\max}$, (\ref{5.22}) follows.
\end{proof}

Next, we introduce the values of Dynkin games with payoffs based on the process $\Psi_N$. Namely,
we set
\[
R^\Psi_N(s,t)=G_s(\Psi_N){\mathbb I}_{s<t}+F_t(\Psi_N){\mathbb I}_{t\leq s},
\]
 \[
 V^\Psi_{\Delta}=\inf_{\zeta\in{\mathcal T}^\Xi_{\Delta}}\sup_{\eta\in{\mathcal T}^\Xi_{\Delta}}ER^\Psi_N(N^{-1}\zeta,N^{-1}\eta)
 \]
 \[
\mbox{and}\,\, V^\Psi_{\mathcal Q}=\inf_{\zeta\in{\mathcal T}^{\mathcal Q}}\sup_{\eta\in{\mathcal T}^{\mathcal Q}}
ER^\Psi_N(N^{-1}\zeta,N^{-1}\eta).
 \]
\begin{lemma}\label{lem5.5} For any ${\varepsilon}>0$,
\begin{equation}\label{5.25}
V^\Psi_{\Delta}=V^\Psi_{\mathcal Q}.
\end{equation}
\end{lemma}
\begin{proof}
As in Lemma \ref{lem5.2} we will prove (\ref{5.25}) obtaining both $V_{\Delta}^\Psi$ and $V^\Psi_{\mathcal Q}$ by
the dynamical programming procedure. Again, we have $V^\Psi_{\Delta}=V^\Psi_{{\Delta},0}$ and   $V^\Psi_{\mathcal Q}=
V^\Psi_{{\mathcal Q},0}$ where $V^\Psi_{{\Delta},k_{\max}}=F_T(\Psi_N)=V^\Psi_{{\mathcal Q},k_{\max}}$ and for
$k=k_{\max}-1, k_{\max}-2,...,0$,
\[
V^\Psi_{{\Delta},k}=\min\big(G_{N^{-1}n_k}(\Psi_N),\,\max(F_{N^{-1}n_k}(\Psi_N),\, E(V^\Psi_{{\Delta},k+1}|
{\mathcal G}_{n_k}^\Xi))\big)
\]
and
\[
V^\Psi_{{\mathcal Q},k}=\min\big(G_{N^{-1}n_k}(\Psi_N),\,\max(F_{N^{-1}n_k}(\Psi_N),\, E(V^\Psi_{{\mathcal Q},k+1}|
{\mathcal Q}_{n_k}))\big).
\]

For any vectors $x_0,x_1,x_2,...,x_{k_{\max}}\in{\mathbb R}^d$ set $x(0)=x_0$, $x(t)=x_k$ if $N^{-1}n_k\leq t
<N^{-1}n_{k+1}$ and define the functions
\[
q_{k_N(t)}(x_1,...,x_{k_N(t)})=F_t(x)\,\,\mbox{and}\,\,
r_{k_N(t)}(x_1,...,x_{k_N(t)})=G_t(x).
\]
Introduce
\[
\Phi_l(x_1,...,x_l)=\min\big(r_l(x_1,...,x_l),\,\max(q_l(x_1,...,x_l),\, h(x_1,...,x_l))\big)
\]
where
\[
h(x_1,...,x_l)=E\Phi_{l+1}\big(x_1,...,x_l,\, x_l+{\sigma}(x_{l})(W_N(N^{-1}n_{l+1})-W_N(N^{-1}n_l))\big).
\]
Since $\Psi_N(N^{-1}n_l)$ is both ${\mathcal G}_{n_l}$ and ${\mathcal Q}_{n_l}$-measurable while
$W_N(N^{-1}n_{l+1})-W_N(N^{-1}n_l)$ is idependent of both ${\mathcal G}_{n_l}$ and ${\mathcal Q}_{n_l}$ we see by
induction that
\[
V^\Psi_{{\mathcal Q},l}=\Phi_l(\Psi_N(N^{-1}n_1),\Psi_N(N^{-1}n_2),...,\Psi_N(N^{-1}n_l))=V^\Psi_{{\Delta},l},
\]
for all $l=k_{\max},k_{\max}-1,...,0$ where $\Phi_0=\min(F_0(x_0),\max(G_0(x_0),E\Phi_1(x_0+
{\sigma}(x_0)W_N(N^{-1}n_1)))$,
and (\ref{5.25}) follows.
\end{proof}

Now we can complete the proof of Theorem \ref{thm2.2} writing first,
\begin{eqnarray}\label{5.26}
&|V^\Xi-V_N|\leq |V_N-V_N^{\Delta}|+|V_N^{\Delta}-\hat V_N^{\mathcal Q}|+|\hat V_N^{\mathcal Q}-V^\Psi_{\mathcal Q}|\\
&+|V^\Psi_{\mathcal Q}-\hat V^\Xi_{\Delta}|+|\hat V^\Xi_{\Delta}-V^\Xi_{\Delta}| +|V^\Xi_{\Delta}-V^\Xi|.\nonumber
\end{eqnarray}
 It remains to estimate $|\hat V_N^{\mathcal Q}-V^\Psi_{\mathcal Q}|$ and $|V^\Psi_{\mathcal Q}-\hat V^\Xi_{\Delta}|=|V^\Psi_{\Delta}-\hat V^\Xi_{\Delta}|$ since all other terms in the right hand side of (\ref{5.26}) are dealt with by Lemmas
 \ref{lem5.1}--\ref{lem5.3}. In both remaining estimates we use the fact that the game values there are
 defined with respect to the same sets of stopping times which will allow us to rely on uniform bounds
 on distances between the corresponding processes. By (\ref{2.9}) and the Cauchy-Schwarz inequality,
 \begin{eqnarray}\label{5.27}
 &\quad|\hat V_N^{\mathcal Q}-V^\Psi_{\mathcal Q}|\leq\sup_{\zeta\in{\mathcal T}^{{\mathcal Q}}}\sup_{\eta\in{\mathcal T}^{{\mathcal Q}}}E|\hat R(N^{-1}\zeta,N^{-1}\eta)- R^\Psi_N(N^{-1}\zeta,N^{-1}\eta)|\\
 &\leq\max(E\sup_{0\leq t\leq 1}|F_t(\hat X_N)-F_t(\Psi_N)|,\,
 E\sup_{0\leq t\leq 1}|G_t(\hat X_N)-F_t(\Psi_N)|)\nonumber\\
 &\leq \sqrt 2K(E\max_{0\leq k\leq k_{\max}}|\hat X_N(N^{-1}n_k)-\Psi_N(N^{-1}n_k)|^2\nonumber\\
 &+P\{\max_{0\leq k\leq k_{\max}}|\hat X_N(N^{-1}n_k)-\Psi_N(N^{-1}n_k)|>1\}\big)^{1/2}\nonumber\\
 &\times\big(E\exp(2K(\max_{0\leq k\leq k_{\max}}(|\hat X_N(N^{-1}n_k)|+
 |\Psi_N(N^{-1}n_k)|)))\big)^{1/2}.\nonumber
 \end{eqnarray}
 Next, by Lemmas \ref{lem3.1}, \ref{lem5.4} and Theorem \ref{thm2.1},
  \begin{eqnarray}\label{5.28}
&E\max_{0\leq k\leq k_{\max}}|\hat X_N(N^{-1}n_k)-\Psi_N(N^{-1}n_k)|^2\\
&\leq  3E\max_{0\leq k\leq k_{\max}}|\hat X_N(N^{-1}n_k)-X_N(N^{-1}n_k)|^2\nonumber\\
&+3E\max_{0\leq k\leq k_{\max}}|X_N(N^{-1}n_k)-\Xi(N^{-1}n_k)|^2\nonumber\\
&+3E\max_{0\leq k\leq k_{\max}}|\Xi(N^{-1}n_k)-\Psi_N(N^{-1}n_k)|^2\nonumber\\
&\leq 408L^8N^{-1/2}+3C_0[N^{\frac 14}]^{-\frac 1{50d}}+96\exp(24L^2d)
{\Delta}(N). \nonumber
\end{eqnarray}
In view of the Chebyshev inequality the probability in (\ref{5.27}) is also estimated by
the right hand side of (\ref{5.28}).

Similarly, by (\ref{2.9}) and by Lemmas \ref{lem4.3}, \ref{lem5.0} and \ref{lem5.4},
\begin{eqnarray}\label{5.29}
&|V^\Psi_{\Delta}-\hat V^\Xi_{\Delta}|\leq\sup_{\zeta\in{\mathcal T}^{{\Delta}}}\sup_{\eta\in{\mathcal T}^{{\Delta}}}E|R^\Psi_N(N^{-1}\zeta,N^{-1}\eta)\\
&- \hat R^\Xi(N^{-1}\zeta,N^{-1}\eta)|\leq 2K \big(E\max_{0\leq k\leq k_{\max}}|\Psi_N(N^{-1}n_k)
-\hat\Xi(N^{-1}n_k)|^2\big)^{1/2}\nonumber\\
&\times\big(E\exp(2K(\max_{0\leq k\leq k_{\max}}(|\Psi_N(N^{-1}n_k)|+
|\hat\Xi(N^{-1}n_k)|)))\big)^{1/2}\nonumber\\
&\leq 2\sqrt 2K\big (E\max_{0\leq k\leq k_{\max}}|\Psi_N(N^{-1}n_k)-\Xi(N^{-1}n_k)|^2\nonumber\\
&+E\max_{0\leq k\leq k_{\max}}|\Xi(N^{-1}n_k)-\hat\Xi(N^{-1}n_k)|^2\big)^{1/2}(D^\Xi_{4K})^{1/2}
\nonumber\\
&\leq 16K\sqrt {{\Delta}(N)}(1+3\exp(24L^2d))^{1/2}(D^\Xi_{4K})^{1/2}.\nonumber
\end{eqnarray}
Combining (\ref{5.26}) together with (\ref{5.27})--(\ref{5.29}) and Lemmas \ref{lem5.0}--\ref{lem5.3}
we complete the proof of Theorem \ref{thm2.2}.
\qed


\section{Introduction}
Due to the success achieved in recent years by Deep Reinforcement Learning \cite{origDQNpaper} \cite{A_Brief_Survey}, Industrial applications are becoming increasingly tangible \cite{sutton2018}. Research is being conducted on 3D map reconstruction for autonomous cars where DRL can be one of the solutions \cite{zimmermann2017learning} and also in the field of AUVs \cite{barratt2017active} as well as many other applications that interact with the real world. Once DRL algorithms are implemented on physical systems and interact with the real world, these systems can be dangerous for themselves and humans. For this reason, debugging tools are needed to understand why the agent behaves that way and whether the agent is making the right decision for the correct reason and not making a right decision for the wrong reason \cite{visNN}.

Deep reinforcement learning algorithms are nowadays interpreted and measured by the rewards the agents can get. For this reason these agents are called black box algorithms and are criticized. This makes them difficult to use in critical real-world applications.

This paper reveals that visualization techniques are a powerful debugging tool, that provides much more information than interpreting rewards. With the help of Guided Backpropagation it is even possible to locate the error in a certain layer or stream in a neural network. Moreover it is shown that Grad-Cam methods can deliver results very early in training in case of very badly trained networks. This is a big advantage especially for off-policy algorithms that take a long time to explore at the beginning of the learning process. With off-policy algorithms it can take a few days until the rewards start to increase so that the developer can determine if the neural network is learning at all \cite{Sutton_policyGradiens}.

\textbf{Contributions.} For DRL, the claim made by Adebayo et al. \cite{sanityChecks}, that Guided Backpropagation does not visualize the desired regions, but through partial input recovery it works as a kind of edge detector, is shown not to be accurate.
Also, the claim that gradient methods can be difficult to interpret, because, when answering the question "What perturbation to the input increases a particular output?", gradient methods can choose perturbations which lack physical meaning \cite{visualAtari}, is shown not always to be an issue.

Furthermore two new visualization techniques were developed, one of which provides particularly good results. These were compared and analysed with 4 other popular visualization techniques.  Their advantages and disadvantages are discussed and different fields of application for the respective visualizations are suggested.

\section{Related Work}
In this section, previous work is presented and discussed.
As already mentioned, there is currently not a lot of work dealing with the topic of visualization in the area of deep reinforcement learning algorithms. First two works from the field of deep reinforcement learning  are presented and then and then  visualization techniques from the field of image processing.

\textbf{Semi Aggregated Markov Decision Processes.}
The authors which introduced Semi Aggregated Markov Decision Processes \cite{t-SNE} used the Atari 2600 environments as interpretable testbeds, they developed a method of approximating the behavior of deep RL policies via Semi Aggregated Markov Decision Processes (SAMDPs). They used the more interpretable SAMDPs to gain insights about the higher-level temporal structure of the policy. From a user perspective, an issue with the explanations is that they emphasize t-SNE clusters and state-action statistics which are uninformative to those without a machine learning background.

\textbf{Perturbation-based saliency methods.}
Another recently published work shows Perturbation-based saliency methods for the visualization of learned policies by Greydanus et al. \cite{visualAtari}. Their approach is to answer the question, "How much does removing information from the region around location change the policy?". The authors defined a saliency metric for image location as:
\begin{equation}
\mathcal { S } _ { \pi } ( t , i , j ) = \frac { 1 } { 2 } \left\| \pi _ { u } \left( I _ { 1 : t } \right) - \pi _ { u } \left( I _ { 1 : t } ^ { \prime } \right) \right\| ^ { 2 }
\end{equation}
The difference $\pi _ { u } \left( I _ { 1 : t } \right) - \pi _ { u } \left( I _ { 1 : t } ^ { \prime } \right)$ can be interpreted as a finite differences approximation of the directional gradient $\nabla _ { \hat { v } } \pi _ { u } \left( I _ { 1 : t } \right)$ where the directional unit vector $ \hat { v }$ denotes the gradient in the direction of $I _ { 1 : t } ^ { \prime }$.

In other words, is looking at how important were these pixels for the policy. By checking how strong the policy changes after removing some informations from the image. They use the same approach to construct Saliency Maps for the value estimate $V ^ { \pi }$ too. Greydanus et al. \cite{visualAtari} claims that gradient-based saliency methods do not yield well interpretable results. When answering the question "What perturbation to the input increases a particular output?", gradient methods can choose perturbations which lack physical meaning.

\textbf{Gradients.} The basic idea of backpropagation-based visualizations is to highlight relevant pixels by propagating the network
output back to the input image space. The intensity changes of these pixels which have the most significant impact on network decisions. Despite its simplicity, the results of saliency map are normally very noisy which makes the interpretation difficult. \cite{visBackprop}.

\textbf{Guided Backpropagation.} The idea behind guided backpropagation is that neurons act like detectors of particular image features. It is interesting in what image features the neuron detects and not in what kind of features it doesn't detect. That means when propagating the gradient, the ReLu function set all the negative gradients to zero. \cite{visBackprop} With other ways we only backpropagate positive error signals and we also restrict to only positive inputs.

\textbf{Gradient-weighted Class Activation Mapping.}
\label{sec:g_cam_meth}
One of the problems when it comes to using CAM is that a modern neural network not only consists of convolution layers but of different layers such as LSTM, MaxPooling, etc. GradCAM is an extension of CAM and it is broadly applicable to any CNN-based architectures.
In order to obtain the class-discriminative localization map Grad-CAM $L_{\mathrm{Grad}-\mathrm{CAM}}^{c} \in \mathbb{R}^{u \times v}$ of width $u$ and height $v$ for any class $c$. First, the gradients $y^c$ of class $c$ are calculated up to the desired convolution feature map activations $A_k$. An average pooling over the width and height dimensions is then carried out \cite{gradCam}.
\begin{equation}
\alpha_{k}^{c}=\overbrace{\frac{1}{Z} \sum_{i} \sum_{j}}^{\text {global average pooling }} \underbrace{\frac{\partial y^{c}}{\partial A_{i j}^{k}}}_{\text {gradients via backprop }}
\end{equation}
Weight $\alpha^c_k$ represents a partial linearization of the deep network downstream from $A$, and captures the
"importance" of feature map $k$ for a target class $c$. On the end it  performs a weighted combination of forward activation maps with a ReLU fuction. \cite{gradCam}
\begin{equation}
L_{\mathrm{Grad}-\mathrm{CAM}}^{c}=\operatorname{Re} L U\underbrace{\left(\sum_{k} \alpha_{k}^{c} A^{k}\right)}_{\text {linear combination }}
\end{equation}
The result is a heatmap of the same size as the convolutional feature map. This feature map must then be
enlarged to the size of the original image and place it over the image to get the final result.\\
If Grad-Cam is multiplied by Guided Backpropagation with the Hadamard product we get Guided Grad-Cam \cite{gradCam}.

\textbf{Gradient Methods.} Adebayo et al. \cite{sanityChecks} deals with the informative value of visualization techniques. In this work, various visualization techniques were compared and checked whether the techniques actually depend on the model, the training data or whether it partially reconstructs the image. In other words, their work claims that Guided Backpropagation and Guided GradCam act like an edge detector, which means that they show the desired positions without showing the learned model.

In their work they randomize the weights of a model starting from the top layer, successively, all the way to the bottom layer. This procedure destroys the learned weights from the top layers to the bottom ones. Their results indicate that Guided backpropagation and Guided GradCam do not visualize the learned model, but instead partially
reconstruct the image. They interpret their findings through an analogy with edge detection in images, a technique that requires neither training data nor model.\\

\textbf{Laplacian Operator in Image Processing}. To understand one of the results we will derive the kernel of the Laplacian filter which is used for edge detection. One approach for the design of directionally invariant high-pass filters for image processing (also called edge detectors) is to use second-order derivation operators, e.g. the Laplace operator \cite{laplacian}.
For continuous functions, the Laplace operator is defined by:
\begin{equation}\mathbf{L}=\frac{\partial^{2} I[x, y]}{\partial x^{2}}+\frac{\partial^{2} I[x, y]}{\partial y^{2}}
\end{equation}
We approximate the partial derivatives by difference equations and thus obtain :
\begin{equation}\frac{\mathrm{d}^{2} \mathrm{I}[\mathrm{x}, \mathrm{y}]}{\mathrm{d} \mathrm{x}^{2}}=\{\mathrm{I}[\mathrm{x}+\Delta \mathrm{x}, \mathrm{y}]-2 \mathrm{I}[\mathrm{x}, \mathrm{y}]+\mathbf{I}[\mathrm{x}-\Delta \mathrm{x}, \mathrm{y}]\} / \Delta \mathrm{x}^{2}
\end{equation}
\begin{equation}\frac{\mathrm{d}^{2} \mathrm{I}[\mathrm{x}, \mathrm{y}]}{\mathrm{d} \mathrm{y}^{2}} \approx\{\mathrm{I}[\mathrm{x}, \mathrm{y}+\Delta \mathrm{y}]-2 \mathrm{I}[\mathrm{x}, \mathrm{y}]+\mathrm{I}[\mathrm{x}, \mathrm{y}-\Delta \mathrm{y}]\} / \Delta \mathrm{y}^{2}
\end{equation}
Thus with $\Delta x, \Delta y=1$ (except for the sign) the mask for the Laplace operator is :
\begin{equation}\mathbf{L}_{1}=\left[\begin{array}{rrr}
0 & -1 & 0 \\
-1 & 4 & -1 \\
0 & -1 & 0\end{array}\right]
\label{L1}
\end{equation}
Numerous other approximations of the Lapace operator are possible. Examples are
the following masks (their transfer functions have the form known from the Gaussian and binomial distributions)\cite{laplacian}
\begin{equation}\mathbf{L}_{2}=\left[\begin{array}{ccc}
0 & -1 & -1 \\
-1 & 8 & -1 \\
-1 & -1 & 0
\end{array}\right] \quad \mathbf{L}_{3}=\left[\begin{array}{ccc}
1 & -2 & 1 \\
-2 & 4 & -2 \\
1 & -2 & 1
\end{array}\right] \quad \mathbf{L}_{4}=\left[\begin{array}{ccc}
-1 & -2 & -1 \\
-2 & 12 & -2 \\
-1 & -2 & -1
\end{array}\right]
\label{L3}
\end{equation}

\section{Experimental Setup}

Experiments were performed in two different environments a simple (Breakout-v0) and a complex one (Seaquest-v0) from OpenAI Gym \cite{brockman2016openai}. Four different agents were implemented. DDDQN (4 frames as input) \cite{sewak2019deep}, Splitted Attention DDDRQN (with LSTM), and two on Policy gradient algorithms A3C (3 frames as input) \cite{a3cOrigin} and an A3C Agent with LSTM.

The Splitted Attention DDDRQN was by far the best trained agent and receives most of the points (Seaquest-v0 9521 Points) that is why most of the results are referring to this agent \cite{attention}.

In order to better examine the visualization methods and to enable better interpretation, the original frames of the games are placed over the gradients with a $50\%$ opacity. In this way it is possible to assign the gradients to the features and to better interpret the results.

With the off policy algorithms not only the output is visualized but also the Q-value and the Advantage stream. To proof the results of Ziyu Wang et al. \cite{dueling}. In order to maintain comparability between the visualization techniques, the same state was always visualized in this work. This also applies to the visualization of the actor and critic agents, as well as the visualization of the value and advantage streams.
Two new visualization techniques have been developed and the following visualization methods have been implemented. Some features of the implementation are discussed below.

\textbf{Gradient and Guided Backpropagation.}
Compared to image processing, where the gradients of the guided backpropagation or gradient method are normalized over the image, the gradients in a video can also be normalized over the entire video.
For this reason, both have been implemented and tested. First, the gradients output were normalized for each state. Then the gradient and guided back propagation method around the whole video was normalized and tested.\\
In the visualizations, the gradients were checked in relation to different output layers. In particular, this work examines the advantage and the value stream in the off-policy algorithms in more detail, as well as the last layer that delivered the best results. In the actor critic methods both outputs of the NN were examined.

\textbf{Grad-Cam and Guided Grad-Cam.}
\label{sec:con_grad_cam}
With the Grad-Cam and Guided Grad-Cam method, the visualization can be applied to different convolutional layers. An example of what the differences look like is also shown. The best results were achieved on the first convolutional layer across all agents and across all environments. For this reason, the results of the Grad-Cam methods are usually applied to the first convolutional layer.\\\newline
\textbf{G1Grad-Cam and G2Grad-Cam.}
Two new visualization techniques were developed and will be presented in this work, which are also compared. Both visualization techniques are a further development of Grad-Cam and Guided Grad-Cam. The idea behind it is the same as for guided back propagation, that neurons act like detectors of particular image features. And we are interested in what image features the neuron detects and not in what kind of features it does not detect. That means when propagating the gradient, we set all the negative gradients to 0.
In the further course, Grad-Cam with the Guided Model is called G1Grad-Cam and GradCam with the Guided Model multiplied by Guided backpropagation is called G2Grad-Cam.\\

\section{Experimental Results}
Since a state usually contains several frames, the results of the gradient methods (unless other-wise stated) are related to the last frame in the sequence. With the Grad-Cam methods the results (unless otherwise stated) relate to the first convolutional layer. Furthermore, the word \emph{stable} is defined in the context of visualization techniques in this paper as follows: gradients or visual highlights that can be seen on most frames in a video. Gradients or visual highlights that can be seen on every 4th, 5th (or even less) frame in a video are called \emph{not stable}.

First we discuss the visualization techniques, then we look closer at the class discriminative visualization algorithms and finally we make a hypothesis about the importance of negative gradients in backpropagation algorithms. Detailed results are all provided in the appendix (Figures \ref{fig:dddqn_r_grad} to \ref{fig:a3cLSTM_c_grad_cam}).

\subsection{Visualization Algorithms}
\textbf{Gradient.}
Gradients method delivers a lot of noise which often mixed with the important features. It is only very poorly suited for debugging neural networks in the deep reinforcement learning area. We get similar results with the agent in all environments. This can be seen in Figures: \ref{fig:dddqn_r_grad}, \ref{fig:dddqn_s_grad_a}, \ref{fig:dddqn_s_grad_v}, \ref{fig:spatt_grad}, \ref{fig:spatt_grad_diver}, \ref{fig:back_swa}, and \ref{fig:break_a3c_crit_grad}.

\textbf{Guided Backpropagation.}
Guided backpropagation delivers the best and most stable results under all environments and among all agents.
Also, that it shows negative gradients is a very good indication of how well an agent is trained. It can be seen that the better the agent has been trained, the stronger the transition between negative and positive gradients.

Another interesting observation that guided back propagation (compared to the Grad-Cam methods) did not visualize the agent so well during the breakout game. Even in the DDDQN network, where the agent was well trained, only weak gradients could be recognized on the agent himself on Figures \ref{fig:dddqn_r_a} and \ref{fig:dddqn_r_guid_back}. In contrast, on Seaquest, which is a much more complex environment and the agent was not well trained, very strong gradients were displayed on the agent itself, as  Figures \ref{fig:dddqn_s_grad_a} and \ref{fig:dddqn_s_grad_v} show.

Another comparison that has been made in this work is how the visualization of the guided backpropagation algorithm changes with respect to normalization. In other words, how does the visualization change when the normalization of the gradients is carried out over a frame compared to when the normalization was created over the entire video.

The results showed that when the frame was normalized, the gradients in the video flashed more strongly. With normalization across the entire video, the transitions from the frames were smoother. In this way, the less known / visited states can be recognized because the gradients on which are weaker to recognize.
This method is also the most suitable for visualizing the differences between the advantage and the value stream in the off-policy algorithms. Guided back propagation was able to identify most of the features in any environment and these were also very stable across the video.

During the development of the split attention DDDQN agent, the guided back propagation method for debugging was also used. An interesting finding that was made during development was that although the neural network had several errors, results were still very good (over 3000-3500 points, similar results were achieved by the normal attention DDDRQN network). Only after the Advantage and Value Stream was visualized did it become apparent that the network only learned on the Advantage side and that the gradients on the value side were very strong but chaotic. Based on the points, the errors that were made during programming would not have been noticed. Altogether two errors could be discovered and they could even be localized in the value stream. One mistake was incorrectly linking the layer and another when merging the two streams.

When developing the A3C with LSTM network, guided back propagation was also used to debug the network. Before a working A3C with LSTM was developed in this work, attempts were first made to train the agent with bidirectional layers. This was unsuccessful. In the visualization, no gradients were displayed when the gradients from the output layer to the input layer were calculated (the output gradients during printing were also 0). Then the network with guided backpropagation was examined more precisely with this visualization technique, because in contrast to the Grad-Cam methods, the gradient methods calculate the gradients from each individual layer to the input, this means that the individual layers can be examined. It turned out that the agent started to learn in the first three layers and no longer from the bidirectional layers. When these layers were replaced by LSTMs, the agent immediately began to learn even in the higher layers.

\textbf{Grad-Cam.}
This method also showed stable results (based on the first convolutional layer), even if the results were often issued in inventory, especially with less well-trained agents, as seen in Figure \ref{fig:guided_grad325}.

Looking at the higher layers, some features could also be visualized, but here the visualization was inverted more often, as shown in Figure \ref{fig:grad_cam2_inverted}, and the specified position of the features in the visualization algorithm was less precise, shown in Figures \ref{fig:grad_cam2} and \ref{fig:grad_cam3}.\\
One advantage over the guided backpropagation method which is noticeable, is that with less well trained agents, the visualization (even if mostly often inventoried) was able to visualize the features faster and without interference. However the G1Grad-Cam could beat these results.

Grad-Cam was able to achieve better results in the Breakout environment (see Figure: \ref{fig:dddqn_r_grad_cam}), where the agent could be visualized relatively poorly with guided backpropagation. Another advantage of the grad cam method (at least for neural networks without LSTM) compared to guided backpropagation is that, as can be seen in Figure \ref{fig:dddqn_r_grad_cam}, the time flow can be visualized. Means how important the previous frames were.

Due to the negative gradients that exist in guided backpropagation, a superimposition or averaging of the gradients from all input frames would not provide a similar result, since the gradients would cancel each other out with guided backpropagation.

Since the Grad-Cam has a ReLU function, only positive results are displayed. However, this has the disadvantage that we cannot differentiate as well if an agent is well trained. The visualization differences are minimal as can be seen in the Actor Critic between Figures \ref{fig:a3c_act_grad_cam} and \ref{fig:a3c_crit_grad_cam} and different between the Splitted Attention DDDRQN (See Figure \ref{fig:spatt_grad_cam}) and the DDDQN Agent . However, the results with Grad-Cam are better  with poorly trained agents and have less disruption than with guided backpropagation. One reason for this could be that the grad-cam carried an average pooling across the height and width of the dimension are carried out. With average pooling, the tendencies could be displayed better and there would be fewer disturbances due to averaging. This could be the reason why by Grad-Cam by weakly trained networks achieve better results than with guided backpropagation.

A disadvantage compared to guided back propagation, which can be seen in all agents is that not all features can be visualized. By the breakout environment  the area of the image where the agent breaks through the last line and receives many points could be not visualized (see Figure \ref{fig:dddqn_r_guid_back} and Figure \ref{fig:dddqn_r_grad_cam}). In Seaquest, Grad-Cam was unable to visualize the oxygen bar, nor the divers collected.

\textbf{Guided Grad-Cam and G2Grad-Cam.}
The combination of guided back propagation and one of the Grad-Cam methods has proven to be very unstable. One reason is that not all features are displayed in the Grad-Cam method, as has already been mentioned. But the main reason is that the results are shown often inverted by the Grad-Cam method. Due to the inversion, the areas with the features have a value of 0, which means that the multiplication with the guided back propagation also results in 0.

Basically, with these two methods, no additional knowledge can be obtained that has already been obtained with guided back propagation or Grad-cam.

\textbf{G1Grad-Cam}
The G1Grad-cam method gave much better results for the DDDQN agent in the game breakout and also the time flow than with the Grad-Cam method, as shown in Figure \ref{fig:dddqn_r_g1grad_cam} (G1Grad-Cam) versus Figure \ref{fig:dddqn_r_grad_cam} (Grad-Cam). Interestingly, the G1Grad-Cam method has problems visualizing the features in game Seaquest.

The G1Grad-Cam method shows less inverted results than the Grad-Cam method. However, especially with less well-trained agents, the results are not stable or not exactly in position. Basically, the method only convinced the DDDQN agent in the game Breakout. Here G1grad-Cam was able to display the ball and the agent as well as their past positions very clearly than all other visualization techniques.

However, the upper breakthrough area could not be visualized as the guided back propagation method did.\\\newline
An interesting aspect of the poorly trained splitted attention agent is that in Seaquest the G1Grad-Cam method gives the best interpretable results over all visualization methods, as shown in Figure \ref{fig:g1grad_cam325} (in contrast to the well trained one, where it gives no results). The neural network was saved after 325 episodes (for comparison, the well-trained neural network was saved after 5300 episodes).  After 325 episodes the neural network has done about 250 000 steps and 75\% of them have chosen a random action (because of exploration). After this short period of time, the G1Grad-Cam method was able to deliver well interpretable results.

For comparison: After 1500 episodes it can be determined via the rewards that the neural network is learning. This means that with the G1Grad-Cam method it is possible to recognize up to 5 times faster if the neural network is learning at all. This makes it a helpful debugging tool.

\subsection{Action Discriminative Visualization Algorithms}
The fact that the agent has learned to recognize features does not mean that the agent has learned how to behave. The agent recognizes e.g. the oxygen bar and understand when it ends that the episode will end, but it has not learned what to do about it. It is similar with the fishes that the agent recognizes them but does not necessarily mean that the agent will avoid the fish or knows what to do with it. For this reason, action discriminative algorithms were examined more closely.

The investigations did not give any indication that Grad-Cam and G1Grad-Cam, which are action discriminative algorithms, have a visible visual relationship between the state and the action taken. The expectation that Grad-Cam would emphasize a particular fish because the agent would swim away from a fish or target a fish, could not be confirmed.

\subsection{Hypothesis about Negative Gradients in Guided Backpropagation and their Meaning}
Apparently negative gradients also play a role. With the DDDQN agent, the negative gradients were time-dependent. The newest frame has the most positive and the oldest most negative gradients and the negative gradients are always shown where the ball was or will be. One reason for this could be the different architecture of the neural network which only calculates the error of the selected action but not the error of the non-selected actions compared to the other developed CNN. With the other agents, it can be observed that the negative gradients did not form in a time-dependent but position-dependent manner. The strong negative gradients have formed around the features. It can also be seen that the stronger the positive and negative gradients, the better the agent.

\begin{wrapfigure}{r}{0.3\textwidth}
    \centering
    \vspace*{-1em}
    \includegraphics[width=0.3\textwidth]{pictures/results/laplace_operator.png}
    \caption{The agent is covered with positive gradients followed by negative and positve again.}
    \label{fig:lap}
\end{wrapfigure}

A possible explanation could be that with guided backpropagation the gradients resemble a matrix or the kernel of an edge detector. And the Laplacian Operator has strong positive and negative values in the matrix to detect edges. Backpropagation could create a matrix that has learned to better identify features with strong negative and positive values, just like with a Laplace operator. Figure \ref{fig:lap} shows that strong positive gradients are followed by strongly negative gradients and some small positve again (compare in Equations \ref{L1} and \ref{L3}, Equation $L_1$ and $L_3$). The Laplace operator has a similar structure. The difference is that the Laplace operator detects edges and not more complex features. Guided backpropagation would create a kind of Laplace matrix for features based on this hypothesis. This could be a possible explanation for the role of negative gradients.

\section{Conclusions and Future Work}

\textbf{Visualisation techniques}. First of all, the assumptions made in the paper "Visualizing and Understanding Atari Agents" \cite{visualAtari}, that guided backpropagation cannot be used for visualization techniques and the assertion made in the paper "Sanity Checks for Saliency Maps" \cite{sanityChecks}, that guided backpropagation and guided Grad-Cam (at least in image processing) do not visualize the learned model but work similarly to an edge detector do not seem apply to deep reinforcement learning policies.

Visualization methods are very well suited as an additional, if not main debugging tool. Especially Guided Backpropagation was used during the development of Splitted Attention DDDQN with bidirectional LSTM agents and the A3C with LSTM agent to detect various errors in the neural network. Not only can errors be detected but also an assignment could be made in which stream the error was located and which layer caused problems. This kind of debugging is not possible with the usual reward evaluation. Especially since the faulty neural network could achieve better results than the original one despite the errors it contains, these errors would not have been noticed.

Furthermore, it was also shown with two agents (Figure \ref{fig:a3c_crit_guid_back} and Figure \ref{fig:dddqn_s_guid_back_v}) that Guided backpropagation can be used to detect if the agent has learned to avoid an area. The agent obtained a high reward, but this is not the expected behavior. The agent has learned to stay in the water at a certain height. The agent always shoots to the left or to the right if something comes up there. This is an important insight because it means that if the environment changes the agent will probably not be able to cope with these changes as well as an agent that has a lower score, but swims specifically towards the fishes. Here a simple reward function could even lead to misinterpretations. Guided backpropagation could show the different strength of the gradients on the fish that swam at different heights, which could lead to the conclusion that the agent does not visit certain areas of the environment.

The Grad-Cam and especially the G1Grad-Cam method achieves very early results. This is useful during the training process of the neural network. For example, if an agent has to be trained for 14 days in a HPC cluster, G1Grad-Cam can quickly provide initial information after a few minutes / hours as to whether the agent recognizes any features at all or whether there are indications of errors in the neural network. The rewards that are currently used as the main debugging tool are hardly usable at the beginning, especially with off-policy algorithms. Because the agent is exploring at the beginning, the rewards are random, but the neural network learns to recognize the features even if it does not yet know what they mean or how the agent has to behave. This is a big time advantage over the Reward function that took 2 days with the Split Attention Agent to show the first signs that the Rewards are increasing.

The error does not necessarily have to be in the neural network, but also a faulty implementations can be detected in this way (during this work wrong stacking of the frames could be visualized on the neural network and the error could be corrected by the DDDQN agent).
The G1Grad-Cam and Grad-Cam method can save time when designing neural networks during debugging compared to a pure interpretation by the Reward function.

However, no evidence was found that using G1/Grad-Cam methods which are action discriminative methods, can visualize the difference in importance between the features, that has the biggest impact on the action (agent's decision). No feature was highlighted that is more important for the decision of an action.

Guided backpropagation was able to recognize most of the features. All features detected by the Grad-Cam methods and more. Even though the gradients are sometimes hardly visible and only after long training the DDDQN agent could visualize itself in the game Breakout.\\
This method is especially suitable to evaluate the agent at the end (Does the agent recognize all important features? Are there differences in intensity between the same features in different states? How strong are the gradients on the features?) or for debugging purposes. Guided backpropagation is better suited for debugging than the Grade-Cam method, because individual streams could be examined and individual layers. In this way the error can be identified more quickly under certain circumstances (as in the development of the Split Attention Agent).

\textbf{Negative gradients.} A hypothesis about possible explanation for the importance of negative gradients that forms around features were put forward in this work. The explanation was compared to a Laplacian filter which revealed the edges. However, edges were not revealed here, but entire features it was concluded that through backpropagation a kind of Laplacian kernel feature detector was visualized. Where the negative gradients would be produced by a second derivative to better detect the features.

\textbf{Future work}. After having shown in this work that visualization techniques are a basic important tool for debugging neural networks, there are still some important questions left.
First of all the features that are important for the agent could be visualized. What could not be shown in this paper is that in action discriminative methods, the features that have a greater importance for the selected action are more strongly emphasized. A possible reason for this could be that by averaging all feature maps of the Grad-Cam methods the differences between the normal features and the features that directly influenced the agent's decision were very small. Here, a special implementation of Guided backpropagation might help to better identify the differences, by reprogramming the Guided backpropagation to an action discriminative algorithm.  This would give a better understanding of the advantages shown in this work, that guided backpropagation can better evaluate the intensity of how well a neural network recognizes the feature. In combination with a modified action discriminative Guided backpropagation algorithm, it might be possible to get more meaningful results if it is possible to visualize the feature that had the greatest influence on the current action.\\

\clearpage
\bibliographystyle{plain}