Reinforcement learning methods can be computationally expensive. Their cost is prone to be higher when the cardinality of the state space representation becomes larger. This curse of dimensionality plays an important role on our work, since gait generation by using more degrees of freedom at each leg, implies a bigger state space after discretization, and look-up tables become impractical. Thus, appropriate function approximators are needed for such kind of tasks on robotics. This chapter shows the advantage of using reinforcement learning, specifically within the batch framework. A neuroevolution of augmenting topologies scheme is used as function approximator, a particular case of a topology and weight evolving artificial neural network which has proved to outperform a fixed-topology network for certain tasks. A comparison between function approximators within the batch reinforcement learning approach is tested on a simulated version of an hexapod robot designed and already built at our undergraduate and graduate students group.