\include{header}


\begin{slide}{Cha\^{\i}nes avec co\^uts associ\'es}
\heading{
(tous les \'etats persistants et ap\'eriodiques)
}

Co\^ut d'une transition: $A_{i,j}$ (en moyenne) pour une transition de $i$ \`a $j$

Co\^ut moyen d'une transition: de l'\'etat $i$: 
\[ a_i ~=~ \sum_{j=1}^N P_{i,j}A_{i,j}\]


Tendance vers la moyenne:

Le co\^ut moyen par transition tend vers $g$
o\`u $g$ est le co\^ut moyen d'une transition dans la distribution limite $\Pi$
\end{slide}

\begin{slide}{Calcul de $g$}

\[  \sum_{i=1}^N \Pi _i a_i =g\]

Différences entre les états:\\
pour tout $i$ on sait que la limite de\\
$cout ~des ~t~premieres~transitions/t$ est $g$ mais tous les états
ne sont pas égaux; pour un état $i$ on a que la limite de\\
$cout ~des ~t~premieres~transitions-tg$ existe, $\delta_i$;\\
comment calculer les $\delta_i$ pour savoir quels sont les bons états?

$\delta_i ~=~ a_i + \sum_{j=1}^n P_{i,j}\delta_j -g$

mais cela ne suffit pas pour déterminer les $\delta$;

on ajoute 
$  \sum_{i=1}^N \Pi _i \delta_i =0$
\end{slide}

\begin{slide}{}
\heading{D\'ecisions qui peuvent changer\\les probabilit\'es de transition
}

La possibilit\'e de choix: supposons que dans l'\'etat $i$ on peut choisir
entre plusieurs {\it d\'ecisions} et que pour la d\'ecision $d$, la probabilit\'e
d'aller en \'etat $j$ est $P^d_{i,j}$ avec un co\^ut $a^d_{i,j}$

on peut calculer l'esp\'erance du co\^ut d'une transition:
\[a^d_i ~=~ \sum_{j=1}^N P^d_{i,j} a^d_{i,j}\]
mais minimiser ca (la politique gloutonne)
n'est pas forc\'ement la bonne politique
\end{slide}

\begin{slide}{Décider la meilleur politique}
Le nombre de politiques possibles peut \^etre trop grand pour
permettre de calculer le $g$ de chacune\\
et peut-\^etre ce n'est pas la politique poss\'edant le plus petit $g$
qu'il convient de choisir...

\end{slide}


\begin{slide}{}
\heading{Actualisation des  co\^uts
}

Un compromis entre la politique gloutonne et minimiser $g$

Actualisation: Un euro aujourd'hui est plus utile qu'un euro l'ann\'ee prochaine;\\
Un co\^ut d'un euro aujourd'hui est plus grave qu'un pareil co\^ut l'ann\'ee prochaine;

On veut calculer les co\^uts sur la supposition qu'un euro au temps $t+1$ vaut $\rho$
euros au temps $t$; $0<\rho <1$.

Rapport avec le taux d'int\'er\^et: si le taux r\'eel d'int\'er\^et (pay\'e ou re\c{c}u) est $\tau$,
on a\\$\rho = 1/(1+\tau )$.
\end{slide}

\begin{slide}{}
\heading{Calcul des co\^uts
}
Les \'equations pour les co\^uts totaux: On a toujours un co\^ut imm\'ediat (moyen)
en l'\'etat $i$ de $a_i$ et une probabilit\'e $P_{i,j}$ de transition de l'\'etat $i$
\`a $j$:

\[ v_i ~=~ a_i + \rho \sum_{j=1}^N P_{i,j} v_j \]

Syst\`eme non singulier: on peut calculer les $v_i$ de ces \'equations
parce que
$\rho< 1$.

\end{slide}

\begin{slide}{ Optimisation des co\^uts }
Selon notre point de vue nous voulons choisir une politique de
fa\c{c}on \`a minimiser
\begin{itemize}
\item soit \colmath{g} (sans actualisation)
\item soit \colmath{v_i} pour l'\'etat initial \colmath{i} (avec actualisation).
\end{itemize}

Existence d'algorithmes assez efficaces qui convergent sur une
politique optimale.

Dans les deux cas l'algorithme consiste à commencer avec une politique
arbitraire et de l'améliorer tant que l'amélioration est non nulle.
\end{slide}

\begin{slide}{
Principe d'amélioration}
Calculer les valeurs rélatives des états
(différences entre les états de l'espérance de la somme de tous les
coûts de transition jusqu'à l'infini, actualisée ou non;
c'est-à-dire les $\delta_i$ ou les $v_i$);\\
décider une nouvelle politique basée sur le coût de la première
transition plus la valeur de l'etat après cette transition
(actualisée le cas échéant.)

 
\end{slide}

\begin{slide}{}
\heading{
Calcul d'une politique optimale avec actualisation
}

On peut utiliser l'algorithme d'am\'elioration d'une
politique initiale: calculer le co\^ut total (avec actualisation) $v_j$ \`a partir de
chaque \'etat $j$; choisir \`a chaque \'etat $i$ la d\'ecision $ *{d}$ qui minimise
$a^{ *{d}}_i + \rho \sum_{j=1}^N P^{ *{d}}_{i,j} v_j$;
r\'ep\'eter tant qu'il y a une r\'eduction;\\
(Ca \'equivaut \`a
minimiser le co\^ut qu'on aurait si on choisissait une nouvelle
politique pour la premi\`ere \'etape et gardait l'ancienne politique
apr\`es, ce qui explique pourquoi il y a am\'elioration)
\end{slide}
\begin{slide}{}
\heading{
Terminaison de l'algorithme
}
\begin{itemize}
\item R\'eduction des co\^uts \`a chaque it\'eration
\item Un nombre fini de politiques possibles
\item Donc, terminaison garantie
\item En principe pourrait \^etre tr\`es lente\\
(nombre de politiques tr\`es \'elev\'e) 
\item Mais ``en pratique'' l'algorithme trouve la politique optimale
apr\`es un nombre raisonnable d'it\'erations
\end{itemize}

\end{slide}



\begin{slide}{ Le cas sans actualisation }
Ce cas est plus compliqu\'e parce que les \'equations:
\[ v_i ~=~ a_i + \rho \sum_{j=1}^N P_{i,j} v_j \]
ne sont pas utilisables si $\rho=1$; (soit aucune solution,
soit plusieurs)

Rappel : on a  $ \delta_i = a_i - g + \sum_{j=1}^N P_{i,j}\delta_j $


On essaie d'optimiser la politique en utilisant la m\^eme
id\'ee que dans le cas avec actualisation:
\end{slide}

\begin{slide}{L'algorithme}
\begin{itemize}
\item Choisir une politique initiale
\item Calculer $\Pi$, $g$ et les $\delta_i$
\item Utiliser ces $\delta_i$ pour chercher une meilleure
d\'ecision en chaque \'etat
\item It\'erer tant qu'il y a am\'elioration
\end{itemize}
\end{slide}



\begin{slide}{ Un exemple: assurance d'un v\'ehicule }
Le co\^ut de l'assurance d'un v\'ehicule est 100, 200, 400 ou
600.\\
Apr\`es un an sans aucun accident d\'eclar\'e, le prix est r\'eduit
au niveau inf\'erieur\\
Apr\`es un an avec un accident d\'eclar\'e, le prix est augment\'e
au niveau sup\'erieur\\
La probabilit\'e d'un accident grave est 5\% par an\\
La probabilit\'e d'un accident mineur est 15\% par an et le
co\^ut de sa r\'eparation est 500\\[1cm]
Devrait-on d\'eclarer un accident mineur ou payer la r\'eparation?\\
(nous prenons $\rho=0.9$ et supposons les co\^uts actualis\'es au
d\'ebut
de l'ann\'ee)

\end{slide}


\begin{slide}{}
\heading{
Calcul de la politique optimale
}
Je commence avec la politique de d\'eclarer tout incident
\textcolor{magenta}{\begin{eqnarray*}
v_1 &=& 100 + 0.9(.8v_1+.2v_2)\\
v_2 &=& 200 + 0.9(.8v_1+.2v_3)\\
v_3 &=& 400 + 0.9(.8v_2+.2v_4)\\
v_4 &=& 600 + 0.9(.8v_3+.2v_4)
\end{eqnarray*}}
et je calcule $\color{red}{\bf v}=[1315,1489,1905,2405]$\\
Donc une meilleur politique pour les niveau 200 et 400
est de payer les r\'eparations (par exemple pour $v_2$,
$200 + 0.9(.8v_1+.2v_3)>275 + 0.9(.95v_1+.05v_3)$):
\end{slide}

\begin{slide}{Faire le même calcul pour la nouvelle politique}

\textcolor{magenta}{\begin{eqnarray*}
v_1 &=& 100 + 0.9(.8v_1+.2v_2)\\
v_2 &=& 275 + 0.9(.95v_1+.05v_3)\\
v_3 &=& 475 + 0.9(.95v_2+.05v_4)\\
v_4 &=& 600 + 0.9(.8v_3+.2v_4)
\end{eqnarray*}}
et $\color{red}{\bf v}=[1304,1472,1839,2347]$
\end{slide}
\begin{slide}{}
Maintenant on voit qu'une meilleur politique \`a $v_2$
est de d\'eclarer l'accident\\
(parce que maintenant\\
$200 + 0.9(.8v_1+.2v_3)$\\$~~<~~275 + 0.9(.95v_1+.05v_3)$)

Donc, une troisi\`eme politique:
\textcolor{magenta}{\begin{eqnarray*}
v_1 &=& 100 + 0.9(.8v_1+.2v_2)\\
v_2 &=& 200 + 0.9(.8v_1+.2v_3)\\
v_3 &=& 475 + 0.9(.95v_2+.05v_4)\\
v_4 &=& 600 + 0.9(.8v_3+.2v_4)
\end{eqnarray*}}
et $\color{red}{\bf v}=[1299,1465,1833,2341]$.
\end{slide}

\begin{slide}{
On a trouvé la solution\\optimale!}

\color{black}Le mod\`ele n'est pas tr\`es r\'ealiste (tous les
accidents mineurs n'ont pas le m\^eme co\^ut)
mais ce calcul peut aider \`a prendre de bonnes d\'ecisions,
par exemple en l'\'etat $2$ d\'eclarer un sinistre si le co\^ut
est sup\'erieur \`a $\rho\times(1833-1299)$.
\end{slide}


\end{document}









