Although I am not aware of any "benchmark problems" for (discrete) MDPs, I'll comment a bit on possible benchmarks and I will show some benchmarks used to test POMDP algorithms.
MDP vs POMDP
In Markovian Decision Processes (MDPs) the whole state space is known, this means you know all the information for your problem; therefore, you can use them to find solutions for perfect information problems or games.
Many of these games could use an MDP, some examples: 2048 and chess. Note that you must take into mind that the computational complexity grows with the number of states.
Although I could not find any benchmarks for MDPs, games with perfect information can be used to compare MDP solvers.
When a problem or game has imperfect information, you should use a Partially Observable Markovian Decision Processes (POMDPs); in which you do not need to know the current state, but you keep track of the probabilities of being in any of the (discrete) states.
Since I worked with POMDPs, I will comment some of the benchmarks researches used for discrete POMDPs (Pineau et al. (2003), Spaan and Vlassis (2004), Kurniawati et al. (2008), Ong et al. (2010), ArayaLopez et al. (2010)):
- Tag: a robot and target move in a grid environment and can move one step at a time, moving has a cost, and a reward is gained if the robot is at the same position as the target (i.e. tagged it).
- Two-Robot Tag: two robots attempt to catch a target, thereby sharing their observations and actions; the target tries to get away from them.
- Mazes (Littman et al. (1995), Kaelbling et al. (1998), Spaan and Vlassis (2004)):
- Hallway and Hallway2 are robot navigation tasks in a hallway, where the robot has only local noisy sensor information. The difficulty of hallways is it being long areas which look alike, which causes ambiguity in the localization.
- Tiger-grid a two world state with a tiger being either behind the left or right door. The actions are listen, open the right or left door and there is a positive reward when opening the door without the tiger, otherwise a large negative reward.
- Rock Sample: a rover explores a grid area, it knows its own position and the position of the rocks, however, it does not know which rocks are valuable. The rover can sense how valuable they are, but this sensor is less reliable when it is used farther away.
The tag game: the robot (blue) and target on a map with 29 positions and 870 states (29 for the robot, 29 + 1 (tagged) for the target).
These problems tend to be of the same size (number of states and actions) such that the results of different algorithms can be compared easily.
- Araya-Lopez, M., Thomas, V., Buffet, O., and Charpillet, F. (2010). A closer look at MOMDPs. In 2010 22nd IEEE International Conference on Tools with Artificial Intelligence, volume 2, pages 197–204.
- Kaelbling, L.P., Littman, M.L., Cassandra, A.R. (1998).
Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1-2): 99-134
- Kurniawati, H., Hsu, D., and Lee, W. (2008). SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. In Proceedings of Robotics: Science and Systems IV, Zurich, Switzerland.
- Littman, M.L., Cassandra, A.R. and Kaelbling, L.P. (1995). Learning policies for partially observable environments: Scaling up. in Proc. 12th Int. Conf. on Machine Learning, San Francisco, CA.
- Ong, S. C. W., Png, S. W., Hsu, D., and Lee, W. S. (2010). Planning under Uncertainty for Robotic Tasks with Mixed Observability. The International Journal of Robotics Research, 29(8):1053–1068.
- Pineau, J., Gordon, G., and Thrun, S. (2003). Point-based value iteration: An anytime algorithm for POMDPs. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI),
- Spaan, M. T. J. and Vlassis, N. (2004). A point-based POMDP algorithm for robot planning. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pages 2399–2404, New Orleans, Louisiana.