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
PRAINDITTERENTILPPLOYY
8 M
(M, M, M,T0, 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* 11 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 Buil 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 can 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": "jwvJE2HgAf9", "reviewer": "Reviewer_Z8Zo", "summary": "This paper introduces a novel problem and a set of possible solutions for the automated grading of interactive programs (i.e. programming assignments where some interaction with the program is needed to evaluate whether it performs the right tasks). The problem is modeled as a Markov decision process (MDP) and several modelings of the overall problem are considered (for example learning from a set of positive and negative example MDPs). A main model is to setup a new MDP in which the reward function reflects the difference (in terms of rewards and transitions) between the model solution and the students solution MDP. A challenge is to actually flag the \"bug\" states, in which the reward/transition deviates \"too much\", for which a classifier can be learned in addition. An overall solution is an iterative algorithm (collaborative RL) in which both steps are combined. The approach is tested on a small toy problem, and a large real-world dataset from code.org.", "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": "I have mixed feelings about this paper, although leaning to a slightly positive evaluation. I really like the setting, and the general MDP-based approach. I think the general storyline of the paper makes a lot of sense (algorithmically) and the overall motivation and application are very nice and interesting. I think methods such as these will be needed for a lot of online/MOOC-like educational settings. However, I think the paper itself is not clear in all places yet, it sometimes feels a bit preliminary in terms of choices and methods, and there are sloppy things throughout the paper (many small grammar errors, missing words, typos; the paper needs polishing). A main downside is that the paper seems very process-oriented, and it would have been better to describe the final model as it is, even though some of the build-up is useful. The experimental evaluation seems convincing in terms of the performance of the methods, but it is hard to really evaluate, also because the description of the setting, domains and how they are modeled are not adequate. Even the extra material only consists of code (Python notebooks) and no further description. I am not sure whether everything is repairable in reasonable time. I will elaborate below, Section-wise.\n\n- The abstract and introduction section are done well. However, the related work section is inadequate and short. I would at least expect a couple of distinct lines: i) software testing with reinforcement learning, ii) RL and verification. iii) RL and behavior classification (i.e. MDP classification) and maybe some more about iv) educational settings. Small error here: complimentary -> complementary.\n\n- Reference [3]: what is meant here?\n\n- Section 2 is mostly clear, but quite process-oriented (in terms of building up the story) and it could have been introduced more in terms of stating the model immediately. I am not sure why Def.2.1. needs to be deterministic, since later in the paper, typically in the distance calculations, T(s,a)-\\tilde{T}(s,a) is used. Depending on the type of state representations (and/or stochasticity in the used domains) continuous states might fit better, but overall this is sometimes confusing. \nIn addition to [16-19] there is seminal work by Givan, and by Boutilier, early 2000s, on model minimization and stochastic bisimulations that is good to mention (or use). \nNot sure why already here it is mentioned that \"non-tabular MDPs\" and \"cannot... enumerate\" since at this point in the paper, everything IS table-based still and discrete. Later this may be different when approximation architectures are used, but for the story here it is unimportant.\nThe model in Section 2.2. is conceptually nice.\n\n- Section 3 starts with a cold start problem, but it is more like a chicken-and-egg problem, or something that is typically solved by some form of EM algorithm (as seems the iterative algorithm in section 4). Sections 3.1. and 3.2. are clear; one can learn to discriminate samples from negative/positive example MDPs, or learn a generative model from the model MDP and see whether there is enough deviation from this model. Section 3.3. is less clear, and overall through sections 3.1-3.4 the setting changes in terms of what is expected/assumed in terms of examples (positive, negative, model MDP or something else). In Section 3.1. \"which\" policy is used to generate the samples in both MDPs (line 166)?\nIn Section 3.3. I do not understand \"as explained... only have access to either ...\" (191). I think more detail is needed here also about some deep learning aspects such as why and how the LSTMs are used, and why h_t is first approximated, after which a seperate network f generates \\tilde{s}_{t+1} from this. I suspect first some embedding is learned, but this is not clear. Also here (eq. 6) it seems that \\tilde{s}_{t+1}-\\tilde{T}(s,a) would seem to assume continuous states? Overall, the use of various forms of T and R (either with or without tilde, uppercase, lowercase, etc) and its relation to either the reference MDP or a student solution, is sometimes confusing. Also here, in Sections 3.3. and 3.4. the assumptions vary; in the first one needs one, and in the second one needs two (positive and negative): later in the experiments it is unclear how each of these assumptions for each algorithmic setting is practically implemented/ensured.\nThe distance function in eqs. 9 and 10 makes sense, although the one in eqqs. 4-6 needs more motivation.\n\n- Section 4 makes sense in terms of the text itself, although sentence 222 is an illustration of the process-oriented nature of it again. I think the algorithm should be motivated slightly better, and I do not think the term \"collaborative\" is appropriate here. However, from sentence 228-229 it also seems like the chosen solution is more ad hoc than it seems. Can you elaborate? And what is meant by \"manually\" in line 250? There seems to be no formal reference to Algorithm 1 in the text? Lines 249-250 contains a big claim about the method, but it is not substantiated nor empirically shown later. I think such a claim needs more attention. Figure 1 is not informative for me.\n\n- Section 5 is the most confusing part of the paper. Because there is no clear single approach in terms of solutions (and assumptions needed to make each algorithm work) it is unclear how to read the tables. It is clear that on a general level, the two novel algorithms perform best, but relative performance against simple baselines is different from evaluating the absolute performance and effectiveness of the approach for this kind of problems. Also, the two problem domains are not well described. I have taken a look at the previous version of the paper, and I played around with the bounce domain on code.org, and from that I finally got a much better idea of what is being tried here, but not completely. The first domain, the car, keeps rather vague from the description in this paper. Why does line 264 talk about \"three toy environments\"? For me, the two first car experiments seem \"toy-like\" but the bounce experiment in section 5.2. is really based on a large amount of real-world data. \nThe authors promise \"model specification and .... details ... in supplementary material\" but like said before, this only contains Python notebooks. I think that the paper itself should have given all the right details to understand both domains. As it is now, I cannot evaluate the results properly. Paragraphs such as 272-275 definitely do not help. In addition, I think it highly important to give details on how to practically model particular domains (games) as MDPs in this approach, and some illustration of the size and complexity of the MDPs and used deep networks.\nI also would like to know more about the difference between the contrastive and non-contrastive algorithm: now it seems it varies randomly which algorithm is better when. What would also be very useful (and needed maybe) is an analysis of a single case, to show the models (MDPs) and the learned distance function and a practical illustration of how and why a particular solution MDP is taken as either correct or faulty. Now the paper stays quite abstract on all these matters.\nThe part in 317-325 is nice and informative, but the next paragraph 326-335 then again less clear again.\n\n- Section 6 is comprised of a very selective set of aspects, but a proper discussion of the general results and contributions (and future work) is lacking.\n\nOverall, a paper with good ideas, interesting setting, but some less worked out parts, and sloppyness/unclarities in formalizations and especially the experimental setting and evaluation. I really like the general approach but I have severe doubts whether this paper is finished enough in this state.\n\nPOST-REBUTTAL\nThank you for the adequate reactions to many points. The suggested alterations make me raise my score to the positive side.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the limitations are not well addressed, but the societal impact indeed is.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {"ethical_concerns": "None at this stage. Algorithms in educational settings in general could induce many ethical challenges in the future, but in the current state of the algorithm it is as stated by the authors (\"societal benefits... outweigh.... the harm at this point\"."}}, {"review_id": "Vh_YYJJw6Vk", "reviewer": "Reviewer_Zkxa", "summary": "This paper tackles the problem of automatically grading coding assignments in which students write interactive programs (e.g., games). Such interactive programs are difficult to grade using traditional unit tests, since the test inputs need to dynamically adapt to the changing state of the program. This paper proposes a novel approach that learns to detect bugs in students’ programs by comparing them to a reference solution (and potentially a few examples of incorrect implementations). The key idea is to formalize the program as an MDP, and formalize the problem of detecting differences between the student’s program’s MDP and the reference solution’s MDP as detecting differences in the reward functions and state transition dynamics of the two MDPs. The proposed method trains an agent to visit states in which these differences are large, and uses the trajectories produced by this agent to train a world model that enables us to compute the differences.", "questions": "", "limitations": "", "rating": 9, "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": "Overall, I enjoyed reading this paper. It is a really creative synthesis of ideas from computer-aided education and reinforcement learning, and has the potential to positively impact millions of students.\n\nThere are a few connections to the safe RL literature that could potentially be useful for deriving a general approach to the cold-start problem discussed in Section 4 (e.g., instead of simply pre-training a play-to-win agent in the reference MDP). For example, there is some work on training classifiers to predict human judgments about unsafe states [1], efficiently learning to predict failure probabilities of agents [2], and training agents to intentionally seek out unsafe states so as to improve the accuracy of the unsafe state classifier [3, 4]. More generally, the problem of simultaneously training an RL agent and a reward model has been explored extensively in the context of self-supervised RL. For example, there is work on learning from intrinsic motivations like empowerment [5], curiosity [6], and diversity [7], where the agent typically optimizes a variational lower bound that is learned interactively. These prior methods might contain some useful ideas for scaling up the “collaborative training” approach in Section 4.\n\n1. [Trial without Error](https://arxiv.org/abs/1707.05173)\n2. [Rigorous Agent Evaluation](https://arxiv.org/abs/1812.01647)\n3. [Improving Safety in RL](https://arxiv.org/abs/1903.09328)\n4. [Learning Human Objectives](https://arxiv.org/abs/1912.05652)\n5. [Variational Information Maximisation](https://arxiv.org/abs/1509.08731)\n6. [Curiosity-driven Exploration](https://arxiv.org/abs/1705.05363v1)\n7. [Diversity is All You Need](https://arxiv.org/abs/1802.06070v6)\n\nI think the play-to-grade idea could be useful for applications beyond education; for example, generalization to new MDPs with different dynamics, which is a problem in imitation learning (e.g., for robotic control). Play-to-grade could potentially provide a way to test whether the agent’s MDP is actually different from the demonstrator’s MDP, which could then be helpful for deciding whether or not to employ some kind of transfer learning method to adapt the demonstrations to the new MDP.\n\nA few minor questions and comments:\n - Line 191: I didn’t understand the first sentence. Earlier, isn’t it stated that we do not have direct access to the transition function or reward function in any of the MDPs, including the reference?\n - Section 3.3: The connection between state transitions and Hoare triples is pretty cool!\n - Section 3.4: Couldn’t you also use the distance to bug MDPs to do bug classification (not just detection)? Could you calculate pairwise distances between student submissions, embed them in a latent space, and cluster them to discover new types of bugs that are not in the teacher’s examples of buggy programs?\n\nTypos:\n - Line 35: “a 20 seconds” → 20 seconds\n - Line 54: “students assignment” → student’s assignment\n - Line 71: “network to understanding” → networks to understand\n - Line 73: “up approximately” → up to approximately\n - Line 82: “buggy.” → “buggy?”\n - Line 99: “game objects positional” → game objects’ positions\n - Line 132: “of The challenge” → of the challenge\n - Line 154: “of solving is task” → of solving this task\n - Line 184: “They are also been” → They have also been\n - Line 196: “If we learn to T_theta” → If we learn T_theta\n - Line 234: “and easy to fail” → in which it is easy to fail\n - Line 267: “to be” → be\n - Line 278: “that just spins” → and just spins\n - Line 295: “correctly the bug state” → correctly identify the bug state\n - Line 318: “of submission in dataset” → of submissions in the dataset\n - Line 346: “requires” → require\n - Line 350: “outweighs” → outweigh\n\nUpdate after reading author response\n-----\nThank you for your response. I will keep my original score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately address limitations and societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Oxf4EYVdWl4", "reviewer": "Reviewer_3Rdw", "summary": "The paper presents an approach to automatically detect correct/good and incorrect/bad program submissions by a student, for particularly challenging programming tasks requiring dynamic input from the user to check for implementation correctness.  The approach models the student submissions as MDPs. The claim is that correct student submissions will be closer to each other than the incorrect ones. To this end, the authors propose a solution based on 'differential states', to determine the distance between two MDPs, in order to classify student submissions appropriately. Using this classification mechanism, one can automatically detect good/bad submissions for a task. Furthermore, this classification requires only a few examples (correct/incorrect) from the teacher to begin with. The approach is evaluated on student submissions for a real-world programming task (hosted by the popular coding platform Code.org), and the proposed method achieves high accuracy/recall on the same.", "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": "**Pros**\n\n* The authors formulate the problem of classifying student submissions, modeled as MDPs clearly. Modeling student submissions in a programming domain as individual MDPs, and reducing the problem of finding bugs to that of finding differential states is novel and interesting.  \n* The idea of using 'Contrastive HoareLSTM' to determine the distance function, and mitigate the approximation error was a nice addition.\n* The use of the Bounce Dataset for evaluation, if made public (which is the claim) will be very useful for the community to carry forward research in the direction of automated feedback generation of programming.\n* Proof of concept presented on the Car Environment presented useful insights on the inner workings of the algorithm.\n* The code files provided in the supplementary material run smoothly.\n\n**Cons**\n\n* Writing: While the problem formulation was clearly explained, the writing could be made more clear Section 2.2 onwards. For instance, notation 'd(M, M^{~})' was not introduced in the text at all. The description of 'd(s,a)'  in Eq.2 and the intuition behind it could be made clearer. I also found the description of Baseline 3.2 hard to follow. It could be elaborated upon a little more. Similarly in Section 4.2 the quantity '\\delta' was not introduced in the text. A simple line suggesting that this quantity is presented in the Algorithm block could make it clearer.\n\n* Baselines for evaluation: Elaborating the key baseline Code-as-text a little more, could provide insights into the additional details captured by the proposed novel algorithm. \n\n* Further analysis of results: Further analysis on which **kinds** of submissions are misclassified by the algorithm, would be interesting. Are there specific types of student approaches that are particularly tricky to assess, and how does the algorithm fair in those cases? An illustration of such a case would be an interesting add-on.\n\n**General Comments**\nThis paper introduces a novel way of analyzing program submissions for a particular task. However, the usefulness of this approach in actually grading assignments such as Bounce can be still explored. More insights/analysis into the false positives in the set of student submissions (particularly in the Tail) evaluated, could be given, to understand the practical use of the algorithm as a grading tool. But, overall designing an RL-based solution for student program grading is very interesting, and opens avenues for future research in this direction.\n\n*Originality* : Novel Approach\n\n*Clarity*: Could be improved, particularly by introducing notation clearly in certain places.\n\n*Quality*: Good\n\n*Significance*: High\n\nUPDATE (Post-Rebuttal): Thank You authors for the responses to my specific queries! I will keep my original score for the paper. I maintain that I generally liked the key idea presented in the paper, but considering the practical nature of the work, its limitations can be better addressed, as already pointed out by Reviewer Z8Zo.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The societal benefits of this kind of research outweigh their potential misuse.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 "}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an interesting idea - converting the problem of finding bugs in programs as an RL problem to find “differential states” between MDPs.

All reviewers liked the idea, but two reviewers gave borderline reviews, with clarity being a major concern.  After calibrating across a range of papers the AC decided to accept this paper based on the idea proposed and the problem being solved which may have practical impact.

However, the authors should try to improve the paper in particular on the clarity front.  Also the authors seem to be unaware of the relevant literature on software testing and debugging, in particular for software with UI, which seems directly related, for example [this paper](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.227.4901&rep=rep1&type=pdf).  It would be good to position this work better with respect to the wider context.
Decision: Accept (Poster)