Benchmarks for reinforcement learning in discrete MDPs

Question

To compare the performance of various algorithms for perfect information games, reasonable benchmarks include reversi and m,n,k-games (generalized tic-tac-toe). For imperfect information games, something like simplified poker is a reasonable benchmark.

What are some reasonable benchmarks to compare the performance of various algorithms for reinforcement learning in discrete MDPs? Instead of using a random environment from the space of all possible discrete MDPs on $n$ states and $k$ actions, are there subsets of such a space with more structure that are more reflective of "real-world" environments? An example of this might be so-called gridworld (i.e. maze-like) environments.

This is a related question, though I'm looking for specific examples of MDPs (with specified transitions and rewards) rather than general areas where MDPs can be applied.

Edit: Some example MDPs are found in section 5.1 (Standard Domains) of Efficient Bayes-Adaptive Reinforcement Learning using Sample-Based Search (2012) by Guez et al.:

The Double-loop domain is a 9-state deterministic MDP with 2actions, 1000 steps are executed in this domain. Grid5 is a 5×5 grid with no reward anywhere except for a reward state opposite to the reset state. Actions with cardinal directions are executed with small probability of failure for 1000 steps. Grid10 is a 10×10 grid designed like Grid5. We collect 2000 steps in this domain. Dearden’s Maze is a 264-states maze with 3 flags to collect. A special reward state gives the number of flags collected since the last visit as reward, 20000 steps are executed in this domain.

Answer 1

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.

POMDP Benchmarks

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.

^References:

• ^{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), pages 477–484.}
• ^{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.}