Developing control methods that allow legged robots to move with skill and agility remains one of the grand challenges in robotics. In order to achieve this ambitious goal, legged robots must possess a wide repertoire of motor skills. A scalable control architecture that can represent a variety of gaits in a unified manner is therefore desirable. Inspired by the motor learning principles observed in nature, we use an optimization approach to automatically discover and fine-tune parameters for agile gaits. The success of our approach is due to the controller parameterization we employ, which is compact yet flexible, therefore lending itself well to learning through repetition. We use our method to implement a flying trot, a bound and a pronking gait for StarlETH, a fully autonomous quadrupedal robot.