I was wondering if there was any known problems to reduce from in order to prove the hardness of a game based on a markov decision process.
For example imagine you have 10 states that a ball can visit. The game start at a random state. Then you have to predict the next 10 movements of the ball. Then you observe the ball rolling across states following an MDP for which you do not know the probability of transitions. You get a score for the number of states you predicted correctly. Then the ball start again at another random location, you have to predict its next 10 mouvements etc... As you observe the ball explore the MDP each time you learn a bit more of the real transition probabilities.
Is there a way to prove hardness of this game, the goal being to predict the most adequate sequence ?
Thanks !