Corrigé ESSEC 2026 Maths 2 appliquées ECG — Stratégie UCB (Q20.a à Q22) : Majoration logarithmique du regret de UCB : E(Ni,n) ≤ 4 ln(n)/δi² + 3

Sujet officiel du concours ESSEC, session 2026, épreuve Maths 2 appliquées ECG. Corrigé rédigé par Ibrahim Alame.

Énoncé

On applique la stratégie UCB (notations $U_{i, j}$ , $V_{i, j}$ de la partie précédente). Soit $s$ tel que $p_{s} = p^{*}$ , $i$ tel que $p_{i} < p^{*}$ (donc $δ_{i} > 0$ ) et $u \in [[1, n - 1]]$ ; on note $A_{i, u}$ l'événement $[min_{r ⩽ j ⩽ n - 1} U_{s, j} ⩽ p_{s}] \cup [V_{i, u} ⩾ p_{s}]$ .

Q20.a Si $[N_{i, n} > u]$ est réalisé, montrer qu'il existe $k \in [[r, n - 1]]$ tel que $[N_{i, k} = u] \cap [U_{i, k} ⩾ U_{s, k}]$ le soit, puis que $V_{i, u} ⩾ min_{r ⩽ j ⩽ n - 1} U_{s, j}$ .
Q20.b Montrer que $[N_{i, n} > u] \subset A_{i, u}$ , puis que $E (N_{i, n}) ⩽ u + n P (A_{i, u})$ .
Q21.a À l'aide de Q17, montrer que $P (min_{r ⩽ j ⩽ n - 1} U_{s, j} ⩽ p_{s}) ⩽ P (min_{1 ⩽ k ⩽ n - 1} V_{s, k} ⩽ p_{s}) ⩽ \frac{1}{n}$ .
Q21.b Si $δ_{i} - ln (n) / u ⩾ 0$ , établir $P (V_{i, u} ⩾ p_{s}) ⩽ exp (- 2 u (δ_{i} - ln (n) / u)^{2})$ .

On suppose $\frac{4 l n n}{δ _{i}^{2}} \in [1, n - 2]$ et l'on choisit $u = ⌊ \frac{4 l n n}{δ _{i}^{2}} ⌋ + 1$ .

Q21.c Montrer que $φ : t \mapsto exp (- 2 (δ_{i} t - ln n)^{2})$ est décroissante sur $[\frac{l n n}{δ _{i}^{2}}, + \infty [$ .
Q21.d En déduire $P (V_{i, u} ⩾ p_{s}) ⩽ \frac{1}{n ^{2}}$ , puis $P (A_{i, u}) ⩽ \frac{2}{n}$ .
Q22. Établir $E (N_{i, n}) ⩽ \frac{4 l n n}{δ _{i}^{2}} + 3$ , puis $E (Δ_{n}) ⩽ 4 β ln (n) + 3 α$ .

Corrigé

Q20.a Fixons $ω$ tel que $N_{i, n} (ω) > u$ , et notons $c_{j} = N_{i, j} (ω)$ pour $j \in [[r, n]]$ . On a $c_{r} = 1$ (Q18.a), $c_{n} ⩾ u + 1$ , et $c_{j + 1} - c_{j} \in {0, 1}$ (le compteur augmente de $1$ exactement quand $I_{j + 1} (ω) = i$ ). Comme $u ⩾ 1$ , $c_{r} = 1 < u + 1 ⩽ c_{n}$ : l'ensemble des $j \in [[r, n]]$ tels que $c_{j} ⩾ u + 1$ est une partie non vide de $N$ , qui admet un plus petit élément $j_{0}$ , avec $j_{0} > r$ . Par minimalité $c_{j_{0} - 1} ⩽ u$ , et puisque le compteur augmente d'au plus $1$ , $c_{j_{0} - 1} = u$ et $c_{j_{0}} = u + 1$ . Posons $k = j_{0} - 1 \in [[r, n - 1]]$ :

$N_{i, k} (ω) = u$ ;
le compteur a augmenté entre $k$ et $k + 1$ , donc $I_{k + 1} (ω) = i$ , ce qui, par définition de UCB, signifie $U_{i, k} (ω) = max_{l} U_{l, k} (ω) ⩾ U_{s, k} (ω)$ .

L'événement $[N_{i, k} = u] \cap [U_{i, k} ⩾ U_{s, k}]$ est donc réalisé. Sur $[N_{i, k} = u]$ , $X^_{i, k} = \frac{1}{u} \sum_{l = 1}^{u} X_{i, l} = X_{i, u}$ , donc

$U_{i, k} (ω) = X_{i, u} (ω) + \frac{ln n}{u} = V_{i, u} (ω),$

$V_{i, u} (ω) = U_{i, k} (ω) ⩾ U_{s, k} (ω) ⩾ r ⩽ j ⩽ n - 1 min U_{s, j} (ω) .$

Q20.b Soit $ω \in [N_{i, n} > u]$ ; posons $ν (ω) = min_{r ⩽ j ⩽ n - 1} U_{s, j} (ω)$ . Si $ν (ω) ⩽ p_{s}$ , le premier événement de la réunion est réalisé. Sinon $ν (ω) > p_{s}$ et Q20.a donne $V_{i, u} (ω) ⩾ ν (ω) > p_{s}$ : le second est réalisé. Dans les deux cas $ω \in A_{i, u}$ , donc $[N_{i, n} > u] \subset A_{i, u} .$

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →