My question is if I should select state_action pairs by theirs immediate reward or should I select them by the episode reward?
By the return (sum of all rewards) from the whole episode. A lot of decisions made in "good" episodes do not lead to immediate rewards, but instead transition towards states where better rewards are possible.
In retrospect, you do not know whether any single action was a good choice, but with the cross entropy method (CEM) you rely on the fact that on average the better episodes will contain more good decisions than the worse episodes, so you train the policy neural network on the state, action pairs from the elite episodes as if all the decisions were correct. This will not be true, but will hopefully be true more often than by chance, so the policy should improve.
This can be a noisy, high variance approach with any RL method. CEM is one of the most sensitive to noise and variance. However, the taxi environment is deterministic, and that makes using CEM more reasonable.