What is the definition of a continuous state/action space?

Question

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 by Csaba Szepesvari or Reinforcement Learning: Theory and Algorithms 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?' and 'Is an Uncountable Set and a Continuous Set the Same Thing?' reinforces my belief that it is not equivalent to the notion of uncountability.

Answer 1

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 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".

Answer 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 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 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.