Variance-Reduced Long-Term Rehearsal Learning with Quadratic Programming Reformulation
Wen-Bo Du, Tian Qin, Tian-Zuo Wang, Zhi-Hua Zhou
In machine learning, a critical class of decision-making problems involves *Avoiding Undesired Future* (AUF): given a predicted undesired outcome, how can one make decisions to prevent it? Recently, the \textit{rehearsal learning} framework has been proposed to address the AUF problem. While existing methods offer reliable decisions for single-round success, they fall short in long-term settings that involve coordinating multiple future outcomes, which better reflect real-world requirements. To address this challenge, we generalize the AUF objective to characterize a long-term decision target that incorporates cross-temporal relations among variables. As directly optimizing the *AUF probability* $P_{AUF}$ over this objective remains challenging, we derive an explicit expression for the objective and further propose a quadratic programming (QP) reformulation that transforms the intractable probabilistic AUF optimization into a tractable one. Under mild assumptions, we prove that QP solutions equals solutions to the AUF optimization, upon which we develop two novel rehearsal learning methods for long-term decision-making: (i) a *greedy* method that maximizes the single-round $P_{AUF}$ at each step, and (ii) a *far-sighted* method that accounts for future consequences in each decision, yielding a higher overall $P_{AUF}$ through a $T/(T+1)$ variance reduction in the AUF objective. We further establish an $\mathcal{O}(1/\sqrt{N})$ excess risk bound for decisions based on estimated parameters, ensuring reliable practical applicability with finite data. Experiments validate both theoretical results and empirical effectiveness of our approach.