Answers.Body: <p>In addition to the reason outlined in the comment, also note that if the state-space and action-space are both finite and of feasible size, tabular methods can be used, and there are some advantages to them (like the existence of convergence guarantees and generally a smaller number of hyperparameters to tune).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-04T19:41:39.477Z
Answers.LastActivityDate: 2020-05-04T19:41:39.477Z
Answers.UserDisplayName: BGasperov
Answers.Body: <p><strong>Note: I assume you mean, countable Action and State Sets by 'Finite'.</strong></p>
  
  <p><em>MDP(s) are not exclusive to finite spaces only. They can be used in Continuous/uncountable sets of Action and States too.</em></p>
  
  <p><em>Markov Decision Process (MDP)</em> is a tuple <span class="math-container">$(\mathcal S, \mathcal A, \mathcal P^a_s, \mathcal R^a_{ss'}, \gamma, \mathcal S_o)$</span> where <span class="math-container">$\mathcal S$</span> is a set of States, <span class="math-container">$\mathcal A$</span> is the set of actions, <span class="math-container">$\mathcal P_{s}^a: \mathcal A \times \mathcal S \rightarrow [0, 1]$</span> is a function that denotes Probability distribution over the states if action <span class="math-container">$a$</span> is execuited at state <span class="math-container">$s$</span>. [1][2]</p>
  
  <p>Where, Q-function is defined as:</p>
  
  <p><span class="math-container">$$ Q^\pi (s,a) = \mathbb E_\pi \left [ \sum \limits_{t=0}^{+\infty} \gamma(t)r_t | s_o = s, a_o = a \right] \tag{*}$$</span></p>
  
  <p><em>Note that <span class="math-container">$r_t$</span> is just special case of Reward function <span class="math-container">$\mathcal R^a_{ss'}$</span>.</em> </p>
  
  <p>Now, if states and actions are discrete, then, the Q-Table Method<a href="https://towardsdatascience.com/simple-reinforcement-learning-q-learning-fcddc4b6fe56" rel="nofollow noreferrer">[3]</a> which is a state-action matrix helps us to evaluate <span class="math-container">$Q$</span> function and optimize efficiency.</p>
  
  <p>Whereas, in cases where the state/action sets are infinite or continuous, Deep Networks are preferred to Approximate <span class="math-container">$Q$</span> function. <a href="https://www.geeksforgeeks.org/deep-q-learning/" rel="nofollow noreferrer">[4]</a>.</p>
  
  <p><strong>Q-Learning is Off-Policy method, doesn't require <span class="math-container">$\pi$</span> policy function</strong></p>
  
  <hr>
  
  <h2>References:</h2>
  
  <ol>
  <li>R. S. Sutton and A. G. Barto. <em>Reinforcement Learning: An Introduction</em>. MIT Press,
  1998.</li>
  <li>Alborz Geramifard, Thomas J. Walsh, Stefanie Tellex, Girish Chowdhary, Nicholas Roy and Jonathan P. How. <em>A Tutorial on Linear Function Approximators for Dynamic Programming and Reinforcement Learning</em>. Foundations and Trends (R) in Machine Learning
  Vol. 6, No. 4 (2013) 375–454</li>
  <li>Andre Violante. <a href="https://towardsdatascience.com/simple-reinforcement-learning-q-learning-fcddc4b6fe56" rel="nofollow noreferrer"><em>Simple Reinforcement Learning: Q-learning</em></a>, <em>Create a q-table</em>, <a href="https://towardsdatascience.com" rel="nofollow noreferrer">https://towardsdatascience.com</a>, 2019.</li>
  <li>Alind Gupta. <a href="https://www.geeksforgeeks.org/deep-q-learning/" rel="nofollow noreferrer"><em>Deep Q-Learning</em></a>, Deep Q-Learning, <a href="https://www.geeksforgeeks.org/deep-q-learning/" rel="nofollow noreferrer">https://www.geeksforgeeks.org/deep-q-learning/</a>, 2020.</li>
  </ol>
  
  <hr>
  
  <p><strong>Edit: I'd like to thank @nbro for editing suggestions.</strong></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-05T17:48:26.670Z
Answers.LastActivityDate: 2020-05-05T18:11:40.323Z
Answers.LastEditDate: 2020-05-05T18:11:40.323Z
Answers.UserDisplayName: Abhas Kumar Sinha
Answers.Body: <p>To my knowledge you can't compute or solve an uncountably large MDP numerically. It will need to be discretized in some capacity. The same applies for classic control: you can't optimize over the true functional so you use a discrete approximation to the system and solve that. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-05T21:10:36.143Z
Answers.Text: I should point out as a matter of practicality, everything is perhaps discrete in the limit. Think about an incredibly fine grained MDP to the point quantum effects start to dominate and the idea of "position" no longer exists.
Answers.UserDisplayName: FourierFlux
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-05T21:07:02.903Z
Answers.LastActivityDate: 2020-05-05T21:07:02.903Z
Answers.UserDisplayName: FourierFlux
Body: <blockquote>
    <p>In the standard Markov Decision Process (MDP) formalization of the reinforcement-learning (RL) problem (Sutton &amp; Barto, 1998), a decision maker interacts with an environment consisting of <strong>finite state and action spaces</strong>.</p>
  </blockquote>
  
  <p>This is an extract from <a href="http://carlosdiuk.github.io/papers/OORL.pdf" rel="nofollow noreferrer">this paper</a>, although it has nothing to do with the paper's content per se (just a small part of the introduction).</p>
  
  <p>Could someone please explain why it makes sense to study finite state and action spaces? </p>
  
  <p>In the real world, we might not be able to restrict ourselves to a finite number of states and actions! Thinking of humans as RL agents, this really doesn't make sense.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-28T13:10:44.133Z
Comments.Text: You are dealing with a _model_ -- the real world is too complex for many problems, but if you restrict the scope/domain, they become tractable.
Comments.UserDisplayName: Oliver Mason
Tags: <reinforcement-learning><markov-decision-process>
Title: Why does it make sense to study MDPs with finite state and action spaces?
UserDisplayName: stoic-santiago
ThreadText: # Why does it make sense to study MDPs with finite state and action spaces?
  
  (Asked by: username_0 on 2020-04-28)
  
  > In the standard Markov Decision Process (MDP) formalization of the reinforcement-learning (RL) problem (Sutton & Barto, 1998), a decision maker interacts with an environment consisting of **finite state and action spaces**.
  
  This is an extract from [this paper](http://carlosdiuk.github.io/papers/OORL.pdf), although it has nothing to do with the paper's content per se (just a small part of the introduction).
  
  Could someone please explain why it makes sense to study finite state and action spaces?
  
  In the real world, we might not be able to restrict ourselves to a finite number of states and actions! Thinking of humans as RL agents, this really doesn't make sense.
  
  **Tags:** reinforcement-learning, markov-decision-process
  
  > **Comments:**
  > **username_1**: You are dealing with a _model_ -- the real world is too complex for many problems, but if you restrict the scope/domain, they become tractable.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_2 on 2020-05-04. Score: 1 | Accepted answer
  
  In addition to the reason outlined in the comment, also note that if the state-space and action-space are both finite and of feasible size, tabular methods can be used, and there are some advantages to them (like the existence of convergence guarantees and generally a smaller number of hyperparameters to tune).
  
  
  ---
  
  ### Answer by username_3 on 2020-05-05. Score: 1
  
  **Note: I assume you mean, countable Action and State Sets by 'Finite'.**
  
  *MDP(s) are not exclusive to finite spaces only. They can be used in Continuous/uncountable sets of Action and States too.*
  
  *Markov Decision Process (MDP)* is a tuple $(\mathcal S, \mathcal A, \mathcal P^a\_s, \mathcal R^a\_{ss'}, \gamma, \mathcal S\_o)$ where $\mathcal S$ is a set of States, $\mathcal A$ is the set of actions, $\mathcal P\_{s}^a: \mathcal A \times \mathcal S \rightarrow [0, 1]$ is a function that denotes Probability distribution over the states if action $a$ is execuited at state $s$. [1][2]
  
  Where, Q-function is defined as:
  
  $$ Q^\pi (s,a) = \mathbb E\_\pi \left [ \sum \limits\_{t=0}^{+\infty} \gamma(t)r\_t | s\_o = s, a\_o = a \right] \tag{\*}$$
  
  *Note that $r\_t$ is just special case of Reward function $\mathcal R^a\_{ss'}$.*
  
  Now, if states and actions are discrete, then, the Q-Table Method[[3]](https://towardsdatascience.com/simple-reinforcement-learning-q-learning-fcddc4b6fe56) which is a state-action matrix helps us to evaluate $Q$ function and optimize efficiency.
  
  Whereas, in cases where the state/action sets are infinite or continuous, Deep Networks are preferred to Approximate $Q$ function. [[4]](https://www.geeksforgeeks.org/deep-q-learning/).
  
  **Q-Learning is Off-Policy method, doesn't require $\pi$ policy function**
  
  ---
  
  ## References:
  
  1. R. S. Sutton and A. G. Barto. *Reinforcement Learning: An Introduction*. MIT Press,
     1998.
  2. Alborz Geramifard, Thomas J. Walsh, Stefanie Tellex, Girish Chowdhary, Nicholas Roy and Jonathan P. How. *A Tutorial on Linear Function Approximators for Dynamic Programming and Reinforcement Learning*. Foundations and Trends (R) in Machine Learning
     Vol. 6, No. 4 (2013) 375–454
  3. Andre Violante. [*Simple Reinforcement Learning: Q-learning*](https://towardsdatascience.com/simple-reinforcement-learning-q-learning-fcddc4b6fe56), *Create a q-table*, <https://towardsdatascience.com>, 2019.
  4. Alind Gupta. [*Deep Q-Learning*](https://www.geeksforgeeks.org/deep-q-learning/), Deep Q-Learning, <https://www.geeksforgeeks.org/deep-q-learning/>, 2020.
  
  ---
  
  **Edit: I'd like to thank @nbro for editing suggestions.**
  
  
  ---
  
  ### Answer by username_4 on 2020-05-05. Score: 0
  
  To my knowledge you can't compute or solve an uncountably large MDP numerically. It will need to be discretized in some capacity. The same applies for classic control: you can't optimize over the true functional so you use a discrete approximation to the system and solve that.
  
  > **Comments:**
  > **username_4**: I should point out as a matter of practicality, everything is perhaps discrete in the limit. Think about an incredibly fine grained MDP to the point quantum effects start to dominate and the idea of "position" no longer exists.  
  
  ---
  
  