Play to Grade: Grading Interactive Coding Games as Classifying Markov Decision Process
Authors: Allen Nie
Emma Brunskill
Chris Piech
Venue:  (2021)
Keywords: Deep Reinforcement Learning
Education
Automated Grading
Program Testing

Abstract: Contemporary coding education often present students with the task of developing programs that have user interaction and complex dynamic systems, such as mouse based games. While pedagogically compelling, grading such student programs requires dynamic user inputs, therefore they are difficult to grade by unit tests. In this paper we formalize the challenge of grading 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 conforms to a set of latent MDPs. We demonstrate that by experiencing a handful of latent MDPs millions of times, we can use the agent to sample trajectories from the input MDP and use a classifier to determine membership. Our method drastically reduces the amount of data needed to train an automatic grading system for interactive code assignments and present a challenge to state-of-the-art reinforcement learning generalization methods. Together with Code.org, we curated a dataset of 700k student submissions, one of the largest dataset of anonymized student submissions to a single assignment. This Code.org assignment had no previous solution for automatically providing correctness feedback to students and as such this contribution could lead to meaningful improvement in educational experience.

Under review as a conference paper at ICLR 2021
PLAY TO GRADE: GRADING INTERACTIVE CODING GAMES AS CLASSIFYING MARKOV DECISION PRO- CESS
Anonymous authors Paper under double-bling blind review
ABSTRACT
Contemporary coding education often present students with the task of developing programs that have user interaction and complex dynamic systems, such as mouse based games. While pedagogically compelling, grading such student programs requires dynamic user inputs, therefore they difficult grade by unit tests. In this paper we formalize the challenge of grading interactive programs as a task of classifying Markov Decision Processes (MDPs). Each student's '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 conforms a set of latent MDPs. We demonstrate that by experiencing a handful of latent MDPs millions of times, we can use the agent to sample trajectories from the in- put MDP and use a classifier to determine membership. Our method drastically reduces the amount of data needed to train an automatic grading system for inter- active code assignments and present challenge to sate--oftthe-ar reinforcement learning generalization methods. Together with Code.org, we curated a dataset of 700k student submissions, one of the largest dataset of anonymized student submissions to a single assignment. This Code.org org assignment had no previous solution for automatically providing correctness feedback students and as such this contribution could lead to meaningful improvement in educational experience.
INTRODUCTION
The rise of online coding education platforms accelerates the trend to democratize high quality com- puter science education for millions of students each year. [Crbett] (200T) suggests that providing feedback to students can have enormous impact on efficiently and effectively helping students learn. Unfortunately 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 program that requires user interaction, e.g. where user interacts with the student's program using mouse, by clicking button it becomes exceedingly difficult to grade automatically. Even for well defined challenges, if the user has any creative discretion, or the problem involves any ran- domness, the task of automatically assessing the work is daunting. Yet creating more open-ended assignments for students can be particularly motivating and engaging, and also help allow students to practice key skills that will be needed in commercial projects.
Generating feedback on interactive programs from humans is more laborious than it might seem. Though the most common student solution to an assignment may be submitted many thousands of times, even for introductory computer science education, the probability distribution of homework submissions follows the very heavy tailed Zipf distribution - the statistical distribution of natural language. This makes grading exceptionally hard for contemporary AI (Wu et al. 2019) as well as massive crowd sourced human efforts (Code.org 2014). While code as text has proved difficult to grade, actually running student code is promising path forward (Yan al. 2019).
We formulate the grading via playing task as equivalent to classifying whether an ungraded student program new Markov Decision Process (MDP) belongs latent class of correct Markov De- cision Processes (representing correct programming solutions to the assignment). Given a discrete set of environments & {en (Sn, A, Rn, P.) 1,2, 3, ...,, partition them into E

---

Under review as a conference paper at ICLR 2021
Launch new bx]1
Sounco bo31
Score potet
Scors opporient soint
spead
Semed11
Score 01 0
Se:
ball spred
Set
bandrour ScoTe
Nardscours hxl1
Bardccors
Setart
O Saanet
Sileett
+
Sauast
R-8-41
I--1-B
18-1444
11-8--11
Figure 1: Bounce can have different "themes" for the background, paddle, and ball. There are two themes to choose from: "hardcourt" and "retro". We show the complete eight different combinations of themes and what the game would look like under these settings.
and E'. Ex is the set of latent MDPs. It includes handful of reference programs that teacher has implemented or graded. E' the set of environments specified by student submitted programs. We are building classifier that determines whether new input decision process is behaviorally identical to the latent decision process.
Prior work providing feedback for code has focused text-based syntactic analysis and automat- ically constructing solution space (Rivers & Koedinger 2013 Ihantola et al., 2015). Such feedback orients around providing hints and unable determine an interactive program 's correctness. Other intelligent tutoring systems focused on math or other skills that don't require creating interactive could analyze the code and seek programs (Ruan al., 2019 2020). Note that principle
to understand the code produces a dynamics and reward model that is isomorphic to the dynamics and reward generated by a correct program. However, there many different ways to express the same correct program and classifying such text might require a large amount of data: as first ap- proach, we avoid this by instead deploying a policy and observing the resulting program behavior, thereby generating execution traces of the student's 's implicitly specified MDP that can be used for classification.
Main contributions in this paper:
We introduce the reinforcement learning challenge of Play Grade.
We propose baseline algorithm where agent learns to play game and use features such as total reward and anticipated reward to determine correctness.
Our classifier obtains 93.1 accuracy on 8359 most frequent programs that cover 50% of the overall submissions and achieve 89.0% accuracy on programs that submitted by less than times. We gained 14-19% absolute improvement over grading programs via code text.
We will release a dataset of over 700k student submissions to support further research.
2 THE PLAY TO GRADE CHALLENGE
We formulate the challenge with constraints that are often found in the real world. Given in- teractive coding assignment, teacher often has a few reference implementations of the assignment. Teachers them show students what correct solution should look like. We also assume that the teacher can prepare a few incorrect implementations that represent their "best guesses" of what wrong program should look like.
To formalize this setting, we consider a set of programs, each fully specifies an environment and its dynamics: & (en (Sn, A, Rn, P.) 1,,,,, 3..... A subset of these environments
2

---

Under review as a conference paper at ICLR 2021
ihen run
ihen bell adenes 526c2e
pablle
bull hita
Leanch ner SAL1
Howe Jeft
Score asporens point
Baily
Mani toll kits pioile
Whon bull in soul
right
Ecerce ball
score poirt
Leanch now ball
Learch
log Rank
(a) We refer to this program as the standard program, as it is the sim- plest combination that makes up correct program.
(b) The probability distribution
conform a Zipf distribution.
Figure 2: This is the drag-and and-drop style code editor that students use to create the game Bounce. Conditions such "when run" or "when left arrow" are fixed in space. Students place commands such as "score point", under each condition. The submission frequency of each unique program conforms Zipfian distribution on log-log plot.
reference environments that are accessible during training, we refer to them E*, and we also have a set of environments that are specified by student submitted programs E'. We can further specify a training set D = {(T', y²):y E {0, 1}} where 7' ~ TTe(*)) and e 8*, and a test set Drest where e()) E, The overall objective of this challenge is:
min (()) = min min le ( (e x)).
(I)
We want policy that can generate trajectory that can help classifier easily distinguish between an input environment that correctly implemented and one that is not. We also allow feature mapping function Φ that takes the trajectory and estimations from the agent as intput and output features for the classifier. We can imagine a naive classifier that labels any environment that playable (defined by being able obtain rewards) by agent correct. A trivial failure case for this classifier would be that if the agent badly trained and fails to play successfully new environment (returning zero reward), we would not know if zero reward indicates the wrongness of the program or the failure of our agent.
Generalization challenge In order to avoid the trivial failure case described above the game states observed are result of our agent's is failure to play the game, not result of correctness or wrongness the program, is crucial that the agent operates successfully under different correct environments. For any correct environment, E {Ei, 8L }, the goal is for agent to obtain the high expected reward.
π arg max Eene, [Br [R(T)]]
(2)
Additionally, we choose the state space to be the pixel-based screenshot the game. This assump- tion imposes the least amount of modification thousands of games that teaching platforms have created for students over the years.
This decision poses a great challenge to our agent. When students create a game, they might choose to express their creativity through a myriad of ways, including but not limited to using exciting background pictures, changing shape or color moving speed of the game objects, etc. Some of these creative expressions only affect game aesthetics, but other will affect how the game is played (i.e., changing the speed of an object). The agent needs to succeed in these creative settings that the classifier will not treat creativity as incorrect.
2.1 BOUNCE GAME SIMULATOR
We pick the coding game Bounce to be the main game for this challenge. Bounce a block-based educational game created to help students understand conditionals We show actual game scenes in Figure I and the coding area in Figure 2a
https://stude http:s///ddlll.....ooo/////////s
3

---

Under review as a conference paper at ICLR 2021
Mhen run
When ball hits Mall
ball
When ball hits paoele
Bounce bell
Scone
Launch new ball
ball
Set
Fandor
Launch
Score point
Set
ball
Launch new ball
Score polint
Set
Fandon
pedole
Launch now ball
(a) wall change
(b) Multiple balls run
(c) paddle points
Figure We demonstrate three examples of how Bounce can be programmed freely by allow- ing infinite repetition of commands and commands to be placed under any condition. Only (a) is considered correct since theme change does not affect game play. Both (b) and (c) are considered incorrect. (c) represents reward design error (give points at incorrect condition). This demonstrates the difficulty of generalization our setting.
The choice gives us three advantages. First, the popularity of this game on Code.org gives us an abundance of real student submissions over the years, allowing to compare algorithms with real data. Second, a block-based program can be easily represented in a structured format, eliminating the need to write a domain-specific parser for student's program. Last, in order to mcasure real progress of this challenge, we need gold labels for each submission. Block-based programming environment allows to specify list of legal and illegal commands under each condition which will provide perfect gold labels.
The Bounce exercise does not have bounded solution space, similar other exercises developed Code.org. This means that the student can produce arbitrarily long programs, such as repeating the same command multiple times (Figure b)) or changing themes whenever condition is triggered (Figure a)). These complications can result in very different game dynamics.
We created simulator faithfully executes command under each condition and will return positive reward when "Score point" block is activated, and negative reward when "Socre opponent point" block is activated. In deployment, such simulator needs be created because coding platforms have already created simulators to run and render student programs.
2.2 CODE.ORG BOUNCE DATASET
Code.org is online computer science education platform that teaches beginner programming. They designed a drag-and-droy interface to teach K-12 students basic programming concepts. Our dataset compiled from 453,211 students. Each time student runs their code, the submission is saved. In total, there are 711 1,274 submissions, where 323,516 unique programs were submitted.
Evaluation metric In an unbounded solution space, the distribution of student submissions incur heavy tail, observed by Wu al. (2019). We show that the distribution of submission in dataset conforms to Zipf distribution. This suggests that we can partition this dataset into two sections, as seen Figure 2b Head + Body: the 8359 most frequently submitted programs that covers 50.5% of the total submissions (359.266). This set contains 4,084 correct programs (48.9%) and 4,275 incorrect programs (51.1%). Tail: This set represents any programs that are submitted less than 5 times. There are 315,157 unique programs in this set and 290.953 of them (92.3%) were only submitted once. We sample 250 correct and 250 incorrect programs uniformly from this set for evaluation.
Reference programs Before looking the student submitted programs, we attempted to solve the assignment ourselves. Through our attempt, we form an understanding of where the student might make mistake and what different variations of correct programs could look like. Our process easily be replicated by teachers. We come up with correct reference programs and incorrect reference programs. This can be regarded as training data.
4

---

Under review as a conference paper at ICLR 2021
Gold annotations We generate the ground-truth gold annotations by defining legal or illegal com- mands under each condition. For example, having more than one "launch new ball" under "when run" is incorrect. Placing "score opponent point" under "when run" is also incorrect. Abiding by this logic, we put down a list of legal and illegal commands for each condition. We note that, we intentionally chose the bounce program it amenable generating gold annotations due the API that code.org exposed to students. While our methods apply broadly, this gold annotation system will not scale other assignments. The full annotation schema Appendix A.5
3 RELATED WORK
Education feedback The quality of an online education platform depends the feedback it can provide to its students. Low quality or missing feedback can greatly reduce motivation for students continue engaging with the exercise (O (O'Rourke al., 2014). Currently, platforms like Code.org that offers block-based programming use syntactic analysis to construct hints and feedbacks (Price & Barnes 2017). The current state-of-the-art introduces method for providing coding feedback that works for assignments up approximately 10 lines of code (Wu et al. 2019). The method does not eas- ily generalize to more complicated programming languages. Our method sidesteps the complexity of static code analysis and instead focus on analyzing the MDP specified by the game environment.
Generalization in RL We are deciding whether input MDP belongs class of MDPs up to some generalization. The generalization represents the creative expressions from the students. A benchmark has been developed to measure trained agent's ability to generalize procedually gen- erated unseen settings of game (Cobbe et al. (019b a). Unlike procedually generated environment where the procedure specifies hyperparameters of the environment, our environment is completely determined by the student program. For example, random theme change can happen if the ball hits the wall. We test the state-of-the-arr algorithms that focus image augmentation techniques on our
environment (Lee et al. 2019: Laskin et al. 2020).
METHOD
4.1 POLICY LEARNING
Given an observation 8t, we first use a convolutional neural network (CNN), the same as the one used in Mnih et al. (2015) feature extractor over pixel observations. To accumulate multi-step information, such as velocity, we use a Long-short-term Memory Network (LSTM). We construct one-layer fully connected policy network and value network that takes the last hidden state from LSTM as input.
We use Policy Proximal Optimization (PPO), a state-of-the--rt on-policy RL algorithm learn the parameters of our model (Schulman et al. 2017). PPO utilizes an actor-critic style train- ing (Mnih et al. 2016) and learns policy x (a, as well a value function V*((s: Ey EL 7",, st] st]
for the policy.
For each episode of the agent training, we randomly sample one environment from a fixed set of correct environments in our reference programs: E ~ E.. The empirical size of & (number of unique correct programs) in dataset is 107,240, We focus on two types of strategies. One strat- egy assumes no domain knowledge, which is more realistic. The other strategy assumes adequate representation of possible combinations of visual appearances.
Baseline training
1. We only train on the environment specified by the standard 2a This serves as the baseline.
program displayed in Figure
Data augmentation training | 1. This is the domain agnostic strategy where we only include the standard program (representing our lack of knowledge on what visual differences might be in student submitted games). We apply the state-of-the-art RL generalization training algorithm to augment our pixel based observation (Laskin et al. 2020). We adopt the top cop-performing augmen- tations (cutout, cutout-color, color-jitter, gray-scale). These augmentations aim change colors
5

---

Under review as a conference paper at ICLR 2021
apply partial occlusion the visual observations randomly that the agent is robust to visual disturbance, which translates to better generalization.
Mix-theme training | 8. This is the domain-aware strategy where include 8 correct environments in our reference environment set, each represents a combination of either "hardcourt" "retro" theme for paddle, ball, or background. The screenshots of all 8 combinations in Figure [ This does not account for dynamics where random theme changes can occur during the game play. However, this does guarantees that the observation state will always have been seen by the network.
be
4.2 CLASSIFIER LEARNING
We design classifier that can take inputs from the environment well as the trained agent. The trajectory т (sn, 40, 81, (1,.).... includes both state observations and reward returned by the environment. We build feature map Φ(T, π) to produce input for the classifier. We want to select features that are most representative of the dynamics and reward model of the MDP that describes the environment. Pixel-based states St has the most amount of information but also the most unstructured. Instead, we choose to focus on total reward and per-step reward trajectory.
Total reward A simple feature that can distinguish between different MDPs the sum of total reward R(r) E, rt. Intuitively, incorrect environments could result in an agent not able to get any reward, extremely high negative or positive reward.
Anticipated reward A particular type of error in our setting is called "reward design" error. An example is displayed in FcgureBc), where point was scored when the ball hits the paddle. This type of mistake is much harder to catch with total reward. By observing the relationship between (s) and rt. we can build an N-th order Markov model to predict Tt, given the previous N-step history of (*=(s==++) 1)..,, V* (s,). If we train this model using the correct reference environments, then can inform us what the correct reward trajectory expected by the agent. We can then compute hamming distance between our predicted reward trajectory á and observed reward trajectory r.
20
Traectory
T II ((re)V
(1,..11) p(ro)
10
(ro) II ( (8t-nt1)) (st)s)
r arg maxpp(f)))
200
400
500
500
1000
d(r, f) = Hamming(r,
Figure 4: V*(ss) indicates the model's
anticipation future reward.
Code-as-text As a baseline, we also explore classifier that completely ignores the trained agent. We turn the program text into a count-based 189-feature vector (7 conditions x 27 commands), where each feature represents the number of times the command is repeated under condition.
EXPERIMENT
5.1 TRAINING
Policy training We train the agent under different generalization strategy for 6M time steps in total. We use 256-dim hidden state LSTM and trained with 128 steps state history. We train each agent till they can reach maximal reward in their respective training environment.
Classifier training We use a fully connected network with hidden layer of size 100 and tanh activation function the classifier. We use Adam optimizer (Kingma Ba 2014) and train for

---

Under review as a conference paper at ICLR 2021
K: # of trajectories sampled
K=1
K=3
K=5
K=7
K=8
Head + Body Student Programs (360K submissions, 8359 unique)
Code-as-text
71.6
Total Reward
84.9
89.2
91.2
91.9
91.9
Total Reward + Anticipated Reward
85.7
90.7
92.7
93.5
94.1
Tail Student Programs (350K submissions, 315K unique!)
Code-as-text
62.2
Total Reward
77.8
82.0
84.0
84.2
84.0
Total Reward + Anticipated Reward
81.2
86.4
88.0
88.8
89.0
Table 1: We evaluate the performance of models two sets of programs based on their fre- quency. "W sampled 500 programs uniformly from tail distribution for evaluation. With K = trajectories per student our best model achieves 94.1 % accuracy head body and 89.0% % on tail.
10,000 iterations till convergence. The classifier is trained with features provided by Φ(T, T). We additionally set heuristic threshold that if d(r, < 0.6, we classify the program having reward design error.
To train the classifier, we sample 16 trajectories by running the agent the 8 correct and 10 incorrect reference environments. We set the window size of the Markov trajectory prediction model to 5 and train a logistic regression model over pairs of ((V*(s:-1) V (s)-3)), .......... VF (st),, re) sampled from the correct reference environments. During evaluation, we vary the number of trajectories we sample (K), and when K > 1, we average the probabilities over K trajectories.
5.2 GRADING PERFORMANCE
We evaluate the performance of our classifier over three set of features and show in Table [ Since we can sample more trajectories from each MDP, we vary the number of samples (K) to show the performance change of different classifiers. When we treat code as text, the representation is fixed, therefore K = 1 for that setting.
We set maximal number of steps be 1,000 for each trajectory. The frame rate of our game is 50, therefore this correspond to 20 seconds of game play. We terminate and reset the environment after 3 balls have been shot in. When the agent win or lose 3 balls, we give additional +100 or -100 to mark the winning or losing of the game. We evaluate over the most frequent 8,359 unique programs that covers 50.1% of overall submissions. Since the tail contains many more unique programs, choose to sample 500 programs uniformly and evaluate our classifier's performance on them.
We actually that using the trajectories sampled by the agent, even if only have 18 labeled reference MDPs for training, we can reach very high accuracy even when we sample very few trajectories. Overall, MDPs on the tail distribution are much harder to classify compared to MDPs from head and body of the distribution. This is perhaps due to the fact the distribution shift that occurs for long-tail classification problems. Overall, when we add reward anticipation as feature into the classifier, we outperform using total reward only.
5.3 GENERALIZATION PERFORMANCE
One of our stated goal for the trained agent π to obtain high expected reward with all correct environments E even though will only be trained with reference environments & We compare different training strategies that allow the agent to generalize to unseen dynamics. In our evaluation, we sample from the head, body, and tail end of the E distribution. Since we only have 51 environments labeled as correct the head distribution, we evaluate agents on all them. For the body and tail portion of the distribution, each ball in goal will get +20 reward, and each ball misses paddle gets -10 reward. The game terminates after 5 balls in missing, making total reward range [-50, 100).
sample 100 correct environments. The reward scheme

---

Under review as a conference paper at ICLR 2021
100
80
Total Reward
40
20
Baseline
Jitter (Laskin et al.)
Cutmut (Laskin et al.)
Color (Laskin et al.)
Grayscale (Laskin et al.)
Mixed Theme (Ours)
Reference
Head
Body
Tail
Figure 5: We compute the average reward across correct environments sampled from head, body, and tail of the distribution and we compare our Mixed Theme training to Color Jitter, Cutout, Cutout Color, Grayscale (Laskin et al. 2020). "Reference" represents single environment specified by the standard program that all agents have been trained on. "Head" refers to the top 51 most frequently appeared correct programs. "Tail" refers to any correct programs that had less than submissions in total. "Body" every program in between. Total reward range is [-50, 100).
We show the result in Figure Since every single agent has been trained on the reference environ- ment specified by the standard program, they all perform relatively well. We can see some of the data augmentation (except Color Jitter) strategics actually help the agent achieve higher reward on the reference environment. However, when we sample correct environments from the body and tail distribution, every training strategy except "Mixed Theme" suffers significant performance drop.
6 DISCUSSION
Visual Features One crucial part of the trajectory is visual features. We have experimented with state-of-the-art video classifier such R3D (Tran et al.] 2018) by sampling couple of thousand videos from both the reference correct and incorrect environments. This approach did not give us a classifier whose accuracy is beyond random chance. We suspect that video classification might suffer from bad sample efficiency. Also, the difference that separates correct environments and incorrect environments concerns more about relationship reasoning for objects than identifying a few pixels from single frame (i.e., "the ball going through the goal, disappeared, but never gets launched again" is an error, but this error is not the result of any single frame).
Nested objective Our overall objective (Equation T is nested objective, where both the policy and the classifier work collaboratively to minimize the overall loss of the classification. However, in this paper, we took the approach of heuristically defining the optimal criteria for policy optimize for expected reward in all correct environments. This is because policy has orders of magnitude more parameters (LSTM+CNN) than our classifier (one layer FCN). Considering the huge parameter space search through and the sparsity of signal, the optimization process could be very difficult. However, there are bugs that need to be intentionally triggered, such as the classic sticky action bug in game design, where when the ball hits the paddle through a particular angle, it would appear to have been "stuck" on the paddle and can't I bounce off. This common bug, though not present in our setting, requires collaboration between policy and classifier in order find out.
CONCLUSION
We introduce the Play to Grade challenge, where we formulate the problem of interactive coding assignment grading classifying Markov Decision Processes (MDPs.. We propose simple solu- tion to achieve 94.1% 1% accuracy over 50% of student submissions. Our approach is not specific to the coding assignment of our choice and can scale feedback for real world use.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Karl Cobbe, Christopher Hesse, Jacob Hilton, and John Schulman. Leveraging procedural genera- tion to benchmark reinforcement learning. arXiv preprint arXiv:19/2.01558 2019a.
Karl Cobbe, Oleg Klimov, Chris Hesse, Tachoon Kim, and John Schulman. Quantifying generaliza-
tion reinforcement learning. In International Conference on Machine Learning, pp. 1282-1289. PMLR, 2019b.
Code.org. Code.org Crowdsourced Hints, 2014. URL wwl.:ttss///bb...chiveee.o/// 201:1003/11203//ttp::/ooomm
org/ /aigtsiitss
Albert Corbett. Cognitive computer tutors: Solving the two-sigma problem. In International Con- feerence User Modeling, pp. 137-147. Springer, 2001.
Petri Ihantola, Arto Vihavainen, Alireza Ahadi, Matthew Butler, Jürgen Börstler, Stephen H Ed- wards, Essi Isohanni, Ari Korhonen, Andrew Petersen, Kelly Rivers, et al. Educational data min- ing and learning analytics in programming: Literature review and case studies. In Proceedings of the 2015 ITiCSE on Working Group Reports, pp. 41-63. 2015.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Michael Laskin, Kimin Lee, Adam Stooke, Lerrel Pinto, Pieter Abbeel, and Aravind Srinivas. Re- inforcement learning with augmented data. arXiv preprint arXiv:2004 2020.
Kimin Lee, Kibok Lee, Jinwoo Shin, and Honglak Lee. Network randomization: A simple technique for generalization in deep reinforcement learning. arXiv, pp. arXiv-1910, 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Belle- mare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, nature, 5 (187540):552 503,,-33,3300 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pp. 1928-1937, 2016.
Eleanor O'Ruurke, 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, pp. 51-60, 2014.
Thomas W Price and Tiffany Barnes. Position paper: Block-based programming should offer intel- ligent support for learners. In 2017 IEEE Blocks and Beyond Workshop (B&B), pp. 65-68. IEEE, 2017.
Kelly Rivers and Kenneth R Koedinger. Automatic generation programming feedback: A data-driven approach. In The First Workshop on Al-supported Education for Computer Science (AIEDCS 2013), volume 50, 2013.
Sherry Ruan, Angelica Willis, Qianyao Xu, Glenn M Davis, Liwei Jiang, Emma Brunskill, and James A Landay. Bookbuddy: Turning digital materials into interactive foreign language lessons through a voice chatbot. In Proceedings of the Sixth (2019) ACM Conference on Learning Scale, pp. 1-4, 2019.
Sherry Ruan, Jiayu He, Rui Ying, Jonathan Burkle, Dunia Hakim, Anna Wang, Yufeng Yin, Lily Zhou, Qianyao Xu, Abdallah AbuHashem, et al. Supporting children's math learning with feedback-augmented narrative technology. In Proceedings of the Interaction Design and Chil- dren Conference, pp. 567-580, 2020.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 7707.06347 2017.
Du Tran, Heng Wang. Lorenzo Torresani, Jamie Ray, Yann LeCun, and Manohar Paluri. A closer look at spatiotemporal convolutions for action recognition. Proceedings of the IEEE conference Computer Vision and Pattern Recognition, pp. 6450-6459 2018

---

Under review as a conference paper at ICLR 2021
Mike Wu, Milan Mosse, Noah Goodman, and Chris Piech. Zero shot learning for code educa- tion: Rubric sampling with deep learning inference. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 782-790, 2019.
Lisa Yan, Nick McKeown, and Chris Piech. The pyramidsnapshot challenge: Understanding student process from visual output of programs. In Proceedings of the 50th ACM Technical Symposium on Computer Science Education, pp. 119-125, 2019.
10


Reviews:
[{"review_id": "jJDwfMGUyF9", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors identify a relatively novel problem to solve with deep reinforcement learning - automatically grading programs which require dynamic input from the user to judge for implementation correctness. In doing so, they also introduce a new dataset and baseline benchmark which can be used to encourage further work in the area. \n\nSome highlights: \n- The work tries to take into account various real-world constraints of the problem. They have realistic expectations for what a teacher would have: one or more correct implementations and one or more incorrect ones. They deal with the possibility that students may choose to be creative and customize the visual aesthetic of the game in a multitude of ways and this must be addressed appropriately.\n- They are methodical about defining the different parts of the evaluation distribution - Head + Body + Tail and the reasoning behind this.\n- They use a few different methodologies for training based on changing the data distribution as well as the reward structure. This is a reasonable sort of ablation study.\n\n\nSome limitations of the work: \n- The work's only example game is 'Bounce' on Code.org. This is one of the most popular games and has an extremely large body of student submissions which give breadth to the training distribution. The programming language is 'block-based' which is extremely structured and distinctly more so than regular imperative programming languages.\n- The annotation system used for Bounce will not scale to other problems.\n- The authors acknowledge that there exists the challenge handling long-tailed distributions in their classification problem. This is probably going to be a significant hurdle for adapting this technique to other program languages/tasks where the tails are even longer. The task of grading is also something that should not have many false negatives (grading as incorrect when it was correct) since that's not good for students.\n\nSome other comments: \n- There appears to be a couple of grammar and one spelling-related typo in the paragraph immediately before the start of Section 2.2\n- Right above section 2, consider changing the definition to  $\\\\mathcal{E}{+} = \\\\mathcal{E}^{\\\\star}{+} \\cup \\\\mathcal{E}^{'}{+}$ (sorry couldn't figure out how to do the + subscript without markdown treating the underscores as signals for italicizing)\n- In the paragraph right before Section 5.2, it would seem that there were 18 trajectories (rather than the stated 16) if you ran on 8 correct and 10 incorrect reference environments. \n\nOverall, considering the three types of comments above, I believe that the paper is an interesting piece of work which makes some rather preliminary progress on a new methodology for automatically grading programming assignments which require dynamic input. However, it leaves some questions up in the air, namely how this approach would scale to different assignments. I would say 'Bounce' represents quite possibly the easiest programming assignment of this category, so it is not the most convincing. I would like to suggest doing the same sort of process for at least a couple of other games, even if they all use the same 'block programming' language from code.org. That would show how much by-hand engineering is required to address the long-tails, the different visual aspects of the game, the length and complexity of episodes, etc. Until then, I will have to say that this is below the threshold for acceptance. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "RMcUhlh-vaW", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "- Quality : Okay\n- Clarity : Poor\n- Originality : Good at problem formulation, but then becomes bad at solution\n- Significance : Could be very significant if done right (not quite there yet).\n\nList of Cons :\n\nA. Needs improvement on writing:\n\n1) \nThe task of the students was confusing to understand. Specifically, for the first 2 pages I was completely lost on what the student is supposed to be implementing. I had the misconception that the coding task is something like Karel, where the student implement a program that is a policy, and are graded on how well the policy acted in a given game environment. That is not what this paper is about. I think the paper started with something like \"Contemporary coding tasks in schools commonly ask the students to implement game environments, for instance, an assignment where the students implement the game PONG, and are graded on whether the resulting game plays like PONG. This types of assignment grading requires interaction as part of a grading process . . . \" This would clear up the confusion.\n\n2) \nEquation 1) is unreadable. What does y = 0 mean? What is \\tau ? What is \\pi ? They are not explained before or after the equation with enough English sentences to intuitively explain what the loss function is doing. And as a result I cannot decipher this giant loss function that, supposedly when minimized according to \\theta – what is \\theta parameterizing? the game playing policy? the classifier of whether an environment is correct? – one would have solved the challenge of playing to grade.\n\n3) \nEquation 2) feels out of place, why all of a sudden we're maximizing reward on an environment? I thought we wanted to have the \"most discerning policy\". See C.1). The authors should make it clear that 2) is already a heuristic, and justifying why this concession is made up-front instead of putting it only in the discussion when the whole paper has ended: \" However, in this paper, we took the approach of heuristically defining the optimal criteria for a policy – optimize for expected reward in all correct environments \"\n\nB. Needs better motivation of the challenges:\n\n1) \nI am not convinced that the grading policy should be run on pixel inputs. I think this is an unwarranted challenge. The authors consider changes to the perceptual input such as \"random theme change can happen if the ball hits the wall\", which seems highly limiting. What would happen if the student add a strobe effect that simply flashes the screen in all possible colors? What would happen if the student flips the world up-side-down? The authors remark that \"Pixel-based states has the most amount of information but also the most unstructured.\" I agree, and I think one can easily resolve this issue by re-structuring the assignment such that the position of the balls and paddle can be easily extracted.\n\nC. Needs better justification/explanation of proposed heuristic solution:\n\n1) \nRather than training the agent to perform well on a game, one should be training agents that break the game in interesting ways, to discover bugs of the environment. For instance, the agent can first try to move the paddle past the left-side of the screen, one can imagine a faulty solution would allow the paddle to infinitely slide off the screen. This paper does not do this, instead, a heuristic of maximizing the reward on any given environment is proposed as a good proxy, due to the difficulty of jointly optimizing the classifier and the policy, again due to the fact of the authors choosing to use CNN as the policy representation.\n\nList of Pros : \n- Done great work at curating the dataset and make it runnable\n- Done great work at specifying the problem statement, and developing a working (albeit misplaced) solution\n\nOverall Comment:\n\nThis paper had great potential. It tackles a class of programs that otherwise would be very difficult to grade, because they require interactions. The problem statement of coordination between the policy and the loss function is beautiful, and it would've been great to see it being solved. However, the paper took a bad turn taking in pixel inputs for no apparent reason, despite owning everything in the simulation stack, from the source code to the rendering engine. This decision ultimately resulted in the paper not able to solve the coordinated optimization task; Resorted to a heuristic objective for the policy; Had to rely on a suite of data augmentation techniques to solve the problem of pixel input, an entirely artificial problem the authors created for themselves. A pixel level input is necessary when one is training RL agents that interacts with the real world where the \"game engine\" is unknown, but the students are literally implementing and handing the game engine to you to grade. Combined with poor writing quality, I think it is not yet ready for publication. \n\nHowever this is a really good problem, and I would like to see this work being further developed, especially in solving the joint-optimization problem, where the agent can maximize for a \"maximally informative trajectory\" w.r.t. the classifier. Extending this approach to solve some additional domains of interactive programs would solidify this paper as one of the significant contributions to MOOCs grading line of literature.\n\n\nfinal recommendations : I maintain my score. I think the other reviewer summarized it best, \"interesting but immature\". I hope to see this work develop and published in the future.", "extra_scores": {}, "extra_text": {}}, {"review_id": "0QYKY3Hlnke", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors contribute an approach to automatically distinguish between good and bad student assignment submissions by modeling the assignment submissions as MDPs. The authors hypothesize that satisfactory assignments modeled as MDPs will be more alike than they are to unsatisfactory assignments. Therefore this can potentially be used as part of some kind of future automated feedback system. The authors demonstrate this approach on an assignment for students to recreate a simple pong-like environment. They are able to achieve high accuracy over the most common submissions. \n\nThe major strength of the paper is in the novelty of the application domain. Reinforcement learning is not typically applied to the education domain in this way. I think there’s certainly potential. In addition, the results do give a positive signal about this research direction. \n\nI have a number of concerns in terms of weaknesses of the paper. First, many of the details of the work are unclear in the current paper draft. I am not sure what the architecture for the agent and the classifier was exactly. Further I’m not sure what exactly the training data was for the agent and the classifier. Separately the authors include the numbers 711,274 (the number of submissions), 18 programs, and a single standard program. Finally it is unclear exactly how long the agents trained for, the authors only state that they trained the agents “until they can reach maximal reward”, without a sense of the number of training episodes. \n\nI think this approach is very interesting, but I’m concerned about whether it’s an appropriate one for this problem domain. If the main issue is feedback then a RL approach is not going to be particularly helpful given RL’s blackbox nature. Further, since the authors could establish a gold standard baseline automatically it’s unclear why they would need an automated approach that only looked at pixels anyway (though it’s also unclear to me the extent to which the gold standard method used in this paper reflects how an instructor would evaluate this assignment). This is also a very simple environment which is well-suited to being modeled by an MDP (since it is a game), and I’m not convinced that this would scale to more complex environments. Finally, it’s unclear to me why student submissions would need to be evaluated from raw pixels and reward values. This seems like an arbitrary constraint since a CS instructor would have access to the model/MDP/submission directly.\n\nI’m not convinced by the evaluation. The authors only compare to a relatively straightforward “code-as-text” baseline. While the authors mention that they attempted an image classifier and found that static images were not suitably discriminative, I don’t see why the authors couldn’t have tried sequences of images. I’d also like to see a more natural baseline, such as a hand-written classifier by a CS instructor or some approximation of this. Something as simple as a KNN classifier could also be worth considering for a baseline. Further, it’s unclear to me what the evaluation domains were, were they the 250 instances taken from the head and tail parts of the dataset? If so, were these all unique instances?\n\nI think this work is interesting, but too immature for publication at this time. I’m recommending rejection.\n\nSome questions for the authors: \n-What was the training curriculum used for the agent(s)? Some clarity across the different numbers of training instances would be appreciated.\n-Did the authors attempt to use sequences of frames in a more straightforward classifier? Or any other way to represent movement/video? Why not, if not?\n-Is there something I’m missing about why this is an appropriate solution to the problem identified by the authors?\n\nThe language across the paper is also uneven and some claims are not substantiated. I’d recommend another pass. Some particular points: \n- “teacher often has” -> “a teacher often has”\n- Is it fair to assume teachers can prepare a few incorrect implementations? I’d like to see a citation to back up this claim, since my understanding is the opposite for complex assignments. \n- “a simulator faithfully executes command”-> “a simulator that faithfully executes commands”\n- “and will return positive reward when “Score point” ” -> “ and returns positive rewards when the “Score point” “\n- “Socre opponent point”-> the “Score opponent point”\n- “such simulator”-> “such a simulator”\n- Code.org didn’t develop this interface they adapted it from Scratch (Maloney et al.)\n- Can you present some evidence that your gold annotation is correct?\n- Why is sample efficiency a concern?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies a novel problem setting of automatically grading interactive programming exercises. Grading such interactive programs is challenging because they require dynamic user inputs. The paper's main strengths lie in formally introducing this problem, proposing an initial solution using reinforcement learning, and curating a large dataset from code.org. All reviewers generally appreciated the importance of the research problem studied and the potential of the work. Even though the reviewers found the work interesting, there was a clear consensus that the work is still immature and not yet ready for publication. I appreciate the authors' engagement with the reviewers during the discussion phase. Overall, the reviewers have provided very detailed and constructive feedback to the authors. We hope that the authors can incorporate this feedback when preparing future revisions of the paper.

Decision: Reject