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 Π
On peut facilement calculer 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 = ai + ∑j=1n Pi,jδj -g
mais cela ne suffit pas pour déterminer les δ;
on ajoute
|
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...
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+τ).
|
Système non singulier: on peut calculer les vi 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+ρ+ρ2 +ρ3 …) = 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).
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 dès 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 vi);
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.)
Démonstration que si la politique actuelle n'est pas optimale, on trouve forcément une meilleure politique (pour les cas avec actualisation):
On a une politique actuelle (1) avec ses vi donnés
par
vi1 = ai1+ρ∑j=1N
Pi,j1vj1
et on suppose qu'il existe une politique optimale (2)
vi2 = ai2+ρ∑j=1N
Pi,j2vj2
et, si la politique actuelle n'est pas déjà optimale, on
a toujours
vi2 < =vi1 et pour au
moins un i vi2 < vi1. On
choisit un k
tel que vk1-vk2
prend sa valeur maximum D.
Quand notre algorithme considère l'état k il calcule
vk* = ai2+ρ∑j=1N
Pi,j2vj1 et on a
vk1-vk* = vk1-vk2+vk2-vk*
=D-ρ∑j=1N Pi,j2(vj2-vj1) > D(1-r) > 0.