Although some research focuses on reducing the network sizes for Sum Product Networks and Sum Product Max Networks, the current structure learning algorithms have no control over the network sizes or the learning times. There exist some applications where the computation time is critical rather than the model performance. Anytime algorithms provide an approach to trade-off the computation time with the quality of the models. In this work, we introduce anytime algorithms for learning the SPNs and SPMNs. These algorithms return multiple models such that the initial approximate models need less learning time and are small in size. But by allowing more nodes and computation time, the performance of the networks improves over time. We evaluate the anytime algorithms over a testbed and demonstrate that the performance of the SPNs in terms of the log-likelihood and the SPMNs as given by the average rewards improves and reflect the performance profiles as expected for an anytime algorithm.