In [1]:
from pylab import *
%matplotlib inline

Remplacement optimal

On dispose d'une machine que l'on doit remplacer de temps en temps. On note $X_t\in\{0,\dots,S\}$ l'age de la machine à l'instant $t$ ($t$ est discret). Si machine a un age $x$, elle tombe en panne avec probabilité $p_x$ entre $t$ et $t+1$ et doit être remplacée ce qui coûte $C$. La machine peut aussi être remplacé de façon pro-active à un coût $C$. Elle doit être remplacée dès que l'age atteint $S$.

Le but de cet exercice est de calculer une politique de remplacement qui minimise le coût actualisé de remplacement.

Question 1 (sur papier)

Formuler le problème comme un processus de décision Markovien:

  • Quel est l'espace d'état / d'action
  • Quel est la fonction de coût
  • Quelles sont les transitions
In [2]:
## Paramètres numériques
p = [.5-.5*cos(.1*k/pi) for k in range(-40,100)]
plot(p)
S=140   # Taille de l'espace d'état
C = 3
R = 1
delta = .99

Question 2 : Value Iteration

Écrire un algorithme qui utiliser "value iteration" pour calculer une politique optimale de remplacement (en complétant le code ci dessous). Tracer la politique et la fonction de valeur en fonction de l'état.

In [ ]:
V = [0]*S # On initialise la fonction de valeur 

# Value iteration algorithm 
for i in range( SOMETHING ):
    for s in range(S-1):
        V[s] = min (  SOMETHING  )
    V[S-1] = SOMETHING 

    
# Meilleure politique
policy = [0]*S
for s in range(S-1):
    if  SOMETHING :
        policy[s] = 1
        
# Pour tracer
subplot(2,1,1); plot(policy)
subplot(2,1,2); plot(V)
In [ ]:

Policy iteration

Le but de cette question est d'écrire un algorithme utilisant l'algorithme "policy iteration" pour calculer une politique optimale. On rappelle l'algorithme:

  1. Initialiser une politique $\pi$
  2. Calculer $V_\pi$ tel que $V_\pi = C_\pi + Q_{\pi} V_\pi$, où $C_\pi$ est le coût de la politique et $Q_{\pi}$ est la matrice de transition correspondant à la politique.
  3. Trouver une politique $\pi'$ qui maximise $C_{\pi'} + Q_{\pi'} V_\pi$.
  4. Revenir à l'étape 2 tant que $\pi\ne\pi'$

Note: de façon matricielle, le $V_{\pi}$ de l'étape 2 est la solution d'un système linéaire qui est peut s'écrire comme $V_\pi = (I-Q_{\pi})^{-1} C_\pi $

Matrices de coût et de transition

Écrire deux fonctions Q_C_pi(politique) qui retourne la matrice de transition et de coût correspondant à la politique.

In [ ]:
def Q_C_pi(politique):
    Q_pi = matrix([[0.]*S for i in range(S)])
    C_pi = [0]*S
    for s in range(S):
        if (politique[s]==1): # We replace
            #SOMETHING
        else:
            #SOMETHING ELSE
    return(Q,transpose(matrix(C_pi)))

Algorithme de policy iteration

In [ ]:
policy = [1]*S
for iteration in range(10):
    Q_pi,C_pi = Q_C_pi(policy)
    V_pi = # SOMETHING
    new_policy = #SOMETHING
    
    if policy == new_policy: break
    policy = new_policy

print('convergence in {0} iterations'.format(iteration)) 
subplot(2,1,1); plot(V_pi)
subplot(2,1,2); plot(policy)
In [ ]:

2. Le problème du stagiaire

On intéroge $n$ candidats pour un poste. Notre but est d'embaucher le meilleur des $n$ candidats.

Après avoir intérogé un nouveau candidat, on sait s'il est meilleur que les candidats précédents (mais pas comment il se comparera aux suivants). Il faut alors décider soit de l'embaucher, soit de passer au suivant (mais on ne peut pas revenir en arrière).

Le but est de maximiser la probabilité d'embaucher le meilleur candidat.

  • Formaliser le problème comme un processus de décision Markovien
    • (indication: on pourra prendre comme espace d'état $E=\{0,1\}$ avec 0 si le candidat n'est pas meilleur que ceux précédent et 1 si le candidat est le meilleur de tous ceux déjà vu).
  • Écrire un algorithme de type "value iteration" qui calcule la politique optimale.
  • Décrire la stratégie optimale (pour n=10, 100, 200, 500). Qu'en déduisez vous?
In [ ]:
In [ ]: