Towards Scalable Adaptive Learning with Graph Neural Networks and
  Reinforcement Learning
Adaptive learning is an area of educational technology that consists in
delivering personalized learning experiences to address the unique needs of
each learner. An important subfield of adaptive learning is learning path
personalization: it aims at designing systems that recommend sequences of
educational activities to maximize students' learning outcomes. Many machine
learning approaches have already demonstrated significant results in a variety
of contexts related to learning path personalization. However, most of them
were designed for very specific settings and are not very reusable. This is
accentuated by the fact that they often rely on non-scalable models, which are
unable to integrate new elements after being trained on a specific set of
educational resources. In this paper, we introduce a flexible and scalable
approach towards the problem of learning path personalization, which we
formalize as a reinforcement learning problem. Our model is a sequential
recommender system based on a graph neural network, which we evaluate on a
population of simulated learners. Our results demonstrate that it can learn to
make good recommendations in the small-data regime.
Jean Vassoyan, Jill-Jênn Vie, Pirmin Lemberger
# Towards Scalable Adaptive Learning with Graph Neural Networks and Reinforcement Learning

###### Abstract

Adaptive learning is an area of educational technology that consists in delivering personalized learning experiences to address the unique needs of each learner. An important sub-field of adaptive learning is learning path personalization: it aims at designing systems that recommend sequences of educational activities to maximize students' learning outcomes. Many machine learning approaches have already demonstrated significant results in a variety of contexts related to learning path personalization. However, most of them were designed for very specific settings and are not very reusable. This is accentuated by the fact that they often rely on non-scalable models, which are unable to integrate new elements after being trained on a specific set of educational resources. In this paper, we introduce a flexible and scalable approach towards the problem of learning path personalization, which we formalize as a reinforcement learning problem. Our model is a sequential recommender system based on a graph neural network, which we evaluate on a population of simulated learners. Our results demonstrate that it can learn to make good recommendations in the small-data regime.

adaptive learning, learning path personalization, graph neural networks, reinforcement learning, recommender system

## 1 Introduction

Adaptive learning is an area of educational technology that focuses on addressing the unique needs, abilities, and interests of each individual student. This field emerged in the 1980s with the introduction of the first _Intelligent Tutoring Systems_ (ITS) and experienced major expansion in the 1990s. As described by T. Murray in [20], an ITS usually consists of four components: a _domain model_, a _student model_, an _instructional model_ and a _user interface model_. As we address the problem from an algorithmic point of view, we only focus on the first three models. The domain model is a representation of the knowledge to be taught; it often serves as a basis for the student model. The student model provides a characterization of each learner that allows to assess their knowledge and skills and anticipate their behavior. The instructional model takes the domain and student models as input to select strategies that will help each user achieve their learning objectives. This general structure allows ITSs to achieve many purposes (recommending exercises, providing feedback, facilitating memorization, etc.) while optimizing a variety of metrics (learning gains, engagement, speed of learning, etc.).

In this paper, we address the problem of learning path personalization with optimization of learning gains. This means that we look for a sequential recommender system that can provide each student with the right content at the right time (according to their past activity), in order to maximize their overall learning gains.

Towards this goal, "standard" approaches often require significant structuring of the domain model. This step is usually assisted by experts: they may be mobilized to tag educational resources, set up prerequisite relationships, draw up skill tables, etc. One example of such structuring is the Q-matrix [2] which maps knowledge components (KC) to exercises. These expert-based approaches present some serious practical limitations. First, they make it quite cumbersome to create resource sets, since each resource has to be properly tagged (sometimes with an extensive set of metadata). They also lead to poorly reusable recommender systems, since prerequisite relationships and skills maps are usually tailored to specific resource sets. This low reusability problem is often exacerbated by the modeling of resources/skills/KC as one-hot encodings [3, 21] which tie the model to a maximum number of resources/skills/KC it can handle. As a result, these approaches produce models that are not suitable for transfer learning. Our approach, on the other hand, is based on a graph neural network, which structure makes it possible to process data in a much more flexible way.

Our contributions in this paper are threefold. First, we introduce a new setting for learning path personalization and formalize it as a model-free reinforcement learning (RL) problem. Second, we present a novel RL policy that can leverage educational resource content and users' feedback to make recommendations that improve learning gains. The
proposed model has the advantage of being inherently scalable, reusable, and independent of any expert tagging. Third we evaluate our model on 6 semi-synthetic environments composed of real-world educational resources and simulated learners. The results demonstrate that it can learn to make good recommendations from few interactions with learners, thereby significantly outperforming the uniform random policy.

The rest of the paper is organized as follows. In Section 2, we relate our paper to prior research. In Section 3, we describe our setting, the assumptions we make and the problem we attempt to solve, which we formalize as a reinforcement learning problem. In Section 4, we present our novel RL policy. In Section 5, we describe our experimental setting and discuss our results. In Section 6 we address some limitations of our model and propose a few directions for future work. We finally conclude in Section 7.

## 2 Related Work

In recent years, several works have used reinforcement learning to address the problem of learning path personalization. Most of these RL approaches are model-based, as they rely on a predefined student model to simulate student trajectories. However, no student model is completely accurate, and the learned instructional policies may overfit to the student model. Doroudi et al. [7] have attempted to learn policies that provide a better reward no matter the student model chosen (i.e. robust policies). Azhar et al. [1] proposed a method to gradually refine the student model by adding features that maximize the reward.

Reward functions usually involve learning gains. Subramanian and Mostow [29] defined learning gains as average difference between posterior and prior latent knowledge. Lan and Baraniuk [15] proposed to learn a policy for selecting learning actions so that the grade on the next exam is maximized. Clement et al. [5] attempted to optimize an increase in success rate in recent time steps, they used an \(\varepsilon\)-greedy approach. Doroudi et al. [8] conducted a thorough review of the different reward functions used in instructional policies.

The closest to our setting is probably the approach proposed by Bassen et al. [3] which, like ours, does not rely on expert pre-labeling of educational resources. However, in the absence of compensation for this lack of information, their reinforcement learning algorithm requires a substantial number of learners to converge to an effective policy: about 1000 learners for a corpus of 12 educational resources. Moreover, in their framework, educational activities were represented as one-hot encodings and passed to the policy via a fixed-size vector. Therefore, this approach does not allow to work with an evolving corpus of educational resources (which is the case for most _e-learning_ platforms) nor to reuse the model on another set, unless it is completely re-trained.

In contrast, our approach leverages information from resource keywords which allows to achieve convergence in a relatively small number of episodes, while maintaining a high level of flexibility. This keyword-based approach was inspired by the work of Gasparetti et al. [12, 11]. Although the authors did not directly address the problem of learning path personalization, they outlined a method of feature extraction from textual resources that proved to be very successful in predicting prerequisite relationships.

## 3 Problem Formulation

### Description of the setting

Consider an _e-learning_ platform with a collection of educational resources which have been designed to cover a specific topic, for example "an introduction to machine learning". Consider a population \(\mathscr{P}\) of learners to be trained on this topic. The goal of learning path personalization is to be able to recommend a sequence of educational resources to each learner so as to maximize his overall _learning gains_. Therefore the resulting machine learning problem can be expressed in the following terms: given a large enough sample \(U\) of users from \(\mathscr{P}\), how can we train a machine learning model to make recommendations to users from \(U\) so as to generalize to the whole population?

In this paper, we work at the scale of short learning paths (\(\sim 1\) hour), which means that each learning session only consists of a few interactions between the learner and the ITS. One advantage of this setting is that it reduces the effects of memory loss: we assume that when a learner visits a new resource, what he learned from the previous ones is still in his working memory.

We first make a few assumptions about the learning sessions:

1. Each learner follows one learning path of equal length (i.e. same number of resources). The purpose of this assumption is primarily to simplify the notations as it can be easily relaxed without making major modifications to the model.
2. There is no interaction between the learner and the external world (no communication, no access to external resources). This makes it possible to work in the closed system {learner + ITS}. While incorrect in most cases, this assumption may be more reasonable in our setting than in a multi-day learning context.
3. We assume the existence of a feedback signal that provides information about user understanding of each resource. This signal can take three values: * (\(f_{<}\)): the user did not understand the resource * (\(f_{>}\)): the user understood, but found it too easy * (\(f_{\circ}\)): the resource was at the right level. In practice, such feedback can be obtained from self-assessment or more sophisticated test, and should be associated with an error margin to account for its imprecision. Nevertheless, in this study, we assume that each feedback is perfectly accurate.

A view of such a learning session is provided in Figure 1.

To further simplify the problem, we also adopt a few simplifying assumptions about the educational resources:

1. They are purely textual resources, written in natural language. We indeed consider that most educational
formats can be easily transcribed into text (transcript of a video, legend of a diagram, caption of an image etc.).
* They are _self-contained_, which means that they can be considered independently. This implies for example that they do not explicitly refer to each other. Although quite strong, this assumption is essential to prevent mandatory dependencies and foster diversity of learning paths.
* Each resource explains one or few concepts and has equivalent "educational value". This involves that each resource carries the same "amount" of knowledge.

Some examples of educational resources that satisfy these requirements are provided in Figure 4 of the Appendix.

Our goal with this work is to design a machine learning algorithm that can leverage learners' feedback to text-based educational resources to model their understanding of each concept, anticipate their reactions, and recommend resources that maximize their overall learning gains.

Since most _e-learning_ platforms are in constant evolution, our goal is not only to solve this problem but to do it in a flexible and scalable way. This means that the model should not require full retraining when new resources are added to (or removed from) the platform. Actually, it should be able to extrapolate to new resources what it learned from previous interactions. This suggests that the number of parameters of our model should not depend on the size of the corpus.

### Formalization

In this section, we formalize the problem described above as a reinforcement learning problem. We use the terms "user" and "learner" interchangeably to refer to any individual from the sample \(U\). Similarly, we refer to an educational resource with the terms "document" or "resource".

In the following, we denote: \(T\) the length of each learning session (identical for each user), \(\mathcal{D}\) the corpus of documents, \(d\) a document from \(\mathcal{D}\), \(u\) a user (or learner) from the sample \(U\), \(\mathbf{f}_{d}\) the feedback given by a learner on document \(d\).

The sequential recommendation problem defined above can be easily expressed as a reinforcement learning problem where: the agent is the recommender system, the environment is the population \(\mathcal{P}\) of students and each episode is a learning path. This problem can be formulated as a partially observable Markov decision process (\(\mathcal{S}\), \(\mathcal{A}\), \(\mathcal{O}\), \(\mathcal{T}\), \(\mathcal{R}\), \(\mathcal{Z}\)) where \(\mathcal{S}\) is the state space, \(\mathcal{A}\) is the action space, \(\mathcal{O}\) is the observation space, \(\mathcal{T}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]\) defines the conditional transition probabilities, \(\mathcal{R}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}\) is the reward function and \(\mathcal{Z}:\mathcal{S}\times\mathcal{A}\times\mathcal{O}\rightarrow[0,1]\) is the observation function. More precisely, in our setting:

* \(\mathbf{s}_{t}\in\mathcal{S}\) is the (unknown) knowledge state of the learner at step \(t\);
* \(\mathbf{a}_{t}\in\mathcal{A}\) is the document selected by the recommender system at step \(t\); we can write \(\mathbf{a}_{t}=\mathbf{d}_{t}\);
* \(\mathbf{o}_{t}\in\mathcal{O}\) is the observation made at step \(t\), which is a tuple of the selected document and the returned feedback: \(\mathbf{o}_{t}=(\mathbf{d}_{t},\mathbf{f}_{t})\);
* \(\mathcal{T}(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime})=\mathbb{P}(\mathbf{s}_{ t+1}=\mathbf{s}^{\prime}\mid\mathbf{s}_{t}=\mathbf{s},\mathbf{a}_{t}= \mathbf{a})\) is unknown, as it represents the impact of selecting document \(\mathbf{a}\) on learner's state \(\mathbf{s}_{t}\);
* \(\mathcal{Z}(\mathbf{s},\mathbf{a},\mathbf{o})=\mathbb{P}(\mathbf{o}_{t+1}= \mathbf{o}\mid\mathbf{s}_{t+1}=\mathbf{s},\mathbf{a}_{t}=\mathbf{a})\) is also unknown and represents the probability of observing \(\mathbf{o}\) in state \(\mathbf{s}\) after choosing document \(\mathbf{a}\);
* \(\mathcal{R}(\mathbf{s}_{t},\mathbf{a}_{t})\) is the learning gain of the user at step \(t\), which we define as follows: \[\mathcal{R}(\mathbf{s}_{t},\mathbf{a}_{t})=\mathbb{1}_{\{\mathbf{f}_{t}=f_{ \circ}\}}.\] (1) We indeed consider that only feedback \(f_{\circ}\) corresponds to an effective learning gain. We denote \(\mathcal{R}(\mathbf{s}_{t},\mathbf{a}_{t})=\mathbf{r}_{t}\) in the following.

To solve this problem, we need to find a policy \(\pi:\mathcal{O}\rightarrow\mathcal{A}\) that maximizes the expected return over each episode \(\eta\):

\[\pi^{*}=\operatorname*{arg\,max}_{\pi}\,\mathbb{E}_{\eta\sim\pi}\left[\,\sum _{t=1}^{T}\mathbf{r}_{t}\,\right]. \tag{2}\]

## 4 Our RL Model

A common approach to solve partially observable Markov decision processes (POMDP) is to leverage information from past observations \(\mathbf{o}_{1},\ldots,\mathbf{o}_{t}\) to build an estimation of \(\mathbf{s}_{t}\) which is then used to select the next action (illustrated in Figure 2). This boils down to encoding these observations into a latent space \(\mathcal{S}\). In our setting, this latent space contains all possible knowledge states for the learner, which is why we call it _knowledge space_ in the following.

### Knowledge space

While more compact than the observation space, the knowledge space should be informative enough to convey a relevant approximation of learner's knowledge.

We decided to structure this representation with the keywords of the corpus, denoted \((w_{1},\ldots,w_{M})\). We define a keyword as a word or group of words that refers to a technical concept closely related to the subject of the corpus. Some examples of keywords extracted from educational resources are provided in the Appendix. The keywords carry information about the concepts addressed by the documents and are therefore a good approximation of their pedagogical content.

Figure 1: A view of a learning session. In this example, the session length is \(T=4\). \(\mathbf{Actions}_{1},\mathbf{a}_{2},\mathbf{a}_{3},\mathbf{a}_{4}\) are the recommendations of the ITS. \(\mathbf{f}_{1},\mathbf{f}_{2},\mathbf{f}_{3},\mathbf{f}_{4}\) are the feedback signals returned by the user.
That is why we modeled the knowledge state of each learner as a collection of vectors \((\mathbf{w}_{1},\ldots,\mathbf{w}_{M})\) which represents his "understanding" of each keyword. We indeed consider that a keyword can be understood in multiple ways depending on the context in which it occurs, and a multidimensional vector can be a convenient way to capture this plurality. This is illustrated in Figure 2. From this perspective, the knowledge space \(\mathcal{S}\) can be defined as \(\mathcal{S}:=\underbrace{\mathbb{R}^{K}\times\cdots\times\mathbb{R}^{K}}_{M}\).

Note that we do not consider keyword extraction as a task requiring expert knowledge since it can be done by any creator of educational content and involves fewer skills than defining the knowledge components of a course. Moreover, it is mainly a pattern-matching task that can be automated through a keyword extraction algorithm [9, 22, 4].

### Policy

Following the previous considerations, the policy \(\pi_{\theta}\) should take a collection of observations \(\mathbf{o}_{1},\ldots,\mathbf{o}_{t}\) as input, encode it into the latent space \(\mathcal{S}\) and return a recommendation for the next document \(\mathbf{d}_{t}\). We emphasize that this function should also meet the aforementioned flexibility and scalability requirements.

A natural way to model the relationship between documents and keywords is to build a bipartite graph \(\mathcal{G}=(\mathcal{V}_{\mathcal{D}},\mathcal{V}_{\mathcal{W}},\mathcal{E})\), where \(\mathcal{V}_{\mathcal{D}}\) is the set of _document_ nodes, \(\mathcal{V}_{\mathcal{W}}\) is the set of _keyword_ nodes and \(\mathcal{E}\) is the set of edges, with \((v_{d},v_{w})\in\mathcal{E}\) if the document \(d\) contains the word \(w\).

We chose to use a graph neural network (GNN) as a policy. GNNs are quite convenient for this task as they allow to enrich node features with information about their extensive neighborhood, through message-passing. Therefore, documents (respectively keywords) that share a large number of keywords (respectively documents) will also have similar embeddings. This allows to build keyword embeddings that contain information about feedback from neighboring documents \((\mathbf{o}_{1},\ldots,\mathbf{o}_{t}\rightarrow\hat{\mathbf{s}}_{t})\). Message-passing can also be used the other way around, from keywords to documents, to build embeddings that inform about the relevance of each document according to the estimated knowledge state \((\hat{\mathbf{s}}_{t}\rightarrow\mathbf{a}_{t})\). Another significant advantage of GNNs is that their number of parameters does not depend on the size and structure of the graph, which makes them highly flexible and scalable.

Multiple options are possible for the initial node features. For keyword nodes, pre-trained word embeddings are a natural choice. As for the document nodes, a simple null vector is sufficient. However one may choose to include extra information about the documents if it is available (type of document, format, length etc.). We denote as \((\mathbf{x}_{w})_{w\in\mathcal{V}_{\mathcal{W}}}\) and \((\mathbf{x}_{d})_{d\in\mathcal{V}_{\mathcal{D}}}\) the initial feature vectors of keyword and document nodes.

In our model, we adapted a version of GAT (graph attention networks) [32] to the heterogeneity of our bipartite graph:

\[\forall d\in\mathcal{V}_{\mathcal{D}},\;\mathbf{h}_{d}^{(\ell+1)} =\sigma\left(\sum_{w\in\mathcal{N}(d)}\alpha_{dw}^{(\ell)}W_{D}^{ (\ell)}\mathbf{h}_{w}^{(\ell)}+B_{D}^{(\ell)}\right) \tag{3}\] \[\forall w\in\mathcal{V}_{\mathcal{W}},\mathbf{h}_{w}^{(\ell+1)} =\sigma\left(\sum_{d\in\mathcal{N}(w)}\alpha_{wd}^{(\ell)}W_{W}^{ (\ell)}\mathbf{h}_{d}^{(\ell+1)}+B_{W}^{(\ell)}\right) \tag{4}\]

\(\mathbf{h}_{d}^{(\ell)}\in\mathbb{R}^{K}\) is the embedding of node \(d\) at \(\ell\)th layer, with \(\mathbf{h}_{d}^{(0)}=\mathbf{x}_{d}\). \(\mathcal{N}(d)\) is the set of neighbors of node \(d\) in the graph. \(\alpha_{dw}^{(\ell)}\) is a _self-attention_ coefficient, detailed in the Appendix. \(\sigma(\cdot)\) is the ReLU activation function (rectified linear unit). \(W_{W}^{(\ell)}\), \(W_{D}^{(\ell)}\), \(B_{W}^{(\ell)}\) and \(B_{D}^{(\ell)}\) are trainable parameters. This back-and-forth mechanism between documents and keywords allows to learn distinct filters for each node type (document or keyword), effectively addressing the graph's heterogeneity. In the following, we refer to equations (3) and (4) as _bipartite GAT layers_ and denote them (\(\text{KW}\xrightarrow{(3)}\text{DOC}\)) and (\(\text{DOC}\xrightarrow{(4)}\text{KW}\)). Note that they can be chained one after the other.

We define our first block of bipartite GAT layers as follows:

\[\text{BLOCK1}\;=\;\text{KW}\xrightarrow{(3)}\text{DOC}\xrightarrow{(4)}\text {KW}\xrightarrow{(3)}\text{DOC}. \tag{5}\]

After this block, document embeddings \((\mathbf{h}_{d}^{(2)})_{d\in\mathcal{V}_{\mathcal{D}}}\) contain information about keywords from their extended neighborhood. Using a Hadamard product, we enrich these embeddings with user feedback:

\[\mathbf{h}_{d}^{(\varphi)}=\mathbf{h}_{d}^{(2)}\odot\mathsf{MLP}_{K_{d} \to K}(\mathbf{f}_{d}) \tag{6}\]

\(\mathbf{h}_{d}^{(2)}\) and \(\mathbf{h}_{d}^{(\varphi)}\) are the embeddings of document \(d\) before and after adding the feedback. \(\mathbf{f}_{d}\) is an encoding of user's feedback on document \(d\), which is passed through a multilayer perceptron (MLP). We use a "not visited" feedback for the documents that the learner has not yet visited.

After doing this operation on each document node, we apply another block of bipartite GAT layers:

\[\text{BLOCK2}\;=\;\text{DOC}\xrightarrow{(4)}\text{KW}\xrightarrow{(3)}\text {DOC}. \tag{7}\]

Operation (4) allows to enrich keyword embeddings with feedback from neighboring documents, which carry information about user's understanding. We consider these embeddings as a good approximation of learner's knowledge state, which is why we define \(\hat{\mathbf{s}}_{t}:=(\mathbf{h}_{w}^{(2)})_{w\in\mathcal{V}_{\mathcal{W}}}\). The final GAT layer (3) maps \(\hat{\mathbf{s}}_{t}\) to documents for the next recommendation.

Figure 2: Up, a view of common policy architecture to solve POMDP. Down, this architecture applied to our setting.
Before assigning probabilities to each document in the final step, we enrich document embeddings by incorporating information about the remaining time in the session, which, as we observed, slightly improved the performance of the model:

\[\mathbf{h}_{d}^{(\tau)}=\mathbf{h}_{d}^{(3)}\odot\mathsf{MLP}_{K_{\tau}\to K}( \Delta_{t}) \tag{8}\]

\(\mathbf{h}_{d}^{(3)}\) and \(\mathbf{h}_{d}^{(\tau)}\) are the embeddings of document \(d\) before and after adding the remaining time. \(\Delta_{t}=T-t\) is an encoding of the remaining time (or remaining steps) at step \(t\).

Eventually, the embeddings \(\mathbf{h}_{d}^{(\tau)}\) are passed through an MLP to assign a score to each document. These scores are converted into probabilities via a softmax over all document nodes (further details in the Appendix):

\[\pi_{\theta}\left(d\mid\mathbf{o}_{1},\ldots,\mathbf{o}_{t}\right)=\underset {\mathcal{V}_{D}}{\text{softmax}}\left(\mathsf{MLP}_{K\to 1}(\mathbf{h}_{d}^{( \tau)})\right). \tag{9}\]

The full architecture of the policy is illustrated in Figure 3.

### RL Algorithm

As our policy selects the next action directly from observations, it belongs to the _policy-based_ reinforcement learning paradigm, especially the _policy gradient_ methods. The latter make it possible to maximize the expected return by optimizing directly the parameters of \(\pi_{\theta}\) through gradient descent. We chose the REINFORCE algorithm [31] for its simplicity. At the end of each episode, \(\pi_{\theta}\) is updated as follows:

\[\forall t\in[1,T],\quad\theta\leftarrow\theta+\lambda\nabla_{\theta}\log\pi_{ \theta}\left(s_{t},a_{t}\right)v_{t} \tag{10}\]

with \(\lambda\) the learning rate and \(v_{t}=\sum_{t^{\prime}=t}^{T}\gamma^{t^{\prime}-t}r_{t^{\prime}}\) the return of the episode from step \(t\).

Note that we could learn our policy using more sophisticated RL algorithms like actor-critic, which usually has lower variance. However, it is likely that the current architecture would provide a poor state value function as it only operates at the scale of node neighborhoods and does not have a "global" view of the graph. Some changes in this architecture might nevertheless be done to process information at a larger scale, as discussed in Section 6.

## 5 Experiments

Given the complexity of conducting mass experiments on real learners, we chose to evaluate our model in an environment made up of semi-synthetic data. Our implementation is written in Python and is available on GitHub1. We also provided the hyperparameters of our model in Table 4 of the Appendix.

Footnote 1: [https://github.com/jvasso/graph-rl4adaptive-learning](https://github.com/jvasso/graph-rl4adaptive-learning)

### Experimental setting

#### Linear corpus

We introduce what we call a "linear" corpus. Starting from a regular course divided into sections and subsections, we treat each subsection as one document. The corpus resulting from this decomposition is "linear", in the sense that it was designed to be followed in a single, pre-defined order, which is identical for each learner. Therefore, it leaves practically no room for personalization. Six corpora were constructed this way: three about data science (1-3) and three about programming (4-6). They were all built from courses taken from a popular _e-learning_ platform.

For the purpose of our experiments, we have chosen to tag keywords "by hand" to avoid introducing any noise in the results. Our methodology was quite simple: for each document, we collected keywords referring to technical concepts related to the topic of the course. Table 1 presents some key statistics about each corpus and their associated bipartite graphs. Note that the graph of corpus 5 is disconnected: indeed, one of its documents only contains keywords that do not appear in any other document. Despite significantly complicating the task for a diffusion model like ours, we have chosen to keep this corpus for our experiments.

#### Simulated learners

Since each corpus has been designed to be explored in a single pre-defined order, we assume that the only way to

\begin{table}
\begin{tabular}{l r r r r} \hline corpus & \# doc & \# kw & \# edges & diameter \\ \hline Corpus 1 & 33 & 68 & 154 & 10 \\ Corpus 2 & 11 & 31 & 62 & 6 \\ Corpus 3 & 19 & 39 & 83 & 8 \\ Corpus 4 & 28 & 55 & 113 & 8 \\ Corpus 5 & 18 & 41 & 66 & \(\infty\) \\ Corpus 6 & 20 & 45 & 143 & 6 \\ \hline \end{tabular}
\end{table}
Table 1: Key statistics of each corpus

Figure 3: The architecture of our policy network on a 3-document corpus
understand it is to follow this order scrupulously. Therefore we have decided to simulate the behavior of learners in this very simple way: as long as the policy recommends documents in the right order, the learner returns the feedback (\(f_{\circ}\)). Conversely, each time the algorithm recommends a document too early or too late, the learner returns the feedback (\(f_{<}\)) or (\(f_{>}\)). A detailed example is given in the Appendix.

Since our simulated learners have a straightforward behavior, the purpose of this experiment is not to evaluate the personalization or generalization capabilities of our model, but to assess its ability to grasp the structure of a corpus, by finding its original order in a reasonable number of episodes (i.e. a few learners). While trivial at first glance, this task can be quite difficult for an RL agent in the small-data regime. Besides, each corpus contains some parts that are independent of each other which suggests that in practice, multiple learning trajectories might be understandable to real learners. From this perspective, the "strict" feedback of our simulated learners can distort the real nature of the relationships between resources and make the task more difficult for our recommender system.

_Policy_

In our experiments, we compared 3 different policies. The first one is the uniform random policy. The second one is our policy with one-hot-encodings as keyword features. The third one is our policy with Wikipedia2Vec embeddings [34] as keyword features. Wikipedia2Vec embeddings are quite suitable for our task as they contain encyclopedic information about the relationship between words and entities. They were derived from a skip-gram model trained on a triple objective, which is detailed in the Appendix. We used null vectors as document features for each policy.

_Training_

In each experiment, the maximum achievable return is equal to the size of the corpus. We set the horizon \(T\) to the size of the corpus to make sure that only an optimal policy (i.e. one that makes no "mistake") can reach this return. In this setting, the return of the random policy follows a binomial distribution with parameters (\(T\), \(\frac{1}{T}\)). Therefore its expected return is 1 for each episode. We also set the discount factor \(\gamma=0\) during training because in this very specific setting, the best action at each step \(t\) can be learned from immediate reward. We trained our model from scratch over 50 episodes (\(\sim\) 50 students) for each corpus, with a constant learning rate.

### Results

Since the REINFORCE algorithm has quite a high variance, we averaged each episodic return over 25 random seeds. The resulting learning curves are shown in Figure 6 of the Appendix and the last episodic returns (measured at 50\({}^{\text{th}}\) episode) are reported in Table 2.

From these curves, one can notice that despite the small-data regime and the choice of a sub-optimal RL algorithm (the REINFORCE algorithm is known to be quite unstable and sample-inefficient), our agent succeeded in recovering a significant part of the original order of each corpus. Most of the time, it achieved average return over 10 whereas the random policy was stuck in an expected return of 1.

Best performance was achieved on Corpus 2. Indeed, it is the only one for which our model managed to reach the maximum achievable return most of the time. This may be partly due to the small number of documents in this corpus. However, we stress that the number of documents alone is not a sufficient feature to account for the variability of the results. For instance, corpora 3 and 6 have a nearly similar number of documents, but our model performed very differently on these two corpora. Moreover, in the case of the Wikipedia2Vec approach, it is not guaranteed that a large corpus should be more difficult than a small one, since the episodes are shorter for small corpora and therefore the algorithm has fewer steps to grasp the geometrical structures in the distribution of Wikipedia2Vec embeddings.

The diameter of the graph may also impact the performance of the model. Indeed, Corpus 2 is again the one with the smallest diameter, which may have helped the model to determine the relationships between documents and keywords more quickly. However, this must be balanced with the results on Corpus 6, on which our model performed far worse (in terms of normalized return) despite equal diameter.

Another noticeable result is the one of Corpus 5. We remind that this corpus was the only one to be disconnected. Actually, it was disconnected at the 11\({}^{\text{th}}\) document, which is consistent with the performance of the model: indeed, episodic return lower than 10 indicates that it failed to make recommendations beyond the 10\({}^{\text{th}}\) document. This can be explained quite simply: since this document is disconnected from the rest of the graph, it does not benefit from message-passing and therefore receives no information about other documents feedback.

Eventually, one cannot ignore the extremely high variance of the episodic return for almost all corpora (except for Corpus 2). This is partly due to the choice of the REINFORCE algorithm, which is known for its high instability.

_Ablation study_

We conducted an ablation study to analyse the contribution of Wikipedia2Vec embeddings compared to simple one-hot encodings. Even though the approach with embeddings performed significantly better on each corpus, the high error margins and the similarity between trends suggest that our model was not truly able to leverage high level information

\begin{table}
\begin{tabular}{l c c} \hline \hline Corpus & Wikipedia2Vec & One-hot encodings \\ \hline Corpus 1 & \(\mathbf{16.48\pm 2.66}\) & \(13.36\pm 1.74\) \\ Corpus 2 & \(\mathbf{10.84\pm 0.14}\) & \(10.28\pm 0.37\) \\ Corpus 3 & \(\mathbf{14.40\pm 1.31}\) & \(11.68\pm 1.13\) \\ Corpus 4 & \(\mathbf{15.16\pm 0.90}\) & \(12.52\pm 0.98\) \\ Corpus 5 & \(\mathbf{9.80\pm 2.13}\) & \(7.56\pm 1.83\) \\ Corpus 6 & \(\mathbf{11.24\pm 1.52}\) & \(8.24\pm 0.84\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Comparison between episodic returns when using Wikipedia2Vec and one-hot encodings as keyword features
about the relationships between Wikipedia entities. Instead, it is more likely that it simply "overfit" to each corpus. This lack of generalization is not a problem in the setting of our experiment but can be a serious issue in transfer learning scenarios and therefore needs to be addressed.

## 6 Limitations and Future Work

### Size and structure of the graph

All of our experiments have been conducted on small graphs (less than \(\sim\) 100 nodes). However, it is likely that our model would struggle a little more on larger graphs as the receptive field of each node accounts for a smaller fraction of the graph in such case. Besides, it is not possible to increase the depth of a GNN indefinitely because of the over-smoothing problem [14, 33, 16]. Therefore, it is likely that these embeddings alone would not be sufficiently informative to allow for long-term planning. This limitation can be addressed with down- and upsampling methods such as pooling and unpooling operations on graphs, which make it possible to process information at multiple scales [6, 28, 35]. It can also be addressed with planning techniques such as Monte Carlo Tree Search, which has demonstrated great performance in combination with deep RL techniques [23, 26, 27].

As we saw in subsection 5.2, there is also an issue with disconnected graphs since our model failed to make predictions beyond the disconnected document node in Corpus 5. One possible solution could be to slightly modify the structure of the graph, for example through link prediction based on keyword embeddings.

Eventually, it is important to note that we tested our approach on corpora related to engineering topics -- machine learning and programming -- which keyword distributions might be quite similar (cf. Figure 5 in the Appendix). Yet, corpora related to different topics may have completely different keyword distributions. Therefore, it would be worth comparing the performance of the model on a wider range of subjects in the future.

### Variance and sample efficiency

As stated in Section 5, our approach suffers from high variance, partly due to the choice of the REINFORCE algorithm. Some other on-policy methods have demonstrated great success in reducing variance [24, 25, 18]. Nevertheless, these approaches remain generally not very sample-efficient. To improve sample-efficiency, it is quite common to use off-policy algorithms as they allow to reuse past experience [19, 17, 13]. However, as stated in Section 4, the implementation of an approximate Q-value function with a GNN is not trivial as it requires to leverage information at the scale of the entire graph, which involves modifications in the model. Another alternative is to use a model-based reinforcement learning algorithm (MBRL) [30, 23]. As they allow to learn a model of the environment (i.e. a model that predicts the next observations and rewards), MBRL techniques enable to reuse past experience and learn from a richer signal than the reward signal alone. Therefore, they are usually much more sample-efficient than model-free RL techniques. These approaches might be more appropriate in our case, as a local model like a GNN may more easily predict immediate feedback than the (long-term) _value_ of a state-action pair.

### Interpretability

One of the main limitations of our approach is its lack of interpretability. Ideally, an ITS would not only provide a personalized learning experience but also inform the learner about their progress and level of understanding, in order to encourage self-awareness and self-regulation. This is usually done with an _open learner model_. However, like most deep learning approaches, our recommender system is a black-box model and does not allow for easy interpretation. Yet, we hypothesize that the estimated knowledge state \(\hat{\mathbf{s}}_{t}\) does not only contain semantic information about keywords but also about the way they were understood by the learner. Therefore, future work may consist in projecting these keyword embeddings into lower dimensional space to visualize their evolution throughout learning sessions.

### Reusability

We designed a model that is flexible enough to be _theoretically_ capable of transferring its knowledge from one corpus to another. However, this is only possible if the model has managed to capture high-level information that is common to all corpora. Unfortunately, our experiments do not allow to truly evaluate the transfer learning capabilities of our model. However, since it seems to overfit to the structure of each corpus, it might not have learned that much about the high-level relationships in the distribution of Wikipedia2Vec embeddings. Therefore, transfer learning might not be very effective in this case. Future directions to reduce overfitting may consist in applying regularization techniques to GNN (such as node dropout), or using training techniques that push the model to learn higher-level knowledge, such as meta-learning for RL [10].

## 7 Conclusion

In this paper, we presented a new model for learning path personalization, designed to be reusable and independent of any expert labeling. We demonstrated its ability to learn to make recommendations in 6 semi-synthetic environments made-up of real-world educational resources and simulated learners. Since this model is theoretically capable of transferring its knowledge from one corpus to another, it is a first step towards an approach that could considerably reduce the cold-start problem. Future work will investigate its performance in the context of transfer learning and with real students.

## 8 Acknowledgments

We would like to warmly thank Vincent Francois-Lavet from VU Amsterdam who gave us some great advice on the formalization of the reinforcement learning problem. We would also like to thank Nicolas Vayatis, Argyris Kalogeratos (Centre Borelli), Nathanael Beau and Antoine Sailenfest (one-point) for their insightful reviews of the paper.
