I'm working in python. Would like to practice some machine learning, and I've always been curious about an analog to the problem below...

A collection of 3 letters are drawn randomly from the 26 letters of the alphabet. None, any, or all of the letters can be discarded and replaced with an equal number of not-yet-drawn letters. This discarding and replacing happens 3 times (or more generally n times). After all the replacements have taken place a point value is awarded to the resulting 3-letter-word. Some words have high point values, and others less so. I'm interested in the optimum replacement strategy. For example, say only the words "FOX" and "THE" reward any value. All other 3 letter combos are worthless. I want the machine to learn the correct replacement strategy while holding "FOW" with one replacement remaining. In this simple case, the strategy is to replace the W only, and attempt to draw the X. This strategy is superior to replacing all 3 letters in an attempt to make "THE," since drawing "THE" only gets points 1/('count of remaining letters' choose 3) times, whereas replacing the W gets points 1/('count of remaining letters'); the instance where an X is drawn.

Can anyone point me in the right direction?


1 Answer 1


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.

  • 1
    $\begingroup$ I think this is heading in the right direction, but you cannot usually "train" a Markov model. If you include the selection/rejection policy in the MRR, then you could try some kind of search (e.g. a GA). But better would be to use a Markov Decision Process (MDP) model of the environment and apply some kind of reinforcement learning solver to find the optimum policy. Given the scale of the OP's problem, I would suggest using dynamic programming because it is likely they could find a perfectly optimised policy that way. $\endgroup$ May 14, 2018 at 7:22
  • $\begingroup$ @NeilSlater I'm checking this out now. youtu.be/5R2vErZn0yw Seems to be what I need $\endgroup$
    – GotYaNumba
    May 14, 2018 at 8:04
  • $\begingroup$ @GotYaNumba Yes. If your problem scales up (e.g. larger numbers of letters, more complex rules) then you will want to move on from DP. But many other RL approaches are similar to DP, so it's a good entry point to learn how they work. e.g. Q-learning is effectively value iteration using samples. $\endgroup$ May 14, 2018 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.