\documentclass[10pt]{article}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[version=4]{mhchem}
\usepackage{stmaryrd}
\usepackage{bbold}

%New command to display footnote whose markers will always be hidden
\let\svthefootnote\thefootnote
\newcommand\blfootnotetext[1]{%
  \let\thefootnote\relax\footnote{#1}%
  \addtocounter{footnote}{-1}%
  \let\thefootnote\svthefootnote%
}

%Overriding the \footnotetext command to hide the marker if its value is `0`
\let\svfootnotetext\footnotetext
\renewcommand\footnotetext[2][?]{%
  \if\relax#1\relax%
    \ifnum\value{footnote}=0\blfootnotetext{#2}\else\svfootnotetext{#2}\fi%
  \else%
    \if?#1\ifnum\value{footnote}=0\blfootnotetext{#2}\else\svfootnotetext{#2}\fi%
    \else\svfootnotetext[#1]{#2}\fi%
  \fi
}

\begin{document}
\section*{Conception : ESSEC BS}
\section*{MATHÉMATIQUES 2 APPLIQUÉES FILIÈRE ÉCONOMIQUE ET COMMERCIALE VOIE GÉNÉRALE}
Vendredi 24 avril 2026 de 14h à 18 h

La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies.\\
Les candidats sont invités à encadrer dans la mesure du possible les résultats de leurs calculs.\\
Aucun document n'est autorisé. L'utilisation de toute calculatrice et de tout matériel électronique est interdite. Seule l'utilisation d'une règle graduée est autorisée.\\
Si au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il la signalera sur sa copie et poursuivra sa composition en expliquant les raisons des initiatives qu'il sera amené à prendre.

Le sujet s'intéresse à un problème dit du "bandit manchot" qui est un exemple d'apprentissage par renforcement.

L'apprentissage par renforcement est un sujet largement utilisé dans le domaine de l'intelligence artificielle. Cela consiste schématiquement à apprendre, à partir d'expériences, quelles actions sont à réaliser pour optimiser une récompense quantitative au cours du temps.

Pour les scripts et fonctions Python, on supposera que les instructions suivantes ont été exécutées :

\begin{verbatim}
import numpy as np,numpy.random as rd
\end{verbatim}

Un aide-mémoire Python et SQL se trouve à la fin de l'énoncé.\\
Les événements et variables aléatoires qui interviennent dans ce problème sont tous et toutes définis sur le même espace probabilisé \((\Omega, \mathcal{A}, \mathbb{P})\).

Si \(X\) est une variable aléatoire réelle sur cet espace, \(\mathbb{E}(X)\) désigne son espérance lorsque celle-ci existe.

Le mot "Fin" marque la fin de l'énoncé.

\section*{Résultats généraux}
On rappelle l'inégalité de Markov :\\
si \(X\) est une variable aléatoire à valeurs positives admettant une espérance et \(a>0\) un réel alors

\[
\mathbb{P}(X \geqslant a) \leqslant \frac{\mathbb{E}(X)}{a}
\]

\begin{itemize}
  \item[1.] Soit \(k \in \mathbb{N}^{*}\) et \(B_{1}, \ldots, B_{k}\) des événements. Montrer que \(\mathbb{P}\left(\bigcup_{i=1}^{k} B_{i}\right) \leqslant \sum_{i=1}^{k} \mathbb{P}\left(B_{i}\right)\).
  \item[-] Soit \(\theta \in[0,1]\).
  \item[2.] On définit pour tout \(t \in \mathbb{R}, f(t)=\frac{t^{2}}{8}+\theta t-\ln \left(1-\theta+\theta \mathrm{e}^{t}\right)\).
  \begin{itemize}
    \item[a)] Montrer que \(f\) est de classe \(C^{2}\) sur \(\mathbb{R}\) et que pour tout \(t\) réel : \(f^{\prime \prime}(t)=\frac{\left(1-\theta-\theta \mathrm{e}^{t}\right)^{2}}{4\left(1-\theta+\theta \mathrm{e}^{t}\right)^{2}}\).
    \item[b)] En déduire que pour tout \(t\) réel, \(f(t) \geqslant 0\) puis que
\[
(1-\theta) \mathrm{e}^{-\theta t}+\theta \mathrm{e}^{(1-\theta) t} \leqslant \exp \left(\frac{t^{2}}{8}\right)
\]
  \end{itemize}
  \item[3.] a) Justifier brièvement que la fonction \(t \mapsto \mathrm{e}^{t}\) est convexe sur \(\mathbb{R}\).
  \begin{itemize}
    \item[b)] En déduire que pour tout \(x \in[-\theta, 1-\theta]\) et \(t \in \mathbb{R}, \mathrm{e}^{t x} \leqslant(\theta+x) \mathrm{e}^{(1-\theta) t}+(1-\theta-x) \mathrm{e}^{-\theta t}\).
  \end{itemize}
  \item[4.] Soit \(X\) une variable aléatoire d'espérance nulle à valeurs dans le segment \([-\theta, 1-\theta]\). En utilisant les deux questions précédentes, montrer que pour tout \(t \in \mathbb{R}, \mathbb{E}\left(\mathrm{e}^{t X}\right)\) existe et
\[
\mathbb{E}\left(\mathrm{e}^{t X}\right) \leqslant \exp \left(\frac{t^{2}}{8}\right)
\]
\end{itemize}

\begin{itemize}
  \item[-] Soit \(n \in \mathbb{N}^{*}\) et \(X_{1}, \ldots, X_{n}\) des variables aléatoires indépendantes à valeurs dans [0, 1] et de même espérance \(\mu\). On définit \(\bar{X}_{n}\) par \(\bar{X}_{n}=\frac{1}{n} \sum_{k=1}^{n} X_{k}\).
  \item[5.] Inégalité de Hoeffding - Soit \(\varepsilon \geqslant 0\).
  \begin{itemize}
    \item[a)] En utilisant l'inégalité de Markov, montrer que, pour tout \(t>0\) :
\[
\mathbb{P}\left(\bar{X}_{n}-\mu \geqslant \varepsilon\right) \leqslant \frac{\mathbb{E}\left(\mathrm{e}^{t\left(\bar{X}_{n}-\mu\right)}\right)}{\mathrm{e}^{t \varepsilon}} \text { puis que } \mathbb{P}\left(\bar{X}_{n}-\mu \geqslant \varepsilon\right) \leqslant \mathrm{e}^{-t \varepsilon} \prod_{k=1}^{n} \mathbb{E}\left(\exp \left(\frac{t}{n}\left(X_{k}-\mu\right)\right)\right)
\]
    \item[b)] En déduire que, pour tout \(t \geqslant 0, \mathbb{P}\left(\bar{X}_{n}-\mu \geqslant \varepsilon\right) \leqslant \exp \left(-t \varepsilon+\frac{t^{2}}{8 n}\right)\), puis en choisissant convenablement \(t\) que
\[
\mathbb{P}\left(\bar{X}_{n}-\mu \geqslant \varepsilon\right) \leqslant \exp \left(-2 n \varepsilon^{2}\right)
\]
  \end{itemize}
  \item[6.] Soit \(\varepsilon \geqslant 0\). En considérant les variables \(1-X_{1}, \ldots, 1-X_{n}\), montrer que
\[
\mathbb{P}\left(\bar{X}_{n}-\mu \leqslant-\varepsilon\right) \leqslant \exp \left(-2 n \varepsilon^{2}\right)
\]
  \item[7.] Soit \(\alpha \in] 0,1\left[\right.\). Si le paramètre \(\mu\) est inconnu et \(X_{1}, \ldots, X_{n}\) suivent la même loi, montrer que \(\left[\bar{X}_{n}-\sqrt{\frac{\ln \left(\frac{2}{\alpha}\right)}{2 n}}, \bar{X}_{n}+\sqrt{\frac{\ln \left(\frac{2}{\alpha}\right)}{2 n}}\right]\) est un intervalle de confiance aléatoire pour l'estimation de \(\mu\) au niveau de confiance \(1-\alpha\).
\end{itemize}

\section*{Description du modèle}
On modélise le problème, évoqué dans le préambule, de la manière suivante :\\
\(n\) et \(r\) sont des entiers naturels plus grands que 2 et \(r<n\).\\
Les actions sont identifiées aux entiers de 1 à \(r\) et \(n\) actions sont réalisées l'une après l'autre et numérotées de 1 à \(n\).\\
\(p_{1}, \ldots, p_{r}\) sont des réels appartenant à ]0, 1[ non tous égaux et on note \(p^{*}\) leur maximum.\\
On définit, pour tout le sujet, les variables aléatoires suivantes :

\begin{itemize}
  \item[-] Le choix des actions : \(\left(I_{j}\right)_{j \in \llbracket 1, n \rrbracket}\) à valeurs dans \(\llbracket 1, r \rrbracket, I_{j}\) est égale à la \(j\)-ème action réalisée.
  \item[-] Les récompenses aléatoires proposées : \(\left(X_{i, j}\right)_{i \in[1, r], j \in \llbracket 1, n \rrbracket}\) sont des variables de Bernoulli indépendantes telles que pour tout \(i \in \llbracket 1, r \rrbracket, j \in \llbracket 1, n \rrbracket, X_{i, j}\) est de paramètre \(p_{i}\).\\
\(X_{i, j}\) est la récompense aléatoire pour l'action \(i\) lorsque celle-ci est effectuée pour la \(j\)-ième fois.\\
On suppose que les \(\left(X_{i, j}\right)_{i \in \llbracket 1, r \rrbracket, j \in \llbracket 1, n \rrbracket}\) sont indépendantes des \(\left(I_{j}\right)_{j \in \llbracket 1, n \rrbracket}\).
  \item[-] \(Y_{j}\) est la variable aléatoire égale à la récompense pour la \(j\)-ème action réalisée, \(j \in \llbracket 1, n \rrbracket\).
  \item[-] Par exemple, si pour un certain \(\omega \in \Omega\), les quatre premières actions réalisées sont 2, 4, 3 et 2, alors on a :
\[
\begin{aligned}
& I_{1}(\omega)=2, I_{2}(\omega)=4, I_{3}(\omega)=3, I_{4}(\omega)=2, Y_{1}(\omega)=X_{2,1}(\omega), Y_{2}(\omega)=X_{4,1}(\omega), \\
& Y_{3}(\omega)=X_{3,1}(\omega), Y_{4}(\omega)=X_{2,2}(\omega) .
\end{aligned}
\]
\end{itemize}

\begin{itemize}
  \item[-] Pour tous \(i \in \llbracket 1, r \rrbracket, j \in \llbracket 1, n \rrbracket\) et \(\omega \in \Omega, N_{i, j}(\omega)\) est égal au nombre d'indices \(k \in \llbracket 1, j \rrbracket\) tels que \(I_{k}(\omega)=i\).
  \item[-] Pour \(i \in \llbracket 1, r \rrbracket, j \in \llbracket 1, n \rrbracket\) et \(\omega \in \Omega, \bar{X}_{i, j}(\omega)=\frac{1}{j} \sum_{k=1}^{j} X_{i, k}(\omega)\) et
\[
\hat{X}_{i, j}(\omega)= \begin{cases}\frac{1}{N_{i, j}(\omega)} \sum_{k=1}^{N_{i, j}(\omega)} X_{i, k}(\omega) & \text { si } N_{i, j}(\omega) \neq 0 \\ 0 & \text { sinon } .\end{cases}
\]
\end{itemize}

L'objectif est de maximiser, en moyenne, la récompense totale en définissant les variables \(I_{j}\) pour ce faire. Ces définitions constituent la définition d'une stratégie.

\section*{Utilisation d'une table SQL}
On a réalisé l'expérience décrite dans le modèle ci-dessus et enregistré les résultats obtenus dans une table Bandit.

Précisément cette table est composé de \(n\) enregistrements, \(n \geqslant 1000\). Elle comporte trois champs, Numero , Action et Recompense qui sont de type entier.

Si par exemple la dixième action réalisée est l'action 2 générant une récompense égale à 1, ceci est représenté par la ligne (10, 2, 1) dans la table.

Cette table est associée à un élément \(\omega\) de \(\Omega\).

\begin{itemize}
  \item[8.] a) Quelle requête renvoie \(I_{100}(\omega)\) lorsqu'on l'exécute ?
  \begin{itemize}
    \item[b)] Quelle requête renvoie la colonne des numéros des actions où on a réalisé l'action 2 et obtenu une récompense non nulle?
    \item[c)] Ecrire une requête qui renvoie \(N_{1,100}(\omega)\).
    \item[d)] Ecrire une requête qui renvoie \(\hat{X}_{2, n}(\omega)\). Si l'on a \(N_{2, n}(\omega) \geqslant 100\), de quel paramètre \(\hat{X}_{2, n}(\omega)\) est-elle une bonne estimation?
  \end{itemize}
\end{itemize}

\section*{La stratégie ETC \({ }^{\mathbf{1}}\) et une majoration de son regret moyen}
On note \(R_{n}\) la récompense totale après que les \(n\) actions sont exécutées, \(R_{n}=\sum_{j=1}^{n} Y_{j}\).

\begin{itemize}
  \item[9.] Soit \(j \in \llbracket 1, n \rrbracket\).
  \begin{itemize}
    \item[a)] Montrer que, \(\mathbb{E}\left(Y_{j}\right)=\sum_{i=1}^{r} \mathbb{P}\left(\left[Y_{j}=1\right] \cap\left[I_{j}=i\right]\right)\).
    \item[b)] Etablir que \(\mathbb{P}\left(\left[Y_{j}=1\right] \cap\left[I_{j}=i\right]\right)=\sum_{k=1}^{j} \mathbb{P}\left(\left[X_{i, k}=1\right] \cap\left[I_{j}=i\right] \cap\left[N_{i, j}=k\right]\right)\).
    \item[c)] En déduire que \(\mathbb{E}\left(Y_{j}\right)=\sum_{i=1}^{r} p_{i} \mathbb{P}\left(I_{j}=i\right)\) puis que \(\mathbb{E}\left(Y_{j}\right) \leqslant p^{*}\).
  \end{itemize}
  \item[-] On définit le regret \(\Delta_{n}=n p^{*}-R_{n}\) et on pose pour tout \(i \in \llbracket 1, r \rrbracket, \delta_{i}=p^{*}-p_{i}\).
  \item[10.] a) Soit \(i \in \llbracket 1, r \rrbracket\). Montrer que \(\mathbb{E}\left(N_{i, n}\right)=\sum_{j=1}^{n} \mathbb{P}\left(I_{j}=i\right)\).
\end{itemize}

\footnotetext{\begin{enumerate}
  \item Explore then commit
\end{enumerate}
}
\begin{itemize}
  \item[]
  \begin{itemize}
    \item[b)] En déduire que \(\mathbb{E}\left(\Delta_{n}\right)=\sum_{i=1}^{r} \delta_{i} \mathbb{E}\left(N_{i, n}\right)\).
  \end{itemize}
  \item[11.] Stratégie "No Strategy" - On suppose dans cette question que pour tout \(j \in \llbracket 1, n \rrbracket, I_{j}\) suit la loi uniforme sur \(\llbracket 1, r \rrbracket\). Calculer \(\mathbb{E}\left(\Delta_{n}\right)\) en fonction de \(n, r\) et des \(\delta_{i}\).
  \item[-] Stratégie "ETC" - On suppose que \(m\) est un entier plus grand que 2 tel que \(r m<n\). On définit une nouvelle variable aléatoire \(Z_{m}\) par, pour tout \(\omega \in \Omega\) :\\
\(Z_{m}(\omega)\) est égal au plus petit indice \(k \in \llbracket 1, r \rrbracket\) pour lequel on a \(\hat{X}_{k, m r}(\omega)=\max _{1 \leqslant i \leqslant r} \hat{X}_{i, m r}(\omega)\).\\
La stratégie ETC consiste à définir les \(I_{j}\) comme suit pour tout \(j \in \llbracket 1, n \rrbracket\) et pour tout \(\omega \in \Omega\) :
  \begin{itemize}
    \item[-] si \(j \in \llbracket 1, m \rrbracket\) alors \(I_{j}(\omega)=1\), si \(j \in \llbracket m+1,2 m \rrbracket\) alors \(I_{j}(\omega)=2, \ldots\), si \(j \in \llbracket(k-1) m+1, k m \rrbracket\) alors \(I_{j}(\omega)=k, \ldots\), si \(j \in \llbracket(r-1) m+1, r m \rrbracket\) alors \(I_{j}(\omega)=r\),
    \item[-] si \(m r<j \leqslant n, I_{j}(\omega)=Z_{m}(\omega)\).
  \end{itemize}
\end{itemize}


On suppose dans la suite de cette partie que l'on applique la stratégie ETC.

\begin{itemize}
  \item[12.] Dans cette question \(n=10, r=3, m=2\), on réalise les 10 actions en appliquant la stratégie ETC et on obtient le tableau suivant :

\begin{tabular}[t]{|l|l|l|l|l|l|l|l|l|l|l|}
\hline
\(j\) & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
\(I_{j}(\omega)\) & 1 & 1 & 2 & 2 & 3 & 3 & ... & ... & ... & ... \\
\hline
\(Y_{j}(\omega)\) & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 \\
\hline
\end{tabular}

Préciser alors les valeurs de \(\hat{X}_{1,6}(\omega), \hat{X}_{2,6}(\omega), \hat{X}_{3,6}(\omega)\) et \(Z_{2}(\omega)\). En déduire par quelle(s) valeur(s) il faut compléter la deuxième ligne du tableau.
  \item[13.] Écrire une fonction Python \(\mathrm{Z}(\mathrm{m}, \mathrm{r}\), Rec \()\) qui renvoie la valeur de \(Z_{m}\) obtenue lorsque la variable Rec est le vecteur des récompenses obtenues pour les \(r m\) premières actions suivant la stratégie ETC.
  \item[14.] Soit \(i \in \llbracket 1, r \rrbracket\).
  \begin{itemize}
    \item[a)] Que vaut \(N_{i, m r}\) ? En déduire que, \(\hat{X}_{i, m r}=\bar{X}_{i, m}\).
    \item[b)] En déduire que pour tout \(\varepsilon \geqslant 0\),
\[
\mathbb{P}\left(\hat{X}_{i, m r}-p_{i} \geqslant \varepsilon\right) \leqslant \exp \left(-2 m \varepsilon^{2}\right) \text { et } \mathbb{P}\left(\hat{X}_{i, m r}-p_{i} \leqslant-\varepsilon\right) \leqslant \exp \left(-2 m \varepsilon^{2}\right)
\]
  \end{itemize}
  \item[15.] On note \(s\) un élément de \(\llbracket 1, r \rrbracket\) tel que \(p_{s}=p^{*}\). Soit \(i \in \llbracket 1, r \rrbracket\).
  \begin{itemize}
    \item[a)] Montrer que \(\mathbb{E}\left(N_{i, n}\right)=m+(n-m r) \mathbb{P}\left(Z_{m}=i\right)\).\\
En déduire que : \(\mathbb{E}\left(N_{i, n}\right) \leqslant m+(n-m r) \mathbb{P}\left(\hat{X}_{i, m r} \geqslant \hat{X}_{s, m r}\right)\)
    \item[b)] Montrer que \(\mathbb{P}\left(\hat{X}_{i, m r} \geqslant \hat{X}_{s, m r}\right) \leqslant \mathbb{P}\left(\hat{X}_{i, m r}-p_{i} \geqslant \frac{\delta_{i}}{2}\right)+\mathbb{P}\left(p_{s}-\hat{X}_{s, m r} \geqslant \frac{\delta_{i}}{2}\right)\).
    \item[c)] En conclure que :
\[
\mathbb{E}\left(N_{i, n}\right) \leqslant m+2(n-m r) \exp \left(-m \frac{\delta_{i}^{2}}{2}\right) \leqslant m+2 n \exp \left(-m \frac{\delta_{i}^{2}}{2}\right)
\]
  \end{itemize}
  \item[16.] a) Établir que :
\[
\mathbb{E}\left(\Delta_{n}\right) \leqslant m \sum_{i=1}^{r} \delta_{i}+2 n \sum_{i=1}^{r} \delta_{i} \exp \left(-m \frac{\delta_{i}^{2}}{2}\right)
\]
\end{itemize}

\begin{itemize}
  \item[]
  \begin{itemize}
    \item[] ▷ On pose \(\alpha=\sum_{i=1}^{r} \delta_{i}\) et \(\beta=\sum_{1 \leqslant i \leqslant r, \delta_{i} \neq 0} \frac{1}{\delta_{i}}\).
    \item[b)] Montrer que pout tout \(x>0, \mathrm{e}^{-x} \leqslant \frac{1}{x \mathrm{e}}\). En déduire que \(\mathbb{E}\left(\Delta_{n}\right) \leqslant m \alpha+2 n \frac{\beta}{m}\).
    \item[c)] En choisissant \(m=\left\lfloor\sqrt{\frac{2 n \beta}{\alpha}}\right\rfloor+1\), montrer que pour \(n\) assez grand, \(m \geqslant 2, m r<n\) et que
\[
\mathbb{E}\left(\Delta_{n}\right) \leqslant \sqrt{8 \alpha \beta} \sqrt{n}+\alpha
\]
  \end{itemize}
\end{itemize}

\section*{La stratégie UCB \({ }^{\mathbf{2}}\) et une majoration de son regret}
On conserve les notations de la partie précédente mais on va redéfinir les variables \(I_{j}\).

\begin{itemize}
  \item[17.] Soit \(\theta \in] 0,1\left[, j \in \llbracket 1, n \rrbracket\right.\) et \(i \in \llbracket 1, r \rrbracket\), on pose \(\gamma=\sqrt{\frac{-\ln (\theta)}{2 j}}\). Montrer que \(\mathbb{P}\left(\bar{X}_{i, j}+\gamma \leqslant p_{i}\right) \leqslant \theta\).
  \item[-] La stratégie UCB consiste à définir les \(I_{j}\) comme suit pour tout \(j \in \llbracket 1, n \rrbracket\) et pour tout \(\omega \in \Omega\) :
  \begin{itemize}
    \item[-] si \(j \in \llbracket 1, r \rrbracket\) alors \(I_{j}(\omega)=j\);
    \item[-] si \(j \in \llbracket r, n-1 \rrbracket\), posons pour tout \(i \in \llbracket 1, r \rrbracket, U_{i, j}(\omega)=\hat{X}_{i, j}(\omega)+\sqrt{\frac{\ln (n)}{N_{i, j}(\omega)}}\). \(I_{j+1}(\omega)\) est égal au plus petit indice \(i \in \llbracket 1, r \rrbracket\) pour lequel on a \(U_{i, j}(\omega)=\max _{1 \leqslant k \leqslant r} U_{k, j}(\omega)\).
    \item[-] On note aussi pour \(i \in \llbracket 1, r \rrbracket\) et \(j \in \llbracket 1, n-1 \rrbracket, V_{i, j}(\omega)=\bar{X}_{i, j}(\omega)+\sqrt{\frac{\ln (n)}{j}}\).
  \end{itemize}
\end{itemize}

On suppose dans la suite de cette partie que l'on applique la stratégie UCB.

\begin{itemize}
  \item[18.] a) Justifier que pour \(i \in \llbracket 1, r \rrbracket\) on a \(N_{i, r}=1\) et \(\hat{X}_{i, r}=X_{i, 1}\).
  \begin{itemize}
    \item[b)] Ecrire une fonction Python Bernoulli(p) qui renvoie la valeur d'une simulation d'une variable aléatoire suivant la loi de Bernoulli de paramètre \(p\).
    \item[c)] En supposant que hatX contient \(\hat{X}_{i, j}, \mathrm{~N}\) contient \(N_{i, j}\) et le vecteur P contient les valeurs de \(p_{1}, \ldots, p_{r}\), écrire une fonction Python maj(hatX, N, i, P) qui simule la récompense de l'action \(i\), celle-ci étant \((j+1)\)-ème action réalisée et renvoie la valeur de \(\hat{X}_{i, j+1}\) dans ces conditions.
  \end{itemize}
  \item[19.] Compléter l'écriture de la fonction Python Actions(P,n) ci-dessous pour qu'elle renvoie la simulation d'un vecteur des \(n\) actions réalisées par l'algorithme UCB si le vecteur P contient les valeurs de \(p_{1}, \ldots, p_{r}\).
\begin{verbatim}
def Actions(P,n):
    r=np.shape(P)[0]; I=np.zeros(n)
    I[0:r]=[k+1 for k in range(r)];N=np.ones(r)
    hatX=np.array([Bernoulli(P[i]) for i in range(r)])
    for j in range(...,...):
        Max=hatX[0]+np.sqrt(np.log(n)/N[0])
        I[j]=1
\end{verbatim}


\end{itemize}

\footnotetext{\begin{enumerate}
  \setcounter{enumi}{1}
  \item Upper confidence bound
\end{enumerate}
}\begin{verbatim}
    for k in range(1,r):
        val=hatX[k]+np.sqrt(np.log(n)/N[k])
        if val>Max:
            Max=...
            I[j]=...
    hatX[I[j]-1]=maj(hatX[I[j]-1],N[I[j]-1],I[j],P)
    N[I[j]-1]=...
return I
\end{verbatim}

\begin{itemize}
  \item Dans la suite de l'énoncé, on considère \(s \in \llbracket 1, r \rrbracket\) tel que \(p^{*}=p_{s}, i \in \llbracket 1, r \rrbracket\) tel que \(p_{i}<p^{*}\) et \(u \in \llbracket 1, n-1 \rrbracket\). On note \(A_{i, u}\) l'événement \(\left[\min _{j \in \llbracket r, n-1 \rrbracket} U_{s, j} \leqslant p_{s}\right] \cup\left[V_{i, u} \geqslant p_{s}\right]\).
\end{itemize}

\begin{enumerate}
  \setcounter{enumi}{19}
  \item Majoration de \(\mathbb{E}\left(N_{i, n}\right)\)
\end{enumerate}

\begin{itemize}
  \item[a)] Montrer que si \(\left[N_{i, n}>u\right]\) est réalisé alors il existe \(k \in \llbracket r, n-1 \rrbracket\) tel que \(\left[N_{i, k}=u\right] \cap\left[U_{i, k} \geqslant U_{s, k}\right]\) est réalisé, puis que \(\left[V_{i, u} \geqslant \min _{j \in \llbracket r, n-1 \rrbracket} U_{s, j}\right]\) l'est.
  \item[b)] Montrer que si \(\left[N_{i, n}>u\right]\) est réalisé alors \(A_{i, u}\) l'est. En déduire que
\[
\mathbb{E}\left(N_{i, n}\right) \leqslant u+\mathbb{P}\left(A_{i, u}\right) n
\]
\end{itemize}

\begin{enumerate}
  \setcounter{enumi}{20}
  \item Majoration de \(\mathbb{P}\left(A_{i, u}\right)\)
\end{enumerate}

\begin{itemize}
  \item[a)] Montrer en utilisant la question 17 que :
\[
\mathbb{P}\left(\min _{j \in \llbracket r, n-1 \rrbracket} U_{s, j} \leqslant p_{s}\right) \leqslant \mathbb{P}\left(\min _{k \in \llbracket 1, n-1 \rrbracket} V_{s, k} \leqslant p_{s}\right) \leqslant \frac{1}{n}
\]
  \item[b)] Etablir que si \(\delta_{i}-\sqrt{\frac{\ln (n)}{u}} \geqslant 0, \mathbb{P}\left(V_{i, u} \geqslant p_{s}\right) \leqslant \exp \left(-2 u\left(\delta_{i}-\sqrt{\frac{\ln (n)}{u}}\right)^{2}\right)\).
  \item[-] On suppose dans la suite que \(n\) est assez grand pour que \(\frac{4 \ln (n)}{\delta_{i}^{2}} \in[1, n-2]\). On choisit \(\left\lfloor\frac{4 \ln (n)}{\delta_{i}^{2}}\right\rfloor+1\) comme valeur de \(u\) pour la suite de cette question.
  \item[c)] Montrer que la fonction \(\varphi: t \mapsto \exp \left(-2\left(\delta_{i} \sqrt{t}-\sqrt{\ln (n)}\right)^{2}\right)\) est décroissante sur \(\left[\frac{\ln (n)}{\delta_{i}^{2}},+\infty[\right.\).
  \item[d)] En déduire que \(\mathbb{P}\left(V_{i, u} \geqslant p_{s}\right) \leqslant \frac{1}{n^{2}}\) puis que \(\mathbb{P}\left(A_{i, u}\right) \leqslant \frac{2}{n}\).
\end{itemize}

\begin{enumerate}
  \setcounter{enumi}{21}
  \item Etablir que \(\mathbb{E}\left(N_{i, n}\right) \leqslant \frac{4 \ln (n)}{\delta_{i}^{2}}+3\) puis que \(\mathbb{E}\left(\Delta_{n}\right) \leqslant 4 \beta \ln (n)+3 \alpha\).
\end{enumerate}

\section*{Aide-mémoire}
Toutes les fonctions et instructions présentées ne sont pas utiles et il est possible d'utiliser d'autres fonctions ou instructions absentes de cet aide-mémoire.

Listes

\begin{itemize}
  \item[]
  \begin{itemize}
    \item[]
    \begin{itemize}
      \item[] [] Créer une liste vide
    \end{itemize}
  \end{itemize}
  \item[] [a]\textit{n ou n}[a] Créer une liste avec \(n\) fois l'élément a
  \begin{itemize}
    \item[L.] append(a) Ajoute l'élément a à la fin de la liste L
    \begin{itemize}
      \item[] L1 + L2 Concatène les deux listes L1 et L2
      \begin{itemize}
        \item[] len(L) Renvoie le nombre d'éléments de la liste L
      \end{itemize}
    \end{itemize}
    \item[L.] count(a) Renvoie le nombre d'occurences de a dans la liste L
    \item[L.] remove(a) Enlève la première occurence de la valeur a de la liste L
    \begin{itemize}
      \item[]
      \begin{itemize}
        \item[a] in L Vaut True si a se trouve au moins une fois dans L et False sinon
      \end{itemize}
    \end{itemize}
  \end{itemize}
\end{itemize}

Module mathématique numpy de Python

\begin{verbatim}
import numpy as np
                np.array(L) Transforme la liste L en vecteur ou matrice numpy
    np.zeros([n,m]) Crée la matrice nulle de taille n x m
                np.zeros(n) Crée le vecteur nul de taille n
                    np.sqrt(x) Renvoie (x) si x 2 
                        np.log(x) Renvoie ln(x) si x> 0
\end{verbatim}

Sous module random de numpy pour la simulation probabiliste

\begin{verbatim}
import numpy.random as rd
    rd.randint(a,b,[r,s]) Simule une réalisation d'une matrice (r,s) dont les coefficients sont des variables
                    aléatoires indépendantes qui suivent la loi uniforme discrète U( [ a,b 1])
\end{verbatim}

Si le paramètre [r,s] est remplacé par r, cette fonction renvoie une réalisation d'un vecteur de longueur r correspondant à la loi en question, et si ce paramètre est omis, elles renvoient un seul coefficient suivant les mêmes contraintes.

Sous module graphique pyplot de matplotlib

\begin{verbatim}
import matplotlib.pyplot as plt
    plt.plot(X,Y,options) Crée la courbe des points définis par les listes X, abscisses, et Y, ordonnées
                    suivant les options graphiques définies par la chaîne de caractères facultative options
        plt.xlim(xmin,xmax) Fixe les bornes de l'axe des abscisses
        plt.ylim(ymin,ymax) Fixe les bornes de l'axe des ordonnées
                plt.show() Affiche le graphique
                plt.grid() Affiche un quadrillage
\end{verbatim}

Fin

\begin{enumerate}
  \item 
\end{enumerate}

\begin{enumerate}
  \setcounter{enumi}{1}
  \item 
\end{enumerate}


\end{document}