Generalized planning aims to compute generalized plans that solve a whole class of problems from a given tractable planning domain.Recently, the D2L system showed how to learn generalized plans with the form of general policies in a self-supervised manner with a MaxSAT solver, where states and transitions are qualitatively abstracted by a set of description logics features.However, D2L requires to fully explore the state space of the input planning problems, which is a major bottleneck even for simple domains.Therefore, we propose the Incremental-D2L algorithm that only requires to explore small fragments of the input state spaces and show that it scales to harder training instances.For very hard domains, where we are unable to learn a general policy, Incremental-D2L yields a partial policy that we can use to enhance a greedy best-first search.Our experiments show that preferring learned {\em helpful actions}, i.e., actions compatible with the (partial) policy, significantly reduces the search effort for many of the considered domains.