Bio-inspired legged robots have demonstrated the capability to walk and run across a wide variety of terrains, such as those found after a natural disaster. However, the survival of victims of natural disasters depends on the speed at which these robots can travel. This paper describes the need for adaptive gait tuning on an eight-legged robot, which will enable it to adjust its gait parameters to increase the speed at which it navigates difficult and varying terrains. Specifically, we characterize the robot's performance on varied terrains and use the results to inform the implementation of a finite-difference policy gradient reinforcement learning algorithm. We compare the robot's performance under hand-tuned policies with the performance under the reinforcement learning algorithm, and finally, suggest improvements to the presented policy search process.