Crime observations are one of the principal inputs used by governments for designing citizens’ security strategies. However, crime measurements are obscured by underreporting biases, resulting in the so-called “dark figure of crime”. This work studies the possibility of recovering “true” crime and underreported incident rates over time using sequentially available daily data. For this, a novel underreporting model of spatiotemporal events based on the combinatorial multi-armed bandit framework was proposed. Through extensive simulations, the proposed methodology was validated for identifying the fundamental parameters of the proposed model: the “true” rates of incidence and underreporting of events. Once the proposed model was validated, crime data from a large city, Bogotá (Colombia), was used to estimate the “true” crime and underreporting rates. Our results suggest that this methodology could be used to rapidly estimate the underreporting rates of spatiotemporal events, which is a critical problem in public policy design.