Chaînes de Markov avec coûts associés
(tous les états persistants et apériodiques)

Coût d'une transition: Ai,j pour la transition de i à j (ne dépend pas du temps ni de l'histoire)

Coût moyen d'une transition: de l'état i:
ai  =  N
å
j=1 
Pi,jAi,j

Tendance vers la moyenne:

Le coût moyen par transition tend vers g où g est le coût moyen d'une transition dans la distribution limite P

On peut facilement calculer g:
N
å
i=1 
Pi ai = g

Décisions qui peuvent changer
les probabilités de transition

La possibilité de choix: supposons que dans l'état i on peut choisir entre plusieurs décisions et que pour la décision d, la probabilité d'aller en état j est Pdi,j avec un coût adi,j

on peut calculer l'espérance du coût d'une transition:
adi  =  N
å
j=1 
Pdi,j adi,j
mais minimiser ca (la politique gloutonne) n'est pas forcément la bonne politique

Le nombre de politiques possibles peut être trop grand pour permettre de calculer le g de chacune
et peut-être ce n'est pas la politique possédant le plus petit g qu'il convient de choisir...

Actualisation des coûts

Un compromis entre la politique gloutonne et minimiser g

Actualisation: Un euro aujourd'hui est plus utile qu'un euro l'année prochaine;
Un coût d'un euro aujourd'hui est plus grave qu'un pareil coût l'année prochaine;

On veut calculer les coûts sur la supposition qu'un euro au temps t vaut r euros au temps t+1; 0 < r < 1.

Rapport avec le taux d'intérêt: si le taux réel d'intérêt (payé ou reçu) est t, on a
r = 1/(1+t).

Calcul des coûts
Les équations pour les coûts totaux: On a toujours un coût immédiat (moyen) en l'état i de ai et une probabilité Pi,j de transition de l'état i à j:


vi  =  ai + r N
å
j=1 
Pi,j vj

Système non singulier: on peut calculer les vi de ces équations parce que r < 1.

Le coût dans la distribution limite: Si le coût moyen d'une transition dans la distribution limite (sans actualisation) est g, le coût (total) si on commence dans cette distribution est g(1+r+r2 +r3 ¼) =  g/(1-r). Donc g rt /(1-r) est une approximation au coût à partir de temps t (t grand et la chaîne régulière).

Calcul d'une politique optimale avec actualisation
On considère (enfin) le cas où on peut choisir entre plusieurs décisions en chaque état et on veut minimiser le coût total avec actualisation.
C'est évident que la décision optimale en chaque état ne dépend ni de l'histoire ni du temps.

On peut utiliser l'algorithme d'amélioration d'une politique initiale: calculer le coût total (avec actualisation) vj à partir de chaque état j; choisir à chaque état i la décision *d qui minimise a *di + råj=1N P *di,j vj; répéter tant qu'il y a une réduction;
(Ca équivaut à minimiser le coût qu'on aurait si on choisissait une nouvelle politique pour la première étape et gardait l'ancienne politique après, ce qui explique pourquoi il y a amélioration)

Terminaison de l'algorithme

Démonstration plus ``mathématique'' que l'algorithme réduit les coûts à chaque étape, sauf si on est déjà à une politique optimale:

D'abord avec les décisions d on a:
vdi  =  adi + r N
å
j=1 
Pdi,j vdj

On choisit *d tel que
a *di + r N
å
j=1 
P *di,j vdj £ vdi
(et on continue si on a < pour au moins un i)

Les vrais nouveaux coûts sont donnés par:
*v *di = a *di + r N
å
j=1 
P *di,j *v *dj

Donc:
vdi - *vi *d ³ r N
å
j=1 
P *di,j(vdj - *vj *d)
(et on a > pour au moins un i)

Considérons le i qui donne le minimum de vid - *vi *d: on a


vdi - *vi *d ³ r N
å
j=1 
P *di,j(vdi - *vi *d)


vdi - *vi *d ³ r(vdi - *vi *d)


vdi - *vi *d ³ 0

et, donc, vdj - *vj *d ³ 0 pour tout j

Finalement on ne peut pas avoir =0 pour tout j; et donc on a une amélioration pour tout j...

Le cas sans actualisation
Ce cas est plus compliqué parce que les équations:
vi  =  ai + r N
å
j=1 
Pi,j vj
ne sont pas utilisables si r = 1; (soit aucune solution, soit plusieurs)

On peut définir v(n)i le coût moyen d'une suite de n transitions à partir de l'état i. On trouve que
v(n)i  ®   n g + vi
où, maintenant, vi est le coût d'avoir commencé en l'état i.

On a
vi = ai - g + åj=1N Pi,jvj

mais ces équations ne suffisent pas (ajout de la même constante k à chaque vi donne une nouvelle solution) Il faut ajouter
N
å
i=1 
Pi vi = 0

On essaie d'optimiser la politique en utilisant la même idée que dans le cas avec actualisation:

Un exemple: assurance d'un véhicule
Le coût de l'assurance d'un véhicule est 100, 200, 400 ou 600.
Après un an sans aucun accident déclaré, le prix est réduit au niveau inférieur
Après un an avec un accident déclaré, le prix est augmenté au niveau supérieur
La probabilité d'un accident grave est 5% par an
La probabilité d'un accident mineur est 15% par an et le coût de sa réparation est 500
Devrait-on déclarer un accident mineur ou payer la réparation?
(nous prenons r = 0.9 et supposons les coûts actualisés au début de l'année)

Calcul de la politique optimale
Je commence avec la politique de déclarer tout incident
v1
=
100 + 0.9(.8v1+.2v2)
v2
=
200 + 0.9(.8v1+.2v3)
v3
=
400 + 0.9(.8v2+.2v4)
v4
=
600 + 0.9(.8v3+.2v4)
et je calcule v=[1315,1489,1905,2405]
Donc une meilleur politique pour les niveau 200 et 400 est de payer les réparations (par exemple pour v2, 200 + 0.9(.8v1+.2v3) > 275 + 0.9(.95v1+.05v3)):
v1
=
100 + 0.9(.8v1+.2v2)
v2
=
275 + 0.9(.95v1+.05v3)
v3
=
475 + 0.9(.95v2+.05v4)
v4
=
600 + 0.9(.8v3+.2v4)
et v=[1304,1472,1839,2347] Maintenant on voit qu'une meilleur politique à v2 est de déclarer l'accident
(parce que maintenant
200 + 0.9(.8v1+.2v3)
   <   275 + 0.9(.95v1+.05v3))

Donc, une troisième politique:
v1
=
100 + 0.9(.8v1+.2v2)
v2
=
200 + 0.9(.8v1+.2v3)
v3
=
475 + 0.9(.95v2+.05v4)
v4
=
600 + 0.9(.8v3+.2v4)
et v=[1299,1465,1833,2341]
la solution optimale!
Le modèle n'est pas très réaliste (tous les accidents mineurs n'ont pas le même coût) mais ce calcul peut aider à prendre de bonnes décisions, par exemple en l'état 2 déclarer un sinistre si le coût est supérieur à r×(1833-1299).



File translated from TEX by TTH, version 3.05.
On 7 Oct 2002, 14:49.