One of the simplest problems
A slot machine with K levers
You assign internal rewards at all of the hidden layer steps (steps before the final step)
The further the internal step is from the final step, the more its reward is decreased. So for instance, the final reward might be 100, the second last step gets 90, the third last gets 85, etc.
The TD-Gammon program from 1995 can become master-level after playing about 1.5M games with itself