Contrôle Stochastique & Arrêt Optimal
Guide de révision complet · 12 heures · LPSM – Sorbonne Université
Bloc 1 · Contrôle Optimal des MDP
Ce bloc pose toutes les bases mathématiques. C'est le plus important : toute la suite (RL, arrêt optimal) en découle. Assurez-vous de maîtriser parfaitement les équations de Bellman et le théorème de vérification.
1.1 Systèmes dynamiques et chaînes de Markov
Système déterministe contrôlé
Un système évolue dans l'espace d'état E selon :
Un processus (X_n)_{n≥0} est une chaîne de Markov de transitions (P_n)_{n≥0} si :
pour tout A ∈ ε. La propriété clé est que le futur ne dépend du passé qu'à travers l'état présent.
Transition contrôlée
Un contrôle est une suite π = (a_n)_n de fonctions mesurables a_n : E → C.
Un contrôle randomisé est une suite π = (a_n)_n de fonctions a_n : E → 𝒫(C) (mesures de probabilité).
1.2 Problème de contrôle optimal
On fixe un horizon terminal N, des fonctions de récompense intermédiaire r_0, …, r_{N-1} : E × C → ℝ, et une récompense terminale g : E → ℝ.
V_π(x) = 𝔼_{x,π}[ Σ_{n=0}^{N-1} r_n(X_n, α_n) + g(X_N) ]
α_n = a_n(X_n) est la commande appliquée à l'état X_n.
On définit les fonctions valeur intermédiaires :
V_n(x) = sup_π V_{n,π}(x)
1.3 Opérateurs de récompense et équations de Bellman
Opérateurs de récompense
(T_{n,f} v)(x) := (L_n v)(x, f(x)) [opérateur de stratégie fixée f]
(T_n v)(x) := sup_{a ∈ A} (L_n v)(x, a) [opérateur maximal]
Pour π = (f_0, …, f_{N-1}) politique en N étapes :
V_{n,π} = T_{n,f_n} V_{n+1,π} (n = 0, …, N-1)
Preuve en un mot : Conditionnement sur X_{n+1} + propriété de Markov.
Les fonctions valeur optimales satisfont :
V_n = T_n V_{n+1} = sup_{a ∈ A} { r_n(x,a) + ∫ V_{n+1}(y) P_n(dy|x,a) }, n = 0,…,N-1
Et aussi : V_n = T_n T_{n+1} · · · T_{N-1} g_N
1.4 Théorème de Vérification et Principe de Programmation Dynamique
Soit (v_n)_{n=0}^N une solution des équations de Bellman.
(i) On a v_n ≥ V_n pour tout n.
(ii) Si f_n* est un maximiseur de v_{n+1} pour n = 0, …, N-1, alors v_n = V_n et la politique π* = (f_0*, …, f_{N-1}*) est optimale.
Preuve : Récurrence rétrograde. Pour (i) : v_n = T_n v_{n+1} ≥ T_n V_{n+1} ≥ T_{n,f_n} V_{n+1} = V_{n,π}. Pour (ii) : l'égalité est atteinte.
Sous l'hypothèse de structure, si (f_n*, …, f_{N-1}*) est optimal pour [n, N], alors (f_m*, …, f_{N-1}*) est optimal pour [m, N] pour tout m ≥ n. En d'autres termes :
Exemple : Problème de consommation (log-utilité)
C'est l'exercice 2 de l'examen 2025. Avec U(x) = log(x) :
f_n*(x) = x / (N - n + 1) [consommer 1/(N-n+1) du capital]
Bloc 2 · Arrêt Optimal & Longstaff-Schwartz
L'arrêt optimal est un cas particulier du contrôle stochastique où le seul contrôle est la décision d'arrêter ou de continuer. C'est l'exercice 1 de votre examen 2025.
2.1 Problème d'Arrêt Optimal
τ est un temps d'arrêt si {τ = n} ∈ F_n pour tout n. On note 𝒯_k l'ensemble des temps d'arrêt à valeurs dans {k, k+1, …, N}.
Exemple du Put Bermudéen : Z_n = e^{-rn·T/N} (K - X_n)_+
Équations de Bellman pour l'arrêt optimal
V_n(x) = max{ φ(n, x), C_n(x) } [exercer ou continuer ?]
C_n(x) = 𝔼[ V_{n+1}(X_{n+1}) | X_n = x ] = P_{n+1} V_{n+1}(x) [valeur de continuation]
C_n(x) = espérance de la valeur optimale future = valeur de continuer.
On exerce si φ(n, x) ≥ C_n(x), on continue sinon.
Le processus (S_n)_{n=0,…,N} est une surmartingale sous P. De plus :
- Le temps d'arrêt optimal est τ_n = min{k ≥ n : S_k = φ(k, X_k)} = min{k ≥ n : V_k(X_k) = Z_k}
- Le processus S_n arrêté en τ_0 est une martingale
Représentation de la valeur de continuation
Preuve : V_{n+1}(y) = 𝔼^y[Z_{τ_{n+1}}] par définition de τ_{n+1}. En intégrant contre P_{n+1}(x, dy) on obtient C_n(x) = 𝔼[Z_{τ_{n+1}} | X_n = x].
Récurrence sur les temps d'arrêt optimaux (examen Q.4)
τ_n = n · 1_{Z_n ≥ 𝔼[Z_{τ_{n+1}} | X_n]} + τ_{n+1} · 1_{Z_n < 𝔼[Z_{τ_{n+1}} | X_n]}
= n · B_n + τ_{n+1} · (1 - B_n)
V_0(x_0) = 𝔼[Z_{τ_0}] = max{ φ(0, x_0), 𝔼[Z_{τ_1}] }
2.2 Algorithme de Longstaff-Schwartz
Problème pratique : comment calculer C_n(x) = 𝔼[Z_{τ_{n+1}} | X_n = x] quand la dimension est grande ? On utilise la régression sur un échantillon de Monte Carlo.
Idée centrale
Étant donné M trajectoires (X_n^{(j)})_{n,j}, on approche C_n(x) par une régression sur une base de fonctions :
θ_n* = argmin_θ Σ_{j=1}^M | Z^{(j)}_{τ_{n+1}} - Φ(X_n^{(j)}; θ) |²
θ_n* = (E^T E)^{-1} E^T Y où E_{jk} = e_k(X_n^{(j)}) et Y_j = Z^{(j)}_{τ_{n+1}}.
- Simuler M trajectoires (X_n^{(j)})_{n=0,…,N}, 1 ≤ j ≤ M
- Initialiser : τ^{(j)}_N = N, payoff_opt^{(j)} = Z_N^{(j)} = φ(N, X_N^{(j)})
- Pour n = N-1, …, 1 (boucle rétrograde) :
- Régresser payoff_opt sur {X_n^{(j)}} → obtenir θ_n
- Calculer Φ(X_n^{(j)}; θ_n) ≈ C_n(X_n^{(j)})
- Pour chaque j : si Z_n^{(j)} ≥ Φ(X_n^{(j)}; θ_n), alors τ^{(j)} = n et payoff_opt^{(j)} = Z_n^{(j)}
- Estimateur : V̂_0 = (1/M) Σ_j payoff_opt^{(j)}
Sources d'erreur
Erreur de discrétisation
- Horizon N fini
- Temps discrets seulement
- Diminue avec N → ∞
Erreur de projection
- Base de fonctions trop petite
- C_n ∉ Vect(e_1, …, e_m)
- Diminue avec m → ∞
Erreur Monte Carlo
- Variance σ² / M
- IC 95% : ±1.96 σ/√M
- Diminue avec M → ∞
Biais de l'estimateur
- Sous-optimal (lower bound)
- Corrigé par re-simulation
- Sur-apprentissage si m grand
2.3 Exemple du TP – Put Bermudéen en Black-Scholes 1D
Modèle
X_{n+1} = X_n · exp( (r - σ²/2) h + σ √h · ε_{n+1} ), ε_{n+1} ~ N(0,1)
Bases de fonctions utilisées dans le TP
def base1_ek(x): # Polynôme : 1, x, x², x³ return np.array([np.ones_like(x), x, x**2, x**3]) def base2_ek(x): # Idem + (K-x)₊ (payoff dans la base) return np.array([np.ones_like(x), np.maximum(K-x, 0), x, x**2, x**3])
Avantage de base2 : En incluant le payoff dans la base, on capture mieux le comportement autour du strike K. La base2 donne généralement un prix plus précis.
Code central de l'algorithme LS (TP)
payoff_opt = payoffs_Z[N].copy() # Initialisation : valeur terminale for n in reversed(range(1, N)): # Régression : payoff_opt ~ Φ(X_n; θ) thetas[n] = theta_by_regression(payoff_opt, sample_X[n]) # Décision : exercer si Z_n ≥ Φ(X_n; θ_n) stop_at_n = payoffs_Z[n] >= function_Phi(sample_X[n], thetas[n]) # Mise à jour des payoffs optimaux payoff_opt[stop_at_n] = payoffs_Z[n, stop_at_n].copy()
Bloc 3 · Apprentissage par Renforcement – Fondements
3.1 Le problème RL
Le RL répond à la question : Comment agir sur un système pour optimiser une récompense sans connaissance complète du système ?
| Paradigme | Connaissance | Objectif |
|---|---|---|
| Supervisé | Exemples (x, y) étiquetés | Prédire y à partir de x |
| Non-supervisé | Données x non étiquetées | Trouver une structure cachée |
| Reinforcement | Interactions + récompenses | Maximiser la récompense cumulée |
On apprend P et r implicitement (model-free) ou explicitement (model-based).
3.2 Interface Agent-Environnement
À chaque pas de temps n :
- L'agent observe l'état s_n ∈ S
- L'agent choisit une action a_n ∈ A
- L'environnement retourne la récompense r_n et le nouvel état s_{n+1}
- Le tuple (s_n, a_n, r_n, s_{n+1}) est un sample
Exploration vs Exploitation
C'est le défi central du RL :
Exploitation
- Utiliser ce qu'on connaît
- Maximiser la récompense immédiate
- Risque : minimum local
Exploration
- Essayer de nouvelles actions
- Découvrir de meilleures stratégies
- Coût : sous-optimalité à court terme
3.3 Critères de Performance
| Critère | Définition | Usage |
|---|---|---|
| Sample complexity | Nb de samples pour ε-optimalité | Efficacité globale |
| Rate of convergence | Nb d'itérations pour précision donnée | Vitesse théorique |
| Regret | R(π) = V*(x) - V_π(x) cumulé | Analyse en ligne |
| Convergence asymptotique | Erreur → 0 quand N → ∞ | Preuve de base |
Composantes d'un algorithme RL
Bloc 4 · Algorithmes Value-Based
4.1 Fonction de valeur et Q-fonction
V_n(x) = sup_{a ∈ A} Q_n(x, a)
Équations de Bellman pour Q*
Q_n(x, a) = r_n(x, a) + 𝔼_{x' ~ P_n(·|x,a)}[ sup_{a' ∈ A} Q_{n+1}(x', a') ]
4.2 TD Learning (Temporal Difference)
TD learning estime V_π par approximation stochastique. La mise à jour fondamentale est :
δ_n = r_n + V̂_{n+1,π}(x') - V̂_{n,π}(x) [erreur TD]
x' : état suivant observé après action a depuis x.
Famille TD(λ)
TD(1) = Monte-Carlo : λ = 1, toute la trajectoire → pas de biais, haute variance.
λ intermédiaire : compromis biais-variance.
4.3 Q-learning
Le Q-learning est une approximation stochastique de l'équation de Bellman pour Q*. C'est un algorithme off-policy : la politique d'exploration peut être différente de la politique optimale apprise.
δ_n = r_n + sup_{a' ∈ A} Q̂_{n+1}(x', a') - Q̂_n(x, a)
Si A et S sont finis, les récompenses bornées, et le taux η_k ∈ [0,1) vérifie les conditions de Robbins-Monro :
et si tout (s, a) est visité infiniment souvent, alors Q̂^k(s, a) → Q(s, a) p.s.
- Initialiser Q̂_n(x, a) pour tout n, x, a
- Pour k = 0 à K (épisodes) :
- Poser état initial x
- Pour n = 0 à N-1 :
- Choisir action a selon politique d'exploration
- Observer r_n et x'
- δ_n = r_n + sup_{a'} Q̂_{n+1}(x', a') - Q̂_n(x, a)
- Q̂_n(x,a) ← Q̂_n(x,a) + η δ_n
- x ← x'
- Politique optimale : f̂_n(x) ∈ argmax_a Q̂_n(x, a)
4.4 SARSA (on-policy)
SARSA est on-policy : la politique d'exploration et la politique apprise sont la même. Il alterne évaluation et amélioration de la politique courante π^k.
| Q-learning | SARSA | |
|---|---|---|
| Type | Off-policy | On-policy |
| Cible δ_n | r + sup Q(x', a') | r + Q(x', a') avec a' jouée |
| Convergence | Vers Q* | Vers Q^π |
| Exploration | Découplée de la politique | Couplée à la politique |
4.5 Politiques d'Exploration
ε-greedy
α_n ~ U(A) avec prob. ε
Politique Soft-max (Boltzmann)
λ → 0 : politique greedy (exploitation pure).
Lien avec l'entropie de Shannon : c'est la solution du problème max_p 𝔼_{a~p}[Q(a)] + λH(p).
Bloc 5 · Algorithmes Policy-Based
Au lieu d'apprendre V ou Q et d'en déduire la politique, on paramétrise directement la politique π^θ et on optimise θ.
5.1 Policy Gradient – REINFORCE
π^θ paramétrisé par densités a ↦ p^θ_n(x, a).
Preuve : On écrit Π^θ(ds) = p̃^θ(s) P̃(ds), puis on dérive J = ∫ R(s) p̃^θ(s) P̃(ds) et on utilise ∇_θ log p̃^θ = ∇_θ p̃^θ / p̃^θ.
- Initialiser θ
- Pour m = 1 à M (itérations) :
- Générer K trajectoires S^1, …, S^K selon Π^θ
- Estimer ∇_θ J ≈ (1/K) Σ_k R(S^k) Σ_n ∇_θ log p^θ_n(X^k_n, α^k_n)
- Mise à jour : θ ← θ + η · ∇̂_θ J
Réduction de variance – Baseline
On peut soustraire une constante C à R sans changer le gradient :
Meilleure baseline : C = 𝔼[R(S)] ≈ V_{π^θ}(X_0). → Actor-Critic !
5.2 Actor-Critic
L'actor-critic combine l'apprentissage de V_π (critic) et de π^θ (actor). La clé est la représentation du gradient basée sur la DP :
Interprétation : Le terme (r_k + V_{k+1} - V_k) est l'erreur TD – une mesure de l'avantage d'avoir pris l'action α_k.
Preuve : On différentie la relation de Bellman V_{k,π^θ} = 𝔼[r_k + V_{k+1,π^θ}] par rapport à θ, en utilisant la règle de la dérivée sous l'espérance.
Actor (θ)
- Représente la politique π^θ
- Mise à jour par gradient de J
- Utilise le signal du critic
Critic (φ)
- Représente V^φ_n(x) ≈ V_{n,π^θ}(x)
- Entraîné par régression DP
- Fournit la baseline à l'actor
φ ← argmin_φ 𝔼_{π^θ}[ | Σ_k (r_k + V^φ_{k+1}(X_{k+1}) - V^φ_k(X_k)) |² ]
Bloc 6 · Formules Clés + Exercices d'Examen
6.1 Formulaire à Maîtriser
V_n(x) = sup_{a ∈ A} { r_n(x,a) + ∫ V_{n+1}(y) P_n(dy|x,a) }
C_n(x) = 𝔼[V_{n+1}(X_{n+1}) | X_n = x] = 𝔼[Z_{τ_{n+1}} | X_n = x]
V_n(x) = max{ φ(n, x), C_n(x) }
Q_n(x,a) = r_n(x,a) + 𝔼_{x'~P_n}[ max_{a'} Q_{n+1}(x',a') ]
IC 95% : V̂_0 ± 1.96 · √(Var/M)
6.2 Exercice 1 – Examen Mai 2025 (Arrêt Optimal)
Q.1 – Récurrence rétrograde
La suite (V_n)_{n=0,…,N} satisfait :
V_n(x) = max{ φ_n(x), P_{n+1}V_{n+1}(x) } = max{ φ_n(x), 𝔼[V_{n+1}(X_{n+1}) | X_n = x] }
Le noyau de transition intervient via P_{n+1}V_{n+1}(x) = ∫ V_{n+1}(y) P_{n+1}(x, dy).
Q.2 – Propriété de (S_n)
S_n = V_n(X_n). Ce processus est une surmartingale.
Preuve : 𝔼[S_{n+1} | F_n] = 𝔼[V_{n+1}(X_{n+1}) | X_n] = C_n(X_n) ≤ V_n(X_n) = S_n (car V_n ≥ C_n).
De plus, S_n arrêté en τ_0 est une martingale (car on exerce exactement quand S_n = Z_n).
Q.3 – Représentation C_n(x) = 𝔼[Z_{τ_{n+1}} | X_n = x]
Par définition de τ_{n+1} : V_{n+1}(y) = 𝔼[Z_{τ_{n+1}} | X_{n+1} = y].
Donc : C_n(x) = 𝔼[V_{n+1}(X_{n+1}) | X_n = x] = ∫ V_{n+1}(y) P_{n+1}(x, dy) = ∫ 𝔼[Z_{τ_{n+1}} | X_{n+1} = y] P_{n+1}(x, dy) = 𝔼[Z_{τ_{n+1}} | X_n = x].
Q.4 – Récurrence sur les τ_n
On exerce en n si Z_n ≥ C_n(X_n) = 𝔼[Z_{τ_{n+1}} | X_n], sinon on continue jusqu'à τ_{n+1}.
V_0(x_0) = 𝔼[Z_{τ_0}] = max{φ_0(x_0), 𝔼[Z_{τ_1}]} car {X_0 = x_0} est déterministe.
Q.5 – Algorithme Longstaff-Schwartz
Données : M trajectoires (X_n^{(j)})_{n,j}, bases (e_k)_k.
Algorithme :
- τ^{(j)} = N, payoff^{(j)} = φ_N(X_N^{(j)}) pour tout j
- Pour n = N-1, …, 1 : régresser (payoff^{(j)}) sur {e_k(X_n^{(j)})} → θ_n
- Φ(X_n^{(j)}; θ_n) ≈ C_n(X_n^{(j)})
- Si φ_n(X_n^{(j)}) ≥ Φ(X_n^{(j)}; θ_n) : τ^{(j)} = n, payoff^{(j)} = φ_n(X_n^{(j)})
- V̂_0 = (1/M) Σ_j payoff^{(j)} avec IC 95%
Erreurs : discrétisation (N fini), projection (base trop petite), Monte Carlo (M fini → σ/√M), biais (estimateur par défaut).
6.3 Exercice 2 – Examen Mai 2025 (Épargne/Consommation)
Modèle : X_0 = x_0 > 0, X_{n+1} = X_n + Y_n X_n (1 - U_n), U_n ∈ [0,1], Y_n IID E[Y] = θ.
Objectif : max 𝔼[Σ_{n=0}^{N-1} X_n U_n] (maximiser consommation totale).
Q.1 – Modèle markovien contrôlé
E = ℝ_+, C = [0,1]. Transition : X_{n+1} = X_n(1 + Y_n(1-U_n)) avec Y_n IID.
Récompense : r_n(x, u) = x·u. Terminal : g_N(x) = 0.
Q.2 – Équations de DP
J_n(x) = sup_{u ∈ [0,1]} { x·u + 𝔼[J_{n+1}(X_n(1 + Y_n(1-u)))] }
Q.3 – Structure linéaire J_n(x) = ρ_n · x
On suppose J_{n+1}(x) = ρ_{n+1}·x et on vérifie par récurrence :
= x · sup_{u ∈ [0,1]} { u + ρ_{n+1}(1 + θ(1-u)) }
= x · sup_{u ∈ [0,1]} { u(1 - ρ_{n+1}θ) + ρ_{n+1}(1+θ) }
La fonction est linéaire en u. Donc :
- Si 1 - ρ_{n+1}θ > 0 (i.e. ρ_{n+1} < 1/θ) → U_n* = 1, ρ_n = 1 + ρ_{n+1}θ
- Si 1 - ρ_{n+1}θ < 0 (i.e. ρ_{n+1} > 1/θ) → U_n* = 0, ρ_n = ρ_{n+1}(1+θ)
- Si ρ_{n+1} = 1/θ → indifférent, ρ_n = 1 + ρ_{n+1}θ = 2
Récurrence : ρ_N = 0 → ρ_{N-1} = 1 (U_{N-1}* = 1 car ρ_N = 0 < 1/θ) → ρ_{N-2} dépend de θ...
Q.4 – Interprétation (seuil K)
Il existe K unique tel que :
- U_n* = 0 pour n < K : on n'investit rien, on laisse croître le capital
- U_n* = 1 pour n ≥ K : on consomme tout le capital
Intuition : Si l'horizon est encore long (n < K), il vaut mieux investir pour faire fructifier le capital. Quand l'horizon est court (n ≥ K), on consomme tout immédiatement car il n'y a plus assez de temps pour que l'investissement soit rentable.
6.4 Points Clés pour l'Examen
· Définir une chaîne de Markov et ses transitions
· Énoncer et prouver le Théorème de Vérification
· Énoncer et prouver le DPP
· Dériver le Policy Gradient Theorem
· Expliquer la différence Q-learning vs SARSA (on/off policy)
· Démontrer que la soft-max résout l'entropie régularisée
1. Identifier le type de problème (contrôle ? arrêt optimal ? RL ?)
2. Écrire les équations de Bellman explicitement
3. Chercher une structure (linéaire, exponentielle...) qui est stable par T_n
4. Prouver par récurrence rétrograde
5. Déduire la politique optimale en maximisant
Bon courage pour votre examen !
Maîtrisez les formules F1–F8, les preuves des théorèmes principaux, et l'algorithme de Longstaff-Schwartz.