Which machine learning model should I learn for this problem?
You should use a Markov reward model to model your problem. All the possible words are the different states of your chain. The replacement process corresponds to the transitions of your Markov chain.

After defining all the properties of your chain (states, transitions, rewards, ...), you can train your model and get the best strategy for each current word.