Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the manifold of effective (or reachable) states in MDP with continous states and continuous actions. Based on the continuous-time modeling, the authors present their main theorical contribution, i.e., the theory that proves the set of effective states is a smooth manifold of dimensionality at most the dimensionality of action space plus 1. Then, the authors provide empirical validation from two aspects: 1) the empirical estimation of the effective state manifold, and 2) the performance evaluation of a DDPG variant equipped a low-dimensional manifold representation by learning from the knn-graph estimated geodesic distance.
strength_and_weaknesses: $\textbf{Strengths:}$
+ I appreciate the authors’ efforts in study the manifold of effective states in MDP. Personally, I am interested in it and I think it is fundamental to efficient RL in complex problems.
+ The writing and presentation of the proposed method is almost clear. The organization of this paper is good.
+ The theoretical results and the empirical validation match well to some extent.

&nbsp;

$\textbf{Weaknesses (and Questions): }$

The main theoretical contribution is Theorem 3.2. By referring to Appendix B, I am confused on the proof of Proposition B.2. Concretely, since $\phi_{s^{\prime}}: A \times (\epsilon - \eta, \epsilon + \eta) \rightarrow U \in S_{e}$, the inverse $\phi_{s^{\prime}}^{-1}$ should be a mapping from state to action and time interval, right? This turns to be confusing when the authors derive the equivalence between $h$ and $\phi_{s^{\prime}}^{-1}$. Do I misunderstand some part?



&nbsp;


My other concerns are on the empirical validation.



For the empirical dimensionality estimation, I feel a gap between theory and practice, i.e., the policies (DDPG policies) used to sample state data are poor in performance in MuJoCo and thus should only cover a very small part of all possible smooth policies.

Therefore,  I question the validity and generality of the results of estimated manifold dimensionality.

In addition, what is the exact number of the size $n$ of the sampled states used to estimate the dimensionality in Section 5.1? I am also curious about how different numbers of $n$ affect the dimensionality estimated.

&nbsp;

Similarly, personally, I am not satisfied with the results in Section 5.2, because I am very familiar with the performance of different representative DRL algorithms in MuJoCo and I do not think DDPG is a good baseline algorithm in MuJoCo.

I recommend the authors to conduct the expriments based on TD3 or SAC which will be much more convincing, at least to me.

For the comparison in Figure 5, do the authors have the results of a baseline that keeps the $d_a + 1$ bottleneck structure while not uses $L_{\phi}$ (i.e., train as the original DDPG). I think this baseline will help a lot in understanding the efficacy of $L_{\phi}$.

&nbsp;


For some additional discussion, I wonder the authors’ opinion on how this work, i.e., the manifold of effective state space, relates or differs to recent works on studying low-rank state (representation) space in DRL, e.g., [1,2].

&nbsp;


Reference:

[1] Yuzhe Yang, Guo Zhang, Zhi Xu, Dina Katabi. Harnessing Structures for Value-Based Planning and Reinforcement Learning. ICLR 2020

[2] Aviral Kumar, Rishabh Agarwal, Dibya Ghosh, Sergey Levine. Implicit Under-Parameterization Inhibits Data-Efficient Deep Reinforcement Learning. ICLR 2021

&nbsp;

Minors:
- The reference in the second paragraph in Section 5.2 is broken.
- The figures are in low fidelity. The font size of the texts in the figures are too small to read.


clarity,_quality,_novelty_and_reproducibility: $\textbf{Clarity: }$

The writing and presentation of the proposed method is almost clear. The organization of this paper is good.

&nbsp;

$\textbf{Novelty: }$

To my knowledge, the theoretical and expirical results on state manifold in RL is novel.

&nbsp;

$\textbf{Quality: }$

The theoretical part is almost clear yet I also have questions for the authors. The empirical validation is interesting while is insufficient in several aspects as I point out in the part of Strengths and Weaknesses.

&nbsp;


$\textbf{Reproductibility:}$

The proposed algorithm is clear and it seems to be easy to implement. The source codes are also provided.

summary_of_the_review: According to my detailed review above, I think this paper is below the acceptance threshold mainly due to my concerns on the theory and the empirical results (see concrete content above).

I am willing to raise my rating if my concerns are well addressed.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper shows that, under certain conditions, the set of reachable states is a smooth manifold with dimension at most the dimension of the action plus one. The paper then proposes a DNN architecture with a bottleneck and show its competitive performance in numerical experiments.
strength_and_weaknesses: Strength
- The paper provides an interesting analysis on the geometry of the state space. For a deterministic environment satisfying the three conditions stated in the paper, the effective/reachable state space is shown to be a low-dimension manifold whose dimension is determined by the dimension of the action space.

- The upper bound on the effective dimension is shown to be close to the empirical estimate, and this effective dimension could potentially help the architecture design of value and policy networks in RL algorithms.

Weaknesses
- The analysis only works for deterministic environments. In fact, with noise in the transition dynamics, the dimension of the effective state space will be the entire state space for a general problem. There is a paragraph briefly discussing the possible extension to stochastic environments with additive Gaussian noise, but no actually analysis for the stochastic case.

- The three assumptions seem pretty restrictive. They are essential for the proof as discussed in Appendix A, but they basically restrict the model to be rather simple and not likely to hold in interesting problems like those MuJoCo environments. Does any of the MuJoCo environment (no randomness) satisfy these assumptions?

- In numerical experiments, only one architecture with a bottleneck of $d_a + 1$ is considered. If the goal is to show that $d_a + 1$ is the effective dimension and is sufficient for state representation in a RL algorithm, one may need to try multiple architectures with different bottleneck dimensions and compare their performance.
clarity,_quality,_novelty_and_reproducibility: The paper is easy to follow in general. 
summary_of_the_review: The analysis on the geometry of effective state space is interesting, but the theoretical results only works for a very limited class of problems. Numerical experiments may be a bit limited for validating the low-dimensional effective state space property.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a theoretical analysis to understand the intrinsic dimension for deterministic continuous-time State and action space problems. This method is motivated by understanding the representations required to train optimal policies in these types of spaces will help us better understand the structure of networks that can be used to solve these types of tasks. The method performs some theoretical analysis to indicate that a diffiomorphism can be found between the continuous time optimization problems such that the intrinsic space is only the size of the action space + 1. Two different experiments are shown to try and empirically justify the results that analyze the reproducibility of the theoretical results in some of the mujocu simulated robotic control environments.
strength_and_weaknesses: pros
- The first pro for this method is that it does appear to have a rather helpful proof in showing how the dimensions for a control problem are also heavily connected to the action space for the problem.
- The analysis also includes two different types of empirical experiments to better understand how close do the theoretical analysis is to a practical comparison.

cons
- The analysis, including the theory in the paper, is limited to a very small subset of possible planning problems. While the analysis may be correct, the fact that it only works on continuous state and action problems that are deterministic might say more about the limited applicability of the intrinsic dimensionality findings.
- This is also reflected in some of the experiments that analysis or it would be helpful to include analysis where the state space is image-based rather than the already dense information from the robot poses.
clarity,_quality,_novelty_and_reproducibility: 
- The proposed analysis in the paper focuses on mujoco environments that are deterministic and in the continuous state in action space. What are the connections between the methods described in this work and discreet action spaces such as the Atari environments? Does the analysis in the paper help us determine the intrinsic state space in image-based worlds or worlds with discrete actions?
- One of the cons of this method is that it could be an indicator that the assumptions that the method is continuous and deterministic also imply that this method only works in very simple environments. This could speak more to the non-realistic assumptions which this type of method can be applied. In this type of environment, it could be possible to train a policy where the state space only consists of the time $t$. If the proposed analysis can be generalized to complex and more general environments, it'll be more helpful to the community.
- Also, the assumption of no orbits in theory, which can also be interpreted as the probabilistic graph for the policy must be directed and not have cycles, is also a very strong assumption and that the agent will never revisit a state that visited at a prior time.
- In the empirical analysis section of 3.2, how is a low dimensional mapping learned from the state space to the action space plus one? The details around how this learning and compression algorithm is designed are important to understanding the application of the method for this experiment. 
- In order to train the coordinate chart, is supervised information needed that dictates exactly what the distance between two states should be in the state space? It is not clear where the supervised information comes from next on the left side of equation 3.
- How many random scenes were used for figure 5? It is not clear what implications can be made from figure 5. Is this a proof of concept? 
summary_of_the_review: The work forms a theoretical analysis to indicate the intrinsic dimension of a continuous time control system. The motivation and scope of the contribution need more details before the score can be raised.

---- Updated score
After more clarity on the method and a few updates to the framework.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Reinforcement learning has led to empirical success in complex tasks with continuous state-action spaces in the contexts of game-based and robotics simulations.  Theoretically current tools seem to suggest poor performance - due to the "exponential" scale of the state space representation, even when using strong function approximators like a neural network which is used in practice.  To some extent - these empirical successes have been justified due to the so-called "manifold hypothesis" - that most high-dimensional real-world datasets actually lie on low-dimensional manifolds.  For example, the set of all possible pixel representations of an image is clearly much later than the set of "feasible" images.  Representing the "feasible" region is a low-dimensional manifold, and highlighting that the theoretical guarantees should scale with respect to this manifold instead of the latent space, could be seen as some justification for the results along this lens.  At a high level, this paper essentially proves the manifold hypothesis - stating that the "feasible" state space (i.e. set of states reachable by a smooth policy) has dimension at most the dimension of the action space plus one.  This is applicable for robotics tasks where the state space is the space of all possible images (e.g. 128 x 128 pixels) whereas the actions is a simple 4 dimensional manifold for controlling torque of the four joints.

To be more concrete, the authors consider a continuous-time reinforcement learning with deterministic transitions.  The MDP is represented as $(S, A, f, f_r, s_0, \lambda)$ where $S$ and $A$ are $d_S$ and $d_A$ dimensional subspaces, $f$ is the transition function, $f_r$ the reward function, and $\lambda$ the exponential time-discount factor.  The agent is tasked with learning a policy $\pi$ which is a smooth mapping from states to actions with the goal of maximizing their discounted return, now an integral over time of $f_r(s_t)$ with respect to $t$ where $s_t$ evolves along a curve dictated by the smooth policy.  

Under this notation - the authors then define $S_e = \cup_{\pi \in \Pi} ( s | s = H_{\pi}(t) \text{ for some } t )$ as the set of effective states, where $H_\pi$ is the continuous time trajectory or curve of policy $\pi$ in the state space.  Intuitively, this set can be thought of as the set of "reachable" states in this continuous time MDP model.  Note that any state $s$ which is reachable by "some" policy $\pi$ in the policy class $\Pi$ then belongs in $S_e$.  With this, the main result is the following:

**Theorem 3.2** $S_e$ is a smooth manifold of dimension at most $d_a + 1$.

The authors then complement this theoretical discussion with empirical results.  They compare DDPG on four MuJoCo tasks with two network architectures.  The first is a standard one, first discussed in the DDPG paper. The second is a novel architecture which has a bottleneck output of $d_a + 1$ neurons (for learning the manifold) and the rest is a standard layer as in the original architecture. They introduce a modified loss (to ensure that the output serves as a manifold).  The empirical results show similar performance on the original DDPG algorithm and the one with the modified network architecture.

## Questions
- Do prior works which consider manifold learning on top of developing an RL algorithm essentially just tune the resulting manifold dimension?
- Discussion on top of page 6 is confusing - state that you can find such a $v$ but then state that the existence is beyond the scope?

## Minor Comments
- Last sentence of introduction is unclear and could be rewritten and clarified.
- "This solution" on top of page 3 - solution to what?
- Superscript of $\pi$ missing in $s_l$ in Equation 3
- First paragraph of section 2.2 is a bit unclear
- "start" instead of "starting" in first paragraph of section 3
- Restate definition of $H_\pi$ in Definition 3.1
- Theorem ?? on page 7
- Plots are hard to read in grey-scale


strength_and_weaknesses: ## Strengths
1. Model + Theoretical Results: The theoretical results presented in section 3 is novel to the reinforcement learning community.  In fact, this low-dimensional manifold assumption has been made in several prior works - and so this paper can be seen as a proof for the assumptions of those results (although the paper could have explicitly included what those are).
2. Quality of Results: The theoretical results presented in section 3 help highlight the fact that the effective size of solving an MDP problem can be related to the dimension of the action space.  The neural network architecture is novel - combining manifold learning alongside the typical DDPG losses.
3. Relation to Existing Literature: The authors do a good job relating the current analysis to the current literature on manifold learning (highlighting that it has been tested empirically in the past), and neural network architecture design for reinforcement learning.

## Weaknesses
1. Empirical Results: The empirical results show that the performance of the two network architectures (original one + one which uses manifold learning) are statistically similar (due to overlapping confidence intervals).  Potentially there are more extensive empirical results in prior work that could be cited as well for further justification.
2. Theoretical Benefits: The authors should include more theoretical justification of what Theorem 3.2 allows for current RL convergence results.  For example, taking typical function approximation algorithms in the theoretical reinforcement learning community - does knowledge of reduced dimension of $S_e$ versus the state space allow for reduced regret guarantees?  In isolation, the writing and results seem to suggest this fact but the connection is not formally made.
clarity,_quality,_novelty_and_reproducibility: ## Quality + Originality

As stated earlier - the authors present a theoretical contribution for a dimensionality reduction of the effective state space dimension - an assumption that is typically made in prior work.  The empirical results are not convincing, and potential the authors can include a more nuanced discussion on their performance (potentially manifold learning allows for fewer parameters as well, resulting in computational improvements as well).

## Clarity

The submission is well-written and easy to follow. The added discussion and backgrounds on manifolds is appreciated - especially for those like myself who aren't directly inside of this field.  Couple comments for improvements:
- Some of the discussion in the beginning of sections 2.1 and 3 felt repetitive and could be clarified more
- The reduction from the discrete time to the continuous time example was a bit unclear and could be described in more detail in the revision
- More discussion on prior work - what assumptions were made on dimension of the state space, etc

summary_of_the_review: The authors include strong theoretical contributions on state-space reduction.  However, the empirical results are not convincing, and there are not any concrete theoretical justification on the benefits of their main result (Theorem 3.2).
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper presents a theoretically motivated analysis to understand the intrinsic/ underlying dimension of MDPs. The reviewers acknowledge the value in the proof along with the experimental analysis. However, there were significant concerns on the lack of discussion, the limited dimensionality of problems (state-based vs image-based) and limited applicability to deterministic systems. From an experimental standpoint, 6 seeds are too few hence does not substantiate the statistical claims in the paper. The variation in shaded regions in plots are large, which indicate the method completely fails in some runs.

As this paper was quite borderline, we had several discussions with the reviewers, ACs and SACs. Ultimately, the concerns empirical concerns raised by the reviewers were quite substantial and hence we lean on the side of rejection. Nevertheless, I encourage the authors to integrate the additional discussion and experimental suggestions made by the reviewers for a future submission.
justification_for_why_not_higher_score: Paper is limited to deterministic MDPs, and there is a lack of experiments on truly high-dimensional MDPs like image-based observations.
Decision: Reject