Introduction
Intelligent Tutoring Systems (ITS) are highly effective but notoriously difficult to build. Traditional "Cognitive Tutors" rely on expert-defined production rules to model student behavior, a process that can take up to 1,000 hours of development for a single hour of instruction. This "authoring bottleneck" limits the scalability of ITS across diverse subjects. This paper investigates whether Markov Decision Processes (MDPs) can be used to automatically generate hints by learning from historical student solution data.
Methodology
The authors represent student problem-solving as an MDP. In a logic proof tutor, a "state" is defined by the set of premises a student has derived. By aggregating student attempts, the system builds a state-space graph where edges represent logical rules.
To identify the most effective paths, the system uses reinforcement learning (value iteration). Goal states receive high rewards, while transitions and errors are penalized to encourage efficiency. When a student is stuck, the system identifies the adjacent state with the highest value and generates a hint. The study evaluates two models: Un-ordered (where the sequence of steps is ignored) and Ordered (where the sequence is preserved).
Dataset and Evaluation
The study used 523 solutions from the "Deep Thought" logic tutor, collected from a discrete math course at North Carolina State University. The researchers ran 100,000 simulations to determine the "hint coverage"—the number of student attempts needed to provide hints to a certain percentage of future students.
Key Results
The findings indicate that data-driven hint generation is highly efficient, particularly for the Un-Ordered state model.
As shown in the data, the Un-Ordered model reaches a 50% hintability threshold with only 8 student attempts. Reaching 90% coverage requires 360 attempts. The Ordered model is significantly more data-intensive, requiring 362 attempts just to reach 85% coverage, and failing to reach 90% within the dataset limits.
Conclusion
This research demonstrates that MDPs can validly generate hints with surprisingly small amounts of training data. Furthermore, the data-driven approach identified "buggy" rules that human experts had missed, highlighting its potential to capture complex student behaviors. While future work must address the pedagogical impact of these hints and the state-space explosion in more complex problems, this approach offers a viable solution to the ITS authoring bottleneck.
Summary updated