def policy_improvement(P_prev, P_sampled, alpha):
    """
    Perform policy improvement step. This function interpolates between the
    previous and newly sampled estimates for the probabilities P(a' > a | s).

    Please see the description of the prob_to_Q function above for a more 
    detailed description of the format of the estimates P(a' > a | s). This 
    applies to P_prev, P_sampled, and the function's output.
    
    Inputs: 1) P_prev: previous estimates of P(a' > a | s); this is a 
               num_states x num_actions x num_states matrix.
            2) P_sampled:  newly-sampled estimates for P(a' > a | s); this is a 
               num_states x num_actions x num_states matrix.
            3) alpha: number between 0 and 1; this is the learning rate 
               hyperparameter.
    
    Output: num_states x num_actions x num_states interpolation between P_prev
            and P_sampled. This will be used as a new estimate of P(a' > a | s).
    """
    
    return (1 - alpha) * P_prev + alpha * P_sampled