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:
|
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:
|
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:
|
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...
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).
|
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).
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)
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:
|
On choisit *d tel que
|
Les vrais nouveaux coûts sont donnés par:
|
Donc:
|
Considérons le i qui donne le minimum de vid - *vi *d: on a
|
|
|
Finalement on ne peut pas avoir =0 pour tout j; et donc on a une amélioration pour tout j...
|
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
|
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
|
On essaie d'optimiser la politique en utilisant la même idée que dans le cas avec actualisation:
|
|
Donc, une troisième politique:
et v=[1299,1465,1833,2341]
v1
=
100 + 0.9(.8v1+.2v2)
v2
=
200 + 0.9(.8v1+.2v3)
v3
=
475 + 0.9(.95v2+.05v4)
v4
=
600 + 0.9(.8v3+.2v4)
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).