Exploring the environment efficiently and exploiting learned information effectively are crucial to intelligent agent behavior. Prior work has shown that humans can manage the exploration-exploitation trade-off not only action-by-action, but also at the strategy or rule level, using a heuristic on rule certainty (Collins & Koechlin, 2012). We evaluated this theory on a partially observable rule-switching task and collected human behavioral data (n=112) on two task variants with different levels of rule complexity to test whether taxing cognitive resources impacts exploration heuristics. Our results replicated previous findings, showing that the model is robust to dynamically switching task structure and increased executive demands due to rule complexity. Additionally, we identified a novel meta-heuristic of using high-level rule structure to inform decision-making and computationally characterized its integration with Bayesian inference to support efficient exploration. Through modeling analyses, we show that increased demand on executive function might interfere with this meta-cognitive process.