A major impediment in applying RL theory to any realistic scenario is that even the control problem^[1] is intractable when the state space is exponentially large (in general). Real-life agents probably overcome this problem by exploiting some special properties of real-life environments. Here are two strong candidates for such properties:

• In real life, processes can often be modeled as made of independent co-existing parts. For example, if I need to decide on my exercise routine for the next month and also on my research goals for the next month, the two can be optimized more or less independently.
• In real life, planning can often be decomposed across timescales, s.t. you don't need to make short timescale plans for steps that only happen later on the long timescale. For example, if I'm in the process of planning a trip to Paris, I might need to worry about (i) booking hotel and tickets (long timescale), (ii) navigating the website I'm using to find a flight (medium timescale) and (iii) moving my finger towards the correct key for entering some specific text into a field (short timescale). But I don't need to worry about walking down the escalator in the airport at this moment.

Here's an attempt to formalize these properties.

We will define a certain formal language for describing environments. These environments are going to be certain asymptotic regions in the space of MDPs.

• Each term $t$ has a type which consists of a tuple of inputs $(x_1,x_2\dots x_n)$ and a single output $y$. Each input $x_i$ is a associated with an HV-polytope^[2] $P\left(x_i\right)$. The output is associated with an H-polytope^[3] $Q\left(y\right)$. The inputs represent action spaces (to get a discrete action set, we use the simplex of probability distributions on this set). The output represents the space of admissible equilibria.
• The atomic terms are finite communicating^[4] MDPs, in which each state $s\in S$ is associated with a particular input ${\iota }_s$ and a transition kernel $T_s:P\left({\iota }_s\right)\to \Delta S$ which has to be an affine mapping. For an atomic term, $Q\left(y\right)$ is the polytope of stationary state-action distributions. Notice that it's efficiently computable.
• Given two terms $t_1:(x_1\dots x_n)\to y$ and $t^{\prime }:(x_1^{\prime }\dots x_m^{\prime })\to y^{\prime }$, we can construct a new term $t_1\times t_2:(x_1\dots x_n,x_1^{\prime }\dots x_m^{\prime })\to y\times y^{\prime }$. We set $Q(y\times y^{\prime }):=Q\left(y\right)\times Q\left(y^{\prime }\right)$. This represents a process made of two independent parts.
• Given a term $t:(x_1\dots x_n)\to y$, $n$ terms $\{u_k:(x_{k1}^{\prime }\dots x_{k{m}_k}^{\prime })\to y_k^{\prime }{\}}_{1\le k\le n}$ and surjective affine mappings $\{f_k:Q(y_k^{\prime })\to P(x_k\left)\right\}$, we can construct a new term $t^f\left[u\right]:\left(x_{ij}^{\prime }\right)\to y$. This represents an environment governed by $t$ on long timescales and by $u$ on short timescales. Notice that it's possible to efficiently verify that $f$ is a surjection, which is why we use HV-polytopes for inputs^[5].

It might be useful to think of $t_1\times t_2$ as vertical composition and $t^f\left[u\right]$ as horizontal composition, in the category-theoretic sense.

In order to assign semantics to this language, we need to define the environment associated with each term $t:(x_1\dots x_n)\to y$. We will do so by assigning $t$ a state space $S\left(t\right)$, each state $s\in S\left(t\right)$ an input $\iota \left(s\right)$ (which determines the action space at this state) and a transition kernel. This is done recursively:

For the atomic terms, it is straightforward.

For $t_1\times t_2$:

• $S(t_1\times t_2):=S\left(t_1\right)\times S\left(t_2\right)\times \{1,2\}$. Here, the last factor represents which subenvironment is active. This is needed because we want the two subenvironments to be asynchronous, i.e. their time dynamics don't have to be in lockstep.
• $\iota (s_1,s_2,i):=\iota \left(s_i\right)$
• The transition kernel at $(s_1,s_2,i)$ is defined by updating $s_i$ according to the transition kernel of $t_i$ and then changing $i$ according to some arbitrary probabilistic rule, as long as this rule switches the active subenvironment sufficiently often. The degrees of freedom here are one reason we get an asymptotic region in MDP-space rather than a specific MDP.

For $t^f\left[u\right]$:

• $S\left(t^f\right[u\left]\right):={\bigcup }_{s\in S\left(t\right)}S\left(u_{\iota \left(s\right)}\right)$, where we abuse notation to identify the input $\iota \left(s\right)$ with its index inside the tuple.
• $\iota$ is extended from $u$ in the obvious way.
• Given $s\in S\left(t\right)$ and $s^{\prime }\in S\left(u_{\iota \left(s\right)}\right)$, the $t^f\left[u\right]$-transition kernel at $s^{\prime }$ is defined by (i) with high probability, $s^{\prime }$ is updated according to the transition kernel of $u_{\iota \left(s\right)}$ (ii) with low probability, $s$ is updated according to the transition kernel of $t$, where the action is determined by the frequency of state-action pairs since the last type II transition: it is easy to see that $Q\left(y\right)$ is always a polytope in an appropriately defined space of state-action distributions.

The upshot is that, given a list of term definitions (which has a structure similar to a directed acyclic graph, since the definition of each term can refer to previously defined terms), we get an environment that can have an exponentially large number of states, but the control problem can be solved in time polynomial in the size of this description, given some assumptions about the reward function. Specifically, we "decorate" our terms with reward functions in the following way:

• For atomic terms, we just specify the reward function in the straightforward way.
• For $t_1\times t_2$, we specify some $c_1,c_2\ge 0$. The reward is then a linear combination of the individual rewards with these coefficients (and doesn't depend on which subenvironment is active).
• For a term of the form $t^f\left[u\right]$, we need that $r_k^{\prime }\left(p\right)={max}_{q\in f_k^{-1}\left(p\right)}{r}_{u_k}\left(q\right)$ for some affine $r_k^{\prime }:P\left(x_k\right)\to R$ which is part of the decoration. This can be validated efficiently (here it's important again that the input is an HV-polytope). In addition, we specify some $c,c^{\prime }\ge 0$ and the reward a linear combination with these coefficients of the $t$-reward and the $u$-reward.

For timescale decomposition, this planning algorithm can be regarded as formalization of instrumental goals.

An important problem is, understanding the sample complexity of learning hypothesis classes made of such environments. First in the unbounded case and then with polynomial-time learning algorithms.