Our work is driven by one of the core purposes of artificial intelligence: to develop real robotic agents that achieve complex high-level goals in real-time environments. Robotic behaviors select actions as a function of the state of the robot and of the world. Designing robust and appropriate robotic behaviors is a well-recognized and difficult problem due to the noise, uncertainty and cost of acquiring the necessary state information. We addressed this challenge within the concrete domain of robotic soccer with the fully autonomous Sony legged robots. In this paper, we present one of the outcomes of this research: the introduction of multi-fidelity behaviors to explicitly and efficiently adapt to different levels of state information accuracy. The paper motivates and introduces our general approach and then reports on our concrete work with the Sony robots. The multi-fidelity behaviors we developed allow the robots to successfully achieve their goals in a dynamic and adversarial environment. A robot acts according to a set of behaviors that aggressively balance the cost of acquiring state information with the value of that information to the robot’s ability to achieve its high-level goals. The paper includes empirical experiments which support our method of balancing the cost and benefit of the incrementally-accurate state information.