Hierarchical Reinforcement Learning for Pedagogical Policy Induction (Extended Abstract)

1 Introduction

E-learning environments, such as intelligent tutoring systems (ITSs) has enabled us to provide low-cost and time-flexible education opportunities. It has been shown that such environments can improve students' learning in real classrooms [Koedinger et al., 1997]. During training, the tutor makes decisions on what students should do next based on observations of students' learning state. The tutor's decisions can be viewed as a temporal sequence, each of which affects the student's successive actions and performance. Its impact on student learning cannot often be observed immediately and the effectiveness of one decision also depends on subsequent decisions. Most existing e-learning applications employ Pedagogical policies to decide what action to take next in the face of alternatives. Ideally, an effective learning environment should craft and adapt its decisions to users' needs [Anderson et al., 1995]. In recent years, a number of researchers have studied applying Reinforcement Learning (RL) to induce pedagogical policies directly from studenttutor interaction logs (e.g. [Shen et al., 2018; Chi et al., 2011; Mandel et al., 2014]). Despite promising, most prior applications treat all system actions equally, or independently, and do not account for the long-term impact that tutor decisions may have across these two levels of granularity.

∗This is an abridged version of the AIED 2019 best paper "Hierarchical Reinforcement Learning for Pedagogical Policy Induction" [Zhou et al. 2019]

In ITSs, there are decisions to make at different levels of granularity, from whole problems to single steps. At each of these levels, the system may decide to give a hint, provide a worked example, or give immediate feedback. These actions all have the goal of helping students solve a problem, but some may be more important or impactful than others. Human decision-makers treat these distinct levels of granularity [Evens

and Michael, 2006; Lepper et al., 1993]. In this work, we propose and apply an offline hierarchical reinforcement learning (HRL) framework to induce a pedagogical policy that makes decisions at two levels of granularity: problem and step.

More specifically, the tutor first decides whether the next problem should be a Worked Example (WE), Problem Solving (PS), or Collaborative Problem Solving (CPS). In WE, the student observes how the tutor solves a problem; in PS, the student solves the problem themselves; in CPS, the student and the tutor co-construct the solution. Based on the problem-level decision, the tutor then makes step-level decisions on whether to elicit the next step from the student or to show it directly. We refer to such decisions as elicit/tell. If WE is selected, an all-tell step policy will be carried out; if PS is selected, an all-elicit policy will be executed; finally, if CPS is selected, the tutor will decide whether to elicit or tell a step based on the corresponding step-level policy. A great deal of research has investigated the impacts of the problem-level WE vs. PS and the step-level elicit vs. tell [Renkl et al., 2002; Schwonke et al., 2009; Salden et al., 2010]. However, none of them are well understood, and there is no widespread consensus on how they should be used. Thus, here, we apply data-driven approaches to induce pedagogical policies directly from data. Results from an empirical classroom study showed that the HRL policy was significantly more effective than a DQN induced step-level policy and a random yet reasonable step-level policy. Since both elicit and tell are always considered to be reasonable educational interventions in our learning context, our random policy is random yet reasonable.

2 Background

In recent years, RL, especially Deep RL has been applied to handle complicated tasks and has achieved superhuman performance in several complex games. However, different from the classic game-play situations where the ultimate goal is to make smart system decisions, our ultimate goal for RL is to make the student-tutor interaction productive and fruitful. This raises additional challenges due to the high cost to collect and the complexity of human learning data.

Generally speaking, RL approaches can be categorized into online and offline. Online approaches learn a policy in realtime by interacting with the environment while offline approaches learn from pre-collected training data. Online RL research to induce pedagogical policies has often relied on simulations or simulated students. As a consequence, the success of these approaches is heavily dependent on the accuracy of the simulations. Offline RL approaches, on the other hand, "take advantage of previously collected samples, and generally provide robust convergence guarantees" [Schwab and Ray, 2017]. The success of offline RL is thus often heavily dependent on the quality of the training data. One common convention is to collect an exploratory corpus by training students on an ITS that makes random yet reasonable decisions and then apply RL to induce pedagogical policies from that corpus. Researchers have applied a variety of online [Beck et al., 2000; Iglesias et al., 2009; Rafferty et al., 2016] and offline [Shen et al., 2018; Chi et al., 2011; Mandel et al., 2014] RL approaches for pedagogical policy induction. All the models described here were evaluated in classroom studies, yielding improved student learning and/or behaviors as compared to baseline policies.

Despite these successes, the necessity for accurate simulations (online) or large training corpora (offline) has limited the wide use of RL for policy induction. Additionally, prior research on applying both online and offline RL for pedagogical policy induction has not taken the granularity of decisions into account. In the remainder of the paper, we will refer to these approaches as flat RL to differentiate them from our new HRL approach.

It has been widely shown that HRL can be more effective and data-efficient than flat RL approaches [Cuay´ahuitl et al., 2010; Peng et al., 2017; Wang et al., 2018; Kulkarni et al., 2016]. HRL generally breaks down a large decision-making problem into a hierarchy of small sub-problems and induces a policy for each of them. Since the sub-problems are small, they usually require fewer data to find the optimal policies. For example, Cuay´ahuitl et al. induced navigation policies [Cuay´ahuitl et al., 2010] at 3 levels: buildings, floors, and corridors, showing that HRL converged to an optimal policy in much fewer iterations. Although promising, the use of hierarchy requires additional information, such as the transitions and rewards at different levels of granularity, to induce a policy. A simple and effective way to collect such information is to explore the environment during learning. Therefore, most existing HRL applications have been online. But here, we propose and apply an offline HRL approach that can induce policies from pre-collected data.

3 Policy Induction

In RL policy induction, immediate rewards are generally more effective than delayed rewards. This is because it is easier to assign appropriate credit or blame when the feedback is tied to a single decision. For HRL policy induction, immediate rewards are needed at different levels, to induce hierarchical policies. On the other hand, the most appropriate reward to use in ITSs is student learning gains, which are typically unavailable until the entire training process is complete. This is due to the complex nature of the learning process which makes it difficult to assess students' learning moment by moment and more importantly, many instructional interventions that boost short-term performance may not be effective over the long-term. Therefore, in this work, we first propose and apply a Gaussian Processes based (GP-based) approach to infer "immediate rewards" from the delayed rewards and then apply HRL and DQN to induce the corresponding hierarchical or step-level policies based on the inferred immediate rewards. In the following, we will briefly describe: 1) our proposed GP-based approach to infer immediate rewards, 2) our offline GP-based HRL framework, and 3) DQN. We now present a few critical details of the process, but many have been omitted to save space.

3.1 GP-Based Approach for Immediate Reward Inference

Our historical dataset D consists of student-ITS interaction trajectories with different lengths. Each trajectory d can be viewed as: s1 a1,r1 ---→ s2 a2,r2 ---→ · · · sn an,rn ---→. Here si ai ,ri ---→ si+1 indicates that at the ith turn in d, the learning environment was in state si, the agent executed action ai and received reward ri, and then the learning environment transferred into state si+1. Since our primary interest is to improve students' final learning gain, we used Normalized Learning Gain (NLG) as the reward because it measures students' gain irrespective of their incoming competence. NLG = posttest-pretest √1-pretest where pretest and posttest refer to the students' test scores before and after the ITS training respectively and 1 is the maximum score. Given that a student's NLG will not be available until the entire training is complete, only terminal states have non-zero rewards. That is for a trajectory d, r1 · · · , rn-1 are all equal to 0, only rn = NLG× 100, which is in the range of (-∞, 100].

To infer the immediate rewards, we applied a Gaussian Processes (GP) approach to learn a function that specifies the reward for each state-action pair in the trajectory [Azizsoltani et al., 2019]. This approach distributes immediate rewards inside each trajectory by assuming that they follow Gaussian distributions and that these rewards add up to the delayed reward. Different from standard GP which minimizes the direct output error, this approach minimizes the additive error of the model output. The process starts with assigning a prior probability to each possible function. Then following the Gaussian Process Regression [Rasmussen, 2004; Azizsoltani and Sadeghi, 2018] and using the shared mutual information existed in the feature representation, higher probabilities are given to the functions where the sum of the generated immediate rewards is close to the observed delayed reward. Averaging all the possible functions generates the reward function.

3.2 An Offline GP-based HRL for Policy Induction

Most HRL research is based upon an extension of Markov Decision Processes (MDPs) called Discrete Semi-Markov Decision Processes (SMDPs). An MDP describes a stochastic control process that can be described as a 4-tuple: < S,A, T,R >. In pedagogical policy induction, the states S are vector representations composed of relevant learning environment features such as the difficulty level of a problem, percentage of the correct entries a student has entered so far and so. In this study, the learning environment is described by 142 features; the actions A are selected from {WE, PS, CPS} for problem-level decisions and from {elicit, tell} for steps; the reward function R is calculated from the system's success measures: students' NLG. Once the {S, A, R} has been defined, the transition probabilities T are estimated from the training corpus D.

SMDPs extend the existing MDP framework by adding a set of complex activities [Barto and Mahadevan, 2003] or options [Sutton et al., 1999], each of which can invoke other activities recursively, thus allowing the hierarchical policy to function. The complex activities are distinct from the primitive actions in that a complex activity may contain multiple primitive actions. In our applications, WE, PS and CPS are complex activities while elicit and tell are primitive actions. A complex activity consists of three elements: a policy π that maps states to each available option, a termination condition, and an initiation set. A solution to the SMDP mentioned above is an optimal policy (π∗ ), a mapping from state to complex activities or primitive actions, that maximizes the expected discounted cumulative reward for each state.

Since complex activities can take a variety of time steps to execute, it is necessary to extend the state-transition function to take into account the activity length. The extended transition probability function can be denoted as: P(s′ , t′ |s, a), which specifies the probability of transitioning to state s′ after t′ time steps if taking action a in state s. Accordingly, the expected reward function is also extended to accumulate over the waiting time t′ in s given activity a. Similar to RL, HRL learns the policy through estimating the Q-value function Q(s, a), denoted as the expected cumulative rewards the agent will receive if it takes activity a in state s and follows the policy to the end. The optimal Q-value function Q∗ denotes the expected cumulative rewards the agent can receive if it follows the optimal policy and Q∗ satisfies the Bellman equation [Sutton et al., 1999]. In SMDPs, the Bellman equation can be rewritten as:

where 0 ≤ γ ≤ 1 is a discount factor. For HRL, learning occurs at multiple levels. The global learning generates a policy for the top-level decisions and local learning generates a policy for each complex activity. This process retains the fundamental assumption of RL: that goals are defined by their association with reward, and thus that the objective is to discover actions that maximize the long-term cumulative reward. Local learning focuses not on learning the best policy for the overall task but the best policy for the corresponding complex activity.

In our offline HRL framework, both problem- and steplevel policies were learned by recursively using the Gaussian Processes (GP) to estimate the Q-value function [Rasmussen, 2004] following Equation 1 until the Q-value function and the policy converged. In each iteration, a Q-value was generated for each state-action pair in the training trajectories following Equation 1 based on the inferred immediate rewards and the latest GP model. Then the GP model was updated based on the new Q-value assigned to each state-action pair. Our training corpus contains 1,118 students' interaction logs. To induce the hierarchical policy, we defined a problem-level semi-MDP for determining whether the next problem should be WE, PS or CPS and for each of the training problems, we defined a step-level semi-MDP for inducing a step-level policy to determine elicit vs. tell if a complex activity CPS is selected for that training problem.

3.3 DQN for Policy Induction

A Double DQN approach [Van Hasselt et al., 2016] with the prioritized experience replay technique [Schaul et al., 2015] was applied to induce the DQN step-level policy. A multilayer perceptron neural network was used to approximate the Q-function. The inputs to the neural network were the last 3 step observations of a student and the outputs were the Qvalues for each possible step level action (in our case, elicit and tell). The network consists of two 64-unit layers with the rectified linear unit (ReLU) activation function (except that the output layer has no activation function). As a convention for this algorithm, an experience replay buffer and a target network were used to stabilize the training. The data and immediate rewards used for DQN policy induction were identical to those used for HRL.

4 Empirical Experiment

Participants. This study was conducted in an undergraduate Discrete Mathematics course in Fall 2018 as a regular homework assignment. Students had one week to complete it and were graded based upon their demonstrated effort rather than performance. Students (N=180) were randomly assigned into three conditions (60 in each of HRL, DQN, and Random). Due to final exam preparations, 140 students completed the study. 3 students who scored perfectly in the pre-test and 9 students who completed the study in groups were excluded from our subsequent analysis. The remaining 128 students were distributed as follows: N = 44 for HRL, N = 45 for DQN, and N = 39 for Random. A χ2 test shows that the participants' completion rate did not differ significantly by condition: χ2 (2) = 1.03, p = 0.598.

Pyrenees. Pyrenees is a web-based ITS that teaches students a general problem solving strategy and 10 major probability principles, such as the Complement Theorem and Bayes' Rule. It provides students with step-by-step instruction, immediate feedback, and on-demand help. Except for the pedagogical policy, the remaining components of the tutor, including the GUI interface, the training problems, and the tutorial support were identical for all students.

Procedure. All three conditions went through four phases: 1) textbook, 2) pre-test, 3) training on the ITS, and 4) posttest. The only difference between them was the policy employed by the ITS. During textbook, all students read a general description of each principle, reviewed some examples, and solved some practice problems. Then they took a 14-problem pre-test where no feedback was given. During training on the ITS, all students received the same 12 problems in the same order. Finally, they took a 20-problem posttest. 14 of the problems were isomorphic to the pre-test and the remainders were non-isomorphic complicated problems.

Grading. The pre- and post-tests were graded using a partial credit rubric, where each problem score was determined by the percentage of principles correctly applied. For example, a student who correctly applied 4 of 5 possible principles would get a score of 0.8. Experienced graders conducted the grading in a double-blind manner. For comparison purposes, all test scores were normalized to the range of [0, 100].

5 Results

Despite of random assignment, a one-way ANOVA analysis on the pre-test score showed a marginally significant difference among the three conditions: F(2, 125) = 2.805, p = 0.064, η = 0.043. Subsequent contrast analysis showed that DQN scored significantly higher than HRL: t(125) = 2.06, p = 0.042, d = 0.46 and Random: t(125) = 2.01, p = 0.046, d = 0.46; but there was no significant difference between HRL and Random: t(125) = 0.02, p = 0.986, d = 0.00. Since students were not perfectly balanced in incoming competence, we took students' pre-test score into account in all following analyses. Table 1 shows the mean and standard deviation (SD) of students' learning performance results, showing (from left to right) the Condition with the number of students in parentheses, pre-test (Pre), isomorphic posttest (Iso Post), adjusted post-test (Adj Post) and Normalized Learning Gain (NLG).

To measure students' learning improvement, we compared their isomorphic post-test scores with their pre-test scores. A repeated measures analysis showed that all students scored significantly higher in the isomorphic post-test than in the pre-test: F(1, 127) = 158.63, p < 0.0001, η = 0.555. This is also true for each individual condition including the random baseline. This suggests that the basic practice and problems, domain exposure, and interactivity of our ITS effectively help students acquire knowledge, even when the decisions are made randomly yet reasonably.

Adjusted Post-test. To comprehensively evaluate how the HRL and DQN policies impacted students learning performance, we conducted analysis based on the full post-test score. Comparing to the pre-test, the full post-test contains six additional complicated problems. An ANCOVA analysis on the full post-test using the pre-test score as a covariate showed a significant difference among the three conditions: F(2, 124) = 3.86, p = 0.024, η = 0.030. Then, based on the linear model generated in the ANCOVA analysis and the pre-test score, we calculated the adjusted post-test score (Adj Post). Contrast analysis on the adjusted post-test showed that the HRL condition scored significantly higher than the DQN condition: t(125) = 2.53, p = 0.013, d = 0.57 and the Random condition: t(125) = 2.36, p = 0.020, d = 0.52. No significant difference was found between DQN and Random. The results suggest that the HRL policy is significantly more effective than the DQN policy and the Random policy.

NLG. Similarly, a one-way ANOVA analysis on the NLG (calculated based on pre- and full post-test) showed that there was a significant difference among the three conditions: F(2, 125) = 4.39, p = 0.014, η = 0.066. Subsequent contrast analysis showed that HRL scored significantly higher than DQN: t(125) = 2.75, p = 0.007, d = 0.66 and Random: t(125) = 2.30, p = 0.023, d = 0.52. Again, no significant difference was found between DQN and Random. Note that NLG is the reward we used for policy induction and thus, the results suggest that our HRL policy indeed can improve the desired outcome measure.

6 Conclusion and Discussion

In this study, we proposed and applied an offline GP-based HRL framework to induce a hierarchical pedagogical policy, which makes decisions first at the problem level and then the step level. Results from an empirical classroom study showed that the HRL policy was significantly more effective than a DQN induced step-level policy and a Random step-level policy. The results suggest that HRL can be more effective than flat RL in pedagogical policy induction. One possible explanation is that HRL has an explicit problem-level vision. At the problem level, HRL views a problem as an atomic action, and this abstraction has two potential advantages: 1) it aggregates the effects of all steps in a problem and 2) it converts a long step-level sequence into a short problem-level sequence. The aggregation of steps across a problem may provide HRL with a better estimation of the effect of taking a series of steps; while the problem sequence may give HRL a better view of the long-term effects of each problem. Theoretically, flat RL could learn the impact of a problem by aggregating step-level information, but there is no guarantee that it would. Our results confirm the intuition that HRL should outperform flat RL on pedagogical policy induction because it can simultaneously learn at two levels of granularity - the problem level outer loop and the step level inner loop.

Acknowledgments

This research was supported by the NSF Grants: #1726550, #1651909, and #1660878.