Contrastive Reinforcement Learning of Symbolic Reasoning Domains
Authors: Gabriel Poesia
WenXin Dong
Noah Goodman
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
education
contrastive learning
symbolic reasoning

Abstract: Abstract symbolic reasoning, as required in domains such as mathematics and logic, is a key component of human intelligence. Solvers for these domains have important applications, especially to computer-assisted education. But learning to solve symbolic problems is challenging for machine learning algorithms. Existing models either learn from human solutions or use hand-engineered features, making them expensive to apply in new domains. In this paper, we instead consider symbolic domains as simple environments where states and actions are given as unstructured text, and binary rewards indicate whether a problem is solved. This flexible setup makes it easy to specify new domains, but search and planning become challenging. We introduce five environments inspired by the Mathematics Common Core Curriculum, and observe that existing Reinforcement Learning baselines perform poorly. We then present a novel learning algorithm, Contrastive Policy Learning (ConPoLe) that explicitly optimizes the InfoNCE loss, which lower bounds the mutual information between the current state and next states that continue on a path to the solution. ConPoLe successfully solves all four domains. Moreover, problem representations learned by ConPoLe enable accurate prediction of the categories of problems in a real mathematics curriculum. Our results suggest new directions for reinforcement learning in symbolic domains, as well as applications to mathematics education.

Contrastive Reinforcement Learning of Symbolic Reasoning Domains
Gabriel Poesia Stanford University poesiaucs stanford.
WenXin Dong Stanford University wxd@stanf ord. edu
Noah Goodman Stanford University ngoodman@stan ord. edu
Abstract
Abstract symbolic reasoning, required in domains such mathematics and logic, is a key component human intelligence. Solvers for these domains have important applications, especially computer-assistr education. But learning solve symbolic problems is challenging for machine learning algorithms. Existing models either learn from human solutions or use hand-engineered features, making them expensive to apply in new domains. In this paper, we instead consider symbolic domains as simple environments where states and actions are given as unstructured text, and binary rewards indicate whether problem is solved. This flexible setup makes easy to specify new domains, but search and planning become challenging. We introduce five environments inspired by the Mathematics Common Core Curriculum, and observe that existing Reinforcement Learning baselines perform poorly. We then present novel learning algorithm, Contrastive Policy Learning (ConPoLe) that explicitly optimizes the InfoNCE loss, which lower bounds the mutual information between the current state and next states that continue on a path to the solution. ConPoLe successfully solves four domains. Moreover, problem representations learned by ConPoLe enable accurate prediction of the categories results suggest new directions for reinforcement learning in symbolic domains, well as applications to mathematics education.
problems in a real mathematics curriculum. Our
Introduction
Humans posses the remarkable ability to learn how to reason in symbolic domains, such as arithmetic, algebra, and formal logic. Our aptitude for mathematical cognition builds specialized neural bases but extends them radically through formal education 6 16 12]. Learning to reason symbolic domains poses important challenge for artificial intelligence research. As describe below, this type of reasoning has unique features that distinguish from domains in which machine learning has had recent success.
From a practical viewpoint, since symbolic reasoning skills span years of instruction in school, advances in symbolic reasoning may have large impact education. In particular, automated tutors equipped with step-by-step solvers can provide personalized help for students working through problems (28), and aid educators in curriculum and course design by semantically relating exercises based on their solutions
22 23 Indeed, studies have found automated tutors capable yielding
similar 20 larger 29 educational gains than human tutors. While solving problems alone does
not necessarily translate to good teaching, automated tutors typically have powerful domain models their underlying foundation.
However, even modest mathematical domains are challenging to solve. As an example, consider solving linear equations step-by-step using low-level axioms, such associativity, reflexivity and operations with constants. This formulation allows solution strategies that humans employ to be
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

expressed as combinations of few simple rules, making it attractive for automated tutors [2] 25]. But while formulating the domain simple, obtaining a general solver is not. Naive search is infeasible due to the combinatorial solution space. As an example, the search-based solver used in the recent Algebra Notepad tutor (25 is limited to solutions of up to steps. An alternative is manually writing expert solver heuristics. Again, even for domain such as high-school algebra, this route is difficult and error-prone, As we describe in Section we evaluated Google MathSteps, a library that backs educational applications with a step-by-step algebra solver, on the equations from the Cognitive Tutor Algebra [28] dataset. MathSteps only succeeded in 76% of the test set, revealing several edge cases in its solution strategies. Thus, even very complex expert- expert-written strategies may have surprising gaps.
An alternative could be learn solution strategies via Reinforcement Learning (RL). We formulate symbolic reasoning as an RL problem of deterministic environments that execute domain rules and give binary reward when problem is solved. Since we aim for generality, we assume domain- agnostic interface with the environment: states and actions are given to agents as unstructured text. These domains have several idiosyncrasies that make them challenging for RL. First, trajectories are unbounded, since axioms might always be applicable and lead to new states (e.g. adding a constant to both sides an equation). Second, agents have no direct access to the underlying structure of the domain, only observing strings and sparse binary rewards. Finally, each problem only has one success state (e.g. x number, in equations). These properties rule out many popular algorithms for RL. For instance, Monte Carlo Tree Search (MCTS, (7]) uses random policy rollouts train its value estimates. If the solution state is unique, such rollouts only find non- zonzzero reward if they happen to find the complete solution. Thus. MCTS fails to guide search toward solutions [.] Indeed, show in Section 5.2 Deep Q-Learning, and other algorithms that are based on estimating expected rewards, perform poorly in these symbolic domains.
To overcome these challenges, we propose a novel learning algorithm, Contrastive Policy Learning (ConPoLe), which succeeds in symbolic environments. Our key insight is to directly learn a policy by attempting to capture the mutual information between current and future states that occur in successful trajectories. ConPoLe uses iterative deepening and beam search to find successful and failed trajectories during training. It then uses these positive and negative examples to optimize the InfoNCE loss (24), which lower bounds the mutual information between the current state and successful successors. This provides a new connection between policy learning and unsupervised contrastive learning. Our main contributions in this paper are:
We introduce 5 environments for symbolic reasoning (Fig. 1T drawn from skills listed in the Mathematics Common Core Curriculum (Section 3). . We find that existing Reinforcement Learning algorithms fail to solve these domains.
We formulate policy learning in deterministic environments as contrastive learning, allowing us to sidestep value estimation (Section 4. The algorithm we introduce, ConPoLe, succeeds in all five Common Core environments, as well as in solving the Rubik's 's Cube (Section (.2)).
We provide quantitative and qualitative evidence that the problem representations learned by ConPoLe reflect the equation-solvv curriculum from the Khan Academy platform. This result suggests number of applications of representation learning in education.
2 Related Work
Automated mathematical reasoning spans several research communities. Theorem-proving languages, such as Coq [5] or Lean [10. enable the formalization of mathematical statements and can verify proofs, but they are limited in their ability to discover solutions automatically. rich line of recent work has focused on learning to produce formal proofs using supervised [27 32 2 and reinforcement learning 44 [8 26 Similar to GPT-f (27). our model only assumes unstructured strings as input; however, we do not use a dataset of human solutions. To the best of our knowledge, our work is the first to consider learning formal reasoning directly from text input (like GPT-f) by purely interacting with environment (like rlCop
18
and ASTatic 32).
Existing RL algorithms for theorem proving make use of partial rewards to guide search. For example, rlCop 18 learns to prove in the Mizar Verifier using Monte Carlo Tree Search. In Mizar, applying theorem decomposes the proof into sub-goals. Random policy rollouts often close fraction of the sub-goals, providing signal to MCTS. In our environments, however, there is only one solution state

---

sorting [--+]
|-==-|-=---
|-|==
|=
ternary-addition #(b2 c0 c2) #(a2 b3 c0 c2) #(b3 c0 c2)
#(C0 b3 c2)
- #(cO c2 b3)
multiplication 86e3* 28e2
(86e3* 2e3) + (86e3 * 8e2)
(172e6 688e5)
(86e3* (2e3 + 8e2)
(172e6 + (86e3*
8e2)
240800000
fractions 1/6 + (1*2)
1/6 + 2/6
3/6
1/2
1/6+ 1/3-
+ 1/6+2/(3*2)
(1+2)/6
3/(2*3)
equations 2x+1=5 2x+ (1 1) + 2x+0=4
(x*2)/2 = 4/2-~xx(2111 = 4/2 x=2
(2x (2x+1)= 1= (2x+ 1
2 (2x)/2 = 4/2
x+1 4/2 + x = 4/2
Figure 1: Example of one problem and step-by-step solution in each CommonCore environment, In equations, a problem is linear equation with the four basic operations and arbitrary parentheses, and actions are applications of low-level axioms (e.g. commutativity. associativity, distributivity, calculations with constants and applying operations on both sides). ternary-adee addition simulates step-by, bt-pppp arithmetic with carry in base 3: inputs are sequence of (digit, power) pairs, where letters are digits (a 0, b 1, c = 2) and numbers are powers of 3 (so b2 1- 12))). Adjacent digits can be added together, and digits O can be eliminated. In the example, we start with 1-32 + 2-332 +--32++20 +2.3" 2...2.442220 +2-3² and obtain 3 primitive operations, and must be combined with axioms that split larger numbers to perform long multiplication. In fractions, operations include factoring numbers into a prime multiplied by a divisor, canceling common factors and combining fractions with the same denominator. Finally, in sorting, the agent needs to sort delimited substrings by length by either reversing the entire list or performing adjacent swaps.
3 2 3 multiplican intppiccaiion addition and single-digit multiplication are
for each problem, causing MCTS to degenerate to breadth-first search. This challenge is similar in other large search problems, such as the Rubik's 's Cube. DeepCubeA [1] handles the sparsity problem in the Rubik's Cube by generating examples in reverse, starting from the solution state. This uses the fact that moves in the Rubik's s Cube have inverses, and that the solution state is always known a priori. In contrast, the algorithm we propose in Section 4 which has neither of these assumptions, is still able to learn an effective Rubik's 's Cube solver; we compare it to DeepCubeA in Section 5.2
provide key application for step-by-step solvers. Tutors or database querying B], can use a solver to help students even in the absence of expert human hints (unlike example-tracing tutors, which simply follow extensive problem-specific annotations 30). Currently, solvers used in automated tutors either search-based (25). but limited short solutions, or hand-engineered [17]. Our method can learn high-level solution strategies by composing simple axioms. generalizing to long solutions without the need for expert heuristics. Moreover, our analysis in Section 4 suggests that learned problem embeddings can be applied in mathematics education another advantage of neural solver.
Intelligent Tutoring Systems
20
28
22
for symbolic domains, such as algebra
28
25
Finally, our approach to Reinforcement Learning in symbolic domains builds unsupervised contrastive learning, specifically InfoNCE (24). Contrastive learning has been used to learn repre- sentations that then used by existing Deep RL algorithms 24 19 13] We instead make novel connection, casting policy learning as contrasting examples of successful and failed trajectories.
Setup
Motivated by mathematics education, we are interested in formal domains where problems are solved step-by-step fashion, such as equations or fraction simplification. While various algorithms could compute the final solution to such problems, finding step-by-ster solution by composing low-level axioms is planning problem. Formally, we define domain D (S. A, T, R) as deterministic Markov Decision Process (MDP), where $ is set of states, A(s) is the set of actions available at state 8, T( a) is the transition function, deterministically mapping state 8; E S and action a E A(s)) to the next state 8, and R(s) is the binary reward of a state: R(s) = 1 if is a "solved" state, otherwise R(s)= = 0. States with positive reward are terminal. Initial states can be sampled from probability distribution (s), which we assume to have states of varying distance to the solution
3

---

Table 1: Common Core environments for symbolic reasoning.
Environment
Reference
Average Branching Factor
BFS Success Rate
sorting
CCth.
5.84
17%
Sort objects by length.
lemnary-addition
10.55
9%
Perform step-by-step arithmetic with carry.
multiplication
CCS ContheConttt....i
8.62
26%
Multiply multi-digit whole numbers
fractions
CCSS. N.t...at...ooio Conteent.tt..B
6.58
18%
Manipulate expressions with fractions.
equations
CCSS. Mat.S..at....tet... Content.8.EE.C
27.12
5.5%
Solve linear equations in one variable.
state. This implicit curriculum allows agents to find few solutions from the beginning of training an important starting signal, since we assume no partial rewards.
States in symbolic domains typically have well-defined underlying structure. For example, math- ematical expressions, such as equations, have recursive tree structure, as do SQL queries and programming languages. A different, yet similarly well-defined structure dictates valid states in the Rubik's cube. However, order to study the general problem of symbolic learning, we want to assume no structure for states beyond the MDP specification. Therefore, we assume all states and actions are strings, i.e. S, A(s) C E" for some alphabet Naturally, our goal is to learn a policy π (als) that maximizes the probability that following when starting at randomly drawn state 5g ~ Pr()) leads to a solved state sg.
3.1 Environments
We introduce four environments that exercise abilities listed in the Mathematics curriculum of the Common Core State Standards. The Common Core is an initiative that aims to build a standard high-quality mathematics curriculum for schools in the United States, where "forty-one states, the District of Columbia, four territories, and the Department of Defense Education Activity (DoDEA) have voluntarily adopted and moving forward with the Common Core We draw inspiration from four key contents the curriculum: "Expressions and Equations". "Numbers and Operations Fractions". "Measurements and Data", and "Operations and Algebraic Thinking".
Table lists these environments.
put their respective search problems into perspective, we report two statistics: the average branching factor of 1M sampled states, and the success rate of a simple breadth-firg search (BFS) in solving 1000 sampled problems, when limited to visiting 107 state-action edges. All the environments require strategy and exploiting domain structure to be solved: naïve search succeeds only on the simplest problems, with success rates ranging from 26% in mul
to 5.5% in equations. We describe all axioms available in each environment in detail in the Appendix. Figure I gives an example of a problem and step-by-step solution in each of the environments. Agents operate in fairly low-level axiomatization of each domain: simple actions need to be carefully applied in sequence to perform desirable high-level operations. For example, to eliminate additive term in one side of an equation, one needs subtract that term from both sides, rearrange terms using commutativity and associativity to obtain a sub-expression with the term minus itself, and finally apply cancelation axiom that produces zero. This formulation allows agents to compose actions to form general strategies, but at the same time makes planning challenging.
4 Contrastive Policy Learning
common paradigm in Reinforcement Learning uses rollouts to learn value estimates: a starting state is sampled, the agent executes its current policy until the trajectory horizon, and state value is updated using observed rewards. However, when rewards are sparse, as in the symbolic environments
http:://ww.ccr http::/www.coreesaataard hwt.://utdooorooootoooooooooout standards/

---

considered here, this paradigm suffers from serious attribution problem. In failed trajectories, which are typically the vast majority encountered by an untrained agent, the signal of null reward is weak: failure could have happened due to any of the steps taken. Moreover, the agent has no direct feedback on what would have happened had taken different action a certain state, until it visits another similar state. In turn, long intervals between similar observations can hinder leaning. These issues are ameliorated by Monte Carlo Tree Search, and similar algorithms, which explore a search tree and may abandon sub-tree based expected outcomes. However, MCTS relies on Monte Carlo estimates of the value of candidate states. In games, such as Go or Chess, random rollouts find a terminal state per problem, providing reward signal. (Indeed, self-play in such games always terminates and wins about half games.) But in domains with a single terminal state, like math problems or the Rubik's 's cube, such estimates are unhelpful (.] returning zero reward with probability that approaches exponentially in the distance to the solution.
To obtain signal about each step of a solution, we would like to consider multiple alternative paths, as MCTS does, without relying on random rollouts to yield useful value estimates. To that end, we employ beam search using the current policy N, maintaining beam of the k states most likely to lead to a solution. When a solution found, the beam at each step contains multiple alternatives to the action that eventually led to a solution. We take those alternatives negative examples, and train a policy that maximizes the probability of picking the successful decision over alternatives.
Let fp st) be parametric function that assigns a non-neganee non-negative score between a proposed next state p and the current state s,, Although any non-negative function suffices, here we use a simple log-bilinear model that combines the embeddings of the current and proposed states, both obtained with the state embedding function Φo S + R.:
felp, 8.) exp (do(p)) We (s:))
Once we find a solution using beam search, for each intermediate step t we have state 8ı and set X {PI....,PX of next state proposals, obtained from actions that were available at states in the beam at step t. One of these, which we call S141, is the proposal in the path that led to the found solution. We then minimize:
fo(se+1, 88) Epee Solpi,
(,(0) = Eeg loog
Algorithm I describes method, which we call Contrastive Policy Learning (ConPoLe). In successful trajectories, ConPoLe adds positive and negative examples of actions to a contrastive experience replay buffer. After each problem, it samples batch from the buffer and optimizes L.- Since we can only find positives when a solution is found, ConPoLe essentially ignores unsolved problems. Moreover, improve data efficiency, ConPoLe iteratively deepens its beam search: with an uninitialized policy, it cannot expect to find long solutions, so exploring deep search trees is unhelpful. In our implementation, we simply increase the maximum search depth by every K problems solved, up to a fixed maximum depth.
Our loss E is equivalent to the InfoNCE loss, which is shown in (24 to bound the mutual information: [(1441, s;) 2 log X L, Note that in our domains each state is the next step for the correct solution to some problem, thus the negative set found by beam search approximates negative samples of next states from other solutions, though with a bias toward closer 'hard negatives' [II]. Thus our approach can be interpreted learning representation that captures the mutual information between current states and their successors along successful solutions. The MI bound becomes tighter with more negatives: we explore this property experimentally in Section 5.2 We refer to 24 for a detailed derivation of this bound and its properties.
As our policy we directly use the similarity function [ps 8t)) normalized over possible next states. The objective C, is also the categorical cross entropy between the model-estimated next state distri- bution To (p)st) Epyea f(py and the distribution of successful proposals. It is thus minimized
f(p.a.)
when the predictions match P( pı(s:), the optimal policy.
The ConPole approach avoids value estimation by focusing directly on statistical properties of solutions. The sorting environment illustrates the intuition that this is simpler objective. In this
5

---

domain, the agent has to sort list of substrings by their length, using adjacent swaps or reversing the whole list. The value of state would be proportional to the number of inversions (i.e. pairs of indices that are in the incorrect order). This prediction problem is hard for learning: O(n") pairs of indices need to be considered ConPoLe, however, only needs tell a proposed state has more or less inversions than the current state. In the case of adjacent swaps, this amounts to detecting whether the swapped elements were previously in the wrong order. By having negative examples to contrast with successful trajectories, ConPoLe can learn policy by completely sidestepping value estimation.
Algorithm 1: Contrastive Policy Learning (ConPoLe)
Input: Environment E
Output: Learned policy parameters T init_parameters)
D D+@
n_ r__solved 0
for episode <- to N do
p p p
(solution, visited states) <- beab beam_search( No, beam_size, max_ mea_depphh)
visited_states) solution # null then
n_solved rr_solved+1
neg_states + brisite_sstaee solution do
for i + 1 to length(solution)
pos + (solution (i], solution(i + 1])
neg + [(solution(i]] c) E neg_states states from step of beam_search)
D.add (poss, (pos,neg) neg))
end
B - D. w.s.mplleebacchbl 0 0 @VInfNNCE(() B)
end
end
Experiments
We now evaluate method guided by the following research questions: How does ConPoLe perform when solving symbolic reasoning problems from educational domains? How do negative ex- amples affect ConPoLe's performance? Are ConPoLe's problem embeddings useful for downstream educational applications? Can ConPoLe be applied to other large-scale symbolic problems?
5.1 Setup
We compare ConPoLe against four RL baselines and the Google MathSteps library, which contains manually implemented st-peb solvers for the Fractions and Equations domains (as opposed to simply giving the final answer, as several other libraries do). The first learning based baseline is the Deep Reinforcement Relevance Network [14] DRRN], an adaptation of Deep Q-Learning for environments with textual state and dynamic action spaces. We additionally test Autodidatic Iteration 21 ADI] and Deep Approximate Value Iteration I DAVIJ both methods have been recently used to solve the Rubik's Cube, discrete puzzle that similar the Common Core domains in that only has single solution state. Finally, we use simple Behavioral Cloning (BC) baseline, as done in ( it executes a random policy until its budget is exhausted; then, it trains classifier only on the successful trajectories that picks the successful action.
As simpler alternative ConPoLe, we use baseline we call Contrastive Value Iteration (CVD). This algorithm is identical to ConPoLe except for its loss: we train it to predict the final reward obtained by each explored state. In other words, after finding a solution, CVI will add examples to its replay buffer of the form (s. r) E S x R, where is visited state and r is 1 if that state occurred in
A (n log solution counts inversions by exploiting the merge sort recursion httpp:://eee thubbhbb..tttt..////gge/...... httpgg/ttt...ooogl//////////// comm/googll/nnattteess

---

Agent
Sorting
Addition
Multiplication
Fractions
Equations
BC
92.0%
64.5%
10.0%
52.5%
4.5%
DRRN
29.5%
40.0%
10.5%
20.0%
2.5%
ADI
91.0%
63.5%
9.5%
46.5%
5.5%
DAVI
99.5%
54.0%
18.5%
57.5%
8.0%
MathSteps(M)
100%
76.0%
CVI
77.0%
72.0%
100.0%
84.5%
89.0%
ConPol.e-local
100.0%
98.5%
99.5%
86.0%
76.5%
ConPoLe
100.0%
100.0%
99.5%
96.0%
92.5%
Table 2: Success rate of all agents in the CommonCore environments. Agents were ran with 3 random seeds for 107 environment steps, and tested every 100k steps on a held-out set of 200 problems. We report the best observed success rate of each agent's greedy policy (i.e. no search done at test time). (N) emphasizes that the MathSteps library is not caaming-basedd we simply ran it test problems.
the path to the solution, or 0 otherwise. This can be seen as estimating P(s'): the probability that s' would be observed in a successful trajectory, without conditioning on the current state. Since the reward is binary, this corresponds to value estimation.
All models two-layer character-level LSTM 15 network to encode inputs (DRRN networks). Each agent was trained for 10" steps in each environment; runs took from 24 to 36 hours on single NVIDIA Titan Xp GPU. Problems in the equations domain come from set of 290 syntactic equation templates (with placeholders for constants, which we sample between -10 and 10.) extracted from the Cognitive Tutor Algebra [28 dataset. Other environments use generators describe in the Appendix. Code for agents and CommonCore environments is available at https 7/github. cwm hamp/gposia///amooomoomm socratic tutor Our Common Core environments are implemented in Rust, and simple tigh-throughput API is available for Python.
such
5.2 Solving Common Core domains
We start by comparing agents when learning in the CommonCore environments. In this experiment, agents train using sequentially sampled random problems. We define one environment step as a query in which the agent specifies state, and the environment either returns that the problem is solved or lists available actions and corresponding next states. Since trajectories can be potentially infinite, limit agents search for maximum depth of 30, which was enough for us manually solve sample set of random training problems from all environments.
Table 2 shows the best performance of each agent held-out test set of 200 problems. Success rate is measured using each agent's 's greedy policy: we do not perform any search at test-time. DRRN fails to effectively solve any of the environments. ADI, DAVI and BC can virtually solve the sorting domain, but this performance does not translate to harder domains multiplication and equations. ConPoLe shows strong performance all domains, with CVI being comparable in equations and multiplication, but falling behind in the other two domains.
DRRN quickly converges to predicting near 0 for most state-action pairs, failing to learn from sparse rewards. We note that the environments where DRRN has shown success, such as text-based games, have shorter states and actions as well as intrinsic correlations between states (derived from natural language). These features may help to smooth the value estimation problem but are not available in the Common Core domains.
We note that ADI and DAVI have been previously successful in puzzles with an important feature: the state sampler produces problems that are exactly l steps from the solution for all i up to the maximum necessary. For instance, in the Rubik's Cube, scrambled cubes can be generated by starting from the solution state and performing l moves in reverse. This feature is present in the sorting vorting domain (in which both ADI and DAVI perform well), but not general. For example, even the simplest equation in the Cognitive Tutor dataset still requires actions to be solved; some require up to 30, and there are many gaps in this progression. These gaps cause ADI and DAVI to find states at test time that are out of their training distribution. As suggested in (1]. we experimented with
7

---

replacing the 1-step lookahead of these algorithms by a bounded BFS. However, we found that this naive exploration strategy sample inefficient and did not significantly change their performance.
On the other hand, algorithms that learn from contrasting examples (CVI and ConPolee perform well in all environments. Using only examples derived from solved problems gives much higher signal to each data point: we only consider a "negative" when we have a corresponding positive example which actually led solution. Moreover, we observe gains in using the InfoNCE loss for training with contrasting examples: ConPoLe performs consistently better than CVI, and can very quickly learn to solve almost all sorting and addition problems. In these domains, deciding whether an action moves towards the goal is an easy problem, but precisely estimating values is challenging. In Sorting, for example, CVT's learned policy becomes unreliable for lists with more than 7 elements. We observe similar limitation in Addition, where one sub-prole tlbbproblem is sorting digits by the power of 10 they multiply.
These observations provide evidence to answer our first research question: using contrastive examples beneficial learning policies in symbolic domains, and explicitly optimizing a contrastive loss improves results further.
The impact of negative examples Contrastive learning algorithms have been observed to perform better with more negative samples: the variance of the InfoNCE estimator decreases with more negative examples. However the choice of negative examples can also impact the performance B1. We thus experimented with a simple variant of ConPoLe that produces fewer, but more local, negative examples. Instead of using all candidates visited by beam search, we instead only use those that were actual candidates for successors of states in the solution path. We call this variant ConPol.e-local, since it only uses "local"" negatives. The performance of ConPol.e-local is shown in Table 2 ConPol.e-local behaves like ConPol.e in Sorting, Addition and Multiplication. In the last two domains, however, there is significant performance gap between ConPoLe and ConPoLe-local Interestingly, this does not seem to be the case for CVI. We executed the same experiment with CVI, and observed no reliable difference in performance or learning behavior. This finding supports the importance of the connection between reinforcement learning and contrastive learning: using all available negatives, in the way suggested by InfoNCE, yields the best results.
5.3 Comparing learned representations to human curricula
A learned neural solver yields distributed repre- sentations for problems. One natural question whether these representations capture proper- ties of the problems that resemble how humans structure the same domains.
Embeddings of Khan Academy equations: PCA projection
Section
Equations
One-step multipiiation division equations
Two step equations
To investigate this question, we collected a dataset of equations from the Khan Academy educational portal. We used the equations listed as examples and test problems in the sections of the algebra curriculum dedicated to linear equations. There are four sections: "One-step addition and subtraction equations", "One-step multiplication and division equations". "Two- step equations" and "Equations with variables on both sides". The first three categories had 11 equations, and the last had 9.
9.
Figure 2: PCA projection of ConPoLe's learned representations for equations from Khan Academy, Point sizes indicate ConPoLe's solution length (ranging from 7 to 29 in these exereises). We observe clusters that closely match the different sections of the Khan Academy curriculum.
We evaluated 1-nearest neighbor classifier that predicts the equation's 's category from the closest labeled example, based on four distance metrics: string edit distance (a purely syntactical base- line), and cosine similarity using the representa- tions learned by agents. Chance performance in this task is 26%.
'atps://www.khanccadmn
8

---

Table 3: Accuracy of predicting equation categories from learned representations on Khan Academy,
Representation Accuracy
BC 0.619
DRRN 0.642
ADI 0.619
DAVI
CVI 0.642
Edit Distance
ConPoLe 0.905
0.619
0.714
Table shows ConPoLe's representations yield accurate category predictions (90.5%), while other representations are less predictive than the Edit Distance baseline. We further observe that ConPoLe's latent space is highly structured (Figure sections from Khan Academy form visible clusters. This happens despite of ConPoLe being trained without an explicit curriculum or examples of human solutions.
5.4 Solving the Rubik's Cube
Finally, we apply ConPoLe to a challenging search problem: the Rubik's Cube []] This traditional puzzle consists of 3x3x3 cube, with 12 possible moves that rotate of the 6 faces either clockwise or counterclockwise. Initially, all 9 squares in each face have the same color. The cube can be scrambled by applying face rotations, and the goal is to bring it back to its starting state. There 4.3 x 10t valid configurations of the cube, and a single solution state. We compare ConPoLe to DeepCubeA [1 state-of-the-arr solver that learns with Deep Approximate Value Iteration.
For this task, we simply represent the cube as a string of 54 digits from 0 to 5, representing 6 colors, with separators between faces. We the exact same architecture domains. We train ConPoLe for 102 steps on a single GPU, with a training beam size of 1000, on cubes scrambled with up 20 random moves. (DeepCubeA observed 10 billion cubes during training time, compared to 10 million environment steps taken by ConPol le during training.) In test time, following DuepCubeA, employ Batch Weighted A Search (B (BWAS), using our model's predicted log-probabilities as weight estimates.
used in the Common Core
We find that ConPoLe is able to learn effective solver. We tested 100 instances scrambled with 1000 random moves, as used in DeepCubeA's evaluation. ConPoLe succeeds in all cubes (as does DeepCubeA). In finding solutions, BWAS paired with ConPoLe visits average of 3 million nodes, compared to 8.3 million with DeepCubeA, DeepCube solutions however are shorter (21.6 moves on average, compared to ConPoLe's 's 39.4) Overall, Overall, this result validates the generality and promise of ConPoLe for solving challenging symbolic domains.
Conclusion
We introduced four environments inspired by mathematics education, in which Reinforcement Learning challenging. Our algorithm, based on optimizing a contrastive loss, demonstrated significant performance improvements over baselines. While we used educational domains test bed, our method can in principle be applied to any discrete planning domain with binary rewards. One requirement is that untrained agent must find enough solutions to assemble initial contrastive examples. Procedural mathematical domains are a natural instance of these. However, our educational environments assume a linear structure, where applying axiom directly leads the next state. This assumption breaks in more expressive formulations formal mathematics (such as first-order logic or dependent type theories), where proofs have tree structure. Other domains, such programs, might pose additional challenges because an unbounded number of actions can be available at a state. Adapting ConPoLe for these settings is non-trivial, and poses important challenges for future work.
Our learned solvers can simplify the process of building Intelligent Tutoring Systems. These systems can free educators focus more conceptual problems. On the down side, solvers can provide unfair resources for homework and unequal access could exacerbate incquality. Beyond tutoring, we observed that the representations learned by our agents capture semantic properties about problems. This opens up an avenue for additional research on deep representations for educational applications.
'BWAS can be tuned to trade off shorter solutions for exploring more nodes; we only tested the default parameters in the DeepCubeA implementation. Given DeepCubeA was trained on 1000x more cubes, we would expect its solutions still be shorter if we matched both algorithms in number of visited nodes.

---

Acknowledgements
We thank the anonymous NeurIPS reviewers for the valuable discussion, which significantly improved our work. This work was supported by a NSF Expeditions Grant, Award Number (FAIN) 1918771.
References
[1] Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi. Solving the rubik's cube with deep reinforcement learning and search. Nature Machine Intelligence, 168):356-363, 2019.
[2] Alexander A Alemi, François Chollet, Niklas Een, Geoffrey Irving, Christian Szegedy, and Josef Urban. Deepmath-deep sequence models for premise selection. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 2243-2251, 2016.
[3] John R Anderson, C Franklin Boyle, and Brian J Reiser. Intelligent tutoring systems. Science, 228(4698):456-46, 1985.
[4] Kshitij Bansal, Sarah Loos, Markus Rabe, Christian Szegedy, and Stewart Wilcox. Holist: An environment for machine learning of higher order logic theorem proving. In International Conference on Machine Learning, pages 454-463, PMLR, 2019.
[5] Bruno Barras, Samuel Boutin, Cristina Cornes, Judicaël Courant, -han-Christophe Filliatre, Eduardo Gimenez, Hugo Herbelin, Gerard Huet, Cesar Munoz, Chetan Murthy, et al. The Coq proof assistant reference manual: Version 6.1. PhD thesis, Inria, 1997.
[6] Brian Butterworth and Vincent Walsh. Neural basis of mathematical cognition. Current biology,
21 21(16):R61 8-R621, 2011.
[7] Guillaume Chaslot, Jahn-Takeshi Saito, Bruno Bouzy, JWHM Uiterwijk, and H Jaap Van Den Herik. Monte-carlo strategies for computer go. In Proceedings of the 18th BeNeLux Conference on Artificial Intelligence, Namur, Belgium, pages 83-91, 2006.
[8] Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Michael Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling. arXiv preprint arXiv:2106.01334 2021.
[9] Thomas H Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to algorithmss MIT press, 2009.
[10] Leonardo de Moura, Soonho Kong, Jeremy Avigad, Floris Van Doomn and Jakob von Raumer. The lean theorem prover (system description). In International Conference on Automated Deduction, pages 378-388 388. Springer, 2015.
[11] Stanislas Dehaene. The number sense: How the mind creates mathematics. OUP USA, 2011.
[12] Stanislas Dehacne, Nicolas Molko, Laurent Cohen, and Anna J Wilson. Arithmetic and the brain. Current opinion in neurobiology, 14(2):218-22 224, 2004.
[13] Haotian Fu, Hongyao Tang, Jianye Hao, Chen Chen, Xidong Feng, Dong Li, and Wulong Liu. Towards effective context for meta-reiinforcemmnt learning: approach based on contrastive learning. arXiv preprint arXiv:2009. 13891, 2020.
[14] He, Jianshu Chen, Xiaodong He, Jianfeng Gao, Lihong Li, Li Deng, and Mari Ostendorf. Deep reinforcement learning with natural language action space. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),
pages 1621-1630, 2016.
[15] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9 1997.
[16] Olivier Houdé and Nathalie Tzourio-Mazoyer. Neural foundations of logical and mathematical cognition. Nature Reviews Neuroscience, 4(6):507-514 2003.
[17) Google Inc. Mathsteps: A step by step solver for math. https://github. com/ wtt.tttt...ooooooggg/// google/ mathsteps] 2020.
[18] Cezary Kaliszyk, Josef Urban, Henryk Michalewski, and Mirek Olšák, Reinforcement learning of thcorem proving. arXiv preprint arXiv:1805.07566 2018
10

---

[19] Michael Laskin, Aravind Srinivas, and Pieter Abbeel. Curl: tations for reinforcement learning. In International Conference on Machine Learning, pages 5639-5650. PMLR, 2020.
Contrastive unsupervised represen-
[20] Wenting Ma, Olusola O Adesope, John C Nesbit, and Qing Liu. Intelligent tutoring systems and learning outcomes: A meta-analysis. Journal of educational psychology, 106(4):901, 2014.
[21] Stephen McAleer, Forest Agostinelli, Alexander Shmakov, and Pierre Baldi. Solving the rubik's cube with approximate policy iteration. International Conference on Learning Representations, 2018.
[22] Gordon McCalla. The search for adaptability, flexibility, and individualization: Approaches to curriculum in intelligent tutoring systems. In Adaptive Learning Environments, pages 91-121. Springer, 1992.
[23] Erica Melis and Jörg Siekmann. Activemath: An intelligent tutoring system for mathematics. In International Conference on Artificial Intelligence and Soft Computing, pages 91-101. Springer, 2004.
[24] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, arXiv preprint (cXiv:1807.03744 2018.
[25] Eleanor O'Rourke, Eric Butler, Armando Diaz Tolentino, and Zoran Popović. Automatic generation of problems and explanations for an intelligent algebra tutor. In International Conference on Artificial Intelligence in Education, pages 383-395, Springer, 2019.
[26] Bartosz Piotrowski and Josef Urban. Atpboost: Learning premise selection in binary setting with atp feedback. In International Joint Conference on Automated Reasoning, pages 566-574. Springer, 2018
[27] Stanislas Polu and Ilya Sutskever. Generative language modeling for automated theorem proving. arXiv preprint arXiv:2009.03330 2020.
[28] Steven Ritter, John Anderson, Kenneth Koedinger, and Albert Corbett. Cognitive tutor: Applied research in mathematics education. Psychonomic bulletin & review, 14(2):249-255, 2007.
[29] Kurt VanLehn. The relative effectiveness of human tutoring, intelligent tutoring systems, and other tutoring systems. Educational Psychologist, 16(4):197-221, 2011.
[30] Daniel Weitekamp, Erik Harpstead, and Ken R Koedinger. An interaction design for machine teaching to develop ai tutors. In Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems, pages 1-11, 2020.
[31] Mike Wu, Milan Mosse, Chengxu Zhuang, Daniel Yamins, and Noah Goodman. Conditional negative sampling for contrastive learning of visual representations. In International Conference on Learning Representations, 2021.
[32] Kaiyu Yang and Jia Deng. Learning to prove theorems via interacting with proof assistants, In International Conference on Machine Learning, pages 6984 6994. PMLR, 2019.


Reviews:
[{"review_id": "wvzRJs0Ey7n", "reviewer": "Reviewer_cgrc", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nStrengths:\n1. 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\n\n2. 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.\n\nWeaknesses:\n1. 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.\n\nA comparison between ConPoLe and Autodidactic Iteration - the approach used in DeepCube - on all the environments would have made the paper much stronger.  \n\n2. 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\".\n\nPost-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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "vj57nQlRoW", "reviewer": "Reviewer_xzcf", "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nHowever, I have some concerns about the paper. I would appreciate authors to address these questions and improve writing of the paper in general.\n\nFirst 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.\n\nIn terms of method/technical approach, search of solution space is done via beam search.\nOne 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.\n\nArguably, 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).\n\nThe 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.\n\n\nWriting/Clarity:\n\n- Qualitative examples or demo of the environment/task needs to be given in the main paper without need to look at the supplementary.\n- 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.\n- Algorithm 1: the authors should avoid using weird italic fonts in LaTeX math environments -- roman fonts preferred.\n- 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?\n- Figure 2 seems to be placed in a random place. It would be good to place them in the top area.\n\n\n----------\n\nPOST-REBUTTAL UPDATE: I have updated my rating from 5 to 6. Please see my comments below in reply to the author feedback.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours; additional ~10 hours for post-rebuttal discussions"}, "extra_text": {}}, {"review_id": "WUSQitWBdhx", "reviewer": "Reviewer_z1yq", "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.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nAs a method paper, it is important to evaluate the method on established dataset/problem domains, and compare the method against other baselines. \n\nPros 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). \n\nCons: 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!", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours, split over two days"}, "extra_text": {}}, {"review_id": "VvWavdEdM24", "reviewer": "Reviewer_MxYv", "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). ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nI 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:\n\n1. 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!) \n\nIt 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? \n\n2. 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.\n\nMy two general questions:\n\n1. 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?\n\n2. 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)?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, I think limitations and societal impact are adequately addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}]

Author rebuttal:

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)