Adaptive variability in behavior is crucial when environments promote unpredictability, yet its underlying cognitive mechanisms remain poorly understood. Volatile and adversarial environments can elicit variability by abrupt rule switches and explicitly reinforcing variable choices, respectively; however, literature lacks paradigms, computational models, and data to investigate and compare how (human) agents address such challenges. We introduce a novel hide-and-seek paradigm and use computational modeling to disentangle five candidate cognitive mechanisms of variability: stochastic choice, fast reinforcement learning, action-frequency-based memory, sequence-frequency-based memory, and episodic memory. Across three experiments (N = 290), we show that participants flexibly increased learning rate in volatile environments, but stochasticity, action-frequency-based memory, and reliance on episodic memory in adversarial environments. For the first time, these findings uncover that adaptive variability is not a unitary phenomenon but instead emerges from the flexible recruitment of multiple cognitive mechanisms as environmental demands intensify.