Exploration and search are such crucial occurrences in the natural world around us, yet we don't know much about what drives the precise structure we observe. While exploration by animals in discrete choice tasks has been extensively researched, exploration in sequential contexts has received little attention. We take a behaviorally rich dataset of mice exploring a labyrinth by Rosenberg et al. (2021) and model it using search strategies from foraging literature in an RL framework. We discovered that an ecologically inspired Lévy walk model adequately explains the efficiency and preferences of mice exploring the labyrinth. We implemented the model in the temporally extended ε-greedy exploration framework, which allowed us to interpret the search strategy using general principles. We found that animals exhibit super-diffusive behavior and leverage temporal persistence to navigate the maze rather than making decisions at each intersection. Our study provides a new perspective on Lévy flight foraging and opens new avenues for investigating the interaction between exploration dynamics and the naturalistic environments.