Programmation dynamique

Fabian Bastin

DIRO, Université de Montréal

Janvier 2014

Fabian Bastin Introduction

Contenu de l’introduction

1 Modalités pratiques.
2 Qu’est-ce que la programmation dynamique (PD)?
3 Exemples simples.
4 Modèle de base: versions déterministe et stochastique.
5 Principe d’optimalité et algorithme de la PD.
6 Contrôle en boucle ouverte vs boucle fermée, et valeur de
l’information.
7 Reformulations pour se ramener au modèle de base.
8 Fonction d’utilité et mesure de risque.

Fabian Bastin Introduction

Contact - support de cours

Disponible sur rendez-vous à mon bureau (3367).

Courriel: bastin@[Link]

Les diapositives du cours seront placées au fur et à mesure de

l’avancement du cours sur Studium
([Link]

Les notes sont partiellement inspirées du cours donné par Pierre

L’Ecuyer.
Les figures ont été fournies par D. P. Bertsekas.

Fabian Bastin Introduction

Contact - support de cours

Références:
D. P. Bertsekas, Dynamic Programming and Optimal Control,
Vol. 1 et 2, Athena Scientific, Belmont, Mass., 2005 et 2007.
W. B. Powell, Approximate Dynamic Programming, Second
Edition, Wiley, New York, 2011. Disponible en ligne: http://
[Link]/book/10.1002/9781118029176
P. Glasserman, Monte Carlo Methods in Financial Engineering,
Springer, 2003.
...

Fabian Bastin Introduction

Evaluation

Les modalités d’évaluation précises seront discutées en classe, mais

elle se répartira comme suit:
4 devoirs, chacun comptant pour 12.5% de la note finale;
un examen intra, comptant pour 20%;
un projet final, comptant pour 30%.

Fabian Bastin Introduction

Qu’est-ce que la programmation dynamique?
Processus de décision séquentiel (PDS):
Suite de décisions à prendre, avec un objectif à optimiser.
Temps discret: À chaque étape, on prend une décision, selon
l’information disponible.
Liens (interactions) entre les décisions.
En général, on peut recevoir de l’information additionnelle à
chaque étape, et il y a des aléas dans l’évolution entre les prises
de décision.
Temps continu: la suite de décisions est remplacée par un
contrôle, qui est une fonction du temps.
Exemples: gestion d’un inventaire; conduite automobile; pilotage
d’un avion (pilote automatique), d’un robot, etc.; entretien
préventif; gestion d’un fond d’investissement; option financière de
type américaine; partie de tennis ou de football; jeu d’échecs; etc.
La vie en général!
Fabian Bastin Introduction
Définitions générales

Programmation dynamique:
Ensemble d’outils mathématiques et algorithmiques pour étudier les
processus de décision séquentiels et calculer éventuellement des
stratégies optimales (exactes ou approximatives).

Une politique (ou stratégie) est une règle de prise de décisions qui,
pour chaque situation possible (état du système), nous dit quelle
décision (ou action) prendre dans le but d’optimiser une fonction
objectif globale.
Souvent, la fonction objectif est une espérance mathématique.
Parfois, on pourra caractériser la politique optimale par des
théorèmes (théorie); souvent, on pourra la calculer, ou en calculer
une approximation; dans certains cas la résolution sera trop difficile.

Fabian Bastin Introduction

Exemple: modèle d’inventaire simple, un seul
produit
xk = stock en inventaire au début de la période k.
uk = quantité commandée au début de la période k, et
obtenue immédiatement. Contrainte: uk ≥ 0.
wk = demande durant la période k.
Supposons que les wk sont des v.a.’s indépendantes.
Évolution: xk+1 = xk + uk − wk = f (xk , uk , wk ).
Note: xk peut être négatif (la demande est en attente).
r (xk ) = coût associé à l’inventaire xk au début de la période k.
Coût de stockage si xk > 0; coût de pénurie si xk < 0.
c = coût unitaire d’approvisionnement.
R(xN ) = coût pour l’inventaire terminal.
Coût espéré total, à minimiser:
N−1
" #
X
E R(xN ) + (r (xk ) + cuk ) .
k=0
Fabian Bastin Introduction
Boucle

Contrôle en boucle ouverte: on choisit u0 , . . . , uN−1 à l’avance.

Contrôle en boucle fermée: on choisit uk après avoir observé xk .
Dans le second cas, on cherche une politique π = (µ0 , µ1 , . . . , µN−1 )
qui nous indique comment prendre les décisions: uk = µk (xk ).
Le coût espéré associé à la politique π est
N−1
" #
X
Jπ (x0 ) = E R(xN ) + (r (xk ) + cµk (xk ))
k=0

Comment trouver π = π ∗ qui minimise Jπ (x0 )? Sous certaines

hypothèses raisonnables, on peut montrer que π ∗ a la forme

µk (xk ) = max(0, Sk − xk ).

Dans ce cas, il suffit d’optimiser les Sk (plus simple).

Fabian Bastin Introduction

Séquence

x0 → u0 = µ0 (x0 ), w0 → x1 = x0 + u0 − w0
x1 → u1 = µ1 (x1 ), w1 → x2 = x1 + u1 − w1
x2 → u2 = µ2 (x2 ), w2 → x3 = x2 + u2 − w2
x3 ···

Principaux ingrédients d’un PDS (usuel):

Temps discret; aléas indépendants; contraintes sur les décisions et
politiques; coût additif; on cherche à optimiser une politique.

Fabian Bastin Introduction

Un modèle de PDS déterministe
À l’étape k, le système est dans un état xk ∈ Xk .
Un décideur observe xk et choisit une décision (action) uk ∈ Uk (xk ).
Il paye un coût gk (xk , uk ) pour cette étape, puis le système transite
dans un nouvel état xk+1 = fk (xk , uk ) à l’étape k + 1.
À l’étape k, on a donc:
Xk = espace d’états;
Uk (x) = ensemble des décisions admissibles dans l’état x;
gk = fonction de coût;
fk = fonction de transition;
xk = état du système à l’étape k;
uk = décision prise à l’étape k.
On veut minimiser la somme des coûts de l’étape 0 à l’étape N:
N−1
X
min gN (xN ) + gk (xk , uk )
k=0
s.l.c. uk ∈ Uk (xk ) et xk+1 = fk (xk , uk ), k = 0, . . . , N − 1; x0 fixé.
Fabian Bastin Introduction
Programme

N−1
X
min gN (xN ) + gk (xk , uk )
k=0
s.l.c. uk ∈ Uk (xk ) et xk+1 = fk (xk , uk ), k = 0, . . . , N − 1
x0 fixé.

On peut illustrer cela par un arbre de décision.

Les fonctions gk et fk peuvent être non linéaires et compliquées.
Si gk (xk , uk ) est un revenu au lieu d’un coût, on remplace “min”
par “max” (ou “inf” par “sup”).
Une politique (ou stratégie) admissible est une suite de fonctions
π = (µ0 , . . . , µN−1 ) tel que µk : Xk → Uk et µk (x) ∈ Uk (x) pour
tout x ∈ Xk , 0 ≤ k ≤ N − 1. La décision à l’étape k est µk (xk ).

Fabian Bastin Introduction

Equations de récurrence - équations de Bellman
Pour une stratégie π fixée, posons

Jπ,k (x) = coût total pour les étapes k à N si on est dans l’état x
à l’étape k et si on utilise la politique π
N−1
X
= gN (xN ) + gn (xn , un )
n=k

s.l.c. un = µn (xn ) et xn+1 = fn (xn , un ), n = k, . . . , N − 1

xk = x (fixé).

Ces valeurs satisfont les équations de récurrence (ou équations

fonctionnelles) suivantes:

Jπ,N (x) = gN (x) ∀x ∈ XN

Jπ,k (x) = gk (x, µk (x)) + Jπ,k+1 (fk (x, µk (x))) pour tout x ∈ Xk ,
pour k = N − 1, N − 2, . . . , 1, 0.

Fabian Bastin Introduction

Politique optimale

Sans fixer la politique, pour 0 ≤ k ≤ N et x ∈ Xk , soient

Jk (x) = coût optimal pour les étapes k à N si on est dans

l’état x à l’étape k
N−1
!
X
= min gN (xN ) + gn (xn , un )
uk ,...,uN−1
n=k

s.l.c. un ∈ Un (xn ) et xn+1 = fn (xn , un ), n = k, . . . , N − 1

xk = x (fixé).

Une politique admissible π ∗ = (µ∗0 , . . . , µ∗N−1 ) telle que

def
Jπ∗ ,0 (x) = J0 (x) = J(x) pour tout x

s’appelle une politique optimale.

Fabian Bastin Introduction

On a les équations de récurrence (équations de Bellman):

JN (x) = gN (x) pour tout x ∈ XN

Jk (x) = min {gk (x, u) + Jk+1 (fk (x, u))} pour tout x ∈ Xk ,
u∈Uk (x)
pour k = N − 1, N − 2, . . . , 1, 0.

On cherche J0 (x0 ) pour x0 fixé (problème de la valeur initiale).

On peut résoudre par fixation itérative, chaı̂nage arrière:
Calculer JN−1 (x) pour tout x ∈ XN−1 ,
puis JN−2 (x) pour tout x ∈ XN−2 , etc.
Comment retrouver la solution optimale ?
Durant les calculs, on mémorise, pour chaque k et x ∈ Xk ,

µ∗k (x) = arg min {gk (x, u) + Jk+1 (fk (x, u))} ,
u∈Uk (x)

qui est la décision optimale à prendre dans l’état x à l’étape k.

Note: La notation pourra varier un peu selon les problèmes.

Fabian Bastin Introduction
Algorithme de programmation dynamique

Procédure Chaı̂nage Arrière

pour tout x ∈ XN , JN (x) ← gN (x);
pour k = N − 1, . . . , 0 faire
pour tout x ∈ Xk faire

Jk (x) ← min {gk (x, u) + Jk+1 (fk (x, u))} ;

u∈Uk (x)
µ∗k (x) ← arg min {gk (x, u) + Jk+1 (fk (x, u))} ;
u∈Uk (x)

Fabian Bastin Introduction

Principe d’optimalité de Bellman
Si π ∗ = (µ∗0 , . . . , µ∗N−1 ) est une politique optimale pour le problème
initial et si 0 ≤ i ≤ j ≤ N − 1, alors la politique tronquée
∗ = (µ∗ , . . . , µ∗ ) est une politique optimale pour le sous-problème
πi,j i j
qui consiste à minimiser
j
X
gk (xk , uk )
k=i

pour xi et xj fixés (en posant gN (xN , uN ) ≡ gN (xN )).

Hypothèses importantes: Temps discret et coûts additifs.
Si le coût n’est pas additif, le principe d’optimalité ne tient pas
nécessairement. Exemple: Si on remplace la somme par le
maximum, i.e., on veut minimiser

max [gk (xk , uk ), . . . , gN−1 (xN−1 , uN−1 ), gN (xN )] .

Fabian Bastin Introduction

Plus court chemin dans un réseau.
Si Xk et chaque Uk (x) sont des ensembles finis, le problème se
ramène à un problème de plus court chemin dans un réseau.
Les noeuds du réseau sont tous les couples (k, xk ) possibles, pour
0 ≤ k ≤ N et xk ∈ Xk , et les arcs partant d’un noeud correspondent
aux décisions uk que l’on peut prendre à partir de ce noeud.
Terminal Arcs
with Cost Equal
to Terminal Cost

...
t
Artificial Terminal
Initial State
... Node
s

...

Stage 0 Stage 1 Stage 2 ... Stage N - 1 Stage N

Ce réseau est sans cycle et ordonné topologiquement.

Tout algorithme pour trouver le plus court chemin dans un tel
réseau s’applique pour calculer une politique optimale pour ce PDS.
Important: Il ne faut pas que le nombre d’états devienne trop grand!
Fabian Bastin Introduction
Exemple: ordonnancement de tâches
(DPOC, pages 7 et 19) On a 4 opérations, {A, B, C, D}, à effectuer
sur une machine. On doit faire A avant B, et C avant D.
Il y a un coût Sm si on débute avec l’opération m,
puis un coût Cmn pour passer de l’opération m à l’opération n.
Par exemple, pour la séquence ACDB, le coût total est
SA + CAC + CCD + CDB . ABC CC D

C BC
AB
ACB C BD
C AB
A C CB
AC
C AC
CC D ACD C DB
SA
Initial
State
CAB C BD
CA C AB
SC
C C CA
C AD CAD C DB

CC D CD

C DA
CDA C AB

Fabian Bastin Introduction

 ABC 6

3
AB
ACB 1
2 9
A 4
3 AC
8 ACD 3
5 6
5
Initial
1 0 State
CAB 1
CA 2
3
4
C 3 4
CAD 3
7 6
CD

5 3
CDA 2

Une seule tâche à accomplir: aucune décision à prendre.

Par le principe d’optimalité, s’il ne reste que deux tâches,
l’ordonnancement de ces deux tâches doit minimiser la coût associé.
Même chose s’il ne reste que trois tâches.
Fabian Bastin Introduction
Exemple: allocation d’équipes médicales

On dispose de 5 équipes médicales à allouer à 3 pays en

développement. Plus on alloue d’équipes médicales à un pays, plus
on augmente son nombre d’années–personnes de vie espérée. Cette
augmentation n’est pas linéaire.

Milliers d’années–personnes de vie espérée additionnelle

Nombre d’équipes allouées, uk Pays 0 Pays 1 Pays 2
0 0 0 0
1 45 20 50
2 70 45 70
3 90 75 80
4 105 110 100
5 120 150 130

Fabian Bastin Introduction

Exemple: allocation d’équipes médicales

Soit uk (un entier) le nombre d’équipes allouées au pays k.

On veut maximiser le nombre total d’années-personnes de vie
espérée additionnelle pour les 3 pays.
PDS: N = 3. À l’étape k ≤ 2, il reste uk , . . . , u2 à fixer, xk équipes
sont encore disponibles, et Jk (xk ) est le revenu optimal pour les
pays k, . . . , 2.
Les gk (xk , uk ) = gk (uk ) sont les valeurs données dans le tableau.
(Ici, elles ne dépendent que de uk et pas de xk .)
Le noeud (k, x) correspond à l’état xk : il reste x équipes pour les
pays k, . . . , 2. Le chaı̂nage arrière revient à rechercher le plus long
chemin de (0, 5) à (3, 0).

Fabian Bastin Introduction

Exemple: jeu de Nim

Règles du jeu: on place des pièces dans 4 rangées comme ci-dessous.

•••••••
•••••
•••
•

Deux joueurs jouent à tour de rôle.

Lorsque c’est son tour, un joueur enlève un nombre arbitraire de
jetons dans un même rangée. Il doit en enlever au moins 1. Celui
qui enlève le dernier jeton perd.
Quelle est la stratégie optimale et comment la calculer?

Fabian Bastin Introduction

Jeu de Nim (suite)

Etat du jeu x = (x1 , x2 , x3 , x4 ), où xi est le nombre de jetons dans la

rangée i.
Le numéro d’étape n’a pas d’importance ici.

Posons
(
1 si x1 = · · · = x4 = 0 (situation gagnante),
g (x) =
0 sinon (situation perdante ou intermédiaire).

Chaque joueur applique la même stratégie.

Idée: J(x) = 1 [=0] si on est dans une position gagnante [perdante].
On essaie de mettre l’adversaire dans une position perdante.

Fabian Bastin Introduction

Jeu de Nim (suite)
Posons

J(x) = J(x1 , . . . , x4 )

g (x1 , . . . , x4 ) = 1 si x1 = x2 = x3 = x4 = 0,
=
1 − min J(x1 − u1 , . . . , x4 − u4 ) sinon,
u∈U(x)

où U(x) = {u = (u1 , . . . , u4 ) : 0 ≤ ui ≤ xi pour tout i et

exactement un seul des ui est positif}.

Ainsi, J(x) vaut 1 en cas de situation gagnante, sinon, on joue le

coup qui minimise J, vu qu’après le coup, c’est à l’adversaire de
jouer. Remarque:

arg min 1−J(x1 −u1 , . . . , x4 −u4 ) 6= arg max J(x1 −u1 , . . . , x4 −u4 ).
u∈U(x) u∈U(x)

Fabian Bastin Introduction

On peut calculer un tableau qui pour chaque x nous donne J(x) et
un coup optimal à jouer µ∗ (x). On peut simplifier les calculs en
agrégeant les états; e.g., ne considérer que les états x où
x1 ≥ x2 ≥ x3 ≥ x4 . On a

 1 si x1 = x2 = x3 = x4 = 0,

0 si x1 = 1 et x2 = x3 = x4 = 0,

J(x1 , . . . , x4 ) =

 1 si x1 = 2 et x2 = x3 = x4 = 0,
etc.


état x décision prochain état valeur J(x) condition

(0 0 0 0) — — 1
(1 0 0 0) (1 0 0 0) (0 0 0 0) 0
(x1 0 0 0) (x1 − 1 0 0 0) (1 0 0 0) 1 x1 ≥ 2
(x1 1 0 0) (x1 0 0 0) (1 0 0 0) 1 x1 ≥ 1
(2 2 0 0) (0 2 0 0) (2 0 0 0) 0
(x1 2 0 0) (x1 − 2 0 0 0) (2 2 0 0) 1 x1 ≥ 3
.. .. .. ..
. . . .

Fabian Bastin Introduction

Exemple: une fonction objectif sous forme produit.

N équipes de chercheurs travaillent (indépendamment) sur le même

problème d’ingéniérie.
On voudrait qu’au moins une équipe résolve le problème d’ici 2
mois. On dispose de b nouveaux brillants chercheurs à leur affecter.
Soit pk (uk ) la probabilité que l’équipe k échoue si on lui alloue uk
chercheurs additionnels.
La probabilité que toutes les équipes échouent est
p1 (u1 ) × · · · × pN (uN ). On veut minimiser cette probabilité.
Exemple de Hillier et Lieberman: N = 3, b = 2.

Fabian Bastin Introduction

 Probabilité d’échouer pk (u)
Nb. u de chercheurs
additionnels Équipe 1 Équipe 2 Équipe 3
0 0.40 0.60 0.80
1 0.20 0.40 0.50
2 0.15 0.20 0.30

Jk (x) = Prob. que toutes les équipes k, . . . , N échouent, si on

leur alloue x chercheurs additionnels de façon optimale.

On peut formuler le problème sous forme déterministe classique:

3
Y
min pi (xi ) = p1 (x1 )p2 (x2 )p3 (x3 ),
x
i=1
3
X
t.q. xi = 2, et xi ≥ 0, i = 1, 2, 3.
i=1

Fabian Bastin Introduction

Notons qu’on peut reconstruire une forme linéaire du problème, en
utilisant l’opérateur logarithmique:
3
X
min ln pi (xi ),
i=1
3
X
t.q. xi = 2, et xi ≥ 0, i = 1, 2, 3.
i=1

Réécrivons le problème en considérant une approche par

programmation dynamique séquentielle.

On a:
JN (x) = pN (x) pour tout x;
Jk (x) = min pk (u) × Jk+1 (x − u),
u∈{0,...,x}
x = 0, . . . , b; k = N − 1, . . . , 1.

Fabian Bastin Introduction

Un modèle de PDS probabiliste
Processus de décision markovien sur horizon fini
À l’étape k, on observe l’état xk et prend une décision uk ∈ Uk (xk ).
Puis une variable aléatoire ωk est générée selon une loi de
probabilité Pk (· | xk , uk ) qui peut dépendre de (k, xk , uk ). On
suppose que les valeurs précédentes {(xn , un , ωn ), n < k} ne nous
donnent pas d’information additionnelle sur cette loi Pk lorsqu’on
connaı̂t (k, xk , uk ).
On observe ωk , on paye un coût gk (xk , uk , ωk ), et l’état à la
prochaine étape est xk+1 = fk (xk , uk , ωk ). Coût total (aléatoire):
N−1
X
gN (xN ) + gk (xk , uk , ωk ).
k=0
Une politique admissible est une suite de fonctions
π = (µ0 , . . . , µN−1 ) telle que µk : Xk → Uk et µk (x) ∈ Uk (x) pour
tout x ∈ Xk , 0 ≤ k ≤ N − 1 (+ détails techniques: µk doit être une
fonction mesurable, etc.).
Fabian Bastin Introduction
À l’étape k, on a:
Xk = espace d’états;
Uk (x) = ensemble des décisions admissibles dans l’état x;
Dk = l’espace des perturbations ωk ;
gk = fonction de coût;
fk = fonction de transition;
xk = état du système à l’étape k;
uk = décision prise à l’étape k.
ωk = perturbation (variable aléatoire) produite à l’étape k.

wk

u k = mk(xk) System xk
xk + 1 = fk( xk,u k,wk)

mk

Fabian Bastin Introduction

Pour 0 ≤ k ≤ N + 1 et x ∈ Xk , posons

Jπ,k (x) = coût espéré total de l’étape k à la fin,

si on est dans l’état x à l’étape k
et si on utilise la politique π
N−1
" #
X
= Eπ,x gN (xN ) + gn (xn , un , ωn )
n=k

où Eπ,x indique l’espérance lorsque xk = x, un = µn (xn ) et

xn+1 = fn (xn , un , ωn ) pour n = k, . . . , N − 1.
Pour une politique π donnée, on a l’équation de récurrence

Jπ,N (x) = gN (x) pour tout x ∈ XN

Jπ,k (x) = Eπ,x [gk (x, µk (x), ωk ) + Jπ,k+1 (fk (x, µk (x), ωk ))]
pour 0 ≤ k ≤ N, x ∈ Xk .

où l’espérance est par rapport à ωk qui suit la loi Pk (· | x, µk (x)).

Fabian Bastin Introduction

En effet:
Jπ,k (x)
h i
PN−1
= Eπ,x gN (xN ) + n=k gn (xn , un , ωn )
h h PN−1 ii
= Eπ,x Eπ,x gN (xN ) + n=k gn (xn , un , ωn ) | ωk
h h PN−1 ii
= Eπ,x gk (x, µk (x), ωk ) + Eπ,x gN (xN ) + n=k+1 gn (xn , un , ωn ) | ωk
= Eπ,x [gk (x, µk (x), ωk ) + Jπ,k+1 (fk (x, µk (x), ωk ))] .

On cherche une politique π qui minimise Jπ,0 (x0 ), l’espérance

mathématique de la somme des coûts de l’étape 0 à l’étape N.
Notons π ∗ = (µ∗0 , µ∗1 , . . . , µ∗N−1 ) une telle politique optimale. Posons

Jk∗ (x) = coût espéré total optimal de l’étape k à la fin,

si on est dans l’état x à l’étape k
= min Jπ,k (x)
π
= min Jµk ,...,µN−1 ,k (x).
µk ,...,µN−1

Fabian Bastin Introduction

Proposition.
(A) On a Jk∗ ≡ Jk , où les fonctions Jk sont définies par les équations
de récurrence (ou équations de la programmation dynamique):

JN (x) = gN (x) ∀x ∈ XN
Jk (x) = min E [gk (x, u, ωk ) + Jk+1 (fk (x, u, ωk ))]
u∈Uk (x)
pour 0 ≤ k ≤ N − 1, x ∈ Xk ,

où l’espérance E est par rapport à ωk qui suit la loi Pk (· | x, u).

(B) Une valeur de u qui fait atteindre l’infimum est une décision
optimale à prendre lorsqu’on est dans l’état x à l’étape k. On peut
définir une politique optimale (si elle existe) par

µ∗k (x) = arg min E [gk (x, u, ωk ) + Jk+1 (fk (x, u, ωk ))] .
u∈Uk (x)

On a alors Jk ≡ Jπ∗ ,k pour tout k.

Fabian Bastin Introduction

Preuve informelle de (A) et (B): DPOC pages 23 et 44–46.
Pour π = (µ1 , . . . , µN−1 ), on note π k = (µk , . . . , µN−1 ). On a
N−1
" #
X
Jk∗ (x) = min Eπk ,x gN (xN ) + gi (xi , µi (xi ), ωi )
πk
i=k
pour 0 ≤ k ≤ N, x ∈ Xk .

Pour k = N, on pose JN∗ (xN ) = gN (xN ).

On montre par induction sur k (pour k = N − 1, . . . , 0) que Jk∗ = Jk .
Supposons que c’est vrai pour k + 1. On écrit π k = (µk , π k+1 ).
Preuve informelle (on suppose que tout est fini et que le min est
toujours atteint):

Fabian Bastin Introduction

 Jk∗ (xk )
"
= min Eπk ,x gk (xk , µk (xk ), ωk )
(µk ,π k+1 )

N−1
#
X
+gN (xN ) + gi (xi , µi (xi ), ωi )
i=k+1

= min Eπk ,xk gk (xk , µk (xk ), ωk )

µk

N−1
" " ##!
X
+ min Eπk+1 ,xk+1 gN (xN ) + gi (xi , µi (xi ), ωi ) | ωk
π k+1
i=k+1
∗


= min Eπk ,xk gk (xk , µk (xk ), ωk ) + Jk+1 (fk (xk , µk (xk ), ωk ))
µk
∗


= min Eπk ,xk gk (xk , uk , ωk ) + Jk+1 (fk (xk , uk , ωk ))
uk ∈Uk (xk )
= Jk (xk ).
Fabian Bastin Introduction
Procédure Chaı̂nage Arrière

pour tout x ∈ XN , JN (x) ← gN (x);

pour k = N − 1, . . . , 0 faire
pour tout x ∈ Xk faire

Jk (x) ← min E [gk (x, u, ωk ) + Jk+1 (fk (x, u, ωk ))] ;

u∈Uk (x)
µ∗k (x) ← arg min E [gk (x, u, ωk ) + Jk+1 (fk (x, u, ωk ))] ;
u∈Uk (x)

Fabian Bastin Introduction

Principe d’optimalité de Bellman (cas probabiliste)

Si π ∗ = (µ∗0 , . . . , µ∗N−1 ) est une politique optimale pour le problème

initial et si 0 < k < N, alors la politique tronquée
πk∗ = (µ∗k , . . . , µ∗N−1 ) est une politique optimale pour le
sous-problème qui consiste à minimiser
N−1
" #
X
Eµk ,...,µN−1 gN (xN ) + gn (xn , un , ωn ) | xk .
n=k

par rapport à µk , . . . , µN−1 .

Hypothèses: Temps discret, modèle markovien, coûts additifs.

Fabian Bastin Introduction

Si le coût n’est pas additif, le principe d’optimalité ne tient pas
nécessairement.
Exemple: si on veut minimiser

Eµk ,...,µN−1 [max (gk (xk , uk , ωk ), gN−1 (xN−1 , uN−1 , ωN−1 ), gN (xN )) | xk ] .

Le principe ne tient pas non plus pour le sous-problème: minimiser

" j #
X
Eµk ,...,µj gn (xn , un , ωn ) | xk
n=k

si j < N et l’état xj n’est pas déterminé, car il peut arriver que la

politique optimale π ∗ amène des coûts un peu plus élevés pour les
étapes k à j que la politique optimale pour le sous-problème, afin
d’éviter un gros coût à l’étape N, par exemple.

Fabian Bastin Introduction

Commande en boucle fermée: on prend chaque décision le plus tard
possible, lorsqu’on a le maximum d’information.
Par opposition, commande en boucle ouverte: on prend toutes les
décisions u0 , . . . , uN−1 dès le départ.
La différence de coût espéré entre les deux est la valeur de
l’information additionnelle. Cette différence peut être grande.
Dans le cas déterministe: pas de différence.
Ce modèle de PDS possède de nombreuses généralisations:
— Introduction d’un facteur d’actualisation;
— Horizon infini;
— Revenu moyen par unité de temps sur horizon infini;
— Espaces d’états et de décisions infinis;
— Évolution en temps continu;
— Etc.

Fabian Bastin Introduction

Exemple (modifié) de gestion d’un inventaire.
Monsieur D. Taillant vend des Zyx à Loinville.
Les clients arrivent au hasard pour acheter des Zyx.
Au début de chaque mois, l’avion vient à Loinville et peut apporter
une commande de Zyx. Soient:

xk = Niveau des stocks au début du mois k,

avant de commander;
uk = Nombre de Zyx commandés (et reçus) au début du mois
ωk = Nombre de Zyx demandés par les clients durant le
mois k. On suppose que les ωk dont des variables
aléatoires discrètes indépendantes;
C + cu = Coût d’une commande de u Zyx;
v = Prix de vente d’un Zyx (encaissé à la fin du mois);
B = Borne supérieure sur le niveau des stocks.
rk (xk ) = Coût d’inventaire pour xk Zyx au début du mois k;
−gN (xN ) = Valeur de revente de xN Zyx au début du mois N;

Fabian Bastin Introduction

Posons:
Jk (x) = coût espéré total pour les mois k à N, si
xk = x et que l’on suit une politique optimale;
Si les inventaires négatifs (“backlogs”) sont permis, on a
xk+1 = xk + uk − ωk
et on peut optimiser sans tenir compte des revenus de vente, car
ceux-ci ne dépendent pas de la politique. Récurrence:
JN (x) = gN (x), pour x ≤ B;

Jk (x) = min rk (x) + I(u > 0)C + cu − v E[ωk ]

0≤u≤B−x

X
+ P[ωk = i]Jk+1 (x + u − i) , x ≤ B; k = N − 1, . . . , 0;
i≥0
 
X
µ∗k (x) = arg min I(u > 0)C + cu + P[ωk = i]Jk+1 (x + u − i) .
0≤u≤B−x
i≥0

Fabian Bastin Introduction

JN (x) = gN (x), pour x ≤ B;

Jk (x) = min rk (x) + I(u > 0)C + cu − v E[ωk ]

0≤u≤B−x

X
+ P[ωk = i]Jk+1 (x + u − i) , x ≤ B; k = N − 1, . . . , 0;
i≥0
Vk (x) − rk (x)
= Jk (x) (éviter de recalculer la somme pour chaque u)
X
= min −v E[ωk ] + P[ωk = i]Jk+1 (x − i) ,
i≥0


C + c + Vk (x + 1), . . . , C + (B − x)c + Vk (B) si x < B.

µ∗k (x) = arg min (−I[u = 0]v E[ωk ] + I(u > 0)C + cu + Vk (x + u)) .
0≤u≤B−x

Fabian Bastin Introduction

Dans le cas où C = 0, on peut simplifier les calculs davantage:
def
Vk (x) = − rk (x).
Jk (x) 
X
= min −v E[ωk ] + P[ωk = i]Jk+1 (x − i), c + Vk (x + 1) .
i≥0

Coûts de calcul: supposons que la somme sur i (valeurs possibles de

ωk ) a T termes non négligeables. Les coûts de calcul sont
O(NB 2 T ) pour la récurrence sur Jk ;
O(NB(B + T )) pour la récurrence sur Vk ;
O(NBT ) pour la cas simplifié où C = 0.

Fabian Bastin Introduction

Supposons maintenant que les inventaires négatifs ne sont pas
permis. On a
xk+1 = max(0, xk + uk − ωk )
et les équations de récurrence deviennent:
JN (x) = gN (x) pour 0 ≤ x ≤ B;


Jk (x) = min rk (x) + I(u > 0)C + cu

0≤u≤B−x

X
+ P[ωk = i][−v min(i, x + u) + Jk+1 (max(0, x + u − i))]
i≥0

 0 ≤ x ≤ B; k = N − 1, . . . , 0;
pour
X
Vk (x) = min  P[ωk = i][−v min(i, x) + Jk+1 (max(0, x − i))],
i≥0


C + c + Vk (x + 1), . . . , C + (B − x)c + Vk (B)

si x < B.

Fabian Bastin Introduction

Dans le cas où C = 0:

X
Vk (x) = min  P[ωk = i][−v min(i, x) + Jk+1 (max(0, x − i))],
i≥0


c + Vk (x + 1) .

Exemple numérique: DPOC, pages 28–32.

Fabian Bastin Introduction

Exemple: taille d’un lot de pièces à fabriquer
La compagnie Essai-erreur doit fabriquer M exemplaires d’une pièce
pour remplir une commande. Les critères de qualité sont très élevés.
La compagnie estime que chaque pièce produite sera acceptable
avec probabilité p. Les pièces sont fabriquées par lots (“batches”).
Pour fabriquer un lot de u pièces, il en coûte C + cu.
Dans un lot de taille u, le nombre Y de pièces acceptables est une
variable aléatoire binomiale:
 
u
P[Y = y ] = p y (1 − p)u−y , y = 0, . . . , u.
y

En pratique, on va fabriquer un lot de taille > M, car il y aura

probablement des pièces défectueuses (des rejets).
Si le nombre de pièces acceptables est quand même inférieur à M,
on devra produire un second lot, peut-être même un troisième, etc.
Supposons qu’on a assez de temps pour produire N lots.
Si on n’a pas toutes les pièces requises après N lots, on doit payer
une énorme pénalité K .
Fabian Bastin Introduction
Taille d’un lot de pièces à fabriquer (suite)

xk = Nb de pièces encore requises avant de produire le lot k + 1;

uk = Taille du lot k + 1;
yk = Nb de pièces acceptables dans le lot k + 1;
Jk (x) = Coût espéré minimal à partir de maintenant, si on a
k lots de produits et qu’il manque encore x pièces.

On cherche le coût total espéré J0 (M) et une politique optimale.

Pour tout k et x ≤ 0, on a Jk (x) = 0. Pour x > 0:

JN (x) = K ;  
u  
X u
Jk (x) = min C + cu + p y (1 − p)u−y Jk+1 (x − y )
u≥x y
y =0
 
00
µ∗k (x) = arg min .
u≥x

Peut-on simplifier ces équations pour réduire les coûts de calcul?

Fabian Bastin Introduction
Autre notation souvent utilisée: pas de ωk dans la notation.
On définit un noyau de transition (famille de lois de probabilité) par
Q(A | xk , uk ) = P[xk+1 ∈ A | xk , uk ]
= Pk ({ωk ∈ Dk : fk (xk , uk , ωk ) ∈ A}).
On peut remplacer le coût gk (xk , uk , ωk ) par
g̃k (xk , uk ) = E[gk (xk , uk , ωk ) | xk , uk ].
Si Xk ≡ X est fini ou dénombrable, les noyaux de transition
deviennent des matrices de probabilité de transition: on a une
chaine de Markov commandée à espace d’états dénombrable.
On pourra dénoter, par exemple,
pij (u, k) = P[xk+1 = j | xk = i, uk = u].
La matrice P(u, k) dont les éléments sont les pij (u, k) est la matrice
des probabilités de transition à l’étape k, sous la décision u.
Si P(u, k), Uk et g̃k ne dépendent
 pas de k (modèle stationnaire):

X
Jk (i) = min g̃ (i, u) + pij (u)Jk+1 (j) .
u∈U(i)
Fabian Bastin
j
Introduction
Exemple: commande d’une file d’attente finie

On a une file d’attente avec un seul serveur, avec de la place pour n

clients au maximum dans le système, qui évolue en temps discret.
À chaque période, P[m clients arrivent] = pm , m ≥ 0.
Le serveur a 2 vitesses: rapide et lent.
Pour une période en mode rapide [lent], le coût du serveur est cf
[cs ], et si le système n’est pas vide, on sert 1 client avec probabilité
qf [qs ] et 0 clients avec probabilité 1 − qf [1 − qs ].
Il y a aussi un coût de r (i) à chaque période où il y a i clients dans
le système au début de la période.

Fabian Bastin Introduction

État: nombre de clients dans le système.
L’espace des décisions est U = {rapide, lent}.
Soit ξk le nombre de clients servis à la période k.

JN (i) = r (i), pour 0 ≤ i ≤ n;

Jk (0) = r (0) + cs + Vk (0);
Jk (i) = r (i) + min[cf + qf Vk (i − 1) + (1 − qf )Vk (i),
cs + qs Vk (i − 1) + (1 − qs )Vk (i)]
pour 0 ≤ k ≤ N − 1, 1 ≤ i ≤ n,

où

Vk (i) = E [Jk+1 (xk+1 ) | xk − ξk = i]

n−i−1
X ∞
X
= pm Jk+1 (i + m) + Jk+1 (n) pm .
m=0 m=n−i

Fabian Bastin Introduction

Exemple: choix du niveau de risque à chaque étape

Un match est constitué d’une suite d’étapes.

Décisions: à chaque étape, le joueur 1 peut adopter une stratégie
prudente (conservatrice) ou agressive (risquée).
Stratégie prudente [agressive]: on marque i points de plus que
l’adversaire avec probabilité pi [qi ], disons pour −b ≤ i ≤ b.
La variance de la loi des qi est plus grande que celle des pi .
On suppose que le joueur 2 joue toujours de la même façon.
Note: si le joueur 2 optimisait aussi sa stratégie: théorie des jeux.
Plus compliqué. On y reviendra.

Jeu de type A: Celui ou celle ayant le plus de points après N étapes

gagne; en cas d’égalité on ajoute des étapes jusqu’à ce que l’un des
joueurs devance l’autre.
Jeu de type B: Le premier joueur qui devance l’autre par au moins
K points gagne le match.
Fabian Bastin Introduction
État x: nombre de points d’avance du joueur 1 sur le joueur 2.
Jk (x) = probabilité que le joueur 1 gagne s’il a x points d’avance
sur le joueur 2 après k étapes de jeu et s’il prend ses décisions de
façon optimale, i.e., pour maximiser sa probabilité de gain.
Pour un jeu de type B, Jk ≡ J ne dépend pas de k et on a:

1 pour x ≥ K ;



 0 pourb x ≤ −K ;



b
!
J(x) = X X

 max pi J(x + i), qi J(x + i)



 i=−b i=−b
pour − K < x < K .

Fabian Bastin Introduction

Applications possibles:
— Une série de la coupe Stanley (N = 7).
— Un match de hockey divisé en blocs (étapes) de 5 secondes.
— Une course cycliste par étapes.
— Une stratégie d’investissement en finance: fonction objectif
différente.
— Etc.

DPOC, Exemples 1.1.5, 1.3.3: match d’échecs de N parties.

À chaque partie, le joueur 1 peut gagner (i = 1), perdre (i = −1),
ou annuler (i = 0). Après N parties, si un joueur devance l’autre, il
gagne le match, tandis que si le score est égal, on continue et le
premier joueur qui gagne une partie gagne le match.
On suppose que p1 = 0 et p−1 = 1 − p0 (en mode prudent, on peut
seulement annuler ou perdre) et que q0 = 0 et q−1 = 1 − q1 (en
mode agressif, on peut gagner ou perdre).

Fabian Bastin Introduction

 0.5-0.5 1- 0
pd pw

0-0 0-0
1 - pd 1 - pw

0-1 0-1

1st Game / Timid Play 1st Game / Bold Play

2-0
2-0
pw

pd 1-0 1 - pw
1-0 1.5-0.5
1.5-0.5
1 - pd
pw
pd 0.5-0.5 1-1
0.5-0.5 1-1 1 - pw
1 - pd
pw
pd 0.5-1.5
0.5-1.5
0-1
0-1 1 - pw
1 - pd
0-2
0-2

Fabian Bastin
2nd Game / Timid Play Introduction2nd Game / Bold Play
On a ici

Jk (x) = JN (x) pour k > N;


 1 si x > 0;
JN (x) = q1 si x = 0;
0 si x < 0;



 1 si x > 1;
 p0 + (1 − p0 )q1 si x = 1; (jeu prudent);


JN−1 (x) = q1 si x = 0; (jeu agressif);

 q 2 si x = −1; (jeu agressif);
 1


0 si x < −1;
Jk (x) = max[p0 Jk+1 (x) + (1 − p0 )Jk+1 (x − 1),
q1 Jk+1 (x + 1) + (1 − q1 )Jk+1 (x − 1)]
pour 0 ≤ k < N et − k ≤ x ≤ k.

Fabian Bastin Introduction

Si N = 2, au début du match on a

J0 (0) = max [p0 J1 (0) + (1 − p0 )J1 (−1), q1 J1 (1) + (1 − q1 )J1 (−1)]

= max p0 q1 + (1 − p0 )q12 , q1 p0 + (1 − p0 )q12 + (1 − q1 )q12
 

= q1 p0 + (1 − p0 )q12 + (1 − q1 )q12 (jeu agressif).

La politique optimale si N = 2 est donc:

jouer prudent si on est en avance, jouer agressif sinon.

Fabian Bastin Introduction

 pd 1.5-0.5

1- 0
1 - pd
pw
Timid Play
1-1
0-0
1 - pw
Bold Play
pw 1- 1

0-1
1 - pw
Bold Play
0-2

Fabian Bastin Introduction

Intéressant: On pourrait croire que q1 < 1/2 implique que
J0 (0) < 1/2, mais non. Notre probabilité de gagner le match peut
dépasser 1/2 même si notre probabilité de gagner une partie est
toujours < 1/2.
Par exemple, si q1 = 0.45 et p0 = 0.90, alors J0 (0) ≈ 0.530.

Explication: Le joueur 1 choisit son style de jeu à chaque étape et

peut adapter sa stratégie au pointage, ce qui lui donne un avantage
sur le joueur 2, qui n’a aucun choix.
Le joueur 1 utilise une politique en boucle fermée. S’il était forcé de
choisir toutes ses décisions à l’avance (politique en boucle ouverte),
on aurait:

décisions prob. de gagner

prudent, prudent p02 q1
prudent, agressif p0 q1 + (1 − p0 )q12
agressif, prudent p0 q1 + (1 − p0 )q12
agressif, agressif q12 + 2(1 − q1 )q12

Fabian Bastin Introduction

En supposant que p0 ≥ 2q1 , la meilleure politique en boucle ouverte
est de jouer prudent pour une étape et agressif pour l’autre.
La prob. de gagner est alors

J˜0 (0) = J0 (0) − (1 − q1 )q12 .

Cette différence de (1 − q1 )q12 est la valeur de l’information.

Par exemple, si q1 = 0.45 et p0 = 0.90, alors (1 − q1 )q12 ≈ 0.105 et
la probabilité de gain avec la meilleure politique en boucle ouverte
est ≈ 0.425.
Conclusion: fixer toutes nos décisions à l’avance est une bien
mauvaise idée.

Fabian Bastin Introduction

Reformulation pour “markovianiser”

Que faire si les hypothèses ne sont pas vérifiées, e.g., si fk , gk et la

loi de ωk dépendent des états et décisions précédant xk et uk ?
En général, on peut toujours se ramener au modèle de base (que
nous avons décrit) en redéfinissant judicieusement les espaces
d’états, de décisions, et de perturbations.
Il suffit d’incorporer suffisamment d’information dans l’état xk
(“state augmentation”).

Fabian Bastin Introduction

Par exemple, si fk [ou gk ] dépend de (xk−1 , uk−1 , xk , uk , ωk ), on
peut redéfinir l’état xk par x̃k = (xk−1 , uk−1 , xk ) et la fonction de
transition devient

x̃k+1 = f˜k (x̃k , uk , ωk ) = (xk , uk , fk (xk−1 , uk−1 , xk , uk , ωk )).

À la limite, on peut définir l’état comme étant toute l’histoire du

processus observée jusqu’à date.
On peut ainsi traiter (en principe) des modèles non additifs.
Mais si l’espace d’états est trop grand, on ne pourra pas résoudre
les équations de récurrence! La malédiction des grandes dimensions
(“the curse of dimensionality”)
Il faut être parcimonieux dans la définition de l’état.

Fabian Bastin Introduction

Exemple: DPOC, p.38.
Supposons qu’à l’étape k, juste avant de prendre la décision uk , on
obtient une prévision yk nous donnant une information plus précise
sur la loi de ωk .
Par exemple, supposons que pour i = 1, . . . , m, P[yk = i] = pi , et
ωk suit la loi Qi lorsquePyk = i.
On a donc P[ωk ∈ ·] = m i=1 pi Qi [·].
On peut se ramener à notre modèle de base en redéfinissant l’état et
la perturbation par x̃k = (yk , xk ) et ω̃k = (ωk , yk+1 ). On obtient
m
" #
X
J˜k (yk , x) = min E gk (x, u, ωk ) + pi J˜k+1 (i, fk (x, u, ωk )) | yk
u∈Uk (x)
i=1
pour 0 ≤ k ≤ N − 1, x ∈ Xk , yk ∈ {1, . . . , m}.

Fabian Bastin Introduction

Mais dans ce cas-ci, il n’est pas nécessaire de mettre yk dans l’état.
Au lieu d’écrire la récurrence en termes des fonctions J˜k (yk , xk ), on
peut l’écrire en termes des fonctions
m
X
Jˆk (xk ) = pi J˜k (i, x).
i=1

On obtient
m
X h i
Jˆk (x) = pi min E gk (x, u, ωk ) + Jˆk+1 (fk (x, u, ωk )) | yk = i .
u∈Uk (x)
i=1

Cela équivaut à observer l’état xk avant d’obtenir la prévision, puis

de prendre la décision uk après avoir observé la prévision.
La décision est prise avec davantage d’information que l’état xk ,
mais on peut quand même écrire la récurrence en termes de
fonctions de xk seulement. C’est plus économique.

Fabian Bastin Introduction

Subtilités mathématiques.

Pour que les espérances Eπ et Eµk ,...,µN−1 soient bien définies, on

doit faire des hypothèses de mesurabilité sur les fonctions fk , gk , et
µk , et les espaces Sk , Uk , et Dk doivent avoir une structure
additionnelle (espaces métriques complets mesurables, etc.). Et on
doit s’assurer qu’il existe une politique optimale qui satisfait les
conditions de mesurabilité.
Dans le cas où les Dk sont dénombrables: pas de problème.
Cas général: beaucoup plus complexe. Nous n’allons pas aborder
ces questions ici.
Questions intéressantes du point de vue mathématique, mais pas
beaucoup d’impact du point de vue pratique.
Références: Bertsekas et Shreve (1978) et Hernández-Lerma et
Lasserre (1995).

Fabian Bastin Introduction

Fonction d’utilité et mesure de risque.

L’espérance mathématique du coût (ou du revenu) n’est pas

toujours la mesure appropriée à optimiser.
Exemple: le paradoxe de St-Petersbourg:
Vous payez x dollars pour jouer au jeu suivant. On tire à pile ou
face, on compte le nombre Y de faces avant l’obtention du premier
pile, et vous recevez 2Y dollars. L’espérance de gain net est
∞
X 1
2y −x =∞
2y +1
y =0

quelque soit x. Mais est-on vraiment prêt à payer un montant

arbitrairement grand pour jouer à ce jeu? Non.
On a une très grande probabilité de recevoir un montant modeste,
et une probabilité minuscule de recevoir un montant gigantesque.
Mais l’utilité d’un gain gigantesque n’est pas proportionnelle au gain.
Fabian Bastin Introduction
Critère min-max
Approche pessimiste: dans le cas où il y a de l’incertitude, on
considère toujours le pire cas (au lieu de l’espérance). C’est le cas
extrême d’aversion au risque.
Au lieu de minimiser (par rapport à π, pour x0 = x)
N−1
" #
X
Eπ,x gN (xN ) + gn (xn , µn (xn ), ωn )
n=0

on voudra minimiser
N−1
" #
X
max gN (xN ) + gn (xn , µn (xn ), ωn ) .
ω1 ,...,ωN
n=0

Rarement la bonne solution. Sauf si ωn est la décision d’un

adversaire. Avec un tel critère, un investisseur ne va jamais investir!

Fabian Bastin Introduction

Fonction d’utilité

Solution beaucoup plus intéressante: fonction d’utilité.

Le preneur de décision veut maximiser E[U(X )] où X est le gain net
et U : R → R est sa fonction d’utilité.
On se ramène au cas précédent, en remplaçant X par U(X ).
Habituellement, la fonction U est croissante et concave.

(i) Neutre au risque: U est croissante et linéaire.

(ii) Propension au risque: U est croissante et strictement convexe.
(iii) Aversion au risque: U est croissante et strictement concave.

Fabian Bastin Introduction

Dans l’appendice G.2 de DPOC, Proposition G.1, on donne des
conditions suffisantes pour l’existence d’une telle fonction U, dans le
cas où X prend les valeurs o1 , . . . , on avec probabilités p1 , . . . , pn .
n
X
E[U(X )] = pi U(oi ).
i=1

Le rôle de la fonction d’utilité consiste essentiellement à modifier la

valeur d’un gain, selon son utilité, de manière à pouvoir exprimer
l’objectif comme une espérance mathématique.

Fabian Bastin Introduction

 P
Si oi ≥ 0 représente le gain, et si i pi U(oi )/oi = 1 (il suffit de
multiplier U par une constante pour obtenir cela), alors on peut
obtenir un résultat équivalent en modifiant les probabilités à la place
de prendre une fonction d’utilité: on remplace pi par
qi = pi U(oi )/oi :
n
X n
X
E[U(X )] = pi U(oi ) = qi o i .
i=1 i=1

C’est ce que l’on fait pour l’évaluation d’options financières.

L’importance sampling (en simulation) équivaut à changer les deux
(les pi et l’utilité) sans changer l’espérance.

Fabian Bastin Introduction

Exemple.
On a deux possibilités d’investissement pour notre capital:
(A) placement sûr qui rapportera 1.5 dollar par dollar investi;
(B) placement risqué qui rapporte 1 dollar par dollar investi avec
probabilité p et 3 dollars par dollar investi avec probabilité 1 − p.
Supposons que l’on place une fraction d du capital dans l’option A,
et 1 − d dans l’option B. L’utilité espérée sera

E[U(X )] = p U(1.5d + (1 − d)) + (1 − p) U(1.5d + 3(1 − d)).

Quelqu’un qui n’aime pas le risque choisira un d plus grand, et

vice-versa.
En général, plus on est riche ou jeune, plus on a raison de préfèrer le
risque (on aura une fonction U(x) dont la dérivée seconde sera plus
proche de 0 pour les grandes valeurs de x).Pour les valeurs
négatives, l’utilité U(−x) peut devenir une constante lorsque
x → ∞.
Fabian Bastin Introduction