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 Π

On peut facilement calculer g:

N ∑ i=1  Πi ai = 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, disons δ_i;
comment calculer les δ_i pour savoir quels sont les bons états?

δ_i  =  a_i + ∑_j=1ⁿ P_i,jδ_j -g

mais cela ne suffit pas pour déterminer les δ;

on ajoute

N ∑ i=1  Πi δi = 0

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: 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 ρ euros au temps t+1; 0 < ρ < 1.

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

vi  =  ai + ρ N ∑ j=1  Pi,j vj

Système non singulier: on peut calculer les v_i de ces équations parce que ρ < 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+ρ+ρ² +ρ³ …) =  g/(1-ρ). Donc g ρ^t /(1-ρ) est une approximation au coût à partir de temps t (t grand et la chaîne régulière).

• soit g
• soit v_i pour l'état initial i.

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:
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 δ_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.)

• Réduction des coûts à chaque itération
• Un nombre fini de politiques possibles
• Donc, terminaison garantie
• En principe pourrait être très lente
  (nombre de politiques très élevé)
• Mais ``en pratique'' l'algorithme trouve la politique optimale après un nombre raisonnable d'itérations

On peut définir v⁽ⁿ⁾_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, v_i est le coût d'avoir commencé en l'état i.

On a
v_i = a_i - g + ∑_j=1^N P_i,jv_j

mais ces équations ne suffisent pas (ajout de la même constante k à chaque v_i donne une nouvelle solution) Il faut ajouter

N ∑ i=1  Πi vi = 0

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

• Choisir une politique initiale
• Calculer Π, g et les v_i
• Utiliser ces v_i pour chercher une meilleure décision en chaque état
• Itérer tant qu'il y a amélioration

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 à ρ×(1833-1299).