Connectez-vous pour consulter le corrigé.
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 suppose que les
instructions suivantes ont été exécutées :
import numpy as np import numpy.random as rd
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é.
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}\]
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(B_i)\]
Soit \(\theta\in[0,1]\).
On définit pour tout \(t\in\mathbb R\), \(\displaystyle f(t)=\frac{t^2}{8}+\theta t-\ln \! \left(1-\theta+\theta \,\mathrm{e}^t\right)\).
Montrer que \(f\) est de classe \(\mathcal C^2\) sur \(\mathbb R\) et que, pour tout réel \(t\), \[f''(t)=\frac{(1-\theta-\theta \,\mathrm{e}^t)^2}{4 \left( 1-\theta+\theta \,\mathrm{e}^t \right)^2}\]
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)\]
Justifier brièvement que la fonction \(x\mapsto \,\mathrm{e}^{tx}\) est convexe sur \(\mathbb R\).
En déduire que pour tout \(x\in[-\theta,1-\theta]\) et \(t\in\mathbb R\), \[\,\mathrm{e}^{tx}\leqslant (\theta+x)\,\mathrm{e}^{(1-\theta)t}+(1-\theta-x)\,\mathrm{e}^{-\theta t}\]
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(\mathrm{e}^{tX})\) existe et \[\mathbb E(\mathrm{e}^{tX})\leqslant \exp \! \left(\frac{t^2}{8}\right)\]
Soit \(n \in\mathbb{N}^\ast\) 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 \(\overline{X}_n\) par : \[\overline X_n=\frac1n\sum_{k=1}^n X_k\]
Inégalité de Hoeffding - Soit \(\varepsilon \geqslant 0\).
En utilisant l’inégalité de Markov, montrer que, pour tout \(t>0\), \[\mathbb P(\overline X_n-\mu\geqslant \varepsilon) \leqslant \frac{\mathbb E(\,\mathrm{e}^{t( \overline{X_n} -\mu)})}{\,\mathrm{e}^{t\varepsilon}}\] puis que \[\mathbb P(\overline X_n-\mu\geqslant \varepsilon) \leqslant \,\mathrm{e}^{-t\varepsilon}\prod_{k=1}^n \mathbb E \! \left( \exp \! \left( \frac{t}{n} \left( X_k - \mu \right) \right) \right)\]
En déduire que, pour tout \(\varepsilon\geqslant 0\), \[\mathbb P(\overline X_n-\mu\geqslant \varepsilon) \leqslant \exp \! \left(-t\varepsilon+\frac{t^2}{8n}\right)\] puis, en choisissant \(t\) convenablement, que \[\mathbb P(\overline X_n-\mu\geqslant \varepsilon) \leqslant \exp(-2n\varepsilon^2)\]
Soit \(\varepsilon\geqslant 0\). En considérant les variables \(1-X_1,\ldots,1-X_n\), montrer que \[\mathbb P(\overline X_n-\mu\leqslant -\varepsilon)\leqslant \exp(-2n\varepsilon^2)\]
Soit \(\alpha\in \left] 0,1 \right[\). Si le paramètre \(\mu\) est inconnu et \(X_1,\ldots,X_n\) suivent la même loi, montrer que \[\left[\overline X_n-\sqrt{\frac{\ln \! \left(\frac2\alpha\right)}{2n}},\overline X_n+\sqrt{\frac{\ln \! \left(\frac2\alpha\right)}{2n}}\right]\] est un intervalle de confiance aléatoire pour l’estimation de \(\mu\) au niveau de confiance \(1-\alpha\).
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 \(1\) avec \(r\leqslant 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 :
Le choix des actions : \((I_j)_{j\in\left[\!\left[1,n\right]\!\right]}\) à valeurs dans \(\left[\!\left[1,r\right]\!\right]\), \(I_j\) est égale à la \(j\)-ème action réalisée.
Les récompenses aléatoires proposées : \((X_{i,j})_{(i,j)\in\left[\!\left[1,r\right]\!\right]\times\left[\!\left[1,n\right]\!\right]}\) sont des variables de Bernoulli indépendantes telles que pour tout \(i\in\left[\!\left[1,r\right]\!\right]\) et \(j\in\left[\!\left[1,n\right]\!\right]\), \(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 sélectionnée pour la \(j\)-ème fois.
On suppose que les \((X_{i,j})_{(i,j)\in\left[\!\left[1,r\right]\!\right]\times\left[\!\left[1,n\right]\!\right]}\) sont indépendantes des \((I_j)_{j\in\left[\!\left[1,n\right]\!\right]}\).
\(Y_j\) est la variable aléatoire égale à la récompense aléatoire pour la \(j\)-ème action réalisée, \(j\in\left[\!\left[1,n\right]\!\right]\).
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 \[I_1(\omega)=2,\quad I_2(\omega)=4,\quad I_3(\omega)=3,\quad I_4(\omega)=2,\] \[Y_1(\omega)=X_{2,1}(\omega),\quad Y_2(\omega)=X_{4,1}(\omega),\quad Y_3(\omega)=X_{3,1}(\omega),\quad Y_4(\omega)=X_{2,2}(\omega)\]
Pour tous \(i\in\left[\!\left[1,r\right]\!\right]\), \(j\in\left[\!\left[1,n\right]\!\right]\) et \(\omega\in\Omega\), \(N_{i,j}(\omega)\) est égal au nombre d’indices \(k\in\left[\!\left[1,j\right]\!\right]\) tels que \(I_k(\omega)=i\).
Pour \(i\in\left[\!\left[1,r\right]\!\right]\), \(j\in\left[\!\left[1,n\right]\!\right]\) et \(\omega\in\Omega\), \[\overline X_{i,j}(\omega)=\frac1j\sum_{k=1}^j X_{i,k}(\omega)\] et \[\widehat X_{i,j}(\omega)= \begin{cases} \dfrac1{N_{i,j}(\omega)}\displaystyle\sum_{k=1}^{N_{i,j}(\omega)} X_{i,k}(\omega)&\text{si }N_{i,j}(\omega)\neq0\\[1em] 0&\text{sinon} \end{cases}\]
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.
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ée 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 \(w\) de \(\Omega\).
Quelle requête renvoie \(I_{100}(\omega)\) lorsqu’on l’exécute ?
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 ?
Écrire une requête qui renvoie \(N_{1,100}(\omega)\).
Écrire une requête qui renvoie \(\widehat X_{2,n}(\omega)\). Si l’on a \(N_{2,n}(\omega)\geqslant 100\), de quel paramètre \(\widehat X_{2,n}(\omega)\) est-elle une bonne estimation ?
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\]
Soit \(j\in\left[\!\left[1,n\right]\!\right]\).
Montrer que \[\mathbb E(Y_j)=\sum_{i=1}^r \mathbb P([Y_j=1]\cap[I_j=i])\]
Établir que \[\mathbb P([Y_j=1]\cap[I_j=i])=\sum_{k=1}^j \mathbb P([X_{i,k}=1]\cap[I_j=i]\cap[N_{i,j}=k])\]
En déduire que \[\mathbb E(Y_j)=\sum_{i=1}^r p_i \, \mathbb P(I_j=i)\] puis que \(\mathbb E(Y_j)\leqslant p^*\).
On définit le regret \(\Delta_n=np^*-R_n\) et on pose, pour tout \(i\in\left[\!\left[1,r\right]\!\right]\), \(\delta_i=p^*-p_i\).
Soit \(i\in\left[\!\left[1,r\right]\!\right]\). Montrer que \[\mathbb E(N_{i,n})=\sum_{j=1}^n \mathbb P(I_j=i)\]
En déduire que \[\mathbb E(\Delta_n)=\sum_{i=1}^r \delta_i \, \mathbb E(N_{i,n})\]
Stratégie « No Strategy » - On suppose dans cette question que pour tout \(j\in\left[\!\left[1,n\right]\!\right]\), \(I_j\) suit la loi uniforme sur \(\left[\!\left[1,r\right]\!\right]\). Calculer \(\mathbb E(\Delta_n)\) en fonction de \(n\), \(r\) et des \(\delta_i\).
Stratégie « ETC » - On suppose que \(m\) est un entier plus grand que \(2\) tel que \(rm<n\).
On définit une nouvelle variable aléatoire \(Z_m\) par, pour tout \(w\in\Omega\), \(Z_m(w)\) est égal au plus petit indice \(k\in\left[\!\left[1,r\right]\!\right]\) pour lequel on a \(\displaystyle \widehat X_{k,mr}(w)=\max_{1\leqslant i\leqslant r}\widehat X_{i,mr}(w)\).
La stratégie ETC consiste à définir les \(I_j\) comme suit pour tout \(j\in\left[\!\left[1,n\right]\!\right]\) et pour tout \(w\in\Omega\) :
si \(j\in\left[\!\left[1,rm\right]\!\right]\), alors \(I_j(w)=i\) si \(j\in\left[\!\left[(i-1)m+1,im\right]\!\right]\) ;
si \(rm<j\leqslant n\), \(I_j(w)=Z_m(w)\).
On suppose dans la suite de cette partie que l’on applique la stratégie ETC.
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{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline j&1&2&3&4&5&6&7&8&9&10\\ \hline I_j(w)&1&1&2&2&3&3&\cdots&\cdots&\cdots&\cdots\\ \hline Y_j(w)&0&1&1&1&0&0&1&0&1&1 \\ \hline \end{array}\] Préciser alors les valeurs de \(\widehat X_{1,6}(w)\), \(\widehat X_{2,6}(w)\) et \(\widehat X_{3,6}(w)\) et \(Z_2(w)\). En déduire par quelle(s) valeur(s) il faut compléter la deuxième ligne du tableau.
Écrire une fonction Python Z(m,r,Rec) qui renvoie la
valeur de \(Z_m\) obtenue lorsque la
variable Rec est le vecteur des récompenses obtenues pour
les \(rm\) premières actions suivant la
stratégie ETC.
Soit \(i\in\left[\!\left[1,r\right]\!\right]\).
Que vaut \(N_{i,mr}\) ? En déduire que \(\widehat X_{i,mr}=\overline X_{i,m}\).
En déduire que pour tout \(\varepsilon\geqslant 0\), \[\mathbb P(\widehat X_{i,mr}-p_i\geqslant \varepsilon)\leqslant \exp(-2m\varepsilon^2) \quad\text{et}\quad \mathbb P(\widehat X_{i,mr}-p_i<-\varepsilon)\leqslant \exp(-2m\varepsilon^2)\]
On note \(s\) un élément de \(\left[\!\left[1,r\right]\!\right]\) tel que \(p_s=p^*\). Soit \(i\in\left[\!\left[1,r\right]\!\right]\).
Montrer que \(\mathbb E(N_{i,n})=m+ \left( n-rm \right) \mathbb P(Z_m=i)\).
En déduire que \[\mathbb E(N_{i,n})\leqslant m+ \left( n-rm \right) \mathbb P(\widehat X_{i,mr}\geqslant \widehat X_{s,mr})\]
Montrer que \[\mathbb P(\widehat X_{i,mr}\geqslant \widehat X_{s,mr}) \leqslant \mathbb P \! \left(\widehat X_{i,mr}-p_i\geqslant \frac{\delta_i}{2}\right) + \mathbb P \! \left(p_s-\widehat X_{s,mr}\geqslant \frac{\delta_i}{2}\right)\]
En conclure que \[\mathbb E(N_{i,n})\leqslant m+2 \left( n-rm \right) \exp \! \left(-m \, \frac{\delta_i^2}{2}\right) \leqslant m+2n\exp \! \left(-m \, \frac{\delta_i^2}{2}\right)\]
Établir que \[\mathbb E(\Delta_n)\leqslant m\sum_{i=1}^r\delta_i+2n\sum_{i=1}^r \delta_i\exp \! \left(-m \, \frac{\delta_i^2}{2}\right)\]
On pose \[\alpha=\sum_{i=1}^r\delta_i \quad\text{et}\quad \beta=\sum_{\substack{i\in\left[\!\left[1,r\right]\!\right]\\ \delta_i>0}}\frac1{\delta_i}\] Montrer que pour tout \(x>0\), \(\displaystyle \mathrm{e}^{-x}\leqslant \frac1{\mathrm{e}x}\). En déduire que \[\mathbb E(\Delta_n)\leqslant m\alpha+2n \, \frac{\beta}{m}\]
En choisissant \(m=\left\lfloor\sqrt{\dfrac{2n\beta}{\alpha}}\right\rfloor+1\), montrer que pour \(n\) assez grand, \(m\geqslant2\), \(mr<n\) et que : \[\mathbb E(\Delta_n)\leqslant \sqrt{8\alpha\beta}\sqrt n+\alpha\]
On conserve les notations de la partie précédente mais on va redéfinir les variables \(I_j\).
Soit \(\theta\in \left] 0,1 \right[\), \(j\in\left[\!\left[1,n\right]\!\right]\) et \(i\in\left[\!\left[1,r\right]\!\right]\). On pose \[\gamma=\sqrt{-\frac{\ln(\theta)}{2j}}\] Montrer que \(\mathbb P(\overline X_{i,j}+\gamma\leqslant p_i)\leqslant \theta\).
La stratégie UCB consiste à définir les \(I_j\) comme suit pour tout \(j\in\left[\!\left[1,n\right]\!\right]\) et pour tout \(\omega\in\Omega\) :
si \(j\in\left[\!\left[1,r\right]\!\right]\) alors \(I_j(\omega)=j\) ;
si \(j\in\left[\!\left[r,n-1\right]\!\right]\), posons pour tout \(i\in\left[\!\left[1,r\right]\!\right]\), \[U_{i,j}(\omega)=\widehat X_{i,j}(\omega)+\sqrt{\frac{\ln(n)}{N_{i,j}(\omega)}}\] \(I_{j+1}(\omega)\) est égal au plus petit indice \(i\in\left[\!\left[1,r\right]\!\right]\) pour lequel on a \[U_{i,j}(\omega)=\max_{1\leqslant k\leqslant r}U_{k,j}(\omega)\]
On note aussi pour \(i\in\left[\!\left[1,r\right]\!\right]\) et \(j\in\left[\!\left[1,n-1\right]\!\right]\), \[V_{i,j}(\omega)=\overline X_{i,j}(\omega)+\sqrt{\frac{\ln(n)}{j}}\]
On suppose dans la suite de cette partie que l’on applique la stratégie UCB.
Justifier que pour \(i\in\left[\!\left[1,r\right]\!\right]\), on a \(N_{i,r}=1\) et \(\widehat X_{i,r}=X_{i,1}\).
Écrire 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\).
En supposant que hatX contient \(\widehat X_{i,j}\), 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 la \((j+1)\)-ième action
réalisée, et renvoie la valeur de \(\widehat
X_{i,j+1}\) dans ces conditions.
Compléter l’écriture de la fonction Python
Actions(P,n) ci-dessous pour qu’elle renvoie la simulation
du vecteur des \(n\) actions réalisées
par l’algorithme UCB si le vecteur P contient les valeurs
de \(p_1,\ldots,p_r\).
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
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
Dans la suite de l’énoncé, on considère \(s\in\left[\!\left[1,r\right]\!\right]\) tel que \(p^*=p_s\), \(i\in\left[\!\left[1,r\right]\!\right]\) tel que \(p_i<p^*\) et \(u\in\left[\!\left[1,n-1\right]\!\right]\). On note \(A_{i,u}\) l’événement \[A_{i,u}=\left[\min_{k\in\left[\!\left[r,n-1\right]\!\right]}U_{s,k}\leqslant p_s\right] \cup \left[V_{i,u}\geqslant p_s\right]\]
Majoration de \(\mathbb E(N_{i,n})\).
Montrer que \([N_{i,n}>u]\) est réalisé alors il existe \(k\in\left[\!\left[r,n-1\right]\!\right]\) tel que \[[N_{i,k}=u]\cap[U_{i,k}>U_{s,k}]\] est réalisé, puis que \[\left[V_{i,u}>\min_{k\in\left[\!\left[r,n-1\right]\!\right]}U_{s,k}\right]\] est réalisé.
Montrer que si \([N_{i,n}>u]\) est réalisé alors \(A_{i,u}\) l’est. En déduire que \[\mathbb E(N_{i,n})\leqslant u+\mathbb P(A_{i,u}) \, n\]
Majoration de \(\mathbb P(A_{i,u})\).
Montrer en utilisant la question 17 que \[\mathbb P \! \left(\min_{k\in\left[\!\left[r,n-1\right]\!\right]}U_{s,k}\leqslant p_s\right) \leqslant \mathbb P \! \left(\min_{k\in\left[\!\left[1,n-1\right]\!\right]}V_{s,k}\leqslant p_s\right) \leqslant \frac1n\]
Établir que si \(\delta_i-\sqrt{\dfrac{\ln(n)}{u}}>0\), \[\mathbb P(V_{i,u}\geqslant p_s) \leqslant \exp \! \left(-2u\left(\delta_i-\sqrt{\frac{\ln(n)}{u}}\right)^2\right)\]
On suppose dans la suite que \(n\) est assez grand pour que \(\dfrac{4\ln(n)}{\delta_i^2}\in\left[\!\left[1,n-2\right]\!\right]\). On choisit \[u=\left\lfloor\frac{4\ln(n)}{\delta_i^2}\right\rfloor+1\] comme valeur de \(u\) pour la suite de cette question.
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[\]
En déduire que \(\mathbb P(V_{i,u}>p_s)\leqslant \dfrac1{n^2}\) puis que \(\mathbb P(A_{i,u})\leqslant \dfrac2n\).
Établir que \[\mathbb E(N_{i,n})\leqslant \frac{4\ln(n)}{\delta_i^2}+3\] puis que \[\mathbb E(\Delta_n)\leqslant 4\beta\ln(n)+3\alpha\]
SELECT col1,col2 ... FROM table ...
Retourne les valeurs des champs col1 et
col2 pour les enregistrements sélectionnés dans
table.
Si col est une colonnede la table table
:
SELECT SUM(col) FROM table ...
Retourne la somme des valeurs du champ col pour les
enregistrements sélectionnés dans table.
SELECT AVG(col) FROM table ...
Retourne la moyenne des valeurs du champ col pour les
enregistrements sélectionnés dans table.
SELECT COUNT(col) FROM table ...
Retourne le nombre d’éléments du champ col pour les
enregistrements sélectionnés dans table.
La fonction peut s’appliquer à des données numériques ou alphanumériques.
WHERE - Commande qui dans une requête
permet de sélectionner les enregistrements d’une table qui respectent
une condition.
AND, OR, NOT - Opérateurs logiques pour
la clause WHERE.
numpy de Pythonimport 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\times m$ |
np.zeros(n) | Crée le vecteur nul de taille $n$ |
np.ones([n,m]) | Crée la matrice de taille $n\times m$ dont tous les coefficients valent $1$ |
np.ones(n) | Crée le vecteur de taille $n$ dont tous les coefficients valent $1$ |
np.max(M) | Renvoie le plus grand élément de $M$, matrice ou vecteur |
np.min(M) | Renvoie le plus petit élément de $M$, matrice ou vecteur |
np.shape(M) | Renvoie dans un couple le format de la matrice $M$ |
np.mean(M) | Renvoie la moyenne des éléments de $M$ |
np.sqrt(x) | Renvoie $\sqrt x$ si $x\geqslant0$ |
np.log(x) | Renvoie $\ln(x)$ si $x>0$ |
random de numpy pour la simulation
probabilisteimport numpy.random as rd
rd.random([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 $\mathcal U(0,1)$. |
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, elle renvoie un seul coefficient suivant les
mêmes contraintes.
Fin
Le corrigé pas à pas, les aides et les explications sont disponibles dans la plateforme.
Sujet original et exigeant, centré sur un modèle de bandit manchot, qui introduit des outils modernes d’apprentissage séquentiel à partir de résultats classiques du programme (convexité, inégalité de Markov, inégalités exponentielles, variables de Bernoulli, espérance conditionnelle).
La première partie du sujet construisait progressivement l’inégalité de Hoeffding, étape par étape.
Bien guidée mais technique, elle demandait de rester très rigoureux dans la manipulation des espérances exponentielles et des majorations probabilistes.
Les candidats à l’aise avec les raisonnements par exponentielle génératrice pouvaient y sécuriser de nombreux points.
La partie centrale introduisait ensuite le modèle du bandit manchot, avec la définition des stratégies et de la notion de regret.
Les calculs d’espérance restaient accessibles, mais la lecture attentive des notations conditionnelles était indispensable.
L’étude de la stratégie Explore Then Commit (ETC) constituait une partie intermédiaire structurée et progressive, reposant essentiellement sur l’inégalité de Hoeffding démontrée auparavant.
Elle permettait d’obtenir une première majoration du regret moyen.
.
La dernière partie consacrée à la stratégie UCB était la plus technique du sujet.
Elle demandait une bonne maîtrise des majorations probabilistes et une lecture précise des événements introduits, mais restait guidée et permettait d’aboutir à une majoration logarithmique du regret, résultat classique en apprentissage séquentiel.
Dans l’ensemble, une épreuve atypique mais cohérente, très formatrice, qui valorisait les candidats capables de suivre un raisonnement probabiliste long et structuré tout en manipulant efficacement les outils d’inégalités exponentielles.