In this work, we study the data collection problem using a data mule in millimeter Wave (mmWave) sensor net-works. The data mule aims to collect data (from a redundant set of sensors) within a minimum expected time, constrained by a lower bound on the delivery probability. Due to multiple factors of uncertainty, such as duty-cycling of sensors and mmWave link attenuation due to random blockage effects, the data mule faces a non-trivial challenge of how many times to probe a sensor (exploit) and which sensor to probe (explore), in order to meet the aforementioned goal. The aforementioned (exploit/explore) problem is modeled using a partially observable Markov decision process. As the direct method of solving the model characterized by a continuous state space is computationally intensive, we present an alternate method by investigating the structural properties of the model. To this end, a simple threshold-based myopic optimal data collection algorithm is shown to exist, and the closed-form expression for the threshold is derived. The effectiveness of the proposed optimal algorithm is validated against state-of-the-art learning-based protocols through extensive simulations.