# Stochasticity Is Not the Hard Part: Reduction and Complexity in Instructional Sequencing over Prerequisite DAGs

arXiv: https://arxiv.org/abs/2608.05455 · HTML: https://mlsanity.com/paper/2608.05455/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 5 Aug 2026.

## Builds on (most cited first, 10 of 10)

- [Curriculum Learning for Reinforcement Learning Domains: A Framework and Survey](https://mlsanity.com/paper/2003.04960/) (2020)
- [Deep Knowledge Tracing](https://mlsanity.com/paper/1506.05908/) (2015)
- [Automated Curriculum Learning for Neural Networks](https://mlsanity.com/paper/1704.03003/) (2017)
- [Context-Aware Attentive Knowledge Tracing](https://mlsanity.com/paper/2007.12324/) (2020)
- [Exploiting Cognitive Structure for Adaptive Learning](https://mlsanity.com/paper/1905.12470/) (2019)
- [Multi-Armed Bandits for Intelligent Tutoring Systems](https://mlsanity.com/paper/1310.3174/) (2013)
- [GraphRAG-Induced Dual Knowledge Structure Graphs for Personalized Learning Path Recommendation](https://mlsanity.com/paper/2506.22303/) (2025)
- [Course-Prerequisite Networks for Analyzing and Understanding Academic Curricula](https://mlsanity.com/paper/2210.01269/) (2022)
- [Parameterized Complexity of MinCSP over the Point Algebra](https://mlsanity.com/paper/2310.05839/) (2023)
- [Order-Sensitive Sequential Interventions on Ideal Lattices](https://mlsanity.com/paper/2604.26472/) (2026)

## Abstract (arXiv)

When a student must learn concepts connected by prerequisite dependencies, when does the order of instruction matter, and what does it cost to find the best one? We study instructional sequencing as a stochastic shortest-path problem in which attempting a concept succeeds with a state-dependent probability and failure leaves the learner state unchanged. We first prove that this stochasticity can be eliminated exactly: the problem collapses to a deterministic shortest-path problem on the lattice of prerequisite order ideals, preserving optimal values and actions. The collapse removes stochastic complexity but not combinatorial complexity: optimal sequencing remains NP-hard -- via reduction from feedback arc set in tournaments -- even with no prerequisite edges, unit costs, uniform binary nonnegative transfer, and success probabilities at least 1/2. Hardness is not uniform: when realizable transfer preferences remain jointly acyclic with the prerequisites, any topological order of the residual joint graph is optimal, and fixed prerequisite width yields polynomial-time exact dynamic programming. A computable diagnostic, mDelta, bounds the value of sequencing before optimization. On 70,893 interactions from an introductory CS course, the diagnostic certifies a doubly easy regime -- little value to optimize and little space to search -- while constructed transfer instances realize the challenging regime, where myopic sequencing suffers large regret yet exact A* with a consistent heuristic expands only linearly many states on that family.