EduQate: Generating Adaptive Curricula through RMABs in Education Settings

We regret that Reviewer MTkZ did not find our work to be a meaningful contribution. We hope that our responses have addressed the reviewer's concerns. We welcome the opportunity for further discussion to clarify any doubts and provide additional insights into our work. Additionally, we would like to address the weaknesses mentioned by the reviewer.

Weaknesses

1. On generating groupings in experiments:
   The Junyi and OLI datasets categorize each exercise in their question banks into topics, which we exploit to group the exercises. Additionally, Junyi provides expert ratings of similarities between questions, which we use to further augment the groupings. Further details on deriving the student models can be found in Appendix D (lines 474-489). We agree that this important detail should be clarified in the main text, and we will include it in future iterations.
   Regarding the number of topics, we provide an ablation study in Appendix E, which examines the simulated and highly constrained situation where $N_{topics}$ = {30,40}. We show that as $N_{topics}$ approaches N, the EdNetRMAB can be approximated to a traditional RMAB, where arms are independent of each other (Figure 4). In such cases, all algorithms perform in a highly unstable manner, as seen in Table 3 of the original paper. In contrast, under realistic scenarios generated from the real-world datasets Junyi and OLI, EduQate outperforms all other algorithms (Table 1 of the main text).

2. On binary state spaces:
   We agree with the reviewer that having a binary state space is a limiting factor of our work. Even though knowledge states can be complex and continuous, these are not observable and requires many assumptions to model. The observations are only at the level of answers to questions posed and these are binary. The complex knowledge states would have to be learnt based on the binary observations received over time. While we consider only single step observation here, in the future, we can consider multi-step observations to reason about this partial observability (of the knowledge state). We wish to point out that even with single step observation where we consider future impact and interrelationships, we are able to outperform existing methods.

3. On EdNetRMABs:
   We provide an illustration of EdNetRMABs in the attached PDF, Figure 1. Additionally, we invite the reviewer to refer to Section 3.1 for full details on EdNetRMABs, which we consider one of the core contributions of this work. We have made every effort to detail it thoroughly. We are happy to address any confusion and provide additional clarifications if needed.

We thank the reviewer for their feedback and aim to address them. We thank the reviewer for pointing out formatting errors and will clarify them in the future iteration.

Questions

1. On simplified modelling:
   There seems to be a misunderstanding here. In our formulation of EdNetRMABs, arms only maintain 2 states - learned or unlearned. Our key distinction between classic RMABs and EdNetRMABS is the introduction of inter-related arms, and pulling an arm results in neighboring arms to be semi-active. When the actions have been selected, EdNetRMABs perform a rollout and neighboring arms will transit to the new state with $P(s’ | s, a = 1)$. We hope this clarifies any confusion.

2. On Bidirectional Relationships between knowledge points:
   While there are some earlier works regarding identifying pre-requisite and recommending educational content in the designed sequential order (e.g. Chang, Hsu & Chen, 2015), our work primarily focuses on topic groups and bidirectional relationships as a general case. In reality, it is difficult to isolate unidirectional relationships when learning education content: learning prerequisite content enhances learning in future content, while mastery over succeeding content may reinforce knowledge in prerequisite content. However, we do agree that learning advanced content without proper foundational knowledge will lead to the reverse learning effect that the reviewer described, and presents an interesting direction for future work.
   Finally, we wish to point out that EdNetRMABs can be easily extended to unidirectional structure, where $\phi_i \neq \phi_j$ for $j ∈ \phi_i$, and EduQate should operate similarly under such conditions.

3. On User Experience:
   We thank the reviewer for their suggestion regarding a user experience study, which we plan to leave for future work. In this work, we primarily focused on introducing a new RMAB and an approach to solve it, emphasizing theoretical credibility and rigor before implementing it in real-world settings.

4. On scalability issues, and why we did not choose Deep Q-Learning:
   Modeling such problems in RL is not trivial, as the state and action spaces grow combinatorially. If there are 100 arms (like in our real world datasets), then the state space is 2^100. The key advantage of RMABs is that they can do independent reasoning across the arms through Whittle index type approaches (thereby avoiding the significant combinatorial complexity).
   Deep Q-learning, while popular, suffers from the same issues that factored MDPs (Green et al (2011)) also suffers from. In both cases, the joint state space must be jointly considered for learning to take place. RMABs and EduQate however, can train in a decentralized settings, where update to each arm are independent.

5. Regarding sample sizes and how $N=100$:
   For both datasets, we selected the top 100 exercises with the most student interactions to create our student models (lines 271-272). This decision was made to ensure the development of realistic student models. For exercises with insufficient student interaction data, the resulting transition matrix was not meaningful. Specifically, some exercises were either solved on the first try by all students who attempted or never solved at all, resulting in an extreme transition matrix that is unlikely to represent real-world student behavior.
   For reference, N for the full Junyi and OLI Statics dataset were 837 and 300 respectively.

6. Regarding $IB$ as a metric:
   We provide the Equation for IB here for the reviewer's convenience. $IB_{Random,EQ}(\pi) = \frac{E_{\pi}(R(.)) - E_{Random}(R(.))} {E_{EQ}(R(.)) - E_{Random}(R(.))}$ Note that when $\pi$ = EduQate, the numerator is equal to the denominator, resulting in 1.0. Our intention for $IB$ was a champion-challenger metric, where we compare EduQate (the champion model) versus the other baselines (challenger).
   In regard to the results, a negative value signifies that the baseline policy performs worst than the random policy, while a low positive value signifies extremely low performance when compared to EduQate. We acknowledge that the statement can be confusing, and have proposed an alternative definition of IB to ease the confusion: $IB_{Random}(\pi) = \frac{E_{\pi}(R(.)) - E_{Random}(R(.))} {E_{Random}(R(.))}$ We have updated the results with the new definition in the PDF attached.

Thanks for the response.

We thank the reviewer for the valuable feedback and the formatting concerns will be fixed.

Questions

1. On implementing more RL baselines:
   Please note that a key component of problems of interest are the presence of the arms (topics). Modeling such problems in RL is not trivial, as the state and action spaces grow combinatorially. If there are 100 arms (like in our real world datasets), then the state space is 2^100. The key advantage of RMABs is that they can do independent reasoning across the arms through Whittle index type approaches (thereby avoiding the significant combinatorial complexity). We discuss Green et al. (2011) in the related works section and justify the advantages of RMABs over factored MDPs (lines 95-99) with regards to the scalability. Furthermore, as supported by Reviewer 4CnK, bandits remain a core model behind today's learning platforms, which this work aims to enhance. In this work, we have devised a novel RMAB model, which can be leveraged upon by education settings for valuable personalized education.

2. On issues of fairness and ensuring all arms are fairly selected:
   We agree that the current work does not directly consider fairness across topics. We understand the reviewer's concern and looked through works on Fairness in RMABs that can be adapted to our setting. Please note that it is feasible to employ (with modifications) the work by Li and Varakantham (2023), citation number 14 to enable their proposed soft fairness constraint in EdNetRMABs.

3. On the claims and expressions:
   There is a typing error in Equation 5, where it should follow Equation 1: $\lambda_i = Q(s_i, a_i=2) - Q(s_i, a_i=0) + \sum_{j\in\phi_i^{-}}(Q(s_j, a_j=1) - Q(s_j, a_j=0))$
   We mistakenly replaced $Q(s_i, a_i=2)$ with $Q(s_i, a_i=1)$. We rewrite the Equation 5 to make it easier to read:

$\lambda_i \geq \lambda_j$ $Q(s_i, a_i=2) - Q(s_i, a_i=0) + \sum_{p\in\phi_i^{-}}(Q(s_p, a_p=1) - Q(s_p, a_p=0)) \geq Q(s_j, a_j=2) - Q(s_j, a_j=0) + \sum_{q\in\phi_j^{-}}(Q(s_q, a_q=1) - Q(s_q, a_q=0))$ $Q(s_i, a_i=2) + \sum_{p\in\phi_i^{-}}(Q(s_p, a_p=1))+Q(s_j, a_j=0)+ \sum_{q\in\phi_j^{-}}(Q(s_q, a_q=0)) \geq Q(s_j, a_j=2) + \sum_{q\in\phi_j^{-}}(Q(s_q, a_q=1))+ Q(s_i, a_i=0)+ \sum_{p\in\phi_i^{-}}(Q(s_p, a_p=0))$

• When arm $i$ and arm $j$ are not connected, but group $\phi_i$ and $\phi_j$ has overlap, i.e., $\phi_i \cap \phi_j \neq \emptyset$. In this case, we add $\underset{z\notin \phi_i \wedge z\notin \phi_j}{\sum} Q(s_z, a_z=0) - \sum_{z\in \phi_i \cap \phi_j} Q(s_z, a_z=0)$ on both sides, we can have the left side(Equation 9):

$Q(s_i, a_i=2) + \sum_{p\in\phi_i^{-}}(Q(s_p, a_p=1))+Q(s_j, a_j=0)+ \sum_{q\in\phi_j^{-}}Q(s_q, a_q=0) + \underset{z\notin \phi_i \wedge z\notin \phi_j }{\sum} Q(s_z, a_z=0) - \sum_{z\in \phi_i \cap \phi_j} Q(s_z, a_z=0)$ $= Q(s_i, a_i=2) + \sum_{p\in\phi_i^{-}}(Q(s_p, a_p=1))+\ \sum_{q\in\phi_j}Q(s_q, a_q=0) + \underset{z\notin \phi_i \wedge z\notin \phi_j }{\sum} Q(s_z, a_z=0) - \sum_{z\in \phi_i \cap \phi_j} Q(s_z, a_z=0) (\text{Combined the third with the fourth term})$ $= Q(s_i, a_i=2) + \sum_{p\in\phi_i^{-}}(Q(s_p, a_p=1))+\sum_{q\notin\phi_i}(Q(s_q, a_q=0)) (\text{Combined the last three terms})$ $= Q(**s**,**a**=\mathbb{I}_{ \{ i=2 \} })$

We revised $Q(**s**,**a**=\mathbb{I}_{i})$

to $Q(**s**,**a**=\mathbb{I}_{\{i=2\}})$ to more clearly denote the action of selecting only arm $i$.
For brevity, we do not include the full proof here, and will correct the errors in future iteration.

5. On limitations of mapping knowledge points, cold-start problems, and time factors:
   In this work, we have addressed several limitations of our method, particularly the cold-start problem, for which we have attempted to circumvent by proposing Experience Replay (lines 185-191). An ablation study in Appendix E.2 demonstrates that EduQate achieves reasonably good results in fewer than 100 episodes.
   Next, regarding methods to derive groupings for knowledge points, we briefly discuss data mining methods in lines 100-104, which focus on deriving relationships between learning content. Our work leverages these works to create the EdNetRMABs and to enhance the learning experience of students.
   Finally, once Q-learning converges and is applied in the real world, it is equivalent to a hashmap retrieval operation with a time complexity of O(1). In this regard, we do not think that the time complexity of EduQate will be a major issue in the learning experience of the student. The number of episodes required for Q-learning convergence is discussed in Appendix E.2 as well.

We thank the reviewer for the positive feedback and comments. We address some of their questions and concerns below:

Questions

1. Can EduQate's recommendations be easily interpreted?
   Reviewers point on interpretability is well noted. Given that RMABs are typically simple models, where arms have only few states (good progress, bad progress etc.) and Whittle index indicates the potential for improvement on that arm, they are very amenable to providing interpretations. For these interpretations to be deeper and meaningful, we also need to explain why the Whittle index takes on a certain value . We can potentially build from work on interpretability in MDPs, but unfortunately, this is non-trivial and difficult for us to show results before the end of the rebuttal period.

2. Are there any potential ethical implications of using EduRMABs and EduQate in education?
   The current EdNetRMABs require the specification of inter-item relationships. Without a learning-based method or end-to-end algorithm to learn these relationships and inform EdNetRMABs, it is possible for bad actors to withhold exposure to certain educational materials from specific groups.
   As with other educational tools, EdNetRMABs are intended to be applied to any domain and thus could potentially be used to impart undesirable skills (e.g., terrorism). Therefore, EdNetRMABs still require careful curation of learning content.

3. The assumption that the student's state is fully observable is a major limitation of the work. This can result in overconfident recommendations.
   We acknowledge the issue of full observability and plan to address it in our future work. Despite this limitation, our results have shown promise over existing methods.

Thank you for addressing my questions.

We thank the reviewer for his positive feedback and comments, and address their questions below:

##Questions

1. On releasing code/simulators
   We will share our code for community use.

2. On Equation (1): Does summing over the pseudo-actions change the optimality of Whittle Index? Is Theorem 1 answering the question?
   Whittle index is optimal only under some strict assumptions/requirements. One such fundamental requirement is that each arm must be indexable. Indexability is characterized by the property where the set P(λ), representing all states in which deactivating the arm is optimal at a game cost λ, must increase monotonically from the empty set to encompass the entire state space as λ increases from 0 to +∞. In our model, the arms exhibit interdependencies, meaning that the index value of any given arm can be influenced by the states of its neighboring arms. Thus, they complicate the computation of the traditional Whittle index. The decision to activate an arm can become more or less favorable depending on the states of other interconnected arms, not solely based on its own state and the subsidy λ. Thus, this summing over pseudo-actions impacts optimality.
   Our theorem 1 demonstrates that despite these complexities, it is possible to adapt the Whittle index to account for interdependencies among arms. This adaptation leverages the inherent structure of interdependencies to refine the decision-making process, thereby aligning it with the theoretical framework required for the optimality of the Whittle index policy.

3. On ablation study under misspecification of $\phi$:
   Please note that $\phi$ represents inter-item relationships and this is usually not very complex or extensive. We believe that trainers/teachers can quickly verify the specified relationships to remove any errors. However, we understand the reviewer's concern. We hypothesise that misspecification of $\phi$ will result in erroneous attribution of positive effects to passive actions and negative effects to pseudo-actions for EduQate. We provide a trial run of the conditions where a proportion of $\phi$ is misspecified in Table 2 of the attached PDF. In this case, EduQate outperforms random policy and WIQL. Even without knowing the underlying transition matrix, EduQate is still able to perform as well as TW (which requires knowledge of transition probabilities).
   Additionally, WIQL can be seen as a special case of EduQate where $\phi_i = \emptyset$ for all $i$, representing an extreme case of misspecification.

4. On $IB$ as a metric:
   The reviewer is correct on the interpretation of $IB$ and we agree with the reviewer's concern when random performs better. IB has been used in RMABs in healthcare settings, albeit over a no-action policy as the baseline. We adapt it to education settings and compare our policies to a random policy, which is known to be a strong policy for education. We agree that in certain cases where random outperforms both $\pi$ and EduQate, $IB$ can be misleading. In our main experiments, $R_{EQ} > R_{random}$ for all cases, and hence the current version of $IB$ is valid. We propose to modify $IB$ to $IB_{Random}(\pi) = \frac{E_{\pi}(R(.)) - E_{Random}(R(.))}{ E_{Random}(R(.))}$ for simplicity, while maintaining the original intention of comparing it to the random policy baseline. We present the updated results in Table 1 of the attached PDF. For EduQate achieving 100%, we present the following. Let $\pi = EQ$, then: $IB_{Random,EQ}(EQ) = \frac{E_{EQ}(R(.)) - E_{Random}(R(.))} {E_{EQ}(R(.)) - E_{Random}(R(.))} = 1$

The new metric seems much more reasonable! Thanks for the explanation.

I read through the rejection reviews as well. Multi-Arm Bandit is still one of the most commonly used algorithms by education platforms such as Duolingo and others. As far as bandit paper goes, this paper's experimental results are sufficient.

I will keep my score, and I'm happy to defend this paper and my decisions.