Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper addresses a societally relevant and technically challenging problem by addressing it in very general terms (rather than offering a solution specific to one application domain). Both the problem and the solution are exceptionally well motivated.

The key conceptual contribution is to identify student submitted programs as MDPs (formalizations of environments for interaction in which certain outcomes are associated with rewards/utility). Although the motivated goal is to provide students with (rich?) feedback on their program, this is reduced to binary grading: classification (although any feedback is better than none in this setting where feedback is desperately needed).

The resource contribution of a dataset is also appreciated.
main_review: The identified problem is highly significant, but the proposed solution is somewhat less. It is unclear if the empirical result achieved is mostly a result of better state space exploration (which can be achieved without involving reinforcement learning) or if the quite complicated collaborative training step (involving all of DQN) was essential. That said, identifying this problem setting as a few-shot classification task to be solved by similarity search is quite interesting.*

* It also suggests a form of rich feedback for students. When students see their grade, they could also be shown which of the reference solutions theirs was most similar to (and even see one of the reference trajectories for that environment, showing how the same kind of bug manifests in their program). 

The central challenge searching for diverse states in interactive software to uncover bugs feels inherently much more related to the areas of automated exploration (e.g. the upstream literature of Go-Explore https://arxiv.org/abs/1901.10995 or recent applications of RRT-based methods to games http://ceur-ws.org/Vol-2313/KEG_2019_paper_9.pdf), and input fuzzing (e.g. upstream of https://www.ei.ruhr-uni-bochum.de/media/emma/veroeffentlichungen/2020/02/27/IJON-Oakland20.pdf) than reinforcement learning. Exploration/fuzzing is often *unmotivated* (not based on maximizing rewards) or at *intrinsically* motivated (not dependent on environmentally-provided rewards). It might be the case that something like Go-Explore (which might be seen as a kind of randomized breadth first search using screenshot pixels to judge distinct states) or a classic fuzzer (given access to an abstraction of the game’s state vector) can provide the diverse trajectory samples needed for the proposed classifiers to work just as well without defining any rewards or running DQN.

limitations_and_societal_impact: The assumption that all student programs have a common action space feels appropriate, but the assumption that they all have the same state space feels much more limiting. It might not occur in the Code.org setting, but it feels quite realistic for some student programs to track state elements (such as the health of enemy characters) where others do not, even when given the same prompt to design their games/programs. The assumption of shared state is critical for being able to transfer policies between the many related submissions being graded. But an approach that did not need to train policies to access diverse trajectories might bypass this limitation.

The authors are encouraged to use their specific knowledge of the domain to explain why even though having different amounts of variable state in different programs might be very common in general, it is almost entirely absent in their domain.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper formalizes the a binary classification problem: whether a student-authored, interactive code program is correct or not. The difficulty of this problem stems from the interactive nature of the program: in order to determine whether it is correct, the algorithm must "play" with it (because it is interactive) and then determine whether it is correct by finding whether the "play" results in some undesired/buggy behaviors. The proposed solution consists of an agent that learns to play with the program, and a modified LSTM (the so called hoareLSTM) that classifies programs (more specifically, certain "state" and "action" pairs in a program) into correct or incorrect. Evaluation on 2 simulated environments and on 1 program assignment demonstrate the effectiveness of the proposed approach over a few baselines (3 in the simulated environment and 2 in the program assignment).
main_review: The paper explores an interesting and important problem. The proposed solution is interesting. However, at this paper's current state, I do not recommend acceptance. My main concern is the lack of clarify and details. I also have some concerns on the real-world applicability of the proposed method. Some of the issues I listed below may seems insignificant on its own, but combined, they make it a bit difficult to get the full picture and understanding of the proposed method. It would have been nice if more details were available in the supplementary material.


1.  The notion of a "game" is not super clear to me. Is it coding environment itself, in which leaners are completing the programming assignment on code.org? Or is it the output of the programing assignment, i.e., what the students are asked to do in the programming assignment? Or is it the environment in which the proposed agent is trying to identify the "bug-triggering state"? Some graphical illustrations or explanations about the "game", the coding environment of code.org, and example solutions would be very helpful. 


2. The definitions of action and state in the program MDP is not super clear to me. For example, what are the representations of states and actions, i.e., are they vectors representing something? What is the action space, and are actions continuous or discrete? Are the set of states finite? What do actions and states correspond to in the context of programs? Again, some illustrations would be helpful. 


3. The argument that prior work on code-level does not generalize well beyond 10 lines of code (line 74 - 76) is not quite well substantiated. First, it's not clear how many time steps the program MDPs are; if they are more or less 10 steps, then the proposed method is no better than previous methods that work on 10 lines of code. Some additional characterization and statistics on the code.org dataset would also be helpful, e.g., the average lengths $t$ of the programs etc. From the supplementary material, the programs seem rather short. Second, I don't see how the proposed method "sidesteps the complexity of static code analyses" because it seems the interactive/dynamic code analysis introduces even more challenges. 


4. The educational utility of identifying the "bug-triggering state" is not demonstrated. Without this, it is difficult to recognize the educational value of this work, because the whole purpose of this work is to give feedback. It would be great if an illustrative example can be provided, i.e., at a certain state the program produces undesirable behavior, and thus is considered wrong. I acknowledge the code.org dataset is still proprietary, but is it possible for the authors to create a fake program on code.org by themselves (I assume code.org is generally accessible) and demonstrate your trained algorithm using your custom-made example?


5. It would be great if additional details and analyses of the proposed method are available. For example:
- How are the teachers' gold solution(s) and "best guesses" of wrong solutions (lines 84 - 87) used? Are the gold solutions the "reference MDPs"? If so then how are the best guessed wrong solutions used?
- In implementing algorithm 1: how many trajectories are collected for the different environment? Is the number related to the complexity of the environment? How is $\delta$ adjusted and why it started at 0.1? 
- Why the hoare triple predictor necessarily needs to be an auto-regressive model? It seems like a feedforward network might also work because the loss in (6) is on a single pair of $(s,a)$? And by the way, only in (4) do $a$ and $s$ have the $t$ subscripts and it's a bit confusing whether $(s,a)\sim\pi$ is sampling a single $(s,a)$ or a sequence of them.
- Why Table 1's setting (5 runs with CI) is different from Table 2's setting (3 runs without CI)? More details on the experimental details would be helpful.


6. It seems that the evaluation on the code.org data is on a single assignment. If this is true, how does this method generalize to other assignment, if one needs to collect a large number of students' submissions and train the method for each programming assignment? Some discussions on the scalability, generalizability, and applicability of the proposed method in the real-world would be helpful.


7. There are a number of typos:
- line 35: "for a 20 seconds"
- line 54: "with a students assignment"
- line 106: "fewer from"
- line 154: "solving is task is"
- line 184: "they are also been extended"
- line 196: "if we learn to"
- line 224: "sample MDPs effective"
- line 238: run-on sentence 
- line 136: I don't think you can write the probability of $D(M,M') > \nu$ because I thought $D(M,M')$ is not a random variable but just a number, so it does not have a distribution? 



=========
post rebuttal:
Having seen the discussions and reviews from the other reviewers and the authors rebuttal, the value of this paper outweigh the many presentation and clarity issues. I have changed my rating and hope the final version is much more polished than the submitted one.
limitations_and_societal_impact: See review above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper describes a new method for automatically identifying whether a student's code submission for an interactive task (e.g., code for a game with specific rules defined in the assignment) is correct or incorrect. Using a very small training set of at least one correct and one incorrect example for the assignment, each example and student submission is treated as a separate MDP, and goal is to classify whether a student submission is equivalent to the reference MDP for the correct game. To determine if two MDPs are equivalent, they focus on identifying differential states, which are those states that are most different, and then examine whether they exceed a teacher-defined threshold. A "Play to Grade" objective is defined such that maximizing it means finding a policy that frequently reaches differential states. The challenge is then to determine actions to take in the separate MDPs to maximize reaching of differential states, as randomness in the games means that taking the same actions in ech MDP isn't sufficient, as well as determining an appropriate distance function between (state, action) pairs in the new submission and the reference MDP. The paper considers several approaches to both problems: for the distance function, baselines are based on noisy supervised learning and unsupervised learning, and the improved methods examine unexpectedness in the MDP of predicted versus observed states as well as directly contrasting the student submission with an approximated correct MDP and bug MDP. For learning a policy, the paper considers pre-training versus no pre-training, as well as iteratively improving the constant delta that is used within the determination of whether some (s,a) is a differential state. Two types of experiments are performed: a toy example using a car game and a test of real student submissions from Code.org. Results show an improvement over the baselines for the toy example, and an improvement over an approach that treats code-as-text for the Code.org submissions.

main_review: Overall, I think this paper presents a very fun and interesting idea for how to grade interactive programs, and the approach is fairly different from most of the work I'm familiar with. It's less clear to me how generalizable the results are in order to gauge how well this technique is likely to work in practice, and I would have liked to have seen the paper acknowledge a bit more the difference between formative guidance and feedback on correctness versus incorrectness. I also think that some improvements to clarity would increase its impact. In the review below, I address the four points from the reviewer guidelines.

Originality: 
While I am not deeply immersed in the background literature here, the approach is novel to the best of my knowledge. With regards to related work, it did seem like a somewhat broader set of work that focuses on automated guidance for programs could be helpful given that that seems to be the ultimate goal with formative feedback, e.g.:
- Rivers, K., & Koedinger, K. R. (2017). Data-driven hint generation in vast solution spaces: a self-improving python programming tutor. International Journal of Artificial Intelligence in Education, 27(1), 37-64.
- Paaßen, B., Hammer, B., Price, T., Barnes, T., Gross, S., & Pinkwart, N. (2018). The Continuous Hint Factory-Providing Hints in Vast and Sparsely Populated Edit Distance Spaces. Journal of Educational Data Mining, 10(1).


Quality: 
The paper seems to generally be technically sound. As noted below, there were some points where the lack of clarity made it difficult to evaluate. The major question I had related to the technical work was in the evaluations. My specific concern is how sensitive the algorithm is to the range of incorrect examples and whether the types of errors students tend to make in real environments are likely to be caught by this method. In the toy example, the described error doesn't seem to be generally of the sort we might expect a student to make (it's not clear how clipping the velocity is something that would commonly arise - one might instead expect something to be slightly off in the dynamics through mis-specifying a relationship/formula) and one of the two errors given for bounce again doesn't necessarily seem like something a student is likely to do and to not know is incorrect (having multiple balls when there should only be one). In these examples, it's also not clear how much room there is for creativity or whether the algorithm would be able to identify and not flag differences that are permitted due to "creative discretion", and dealing with creative differences is something that is given as a motivation in the first paragraph of the intro. It seems likely that the way these are accommodated is through the range of sample correct/incorrect submissions containing sufficient information for this to be learned. But, as far as I can tell, the algorithm's sensitivity to the number and range of these submissions is not considered, which may be because in these tasks, there really is only one "correct" MDP or set of behaviors (even if there are many different ways to create code for that behavior). I would have liked to see more discussion of this issue, including potentially evaluating what happens in the real Code.org evaluation is the set of incorrect submissions is varied and minimally, helping the reader understand whether there is any creative discretion permitted (and if so how).

My additional issues are related to both technical quality and clarity. I had a hard time following why the iterative collaborative training was not considered for the Code.org evaluation (as mentioned in lines 326-335). I think the point is that this is not needed, but demonstrating that that would be helpful. 

In lines 288-289, it's stated that "We can see that in Table 1, all models including baseline models are able to predict bug states accurately in a single direction agent setting"; Table 1 doesn't seem to imply that for the GMM. In table 2, 95% confidence intervals aren't given like they were for table 1, and additionally, I was wondering why 3 runs are averaged over for table 2 and 5 for table 1. Finally, I would have appreciated some insight on why CT seemed to make GMM worse.

For the code.org experiment, it's not clear how accurate this is likely to be for real student submissions given that they are actually imbalanced, and it also seems misleading to give the table titles as the total number of submissions given that in fact, 500 submissions with 250 from each class are used for each of body and tail. I recognize that this is given in the caption, but even if one wants to report accuracy on the 500 sampled programs, would it also be possible to report accuracy on the fully dataset? For the tail, how many program submissions were correct versus incorrect? I would have also liked to have known a bit more about the range of the actual kinds of errors in the program behavior - a small amount of information is given in 327-328, but better understanding the complexity of the task and the kinds of errors would help with assessing the practicality of this method.

Finally, from what I can tell, the method used for Code-as-text is not given. I assume this is the code-as-text approach cited much earlier in the paper ([11]) as an example of an alternative, but it would be helpful to make this explicit in the evaluation.


Clarity: 
There were a number of points where additional clarity would have helped the reader; some of these issues are noted above and some here, and a list of small typos is given at the end of the review. First, I'm not sure that lower case delta is defined precisely, and articulating the relationship between nu and delta would be useful. In the experiments, it's not clear what nu is set to (earlier, it's given as a teacher-set parameter).

There are several other points where clarity about parameter setting would be helpful. For the unsupervised learning baselined, it's stated that "We can adjust sigma based on the performance over D" but I don't believe it's specified how that is done. In 4.2, it's stated that delta can be chosen so that all (s, a) can be labeled as correct. Slightly more explanation here would be helpful, and having more explicitly defined the tuple (s, a) earlier (in 2.1-2.2 - the components are clear, but the way it is being used as a tuple isn't always clear - might help). 

In section 4, more clarity about the reward function being used and how this relates to equations 2-3 would be helpful. In paragraph 1, it seems to say that the reward function needs to be about finding bugs (like in 2), but then the second paragraph says the original reward function is good enough. Making more explicit whether this is "in practice, we'll do paragraph 1 using the original reward function, rather than what we just gave" or if something else is meant would be helpful. Additionally, as a limitation, it seems like paragraph 2 is saying that some reward function is needed in the original environment, but then in the discussion, it's stated that this isn't the case. Clarifying this would be helpful.

The compute time and resources are given only in the checklist, not the main text, and the section numbers under 4(d)-(e) are incorrect. The open-sourcing of the dataset is listed as a contribution, but then seems to be more of a plan in 4(b) - a specific timeline would be helpful (i.e., will this definitely be open-sourced if accepted?)


Significance:
If this approach does generalize well to other tasks, I think it has the potential to be very significant, and I think the ideas here are ones that others are likely to build on. The lack of clarity in some places and my uncertainty about whether this is likely to work for a variety of assignments may detract from that significance. Assuming that the dataset is released, as it sounds like is planned, this will be a useful dataset for other researchers.



Typos:
- Line 54: "a students assignment" [missing apostrophe]
- Line 99: "the algorithm takes game objects positional and dynamics as input" [missing word or wrong form (?) and missing apostrophe]
- Lines 132-133: "The difficulty of The challenge "
- Line 148: "direct access to transition function and reward function is not possible" [missing "the"]
- Line 203: "highly reliant on how good our model can approximate the system" ["well" rather than "good"]
- Line 237-238: "The problem with this approach is that the policy is biased toward finishing the original objective in the coding game, it might not lead to any bug discovery" [run-on sentence]
- Line 258: "and reward agent for reaching that state."
- Lines 319-320: "we count any unique program submitted more than 10 submissions as the “body” of the distribution." [missing word?]
- Table 1 caption: "Randomly agent result we report average over 5 runs." [missing word(s) or wrong tense?]


Update after author response:
Thank you for your detailed response! I appreciated especially seeing the breakdown with different numbers of buggy examples, as that seems to help with thinking about how this would apply to use in the classroom. In response to your response on creativity, I definitely understand that this is a difficult problem. I think, however, acknowledging in the text as to how this does and doesn't address creativity, given that it seems to play a central role in your motivation for this work, would be helpful; this is linked to my concerns about clearly acknowledging the limitations, which I think would actually make your work likely to have a larger impact, especially in the communities that are most deeply immersed in the challenges of education and working with students. Thank you also for noting how the velocity clipping is similar to an actual bug - perhaps in the paper a quick mention of how this relates to a real bug would be helpful, in case others (like me) are not imaginative enough to consider how this would arise naturally? Thank you again for your engagement with the reviewing process and for sharing your work.
limitations_and_societal_impact: The discussion of potential negative impacts seems quite superficial. The tool as created is trying to assess correctness, and the motivation early on is for teachers to know if programs are correct - the distinction that should be made is about the suitability for high-stakes versus low-stakes assessment. 

There is also a bridge to be crossed which is not addressed which is moving from correctness feedback to guidance on how to improve. It's not clear from the evaluation whether students are likely to be unaware of their mistakes (in Bounce, it sounds like they would be because games can't be played given the bugs), and if they are not likely to be unaware, then it's not clear that the approach is giving more feedback to them then what they get from trying to play their game. To be clear, I think it's okay that this paper doesn't do everything! But, I would have liked to have seen a little more nuance in discussion of actually applying this, and perhaps references to the kinds of papers noted above that do look at the problem of guiding students.
review_title: null

Meta-review: The paper studies the problem of automatically identifying whether the student program for an interactive coding task is correct or not. The proposed method is based on a novel idea of mapping a student program to an MDP and then developing an RL agent that can play in this MDP with the objective of classifying it as correct or incorrect. Experiments are performed on a synthetic task as well as on a programming task from code.org. The reviewers acknowledged the importance of the studied problem and the potential impact in the domain of coding education. The reviewers raised several concerns in their initial reviews. The reviewers appreciated the authors' responses, which helped in answering most of their questions. 

One specific concern that came up is regarding releasing the dataset. The paper lists one of the four contributions as "We will release a dataset of over 700k submissions to support further research." In the checklist, it is mentioned that the data is currently proprietary, making it sound more of a plan without a clear timeline. Given that the reviewers consider this dataset contribution in the reviewing process, a timeline is important. It is expected that the authors already have a plan in place and would open-source the dataset during the conference timeline (e.g., camera-ready deadline) if the paper is accepted.

Overall, the reviewers have a positive assessment of the paper. The reviewers have provided detailed feedback in their reviews, and we strongly encourage the authors to incorporate this feedback when preparing a revised version of the paper.

Decision: Accept (Poster)