# A Generalized Urn Model with
Multiple Drawing
and Random Addition

Aguech Rafik.
Departement of Mathematics
King Saoudian University
Erryadh K.S.A.
<EMAIL_ADDRESS>
Lasmar Nabil
Departement des Mathematiques
Institut Préparatoire aux
Etudes d’ingénieurs
Monastir, Tunisia
<EMAIL_ADDRESS>
Selmi Olfa
Département des Mathematiques
Faculté des Sciences de Monastir
Monastir, Tunisia
<EMAIL_ADDRESS>Aguech Rafik (Corresponding author) Departement of
Statistics and Operation research, King Saoud University, Riyadh, Riyadh
11692, K.S.A. E-mail<EMAIL_ADDRESS>de Mathématiques, Faculté
des Sciences de Monastir, Avenue de l’environnement 5019, Monastir, Tunisia.
E-mail<EMAIL_ADDRESS>Lasmar Nabil Département de Mathématiques,
Institut Préparatoire aux Études d’ingénieurs de Monastir, Avenue de
l’environnement 5019, Monastir, Tunisia. E-mail<EMAIL_ADDRESS>Selmi
Olfa Département de Mathématiques, Faculté des Sciences de Monastir, Avenue de
l’environnement 5019, Monastir, Tunisia. E-mail<EMAIL_ADDRESS>
# Unbalanced urn model with random addition

Aguech Rafik.
Departement of Mathematics
King Saoudian University
Erryadh K.S.A.
<EMAIL_ADDRESS>
Lasmar Nabil
Departement des Mathematiques
Institut Préparatoire aux
Etudes d’ingénieurs
Monastir, Tunisia
<EMAIL_ADDRESS>
Selmi Olfa
Département des Mathematiques
Faculté des Sciences de Monastir
Monastir, Tunisia
<EMAIL_ADDRESS>Aguech Rafik (Corresponding author) Departement of
Statistics and Operation research, King Saoud University, Riyadh, Riyadh
11692, K.S.A. E-mail<EMAIL_ADDRESS>de Mathématiques, Faculté
des Sciences de Monastir, Avenue de l’environnement 5019, Monastir, Tunisia.
E-mail<EMAIL_ADDRESS>Lasmar Nabil Département de Mathématiques,
Institut Préparatoire aux Études d’ingénieurs de Monastir, Avenue de
l’environnement 5019, Monastir, Tunisia. E-mail<EMAIL_ADDRESS>Selmi
Olfa Département de Mathématiques, Faculté des Sciences de Monastir, Avenue de
l’environnement 5019, Monastir, Tunisia. E-mail<EMAIL_ADDRESS>
###### Abstract

In this paper, we consider a multi-drawing urn model with random addition. At
each discrete time step, we draw a sample of $m$ balls. According to the
composition of the drawn colors, we return the balls together with a random
number of balls depending on two discrete random variables $X$ and $Y$ with
finite means and variances. Via the stochastic approximation algorithm, we
give limit theorems describing the asymptotic behavior of white balls.

Keywords: unbalanced urn, martingale, stochastic algorithm, central limit
theorem.

##  1 Introduction

The classical Pólya urn was introduced by Pólya and Eggenberger [2] describing
contagious diseases. The first model is as follows: An urn contains balls of
two colors at the start, white and black. At each step, one picks a ball
randomly and returns it to the urn with a ball of the same color.

Afterward this model was generalized and it has become a simple tool to
describe several models such finance, clinical trials (see [3], [8]), biology
(see [15]), computer sciences, internet (see [6],[18]), etc.
Recently, H. Mahmoud, M.R. Chen, C.Z Wei, M. kuba and H. Sulzbach [9, 10, 11,
12, 13, 14], have focused on the multidrawing urn. Instead of picking a ball,
one picks a sample of $m$ balls ($m\geq 1$), say $l$ white and $m-l$ black
balls. the pick is returned back to the urn together with $a_{m-l}$ white and
$b_{l}$ black balls, where $a_{l}$ and $b_{l},0\leq l\leq m$ are integers. At
first, they treated two particular cases when {$a_{m-l}=c\times
l\quad\text{and}\quad b_{m-l}=c\times(m-l)$} and when {$a_{m-l}=c\times(m-l)$
and $b_{m-l}=c\times l$}, where $c$ is a positive constant. By different
methods as martingales and moment methods, the authors described the
asymptotic behavior of the urn composition. When considering the general case
and in order to ensure the existence of a martingale, they supposed that
$W_{n}$, the number of white balls in the urn after $n$ draws, satisfies the
affinity condition i.e, there exists two deterministic sequences
$(\alpha_{n})$ and $(\beta_{n})$ such that, for all $n\geq 0$,
$\mathbb{E}[W_{n+1}|\mathcal{F}_{n}]=\alpha_{n}W_{n}+\beta_{n}$. Under this
condition, the authors focused on small and large index urns. Later, the
affinity condition was removed in the work of C. Mailler, N. Lasmer and S.
Olfa [1], they generalized this model and looked at the case of more than two
colors.

In the present paper, we deal with an unbalanced urn model, which was not been
sufficiently addressed in the literature. It was mainly dealt with in the
works of R. Aguech [16], S. Janson [19] and H. Renlund [4, 5]. In [16] and
[19], the authors dealt with model with a simple pick, whereas in [4, 5] the
author considered a model with two picks and, under some conditions, they
described the asymptotic behavior of the urn composition.

In this paper, we aim to give a generalization of a recent work [17]. We deal
with an unbalanced urn model with random addition. We consider an urn
containing two different colors white and blue. We suppose that the urn is non
empty at time 0. Let denote by $W_{n}$ (resp $B_{n}$) the number of white
balls (resp blue balls) and by $T_{n}$ the total number of balls in the urn at
time $n$. Let $(X_{n})_{n\geq 0}$ and $(Y_{n})_{n\geq 0}$ be strictly positive
sequences of independent identically distributed discrete random variables
with finite means and variances. The model we study is defined as follows: At
a discrete time, we pick out a sample of $m$ balls from the urn (we suppose
that $T_{0}=W_{0}+B_{0}\geq m$) and according to the composition of the
sample, we return the balls with $Q_{n}(\xi_{n},m-\xi_{n})^{t}$ balls, where
$Q_{n}$ is a $2\times 2$ matrix depending on the variables $X_{n}$ and $Y_{n}$
and $\xi_{n}$ is the number of white balls in the $n^{th}$ sample.

Let $(\mathcal{F}_{n})_{n\geq 0}$ be the $\sigma$-field generated by the first
$n$ draws. We summarize the evolution of the urn by the recurrence

$\begin{pmatrix}W_{n}\\\ B_{n}\\\
\end{pmatrix}\stackrel{{\scriptstyle\mathcal{D}}}{{=}}\begin{pmatrix}W_{n-1}\\\
B_{n-1}\\\ \end{pmatrix}+Q_{n}\begin{pmatrix}\xi_{n}\\\ m-\xi_{n}\\\
\end{pmatrix}.$ (1)

Note that, with these notations, we have

$\mathbb{P}[\xi_{n}=k|\mathcal{F}_{n-1}]=\displaystyle\frac{\binom{W_{n-1}}{k}\binom{B_{n-1}}{m-k}}{\binom{T_{n-1}}{m}}.$

The paper is organized as follows. In Section 2, we give the main results of
the paper. In the first paragraph of Section 3, we develop Theorem 1 [4] and
apply it to our urn model. The rest of this section is devoted to the prove
the theorems.

Notation: For a random variable $R$, we denote by $\mu_{R}=\mathbb{E}(R)$ and
$\sigma_{R}^{2}=\mathbb{V}ar(X)$. Note that $\mu_{X},\mu_{Y},\sigma^{2}_{X}$
and $\sigma^{2}_{Y}$ are finite.

##  2 Main Results

######  Theorem 1.

Consider the urn model evolving by the matrix $Q_{n}=\begin{pmatrix}0&X_{n}\\\
X_{n}&0\\\ \end{pmatrix}$. We have the following results:

  1. 1.

$T_{n}\stackrel{{\scriptstyle a.s}}{{=}}m\mu_{X}n+o(\sqrt{n}\
\ln(n)^{\delta}),$ (2) $W_{n}\stackrel{{\scriptstyle
a.s}}{{=}}\frac{m\mu_{X}}{2}n+o(\sqrt{n}\ \ln(n)^{\delta})\quad\text{and}\quad
B_{n}\stackrel{{\scriptstyle a.s}}{{=}}\frac{m\mu_{X}}{2}n+o(\sqrt{n}\
\ln(n)^{\delta});\quad\delta>\frac{1}{2}.$ (3)

  2. 2.

$\frac{W_{n}-\frac{1}{2}T_{n}}{\sqrt{n}}\stackrel{{\scriptstyle\mathcal{L}}}{{\longrightarrow}}\mathcal{N}\Big{(}0,\frac{m(\sigma_{X}^{2}+\mu_{X}^{2})}{12}\Big{)}.$
(4)

  3. 3.

$\frac{W_{n}-\mathbb{E}(W_{n})}{\sqrt{n}}\stackrel{{\scriptstyle\mathcal{L}}}{{\longrightarrow}}\mathcal{N}\Big{(}0,\frac{m(\sigma_{X}^{2}+\mu_{X}^{2})+m^{2}\sigma^{2}_{X}}{12}\Big{)}.$
(5)

######  Theorem 2.

Consider the urn model evolving by the matrix $Q_{n}=\begin{pmatrix}X_{n}&0\\\
0&X_{n}\\\ \end{pmatrix}$. There exists a positive random variable
$\tilde{W}_{\infty}$, such that

$T_{n}\stackrel{{\scriptstyle a.s}}{{=}}m\mu_{X}n+o(\sqrt{n}\
\ln(n)^{\delta}),\quad W_{n}\stackrel{{\scriptstyle
a.s}}{{=}}\tilde{W}_{\infty}n+o(n)\quad\mbox{and}\;\;B_{n}\stackrel{{\scriptstyle
a.s}}{{=}}(m\mu_{X}-\tilde{W}_{\infty})n+o(n).$ (6)

Remark: The random variable $\tilde{W}_{\infty}$ is absolutely continuous
whenever $X$ is bounded.

######  Theorem 3.

Consider the urn model evolving by the matrix $Q_{n}=\begin{pmatrix}0&X_{n}\\\
Y_{n}&0\\\ \end{pmatrix}.$ Let
$z:=\frac{\sqrt{\mu_{X}}}{{\sqrt{\mu_{X}}+\sqrt{\mu_{Y}}}}$, we have the
following results:

  1. 1.

$T_{n}\stackrel{{\scriptstyle a.s}}{{=}}m\sqrt{\mu_{X}}\sqrt{\mu_{Y}}\
n+o(n),$ (7) $W_{n}\stackrel{{\scriptstyle
a.s}}{{=}}m\sqrt{\mu_{X}}\sqrt{\mu_{Y}}\ z\ n+o(n)\quad\text{and}\quad
B_{n}\stackrel{{\scriptstyle a.s}}{{=}}m\sqrt{\mu_{X}}\sqrt{\mu_{Y}}(1-z)\
n+o(n).$ (8)

  2. 2.

$\frac{W_{n}-zT_{n}}{\sqrt{n}}\stackrel{{\scriptstyle\mathcal{L}}}{{\longrightarrow}}\mathcal{N}\Big{(}0,\frac{G(z)}{3}\Big{)},$
(9)

where,

$G(x)=\sum_{i=0}^{4}a_{i}x^{i},$

with

$\displaystyle a_{0}=m^{2}(\sigma^{2}_{X}+\mu_{X}^{2})$ , $\displaystyle
a_{1}=m(1-2m)(\sigma_{X}^{2}+\mu_{X}^{2}),$ $\displaystyle
a_{2}=3m(m-1)(\sigma_{X}^{2}+\mu_{X}^{2})-2m(m-1)\mu_{X}\mu_{Y}$ ,
$\displaystyle
a_{3}=m\mathbb{E}(X-Y)^{2}-2(m^{2}-m)\bigl{(}\sigma_{X}^{2}+\mu_{X}^{2}-\mu_{X}\mu_{Y}\bigr{)}$
$\displaystyle\text{and}\quad a_{4}=m(m-1)\mathbb{E}(X-Y)^{2}.$

######  Theorem 4.

Consider the urn evolving by the matrix $Q_{n}=\begin{pmatrix}X_{n}&0\\\
0&Y_{n}\\\ \end{pmatrix}.$ We have the following results:

  1. 1.

If $\mu_{X}>\mu_{Y}$,

$T_{n}\stackrel{{\scriptstyle a.s}}{{=}}m\mu_{X}n+o(n),\quad
W_{n}\stackrel{{\scriptstyle a.s}}{{=}}m\mu_{X}n+o(n)\quad\text{and}\quad
B_{n}\stackrel{{\scriptstyle a.s}}{{=}}B_{\infty}n^{\rho}+o(n^{\rho}),$ (10)

where $\rho=\frac{\mu_{Y}}{\mu_{X}}$ and $B_{\infty}$ is a positive random
variable.

  2. 2.

If $\mu_{X}=\mu_{Y}$,

$T_{n}\stackrel{{\scriptstyle a.s}}{{=}}m\mu_{X}n+o(n),\quad
W_{n}\stackrel{{\scriptstyle a.s}}{{=}}W_{\infty}n+o(n)\quad\text{and}\quad
B_{n}\stackrel{{\scriptstyle a.s}}{{=}}(\mu_{X}m-W_{\infty})\ n+o(n),$ (11)

where $W_{\infty}$ is a positive random variable.

Remark: The case when $\mu_{X}<\mu_{Y}$ is obtained by interchanging the
colors.
Example: Let $m=1$, this particular case was studied by R. Aguech [16]. Using
martingales and branching processes , R. Aguech proved the following results:
if $\mu_{X}>\mu_{Y}$,

$W_{n}=\mu_{X}n+o(n),\quad B_{n}=Dn^{\rho}\quad\text{and}\quad
T_{n}=\mu_{X}n+o(n),$

where $D$ is a positive random variable.
If $\mu_{X}=\mu_{Y}$,

$W_{n}=\mu_{X}\frac{W}{W+B}n+o(n)\quad\text{and}\quad
B_{n}=\mu_{X}\frac{B}{W+B}n+o(n),$

where $W$ and $B$ are positive random variables obtained by embedding some
martingales in continuous time.

##  3 Proofs

The stochastic algorithm approximation plays a crucial role in the proofs in
order to describe the asymptotic composition of the urn. As many versions of
the stochastic algorithm exist in the literature (see [Duflo] for example), we
adapt the version of H. Renlund in [4, 5].

###  3.1 A basic tool: Stochastic approximation

######  Definition 1.

A stochastic approximation algorithm $(U_{n})_{n\geq 0}$ is a stochastic
process taking values in $[0,1]$ and adapted to a filtration $\mathcal{F}_{n}$
that satisfies

$U_{n+1}-U_{n}=\gamma_{n+1}\big{(}f(U_{n})+\Delta M_{n+1}\big{)},$ (12)

where $(\gamma_{n})_{n\geq 1}$ and $(\Delta_{n})_{n\geq 1}$ are two
$\mathcal{F}_{n}$-measurable sequences of random variables, $f$ is a function
from $[0,1]$ onto $\mathbb{R}$ and the following conditions hold almost
surely.

(i)

$\frac{c_{l}}{n}\leq\gamma_{n}\leq\frac{c_{u}}{n}$,

(ii)

$|\Delta M_{n}|\leq K_{u},$

(iii)

$|f(U_{n})|\leq K_{f},$

(iv)

$\mathbb{E}[\gamma_{n+1}\Delta M_{n+1}|\mathcal{F}_{n}]\leq
K_{e}\gamma_{n}^{2},$

where the constants $c_{l},c_{u},K_{u},K_{f},$ and $K_{e}$ are positive real
numbers.

######  Definition 2.

Let $Q_{f}=\\{x;f(x)=0\\}.$ A zero $p\in Q_{f}$ will be called stable if there
exists a neighborhood $\mathcal{N}_{p}$ of $p$ such that $f(x)(x-p)<0$
whenever $x\in\mathcal{N}_{p}\setminus\\{p\\}.$ If $f$ is differentiable, then
$f^{\prime}(p)$ is sufficient to determine that $p$ is stable.

######  Theorem 5 ([4]).

Let $U_{n}$ bea stochastic algorithm defined in Equation (12). If $f$ is
continuous, then $\displaystyle\lim_{n\rightarrow+\infty}U_{n}$ exists almost
surely and is in $Q_{f}$. Furthermore, if $p$ is a stable zero, then
$\mathbb{P}\Big{(}U_{n}\longrightarrow p\Big{)}>0.$

Remark: The conclusion of Theorem 5 holds if we replace the condition $(ii)$
in Definition 1 by the following condition $\mathbb{E}[\Delta
M_{n+1}^{2}|\mathcal{F}_{n}]\leq K_{u}$.

###### Proof of Theorem 5.

For the convenience of the reader, we adapt the proof of Theorem 5 and we show
that, under the new condition $(ii)\quad\mathbb{E}[\Delta
M_{n+1}^{2}|\mathcal{F}_{n}]\leq K_{u}$, the conclusion remains true. In fact,
the following lemmas are useful.

######  Lemma 1.

Let $V_{n}=\sum_{i=1}^{n}\gamma_{i}\Delta M_{i}$. Then, $V_{n}$ converges
almost surely.

###### Proof.

Set $A_{i}=\gamma_{i}\Delta M_{i}$ and
$\tilde{A}_{i}=\mathbb{E}[A_{i}|\mathcal{F}_{i-1}].$ Define the martingale
$C_{n}=\sum_{i=1}^{n}(A_{i}-\tilde{A}_{i}),$ then

$\displaystyle\mathbb{E}(C_{n}^{2})$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{n}\mathbb{E}(A_{i}^{2})=\sum_{i=1}^{n}\mathbb{E}(\gamma_{i}^{2}\Delta
M_{i}^{2})$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{n}\frac{c_{u}^{2}}{i^{2}}\mathbb{E}(\Delta
M_{i}^{2}),$

if there exists some positive constant $K_{u}$ such that $\mathbb{E}[\Delta
M_{n+1}^{2}|\mathcal{F}_{n}]\leq K_{u}$, we conclude that $C_{n}$ is an
$L^{2}-$ martingale and thus converges almost surely.
Next, since

$\sum_{i\geq 1}|\tilde{A}_{i}|\leq\sum_{i\geq
1}\frac{c_{u}^{2}}{(i-1)^{2}}K_{l}<+\infty,$

the series $\sum_{i\geq 1}A_{i}$ must also converges almost surely. ∎

######  Lemma 2.

Let $U_{\infty}$ be the set of accumulation point of $\\{U_{n}\\}$ and
$Q_{f}=\\{x;f(x)=0\\}$ be the zeros of $f$. Suppose $f$ is continuous. Then,

$\mathbb{P}\Big{(}U_{\infty}\subseteq Q_{f}\Big{)}=1.$

###### Proof.

See [4] ∎

Next, we prove the main result of the theorem. If
$\displaystyle\lim_{n\rightarrow+\infty}U_{n}$ does not exist, we can find two
rational numbers in the open interval
$]\displaystyle\liminf_{n\rightarrow+\infty}U_{n},\displaystyle\limsup_{n\rightarrow+\infty}U_{n}[$.
Let $p<q$ be two arbitrary different rational numbers. If we can show that

$\mathbb{P}\Big{(}\\{\liminf U_{n}\leq p\\}\cap\\{\limsup U_{n}\geq
q\\}\Big{)}=0,$

then, the existence of the limit will be established and the claim of the
theorem follows from Lemma 2.
For this reason, we need to distinguish two different cases whether or not $p$
and $q$ are in the same connected component of $Q_{f}$.

Case 1: $p$ and $q$ are not in the same connected component of $Q_{f}$.
See the proof in [4].

Case 2: $p$ and $q$ are in the connected component of $Q_{f}$.
Let $p$ and $q$ be two arbitrary rational numbers such that $p$ and $q$ are in
the same connected component of $Q_{f}$. Assume that
$\displaystyle\liminf_{n\rightarrow+\infty}U_{n}\leq p$ and fix an arbitrary
$\varepsilon$ in such a way that $0\leq\varepsilon\leq q-p$.
We aim to show that $\displaystyle\limsup_{n\rightarrow+\infty}U_{n}\leq q$
i.e, it is sufficient to show that
$\displaystyle\limsup_{n\rightarrow+\infty}U_{n}\leq p+\varepsilon.$
In view of Lemma 1, we have $V_{n}=\sum_{i=1}^{n}\gamma_{i}\Delta M_{i}$
converges a.s, then, for a stochastic $N_{1}>0$, for $n,m>N_{1}$ we have
$|W_{n}-W_{m}|<\frac{\varepsilon}{4}$ and $\gamma_{n}\Delta
M_{n}\leq\frac{\varepsilon}{4}$.
Let $N=max(\frac{4K_{f}}{\varepsilon},N_{1})$. By assumption, there is some
stochastic $n>N$ such that $U_{n}-p<\frac{\varepsilon}{2}$.
Let

$\tau_{1}=\inf\\{k\geq n;U_{k}\geq
p\\}\quad\text{and}\quad\sigma_{1}=\inf\\{k>\tau_{1};U_{k}<p\\},$

and define, for $n\geq 1,$

$\tau_{n+1}=\inf\\{k>\sigma_{n};U_{k}\geq
p\\}\quad\sigma_{n+1}=\inf\\{k>\tau_{n};U_{k}<p\\}.$

Now, for all $k$ we have

$U_{\tau_{k}}=U_{\tau_{k}-1}+\gamma_{\tau_{k}-1}(f(U_{\tau_{k}-1})+\Delta
M_{\tau_{k}}).$

Recall that
$\gamma_{\tau_{k}-1}f(X_{\tau_{k}-1})\leq\frac{K_{f}}{\tau_{k}-1}\leq\frac{K_{f}}{n}$,
for $n\geq N\geq\frac{4K_{f}}{\varepsilon}$ we have
$\gamma_{\tau_{k}-1}f(X_{\tau_{k}-1})<\frac{\varepsilon}{4}$. It follows,

$\gamma_{\tau_{k}-1}(f(U_{\tau_{k}-1})+\Delta
M_{\tau_{k}})\leq\frac{K_{f}}{n}+\frac{\varepsilon}{4}\leq\frac{\varepsilon}{4}+\frac{\varepsilon}{4}=\frac{\varepsilon}{2}.$

Note that $f(x)=0$ when $x\in[p,q]$ ($p$ and $q$ are in $Q_{f}$). For $j$ such
that $\tau_{k}+j-1$ is a time before the exit time of the interval $[p,q]$, we
have

$U_{\tau_{k}+j}=X_{\tau_{k}}+W_{\tau_{k}+j}-W_{\tau_{k}}.$

As $|W_{\tau_{k}+j}-W_{\tau_{k}}|<\frac{\varepsilon}{4},$ we have
$U_{\tau_{k}+j}\leq p+\frac{\varepsilon}{2}+\frac{\varepsilon}{4}\leq
p+\varepsilon,$ the precess will never exceed $p+\varepsilon$ before
$\sigma_{k+1}$. We conclude that $\sup_{k\geq n}U_{k}\leq p+\varepsilon.$
To establish that the limit is to a stable point, we refer the reader to [4]
to see a detailed proof.

∎

######  Theorem 6 ([5]).

Let $(U_{n})_{n\geq 0}$ satisfying Equation (12) such that
$\displaystyle\lim_{n\to+\infty}U_{n}=U^{\star}$. Let
$\hat{\gamma}_{n}:=n\gamma_{n}\hat{f}(U_{n-1})$ where
$\hat{f}(x)=\frac{-f(x)}{x-U^{\star}}$. Assume that $\hat{\gamma}_{n}$
converges almost surely to some limit $\hat{\gamma}$. Then,

if $\hat{\gamma}>\frac{1}{2}$ and if $\mathbb{E}[(n\gamma_{n}\Delta
M_{n})^{2}|\mathcal{F}_{n-1}]\to\sigma^{2}>0$, then

$\sqrt{n}(U_{n}-U^{\star})\to\mathcal{N}\Big{(}0,\frac{\sigma^{2}}{2\hat{\gamma}-1}\Big{)}.$

###  3.2 Proof of the main results

###### Proof of Theorem 1.

Consider the urn model defined in Equation (1) with
$Q_{n}=\begin{pmatrix}0&X_{n}\\\ X_{n}&0\\\ \end{pmatrix}$. We have the
following recursions:

$W_{n+1}=W_{n}+X_{n+1}(m-\xi_{n+1})\quad\text{and}\quad
T_{n+1}=T_{n}+mX_{n+1}.$ (13)

Proof of claim 1

######  Lemma 3.

Let $Z_{n}=\frac{W_{n}}{T_{n}}$ be the proportion of white balls in the urn
after $n$ draws. Then, $Z_{n}$ satisfies the stochastic approximation
algorithm defined by (12) with $\gamma_{n}=\frac{1}{T_{n}}$,
$f(x)=\mu_{X}m(1-2x)$ and $\Delta M_{n+1}=X_{n+1}(m-\xi_{n+1}-mZ_{n})-\mu
m(1-Z_{n})$.

###### Proof.

We need to check the conditions of definition 1.

(i)

Recall that $T_{n}=T_{0}+m\sum_{i=1}^{n}X_{i}$, with $(X_{i})_{i\geq 1}$ are
iid random variables. It follows, by Rajechman strong law of large numbers,
that

$T_{n}\stackrel{{\scriptstyle a.s}}{{=}}\mu_{X}mn+o(\sqrt{n}\
\ln(n)^{\delta}),\quad\delta>\frac{1}{2},$ (14)

it follows that
$\frac{1}{(m\mu_{X}+1)n}\leq\frac{1}{T_{n}}\leq\frac{2}{m\mu_{X}n},$ then,
$c_{l}=\frac{1}{m\mu_{X}+1}$ and $c_{u}=\frac{2}{m\mu_{X}n},$

(ii)

$\mathbb{E}[\Delta
M_{n+1}^{2}|\mathcal{F}_{n}]\leq(6m^{2}+m)\mathbb{E}(X^{2})+9m^{2}\mu^{2}=K_{u},$

(iii)

$|f(Z_{n})|=m\mu_{X}|1-2Z_{n}|\leq 3m\mu_{X}=K_{f}$,

(iv)

$\mathbb{E}(\gamma_{n+1}\Delta
M_{n+1}|\mathcal{F}_{n})\leq\frac{1}{T_{n}}\mathbb{E}(\Delta
M_{n+1}|\mathcal{F}_{n})=0=K_{e}$.

∎

######  Proposition 1.

The proportion of white balls in the urn after $n$ draws, $Z_{n}$, converges
almost surely to $\frac{1}{2}$.

###### Proof of Proposition 1.

Since the process $Z_{n}$ satisfies the stochastic approximation algorithm
defined by Equation (12), we apply Theorem 5. As the function $f$ is
continuous we conclude that $Z_{n}$ converges almost surely to $\frac{1}{2}$:
the unique stable zero of the function $f$. ∎

We apply the previous results to the urn composition. As we can write
$\frac{W_{n}}{n}=\frac{W_{n}}{T_{n}}\frac{T_{n}}{n}$, we deduce from
Proposition 1 and Equation (14) that $\frac{W_{n}}{n}\stackrel{{\scriptstyle
a.s}}{{=}}\bigl{(}\frac{1}{2}+o(1)\bigr{)}\Big{(}\mu_{X}m+o\Bigl{(}\frac{\ln(n)^{\delta}}{\sqrt{n}}\Bigr{)}\Bigr{)},$
then this corollary follows:

######  Corollary 1.

The number of white balls in the urn after $n$ draws, $W_{n}$, satisfies for
$n$ large enough

$W_{n}\stackrel{{\scriptstyle a.s}}{{=}}\frac{\mu_{X}m}{2}n+o(\sqrt{n}\
\ln(n)^{\delta}),\quad\delta>\frac{1}{2}.$

Proof of claim 2 We aim to apply Theorem 6. For this reason, we need to find
this limits:

$\lim_{n\rightarrow\infty}\mathbb{E}[\bigl{(}\frac{n}{T_{n}}\bigr{)}^{2}\Delta
M_{n+1}^{2}|\mathcal{F}_{n}]\quad\text{and}\quad\lim_{n\rightarrow\infty}-\frac{n}{T_{n}}f^{\prime}(Z_{n}).$

We have

$\displaystyle\mathbb{E}[\Delta M_{n+1}^{2}|\mathcal{F}_{n}]$ $\displaystyle=$
$\displaystyle\mathbb{E}(X_{n+1}^{2})\mathbb{E}[(m-\xi_{n+1}-mZ_{n})^{2}|\mathcal{F}_{n}])+\mu^{2}\mathbb{E}[(m-2mZ_{n})^{2}|\mathcal{F}_{n}]$
$\displaystyle-2\mu_{X}^{2}\mathbb{E}[(m-\xi_{n+1}-mZ_{n})(m-2mZ_{n})|\mathcal{F}_{n}]$
$\displaystyle=$
$\displaystyle(\sigma_{X}^{2}+\mu_{X}^{2})\Big{[}m^{2}-4m^{2}Z_{n}+4m^{2}Z_{n}^{2}+mZ_{n}(1-Z_{n})\frac{T_{n}-m}{T_{n}-1}\Big{]}-\mu_{X}^{2}[m^{2}+4m^{2}Z_{n}^{2}-4m^{2}Z_{n}].$

As $n$ tends to infinity, we have $Z_{n}\stackrel{{\scriptstyle
a.s}}{{\longrightarrow}}\frac{1}{2}$ and
$\frac{T_{n}-m}{T_{n}-1}\stackrel{{\scriptstyle a.s}}{{\longrightarrow}}1$.
Then,

$\lim_{n\rightarrow\infty}\mathbb{E}[\Delta
M_{n+1}^{2}|\mathcal{F}_{n}]\stackrel{{\scriptstyle
a.s}}{{=}}(\sigma_{X}^{2}+\mu_{X}^{2})\frac{m}{4}\quad\text{and}\quad\lim_{n\rightarrow\infty}-\frac{n}{T_{n}}f^{\prime}(Z_{n})\stackrel{{\scriptstyle
a.s}}{{=}}2.$

According to Theorem 6, $\sqrt{n}(Z_{n}-\frac{1}{2})$ converges in
distribution to
$\mathcal{N}(0,\frac{\sigma_{X}^{2}+\mu_{X}^{2}}{12\mu_{X}^{2}m})$. Finally,
by writing
$\Big{(}\frac{W_{n}-\frac{1}{2}T_{n}}{\sqrt{n}}\Big{)}=\sqrt{n}(Z_{n}-\frac{1}{2})\frac{T_{n}}{n}$,
we conclude using Slutsky theorem.

Proof of claim 3 To prove this claim, we follow the proof of Lemma 3 and
Theorem 2 in [17]. Using the same methods, we show in a first step that the
variables $(X_{n}(m-\xi_{n}))_{n\geq 0}$ are $\alpha$-mixing variables with a
strong mixing coefficient
$\alpha(n)=o\Big{(}\frac{\ln(n)^{\delta}}{\sqrt{n}}\Big{)}$,
$\delta>\frac{1}{2}$. To conclude, we adapt the Bernstein method. Consider the
same notation as in Theorem 2 in [17], and define
$S_{n}=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\tilde{\xi}_{i}$ where
$\tilde{\xi}_{i}=X_{i}(m-\xi_{i})-\mu_{X}(m-\mathbb{E}(\xi_{i}))$. At first,
we need to estimate the variance of $W_{n}$.

######  Proposition 2.

The variance of $W_{n}$ satisfies

$\mathbb{V}ar(W_{n})=\frac{m(\sigma_{X}^{2}+\mu_{X}^{2})+m^{2}\sigma_{X}^{2}}{12}\
n+o(\sqrt{n}\ \ln(n)^{\delta}),\quad\delta>\frac{1}{2}.$ (15)

###### Proof of Proposition 2.

Recall that the number of white balls in the urn satisfies Equation (13), then

$\mathbb{V}ar(W_{n+1})=\mathbb{V}ar(W_{n})+\mathbb{V}ar(X_{n}(m-\xi_{n}))+2\
\mathbb{C}ov(W_{n-1},X_{n}(m-\xi_{n})).$

We have
$\mathbb{V}ar(X_{n}(m-\xi_{n}))=(\sigma_{X}^{2}+\mu_{X}^{2})\Big{(}\mathbb{V}ar(mZ_{n-1})+\mathbb{E}\Big{(}mZ_{n-1}(1-Z_{n-1})\frac{T_{n-1}-m}{T_{n-1}-1}\Big{)}\Big{)}+\sigma_{X}^{2}\mathbb{E}(m-\xi_{n})^{2}.$

Using Equation (14) and the fact that $Z_{n}\stackrel{{\scriptstyle
a.s}}{{\rightarrow}}\frac{1}{2}$, we obtain

$\displaystyle\mathbb{V}ar(W_{n+1})$ $\displaystyle=$
$\displaystyle\Big{(}1-\frac{2}{n}+o\Big{(}\frac{\ln(n)^{\delta}}{n^{\frac{3}{2}}}\Big{)}\Big{)}\mathbb{V}ar(W_{n})+\frac{m(\sigma_{X}^{2}+\mu_{X}^{2})+m^{2}\sigma_{X}^{2}}{4}+o\Big{(}\frac{\ln(n)^{\delta}}{\sqrt{n}}\Big{)}$
$\displaystyle=$ $\displaystyle a_{n}\mathbb{V}ar(W_{n})+b_{n},$

where
$a_{n}=\Bigl{(}1-\frac{2}{n}+o\Big{(}\frac{\ln(n)^{\delta}}{n^{\frac{3}{2}}}\Big{)}\Bigr{)}$
and
$b_{n}=\frac{m(\sigma_{X}^{2}+\mu_{X}^{2})+m^{2}\sigma_{X}^{2}}{4}+o\Big{(}\frac{\ln(n)^{\delta}}{\sqrt{n}}\Big{)}.$
Thus,

$\mathbb{V}ar(W_{n})=\Big{(}\prod_{k=1}^{n}a_{k}\Big{)}\Big{(}\mathbb{V}ar(W_{0})+\sum_{k=0}^{n-1}\frac{b_{k}}{\prod_{j=0}^{k}a_{j}}\Big{)}.$

There exists a constant $a$ such that

$\prod_{k=1}^{n}a_{k}=\displaystyle\frac{e^{a}}{n^{2}}\Big{(}1+o\Big{(}\frac{\ln(n)^{\delta}}{\sqrt{n}}\Big{)}\Big{)}$,
which leads to

$\mathbb{V}ar(W_{n})=\frac{m(\sigma_{X}^{2}+\mu_{X}^{2})+m^{2}\sigma_{X}^{2}}{12}n+o(\sqrt{n}\ln(n)^{\delta}),\quad\delta>\frac{1}{2}.$

∎

Recall that we follow the proof of Theorem 2 in [17], using Equation (15), we
conclude that

$\frac{W_{n}-\mathbb{E}(W_{n})}{\sqrt{n}}\stackrel{{\scriptstyle\mathcal{L}}}{{\longrightarrow}}\mathcal{N}\Bigl{(}0,\frac{m(\sigma_{X}^{2}+\mu_{X}^{2})+m^{2}\sigma_{X}^{2}}{12}\Bigr{)}.$
(16)

∎

###### Proof of Theorem 2.

Consider the urn model defined in (1) with $Q_{n}=\begin{pmatrix}X_{n}&0\\\
0&X_{n}\\\ \end{pmatrix}$. The following recurrences hold:

$W_{n+1}=W_{n}+X_{n+1}\xi_{n+1}\quad\text{and}\quad T_{n+1}=T_{n}+mX_{n+1}.$
(17)

As $T_{n}$ is a sum of iid random variables then $T_{n}$ satisfies the
following

$T_{n}\stackrel{{\scriptstyle
a.s}}{{=}}\frac{\mu_{X}m}{2}n+o(\sqrt{n}\ln(n)^{\delta}).$ (18)

The processes
$\tilde{M}_{n}=\prod_{k=1}^{n-1}\Big{(}\frac{T_{k}}{T_{k}+m\mu_{X}}\Big{)}W_{n}$
and
$\tilde{N}_{n}=\prod_{k=1}^{n-1}\Big{(}\frac{T_{k}}{T_{k}+m\mu_{X}}\Big{)}B_{n}$
are two $\mathcal{F}_{n}$ positive martingales. In view of (18), we have
$\prod_{k=1}^{n-1}\Big{(}\frac{T_{k}}{T_{k}+m\mu_{X}}\Big{)}\stackrel{{\scriptstyle
a.s}}{{=}}\displaystyle\frac{e^{\gamma}}{n}\Big{(}1+o\Big{(}\frac{\ln(n)^{\delta}}{\sqrt{n}}\Big{)}\Big{)}$
for a positive constant $\gamma$. Thus, there exists nonnegative random
variables $\tilde{W}_{\infty}$ and $\tilde{B}_{\infty}$ such that
$\tilde{W}_{\infty}+\tilde{B}_{\infty}\stackrel{{\scriptstyle
a.s}}{{=}}m\mu_{X}$ and

$\frac{W_{n}}{n}\stackrel{{\scriptstyle
a.s}}{{\longrightarrow}}\tilde{W}_{\infty},\quad\text{and}\quad\frac{B_{n}}{n}\stackrel{{\scriptstyle
a.s}}{{\longrightarrow}}\tilde{B}_{\infty}.$

Example:  In the original Pòlya urn model [2], when $m=1$ and $X=C$
(deterministic), the random variable $\tilde{W}_{\infty}/C$ has a
$Beta(\frac{B_{0}}{C},\frac{W_{0}}{C})$ distribution [7, 19]. Whereas, M.R.
Chen and M. Kuba [10] considered the case when $X=C$ (non random) and $m>1$.
They gave moments of all orders of $W_{n}$ and proved that
$\tilde{W}_{\infty}$ cannot be an ordinary $Beta$ distribution.

Remark: Suppose that the random variable $X$ has moments of all orders, let
$\>m_{k}=E(X^{k})$, for $k\geq 1$. We have, almost surely, $W_{n}\leq T_{n}$
then, by Minskowski inequality, we obtain
$\mathbb{E}(W_{n}^{2k})\leq(mn)^{2k}\mathbb{E}(X^{2k})$. Using Carleman’s
condition we conclude that, if $\sum_{k\geq
1}\mu_{2k}^{-\frac{1}{2k}}=\infty$, then the random variable
$\tilde{W}_{\infty}$ is determined by its moments. Unfortunately, till now we
still unable to give exact expressions of moments of all orders of $W_{n}$.
But, we can characterize the distribution of $\tilde{W}_{\infty}$ in the case
when the variable $X$ is bounded.

######  Lemma 4.

Assume that $X$ is a bounded random variable, then, for fixed $W_{0},B_{0}$
and $m$ the random variable $\tilde{W}_{\infty}$ is absolutely continuous.

The proof that $\tilde{W}_{\infty}$ is absolutely continuous is very close to
that of Theorem 4.2 in [11]. We give the main proposition to make the proof
clearer.

######  Proposition 3.

[11] Let $\Omega_{\ell}$ be a sequence of increasing events such that
$\mathbb{P}(\cup_{\ell\geq 0}\Omega_{\ell})=1$. If there exists nonnegative
Borel measurable function $\\{f_{\ell}\\}_{\ell\geq 1}$ such that
$\mathbb{P}\Big{(}\Omega_{\ell}\cap\tilde{W}_{\infty}^{-1}(B)\Big{)}=\int_{B}f_{\ell}(x)dx$
for all Borel sets B, then,
$f=\displaystyle\lim_{l\rightarrow+\infty}f_{\ell}$ exists almost everywhere
and $f$ is the density of $\tilde{W}_{\infty}$.

Let $(\Omega,\mathcal{F},\mathcal{P})$ be a probability space. Suppose that
there exists a constant $A$ such that, we have almost surely, $X\leq A$.

######  Lemma 5.

Define the events

$\Omega_{\ell}:=\\{W_{\ell}\geq mA\;\mbox{and}\;B_{\ell}\geq mA\\},$

then, $(\Omega_{\ell})_{\ell\geq 0}$ is a sequence of increasing events,
moreover we have $\mathbb{P}(\cup_{\ell\geq 0}\Omega_{\ell})=1$.

Next, we just need to show that the restriction of $\tilde{W}_{\infty}$ on
$\Omega_{\ell,j}=\\{\omega;W_{\ell}(\omega)=j\\}$ has a density for each $j$,
with $Am\leq j\leq T_{\ell-1}.$ Let $(p_{c})_{c\in\text{supp}(X)}$ the
distribution of $X$.

######  Lemma 6.

For a fixed $\ell>0$, there exists a positive constant $\kappa$, such that,
for every $c\in\text{supp(X)}$, $n\geq\ell+1$, $Am\leq j\leq T_{\ell-1}$ and
$k\leq Am(n+1)$, we have

$\sum_{i=0}^{m}\mathbb{P}(W_{n+1}=j+k|W_{n}=j+k-ci)\leq
p_{c}(1-\frac{1}{n}+\frac{\kappa}{n^{2}}).$ (19)

###### Proof.

According to Lemma 4.1 [11], for $Am\leq j\leq T_{\ell-1}$, $n\geq\ell$ and
$k\leq Am(n+1)$, the following holds:

$\sum_{i=0}^{m}{j+c(k-i)\choose i}{T_{n}-j-c(k-i)\choose
m-i}=\frac{T_{n}^{m}}{m!}+\frac{(1-m-2c)T_{n}^{m-1}}{2(m-1)!}+...,$ (20)

which is a polynomial in $T_{n}$ of degree $m$ with coefficients depending on
$W_{0},B_{0},m$ and $c$ only.

Let $u_{n,k}(c)=\sum_{i=0}^{m}\mathbb{P}(W_{n+1}=j+k|W_{n}=j+k-ic)$. Applying
Equation (20) to our model we have

$\displaystyle u_{n,k}(c)$ $\displaystyle=$ $\displaystyle
p_{c}\sum_{i=0}^{m}{j+k\choose i}{T_{n}-j-k\choose m-i}{T_{n}\choose m}^{-1}$
(21) $\displaystyle=$ $\displaystyle p_{c}{T_{n}\choose
m}^{-1}\Big{(}\frac{T_{n}^{m}}{m!}+\frac{(1-m-2c)}{(m-1)!}T_{n}^{m-1}+\ldots\Big{)}\Big{(}\frac{T_{n}^{m}}{m!}+\frac{(1-m)}{2(m-1)!}T_{n}^{m-1}+\ldots\Big{)}^{-1}$
$\displaystyle\stackrel{{\scriptstyle a.s}}{{=}}$ $\displaystyle
p_{c}\Big{(}1-\frac{1}{n}+O\Big{(}\frac{1}{n^{2}}\Big{)}\Big{)}.$

∎

Later, we will limit the proof by mentioning the main differences with Lemma
4.1 [11]. For a fixed $\ell$ and $n\geq\ell+1$, we denote by
$v_{n,j}=\displaystyle\max_{0\leq k\leq
Amn}\mathbb{P}\bigl{(}W_{\ell+n}=j+k|W_{\ell}=j\bigr{)}$. We have the
following inequality:

$\displaystyle v_{n+1,j}$ $\displaystyle\leq$ $\displaystyle\max_{0\leq k\leq
Am(n+1)}\Big{\\{}\sum_{i=0}^{m}\sum_{c\in\text{supp}{(X)}}\mathbb{P}(W_{\ell+n+1}=j+k|W_{\ell+n}=j+k-ci)\Big{\\}}$
$\displaystyle\leq$ $\displaystyle\max_{0\leq k\leq
Am(n+1)}\Big{\\{}\sum_{i=0}^{m}\sum_{c\in\text{supp}{(X)}}\mathbb{P}(W_{\ell+n+1}=j+k|W_{\ell+n}=j+k-ci)$
$\displaystyle\times\mathbb{P}(W_{\ell+n}=j+k-ci|W_{\ell}=j)\Big{\\}}$
$\displaystyle\leq$ $\displaystyle\max_{0\leq k\leq
Am(n+1)}\sum_{i=0}^{m}\sum_{c\in\text{supp}{(X)}}\mathbb{P}(W_{\ell+n+1}=j+k|W_{\ell+n}=j+k-ci)$
$\displaystyle\times\max_{0\leq\tilde{k}\leq
Amn}\mathbb{P}\bigl{(}W_{\ell+n}=j+\tilde{k}|W_{\ell}=j\bigr{)}$
$\displaystyle\leq$
$\displaystyle\sum_{c\in\text{supp}{(X)}}p_{c}\Big{(}1-\frac{1}{n+l}+\frac{\kappa}{(n+l)^{2}}\Big{)}v_{n,j}$
$\displaystyle=\Big{(}1-\frac{1}{n+l}+\frac{\kappa}{(n+l)^{2}}\Big{)}v_{n,j}.$

This implies that there exists some positive constant $C(\ell)$, depending on
$\ell$ only, such that, for a fixed $\ell$ and for all $n\geq\ell+1$, we get

$\max_{0\leq k\leq
m(n-l)}\mathbb{P}\bigl{(}W_{n}=j+k|W_{l}=j\bigr{)}\leq\prod_{i=\ell}^{n}\Big{(}1-\frac{1}{i}+\frac{\kappa}{i^{2}}\Big{)}\leq\frac{C(\ell)}{n}.$
(22)

The rest of the proof follows.

∎

###### Proof of Theorem 3.

Consider the urn model evolving by the matrix $Q_{n}=\begin{pmatrix}0&X_{n}\\\
Y_{n}&0\\\ \end{pmatrix}$. According to Equation (1), we have the following
recursions:

$W_{n+1}=W_{n}+X_{n+1}(m-\xi_{n+1})\quad\text{and}\quad
T_{n+1}=T_{n}+mX_{n+1}+\xi_{n+1}(Y_{n+1}-X_{n+1}).$ (23)

######  Lemma 7.

The proportion of white balls after $n$ draws, $Z_{n}$, satisfies the
stochastic algorithm defined by (12), where
$f(x)=m(\mu_{Y}-\mu_{X})x^{2}-2\mu_{X}mx+\mu_{X}m$,
$\gamma_{n}=\frac{1}{T_{n}}$ and $\Delta
M_{n+1}=D_{n+1}-\mathbb{E}[D_{n+1}|\mathcal{F}_{n}]$, with
$D_{n+1}=\xi_{n+1}(Z_{n}(X_{n+1}-Y_{n+1})-X_{n+1})+mX_{n+1}$.

###### Proof.

We check the conditions of Definition 1, indeed,

(i)

recall that
$T_{n}=T_{0}+m\sum_{i=1}^{n}X_{i}+\sum_{i=1}^{n}\xi_{i}(Y_{i}-X_{i})$, then
$\frac{T_{n}}{n}\leq\frac{T_{0}}{n}+\frac{m}{n}\sum_{i=1}^{n}X_{i}+\frac{m}{n}\sum_{i=1}^{n}|Y_{i}-X_{i}|.$
By the strong law of large numbers we have $\frac{T_{n}}{n}\leq
m(\mu_{X}+\mu_{|Y-X|})+1$. On the other hand, we have
$T_{n}\geq\displaystyle\min_{1\leq i\leq n}(X_{i},Y_{i})mn,$ thus, the
following bound holds

$\frac{1}{(m(\mu_{X}+\mu_{|Y-X|})+1)n}\leq\frac{1}{T_{n}}\leq\frac{1}{m\displaystyle\min_{1\leq
i\leq n}(X_{i},Y_{i})n},$

then $c_{l}=\frac{1}{(m(\mu_{X}+\mu_{|Y-X|})+1)n}$ and
$c_{u}=\frac{1}{m\displaystyle\min_{1\leq i\leq n}(X_{i},Y_{i})},$

(ii)

$\mathbb{E}[\Delta
M_{n+1}^{2}|\mathcal{F}_{n}]\leq(\mu_{(X-Y)^{2}}+3\mu_{X})(m+m^{2})+5m^{2}\mu_{X^{2}}+2m^{2}\mu_{X}\mu_{Y}+m^{2}(|\mu_{X}-\mu_{Y}|+3\mu_{X})=K_{u},$

(iii)

$|f(Z_{n})|\leq m(|\mu_{Y}-\mu_{X}|+3\mu_{X})=K_{f},$

(iv)

$\mathbb{E}[\frac{1}{T_{n+1}}\Delta
M_{n+1}|\mathcal{F}_{n}]\leq\frac{1}{T_{n}}\mathbb{E}[\Delta
M_{n+1}|\mathcal{F}_{n}]=0$

∎

######  Proposition 4.

The proportion of white balls in the urn after $n$ draws, $Z_{n}$, satisfies
as $n$ tends to infinity

$Z_{n}\stackrel{{\scriptstyle
a.s}}{{\longrightarrow}}z:=\frac{\sqrt{\mu_{X}}}{\sqrt{\mu_{X}}+\sqrt{\mu_{Y}}}.$
(24)

###### Proof.

The proportion of white balls in the urn satisfies the stochastic
approximation algorithm defined in (12). As the function $f$ is continuous, by
Theorem 5, the process $Z_{n}$ converges almost surely to
$z=\frac{\sqrt{\mu_{X}}}{\sqrt{\mu_{X}}+\sqrt{\mu_{Y}}}$, the unique zero of
$f$ with negative derivative.

∎

Next, we give an estimate of $T_{n}$, the total number of balls in the urn
after $n$ draws, in order to describe the asymptotic of the urn composition.
By Equation (23), we have

$\frac{T_{n}}{n}=\frac{T_{0}}{n}+\frac{m}{n}\sum_{i=1}^{n}X_{i}+\frac{m(\mu_{Y}-\mu_{X})}{n}\sum_{i=1}^{n}Z_{i-1}+\frac{1}{n}\sum_{i=1}^{n}\Big{[}\xi_{i}(Y_{i}-X_{i})-\mathbb{E}[\xi_{i}(Y_{i}-X_{i})|\mathcal{F}_{i-1}]\Big{]}.$

Since $(X_{i})_{i\geq 1}$ are iid random variables, then by the strong law of
large numbers we have $\frac{m}{n}\sum_{i=1}^{n}X_{i}\stackrel{{\scriptstyle
a.s}}{{\rightarrow}}m\mu_{X}$. Via Cesáro lemma, we conclude that
$\frac{1}{n}\sum_{i=1}^{n}Z_{i-1}$ converges almost surely, as $n$ tends to
infinity, to $z$. Finally, we prove that last term in the right side tends to
zero, as $n$ tends to infinity. In fact, let
$G_{n}=\sum_{i=1}^{n}\Big{[}\xi_{i}(Y_{i}-X_{i})-\mathbb{E}[\xi_{i}(Y_{i}-X_{i})|\mathcal{F}_{i-1}]\Big{]}$,
then $(G_{n},\mathcal{F}_{n})$ is a martingale difference sequence such that

$\frac{<G>_{n}}{n}=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[\nabla
G_{i}^{2}|\mathcal{F}_{i-1}],$

where $\nabla
G_{n}=G_{n}-G_{n-1}=\xi_{n}(Y_{n}-X_{n})-\mathbb{E}[\xi_{n}(Y_{n}-X_{n})|\mathcal{F}_{n-1}]$
and $<G>_{n}$ denotes the quadratic variation of the martingale.
By a simple computation, we have the almost sure convergence of
$\mathbb{E}[\nabla G_{i}^{2}|\mathcal{F}_{i-1}]$ to
$(mz(1-z)+m^{2}z^{2})(\sigma_{Y}^{2}+\sigma_{X}^{2})$. Therefore, Cesáro lemma
ensures that, $\frac{<G>_{n}}{n}$ converges to
$(mz(1-z)+m^{2}z^{2})(\sigma_{Y}^{2}+\sigma_{X}^{2})$ and
$\frac{G_{n}}{n}\stackrel{{\scriptstyle a.s}}{{\longrightarrow}}0$. Thus, for
$n$ large enough we have

$\frac{T_{n}}{n}\stackrel{{\scriptstyle
a.s}}{{\longrightarrow}}m\sqrt{\mu_{X}}\sqrt{\mu_{Y}}.$ (25)

In view of Equation (25), we describe the asymptotic behavior of the urn
composition after $n$ draws. One can write
$\frac{W_{n}}{n}\frac{W_{n}}{T_{n}}\frac{T_{n}}{n}$ and
$\frac{B_{n}}{n}\stackrel{{\scriptstyle
a.s}}{{=}}\frac{B_{n}}{T_{n}}\frac{T_{n}}{n}$, using Equations (24, 25) and
Slutsky theorem, we have, as $n$ tends to infinity,
$\frac{W_{n}}{n}\stackrel{{\scriptstyle
a.s}}{{\longrightarrow}}m\sqrt{\mu_{X}}\sqrt{\mu_{Y}}z$ and
$\frac{B_{n}}{n}\stackrel{{\scriptstyle
a.s}}{{\longrightarrow}}m\sqrt{\mu_{X}}\sqrt{\mu_{Y}}(1-z)$.
Proof of claim 2
Later, we aim to apply Theorem 6. In our model, we have
$\gamma_{n}=\frac{1}{T_{n}}$, then we need to control the following asymptotic
behaviors

$\lim_{n\rightarrow+\infty}\mathbb{E}[\Big{(}\frac{n}{T_{n}}\Big{)}^{2}\Delta
M_{n+1}^{2}|\mathcal{F}_{n}]\quad\text{and}\quad\lim_{n\rightarrow+\infty}-\frac{n}{T_{n}}f^{\prime}(Z_{n}).$

In fact, recall that $\frac{n}{T_{n}}$ converges almost surely to
$\frac{1}{m\sqrt{\mu_{X}}\sqrt{\mu_{Y}}}$ and $\mathbb{E}[\Delta
M_{n+1}^{2}|\mathcal{F}_{n}]=\mathbb{E}[D_{n+1}^{2}|\mathcal{F}_{n}]+\mathbb{E}[D_{n+1}|\mathcal{F}_{n}]^{2}$.
Since $\mathbb{E}[D_{n+1}|\mathcal{F}_{n}]^{2}$ converges almost surely to
$f(z)^{2}=0$, we have,

$\displaystyle\mathbb{E}[D_{n+1}^{2}|\mathcal{F}_{n}]$ $\displaystyle=$
$\displaystyle\mathbb{E}\Big{[}Z_{n}^{2}(X_{n+1}-Y_{n+1})^{2}-2Z_{n}X_{n+1}+X_{n+1}|\mathcal{F}_{n}\Big{]}\mathbb{E}[\xi_{n+1}^{2}|\mathcal{F}_{n}]+m^{2}\mathbb{E}(X^{2})$
$\displaystyle+2m^{2}\Bigl{(}Z_{n}^{2}(\mathbb{E}(X^{2})-\mu_{X}\mu_{Y})-Z_{n}\mathbb{E}(X^{2})\Bigr{)}.$

Using the fact that
$\mathbb{E}[\xi_{n+1}^{2}|\mathcal{F}_{n}]=mZ_{n}(1-Z_{n})\frac{T_{n}-m}{T_{n}-1}+m^{2}Z_{n}^{2}$
and that $Z_{n}$ converges almost surely to $z$, we conclude that
$\mathbb{E}[D_{n+1}^{2}|\mathcal{F}_{n}]$ converges almost surely to $G(z)>0.$
Applying Theorem 6, we obtain the following

$\sqrt{n}(Z_{n}-z)\stackrel{{\scriptstyle\mathcal{L}}}{{\longrightarrow}}\mathcal{N}\Big{(}0,\frac{G(z)}{3m^{2}\mu_{X}\mu_{Y}}\Big{)}.$
(26)

But, we can write
$\frac{W_{n}-zT_{n}}{\sqrt{n}}=\sqrt{n}\bigl{(}\frac{W_{n}}{T_{n}}-z\bigr{)}\frac{T_{n}}{n}$.
Thus, it is enough to use Slutsky theorem to conclude the proof.

∎

###### Proof of Theorem 4.

Consider the urn model defined in (1) with $Q_{n}=\begin{pmatrix}X_{n}&0\\\
0&Y_{n}\\\ \end{pmatrix}$. The process of the urn satisfies the following
recursions:

$W_{n+1}=W_{n}+X_{n+1}\xi_{n+1}\quad\text{and}\quad
T_{n+1}=T_{n}+mY_{n+1}+\xi_{n+1}(X_{n+1}-Y_{n+1}).$ (27)

######  Lemma 8.

If $\mu_{X}\neq\mu_{Y}$, the proportion of white balls in the urn after $n$
draws satisfies the stochastic algorithm defined by (12) where
$\gamma_{n}=\frac{1}{T_{n}}$, $f(x)=m(\mu_{Y}-\mu_{X})x(x-1)$ and $\Delta
M_{n+1}=D_{n+1}-\mathbb{E}[D_{n+1}|\mathcal{F}_{n}]$ with
$D_{n+1}=\xi_{n+1}(Z_{n}(Y_{n+1}-X_{n+1})+X_{n+1})-mZ_{n}Y_{n+1}$.

###### Proof.

We check that, if $\mu_{X}\neq\mu_{Y}$, the conditions of definition 1 hold.
Indeed,

(i)

as $T_{n}=T_{0}+m\sum_{i=1}^{n}Y_{i}+\sum_{i=1}^{n}\xi_{i}(X_{i}-Y_{i})$, then
via the strong law of large numbers we have $|\frac{T_{n}}{n}|\leq
m\mu_{Y}+m\mu_{|X-Y|}+1$. On the other hand, we have $T_{n}\geq\min_{1\leq
i\leq n}(X_{i},Y_{i})mn$, thus,

$\frac{1}{(m\mu_{Y}+m\mu_{|X-Y|})n}\leq\frac{1}{T_{n}}\leq\frac{1}{\displaystyle\min_{1\leq
i\leq n}(X_{i},Y_{i})mn},$

(ii)

$\mathbb{E}[\Delta
M_{n+1}^{2}|\mathcal{F}_{n}]\leq(2m+m^{2})(4\mu_{X^{2}}+\mu_{Y^{2}})+3m^{2}\mu_{Y^{2}}+2m^{2}\mu_{X}+2m^{2}\mu_{X}\mu_{Y}+4m^{2}(\mu_{X}-\mu_{Y})^{2}=K_{u},$

(iii)

$|f(Z_{n})|=|m(\mu_{Y}-\mu_{X})Z_{n}(Z_{n}-1)|\leq 2m|\mu_{Y}-\mu_{X}|=K_{f},$

(iv)

$\mathbb{E}[\gamma_{n+1}\Delta
M_{n+1}|\mathcal{F}_{n}]\leq\frac{1}{T_{n}}\mathbb{E}[\Delta
M_{n+1}|\mathcal{F}_{n}]=0=K_{e}.$

∎

∎

######  Proposition 5.

The proportion of white balls in the urn after $n$ draws, $Z_{n}$, satisfies
almost surely

$\displaystyle\lim_{n\rightarrow\infty}Z_{n}=\left\\{\begin{array}[]{ll}1,&\hbox{
if }\mu_{X}>\mu_{Y};\\\ 0,&\hbox{ if }\mu_{X}<\mu_{Y};\\\
\tilde{Z}_{\infty},&\hbox{ if }\mu_{X}=\mu_{Y},\end{array}\right.$
where $\tilde{Z}_{\infty}$ is a positive random variable.

###### Proof of Proposition 5.

Recall that, if $\mu_{X}\neq\mu_{Y}$, $Z_{n}$ satisfies the stochastic
algorithm defined in Lemma 8. As the function $f$ is continuous, by Theorem 6
we conclude that $Z_{n}$ converges almost surely to the stable zero of the
function $h$ with a negative derivative, which is $1$ if $\mu_{X}>\mu_{Y}$ and
$0$ if $\mu_{X}<\mu_{Y}.$
In the case when $\mu_{X}=\mu_{Y}$, we have
$Z_{n+1}=Z_{n}+\frac{P_{n+1}}{T_{n+1}}$, where
$P_{n+1}=X_{n+1}\xi_{n+1}-Z_{n}\bigl{(}mY_{n+1}+\xi_{n+1}(X_{n+1}-Y_{n+1})\bigr{)}$.
Since $\mathbb{E}[P_{n+1}|\mathcal{F}_{n}]=0$, then $Z_{n}$ is a positive
martingale which converges almost surely to a positive random variable
$\tilde{Z}_{\infty}$.
As a consequence, we have

######  Corollary 2.

The total number of balls in the urn, $T_{n}$, satisfies as $n$ tends to
infinity

if $\mu_{X}\geq\mu_{Y}$

$\frac{T_{n}}{n}\stackrel{{\scriptstyle a.s}}{{\longrightarrow}}m\mu_{X}.$

###### Proof.

In fact, let
$M_{n}=\sum_{i=1}^{n}\xi_{i}(X_{i}-Y_{i})-\mathbb{E}[\xi_{i}(X_{i}-Y_{i})|\mathcal{F}_{i-1}],$
we have

$\displaystyle\frac{T_{n}}{n}$ $\displaystyle=$
$\displaystyle\frac{T_{0}}{n}+\frac{m}{n}\sum_{i=1}^{n}Y_{i}+\frac{1}{n}\sum_{i=1}^{n}\xi_{i}(X_{i}-Y_{i})$
$\displaystyle=$
$\displaystyle\frac{T_{0}}{n}+\frac{m}{n}\sum_{i=1}^{n}Y_{i}+\frac{m(\mu_{X}-\mu_{Y})}{n}\sum_{i=1}^{n}Z_{i-1}+\frac{M_{n}}{n}.$

As it was proved in the previous theorem, we show that, as $n$ tends to
infinity, we have $\frac{M_{n}}{n}\stackrel{{\scriptstyle
a.s}}{{\longrightarrow}}0$. Recall that, if $\mu_{X}>\mu_{X}$ , $Z_{n}$
converges almost surely to $1$. Then, using Cesáro lemma, we obtain the limits
requested. If $\mu_{X}=\mu_{Y}$, we have $\frac{1}{n}\sum_{i=1}^{n}Y_{i}$
converges to $\mu_{Y}$. ∎

Using the results above, the convergence of the normalized number of white
balls follows immediately. Indeed, if $\mu_{X}>\mu_{Y}$, we have, as $n$ tends
to infinity,

$\frac{W_{n}}{n}=\frac{W_{n}}{T_{n}}\frac{T_{n}}{n}\stackrel{{\scriptstyle
a.s}}{{\longrightarrow}}m\mu_{X},$

Let
$\tilde{G}_{n}=\Bigl{(}\prod_{i=1}^{n-1}(1+\frac{m\mu_{Y}}{T_{i}})\Bigr{)}^{-1}B_{n},$
then $(\tilde{G}_{n},\mathcal{F}_{n})$ is a positive martingale. There exists
a positive number $A$ such that
$\prod_{i=1}^{n-1}(1+\frac{m\mu_{Y}}{T_{i}})\simeq An^{\rho}$. Then, as $n$
tends to infinity we have

$\frac{B_{n}}{n^{\rho}}\stackrel{{\scriptstyle
a.s}}{{\rightarrow}}B_{\infty},$

where $B_{\infty}$ is a positive random variable.
If $\mu_{X}=\mu_{Y}$, the sequences
$\Bigl{(}\prod_{i=1}^{n-1}(1+\frac{m\mu_{X}}{T_{i}})\Bigr{)}^{-1}W_{n}$ and
$\Bigl{(}\prod_{i=1}^{n-1}(1+\frac{m\mu_{Y}}{T_{i}})\Bigr{)}^{-1}B_{n}$ are
$\mathcal{F}_{n}$ martingales such that
$\Bigl{(}\prod_{i=1}^{n-1}(1+\frac{m\mu_{X}}{T_{i}})\Bigr{)}^{-1}\simeq Bn,$
where $B>0$, then, as $n$ tends to infinity, we have

$\frac{W_{n}}{n}\stackrel{{\scriptstyle
a.s}}{{\rightarrow}}W_{\infty}\quad\text{and}\quad\frac{B_{n}}{n}\stackrel{{\scriptstyle
a.s}}{{\rightarrow}}\tilde{B}_{\infty},$

where $W_{\infty}$ and $\tilde{B}_{\infty}$ are positive random variables
satisfying $\tilde{B}_{\infty}=m\mu_{X}-W_{\infty}.$ ∎

Remark: The case when $\mu_{X}<\mu_{Y}$ is obtained by interchanging the
colors. In fact we have the following results:

$T_{n}\stackrel{{\scriptstyle a.s}}{{=}}m\mu_{Y}n+o(n),\quad
W_{n}=\tilde{W}_{\infty}n^{\sigma}+o(n)\quad\text{and}\quad
B_{n}=m\mu_{Y}n+o(n),$

where $\tilde{W}_{\infty}$ is a positive random variable and
$\sigma=\frac{\mu_{X}}{\mu_{Y}}.$

## References

  * [1] C. Mailler, N. Lasmer and O. Selmi.(2017). Multiple drawing multi-color urns by stochastic approximation.(to appear).
  * [2] F. Eggenberger and G. Pólya.(1923). Über die statistik verkeletter vorge. Zeitschift für Angewandte Mathematik und Mechanic, 1:279-289.
  * [3] G. Pagés and S. Laruelle. (2015). Randomized urns models revisited using stochastic approximation. Annals of Applied Probability, (23)4: 1409-1436.
  * [4] H. Renlund. (2010). Generalized Polya urns via stochastic approximation. arxiv: 1002.3716v1.
  * [5] H. Renlund.(2011). Limit theorem for Stochastic approxiamtion algorithm. arxiv :1102.4741v1.
  * [6] H. Mahmoud. (2004). Random spouts as internet model and Pólya processes. Actainformatica, 41: 1-18.
  * [7] K.B. Athreya and P.E. Ney.(1972). Branching Processes. Springer-Verlag, Berlin.
  * [8] L.J. Wei.(1978). An application of an urn model to the design of sequential controlled clinical trials. Journal of American Statistics Association,(73), 363:559-563.
  * [9] M. Kuba, H. Mahmoud and A. Panholzer.(2013). Analysis of a generalized Friedman’s urn with multiple drawings, Discrete Applied Mathematics, 161, 2968-2984 .
  * [10] M. R Chen and M. Kuba. (2013). On generalized Polya urn models, Theory of probability and its application, 40, 1169-1186.
  * [11] M. R Chen and C. Z Wei.(2005). A new urn model. Applied Probability, (42)4, 964-976.
  * [12] M. Kuba and H. Sulzbach. (2016). On martingale tail sums in affine two-color urn models with multiple drawings. arXiv:1509.09053.
  * [13] M. Kuba and H. Mahmoud. (2016). Two-colour balanced affine urn models with multiple drawings I: Central limit theorem. arxiv :1503.09069.
  * [14] M. Kuba and H. Mahmoud. (2016). Two-colour balanced affine urn models with multiple drawings II: large-index and triangular urns. arxiv: 1509.09053.
  * [15] N.L. Johnson, S. Kotz.(1977). Urn models and their application. Johnson Wiley.
  * [16] R. Aguech.(2009). Limit Theorems for Random Triangular Urns Schemes. Journal of Applied Probability, 46(3), 827-843.
  * [17] R. Aguech, N. Lasmer, O. Selmi.(2017). A generalized urn model with multiple drawing and random addition. (to appear.)
  * [18] R.N. Goldman.(1985). Polya’s urn model and computer aided geometry design.SIAM Journal on Algebraic Discrete Methods, 6(1), 1-28.
  * [19] S. Janson.(2006).Limit theorems of triangular urn schemes.Probability Theory and Related Fields, 134(3), 417-452.


l2 regularization                                $2.44 \cdot 10^{-5}$                          $3.21 \cdot 10^{-4}$

initial epsilon                                  $0.2$                       $0.27$

final epsilon                                    $0.01$                       $0.01$

epsilon reduction time steps                     $15000$                    $26999$

initial noise scale                              $8.75$                                $18.55$

final noise scale                                $0.12$                               $1.59$

noise reduction time steps                       $15792$                             $27876$

replay buffer capacity                           $32410$                             $45168$

prioritized replay alpha                         $0.61$                                $0.30$

prioritized replay beta                          $0.32$                                $0.44$

target update frequency                          $2$                                    $1$

batch size                                       $470$                                $101$

MPS-TD3 configuration

CHAPTER: RESULTS

The following appendix describes first the results for the agents trained without obstacles. Afterward, we continue when learning included restrictions. Note that all numbers were rounded to two decimal points.

§ LEARNING WITHOUT OBSTACLES

§.§ Training

Iterations until convergence (80% solved episodes on average)

Fraction solved

Steps to goal

Portion of allowed actions

Absolute allowed actions

Number of allowed intervals

On-policy training progress

Fraction solved

Steps to goal

Portion of allowed actions

Absolute allowed actions

Number of allowed intervals

Off-policy training progress

Fraction solved

Steps to goal

Portion of allowed actions

Absolute allowed actions

Number of allowed intervals

MPS-TD3 and PAM training progress

§.§ Evaluation Without Restrictions

1cApproach     1cReturn     1cSteps     1cSolved

TD3                                       $114.57 \pm 3.67$                         $17.33 \pm 2.88$                         $100.00\% \pm 0.00\%$

TD3-Projection                            $91.46 \pm 55.30$                         $17.60 \pm 4.22$                         $83.33\% \pm 40.82\%$

TD3-Masking                               $114.27 \pm6.21$                          $18.83 \pm 5.53$                         $100.00\% \pm 0.00\%$

TD3-Random                                $114.13 \pm 4.54$                         $18.17 \pm 3.87$                         $100.00\% \pm 0.00\%$

DQN-Masked                                $113.80 \pm 4.83$                         $18.83 \pm 4.22$                         $100.00\% \pm 0.00\%$

PPO                                       $115.16 \pm 0.13$                         $15.00 \pm 0.00$                         $100.00\% \pm 0.00\%$

PPO-Projection                            $115.12 \pm 1.03$                         $15.33 \pm 0.52$                         $100.00\% \pm 0.00\%$

PPO-Masking                               $114.81 \pm 0.38$                         $15.00 \pm 0.00$                         $100.00\% \pm 0.00\%$

PPO-Random                                $114.87 \pm 0.50$                         $15.00 \pm 0.00$                         $100.00\% \pm 0.00\%$

PPO-Masked                                $73.06 \pm 64.29$                         $18.00 \pm 1.83$                        $66.67\% \pm 51.64\%$

MPS-TD3                                   $115.53 \pm 1.70$                         $16.83 \pm 1.47$                         $100.00\% \pm 0.00\%$

PAM                                       $11.88 \pm 41.37$                         $38.00 \pm 0.00$                         $16.67\% \pm 40.8\%$

Average return, steps, and solved episodes

1cApproach     1cIntervals     1cSize     1cFraction

TD3                                       $1.01 \pm 0.02$                            $213.07 \pm 3.04$                         $96.85\% \pm 1.38\%$

TD3-Projection                            $1.00 \pm 0.01$                            $190.54 \pm 31.62$                        $86.61\% \pm 14.37\%$

TD3-Masking                               $1.00 \pm 0.00$                            $212.30 \pm 3.22$                         $96.50\% \pm 1.47\%$

TD3-Random                                $1.01 \pm 0.03$                            $211.58 \pm 5.93$                         $96.17\% \pm 2.69\%$

DQN-Masked                                $1.01 \pm 0.02$                            $209.27 \pm 11.66$                        $95.12\% \pm 5.30\%$

PPO                                       $1.00 \pm 0.00$                            $214.65 \pm 0.00$                         $97.57\% \pm 0.00\%$

PPO-Projection                            $1.00 \pm 0.00$                            $213.28 \pm 3.17$                         $96.94\% \pm 1.44\%$

PPO-Masking                               $1.00 \pm 0.00$                            $214.65 \pm 0.00$                         $97.57\% \pm 0.00\%$

PPO-Random                                $1.00 \pm 0.00$                             $213.40 \pm 1.97$                         $97.00\% \pm 0.89\%$

PPO-Masked                                $1.03 \pm 0.03$                            $200.05 \pm 16.24$                        $90.93\% \pm 7.38\%$

MPS-TD3                                   $1.04 \pm 0.06$                            $209.99 \pm 4.59$                         $95.45\% \pm 2.09\%$

PAM                                       $1.08 \pm 0.08$                            $189.50 \pm 14.72$                        $86.14\% \pm 6.69\%$

Average number of disjoint intervals and size of the action space

1cApproach     1cAverage     1cMinimum     1cMaximum     1cVariance

TD3     $212.34 \pm 4.14$     $211.80 \pm 5.21$     $212.88 \pm 3.27$     $40.70 \pm 99.68$

TD3-Projection     $190.38 \pm 31.84$     $190.27 \pm 32 .00$     $190.49 \pm 31.69$     $2.87 \pm 7.03$

TD3-Masking     $212.30 \pm 3.22$     $212.30 \pm 3.22$     $212.30 \pm 3.22$     $0.00 \pm 0.00$

TD3-Random     $211.00 \pm 7.18$     $210.92 \pm 7.35$     $211.07 \pm 7.01$     $0.76 \pm 1.87$

DQN-Masked     $208.98 \pm 12.35$     $208.71 \pm 13.00$     $209.26 \pm 11.70$     $11.58 \pm 28.36$

PPO     $214.65 \pm 0.00$     $214.65 \pm 0.00$     $214.65 \pm 0.00$     $0.00 \pm 0.00$

PPO-Projection     $213.28 \pm 0.00$     $213.28 \pm 0.00$     $213.28 \pm 0.00$     $0.00 \pm 0.00$

PPO-Masking     $214.65 \pm 0.00$     $214.65 \pm 0.00$     $214.65 \pm 0.00$     $0.00 \pm 0.00$

PPO-Random     $213.40 \pm 1.97$     $213.40 \pm 1.97$     $213.40 \pm 1.97$     $0.00  \pm 0.00$

PPO-Masked     $198.85 \pm 17.41$     $198.10 \pm 17.98$     $199.60 \pm 16.86$     $24.94 \pm 33.97$

MPS-TD3     $207.94 \pm 7.73$     $206.64 \pm 9.74$     $209.24 \pm 5.73$     $48.36 \pm 75.40$

PAM     $184.76 \pm 17.78$     $182.38 \pm 19.85$     $187.15 \pm 15.98$     $112.01 \pm 158.66$

Size of the individual intervals

Allowed action space size

Number of intervals

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

On-policy control variables

Allowed action space size

Number of intervals

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

Off-policy control variables

Allowed action space size

Number of intervals

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

MPS-TD3 and PAM control variables

Welch's t-test p-values between average returns

Welch's t-test p-values between average steps

§.§ Evaluation With Simple Restrictions

Average Return

Average fraction of solved environments

Average episode length

1cApproach     1cReturn     1cSteps     1cSolved

TD3                                       $49.22 \pm 36.39$                         $26.32 \pm 7.41$                         $41.25\% \pm 34.27\%$

TD3-Projection                            $73.11 \pm 23.50$                         $22.56 \pm 1.01$                         $65.50\% \pm 19.48\%$

TD3-Masking                               $89.33 \pm 15.48$                         $24.70 \pm 3.12$                         $79.58\% \pm 15.03\%$

TD3-Random                                $78.09 \pm 25.43$                         $27.23 \pm 4.30$                         $69.58\% \pm 26.43\%$

DQN-Masked                                $111.75 \pm 4.72$                $20.52 \pm 4.40$                         $100.00\% \pm 0.00\%$

PPO                                       $56.33 \pm 32.84$                         $20.45 \pm 1.12$                         $45.83\% \pm 32.39\%$

PPO-Projection                            $109.43 \pm 5.16$                        $20.54 \pm 2.24$                         $97.50\% \pm 5.00\%$

PPO-Masking                               $97.91 \pm 19.31$                         $19.25 \pm 1.22$                $87.08\% \pm 15.36\%$

PPO-Random                                $102.94 \pm 2.84$                        $22.75 \pm 0.88$                         $94.17\% \pm 1.29\%$

PPO-Masked                                $49.40 \pm 20.85$                         $22.58 \pm 2.19$                         $47.08\% \pm 19.13\%$

MPS-TD3                                   $84.01 \pm 12.23$                         $24.85 \pm 2.98$                         $77.50\% \pm 12.65\%$

PAM                                       $16.76 \pm 8.53$                         $30.34 \pm 5.03$                         $16.88\% \pm 3.15\%$

Average return, steps, and solved episodes

1cApproach     1cIntervals     1cSize     1cFraction

TD3                                       $1.14 \pm 0.05$                            $194.47 \pm 8.80$                        $88.40\% \pm 4.00\%$

TD3-Projection                            $1.10 \pm 0.04$                            $185.50 \pm 19.24$                        $84.32\% \pm 8.75\%$

TD3-Masking                               $1.11 \pm 0.03$                            $191.11 \pm 6.29$                        $86.87\% \pm 2.86\%$

TD3-Random                                $1.13 \pm 0.04$                            $189.21 \pm 5.14$                        $86.00\% \pm 2.34\%$

DQN-Masked                                $1.06 \pm 0.02$                            $180.19	 \pm 6.55$                        $81.90\% \pm 2.98\%$

PPO                                       $1.14 \pm 0.02$                            $189.32 \pm 2.34$                        $86.05\% \pm 1.06\%$

PPO-Projection                            $1.09 \pm 0.03$                            $180.38 \pm 5.91$                        $81.99\% \pm 2.69\%$

PPO-Masking                               $1.10 \pm 0.02$                            $183.49 \pm 6.77$                        $83.40\% \pm 3.08\%$

PPO-Random                                $1.12 \pm 0.02$                            $182.43 \pm 1.10$                        $82.92\% \pm 0.50\%$

PPO-Masked                                $1.08 \pm 0.02$                            $183.18 \pm 8.62$                        $83.26\% \pm 3.92\%$

MPS-TD3                                   $1.14 \pm 0.03$                            $187.90 \pm 5.11$                        $85.41\% \pm 2.32\%$

PAM                                       $1.11 \pm 0.03$                            $183.57 \pm 6.09$                        $83.44\% \pm 2.77\%$

Average number of disjoint intervals and size of the action space

1cApproach     1cAverage     1cMinimum     1cMaximum     1cVariance

TD3     $185.72 \pm 11.29$     $180.56 \pm 12.50$     $190.87 \pm 10.22$     $270.04 \pm 99.67$

TD3-Projection     $178.84 \pm 16.94$     $174.97 \pm 15.42$     $182.70 \pm 18.49$     $188.68 \pm 88.10$

TD3-Masking     $183.76 \pm 6.48$     $179.37 \pm 6.88$     $188.15 \pm 6.26$     $223.50 \pm 59.92$

TD3-Random     $180.78 \pm 6.86$     $175.99 \pm 7.73$     $185.57 \pm 6.03$     $242.73 \pm 49.80$

DQN-Masked     $176.45 \pm 6.90$     $174.34 \pm 6.96$     $178.57 \pm 6.90$     $103.50 \pm 41.70$

PPO     $180.56 \pm 2.61$     $176.71 \pm 2.83$     $184.41 \pm 2.82$     $169.5 \pm 64.04$

PPO-Projection     $174.61 \pm 4.67$     $171.23 \pm 4.25$     $177.99 \pm 5.29$     $163.84 \pm 64.63$

PPO-Masking     $177.55 \pm 7.54$     $174.59 \pm 7.69$     $180.50 \pm 7.40$     $128.84 \pm 19.23$

PPO-Random     $175.14 \pm 1.09$     $171.75 \pm 1.30$     $178.52 \pm 1.13$     $150.37 \pm 22.16$

PPO-Masked     $177.92 \pm 7.37$     $175.07 \pm 6.81$     $180.77 \pm 7.95$     $135.52 \pm 41.77$

MPS-TD3     $179.17 \pm 6.03$     $173.58 \pm 6.68$     $184.77 \pm 5.61$     $282.13 \pm 63.59$

PAM     $176.92 \pm 7.11$     $173.48 \pm 7.59$     $180.35 \pm 6.70$     $151.23 \pm 42.24$

Size of the individual intervals

Allowed action space size

Number of intervals

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

On-policy control variables

Allowed action space size

Number of evaluation

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

Off-policy control variables

Allowed action space size

Number of intervals

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

MPS-TD3 and PAM control variables

Maximum reward

Minimum reward

TD3 trajectory examples

Maximum reward

Minimum reward

TD3 with projection trajectory examples

Maximum reward

Minimum reward

TD3 with continuous masking trajectory examples

Maximum reward

Minimum reward

TD3 with random replacement trajectory examples

Maximum reward

Minimum reward

DQN with discrete masking trajectory examples

Maximum reward

Minimum reward

PPO trajectory examples

Maximum reward

Minimum reward

PPO with projection trajectory examples

Maximum reward

Minimum reward

PPO with continuous masking trajectory examples

Maximum reward

Minimum reward

PPO with random replacement trajectory examples

Maximum reward

Minimum reward

PPO with discrete masking trajectory examples

Maximum reward

Minimum reward

MPS-TD3 with random replacement trajectory examples

Maximum reward

Minimum reward

PAM trajectory examples

Welch's t-test p-values between average returns

Welch's t-test p-values between average steps

Welch's t-test p-values between the fractions of solved environments

§.§ Evaluation With Complex Restrictions

Average Return

Average fraction of solved environments

Average episode length

1cApproach     1cReturn     1cSteps     1cFraction

TD3                                       $-10.83 \pm 4.46$                         $37.00 \pm 0.00$                         $0.42\% \pm 1.02\%$

TD3-Projection                            $4.36 \pm 17.70$                          $31.89 \pm 6.21$                         $8.33\% \pm 13.20\%$

TD3-Masking                               $21.01 \pm 32.59$                         $32.01 \pm 3.50$                         $20.42\% \pm 23.42\%$

TD3-Random                                $18.34 \pm 28.31$                         $32.39 \pm 2.16$                         $18.33\% \pm 22.12\%$

DQN-Masked                                $108.31 \pm 6.47$                         $21.51 \pm 4.47$                         $97.50\% \pm 3.87\%$

PPO                                       $1.27 \pm 2.13$                           $20.00 \pm 0.00$                         $0.42\% \pm 1.02\%$

PPO-Projection                            $55.10 \pm 27.31$                         $28.60 \pm 3.72$                         $48.75\% \pm 25.29\%$

PPO-Masking                               $52.71 \pm 13.95$                         $25.81 \pm 1.17$                         $45.00\% \pm 12.14\%$

PPO-Random                                $49.73 \pm 20.90$                         $29.65 \pm 1.70$                         $45.00\% \pm 19.62\%$

PPO-Masked                                $33.38 \pm 4.61$                          $24.22 \pm 1.66$                         $31.67\% \pm 4.65\%$

MPS-TD3                                   $5.35 \pm 11.63$                           $35.16 \pm 3.13$                         $5.83\% \pm 4.92\%$

PAM                                       $10.04 \pm 24.82$                         $28.27 \pm 1.56$                         $12.08\% \pm 15.12\%$

Average return, steps, and solved episodes

1cApproach     1cIntervals     1cSize     1cFraction

TD3                                       $1.38 \pm 0.04$                            $165.08 \pm 3.56$                         $75.04\% \pm 1.62\%$

TD3-Projection                            $1.35 \pm 0.08$                            $143.61 \pm 8.58$                         $65.28\% \pm 3.90\%$

TD3-Masking                               $1.42 \pm 0.09$                            $145.85 \pm 4.04$                         $66.29\% \pm 1.83\%$

TD3-Random                                $1.44 \pm 0.04$                            $148.03 \pm 7.65$                         $67.29\% \pm 3.48\%$

DQN-Masked                                $1.33 \pm0.04$                             $144.09 \pm 4.85$                         $65.49\% \pm 2.21\%$

PPO                                       $1.32 \pm 0.03$                            $164.34 \pm 3.07$                         $74.70\% \pm 1.40\%$

PPO-Projection                            $1.35 \pm 0.01$                            $143.51	 \pm 3.05$                         $65.23\% \pm 1.39\%$

PPO-Masking                               $1.37 \pm 0.02$                            $144.57 \pm 3.84$                         $65.71\% \pm 1.74\%$

PPO-Random                                $1.38 \pm0.02$                             $145.62 \pm 1.99$                         $66.19\% \pm 0.90\%$

PPO-Masked                                $1.34 \pm 0.04$                            $145.01 \pm 2.09$                         $65.91\% \pm 0.95\%$

MPS-TD3                                   $1.51 \pm 0.02$                            $142.27 \pm 4.43$                         $64.67\% \pm 2.02\%$

PAM                                       $1.37 \pm 0.04$                            $151.20 \pm 4.19$                         $68.73\% \pm 1.90\%$

Average number of disjoint intervals and size of the action space

1cApproach     1cAverage     1cMinimum     1cMaximum     1cVariance

TD3     $141.25 \pm 5.96$     $129.71 \pm 7.40$     $152.84 \pm 4.84$     $525.27 \pm 118.62$

TD3-Projection     $123.23 \pm 3.85$     $113.66 \pm 2.28$     $132.85 \pm 6.00$     $411.42 \pm 110.39$

TD3-Masking     $122.13 \pm 4.37$     $111.07 \pm 5.96$     $133.27 \pm 3.33$     $473.27 \pm 75.23$

TD3-Random     $122.99 \pm 6.92$     $111.09 \pm 6.80$     $135.00 \pm 7.17$     $510.08 \pm 50.72$

DQN-Masked     $126.31 \pm 5.18$     $117.93 \pm 5.53$     $134.72 \pm 4.94$     $332.59 \pm 39.78$

PPO     $144.62 \pm 3.70$     $134.57 \pm 4.18$     $154.69 \pm 3.30$     $453.64 \pm 41.82$

PPO-Projection     $124.21 \pm 2.50$     $115.20 \pm 2.46$     $133.28 \pm 2.75$     $369.43 \pm 33.25$

PPO-Masking     $124.36 \pm 4.04$     $114.47 \pm 4.01$     $134.32 \pm 4.11$     $405.97 \pm 30.57$

PPO-Random     $124.89 \pm 2.20$     $115.04 \pm 2.42$     $134.80 \pm 2.15$     $411.82 \pm 38.29$

PPO-Masked     $126.44 \pm 1.07$     $117.91 \pm 1.39$     $134.99 \pm 1.21$     $341.81 \pm 26.87$

MPS-TD3     $114.46 \pm 3.91$     $101.47 \pm 3.67$     $127.53 \pm 4.18$     $534.03 \pm 32.51$

PAM     $130.00 \pm 5.09$     $120.30 \pm 5.52$     $139.75 \pm 4.83$     $405.11 \pm 55.11$

Size of the individual intervals

Allowed action space size

Number of intervals

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

On-policy control variables

Allowed action space size

Number of evaluation

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

Off-policy control variables

Allowed action space size

Number of intervals

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

MPS-TD3 and PAM control variables

Maximum reward

Minimum reward

TD3 trajectory examples

Maximum reward

Minimum reward

TD3 with projection trajectory examples

Maximum reward

Minimum reward

TD3 with continuous masking trajectory examples

Maximum reward

Minimum reward

TD3 with random replacement trajectory examples

Maximum reward

Minimum reward

DQN with discrete masking trajectory examples

Maximum reward

Minimum reward

PPO trajectory examples

Maximum reward

Minimum reward

PPO with projection trajectory examples

Maximum reward

Minimum reward

PPO with continuous masking trajectory examples

Maximum reward

Minimum reward

PPO with random replacement trajectory examples

Maximum reward

Minimum reward

PPO with discrete masking trajectory examples

Maximum reward

Minimum reward

MPS-TD3 with random replacement trajectory examples

Maximum reward

Minimum reward

PAM trajectory examples

Welch's t-test p-values between average returns

Welch's t-test p-values between average steps

Welch's t-test p-values between the fractions of solved environments

§ LEARNING WITH DYNAMIC OBSTACLES

§.§ Training

Iterations until convergence (80% solved episodes on average)

Fraction solved

Steps to goal

Portion of allowed actions

Absolute allowed actions

Number of allowed intervals

On-policy training progress

Fraction solved

Steps to goal

Portion of allowed actions

Absolute allowed actions

Number of allowed intervals

Off-policy training progress

Fraction solved

Steps to goal

Portion of allowed actions

Absolute allowed actions

Number of allowed intervals

MPS-TD3 and PAM training progress

§.§ Evaluation Without Restrictions

1cApproach     1cReturn     1cSteps     1cSolved
TD3                                       $115.02 \pm 2.18$                       $16.50 \pm 1.76$                       $100.00\% \pm 0.00\%$

TD3-Projection                            $114.15 \pm 6.11$                       $17.83 \pm 5.49$                       $100.00\% \pm 0.00\%$

TD3-Masking                               $117.54 \pm 0.27$                       $16.00 \pm 0.00$                       $100.00\% \pm 0.00\%$

TD3-Random                                $115.56 \pm 5.11$                       $17.50 \pm 3.67$                       $100.00\% \pm 0.00\%$

DQN-Masked                                $117.61 \pm 0.09$                       $16.00 \pm 0.00$                       $100.00\% \pm 0.00\%$

PPO                                       $114.82 \pm 1.07$                       $15.17 \pm 0.41$                       $100.00\% \pm 0.00\%$

PPO-Projection                            $115.17 \pm 0.08$                       $15.00 \pm 0.00$                       $100.00\% \pm 0.00\%$

PPO-Masking                               $115.73 \pm 1.91$                       $16.00 \pm 0.00$                       $100.00\% \pm 0.00\%$

PPO-Random                                $115.03 \pm 0.23$                       $15.00 \pm 0.00$                       $100.00\% \pm 0.00\%$

PPO-Masked                                $115.04 \pm 1.54$                       $17.00 \pm 0.89$                       $100.00\% \pm 0.00\%$

MPS-TD3                                   $115.76 \pm 1.68$                       $15.67 \pm 0.52$                       $100.00\% \pm 0.00\%$

PAM                                       $0.20 \pm 13.78$                        $-$                                    $0.00\% \pm 0.00\%$

Average return, steps, and solved episodes

1cApproach     1cIntervals     1cSize     1cFraction

TD3                                       $1.00 \pm 0.00$                            $211.56 \pm 5.93$                       $96.16\% \pm 2.70\%$

TD3-Projection                            $1.00 \pm 0.00$                            $200.64 \pm 34.81$                      $91.20\% \pm 15.82\%$

TD3-Masking                               $1.00 \pm 0.00$                            $214.81 \pm 0.44$                       $97.64\% \pm 0.20\%$

TD3-Random                                $1.00 \pm 0.00$                            $210.05 \pm 12.09$                      $95.48\% \pm 5.50\%$

DQN-Masked                                $1.00 \pm 0.00$                            $214.98 \pm 0.00$                       $97.72\% \pm 0.00\%$

PPO                                       $1.00 \pm 0.00$                            $214.58 \pm 0.16$                       $97.54\% \pm 0.07\%$

PPO-Projection                            $1.00 \pm 0.00$                            $214.65 \pm 0.00$                       $97.57\% \pm 0.00\%$

PPO-Masking                               $1.00 \pm 0.00$                            $214.98 \pm 0.00$                       $97.72\% \pm 0.00\%$

PPO-Random                                $1.00 \pm 0.00$                            $214.65 \pm 0.00$                       $97.57\% \pm 0.00\%$

PPO-Masked                                $1.00 \pm 0.00$                            $213.85 \pm 2.30$                       $97.21\% \pm 1.05\%$

MPS-TD3                                   $1.00 \pm 0.00$                            $211.69 \pm 1.50$                       $96.22\% \pm 0.68\%$

PAM                                       $1.05 \pm 0.05$                            $201.33 \pm 14.69$                      $91.51\% \pm 6.68\%$

Average number of disjoint intervals and size of the action space

1cApproach     1cAverage     1cMinimum     1cMaximum     Variance

TD3     $211.56 \pm 5.93$     $211.56 \pm 5.93$     $211.56 \pm 5.93$     $0.00 \pm 0.00$

TD3-Projection     $200.64 \pm 34.81$     $200.64 \pm 34.81$     $200.64 \pm 34.81$     $0.00 \pm 0.00$

TD3-Masking     $214.81 \pm 0.44$     $214.81 \pm 0.44$     $214.81 \pm 0.44$     $0.00 \pm 0.00$

TD3-Random     $210.05 \pm 12.09$     $210.05 \pm 12.09$     $210.05 \pm 12.09$     $0.00 \pm 0.00$

DQN-Masked     $214.98 \pm 0.00$     $214.98 \pm 0.00$     $214.98 \pm 0.00$     $0.00 \pm 0.00$

PPO     $214.58 \pm 0.16$     $214.58 \pm 0.16$     $214.58 \pm 0.16$     $0.00 \pm 0.00$

PPO-Projection     $214.65 \pm 0.00$     $214.65 \pm 0.00$     $214.65 \pm 0.00$     $0.00 \pm 0.00$

PPO-Masking     $214.98 \pm 0.00$     $214.98 \pm 0.00$     $214.98 \pm 0.00$     $0.00 \pm 0.00$

PPO-Random     $214.65 \pm 0.00$     $214.65 \pm 0.00$     $214.65 \pm 0.00$     $0.00 \pm 0.00$

PPO-Masked     $213.85 \pm 2.30$     $213.85 \pm 2.30$     $213.85 \pm 2.30$     $0.00 \pm 0.00$

MPS-TD3     $211.69 \pm 1.50$     $211.69 \pm 1.50$     $211.69 \pm 1.50$     $0.00 \pm 0.00$

PAM     $198.99 \pm 17.84$     $198.19 \pm 18.92$     $199.8 \pm 16.78$     $28.27 \pm 51.06$

Size of the individual intervals

Allowed action space size

Number of intervals

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

On-policy control variables

Allowed action space size

Number of intervals

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

Off-policy control variables

Allowed action space size

Number of intervals

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

MPS-TD3 and PAM control variables

Welch's t-test p-values between average returns

Welch's t-test p-values between average steps

§.§ Evaluation With Simple Restrictions

Average Return

Average fraction of solved environments

Average episode length

1cApproach     1cReturn     1cSteps     1cSolved

TD3                                       $107.03 \pm 9.62$                       $19.10 \pm 1.58$                       $94.00\% \pm 8.22\%$

TD3-Projection                            $114.23 \pm 1.98$                       $17.23 \pm 0.33$                       $99.00\% \pm 2.24\%$

TD3-Masking                               $110.53 \pm 6.44$                       $17.53 \pm 0.16$                       $95.83\% \pm 5.63\%$

TD3-Random                                $112.22 \pm 2.94$                       $18.09 \pm 0.45$                       $98.50\% \pm 2.24\%$

DQN-Masked                                $115.34 \pm 0.49$                       $17.90 \pm 0.36$                       $100.00\% \pm 0.00\%$

PPO                                       $90.77 \pm 15.85$                       $19.61 \pm 1.27$                       $78.33\% \pm 15.47\%$

PPO-Projection                            $90.73 \pm 6.75$                        $16.39 \pm 0.25$                       $80.00\% \pm 4.47\%$

PPO-Masking                               $111.61 \pm 2.63$                       $17.12 \pm 0.41$                       $97.08\% \pm 2.92\%$

PPO-Random                                $104.83 \pm 1.27$                       $19.42 \pm 1.02$                       $91.67\% \pm 2.04\%$

PPO-Masked                                $95.76 \pm 9.99$                        $20.92 \pm 0.84$                       $85.42\% \pm 9.14\%$

MPS-TD3                                   $110.82 \pm 5.27$                       $19.99 \pm 0.97$                       $97.92\% \pm 5.10\%$

PAM                                       $2.67 \pm 11.72$                        $-$                                    $0.00\% \pm 0.00\%$

Average return, steps, and solved episodes

1cApproach     1cIntervals     1cSize     1cFraction

TD3                                       $1.06 \pm 0.02$                            $191.65 \pm 10.88$                      $87.11\% \pm 4.94\%$

TD3-Projection                            $1.06 \pm 0.00$                            $179.27	 \pm 4.73$                      $81.48\% \pm 2.15\%$

TD3-Masking                               $1.06 \pm 0.01$                            $176.59 \pm 4.08$                       $80.27\% \pm 1.85\%$

TD3-Random                                $1.06 \pm 0.01$                            $185.03	 \pm 4.24$                       $84.11\% \pm 1.93\%$

DQN-Masked                                $1.05 \pm0.01$                             $183.71 \pm 3.19$                       $83.50\% \pm 1.45\%$

PPO                                       $1.08 \pm 0.02$                            $192.99 \pm 3.73$                       $87.72\% \pm 1.70\%$

PPO-Projection                            $1.06 \pm0.00$                             $165.93 \pm 5.13$                       $75.42\% \pm 2.33\%$

PPO-Masking                               $1.04 \pm 0.01$                            $189.26 \pm 6.30$                       $86.03\% \pm 2.86\%$

PPO-Random                                $1.08 \pm 0.01$                            $180.81 \pm 0.94$                       $82.19\% \pm 0.43\%$

PPO-Masked                                $1.07 \pm 0.01$                            $180.42 \pm 3.66$                       $82.01\% \pm 1.66\%$

MPS-TD3                                   $1.07 \pm 0.02$                            $190.53 \pm 4.32$                       $86.60\% \pm 1.97\%$

PAM                                       $1.10 \pm 0.03$                            $192.07 \pm 8.97$                       $87.30\% \pm 4.08\%$

Average number of disjoint intervals and size of the action space

1cApproach     1cAverage     1cMinimum     1cMaximum     1cVariance

TD3     $187.48 \pm 11.46$     $184.77 \pm 11.62$     $190.18 \pm 11.33$     $150.57 \pm 39.10$

TD3-Projection     $175.27 \pm 4.83$     $173.54 \pm 4.66$     $177.00 \pm 5.07$     $65.24 \pm 31.99$

TD3-Masking     $172.52 \pm 4.41$     $171.05 \pm 4.43$     $173.99 \pm 4.45$     $61.92 \pm 30.05$

TD3-Random     $180.56 \pm 4.37$     $179.43 \pm 4.39$     $181.70 \pm 4.40$     $39.07 \pm 19.09$

DQN-Masked     $180.01 \pm 3.46$     $178.16 \pm 3.13$     $181.86 \pm 3.91$     $95.43 \pm 64.22$

PPO     $187.94 \pm 4.44$     $185.29 \pm 5.09$     $190.58 \pm 4.07$     $117.63 \pm 84.64$

PPO-Projection     $162.15 \pm 5.00$     $161.00 \pm 5.09$     $163.30 \pm 4.95$     $32.70 \pm 16.90$

PPO-Masking     $186.49 \pm 6.58$     $184.44 \pm 6.62$     $188.55 \pm 6.55$     $123.00 \pm 19.83$

PPO-Random     $175.44 \pm 0.97$     $173.63 \pm 1.00$     $177.24 \pm 1.07$     $76.70 \pm 19.81$

PPO-Masked     $175.87 \pm 3.41$     $173.68 \pm 3.57$     $178.07 \pm 3.32$     $98.82 \pm 27.54$

MPS-TD3     $185.30 \pm 4.54$     $182.89 \pm 4.46$     $187.71 \pm 4.89$     $127.62 \pm 71.50$

PAM     $186.81 \pm 10.60$     $184.50 \pm 11.08$     $189.12 \pm 10.19$     $98.49 \pm 38.23$

Size of the individual intervals

Allowed action space size

Number of intervals

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

On-policy control variables

Allowed action space size

Number of evaluation

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

Off-policy control variables

Allowed action space size

Number of intervals

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

MPS-TD3 and PAM control variables

Maximum reward

Minimum reward

TD3 trajectory examples

Maximum reward

Minimum reward

TD3 with projection trajectory examples

Maximum reward

Minimum reward

TD3 with continuous masking trajectory examples

Maximum reward

Minimum reward

TD3 with random replacement trajectory examples

Maximum reward

Minimum reward

DQN with discrete masking trajectory examples

Maximum reward

Minimum reward

PPO trajectory examples

Maximum reward

Minimum reward

PPO with projection trajectory examples

Maximum reward

Minimum reward

PPO with continuous masking trajectory examples

Maximum reward

Minimum reward

PPO with random replacement trajectory examples

Maximum reward

Minimum reward

PPO with discrete masking trajectory examples

Maximum reward

Minimum reward

MPS-TD3 with random replacement trajectory examples

Maximum reward

Minimum reward

PAM trajectory examples

Welch's t-test p-values between average returns

Welch's t-test p-values between average steps

Welch's t-test p-values between the fractions of solved environments

§.§ Evaluation With Complex Restrictions

Average Return

Average fraction of solved environments

Average episode length

1cApproach     1cReturn     1cSteps     1cSolved

TD3                                       $43.94 \pm 19.87$                       $22.89 \pm 2.17$                       $33.75\% \pm 17.23\%$

TD3-Projection                            $107.36 \pm 6.57$                       $19.80 \pm 4.90$                       $95.00\% \pm 4.47\%$

TD3-Masking                               $113.88 \pm 1.28$                       $17.59 \pm 0.81$                       $99.17\% \pm 1.29\%$

TD3-Random                                $106.85 \pm 4.65$                       $21.36 \pm 2.34$                       $95.42\% \pm 4.31\%$

DQN-Masked                                $112.14 \pm 2.40$                       $17.88 \pm 0.28$                       $96.25\% \pm 2.62\%$

PPO                                       $12.70 \pm 7.96$                        $22.02 \pm 5.80$                       $6.67\% \pm 4.92\%$

PPO-Projection                            $110.61 \pm 3.06$                       $16.45 \pm 0.23$                       $95.00\% \pm2.74\%$

PPO-Masking                               $106.80 \pm 4.92$                       $18.15 \pm 0.75$                       $86.03\% \pm 2.86\%$

PPO-Random                                $94.56 \pm 4.39$                        $21.83 \pm 1.61$                       $83.33\% \pm 4.38\%$

PPO-Masked                                $67.56 \pm 1.45$                        $22.86 \pm 1.76$                       $82.01\% \pm 1.66\%$

MPS-TD3                                   $110.73 \pm 1.42$                       $21.10 \pm 0.10$                       $99.17\% \pm 2.04\%$

PAM                                       $-10.87 \pm 3.94$                       $-$                                    $0.00\% \pm 0.00\%$

Average return, steps, and solved episodes

1cApproach     1cIntervals     1cSize     1cFraction

TD3                                       $1.39 \pm 0.08$                            $151.03 \pm 7.59$                       $68.65\% \pm 3.45\%$

TD3-Projection                            $1.28 \pm 0.10$                            $140.90 \pm 10.16$                      $64.04\% \pm 4.62\%$

TD3-Masking                               $1.32 \pm 0.01$                            $147.72 \pm 1.30$                       $67.15\% \pm 0.59\%$

TD3-Random                                $1.33 \pm 0.01$                            $149.42 \pm 1.43$                       $67.92\% \pm 0.65\%$

DQN-Masked                                $1.34 \pm0.01$                             $147.99 \pm 0.61$                       $67.27\% \pm 0.28\%$

PPO                                       $1.39 \pm 0.02$                            $160.93\pm 4.73$                        $73.15\% \pm 2.15\%$

PPO-Projection                            $1.32 \pm 0.02$                            $144.10 \pm 1.31$                       $65.50\% \pm 0.59\%$

PPO-Masking                               $1.34 \pm 0.01$                            $145.96 \pm1.23$                        $66.35\% \pm 0.56\%$

PPO-Random                                $1.34 \pm 0.01$                            $145.39 \pm 0.65$                       $66.08\% \pm 0.30\%$

PPO-Masked                                $1.36 \pm 0.02$                            $144.46 \pm 2.11$                       $65.67\% \pm 0.96\%$

MPS-TD3                                   $1.39 \pm 0.03$                            $144.93 \pm 1.31$                       $65.88\% \pm 0.60\%$

PAM                                       $1.37 \pm 0.03$                            $153.85 \pm 3.87$                       $69.93\% \pm 1.76\%$

Average number of disjoint intervals and size of the action space

1cApproach     1cAverage     1cMinimum     1cMaximum     1cVariance

TD3     $129.19 \pm 11.02$     $119.01 \pm 12.69$     $139.44 \pm 9.35$     $431.86 \pm 66.18$

TD3-Projection     $126.09 \pm 4.88$     $119.3 \pm 2.67$     $132.94 \pm 7.21$     $261.44 \pm 84.26$

TD3-Masking     $130.65 \pm 1.69$     $122.46 \pm 1.99$     $138.91 \pm 1.41$     $319.12 \pm 27.2$

TD3-Random     $131.62 \pm 1.49$     $123.24 \pm 1.65$     $140.04 \pm 1.49$     $331.53 \pm 25.68$

DQN-Masked     $129.89 \pm 1.28$     $121.46 \pm 1.64$     $138.32 \pm 1.07$     $332.14 \pm 31.81$

PPO     $137.77 \pm 4.57$     $126.66 \pm 4.76$     $148.97 \pm 4.42$     $467.54 \pm 25.27$

PPO-Projection     $126.64 \pm 1.10$     $118.44 \pm 1.34$     $134.89 \pm 1.05$     $320.97 \pm 24.38$

PPO-Masking     $127.55 \pm 0.99$     $118.85 \pm 1.16$     $136.30 \pm 0.99$     $353.00 \pm 33.03$

PPO-Random     $126.87 \pm 0.81$     $118.27 \pm 0.98$     $135.53 \pm 0.80$     $339.53 \pm 17.15$

PPO-Masked     $125.10 \pm 2.72$     $116.26 \pm 2.88$     $133.96 \pm 2.57$     $353.42 \pm 15.28$

MPS-TD3     $124.01 \pm 2.39$     $113.57 \pm 3.23$     $134.53 \pm 1.75$     $446.62 \pm 57.25$

PAM     $133.34 \pm 2.92$     $123.84 \pm 2.55$     $142.90 \pm 3.68$     $405.65 \pm 56.05$

Size of the individual intervals

Allowed action space size

Number of intervals

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

On-policy control variables

Allowed action space size

Number of evaluation

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

Off-policy control variables

Allowed action space size

Number of intervals

Average interval length

Minimum interval length

Maximum interval length

Interval length variance

MPS-TD3 and PAM control variables

Maximum reward

Minimum reward

TD3 trajectory examples

Maximum reward

Minimum reward

TD3 with projection trajectory examples

Maximum reward

Minimum reward

TD3 with continuous masking trajectory examples

Maximum reward

Minimum reward

TD3 with random replacement trajectory examples

Maximum reward

Minimum reward

DQN with discrete masking trajectory examples

Maximum reward

Minimum reward

PPO trajectory examples

Maximum reward

Minimum reward

PPO with projection trajectory examples

Maximum reward

Minimum reward

PPO with continuous masking trajectory examples

Maximum reward

Minimum reward

PPO with random replacement trajectory examples

Maximum reward

Minimum reward

PPO with discrete masking trajectory examples

Maximum reward

Minimum reward

MPS-TD3 with random replacement trajectory examples

Maximum reward

Minimum reward

PAM trajectory examples

Welch's t-test p-values between average returns

Welch's t-test p-values between average steps

Welch's t-test p-values between the fractions of solved environments

§ STATEMENT OF AUTHORSHIP

I hereby declare that the paper presented is my own work and that I have not called upon the help of a third
party. In addition, I declare that neither I nor anybody else has submitted this paper or parts of it to obtain
credits elsewhere before. I have clearly marked and acknowledged all quotations or references that have been taken from the works of others. All secondary literature and other sources are marked and listed in the bibliography. The same applies to all charts, diagrams and illustrations as well as to all Internet resources. Moreover, I consent to my paper being electronically stored and sent anonymously in order to be checked for plagiarism. I am aware that if this declaration is not made, the paper may not be graded.

Mannheim, 03.04.2023  Signature