It is very difficult to construct by hand recurrent networks of noisy spiking neurons that are able to carry out nontrivial computational tasks. Obviously evolution has found a different strategy for that. Therefore we have analyzed the power of reward-based learning for configuring the connections and parameters (synaptic weights) of such a network. More specifically, we have considered a model where stochastic local plasticity rules drive the network to search for highly rewarded network configurations. On the abstract level, the resulting paradigm provides an interesting alternative to classical policy learning through gradient ascent: A continuous policy search through stochastic sampling from a posterior distribution that integrates structural constraints with reward expectations.