Abstract: We present a learning technique that automatically synthesizes realistic locomotion for the animation of physics-based models of animals. The method is especially suitable for animals with highly flexible, many-degree-of-freedom bodies and a considerable number of internal muscle actuators, such as snakes and fish. The multilevel learning process first performs repeated locomotion trials in search of actuator control functions that produce efficient locomotion, presuming virtually nothing about the form of these functions. Applying a short-time Fourier analysis, the learning process then abstracts control functions that produce effective locomotion into a compact representation which makes explicit the natural quasi-periodicities and coordination of the muscle actions. The artificial animals can finally put into practice the compact, efficient controllers that they have learned. Their locomotion learning abilities enable them to accomplish higher-level tasks specified by the animator while guided by sensory perception of their virtual world; e.g., locomotion to a visible target. We demonstrate physics-based animation of learned locomotion in dynamic models of land snakes, fishes, and even marine mammals that have trained themselves to perform "SeaWorld" stunts.