Approche de Courtois et Semal

Par exemple, l'idée est d'étudier uniquement le problème à l'état stationnaire et le considérer comme un problème d'algèbre linéaire. On étudie donc l'équation

$$\pi (P - Id) = 0$$

On s'intéresse comme dans d'autres méthodes à une récompense $r(i)$ calculée sur la distribution stationnaire $\pi$. Cette approche numérique a été proposée par Courtois et Semal puis a été étendue par de nombreux auteurs. On cherche à borner $\sum_i r(i) \pi(i)$ sans connaitre la distribution $\pi$. La première hypothèse est que nous pouvons encadrer $r(i)$ : $\rho_1 \leq r(i) \leq \rho_2$ pour tout $i$.

On divise l'espace d'états de la chaîne en deux composantes $G$ et $H$. $G$ contient les états utiles pour le calcul de la récompense alors que $H$ ne contient que des états de très faibles probabilités, ce qui permet d'avoir une borne efficace. Soit R la récompense que l'on cherche à obtenir et soit $RG$ et $RH$ les récompense conditionnelles sachant que l'on est dans un état de $G$ ou de $H$. On a :

$$R = \pi (G) RG + \pi (H) RH$$

On élimine $RH$ grâce à l'encadrement sur les récompense $r(i)$ et on note que $\pi(H) = 1 - \pi(G)$ pour obtenir une formule générale d'encadrement :

$$\pi (G) (RG - \rho_1) + \rho_1 \leq R \leq \pi (G) (RG - \rho_2) + \rho_2$$

Si on est capable d'obtenir un encadrement de $RG$ et de $\pi(G)$ alors on peut obtenir un encadrement sur $R$. Courtois et Semal ont montré que le vecteur $\pi_G$ est compris dans un polyhèdre dont les points extrémaux sont, en général, plus faciles à calculer, ce qui donne une borne de la récompense $R$. L'approche est initialement totalement algébrique et implique quelques contraintes sur le graphe de la chaîne. Des extensions et améliorations proposées, en particulier par Carrasco puis par par Rubino et Mahévas, emploient des propriétés sur les temps d'absorption, de nature plus probabilistes. Il y a les liens entre ces algorithmes et les approches modulaires, déjà explorés par Buchholz en 2002, et que nous souhaitons approfondir au sein du projet grâce à une collaboration PRiSM-ARMOR.