Reinforcement learning (RL) in general refers to a rich class of simulation-based approaches that are geared towards solving problems of stochastic control. Such problems are often formulated using the framework of Markov decision Processes (MDPs). Regular solution procedures for MDPs suffer from two major problems: (a) they require complete model information and (b) the amount of computational effort required to solve such procedures grows exponentially in the size of the state space (the curse of dimensionality). Both problems are effectively tackled when using RL. Most RL algorithms are based on stochastic approximation and incorporate outcomes from real or simulated data directly. Further, feature-based function approximation is often used to handle large/high-dimensional state spaces. In this chapter, we discuss algorithms that are based on both full-state representations as well as function approximation. A distinguishing feature of these algorithms is that they are based on simultaneous perturbation techniques. Apart from being easily implementable, some of these algorithms also exhibit significant improvement in performance over other well known algorithms in the literature.