Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers policies expressed as a reasoning Markov chain over actions in the current state that refines its choice of actions until arriving at a steady-state distribution over actions. In this framework the authors learn the number of steps to take before outputting an action and outline a policy gradient theorem that can be leveraged to differentiate through this process. The reason for learning this kind of policy seems to be in order to increase the expressiveness of distributions with multiple modes in the case of continuous action spaces. The authors present experiments demonstrating superior performance to baselines in 6 MuJoCo and 12 DMLab continuous control domains. 
strengths_and_weaknesses: Strengths: 
- The authors propose an adaptive iterative reasoning process with the goal of allowing for more complex multi-modal action space distributions for problems with continuous action spaces.
- The authors compare to a solid set of baselines across 6 mujoco domains and 12 DMLab domains while also providing nice qualitative experiments and relevant ablation experiments. 
- The approach is a bit outside the box from recent research with the fact that it works well striking me as somewhat surprising on the surface. 
- The derivation of Theorem 3.2 seems involved beyond the standard policy gradient derivation.

Weaknesses: 
- The authors only provide an intuitive rationale for their proposed strategy, on the surface it seems a bit weird to iteratively update actions in this way. I understand that it makes the distribution more expressive, but it is not clear to me why this direction is preferable to normalizing flows or some adaptive version of normalizing flows. 
- "Steady-state policy gradient" is a confusing term in light of the RL literature. I get what you mean upon reading, but it is confusing with the policy gradient for continuing environments which is defined over a different steady-state distribution (i.e. Sutton and Barto, 2018 Section 13.6). 
- It would be nice to provide readers with more information regarding how convergence to the steady-state distribution was determined for those not familiar with pseudo scale reduction factors. 
questions: - Can you compare what is achieved by your approach more directly to normalizing flows? The main advantage I understood from the related work section is allowing for a dynamic amount of computation. Am I missing something? Can there be an empirical comparison with normalizing flows? 
- What are the “mild assumptions” used in the proof of Lemma 3.1? Even looking through the proof in the appendix, it is not 100% clear to me what these assumptions are. Based on my experience with the Markov chain literature I was expecting something related to stochasticity of transitions or irreducibility and aperiodicity of the Markov chain etc. 
- Can you elaborate more about how information reuse is a benefit of this framework? It seems more like a necessity to make it practical? Is this meant in comparison with normalizing flows?  
limitations: It seems that the authors mostly highlight value in their work with respect to continuous action space domains. Could this approach also provide value in domains with discrete action spaces?
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper introduces a new serial markov chain reasoning for representing agent behavior. Instead of using a policy, the agent selects an action by maintaining an action-belief and a belief transition policy. The authors derive a steady state policy gradient algorithm for estimating the belief transition policy in a MaxEnt RL environment. In addition, this paper also provide a method to determine the number of reasoning steps dynamically. Finally, some empirical experiments are presented to verify the performance of the proposed method in real applications. 
strengths_and_weaknesses: Strengths: This method presented in this paper is novel. It has a potential to solve some RL problems in a more expressive way. The idea of learning the action belief instead of the policy makes sense to me. The proof of the theorems is rigorous and looks right to me. The experiments presented in this paper are sufficient and well-designed. The results look promising as the SSPG algorithm outperforms others with significant gains. 

Weakness: This paper is a bit hard to follow since some background knowledge is not clearly presented. Before you introduce how to apply the techniques, it is better to have a comprehensive description for them. 

questions: I have several questions. The authors state that the proposed reasoning Markov chain is more general compared to the traditional policy. And in the first section, you mentioned that the agent’s behavior can approximate any arbitrary distribution with simple parameterized transition functions.  I don’t fully get this point from the theoretical analysis. Is it true that a parameterized belief transition function can approximate any policy? Can you elaborate your statement a bit by referring to the theorems in the paper?
And since you are using the stationary distribution of a markov chain to define the action, you assumed that the markov chain is ergodic and every action is reachable in every state. I suggest the authors explain the assumptions first before presenting the method and theorems. 

limitations: Yes. The authors adequately addressed the limitations.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a novel framework for representing decision making in an RL problem as an iterative reasoning process based on serial Markov chains. The authors derive a policy gradient theorem for their framework in the standard RL setting, as well as the MaxEnt RL setting. The empirical evaluation shows improved performance in both state and pixel observations and demonstrates the expressivity of the proposed policy representation.

strengths_and_weaknesses: This is a solid paper with a clear and interesting idea, novel contribution, and a series of thoroughly conducted evaluations. I, however, have certain concerns regarding one of the key equations / definitions used by the authors which is the basis for all of the main derivations. 

## Strengths

### 1. Novelty
The proposed method for obtaining policy gradients using serial Markov chain reasoning is novel, to the best of my knowledge. Furthermore, I believe the contributions are significant and relevant as the proposed framework is a core development of RL algorithms and can be potentially impactful. 

### 2. Empirical Soundness
The empirical evaluation is thorough and sound. In particular, I appreciate using Rliable metrics and comparison against several strong baselines for both state and pixel observations. Finally, several ablation studies are conducted in Appendix E to shed more light onto the method and its hyperparameters.

### 3. Demonstration of useful properties of the proposed method
I greatly appreciate section 4.2 and correspondingly Appendix F. I have found the empirical results on policy expressiveness and adaptivity to be very convincing and a nice divergence from the standard comparison in the (deep) RL community that is usually concerned only with pure performance. Nevertheless, I do appreciate that the proposed method is outperforming SOTA algorithms.

## Weaknesses

### 1. Theoretical soundness
I have carefully checked the proofs of Lemma 3.1 and Theorem 3.2 and I acknowledge that the math is correct and sound (based on my understanding) **if** one agrees with the fact that $Q_n^s(s, a)$ is not a function of policy parameters $\theta$. However, I am not convinced this is the case. The concerning equation is equation (8) in which the authors define: 
$$
Q_n^s(s, a) = \int_A \pi_n^b(a’|a,s) Q_\phi^s(s, a’)da’,     \text{   with    } \nabla_\theta Q_n^s(s, a) = 0
$$
First, I am confused with the **"with"** statement; is that an assumption, condition, or a result of the definition of $Q_n^s(s, a)$? Second, in L416 of Appendix, the authors write “[since] $Q_n^s(s, a)$ is a local approximation of the RMC with no dependence from $\theta$...” and continue the proof without again stating why that is the case. 

My understanding is that the $\pi_\theta^b$ is paremetrized by $\theta$, hence $\pi_n^b$ is also a function of $\theta$ based on equation (4). In that case, I am interested to know why differentiating equation (8) does not yield the following result which is clearly non-zero: 

$$ \nabla_\theta Q_n^s(s, a) = \int_A \nabla_\theta \pi_n^b(a' | a, s) Q_\phi^s(s, a') da' +  \pi_n^b(a' | a, s) \nabla_\theta  Q_\phi^s(s, a') $$

Given that equation (8) is the key for all the consequent derivations, including the main theoretical result of the paper, I am concerned with the theoretical soundness of the paper. 

Note: With that said, I am hopeful that this is just a misunderstanding from my side and I am looking forward to hearing the authors’ response to elaborate and clear the confusion. Unfortunately for this reason, my rating is relatively low depite my acknowledgment of the strengths of the work. But I am eagerly looking forward to increasing it if the authors can explain the reasoning behind $\nabla_\theta Q_n^s(s, a) = 0$.

**Update after the rebuttal:** I acklowledge that I have been convinced by the argument of the authors and have increased my score from 6 (weak accept) to 7 (accept).

questions: My major question is regarding the point discussed in the weaknesses. I have noted it here for easier reference. The rest of the questions are mostly minor comments/suggestions. 

1. Can you clarify equation (8) and explain why $\nabla_\theta Q_n^s(s, a) = 0$. I am not convinced by the argument of the local approximation, as detailed above. 
2. I suggest the authors give titles to the theorems for better clarification and better guidance of the reader. An inexperienced reader may be lost within the heavy math.
3. The parameterization of the policy is sometimes written (denoted as $\pi_\theta^b$) and sometimes dropped (denoted as $\pi^b$ or $\pi^s$). This can confuse and mislead the reader. 
4. This is for my curiosity and I was not expecting to find this answer in the paper. Can recurrent neural networks be used to parameterize the RMC? I believe prior work has made the connection between RNNs and Markov chain reasoning.
5. Figure 1 is a very generic figure without giving much information about the method. I suggest the authors reconsider that and replace it with something more specific to their work. 
6. The colors and font size on Figure 2 makes the text hard to read.

limitations: Yes, the authors have addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes a family of implicitly defined stochastic policies that arise as the steady-state distribution of a Markov Chain whose transition function is a neural net which takes an action, a system state and a noise vector and produces a new action. The authors motivate this family of policies in three ways: a) they can approach any distribution over the action space b) the computation required to plan an action can vary depending on the state c) planning can be shortened by initializing the Markov chain with recently used actions, which can be seen as a form of solution re-use. The method improves over all considered baselines in typical benchmarks.
strengths_and_weaknesses: ### Strengths

* The idea reminds me of things like deep equilibrium models, but I believe the specific form here might have an advantage over those (stochasticity). I certainly haven't seen this type of model applied to RL, and I found it quite interesting.
* The paper has a good flow. Ideas, derivations and results are presented in a way that can be followed easily. Steps that would be complicated to parse at first reading are relegated to the appendix, which is good.
* The experimental results are both thorough and equivocally in favor of the model.
* The paper presents ablations that support the motivation for using a policy that refines itself over multiple steps (beyond that of improved performance). The experiments on simple positional bandits show that the model has an easier time accommodating multi-model distributions compared to normalizing flows, which would be the go-to model for something like this (aside from mixture density networks perhaps). Figure 4 b) and d) support the intuitions about multi-step reasoning. In OpenAI-Gym, Humanoid requires the most reasoning steps, while pendulum requires the least for instance. Re-using recent actions seems to bring an overall reduction in the number of reasoning steps, which is another thing that checks out.

### Weaknesses

* I believe the core weakness of the paper is the increase in computation. The authors analyze this point in terms of training time. I believe it should also be analyzed in terms of the cost of acting during deployment. How many times per second can we query such a policy? This remains somewhat unaddressed. I think it would also be interesting to compare SSPG to the other baselines in terms of the number of reasoning steps that are used (at the end of training, if we allow SSPG to be trained the usual way). At how many steps does SSPG outperform the others? There is a comparison of SSPG to itself in this fashion in the two hardest environments, but that doesn't exactly cover the same area.
* The increase in complexity over a standard policy is another weakness. SSPG adds some hyper-parameters and non-trivial implementation cost into the mix. There are also concerns about the assumptions that we have to make, such as the accuracy of the convergence criteria.

questions: ### Questions

* In eq. 13, the gradient term contains a product of gradients over the reasoning steps. Do the usual concerns about vanishing/exploding gradients apply here? Did you observe instability in practice?

* What is the real-time capability of these policies (in terms of deployment after training)?
limitations: These points are addressed well, aside from my comments above about computation time at deployment.
review_title: null

Meta-review: metareview: The paper makes a solid algorithmic contribution to RL that is extensively evaluated empirically and is a certain accept.
confidence: Certain
Decision: Accept