Nous considérons le problème du contrôle optimal actualisé à horizon infini formalisé dans le cadre des processus de décision Markoviens. Nous nous focalisons sur plusieurs variations approchées du schéma itération sur les politiques: itérations sur les politiques approché (API), itérations sur les politiques conservatif (CPI), une adaptation naturelle de l'algorithme ''Policy Search by Dynamic Programming'' au cas de l'horizon infini (PSDP), et itérations sur les politiques non-stationnaires (NSPI). Pour tous ces algorithmes, nous décrivons des bornes de performance en fonction de l'erreur $\epsilon$ à chaque itération, et faisons une comparaison en portant une attention particulière aux coefficients de concentration impliqués, au nombre d'itérations et à la mémoire requis. Notre analyse souligne plusieurs points: 1) Les garanties de performance de CPI peuvent être arbitrairement meilleures que celle d'API, mais au prix d'une augmentation---exponentielle en $\frac{1}{\epsilon}$---du nombre d'itérations. 2) PSDP combine les avantages d'API et CPI: sa garantie de performance est similaire à celle de CPI, et elle est obtenue en un nombre d'itérations identique à celui d'API. 3) Contrairement à API qui requiert une mémoire constante, la mémoire dont CPI et PSDP ont besoin est proportionnelle au nombre d'itérations, ce qui peut être problématique lorsque le facteur d'actualisation $\gamma$ est proche de 1 ou lorsque l'erreur d'approximation $\epsilon$ est proche de 0; nous montrons que l'algorithme NSPI permet de faire un compromis entre la bonne mémoire d'API et la meilleure performance de PSDP. Enfin, des simulations numériques de ces schémas algorithmiques confirment notre analyse.