Play to Grade: Testing Coding Games as Classifying Markov Decision Process
Authors: Allen Nie
Emma Brunskill
Christopher J Piech
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
computational education
automated testing
LSTM
MDP equivalence

Abstract: Contemporary coding education often presents students with the task of developing programs that have user interaction and complex dynamic systems, such as mouse based games. While pedagogically compelling, there are no contemporary autonomous methods for providing feedback. Notably, interactive programs are impossible to grade by traditional unit tests. 
In this paper we formalize the challenge of providing feedback to interactive programs as a task of classifying Markov Decision Processes (MDPs). Each student's program fully specifies an MDP where the agent needs to operate and decide, under reasonable generalization, if the dynamics and reward model of the input MDP should be categorized as correct or broken. We demonstrate that by designing a cooperative objective between an agent and an autoregressive model, we can use the agent to sample differential trajectories from the input MDP that allows a classifier to determine membership: Play to Grade. Our method enables an automatic feedback system for interactive code assignments. We release a dataset of 711,274 anonymized student submissions to a single assignment with hand-coded bug labels to support future research.

Play to Grade: Testing Coding Games as Classifying Markov Decision Process
Allen Nie Computer Science
Emma Brunskill
Chris Piech Computer Science Stanford University
Computer Science Stanford University
Stanford University
Abstract
Contemporary coding education often presents students with the task of develop- ing programs that have user interaction and complex dynamic systems, such as mouse based games. While pedagogically compelling, there are no contemporary autonomous methods for providing feedback. Notably, interactive programs im- possible to grade by traditional unit tests. In this paper we formalize the challenge of providing feedback to interactive programs sion Processes (MDPs). Each student's ' program fully specifies an MDP where the agent needs to operate and decide, under reasonable generalization, if the dynamics and reward model of the input MDP should be categorized as correct or broken. We demonstrate that by designing a cooperative objective between an agent and an autoregressive model, we can use the agent to sample differential trajectories from the input MDP that allows classifier determine membership: Play Grade. Our method enables an automatic feedback system for interactive code assignments. We release dataset of 11,,274 anonymized student submissions a single assignment with hand-coded bug labels to support future research.
task of classifying Markov Deci-
1 Introduction
The need for high quality education at scale is of critical importance 1. for millions of students is possible, providing feedback cornerstone of education remains an open challenge. The quality of an online education platform depends on the feedback it can provide its students. However contemporary coding education has a clear limitation. Students are able to get automatic feedback only up until they start writing interactive programs. When student authors a program that requires user interuction, e.g. where user interacts with the student's program using mouse (such as game), or by clicking on button (such as in graphical user interface) it becomes exceedingly difficult to grade automatically. Even for well defined challenges, the user has any creative discretion, or the problem involves any randomness, the task of automatically assessing the work daunting. This is especially true as coding has become more popular and feedback is required for many students. One popular intro to programming platform, Code.org has over 61 million enrolled students 22. For their many interactive assignments they have no ability to even identify if a student has working solution.
While delivery of content
Why providing feedback to interactive programs so hard? The standard way to provide feedback is through human labor. Teachers need to interact with each student's program for 20 seconds to 10 minutes in order to grade. This may seem small, but for the quantity of unique programs on platform such Code.org that amounts to approximately 9.5 years of human effort to provide feedback for a single assignment. Code.org has tried crowdsourcing feedback from hundreds of thousands of teachers which has fallen short for similar reasons: labelling is hard and undesirable work 3) Interactive assignments can not be auto graded as running the program requires dynamic
enieesttnfodd.c
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

input. Moreover, heavily scaffolded assignments ones that force students to program their interactive programs in way that enables standard testing are considered to be sub-par learning experience for students and are not common in contemporary classrooms.
There is a long history of work towards providing feedback to students working on open ended assignments which has shown that automatically providing feedback based on code text is a hard machine learning problem 4 5
7 91. This is true for many reasons. Even for introductory level computer science education, homework datasets have statistical distributions with heavy tails similar to natural language [O]. Moreover, these distributions tend be highly discontinuous two solutions which are only slightly different in text can be very different in its behavior. As such, approaches to grading which rely only on reading the text of a students code end up being as complex as understanding passage of natural language [TT]. Finally, because feedback is necessary for the first student working on an assignment, not just the millionth, and new assignments are often introduced, the challenge is inherently few shot.
6
In this work we show that an algorithm that learns to interact with student's assignment, to play with the student work, can enable new capacity for understanding student work. A collaborative system which can simultaneously learn understand what type of behavior is undesirable, as well as play student's work to actively trigger these undesirable behaviors, is the crucial first step to developing automatic and intelligent feedback for massive online coding education.
Our contributions:
We introduce the reinforcement learning challenge of Play to Grade
We propose a collaborative algorithm where an agent simultaneously learns to play a game and recognize what states bug inducing states.
Our solution obtains 49.4%%94.%% accuracy on real-world coding dataset provided by Code.org. We gained a 19-25 percentage point improvement over grading programs via code text.
We release Bounce dataset of student submissions with ground truth bug labels and an OpenAl- Gym compatible environment to support further research: https: play-to-gras grade
com/windweller:
1.1 Related Work
Education feedback The quality of an online education platform depends on the feedback it can provide to its students. Low quality or missing feedback can greatly reduce motivation for students to continue engaging with the exercise 12]. Currently, platforms like Code.org .ode that offers block-based programming use syntactic analysis to construct hints and feedbacks [13. Using recurrent neural networks to understanding programs through code text has also been well-explored. focusing on providing code-level feedbacks or correcting syntactical errors [14 15). Other works generate hints based on writing complicated automatic syntax tree [6 17 which could place heavy burden on teachers and education platforms. The current ofate-of-the-art introduces method for providing coding feedback that works for assignments up to approximately 10 lines of code [10]. The method does not casily generalize longer and more complicated programs. We take inspiration that the underlying code can vary but the correct behaviors should all be the same. Our method sidesteps the complexity of static code analysis and instead focus on analyzing the MDP specified by the game environment. Our work is complementary to these methods because we provide a new tool of analysis for understanding a program's behavior and providing feedback beyond static text analysis.
Reinforcement learning for software testing Designing automated test for software has been well-explored by using template-basse test case generation (18) and input fuzzing [99 Recently, there have been a lot of interests in using RL agents to find bugs in games, The most prevalent solution an agent that heavily focuses on exploring new states (20) 21 22 23 Such agent optimizes an objective such as discretely counting the number of states the agent can reach 24 or use curiosity objective to encourage visiting new states 225 26). They all rely on the strong assumption that once a bug state is reached, we will be able to know that the state is a bug. We show that exploration (or reaching the bug state) is only half of the challenge. However, is possible that these pure-exploration agents or input fuzzing can provide additional diverse trajectories to further optimize the bug classifier. The idea of pairing a RI. agent with a predictive model also explored in safe RL, such as predicting
whether state is unsafe [27 28 and training agents to seek out unsafe states 22 30).

---

2
The Play to Grade Challenge
In this section we are going to introduce a novel challenge for the machine learning community: how can an algorithm learn how to "play" with a student submission in order to understand the ways in which it might be buggy? The challenge applies to the task of giving feedback for any interactive student work. In this paper we will focus games typical of introduction to programming courses.
We formulate the challenge with constraints that are often found in the real world. Given an interactive coding assignment, a teacher often has a few solution implementations of the assignment. We also assume that the teacher can prepare a few incorrect implementations that represent their "best guesses" of what a wrong program should look like. This sets up few shot challenge where an algorithm must learn to generalize from the few teacher examples, to the cons-of-thousane (or more) unlabeled combinations of mistakes and invariances found in natural student code.
Definition 2.1. deterministic Markov Decision Process (MDP) a 4-uupee M = A,T. R>, where& S is set of states; A is a set of actions; T : S x A - S is the transition dynamics; and R: S x A - IR is the reward function.
We can consider each student implementation of the interactive assignment as a separate MDP. Shared structures between these MDPs can be leveraged to train a grading algorithm. The first assumption that we take is that all MDPs share the same action space A. This is not difficult requirement to satisfy because specifying how game should be played often part of the instruction for the homework. The second assumption is that all MDPs in this set share the same state space S. This can be satisfied in two ways: 1) If the algorithm takes game objects' positions and dynamics as input, we can design the state space to include much information possible (i.e., grab all objects on the canvas); 2) If the algorithm takes screenshots/images of game play, then the state space is trivially the same, up to scaling factor.
To formalize this setting, we consider a training dataset, D, of programs, each fully specifies 1, 1,2,3...., where Un E {0. 1} is a binary label for the MDP M,,, and a set of programs similarly specified to be tested in Deest- We note that n is often a small number, usually less than 20, significantly fewer than other supervised learning tasks. y = 0 means the game has no bug, and y = 1 means the game has at least one bug. The training objective is to correctly assign label Un for each Mn. The play-to-grade challenge is to show that a system trained on this few-shot training data can be generalized to accurately identify bugs for all students in the class. Though our work focuses on the binary bug labeling, our proposed algorithms are not inherently limited by this. We leave multi-class bug labeling (i.e., which bug is discovered in the MDP) for future work and note they can provide even larger impacts on generating fine-gratd fineggrained feedbacks to student assignments.
an environment and its dynamics: D {[M,, = (S, A. Tn, RR), Un)
2.1 Equivalence Relations in MDP
The study of equivalence relations in MDPs and labelled transition systems has long history. Previous works focus on determining equivalence relations of states in order to condense state representations for easier policy learning B2 33
34 335. The general notion is that if two states are equivalent, they should receive similar reward and lead to a similar next state. Therefore, a distance measure d can be defined to judge whether two states are equivalent.
To solve the play to grade challenge, instead of considering whether two states are equivalent, we can try to determine whether the two MDPs are the same. If the reference MDP has reward function R and transition function T, we only need to know if T and R from the new MDP are the same as the reference MDP. Unfortunately, since we cannot directly compare the parametrized functional forms, we extend the distance metric developed by 33 from state equivalence relations to MDP equivalence relations by sum over all state in Eq We can use any norm to measure distance of next state for continuous state space, and use an indicator function if the state is discrete. We can use and 3 to decide how much we weigh the difference between MDPs.
M) = Σ max R(s, a) - R(s, a)) + (I)T(s T(s, S
(1)
However, we will not be able to compute D(M, M) exactly for non-tabular MDPs because we cannot efficiently enumerate over all possible states. Our goal is to find some kind of difference between the two MDPs so that we can confidently reject the notion that the given MDP M is the same as
3

---

reference MDP M. Therefore, instead of calculating the difference between the two MDPs over all states, we only need subset of states where the difference is the most significant. As long as we can discover a subset of states, or even one state where significant difference occurred, we can decide that two MDPs are not the same. We call these states the differential states. The difficulty of The challenge is determined by the cardinality of the differential states.
2.2 Play to Grade Objective
The objective is to reach differential states so that we can confidently determine if the student solution is sufficiently different from a reference MDP: ((M, M) > where is chosen by the teacher, and can be thought of as some fault tolerance level. Because (MM, M) is summation over norms, identifying some or any differential states would trivially satisfy this objective. We can rewrite this existential search objective as an optimization instead. We can define new MDP where the reward function is the difference on (s, a), and the rest are the same as M. We can obtain policy that learns to maximize this reward, which is equivalent to searching for differential states by sampling differential trajectories between two MDPs:
d(s, a) al R(s,s) R(s, (1) a) a(s.
π arg max R. (o,a)~ (d((s) > >6]
Now that have clear optimization objective that we can solve it using any reinforcement learning algorithm, we must consider another difficulty. Even though the MDP framework provides a simple abstraction to the problem we face, we do not have real access to the underlying reward and transition function. Given a state s from M and action from T (s). we are unable to directly query the reference MDP M for T's a) and R(s, a). This is because we are in an episodic setting, where the direct access to transition function and reward function is not possible. Also, we generally assume that each episode will have random initial state different downward direction each time you play). This randomness is defined internally and does not allow for outside control (such as seeding). This means we can't simply use one policy и to sample two trajectories from both MDPs and directly compare the reward and the next state.
p(so) (i.e., in breakout, the ball gets launched
3 Recognizing Bugs
The main challenge of solving this task is: if we know what differential states look like (i.c., have a good state distance function d(s,, a)). can directly train agent reach these states; conversely, we have a good agent that can reliably reach these differential states all the time, we can find a good d(s, a). The fact that we have neither, is the cold-start problem of this challenge.
We will address the cold-start problem in the next section, but first, if we assume that we do have a good policy that can generate differential trajectories, how should we parametrize and learn distance function d((s, a) that recognizes (s, a) does not belong the reference MDP? We introduce a few basclines and propose two methods that have a good inductive bias to recognize differential states.
3.1 Baseline: Noisy Supervised Learning
good distance function can be learned with noisy supervised learning. Since we have a small set of labelled MDPs (i.e., (M, y 0). (M, y = 1)) in our training dataset D, we can label all state-action tuples sampled from the correct MDP as no-bug, and all state-action tuples from the incorrect MDP as bug. and train supervised classifier. We define the state classification function that use to label state-action tpllss as o : S x A S + {0, 1}. @(5, a, 3') = if (3, a, 3') are sampled by evaluating т on M, otherwise they are sampled from MM.
3.2 Baseline: Unsupervised Learning
Another baseline idea to learn the distribution of (s, a) sampled from M. We can train a generative
model on (s, a,s') triples collected from (M,y 0). The model can optimize to approximate a joint
distribution (s,,, a, 8'). We compare a Gaussian mixture model and a variational autoencoder (36)
as our generative model of choice. We turn our generative model into classification function, using
the same é from Section 3.1: d(3, ā, 3') & po(5, ā, 5') a. For both bascline algorithms, we can

---

assign a label to the new MDP M by computing D(M, M) = E (aa))m,,lllsa T(s, a))] and set decision threshold (M,, M) 2 v.
3.3 HSareLSTM
Since the policy samples sequential observations from an MDP, natural to calculate distance as a form of unexpectedness between predicted state and observed state. In fact, the programming language community has been looking into triple of pre/post-condition along with an action input for long time. These are called Hoare triples [37]. They have also been extended to measure state equivalence in MDP 38 Previous work computational education has used them learn program embeddings for generating feedbacks [1].
We approximate the distance function d(ss, a) in Eq 2 by learning transition and reward model. Unlike model-based reinforcement learning [39]. where an accurate model of transition model T and reward function R must be learned for policy optimization, we only need to optimize the models to the extent that we can confidently make decisions about M label.
As explained before, we only have access to either (T, R) (T: R). but not both. We can learn predictive model (s s, a) and (s(s, a) for the reference MDP's (I, R). We note that the model does not need to be autoregressive, but we choose to parametrize them as autoregressive long- sho-ttort-term memory (LSTM) network [40]. We choose and g to be fully connected neural networks with separate parameters. Since are predicting Hoare triples, we call this the HoareLSTM model.
h1 L o2, 1(-1)
(4)
8+41 f(h)): = (ha))
(5)
((0) (s (Ife R(s, a)l + || - T(ss, a)ll
(6)
If we learn Ta and Rg approximate T and R from the reference MDP M, can compute state- action tuple distance function from AM to M, given any MDP M. We denote this approximate distance function du that takes T and R input:
as, R) = alA: R(s, B11 a(s
M) = ((,,a)=n, M [d)r(s.a)]
(8)
We use D(M, M) to compute the difference between the predicted trajectory by approximating T and R from MDP M and observed trajectory by actually sampling from T and Rt At last, we can determine if M is the same M by checking if D M) 2
3.4 Contrastive HoareLSTM
The distance we calculate is highly reliant on how well our model can approximate the system dynamics of state evolution. However, our model has inherent approximation error. We present the idea of a contrastive distance to potentially mitigate this error.
Instead of learning to approximate one reference MDP's (T, R2), we can learn to approximate correct MDP M+ with (T+, R+), and a bug MDP M with (T= Given a new test MDP's (T, R), we can perform a contrastive comparison to determine the distance function dast,
dss .MM (s,a; R) =a R(s, a) Rt (s. a)) - -, (s) 3|T(s, - (s, () a) 2 (s. a)ll
(9)
(10)
We still use policy π to sample (s, a) from the new input MDP M, but instead of directly comparing it with one MDP M, now comparing it with two MDPs M and M and see which transition and reward model better predicts the behavior of the new input MDP.
The main advantage of using difference comparison is that we are likely to be more fault tolerant. If we look at how we decide if MDP has bug: D(M, M) > the choice of needs to reflect our approximation error when we try to learn T and R so that we are not classifying an correct MDP as bug MDP if our model is not able to recreate the transition dynamics accurately. If we approximate both (T, R)) and (T. R) and use the same family of models with similar parameter size,
5

---

the approximation errors could cancel out in the contrastive setting, The disadvantage is that now we need train two models, and the distance can be influenced by how well each model is optimized.
Algorithm 1: Collaborative Reinforcement
[M y=
Learning
PRAINDITTERENTALPPLOYY
8 M
(M, M, M,T,, do)
6 0.1
M
for π + N do
D, = CollectTraaectory (M, M, To)
D M. An)
d3 = TrainDisstFunc((()), D,)
8 AdjustDeetaaM,,aee M,, mo, 5, do)
Let r* 1100111000 as) > 6)
M x=1)
n. TrainDQN ( (To M,r r*)
end
Grading interactive coding assign- ments as pairwise distance comparisons be- tween few-shot reference MDPs.
Figure 1:
return NN, d
Collaborative Training
With parametrized approximate distance function d(ss a) and an agent π that learns maximize this distance function as reward, the solution seems complete. However, neither the distance function nor the agent can work well in the beginning. Agent randomly on the states, and the distance function can't capture any difference between states. This is the cold-start problem: we need to simultaneously learn to play the game and find bugs. We present some standard agents and leave more detailed investigations to future work.
4.1 Initial Agent: Random or Play-to-Win
One solution is start with an agent that acts randomly. This strategy is particularly useful if the state space can be easily explored. By sampling random trajectories, we might be able to quickly train a good distance function. The drawback is the inefficiency and the fact that a random agent will struggle with games that have hard-to-reach states.
Another solution is to train policy maximize the original reward (i.e., play to win). If the reference MDP has clearly defined reward function that gives reward, we can train a policy ı that simply learns to maximize the episodic total reward. This is very useful pre-training to hot-start the policy, especially important in games with long horizon in which it is easy to fail.
The problem with this approach is that the policy is biased toward finishing the original objective in the coding game. If the bug states can only be reached by losing the game, it will not lead to any bug discovery. Another problem is that some coding games do not have clearly defined reward. In that situation, we can use curiosity based objective [21]. But as we will show in the experiment section, play-to-win policy is often good enough sampling sufficient differential trajectories to train good distance function.
4.2 Improved Agent Using Iterative Training
With the initial agent, we can start to collect trajectories that we can use to train the underlying parameters of our distance function. If our parametrized distance function is a discriminative model (i.e., noisy supervised learning), the optimality of the agent will have an impact on the quality of state level pseudo labeling. We can see in Section 5.1.1 and Section (.1.2) noisy supervised learning can do quite well as long as the agent can reliably reach the bug states. If our distance function is a generative model that estimates the joint distribution of the observed data, how the agent collects trajectories does not affect the learning of the model. However, we still need to set a threshold to determine if (s, a) is bug-inducing state not, indicated in Equation
Empirically, for our environments, we find that do not need to more than iteration of collaborative training. Therefore, we are able to adjust 8 at the end of each iteration manually by looking at the distance-to-selff (M,, M)- - if we take (s, a) from the reference MDP and use to calculate the difference to itself, we can choose 8 so that all (s, a) can be labeled as correct. We leave the exploration of how to automatically adjust ó to future work and more complicated environments.

---

Car-Easy
Car HardHard
Rounce
Rounce-Rune Rug: Maltipe Balk When Ren
Rounce-Rug Bui Bronces On Gatt
Figure 2: We show the illustration of the car environment and two settings on the left, and bounce environment and its two incorrect implementations on the right. For the car environment, bug states are indicated by the dotted red lines and the error signs inside. Note that the correct car environment only has the car and the gold star, without any dotted line or error sign.
5
Experimental Results
5.1 Car Environment
We use toy example to explore some basic aspects about the play-to-grade challenge. this toy example, we continue our intuition that the goal is to reach and identify the bug-triggering state. build 2D environment where the agent needs to drive a car to reach a gold state, and potential bug states are defined as specific coordinates this 2D field. All states are easily accessible by the agent. This is the most generalized and simplest representation the play-to-grade challenge. We can use this toy environment to help understand some fundamental challenges in play-to-gra grade and understand the properties of collaborative training.
In all car environments, the agent can finish the game by reaching the gold star. When bug- bug-state is reached, the car's physical movement altered, resulting back-and-ford movement around the same location reflecting the idea that the car is "stuck".
5.1.1 Bug Classification
We define a Car environment setting: Car-Easy, where almost all agents can easily reach the bug state regardless of whether they adopt the collaborative training objective not (unless this agent is adversarial). The objective of this setting is to test how well bug classifiers perform with an optimal agent. Although most agents be optimal, they not equivalent in the eye of the bug classifiers, because the trajectories these agents collect will differ quite significantly. We test two agents, one that only drives straight line the gold star state (the single-direction agent); the other drives randomly (the random agent). The trajectory generated by a random policy is much harder to learn to predict and memorize compared single direction policy.
In Table D all models including baseline models are able to predict bug states with high precision in single direction agent setting. However, only our proposed methods: HoareLSTM and Contrastive HoareL.TTH are able to learn well by predicting next states in an autoregressive manner. We report the model specification and optimization details in appendix.
5.1.2 Collaborative Training Improvement
Most of the time, we will not have an optimal agent that can always reach a bug state in every trajectory. Therefore, is important for us to test bug states that are sparse and slightly harder to reach. We devise the plane. This creates situation where the agent only encounters bug states if the agent plays into the bug state. We use this to show that letting the classifier and the agent train iteratively can improve the performance of both classifier and agent. In Table we show that by applying collaborative training (CT), we allow the agent to become much better at reaching bug states, and in return, allow us to train a much stronger bug classifier even after one iteration. We argue that CT necessary when bug states are far away from the goal and that is the reason why recall is increased on most models after CT.
setting where bugs only appear in small rectangular regions of the 2D
5.2 Bounce
Data source Code.org an online computer science education platform that teaches K-12 students beginner programming using drag-and-drop interface. Our dataset is compiled of 453,211 students
7

---

Single Direction Agent
Random Agent
Accuracy
Precision
Recall
Accuracy
Precision
Recall
Baselines
Noisy Supervised Learning
91.0 1 4.7
90.3 1 5.1
98.6 1 1.8
60.3 11.8
48.0 14.8
84.6 1 17.8
Gaussian Mixture Model
25.3 12.5
60.6 26.0
23.8 15.7
17.0 10.6
18.0 11.0
7.3
Variational Autocncoder
83.8 + 4.4
84.9 + 5.0
95.7 = 1.1
69.5 6.4
51.6 = 10.9
86.0 = 8.5
Our methods
HoareLSTM
99.3 + 1.9
99.0 + 2.7
100.0 + 0.0
98.5 + 1.1
99.6 + 1.0
91.1 + 6.0 86.0 + 5.2
Contrastive HoareLSTM
100.0 0.0
100.0 + 0.0
100.0 = 0.0
94.5 1.8
94.4 + 2.8
Table Bug-state level result of the Car-Easy environment. We report the result of both agents over 5 runs. For non-sequential models, we stack the previous 4 states with the current state. We measure the accuracy of correctly classifying bug or non-bug states. Recall and precision are measured only for bug states. We report 95% confidence interval.
Random Agent Prec
CT
Iteration Prec
CT
Iteration 2
Acc
Rec
Acc
Rec
Acc
Prec
Rec
Baselines
Noisy Supervised Learning
46.8
12.6
37.2
67.4
53.6
94.0
67.7
47.7
82.6
Gaussian Mixture Model
8.4
3,4
2.1
11.8
8.3
2.9
12.3
0.0
0.0
Variational Autoencoder
63.8
32.0
96.4
66.5
53.0
95.6
77.8
74.8
96.7
Our methods
HoareLSTM
99.2
76.5
80.0
100.0
100.0
100.0
99.3
99.0
100.0
Contrastive HoareLSTM
98.4
93.9
87.1
97.2
99.7
94.9
97.9
99.9
96.6
Table 2: Bug-state level result of the Car-Hard environment. We show how collaborative iterative training can help classifiers get higher performance. We also average over runs. We measure the accuracy of correctly classifying bug or non-bug states. Recall and precision are measured only for bug states.
who wrote solution to the Bounce assignment. In total, there 711,274 submissions, where 111,773 unique programs were submitted. Since the data are student programs, there no personally identifiable information in dataset. All programs have been manually labeled with the set of bugs they contain. We provide a data risk statement in Section A.5
Code.org students use drag-and and--ndd-dd drop style code editor to program the game of Bounce, single player version of Pong where a player tries to bounce a ball into a goal using a paddle. Students program if/then relationships such as "when run", "launch ball". The "launch ball" command shoots a ball in a random direction and the randomization is not editable by the agent. There is no limit on how many commands can be used, allowing freedom to, for example, add five "Launch new ball" under one condition. Two example bugs are visualized in Figure 2 Bounce was intentionally chosen as it was difficult for an agent autonomously grade based on playing, but easy for human annotators to provide gold-standard bug-labels based on looking at the source code.
Assignment detail
Evaluation In an unbounded solution space, the distribution of student submissions incur heavy tail, observed by [TO] We show that the distribution of submissions in dataset conforms Zipf distribution Figure A.3bl This suggests that we can partition this dataset into two sections. Body: we count any unique program submitted by more than 10 students as the "body" of the distribution. accounts for 80.0% (565,714) of the total submissions. This set contains 500 unique correct programs and 2,690 unique incorrect programs. Tail: This set represents any programs that are submitted less than 10 times. This set contains 101,986 unique incorrect and 6,597 unique correct solutions. For both Body and Tail distribution, we sample 250 correct and 250 incorrect programs uniformly from each set for evaluation.

---

Correct Program Precision
Broken Program
Accuracy
Recall
Precision
Recall
Body Student Programs (566K submissions, 3,190 unique)
Majority Class
50.0
Code-as-text
74.2
84.6
59.2
68.6
89.2
Contrastive HoareLSTM + PTW
93.4
88.6
99.6
99.5
87.2
Tail Student Programs (146K submissions, 108,583 unique)
Majority Class
50.0
Code-as as- aede-t
68.4
85.9
44.0
62.4
92.8
Contrastive HoareLSTM PTW
94.0
91.0
97.6
97.4
90.4
Table 3: We report the pre-trained "play-to-win" (PTW) agent's ' performance when predicting if program has a bug with different methods of bug identification. For both body and tail distribution, we sample 250 correct and 250 broken programs for balanced evaluation.
Analysis We evaluate our algorithm's ' ability to find bugs in student Bounce programs. Unlike the Car environment, Bounce has most bug states close to the goal state; for example, if the wall or paddle does not bounce the ball, game cannot complete. Therefore, we focus on evaluating our bug prediction. We train our prediction
10 incorrect programs and correct program. We report the result Contrastive HoareLSTM trained with trajectories sampled by a pre-trained play-to-win to-win agent Bounce. The final grading label is determined by a majority vote with 10 contrastive distance functions. Table 3 shows that we are able to achieve high accuracy (93.4-94.0% 4%)% relative to the code-as-text baseline on the binary classification of student assignment. This shows the potential of play-to-grade algorithms in assisting in real-world classrooms.
Discussion
Providing helpful feedback Our current formulation of "identifying bug state" holds tremendous educational utility. For beginner programmers, it is important for them to where the program went wrong and try to develop a solution by themselves. By identifying a bug state, we can record a 2-3 seconds short video around the bug state and display students where their program made mistake. We plan to collaborate with Code.org to deploy our trained algorithm in a real production environment, but this live experiment is beyond the scope of our technical paper.
What if game internal states can't be retrieved? There are many situations where the internal object representations (such as velocity, position) can't 't be accessed easily from outside; in this case, often all the information we have would be the image snapshots of the game state. It is that the iterative learning paradigm we proposed would be more compute intensive, but the model components we explored in this paper are capable of learning and operating on pixels
Does this work for non-game programming assignments? Many interactive student assignments might not be "game" and the reward might not be clearly defined. However, since algorithm does not rely on the internal reward of the game we only rely on the classifier to discover differential trajectories between correct and incorrect programs, our solution should generalize to other types of programming assignments that require interactive user inputs such as web apps.
Creativity as distance Often times, students create solutions that are creative. Understanding and rewarding creativity is the major challenge in AI for education. Though we didn't 't use the Bounce dataset to focus on the problem of understanding creativity, our work opens up interesting angle to address this very hard challenge. In this work we identified several unique approaches that we believe will be useful in recognizing creativity. The idea of play-to-grade could help to identify the difference between a truly broken solution and one which is playable, but different from the reference solution. Or perhaps we could think of creativity as being related to the delta (distance to the correct solution). We imagine that this line of research will be very exciting future work for both the fields of education and reinforcement learning.

---

Future work We see several promising directions to extend this work. First, given that Bounce dataset includes multi-class bug labels, turning the binary classification into multi-class multi-label classification would bring some new exciting challenges to our framework. Second, as shown in Table iterative training is not always monotonically improving the performance of the algorithm. Exploring the properties of iterative training is left for future work.
7
Conclusion
Providing generalizable algorithm that can play interactive student programs in order to give feedback is an important problem for education and an exciting intellectual challenge for the rein- forcement learning community. In this work, we introduce the challenge and dataset, set up the MDP distance framework, provide algorithms that achieve high accuracy, and demonstrate this is a promising direction of applying machine learning to assist education.
Acknowledgement
This work was supported in part by Stanford Hoffman- Yee Human Centered AI grant. We would like to thank code.org, and Baker Franke, for generously providing the research community with data. We additionally thank Lisa Yan, Tong Mu, Mike Wu, Yunsung Kim, Ali Malik, Moussa Doumbouya, Henry Zhu for feedback on this project.
References
[1] William G Bowen. The "cost disease' 'n higher education: is technology the answer? The Tanner Lectures Stanford University, 2012.
[2] Code.org about page: https://code.orr/abbuu
[3] crowd-sourcing hints project for code.org: https:/ccode.orghhint..
[4] Chris Piech, Jonathan Bassen, Jonathan Huang, Surya Ganguli, Mehran Sahami, Leonidas J Guibas, and Jascha Sohl-Dickstein, Deep knowledge tracing. Advances in neural information processing systems, pages 505-513, 2015.
[5] Sumit Basu, Chuck Jacobs, and Lucy Vanderwende. Powergrading: a clustering approach to am- plify human effort for short answer grading. Transactions of the Association for Computational Linguistics, 1:391-402, 2013.
[6] Lisa Yan, Nick McKeown, and Chris Piech. The pyramidsnapshot challenge: Understanding student process from visual output of programs. Proceedings of the 50th ACM Technical Symposium on Computer Science Education, SIGCSE '19, pages 119-125, New York, NY, USA, 2019. ACM.
[7] Lisa Wang, Angela Sy, Larry Liu, and Chris Piech. Learning represent student knowledge on programming exercises using deep learning. In EDM, 2017.
[8] Jiawei Liu, Yang Xu, and Lingzhe Zhao. Automated essay scoring based two-stage learning. arXiv preprint
2019.
[9] Qian Hu and Huzefa Rangwala. Reliable deep grade prediction with uncertainty estimation. arXiv preprint arXiv:1902.102153 2019.
[10] Mike Wu, Milan Mosse, Noah Goodman, and Chris Piech. Zero shot learning for code education: Rubric sampling with deep learning inference. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 782-790, 2019.
[11] Ali Malik, Mike Wu, Vrinda Vasavada, Jinpeng Song, Madison Coots, John Mitchell, Noah Goodman, and Chris Piech. Generative grading: Near human-level accuracy for automated feedback richly structured problems. Educational Data Mining, 2.21.
10

---

[12] Eleanor O'Rourke, Christy Ballweber, and Zoran Popovií. Hint systems may negatively impact performance in educational games. In Proceedings of the first ACM conference on Learning scale conference, pages 51-60) 2014.
[13] Thomas W Price and Tiffany Barnes. Position paper: Block-based programming should offer intelligent support for learners. In 2017 IEEE Blocks and Beyond Workshop (B&B), pages 65-68. IEFE, 2017.
[14] Chris Piech, Jonathan Huang, Andy Nguyen, Mike Phulsuksombati, Mehran Sahami, and Leonidas Guibas. Learning program embeddings propagate feedback student code. In International conference on machine Learning, pages 1093-1102. PMLR, 2015.
[15] Sahil Bhatia and Rishabh Singh. Automated correction for syntax errors in programming assignments using recurrent neural networks. arXiv preprint arXiv:1603.06129, 2016.
[16] Kelly Rivers and Kenneth R Koedinger. 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, 2017.
[17] Benjamin PaaBen, Barbara Hammer, Thomas William Price, Tiffany Barnes, Sebastian Gross, and Niels Pinkwart. The continuous hint factory- hints vast and sparsely populated edit distance spaces, arXiv preprini arXiv: 06564, 2017.
[18] Cuixiong Hu and lulian Neamtiu, Automating gui testing for android applications. In Pro- ceedings of the 6th International Workshop on Automation of Software Test, pages 77-83, 2011.
[19] Cornelius Aschermann, Sergej Schumilo, Ali Abbasi, and Thorsten Holz. Ijon: Exploring deep state spaces via fuzzing. In 2020 IEEE Symposium on Security and Privacy (SP), pages 1692-1612. IEEE, 2020.
[20] Shakir Mohamed and Danilo Jimenez Rezende. Variational information maximisation for intrinsically motivated reinforcement learning. arXiv preprint arXiv:1509.08731, 2015.
[21] Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International conference on machine learning, pages 2778- 2787. PMLR, 2017.
[22] Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. arXiv preprint arXiv:1802.060% 2018.
[23] Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: a new approach for eand-exploration problems. arXiv preprint arXiv: /901. 10995, 2019.
[24] Yan Zheng, Xiaofei Xie, Ting Su, Lei Ma, Jianye Hao, Zhaopeng Meng, Yang Liu, Ruimin Shen, Yingfeng Chen, and Changjie Fan. Wuji: Automatic online combat game testing using evolutionary deep reinforcement learning. In 2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 772-784. IEEE, 2019.
[25] Zeping Zhan, Batu Aytemiz, and Adam M Smith. Taking the scenic route: Automatic exploration for videogames. arXiv preprint arXiv:1812.033 2018.
[26] Camilo Gordillo, Joakim Bergdahl, Konrad Tollmar, and Linus Gisslén. Improving playtesting coverage via curiosity driven reinforcement learning agents. arXiv preprint arXiv:2103.13 13798. 2021.
[27] William Saunders, Girish Sastry, Andreas Stuhlmueller, and Owain Evans. Trial without error: Towards safe reinforcement learning via human intervention. arXiv preprint arXiv: /ixv:1777...0 7007.50 1000005573. 2017.
[28] Jonathan Uesato, Ananya Kumar, Csaba Szepesvari, Tom Erez, Avraham Ruderman, Keith Anderson, Nicolas Heess, Pushmeet Kohli, et al. Rigorous agent evaluation: An adversarial approach to uncover catastrophic failures. arXiv preprint
2018. 2018.
11

---

[29] Bharat Prakash, Mohit Khatwani, Nicholas Waytowich, and Tinoosh Mohsenin. Improving safety in reinforcement learning using model-based architectures and human intervention. In The Thirty-Second International Flairs Conference, 2019.
[30] Siddharth Reddy, Anca Dragan, Sergey Levine, Shane Legg, and Jan Leike. Learning human objectives by evaluating hypothetical behavior. In International Conference on Machine Learning, pages 8020-8029. PMLR, 2020.
[31] Balaraman Ravindran and Andrew G Barto. Symmetries and model minimization in markov decision processes, 2001.
[32] Robert Givan, Thomas Dean, and Matthew Greig, Equivalence notions and model minimization in markov decision processes. Artificial Intelligence, 147(1-2):163-222 2003.
[33] Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite markov decision processes, In UAI, volume pages 162-169, 2004.
[34] Lihong Li, Thomas J Walsh, and Michael L Littman. Towards unified theory of state abstraction for mdps. ISAIM, 4:5, 2006.
[35] Elise van der Pol, Thomas Kipf, Frans A Oliehoek, and Max Welling, Plannable approximations mdp homomorphisms: Equivariance under actions. arXiv preprint 1rXiv:2002.1166: 2020.
[36] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint 1rXiv:1312.6114, 14, 2013.
[37] Charles Antony Richard Hoare. An axiomatic basis for computer programming. Communica- the tions the ACM, 12(10):576-580 1969.
[38] Pablo Samuel Castro, Prakash Panangaden, and Doina Precup. Equivalence relations in fully and partially observable markov decision processes. In Twenty-Firs International Joint Conference on Artificial Intelligence, 2009.
[39] Leslie Pack Kaelbling, Michael L Littman, and Andrew W Moore. Reinforcement learning: A survey. Journal of artificial intelligence research, 4:237-285, 1996.
[40] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 1735 1997.
[41] Aaron Van Oord, Nal Kalchbrenner, and Koray Kavukcuoglu. Pixel recurrent neural networks.
In International Conference on Machine Learning, pages 1747-1756. PMLR, 2016.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] in Discussion.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We discussed this in Section 7. In short, we intend our algorithm to provide formative feed- back, not used for standardized testing assessment. The societal benefit of developing this technology far outweighs the harm at this point.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes].
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you experiments...
12

---

(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes] In supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? (Ye]] In supplementary material.
(c) Did you report error bars (c.g., with respect to the random seed after running ex- periments multiple times)? [Yes] We reported error bars in main paper and/or in supplementary materials.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Experiments are run on one Nvidia RTX 3070 GPU. The training takes less than 30 minutes and evaluation takes less than 5 hours for our sampled set of programs.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [No] The data currently proprietary, though we do have plan to open-source it.
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] See Section 6.3 Data source.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] See Section 6.3 Data source.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "pgXocNY9aKp", "reviewer": "Reviewer_CvhS", "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).", "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": "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.\n\n\n1.  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. \n\n\n2. 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. \n\n\n3. 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. \n\n\n4. 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?\n\n\n5. It would be great if additional details and analyses of the proposed method are available. For example:\n- 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?\n- 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? \n- 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.\n- 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.\n\n\n6. 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.\n\n\n7. There are a number of typos:\n- line 35: \"for a 20 seconds\"\n- line 54: \"with a students assignment\"\n- line 106: \"fewer from\"\n- line 154: \"solving is task is\"\n- line 184: \"they are also been extended\"\n- line 196: \"if we learn to\"\n- line 224: \"sample MDPs effective\"\n- line 238: run-on sentence \n- 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? \n\n\n\n=========\npost rebuttal:\nHaving 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See review above.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "iy20gIFkvM", "reviewer": "Reviewer_TaJm", "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.\n\nThe 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).\n\nThe resource contribution of a dataset is also appreciated.", "questions": "", "limitations": "", "rating": 8, "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 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.*\n\n* 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). \n\nThe 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\nThe 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_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "h9h_GxtzO3G", "reviewer": "Reviewer_JNms", "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.\n", "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": "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.\n\nOriginality: \nWhile 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.:\n- 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.\n- 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).\n\n\nQuality: \nThe 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).\n\nMy 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. \n\nIn 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.\n\nFor 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.\n\nFinally, 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.\n\n\nClarity: \nThere 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).\n\nThere 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). \n\nIn 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.\n\nThe 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?)\n\n\nSignificance:\nIf 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.\n\n\n\nTypos:\n- Line 54: \"a students assignment\" [missing apostrophe]\n- Line 99: \"the algorithm takes game objects positional and dynamics as input\" [missing word or wrong form (?) and missing apostrophe]\n- Lines 132-133: \"The difficulty of The challenge \"\n- Line 148: \"direct access to transition function and reward function is not possible\" [missing \"the\"]\n- Line 203: \"highly reliant on how good our model can approximate the system\" [\"well\" rather than \"good\"]\n- 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]\n- Line 258: \"and reward agent for reaching that state.\"\n- Lines 319-320: \"we count any unique program submitted more than 10 submissions as the “body” of the distribution.\" [missing word?]\n- Table 1 caption: \"Randomly agent result we report average over 5 runs.\" [missing word(s) or wrong tense?]\n\n\nUpdate after author response:\nThank 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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. \n\nThere 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. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "roughly 4 hours, although I did not track closely"}, "extra_text": {"ethical_concerns": "I would love to see more attention to whether terms of service like those cited are really equivalent to informed consent, but the research seems to be following standard practice. I am not sure from the documents whether anonymization happens before the researchers ever have access to it (rendering it non-human-subjects) - i.e., stripping of any PII - or if an IRB approved the study as exempt.\n"}}]

Author rebuttal:

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)