Answers.Body: <ol>
  <li><p>In non-trivial cases, the transition matrix is (generally) not maintained in the traditional tabular form. If the representation used factored notation (Factored MDP) then Dynamic Bayesian networks can be used. </p></li>
  <li><p>Another approach would be to abstract state spaces so that you have reduced number of states in the representation of P. These can be roughly classified as model minimization techniques.</p></li>
  <li><p>Hierarchical representations can be adopted if some tasks can be split. E.g., the classical "taxi problem" has an explicit Get-passenger and Put-passenger task, that form the hierarchy. Now each of the smaller tasks can possibly have a well formed transition function.</p></li>
  <li><p>It may also be prudent to use model free learning methods in such cases.</p></li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-05-18T14:27:19.813Z
Answers.LastActivityDate: 2017-05-18T14:27:19.813Z
Answers.UserDisplayName: okkhoy
Body: <p>I understand an MDP (Markov Decision Process) model is a tuple of <span class="math-container">$\{S, A, P, R \}$</span> where:</p>
  
  <ul>
  <li><span class="math-container">$S$</span> is a discrete set of states</li>
  <li><span class="math-container">$A$</span> is a discrete set of actions</li>
  <li><span class="math-container">$P$</span> is the transition matrix ie. <span class="math-container">$P(s' \mid s, a) \rightarrow [0,1]$</span></li>
  <li><span class="math-container">$R$</span> is the reward function id. <span class="math-container">$R(s, a, s') \rightarrow \mathbb{R}$</span></li>
  </ul>
  
  <p>For a non-trivial MDP, say <span class="math-container">$1000$</span> states and <span class="math-container">$10$</span> actions, the transition matrix has theoretically <span class="math-container">$S \times A \times S = 10,000,000$</span> entries (though many entries will be <span class="math-container">$0$</span>).</p>
  
  <p>I understand that one way of generating the <span class="math-container">$P$</span> matrix is to estimate it via Monte Carlo sampling, by simulating the environment. However, with non-trivial state space and simulation costs, this could be prohibitively expensive.</p>
  
  <p>In practice, when a non-trivial MDP is being formulated, what are the different ways an accurate <span class="math-container">$P$</span> matrix can be produced?</p>
  
Tags: <reinforcement-learning><markov-decision-process><monte-carlo-methods><transition-model>
Title: How do you generate the transition probabilities of a non-trivial MDP?
UserDisplayName: Brendan Hill
ThreadText: # How do you generate the transition probabilities of a non-trivial MDP?
  
  (Asked by: username_0 on 2016-12-22)
  
  I understand an MDP (Markov Decision Process) model is a tuple of $\{S, A, P, R \}$ where:
  
  * $S$ is a discrete set of states
  * $A$ is a discrete set of actions
  * $P$ is the transition matrix ie. $P(s' \mid s, a) \rightarrow [0,1]$
  * $R$ is the reward function id. $R(s, a, s') \rightarrow \mathbb{R}$
  
  For a non-trivial MDP, say $1000$ states and $10$ actions, the transition matrix has theoretically $S \times A \times S = 10,000,000$ entries (though many entries will be $0$).
  
  I understand that one way of generating the $P$ matrix is to estimate it via Monte Carlo sampling, by simulating the environment. However, with non-trivial state space and simulation costs, this could be prohibitively expensive.
  
  In practice, when a non-trivial MDP is being formulated, what are the different ways an accurate $P$ matrix can be produced?
  
  **Tags:** reinforcement-learning, markov-decision-process, monte-carlo-methods, transition-model
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2017-05-18. Score: 1
  
  1. In non-trivial cases, the transition matrix is (generally) not maintained in the traditional tabular form. If the representation used factored notation (Factored MDP) then Dynamic Bayesian networks can be used.
  2. Another approach would be to abstract state spaces so that you have reduced number of states in the representation of P. These can be roughly classified as model minimization techniques.
  3. Hierarchical representations can be adopted if some tasks can be split. E.g., the classical "taxi problem" has an explicit Get-passenger and Put-passenger task, that form the hierarchy. Now each of the smaller tasks can possibly have a well formed transition function.
  4. It may also be prudent to use model free learning methods in such cases.
  
  
  ---
  
  