Humans are driven by an intrinsic motivation to learn, but the developmental origins of curiosity-driven exploration remain unclear. We investigated the computational principles guiding 4-year-old children's exploration during a touchscreen game (N = 102, F = 49, M = 53, primarily white and middle-class, data collected in the Netherlands from 2021-2023). Children guessed the location of characters that were hiding following predictable (yet noisy) patterns. Children could freely switch characters, which allowed us to quantify "when" they decided to explore something different and "what" they chose to explore. Bayesian modeling of their responses revealed that children selected activities that were more novel and offered greater learning progress (LP). Moreover, children's interest in making LP correlated with better learning performance. These findings highlight the importance of novelty and LP in guiding children's exploration.