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 Π

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  =  ai + j=1n Pi,jδj -g

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

on ajoute

N

i=1 
Πi δi = 0

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 ρ 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+τ).

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 + ρ N

j=1 
Pi,j vj

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).

Optimisation des coûts

Selon notre point de vue nous voulons choisir une politique de façon à minimiser

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.




File translated from TEX by TTH, version 3.05.
On 21 Nov 2005, 14:51.

symboles bricolés pour netscape par sed