Answers.Body: <p>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.</p>
  
  <h1>MDP vs POMDP</h1>
  
  <p>In <a href="https://en.wikipedia.org/wiki/Markov_decision_process" rel="nofollow noreferrer">Markovian Decision Processes (MDPs)</a> 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 <a href="https://en.wikipedia.org/wiki/Perfect_information" rel="nofollow noreferrer"><em>perfect information</em></a> problems or games. 
  Many of these games could use an MDP, some examples: <a href="https://jdlm.info/articles/2018/03/18/markov-decision-process-2048.html" rel="nofollow noreferrer">2048</a> and <a href="https://www.chessprogramming.org/Reinforcement_Learning" rel="nofollow noreferrer">chess</a>. Note that you must take into mind that the <a href="http://web.mit.edu/jnt/www/Papers/J016-87-mdp-complexity.pdf" rel="nofollow noreferrer">computational complexity</a> 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.</p>
  
  <p>When a problem or game has <em>imperfect information</em>, you should use a  <a href="https://en.wikipedia.org/wiki/Partially_observable_Markov_decision_process" rel="nofollow noreferrer"><em>Partially Observable Markovian Decision Processes (POMDPs)</em></a>; 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.</p>
  
  <h2>POMDP Benchmarks</h2>
  
  <p>Since I worked with <em>POMDPs</em>, 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)):</p>
  
  <ul>
  <li><em>Tag</em>: 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).</li>
  <li><em>Two-Robot Tag</em>: two robots attempt to catch a target, thereby sharing their observations and actions; the target tries to get away from them.</li>
  <li><em>Mazes</em> (Littman et al. (1995), Kaelbling et al. (1998), Spaan and Vlassis (2004)): 
  
  <ul>
  <li><em>Hallway</em> and <em>Hallway2</em> 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.</li>
  <li><em>Tiger-grid</em> a two world state with a tiger being either behind the left or right door. The actions are <em>listen</em>, <em>open the right</em> or <em>left</em> door and there is a positive reward when opening the door without the tiger, otherwise a large negative reward.</li>
  </ul></li>
  <li><em>Rock Sample</em>: 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.</li>
  </ul>
  
  <p><br/>
  <a href="https://i.sstatic.net/gKzqF.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/gKzqF.png" alt="tag-game"></a></p>
  
  <p><sup>The <em>tag</em> 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).</sup></p>
  
  <p>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.</p>
  
  <p><sup><strong>References</strong>:</sup></p>
  
  <ul>
  <li><sup>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.</sup></li>
  <li><sup>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</sup></li>
  <li><sup>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.</sup></li>
  <li><sup>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.</sup></li>
  <li><sup>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.</sup></li>
  <li><sup>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.</sup></li>
  <li><sup>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.</sup></li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-03T08:31:02.280Z
Answers.LastActivityDate: 2019-09-15T15:54:24.273Z
Answers.LastEditDate: 2019-09-15T15:54:24.273Z
Answers.UserDisplayName: agold
Body: <p>To compare the performance of various algorithms for <a href="https://en.wikipedia.org/wiki/Perfect_information" rel="nofollow noreferrer">perfect information games</a>, reasonable benchmarks include <a href="https://en.wikipedia.org/wiki/Reversi" rel="nofollow noreferrer">reversi</a> and <a href="https://en.wikipedia.org/wiki/M,n,k-game" rel="nofollow noreferrer">m,n,k-games</a> (generalized tic-tac-toe). For imperfect information games, something like <a href="https://en.wikipedia.org/wiki/Kuhn_poker" rel="nofollow noreferrer">simplified poker</a> is a reasonable benchmark.</p>
  
  <p>What are some reasonable benchmarks to compare the performance of various algorithms for reinforcement learning in <strong>discrete</strong> <a href="https://en.wikipedia.org/wiki/Markov_decision_process" rel="nofollow noreferrer">MDPs</a>? Instead of using a random environment from the space of all possible discrete MDPs on <span class="math-container">$n$</span> states and <span class="math-container">$k$</span> 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.</p>
  
  <p><a href="https://stats.stackexchange.com/questions/145122/real-life-examples-of-markov-decision-processes">This</a> 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.</p>
  
  <p><strong>Edit:</strong> Some example MDPs are found in section 5.1 (Standard Domains) of <a href="https://papers.nips.cc/paper/4767-efficient-bayes-adaptive-reinforcement-learning-using-sample-based-search.pdf" rel="nofollow noreferrer">Efficient Bayes-Adaptive Reinforcement Learning using Sample-Based Search</a> (2012) by Guez et al.:</p>
  
  <blockquote>
    <p>The <strong>Double-loop</strong> domain is a 9-state deterministic MDP with 2actions,
    1000 steps are executed in this domain. <strong>Grid5</strong> 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. <strong>Grid10</strong> is a 10×10 grid designed like Grid5.
    We collect 2000 steps in this domain. <strong>Dearden’s Maze</strong> 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.</p>
  </blockquote>
  
Tags: <reinforcement-learning><environment><markov-decision-process><benchmarks>
Title: Benchmarks for reinforcement learning in discrete MDPs
UserDisplayName: user76284
ThreadText: # Benchmarks for reinforcement learning in discrete MDPs
  
  (Asked by: username_0 on 2019-09-01)
  
  To compare the performance of various algorithms for [perfect information games](https://en.wikipedia.org/wiki/Perfect_information), reasonable benchmarks include [reversi](https://en.wikipedia.org/wiki/Reversi) and [m,n,k-games](https://en.wikipedia.org/wiki/M,n,k-game) (generalized tic-tac-toe). For imperfect information games, something like [simplified poker](https://en.wikipedia.org/wiki/Kuhn_poker) is a reasonable benchmark.
  
  What are some reasonable benchmarks to compare the performance of various algorithms for reinforcement learning in **discrete** [MDPs](https://en.wikipedia.org/wiki/Markov_decision_process)? 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](https://stats.stackexchange.com/questions/145122/real-life-examples-of-markov-decision-processes) 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](https://papers.nips.cc/paper/4767-efficient-bayes-adaptive-reinforcement-learning-using-sample-based-search.pdf) (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.
  
  **Tags:** reinforcement-learning, environment, markov-decision-process, benchmarks
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-09-03. Score: 5 | Accepted answer
  
  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)](https://en.wikipedia.org/wiki/Markov_decision_process) 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*](https://en.wikipedia.org/wiki/Perfect_information) problems or games.
  Many of these games could use an MDP, some examples: [2048](https://jdlm.info/articles/2018/03/18/markov-decision-process-2048.html) and [chess](https://www.chessprogramming.org/Reinforcement_Learning). Note that you must take into mind that the [computational complexity](http://web.mit.edu/jnt/www/Papers/J016-87-mdp-complexity.pdf) 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)*](https://en.wikipedia.org/wiki/Partially_observable_Markov_decision_process); 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](https://i.sstatic.net/gKzqF.png)](https://i.sstatic.net/gKzqF.png)
  
  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.
  
  
  ---
  
  