Regret-Guided Curriculum: Task Regret-Guided Curriculum: Task-Selection PAIRED for Discrete Task Libraries

We present a novel algorithmic framework for automated curriculum learning over large discrete task libraries, inspired by the PAIRED (Protagonist-Antagonist Induced Regret Environment Design) paradigm but operating by selecting tasks from an existing task pool rather than generating environments. The central idea is to use regret — the performance gap between a stronger adversary model and the current student model — as a learning signal to prioritize tasks that are simultaneously solvable with learning progress and informative about the student’s weaknesses. Crucially, to mitigate the empirical and theoretical pitfalls of predicting scalar regret values from task embeddings, we propose a set of practical and theoretically justified modifications: (1) regret-binning (predicting whether a task falls in a learnable regret interval), (2) a Task Relation Encoder (TRE) that learns local generalization of bin labels over embedding neighborhoods, and (3) a principled adversary scheduling mechanism that treats adversary strength as a slowly varying parameter. We provide a complete algorithm, a set of theoretical propositions showing under mild smoothness and boundedness conditions that TRE-based selection concentrates probability mass on informative tasks and yields improved cumulative learning gain compared to random sampling, and pseudocode for implementation. We discuss limitations, practical choices, and directions for empirical validation.