PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Armed Bandits for Intelligent Tutoring Systems

Benjamin Clement, Didier Roy, Pierre-Yves Oudeyer, Manuel Lopes

arXiv:1310.3174v2cs.AI

TL;DR

The paper tackles personalized activity sequencing in Intelligent Tutoring Systems under limited time, motivation, and student-specific learning differences. It combines learning-progress estimation with multi-armed bandits and coarse expert guidance, achieving learning efficiency comparable to expert sequences and greater gains for more heterogeneous students.

  • Problem

    ITS must choose activity sequences that maximize skills while accommodating limited time, motivation, and differences between students.

  • Method

    The approach combines online learning-progress estimation, multi-armed bandits, and coarse expert constraints to personalize teaching sequences.

  • Results

    The algorithms achieve learning efficiency comparable to expert sequences and produce greater learning gains for populations with more varied and stronger difficulties.

  • Takeaways & Limitations

    Personalized online teaching can work with little domain and student information, while ZPDES is identified as the most promising algorithm for real use.

  • Takeaways & Limitations

    The experiments use unequal numbers of exercises because students had a fixed 40-minute class period, complicating comparisons across algorithms.

Abstract

from arXiv · show

We present an approach to Intelligent Tutoring Systems which adaptively personalizes sequences of learning activities to maximize skills acquired by students, taking into account the limited time and motivational resources. At a given point in time, the system proposes to the students the activity which makes them progress faster. We introduce two algorithms that rely on the empirical estimation of the learning progress, RiARiT that uses information about the difficulty of each exercise and ZPDES that uses much less knowledge about the problem. The system is based on the combination of three approaches. First, it leverages recent models of intrinsically motivated learning by transposing them to active teaching, relying on empirical estimation of learning progress provided by specific activities to particular students. Second, it uses state-of-the-art Multi-Arm Bandit (MAB) techniques to efficiently manage the exploration/exploitation challenge of this optimization process. Third, it leverages expert knowledge to constrain and bootstrap initial exploration of the MAB, while requiring only coarse guidance information of the expert and allowing the system to deal with didactic gaps in its knowledge. The system is evaluated in a scenario where 7-8 year old schoolchildren learn how to decompose numbers while manipulating money. Systematic experiments are presented with simulated students, followed by results of a user study across a population of 400 school children.

1. INTRODUCTION

Intelligent Tutoring Systems must choose activity sequences that maximize learning despite limited time, motivation, and student differences. The paper uses online multi-armed bandits, expert constraints, and learning-progress estimates to personalize teaching with little domain knowledge.

  • The tutoring challenge: Teachers must optimize activity sequences across skills while accounting for limited time, motivation, and individual differences between students.A sequence effective for one student may be inefficient for another.
  • Approach: The system estimates learning progress and proposes the activity expected to make each student progress faster.RiARiT uses exercise-difficulty information, whereas ZPDES requires much less problem knowledge.
  • Design principles: The approach aims to provide a more motivating experience by selecting activities at an appropriate challenge level while adapting online to each student.The design reduces dependence on predefined population-wide cognitive and student models.
  • Expert guidance: Expert teachers can provide coarse pedagogical constraints and an initial canonical sequence to bootstrap exploration.This reduces the need to explore every activity before optimization begins.
  • Approach: The paper’s main contribution is applying multi-armed bandit algorithms to ITS for personalized online activity selection.The algorithms explore activities to estimate individual learning progress and exploit those producing better progress.
  • Evaluation: The evaluation combines simulated-student studies with a real-world tablet experiment involving 400 children aged 7–8 from 11 schools.The user study concerns number decomposition while manipulating money.

2. RELATED WORK - OPTIMIZING TEACHING SEQUENCES USING MACHINE LEARNING

Prior work optimizes teaching sequences through planning, reinforcement learning, Bayesian models, or global data-driven methods. These approaches often require accurate student models or cannot personalize sequences, whereas this paper adjusts an expert-defined zone using student responses and learning progress.

  • Model-based planning: POMDP-based planning selects activities from estimated skill acquisition but commonly assumes students learn in the same way.Its effectiveness depends on the quality of the embedded student and cognitive model.
  • Model-based planning: Knowledge-tracing-based approaches require many parameters that are difficult to identify for individual students because data are sparse and models may be inaccurate.Population-level planning can also be suboptimal for a particular student.
  • Alternative learning methods: Other methods use reinforcement learning, Bayesian networks, or ant-colony optimization, but global optimization cannot provide personalized teaching sequences.These methods target hints, pedagogical strategies, assistance decisions, or population-wide sequences.
  • Zone-based adaptation: This work uses an expert-defined approximate zone of proximal development that optimization algorithms adjust using student answers and learning progress.The expert supplies an initial pedagogical structure rather than a fully specified adaptive model.

3. TEACHING SCENARIO

The teaching scenario trains number decomposition through money and token exercises designed to support varied learning trajectories. Exercises vary by interaction, decomposition difficulty, presentation, notation, and money representation, with an expert-designed sequence used as the evaluation baseline.

  • Scenario: Students learn number decomposition by solving money and token games in a browser-based environment.They select combinations of banknotes, coins, or tokens to buy objects at given prices.
  • Exercise design: Activities vary hierarchically across exercise type, decomposition difficulty, price presentation, cents notation, and money representation.Easy decompositions relate directly to 1, 2, or 5 bills or coins, whereas harder ones use 3, 4, 6, 7, 8, or 9.
  • Evaluation baseline: The evaluated baseline is an optimized expert-designed sequence that increases problem and interaction complexity together.A random policy is excluded because it produces excessive errors and disruptive exercise changes.

4. INTELLIGENT TUTORING SYSTEMS WITH MULTI-ARMED BANDITS

The paper frames tutoring-sequence selection as an online optimization problem: multi-armed bandits estimate student-specific learning progress while expert constraints limit and guide exploration. ZPDES uses sparse domain knowledge and empirical success, whereas RiARiT additionally models student proficiency and activity difficulty.

  • 4. INTELLIGENT TUTORING SYSTEMS WITH MULTI-ARMED BANDITS: The system assumes expert-defined activities and coarse pedagogical constraints, but detailed expert knowledge becomes difficult to provide as the number of activities or knowledge components grows.The paper notes that automatic methods for supplying such knowledge exist and remain an active research area.
  • 4.1. MULTI-ARMED BANDITS FOR ONLINE OPTIMIZATION OF TEACHING SEQUENCES: Multi-armed bandits adapt activity selection to student-specific learning progress, balancing exploration of unfamiliar exercises with exploitation of activities estimated to improve learning.The reward is learning progress, treated as a proxy for maximizing acquired skills; rewards are non-stationary because activities stop producing progress as competence increases.
  • 4.1. MULTI-ARMED BANDITS FOR ONLINE OPTIMIZATION OF TEACHING SEQUENCES: The zone-of-proximal-development mechanism restricts the available activities, reducing abrupt difficulty changes while using expert-defined prerequisites and qualitative equivalences to guide exploration.When progress stalls, the ZPD can widen to another exercise type; when activities have ordered difficulty, it advances after sufficient success.
  • 4.2. ZPDES ALGORITHM: ZONE OF PROXIMAL DEVELOPMENT AND EMPIRICAL SUC-: ZPDES estimates each activity’s quality from recent changes in correctness rates, requiring little domain knowledge and allowing wider exploration when activity difficulty is not consistently ordered across students.Its reward compares success in the most recent half of a window with the preceding half; already-mastered or unsolvable activities receive zero reward.
  • 4.3. RIARIT ALGORITHM: RIGHT ACTIVITY AT THE RIGHT TIME: RiARiT adds domain and student information by explicitly estimating student knowledge and using that estimate to compute activity rewards.The approach is more informed than ZPDES and relies on competence-level estimates rather than only exercise successes and failures.

5. SIMULATIONS WITH VIRTUAL STUDENTS

Simulations with heterogeneous virtual students test whether RiARiT and ZPDES adapt exercise selection to individual learning progress. Both methods generally improve learning over the Expert Sequence, especially for students with activity-specific comprehension limits.

  • Simulation design: The simulations compare a broadly capable population “Q” with a more heterogeneous population “P”, in which some students have activity-specific comprehension limitations.The experiments use populations of 1000 students solving 100 exercises, with different learning rates and maximum understanding levels.
  • Exercise selection: RiARiT and ZPDES propose more difficult exercises earlier while retaining basic exercises longer, adapting selections to students’ actual levels.The exercise counts include proposals regardless of whether students succeed or fail.
  • Skill evolution: For population “Q”, RiARiT and ZPDES produce faster skill learning than the Expert Sequence, while population “P” students can remain blocked under the non-adaptive sequence.ZPDES estimates learning progress, whereas RiARiT also uses estimated levels across knowledge components and parameter impact to select better-adapted exercises.
  • Final competence: For population “P”, RiARiT and ZPDES both outperform the Expert Sequence because the hand-designed sequence cannot adapt when students cannot understand particular activities.For population “Q”, RiARiT is better than the Expert Sequence, while the supplied text reports no distinguishable difference between ZPDES and the Expert Sequence.
  • Final competence: After 100 steps, RiARiT and ZPDES generally yield higher competence across knowledge components, with stronger gains for population “P” students.The boxplots summarize competence distributions using medians and quartiles; non-overlapping notches indicate statistically significant differences.
  • Error analysis: Automatic methods also reduce errors over time relative to the Expert Sequence, particularly for population “P”; RiARiT produces fewer errors than ZPDES there.At the beginning, error counts are equal across methods.

6. USER STUDIES

In a user study with 400 children aged 7–8, RiARiT and ZPDES generally enabled higher achievement and more adaptive exercise paths than the expert sequence, while the ITS group improved more than controls.

  • User study protocol: The study included 400 students aged 7–8 from 11 schools, with each student completing exercises during a constrained 40-minute session.
  • For most exercise types, statistical tests found significant differences between the automatic algorithms and the Expert Sequence, with ZPDES better in most cases.
  • 95% of students using ZPDES and 90% using RiARiT succeeded at least one R exercise, versus 75% with the Expert Sequence; differences increased for MM and RM.
  • The automatic algorithms proposed diverse exercise types, difficulties, and transition paths earlier, whereas the Expert Sequence usually followed the same path.
  • Differences in pre- and post-tests: 65% of application users initially at M level 1 moved higher, compared with about 20% for R and 40% for MM; only 15% of control students moved higher across exercise types.

7. CONCLUSIONS AND FUTURE WORK

The paper concludes that multi-armed bandits enable personalized tutoring with little domain knowledge, matching expert-sequence learning and helping heterogeneous students most. Future work targets deployment conditions, model bootstrapping, richer bandits, and information transfer between students.

  • Learning gains were comparable to expert sequences for homogeneous students and substantially greater for populations with more varied levels and difficulties.
  • The approach is intended to deliver exercises at students’ competence levels rather than necessarily outperform expert teaching sequences.
  • User studies found significantly faster learning for several competences, while ZPDES offered the best adaptation with fewer information requirements and parameters.
  • The methods may suit tutoring situations with many interactions and simpler exercises, especially inner-loop adaptation, while deployment conditions remain under study.
  • Future directions include model-based bootstrapping, contextual or linear bandits, studying factorized-parameter properties, and transferring information across similar students.

A COMPUTATIONAL CONSIDERATIONS

To handle many activities, the system represents exercises as parameterized templates and factorizes RiARiT’s competence representation across parameters. This reduces the need to explore every complete activity but assumes parameter independence.

  • Activities are represented as parameter sets a = (a_1, ..., a_np), allowing parameterized templates when the activity space is large.
  • For ZPDES, the parameterized formulation uses a separate reward weight for each parameter.
  • RiARiT factorizes its R Table by parameter, using qi(aj) to estimate the competence required for each knowledge component and parameter value.
  • The factorization assumes activity parameters are uncorrelated, an assumption acknowledged as generally invalid but reported not to change results in practice.

B EXPERT PEDAGOGICAL SEQUENCE

The expert baseline is a validated instructional sequence comprising 28 exercises in five exercise groups. It repeats parameterized exercises and advances after successful performance.

  • The expert sequence was optimized using instructional design theory and validated through several user studies.
  • The baseline contains 5 exercise groups totaling 28 exercises, covering integer-price, decimal-price, one-object, MM, and RM activities.
  • Each parameterized exercise is proposed four times before progression is considered.
  • After three correct answers, students advance to the next exercise group when applicable.
  • The sequence changes exercise groups under specified conditions and begins the new group from its highest successfully completed exercise.
  • Table 2 summarizes the 28 progression stages and the evolution of activity parameters.

C TABLES

The user-study tables document RiARiT’s parameter settings and pedagogical constraints. They specify competence requirements and conditions that activate or deactivate exercise parameters.

  • Tables 3–5 provide the parameter settings used during the RiARiT user studies.
  • Table 3 maps parameter values to the minimum competence level required in each knowledge component to solve an exercise.
  • Table 4 defines preconditions under which exercise parameters may be used, usually requiring a minimum skill level for a knowledge component.
  • Table 5 defines conditions that deactivate exercise parameters, usually when one or more knowledge components exceed maximum skill levels.
Loading 1310.3174v2…