4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.


tag-game

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.
$\endgroup$
  • $\begingroup$ How does this answer the question? If it really answers the question, edit your post to clarify how. $\endgroup$ – nbro Sep 3 at 15:38
  • $\begingroup$ It does not directly answer the question, but I am giving some information that is closely related and hopefully helps the questioner: benchmarks for POMDPs. $\endgroup$ – agold Sep 3 at 21:03
  • $\begingroup$ Your answer might be useful to some people, but it is misleading indeed. $\endgroup$ – nbro Sep 3 at 21:12
  • $\begingroup$ I am sorry if the answer is misleading, but my intention is to help the questioner; furthermore, I am indicating that it is not the answer to his/her question. Could you please give some feedback on why you think this answer is "misleading"? $\endgroup$ – agold Sep 3 at 21:18
  • 1
    $\begingroup$ Ok, to clear it up I have added "discrete", but by definition, an MDP is discrete, also see the book of Sutton & Barto. In the case of continuous states/actions, this is indicated specifically as Continuous (time) MDP. $\endgroup$ – agold Sep 3 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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