Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper presents four symbolic reasoning domains that are inspired by the common core curriculum and a policy learning scheme that uses a distance metric as a value heuristic, for planning.
main_review: The motivation of this paper is to produce programs that can automatically solve some of the common common core curriculum problems in math. The domains are interesting, whereas the learning algorithm seems to produce a good performance. I enjoyed reading this paper quite a bit, but I do think the domains presented are on the easier side, and there are not enough baselines (like other methods), so I am going to recommend a weak reject. 

As a method paper, it is important to evaluate the method on established dataset/problem domains, and compare the method against other baselines. 

Pros of this paper are: the paper is largely well written. The domains are well motivated (not from the method perspective, because there are other domains from prior works, but well-motivated by the common core curriculum). 

Cons: The second paragraph in the introduction is distracting and does not help with the main message of this paper. Being a good tutor does not have much to do with having a good automatic solution engine, and this paper does not show that this engine helps with the human subjects during learning. Technically, it is important not to ignore domains that prior work has used and just dive into designing your own domains, then run just your own method. Nonetheless, these exciting results are a good starting point for something cool!
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a RL approach (ConPoLe) that minimizes the contrastive loss to tackle some elementary school level symbolic reasoning problems (CommonCore) like solving level simple math equations, fractions, and sorting, where the state is represented as a general string rather than as structured input (e.g. AST after parsing). The problem is difficult because the reward is sparse (only rewarded when successed). The main idea is to learn a parametric score function for next state proposals, through contrastive learning treating the one that led to the solution as positive and the rest ones as negative examples. The proposed method can achieve successful results on those four symbolic reasoning domains, outperforming all baselines.

main_review: This paper studies an interesting and novel problem and application of RL. I think being able to solve complex reasoning problems (such as automatic proof) is in general a very interesting and important area of study. As such, introducing four symbolic reasoning domains seems to be a good novelty of this work and I think this can be a valuable environment for the community. Empirical results are also promising.

However, I have some concerns about the paper. I would appreciate authors to address these questions and improve writing of the paper in general.

First of all, I am not sure this approach can be seen as an instance of reinforcement learning; this looks more like conventional AI or state search algorithm with a potential/score function learned through contrastive representation learning. There is not much MDP formalism (like reward, policy, or value function) being involved -- the policy or planner for solving a task at hand (i.e. test setting) is simply a beam search with trying all possible actions.

In terms of method/technical approach, search of solution space is done via beam search.
One limitation therefore is that it cannot learn from unsolved problems via beam search. This might be okay given that we are able to find some solution with an uninformed but reasonable beam search or IDA like search algorithm, but the method won’t scale up and work well on difficult reasoning tasks (e.g. automatic proof) where random or exhaustive MCTS is not enough.

Arguably, the environment is too simple. Compared to automatic proof and solving logic problems, the problem appears to be solvable with a reasonable heuristic or efficient state space search algorithm (such as A* or IDA).

The authors claim the state observation is given as an unstructured string. However, it seems that during the next state generation through possible action(mnemonic) some semantic structure is taken into account. In order to apply those actions and tell the operand (e.g. sub “3”, sub_comm “4”), either the agent or the environment itself should be aware of the structure of the equation. So claiming the environment is essentially “unstructured string” might sound like a bit of overclaiming.


Writing/Clarity:

- Qualitative examples or demo of the environment/task needs to be given in the main paper without need to look at the supplementary.
- Section 4 seems written verbose. It would be a much more clear organization if section 4 had several subsections (or paragraphs) describing each component constituting the overall algorithm.
- Algorithm 1: the authors should avoid using weird italic fonts in LaTeX math environments -- roman fonts preferred.
- In Algorithm 1, $\theta_\pi$ is the only learnable parameter, but this is mentioned nowhere in the main text. In the score function formulation (L173-180), we have $\theta$ --- are they essentially the same thing? Also, it’s not clear how exactly $f_\theta$ is being incorporated into the policy. It is also not very clear what is the exact policy setup for exploitation (i.e. how to solve the given task during test after training is done); do we still use beam search?
- Figure 2 seems to be placed in a random place. It would be good to place them in the top area.


----------

POST-REBUTTAL UPDATE: I have updated my rating from 5 to 6. Please see my comments below in reply to the author feedback.
limitations_and_societal_impact: Limitation of the work is discussed. There is no concerns or issues, at least to my understanding, about negative social impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a new reinforcement learning method for symbolic domains with sparse binary rewards (e.g., finding step-by-step solutions to math problems). The method assumes the availability of many problem instances within the domain, of varying levels of difficulty; the agent learns by solving the easier problems first, and training to distinguish positive and negative examples of state transitions on the way to a solution, using a version of the InfoNCE loss from the contrastive learning literature. ConPoLe operates directly on text representations of states within a domain, so adapting it to new domains does not require domain-specific hand-engineered features. The paper presents four novel domains corresponding to different kinds of math problem, inspired by the Common Core curriculum, and shows that ConPoLe outperforms existing methods by a wide margin. In addition, a small-scale experiment suggests that the embeddings that ConPoLe learns cluster according to existing pedagogical classifications of math problems on Kahn Academy. ConPoLe is also tested in an established Rubik's cube domain, comparing favorably to the DeepCubeA baseline in terms of data efficiency and search time (if not final solution length). 
main_review: ConPoLe is an appealingly simple idea. It exploits the unique features of the sorts of symbolic domains considered here (unlimited problem examples, of varying levels of difficulty), and avoids relying on meaningful intermediate rewards or hand-engineered features, which would be cumbersome to develop. The experiments are compelling and even if ConPoLe does not end up scaling to domains like program synthesis and automated theorem proving, I buy that there are already important application areas (like interactive tutoring systems) in which ConPoLe could be really useful.

I have two suggestions for improving the clarity of the paper, and two questions that would be great to see addressed in the paper (or perhaps as part of follow-on work). First, the suggestions:

1. Although "beam search" is a standard algorithm, there are different ways of instantiating it; I had trouble figuring out how exactly yours worked. Suppose at step $i$ there are $N$ trajectories $(s^j_1, \dots, s^j_i)$ (for $j = 1, \dots, N$) in the beam. Presumably, the beam is extended by considering all valid extensions-by-one-state of the current trajectories—for each trajectory in the beam, for each action, we can run the action to determine an extended trajectory. But how are these extended trajectories scored, to then cull all but the top $N$? I thought the score might be the probability, under the current policy, of the entire sequence (where the policy is to select a next state s' proportionally to f(s^j_i, s'), across the *valid* next state). But I wasn't sure, and spelling this out would be a great help. (Hopefully I haven't gravely misunderstood!) 

It was also unclear to me exactly how the negative examples were chosen. When beam search concludes, we have $N$ trajectories of length, say, $k$ in the beam, with one of them ending in success. For each state $s_i$ along the successful trajectory, which negative examples are added? The pseudocode makes it seem like only the $(i+1)$th state of each trajectory (excluding the successful one) is included as a negative example. But why? These $(i+1)$th states are parts of trajectories that don't necessarily include the successful trajectory's $s_i$; what makes them more appropriate as negative examples than any of the other states in the replay buffer? 

2. I wasn't sure what to make of the "mutual information" intuition in L189-196. The claim seems to be that the loss is a bound on the mutual information between successive states in successful trajectories. Does this argument depend at all on the distribution from which the negative examples are generated? A cursory skim of [22]'s notation makes it look as though they should be generated from a marginal distribution, e.g. the marginal distribution over states found along successful trajectories for problems sampled from your "problem generator." Does generating negatives via beam search actually sample from this distribution? L195 seems to suggest that your Section 5 observation that using more negatives improves learning is connected to the tightness of the InfoNCE bound on mutual information, but I wasn't sure why. What is the connection between a tighter bound on mutual information, and learning quality? My current impression is that the paper would be fine without this paragraph, but if it is included, it would be great if you could unpack the intuition a bit more.

My two general questions:

1. It's very nice that ConPoLe doesn't require hand-engineered feature representations. But I am curious about the extent to which it relies on correlational information present in the textual representations of states. Do you think the particular state representations you use meaningfully affect performance? Do you think pretraining / sharing the embeddings across different domains could help?

2. How important is it to get the data-generating distribution right during training? I can imagine a few ways a task might be 'out-of-distribution' -- e.g., if it requires a longer sequence of steps than the tasks seen during training, or is simply a longer string (more arithmetic operations in the equation, e.g.). When would ConPoLe succeed and fail at generalizing? Have you tested its ability to generalize in this way (or other ways)?
limitations_and_societal_impact: Yes, I think limitations and societal impact are adequately addressed.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: In this paper, the authors address the problem of learning policies on symbolic domains - like mathematical equations. They propose ConPoLe - learning algorithm that relies on optimizing InfoNCE, a well-known contrastive loss. They benchmark ConPoLe on four different environments and show that it generalizes well. A key contribution of the paper is the introduction of these environments themselves.
main_review: The primary premise of this paper is to learn effective policies on symbolic domains. To that end, the authors first create four different environments drawn from the Mathematics curriculum of the US Common Core State Standards. Their solution approach is motivated by the observation that learning value estimates is not difficult when rewards are sparse. They focus specifically on symbolic domains that are characterized by a single reward state - e.g., Rubik's cube. Their approach relies on minimizing the InfoNCE loss and avoids value estimation completely. This differentiates their approach from other works in this area - notably DeepCube.

Strengths:
1. The four new environments introduced in this paper are valuable to the RL community. Since they are drawn from a typical mathematics curriculum, solutions in this space might be expected to improve educational tools

2. Formulating this problem in terms of a contrastive learning problem is somewhat novel - and effectively sidesteps the need to calculate noisy value function estimates when the rewards are sparse as in these environments.

Weaknesses:
1. The paper relies quite a bit on datasets and reinforcement learning baselines that the authors develop. As such, it is difficult to ascertain the effectiveness of their approach over modern learning methods. For example, for the CommonCore environments, 3 out of the 4 methods evaluated are variations of ConPoLe - with DRRL, a relatively old method, being the only baseline.

A comparison between ConPoLe and Autodidactic Iteration - the approach used in DeepCube - on all the environments would have made the paper much stronger.  

2. The more interesting learning problem - from the point of view of scale - is the comparison with DeepCube. The paper doesn't provide any insight into whether ConPoLe is actually competitive. The only datapoint provided is that ConPoLe takes a significantly higher number of average-number-of-moves compared to DeepCube while also visiting less than half the number of nodes. This single datapoint is hardly adequate to lend credibility to their claim that "this result validates the generality and promise of ConPoLe for solving challenging symbolic domains".

Post-rebuttal comments: Thanks to the authors for reporting on the additional experiments. Based on the response, I have increased my score to 5. The comparison between ConPole and ADI makes this paper stronger. However, I still have concerns on the general applicability of ConPole to larger scale problems compared to the datasets the authors introduce. I think this is a good paper in the making if the authors are able to compare ADI and ConPole on a more complex problem like Rubik's cube. 
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: I've read through the reviews and responses as well as the paper. It seems like the reviewers found the paper very interesting: the problem domain is compelling and under-explored, and the motivation of the model is clear. In other words, the reviewers generally felt the paper was well-positioned to bring value to the field of abstract reasoning and planning, and the authors did a decent job at demonstrating this through benchmarks introduced here as well as showing some reasonable baselines fall short. 

However, there were some concerns, and I was borderline as far as whether these concerns are addressable through a minor revision in the final draft. It seems like a lot of the issues are on the stated limitations of the work: the authors acknowledge in the discussion some of these limitations are properties of the domain they are working in. 

After looking carefully at the discussion and the paper, I believe the paper still has value, despite these limitations. We shouldn't detract good research in difficult domains, and the fact that there's more to say about this domain shouldn't make it weaker than a paper that purports to study reasoning in a black-box environment like Atari. However, I strongly assert that the authors make very clear the limitations of their benchmarks and conclusions draft from running models on these benchmarks in the final draft. I cannot conditionally accept the paper, so I am going to trust the authors on this.
Decision: Accept (Poster)