# Using the ITS Components in Improving the Q-Learning Policy for Instructional Sequencing

Amel Yessad

<figure><img src="image_1.png" /></figure>

## To cite this version:

Amel Yessad. Using the ITS Components in Improving the Q-Learning Policy for Instructional Sequencing. ITS 2023: Augmented Intelligence and Intelligent Tutoring Systems, Jun 2023, Corfu, Greece. pp.247-256, 10.1007/978-3-031-32883-1_21. hal-04161602

HAL Id: hal-04161602

https://inria.hal.science/hal-04161602v1

Submitted on 24 Jul 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Using the ITS components in improving the Q-learning policy for instructional sequencing

Amel Yessad¹[0000-0001-7575-6433]

Sorbonne Université, CNRS, LIP6, 4 place Jussieu, 75252 PARIS cedex 05, France
amel.yessad@lip6.fr

**Abstract.** In this paper, we aim to optimize the sequencing of learning activities using the Q-learning, a reinforcement learning method. The Q-learning agent decides each time which activity to propose to the student. The sequencing policy we propose is guided by the aim to improve efficiently the student knowledge state. Thus, the Q-learning learns a mapping of the student knowledge states to the optimal activity to perform in that state.

In this paper, we tackle two main issues in implementing the Q-learning off-policy: the combinatorial explosion of the student knowledge states and the definition of the reward function allowing to improve efficiently the student knowledge state. We rely on the student model and the domain model to answer these two challenges.

We carried out a study to evaluate the approach we propose on simulated students. We show that our approach is more efficient since it achieves better learning gain with fewer activities than a random policy or an expert based policy.

**Keywords:** Adaptive instruction · Sequencing policy · Reinforcement learning · Q-learning · student model · domain model · Intelligent tutoring system.

## 1 Introduction

In intelligent tutoring systems literature, we can distinguish between two main categories to adapt instructional sequencing in terms of the granularity of the instructional activities and time scales: task-loop (or outer loop) and step-loop (or inner loop) [1, 11]. Task-loop adaptivity involves data-driven decisions the system makes to select instructional activities for the student. Step-loop adaptivity involves data-driven decisions the system makes in response to individual actions a student takes within an instructional activity. In this research, we focus on task-loop adaptivity which consists on the sequencing of learning activities (lectures, problems, quizzes, etc.) that are most suitable according to the student characteristics [1]. It has been widely studied but remain a hard challenge in ITS since the adaptation process depends on several dimensions of the student (knowledge state, emotional state, motivation, etc.) often hidden and not directly observable by the systems.
Several research [2, 5, 6] have shown the interest of reinforcement learning (RL) for instructional policies, as RL models can learn complex and latent relationships between instructional tasks, students actions, and knowledge outcomes. Given the importance of sequential student-teacher interactions in education, there is a real interest in applying RL to improve the state-of-the-art technology for ITS. In particular, the problem of sequencing the learning activities according to the student characteristics fits well a RL problem [2].

Unlike supervised learning and unsupervised learning, a RL agent learns from direct interaction with its environment. RL is suitable for systems where the agent needs to learn a policy on what to do in different situations to maximize a long-term utility [9]. Concretely, it is for an agent to learn how to map states to actions.

Using the RL raises two challenging tasks: the definition of the environment informations that we have to take into account as input of the RL agent and the definition of the reward function guiding the learning of the optimal policy. Several model-Based Policies[8]and model-free policies [3] were proposed in the state of the art. In this research, we propose to use the Q-learning [13], a model-free algorithm to learn a sequencing policy. The Q-learning seems to be a good method since we haven't any explicit model of the optimal decision that could be thus reached through a trial and error strategy.

In this research, we rely on the two main components of an ITS, namely, the student model and the domain model to improve the training process of the Q-learning algorithm. On the one hand, the student model is used to infer the student knowledge state each time the student performs a learning activity. The Q-learning learns a mapping of the student knowledge states to a learning activity to recommand in that state. In this paper, we consider only the knowledge state of the student as input to the Q-learning agent. The objective is to learn a sequencing policy that improves efficiently the knowledge state of the students. It is well known that the student's knowledge state may be a complicated function of the history of activities and estimating the parameters of the student model may require enormous amount of data [5]. But we make the assumption that the student model, when available, allows the convergence of the Q-learning to an efficient sequencing policy.

Moreover, we propose a reward function that quantifies the student learning gain according to the student knowledge states inferred by the BKT model [4]. More precisely, we define the student's learning gain as the number of new knowledge components acquired by the student since the last recommanded learning activity. The reward function we propose aims to maximize the expectation of future learning gains. On the other hand, the domain model allows us to reduce the combinatorial explosion of the number of student knowledge states.

RL models need to be trained on student historical data to converge to a good sequencing policy [7]. However, in education, policy evaluation becomes challenging because of the experience is scarce and expensive and the data are sometimes unavailable. In this paper, we answer the issue of data availability by carrying out a first study on simulated students.
We first formalise the problem of instructional sequencing by defining the main elements of the Q-learning policy and the BKT student model. Then, we present our approach and focus on the contributions of the domain experts to reduce, on the one hand the combinatorial explosion of the student knowledge states and on the other hand to define the reward function. Finally, we present the study we carried out to evaluate the proposed approach and its results.

## 2 Reinforcement learning

The reinforcement learning (RL) problem is usually modeled as a Markov decision process (MDP) giving rise to a sequence of observed, states, actions and rewards: $s_0, a_0, r_1, s_1, a_1, r_2, s_2, ..., s_T$. The $s_t$ is the state of the environment, $a_t$ the action taken by the agent and $r_t$ the reward received by the agent at time-step $t$. A RL agent learns to decide actions in different states through trial and error strategy. RL algorithms can be mainly divided into two categories model-based and model-free. In the context of deciding learning activities, the objective is to explore the consequences of decisions on the students and we haven't any, a priori model of the optimal decision. Thus, the model-free methods are more adapted for the context of instructional sequencing. In this work, we focus on the Q-learning, a type of model-free RL algorithms. It relies on a Q-table that associates observed states with actions and a Q-function that maximizes a "reward function" received by the Q-learning agent from the environment after each action.

The Q-table is the key component of the Q-learning algorithm and it is used to calculate the expected maximum future rewards for each learning activity at each student knowledge state. The Q-table guides the Q-learning agent to choose the "optimal" learning activity for each student to maximize her learning gain. Each value of the Q-table is first initialized randomly and then learned iteratively via the Bellman recurrence equation:

$$ \underbrace{\text{New Q}(s, a)}_{\text{New Q-Value}} = \underbrace{Q(s, a)}_{\substack{\text{Immediate reward} \\ \text{learning rate}}} + \alpha \left[ \underbrace{R(s, a)}_{\substack{\text{Discount rate} \\ \text{learning rate}}} + \gamma \right] \underbrace{\max \underbrace{Q'(s', a')}_{\substack{\text{Maximum predicted reward, given \\ new state s' and all its possible actions a'}}}}_{\substack{\text{Discount rate}}} - Q(s, a) $$

Where $R(s, a)$ is the immediate reward received when selecting the action $a$ in the state $s$, $\alpha$ is the learning rate ($0 < \alpha \le 1$) and $\gamma$ is the discount rate ($0 < \gamma \le 1$), reflecting the importance of the immediate reward comparing to the future rewards.

## 3 BKT model

The BKT model [4] is a student modeling method. It is a two state hidden Markov model (see Fig.1) that is used to infer the student's mastery of a knowl-
edge component (KC). The BKT assumes that student knowledge is represented as a set of binary variables – one per KC (the skill is either mastered by the student or not). Observations in BKT are also binary: a student gets a problem (or a problem step) either right or wrong [14].

A student has an initial mastery parameter $L_0$ and at every practice opportunity (or observation), a student who has not mastered the KC has some probability of attaining mastery (the parameter $T$). If a student has mastered a KC, they will answer a question correctly unless they “slip” with some probability (the parameter $S$), and if the student has not mastered the KC, they can only guess correctly with some probability (the parameter $G$).

In BKT, each KC is modeled separately without considering any relationships between KCs. Other work on individualized BKT models [15] describes different approaches for defining and learning student-specific parameters. In this research, we use the Individualized BKT with student-specific $p(L_0)$ and $p(T)$ [4]. These specific parameters depend on the KC complexity and the student class (see 7.2).

The inference model of the BKT gives us a vector of real values (comprise between 0 and 1)—each value represents the probability of mastery for a KC. In the rest of the paper, this vector related to a student is named the knowledge state of the student.

<figure><img src="image_3.png" /><figcaption>Fig. 1. The BKT model and its parameters T, S and G</figcaption></figure>

# 4 Proposed approach

In this work, we aim to learn a sequencing policy that assigns learning activities to students in order to maximize their learning gains. Our contributions are the following:

1. we propose a domain-based method to reduce the risk of combinatorial explosion of the number of students' knowledge states,

2. we define a reward function that relies on the knowledge states inferred by the BKT model,

3. we evaluate the sequencing policy we propose by comparing it with two baseline approaches
# 5 Contributions of human expertise to the Q-learning function approximation

In this section, we present the contributions of domain experts to the Q-learning function approximation. In our case, we identify two major issues that can prevent the convergence of the Q-learning : the combinatorial explosion of the number of the Q-table states (usually called curse of dimensionality) and the definition of an irrelevant reward function.

On the one hand, when the state-action space is small enough, the iterative approximation of the Q-learning algorithm is proved to converge to the true Q-values [12]. However, the combinatorial explosion of the number of possible states in even a modest-size environment makes this table based implementation of Q-learning unfeasible. In our case, we can observe that there is a risk of combinatorial explosion of the number of the Q-table states when the number of the KCs increases. For example, if we have $n$ KCs in the domain model and for each KC we consider a binary random variable representing its mastery (1 if the KC is mastered by the student, 0 otherwise), we obtain $2^n$ knowledge states. Thus, the number of states increases considerably with the number of KC. To answer this issue, we propose an approach based on the domain model.

On the other hand, the definition of a relevant reward function is a challenged task because it guides the sequencing policy towards the objective [10], in our case, achieving efficiently the mastering the domain KCs by the students.

<figure><img src="image_4.png" /><figcaption>Fig. 2. Example of domain model (left graph) and competence structure (right graph).</figcaption></figure>

## 5.1 Competence structure

To answer the combinatorial explosion of the number of possible knowledge states, we ask domain experts to identify prerequisite relationships between the
KCs in order to reduce the number of possible knowledge states of the students. Two KCs X and Y are related by a prerequisite relationship X→Y if and only if the mastery of Y implies the mastery of X and the non mastery of X implies the non mastery of Y. Thus, given prerequisite relationships between KCs, some knowledge states are inprobable and thus considered as non admissible.

For instance, if we consider the domain model of the Fig. 2:

$\{a \to b, a \to c, b \to d, b \to e, c \to e, d \to f, e \to f\}$. The competence structure is obtained by deriving all the admissible knowledge states of the domain model. We can observe that all combinations of KC are not admissible. For instance, the knowledge state $\{a, d\}$ which means that both the KCs a and d are mastered whereas all others are not mastered, cannot be a knowledge state since the KC b has to be mastered before mastering the KC d.

Thus, only 10 knowledge states are admissible instead of $2^6$ possible knowledge states (6 is the number of KCs).

In summary, the more the KS are connected by prerequisite links, the less the number of knowledge states is.

As, we consider each knowledge state as an entry of the Q-table, considering the prerequisite relationships between the KCs allows to reduce considerably the size of this table.

# 6 Definition of the reward

The Q-learning agent performs an iterative process until reaching the knowledge state where all the KC are mastered by the student (the overlay approach). In each learning episode, the Q-Leaning selects a learning activity to present to the student, based on the Q-table and the $\epsilon$-greedy exploration/exploitation strategy. When the student answers the testing activity associated to the selected learning activity, the BKT model infers the new mastery of the KCs worked on the learning activity. Then, the new knowledge state is communicated to the Q-learning agent. Finally, the agent calculates the reward corresponding to the move from the previous knowledge state to the new knowledge state in order to update the Q-table entry according to the Bellman equation (see Fig. 3).

The reward function is defined as the following:

$$R(s, a) = \sum_{i=1}^{N} (s'_{i} - s_{i}) \quad \text{if } s'_{i} > s_{i}$$

where $s'$ is the new knowledge state of the student inferred by the BKT model after selecting the learning activity a and N the number of KCs. This reward function means that the reward depends on the number of new mastered KCs. More the observations allow an improving of the KCs mastery more the reward is significant. The cumulatives rewards quantify the learning gains of the students.

# 7 Evaluation

We evaluate our sequencing policy using simulated students. The evaluation consists on comparing the Q-learning(Ql) with two baseline approaches: random-
<figure><img src="image_5.png" /><figcaption>**Fig. 3.** Connection between the Q-learning and the BKT student model</figcaption></figure>

based approach (Ra) and expert-based approach (Ex). The three approaches serve to design a sequencing policy and aim to achieve efficiently the mastering of all KCs. In this evaluation, we are interested in the number of activities recommended to the student before mastering all KCs.

## 7.1 Random-based and expert-based approaches

To evaluate our approach *Ql* we compare it to two baseline approaches for designing a sequencing policy: Random-based approach (*Ra*) and Expert-based approach (*Ex*).

*Ra* is straightforward, we randomly select a learning activity by excluding the learning activities already proposed.

*Ex* is based on the competence structure presented in section 5.1. The principle of *Ex* is that as long as all the prerequisite KCs of a KC X have not been mastered, the learning activities about these KCs still recommended to the student. One all the prerequisite KCs are mastered, the system starts to recommend learning activities to work on X.

We note that for these two baseline approaches, we also use the BKT model to infer the knowledge state of the simulated student. This allows us to evaluate only the impact of the reinforcement learning as a strategy of instructional sequencing.

## 7.2 Simulated students

for the study, we generate two synthetic datasets in two different ways. On the one hand, we generate a dataset consisting of 20,000 simulated students that is used to learn the parameters of the BKT model for each KC. To do so, we first define three student classes with a probability distribution for each student to belong to one of these classes. Then, for each student class, we set the success of a student in an activity in function of four parameters inspired from the BKT
parameters: *prior*, *learn*, *guess* and *slip*. The parameters *prior* and *learn* depend on the complexity of the *KC* and the student class. The parameters *guess* and *slip* depend on the type of the performed activity (quiz, open-ended question, etc.). In addition and based on the prerequisite relationships between *KCs*, we have added the assumption that a student cannot answer correctly a testing activity on *X* without having first mastered enough all its prerequisite *KCs*. In this simulation, we generate data for 20 *KCs*, 50 prerequisite relationships and 100 activities for each *KC*. All these constraints for the data generation, allow us to have a sufficiently clear characterization of the simulated data.

The evaluation of the fitted BKT model obtains an average RMSE of 0.45180 and an average AUC of 0.710705.

On the other hand, we generate in real time student's interactions that are used to learn the sequencing policy with the *Ql* approach. Each time an activity is performed by the simulated student, an observation (right or wrong) is sent to the Q-learning agent and based on the current knowledge state of the simulated student. This observation is then used by the BKT model to update the knowledge state of the simulated student. In this way, the Q-learning agent receives iteratively the environment state and decides an activity to the simulated student. We note that students from the three classes are generated with fixed probabilities.

## 7.3 Results

Table 1 is a summary of results for the proposed approach *Ql* (a Q-learning based policy) and the two used baseline approaches: *Ra* (a random policy) and *Ex* (an expert-based policy). For each policy, we compute after one hundred executions the mean and the SD (standard deviation) of the number of activities proposed to the students before acquiring all *KCs*,

<table><caption>**Table 1.** The mean and the SD (standard deviation) of the number of activities proposed to the students before acquiring all *KCs*, after one hundred simulations. The total number of simulated activities is 2000 (20 *KCs* and 100 activities per *KC*)</caption><thead><tr><td>Sequencing policies</td><td>Mean</td><td>SD</td></tr></thead><tbody><tr><td>Random policy (Ra)</td><td>754</td><td>469.57</td></tr><tr><td>Expert-based policy (Ex)</td><td>516.54</td><td>19.66</td></tr><tr><td>Q-learning based policy (Ql)</td><td><b>479.54</b></td><td>49.28</td></tr></tbody></table>

The results show that the Q-learning policy is in average the most efficient even if it has a standard-deviation greater than the expert-based approach. This is explained by the random initialisations of the Q-table where some ones make longer the convergence time of the learning process.
The random policy gives the worst results, the standard-deviation between
the executions shows a big variations between the executions.

The expert based approach is less efficient to the Q-learning policy but very
close. It is probably due that certain prerequisite KCs are not necessary to master
some KCs. It may explain the increasing of the mean number for the expert
approach because of the increasing of the number of prerequisite relationships
and thus the inscreasing of the mandatory learning steps. But, we know that is
is quite hard to have a consensus on the domain model.

Moreover, we observe clearly in the learned Q-table that the Q-learning re-
produces most of the prerequisite relationships between the KC. This observation
is interesting because it may provide a solution to the cold-start issue of the Q-
learning when the system interacts with real students. Indeed, we can initialize
the Q-table with a dataset of simulated students before using the Q-learning on
real data.

8 Conclusion

In this research, we propose to use the Q-learning algorithm to decide the more
suitable next learning activity to recommand to the students. The sequencing
policy aims to improve efficiently the student knowledge state. Student knowl-
edge states are inferred dynamically by using the BKT student model.

The proposed approach poses the problem of the combinatorial explosion of
the student knowledge states. For that, a domain-based method is proposed to
reduce the number of the admissible knowledge states and thus the size of the
Q-table.

Based on the objective of improving efficiently the student knowledge states,
a reward function is defined.

We carried out a study on simulated data to evaluate the efficiency of the pro-
posed Q-learning based approach by comparing it with two baseline approaches:
random-based approach and expert-based approach. The results show that our
apporach is the most efficient one but very close to the expert-based approach.

There are several research directions for future work, in particular, to provide
evidence about the benefits of this approach by experimenting it on real data.

References

1. Aleven, V., McLaughlin, E.A., Glenn, R.A., Koedinger, K.R.: Instruction based on adaptive learning technologies. Handbook of research on learning and instruction 2, 522–560 (2016)

2. Bassen, J., Balaji, B., Schaarschmidt, M., Thille, C., Painter, J., Zimmaro, D., Games, A., Fast, E., Mitchell, J.C.: Reinforcement learning for the adaptive scheduling of educational activities. In: Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems. pp. 1–12 (2020)

3. Clement, B., Roy, D., Oudeyer, P.Y., Lopes, M.: Multi-armed bandits for intelligent tutoring systems. arXiv preprint arXiv:1310.3174 (2013)
4. Corbett, A.T., Anderson, J.R.: Knowledge tracing: Modeling the acquisition of pro-cedural knowledge. User modeling and user-adapted interaction 4, 253–278 (1994)

5. Doroudi, S., Aleven, V., Brunskill, E.: Where’s the reward? International Journal of Artificial Intelligence in Education 29(4), 568–620 (2019)

6. Efremov, A., Ghosh, A., Singla, A.: Zero-shot learning of hint policy via reinforce-ment learning and program synthesis. In: EDM (2020)

7. Mandel, T., Liu, Y.E., Levine, S., Brunskill, E., Popovic, Z.: Offline policy evalu-ation across representations with applications to educational games. In: AAMAS. vol. 1077 (2014)

8. Sen, A., Patel, P., Rau, M.A., Mason, B., Nowak, R., Rogers, T.T., Zhu, X.: Ma-chine beats human at sequencing visuals for perceptual-fluency practice. Interna-tional Educational Data Mining Society (2018)

9. Singla, A., Rafferty, A.N., Radanovic, G., Heffernan, N.T.: Reinforcement learn-ing for education: Opportunities and challenges. arXiv preprint arXiv:2107.08828 (2021)

10. Tessler, C., Mankowitz, D.J., Mannor, S.: Reward constrained policy optimization. arXiv preprint arXiv:1805.11074 (2018)

11. VanLehn, K.: Regulative loops, step loops and task loops. International Journal of Artificial Intelligence in Education 26, 107–112 (2016)

12. Watkins, C.J., Dayan, P.: Q-learning. Machine learning 8(3), 279–292 (1992)

13. Watkins, C.J.C.H.: Learning from delayed rewards (1989)

14. Yudelson, M.V., Koedinger, K.R., Gordon, G.J.: Individualized bayesian knowl-edge tracing models. In: Artificial Intelligence in Education: 16th International Conference, AIED 2013, Memphis, TN, USA, July 9-13, 2013. Proceedings 16. pp. 171–180. Springer (2013)

15. Yudelson, M.V., Koedinger, K.R., Gordon, G.J.: Individualized bayesian knowledge tracing models. In: International conference on artificial intelligence in education. pp. 171–180. Springer (2013)