Answers.Body: <p>Generally speaking, we refer to a discrete state/action space, when it is finite (or countable like <span class="math-container">$\mathbb{Z}$</span>). The term continuous state/action space corresponds to closed intervals like <span class="math-container">$[-1,1]$</span> (or products of them). But it is true that the notion of &quot;continuous state space&quot; is not well-defined mathematically.</p>
  <p>The general requirements on the state or action spaces are relatively weak. In  particular, we require the state <span class="math-container">$\mathcal{S}$</span> and action <span class="math-container">$\mathcal{A}$</span> spaces to be Borel spaces. See e.g. in Puterman's Markov decision proccesses: Discrete stochastic dynamic programming book, Sec. 2.3.2</p>
  <p>It includes all finite sets for example. In this case, we talk about discrete control. There, everything works well and is the case mostly studied in Sutton-Barto. (For <span class="math-container">$\mathbb{Z}$</span>, it is more tricky already).</p>
  <p>The issue comes from the additional challenges caused by uncountable action spaces. The general objective of RL is to find a policy <span class="math-container">$\pi^*(a\mid s)$</span> that maximises the expected return. However, such policies do not exist in general. So, some additional conditions need to be put on the action space, as well as on the reward function, in order to guarantee the existence of such a policy.</p>
  <p>For some intuition of what could go wrong is that we want at least to be able to act (in theory) greedily with respect to some <span class="math-container">$Q$</span>-function, i.e. <span class="math-container">$\pi(a\mid s)=\text{argmax}_{a\in\mathcal{A}}Q(s,a)$</span>. However, we need some topological conditions to guarantee the existence of this maximum (or even supremum) on both the <span class="math-container">$Q$</span>-function (so that it is defined and finite) and the action space.</p>
  <p>One way is to put continuity assumptions on policies, that is we want that the actions <span class="math-container">$\pi(a\mid s)$</span> are selected continuously in function of <span class="math-container">$s$</span> (as is the case for example for a Gaussian policy parameterised by a neural network). This is where the term continuous control probably comes from. Similarly, we want the reward function to depend continuosly on <span class="math-container">$(s,a)$</span> and to be concave. Finally, we often put some topological assumptions on the action space: typically we want <span class="math-container">$\mathcal{A}$</span> to be a compact and convex subspace of <span class="math-container">$\mathbb{R}^n$</span>. (Note e.g. in Atari calculating the <span class="math-container">$\max$</span> is not a problem, so the assumptions on the reward function would not be necessary).</p>
  <p>In such a case, see e.g. Thm. 6.11.10 in Puterman, we can have the existence of an optimal continuous policy.</p>
  <p>Now, these conditions are not the most general and there are more general formulations, see the book of Bertsekas and Shreve, <a href="https://web.mit.edu/dimitrib/www/soc.html" rel="nofollow noreferrer">Stochastic Optimal Control</a> as an (advanced) mathematical book on such questions and the underlying measure theoretical issues. Of course, given how complex this is, it is understandable that people use simplified concepts, like &quot;continuous action space&quot;.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-23T09:12:37.150Z
Answers.Text: +1. A well-writen and comprehensive answer. The book by Bertsekas and Shreve looks awfully interesting. On a less serious note, it definitely looks like the kind of book I would have avoided at all cost when I was learning the ropes. ;)
Answers.UserDisplayName: Saptam
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-23T12:11:12.550Z
Answers.Text: Clearly. This book is only for mathematicians that want to do maths in the greatest generality :). That said other books of Bertsekas (e.g. Dynamic Programming and Optimal control) are more accessible, but still pretty rigourous (focusing on the finite state/action case well). Also the Puterman book is a common reference book (he is preparing a second edition of the book).
Answers.UserDisplayName: matorbi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-24T08:11:26.430Z
Answers.Text: Agree completely. In general, I like Bertsekas's style of presentation which follows the usual 'lemma followed by theorem and proof' style of a standard math book while not skipping on the necessary intuitions. His two-part book on convex optimisation (alongside the DP books) is a pretty good example of this.
Answers.UserDisplayName: Saptam
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-24T08:17:59.047Z
Answers.Text: "... (he is preparing a second edition of the book)." -- Really? I only have access to the 2005 copy. I have yet to go through some of the necessary parts, but I would love to learn the newer results.
Answers.UserDisplayName: Saptam
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-22T19:56:08.333Z
Answers.LastActivityDate: 2022-11-22T19:56:08.333Z
Answers.UserDisplayName: matorbi
Answers.Body: <p>Usually these authors are using these terminologies from the background of dynamical systems such as one of your referenced Markov Decision Process (MDP) which is all about input/state space/output and optimal control theory which is about action and feedback additionally. <a href="https://en.wikipedia.org/wiki/State_space" rel="nofollow noreferrer">State space</a> is a key concept of dynamical systems rooted from Hamiltonian mechanics in classical physics.</p>
  <blockquote>
  <p>A state space is the set of all possible configurations of a system.[1] It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory.</p>
  </blockquote>
  <blockquote>
  <p>For instance, the toy problem Vacuum World has a discrete finite state space in which there are a limited set of configurations that the vacuum and dirt can be in. A &quot;counter&quot; system, where states are the natural numbers starting at 1 and are incremented over time[2] has an infinite discrete state space. The angular position of an undamped pendulum[3] is a continuous (and therefore infinite) state space... All continuous state spaces can be described by a corresponding continuous function and are therefore infinite.[3]</p>
  </blockquote>
  <p>For example continuous state space is usually used in some kind of recurrent neural networks as the outputs of hidden layers such as <a href="https://en.wikipedia.org/wiki/Hopfield_network" rel="nofollow noreferrer">Hopfield network</a> and Hopfield first applied Lyapunov stability theorem and LaSalle's invariance theorem from state space analysis of dynamical systems to his network for certain new applications which were impossible before.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-24T08:36:27.743Z
Answers.Text: "State space is a key concept of dynamical systems rooted from Hamiltonian mechanics in classical physics." -- That's something new. Could you elaborate on the Hamiltonian mechanics part or provide some references?
Answers.UserDisplayName: Saptam
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-24T19:22:00.970Z
Answers.Text: Most physics (contemporary string theory included) and control theories are based on continuous state space hypothesis/ideas since it’s easier to do differentiation and integration, and Hamiltonian is basically the total energy of a dynamical system following Newtonian , Kirkoff, Schrödinger or any other natural laws, and state space in quantum mechanics is also necessarily complex number in addition to be continuum. State space acts as critical bridge to input external action on one hand, and link to output targets on the other hand usually in a linear fashion.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-22T05:34:38.720Z
Answers.LastActivityDate: 2022-11-22T05:34:38.720Z
Answers.UserDisplayName: cinch
Body: <p>This question is a result of a discussion with one of my more math-minded friends. When I accidentally mentioned the term continuous state space, he corrected me by saying that I am most probably talking about dense sets since continuity is usually associated with functions. This makes me wonder: what is it meant by a 'continuous' state space? We very often see this term thrown around in the Reinforcement Learning literature without defining properly. Can anybody provide me any references on what it precisely means? Even some of the more mathematically rigorous books like <a href="https://sites.ualberta.ca/%7Eszepesva/rlbook.html" rel="nofollow noreferrer">Algorithms for Reinforcement Learning</a> by Csaba Szepesvari or <a href="https://rltheorybook.github.io" rel="nofollow noreferrer">Reinforcement Learning: Theory and Algorithms</a> by AJKS don't delve into the definition of this term.</p>
  <p>A quick Google search tells me that there is no such thing as a 'continuous' set. Questions like '<a href="https://math.stackexchange.com/q/3362851">Is there such thing as a continuous set?</a>' and '<a href="https://math.stackexchange.com/q/3299369">Is an Uncountable Set and a Continuous Set the Same Thing?</a>' reinforces my belief that it is not equivalent to the notion of uncountability.</p>
  
Tags: <reinforcement-learning><terminology><definitions>
Title: What is the definition of a continuous state/action space?
UserDisplayName: Saptam
ThreadText: # What is the definition of a continuous state/action space?
  
  (Asked by: username_0 on 2022-11-21)
  
  This question is a result of a discussion with one of my more math-minded friends. When I accidentally mentioned the term continuous state space, he corrected me by saying that I am most probably talking about dense sets since continuity is usually associated with functions. This makes me wonder: what is it meant by a 'continuous' state space? We very often see this term thrown around in the Reinforcement Learning literature without defining properly. Can anybody provide me any references on what it precisely means? Even some of the more mathematically rigorous books like [Algorithms for Reinforcement Learning](https://sites.ualberta.ca/%7Eszepesva/rlbook.html) by Csaba Szepesvari or [Reinforcement Learning: Theory and Algorithms](https://rltheorybook.github.io) by AJKS don't delve into the definition of this term.
  
  A quick Google search tells me that there is no such thing as a 'continuous' set. Questions like '[Is there such thing as a continuous set?](https://math.stackexchange.com/q/3362851)' and '[Is an Uncountable Set and a Continuous Set the Same Thing?](https://math.stackexchange.com/q/3299369)' reinforces my belief that it is not equivalent to the notion of uncountability.
  
  **Tags:** reinforcement-learning, terminology, definitions
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2022-11-22. Score: 2 | Accepted answer
  
  Generally speaking, we refer to a discrete state/action space, when it is finite (or countable like $\mathbb{Z}$). The term continuous state/action space corresponds to closed intervals like $[-1,1]$ (or products of them). But it is true that the notion of "continuous state space" is not well-defined mathematically.
  
  The general requirements on the state or action spaces are relatively weak. In particular, we require the state $\mathcal{S}$ and action $\mathcal{A}$ spaces to be Borel spaces. See e.g. in Puterman's Markov decision proccesses: Discrete stochastic dynamic programming book, Sec. 2.3.2
  
  It includes all finite sets for example. In this case, we talk about discrete control. There, everything works well and is the case mostly studied in Sutton-Barto. (For $\mathbb{Z}$, it is more tricky already).
  
  The issue comes from the additional challenges caused by uncountable action spaces. The general objective of RL is to find a policy $\pi^\*(a\mid s)$ that maximises the expected return. However, such policies do not exist in general. So, some additional conditions need to be put on the action space, as well as on the reward function, in order to guarantee the existence of such a policy.
  
  For some intuition of what could go wrong is that we want at least to be able to act (in theory) greedily with respect to some $Q$-function, i.e. $\pi(a\mid s)=\text{argmax}\_{a\in\mathcal{A}}Q(s,a)$. However, we need some topological conditions to guarantee the existence of this maximum (or even supremum) on both the $Q$-function (so that it is defined and finite) and the action space.
  
  One way is to put continuity assumptions on policies, that is we want that the actions $\pi(a\mid s)$ are selected continuously in function of $s$ (as is the case for example for a Gaussian policy parameterised by a neural network). This is where the term continuous control probably comes from. Similarly, we want the reward function to depend continuosly on $(s,a)$ and to be concave. Finally, we often put some topological assumptions on the action space: typically we want $\mathcal{A}$ to be a compact and convex subspace of $\mathbb{R}^n$. (Note e.g. in Atari calculating the $\max$ is not a problem, so the assumptions on the reward function would not be necessary).
  
  In such a case, see e.g. Thm. 6.11.10 in Puterman, we can have the existence of an optimal continuous policy.
  
  Now, these conditions are not the most general and there are more general formulations, see the book of Bertsekas and Shreve, [Stochastic Optimal Control](https://web.mit.edu/dimitrib/www/soc.html) as an (advanced) mathematical book on such questions and the underlying measure theoretical issues. Of course, given how complex this is, it is understandable that people use simplified concepts, like "continuous action space".
  
  > **Comments:**
  > **username_0**: +1. A well-writen and comprehensive answer. The book by Bertsekas and Shreve looks awfully interesting. On a less serious note, it definitely looks like the kind of book I would have avoided at all cost when I was learning the ropes. ;)  
  > **username_1**: Clearly. This book is only for mathematicians that want to do maths in the greatest generality :). That said other books of Bertsekas (e.g. Dynamic Programming and Optimal control) are more accessible, but still pretty rigourous (focusing on the finite state/action case well). Also the Puterman book is a common reference book (he is preparing a second edition of the book).  
  > **username_0**: Agree completely. In general, I like Bertsekas's style of presentation which follows the usual 'lemma followed by theorem and proof' style of a standard math book while not skipping on the necessary intuitions. His two-part book on convex optimisation (alongside the DP books) is a pretty good example of this.  
  > **username_0**: "... (he is preparing a second edition of the book)." -- Really? I only have access to the 2005 copy. I have yet to go through some of the necessary parts, but I would love to learn the newer results.  
  
  ---
  
  ### Answer by username_2 on 2022-11-22. Score: 2
  
  Usually these authors are using these terminologies from the background of dynamical systems such as one of your referenced Markov Decision Process (MDP) which is all about input/state space/output and optimal control theory which is about action and feedback additionally. [State space](https://en.wikipedia.org/wiki/State_space) is a key concept of dynamical systems rooted from Hamiltonian mechanics in classical physics.
  
  > A state space is the set of all possible configurations of a system.[1] It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory.
  
  > For instance, the toy problem Vacuum World has a discrete finite state space in which there are a limited set of configurations that the vacuum and dirt can be in. A "counter" system, where states are the natural numbers starting at 1 and are incremented over time[2] has an infinite discrete state space. The angular position of an undamped pendulum[3] is a continuous (and therefore infinite) state space... All continuous state spaces can be described by a corresponding continuous function and are therefore infinite.[3]
  
  For example continuous state space is usually used in some kind of recurrent neural networks as the outputs of hidden layers such as [Hopfield network](https://en.wikipedia.org/wiki/Hopfield_network) and Hopfield first applied Lyapunov stability theorem and LaSalle's invariance theorem from state space analysis of dynamical systems to his network for certain new applications which were impossible before.
  
  > **Comments:**
  > **username_0**: "State space is a key concept of dynamical systems rooted from Hamiltonian mechanics in classical physics." -- That's something new. Could you elaborate on the Hamiltonian mechanics part or provide some references?  
  > **username_2**: Most physics (contemporary string theory included) and control theories are based on continuous state space hypothesis/ideas since it’s easier to do differentiation and integration, and Hamiltonian is basically the total energy of a dynamical system following Newtonian , Kirkoff, Schrödinger or any other natural laws, and state space in quantum mechanics is also necessarily complex number in addition to be continuum. State space acts as critical bridge to input external action on one hand, and link to output targets on the other hand usually in a linear fashion.  
  
  ---
  
  