Reinforcement learning applied to legged-robots opens up the possibility to design robots capable not simply of walking, but of adapting and learning how to walk autonomously without any human interaction. This new generation of robots can one day navigate disaster areas and explore unchartered terrain. In this paper we evaluate the need for a reinforcement learning algorithm to optimize the gait of OctoRoACH, a hand-sized eight-legged robot. We then perform an evaluation of a likelihood-ratio gradient policy and compare it against our hand-tuned results. Finally, we suggest a different approach to reduce the policy search space that can make the problem more manageable.