Synaptic plasticity is implemented and controlled through over thousanddifferent types of molecules in the postsynaptic density and presynapticboutons that assume a staggering array of different states throughphosporylation and other mechanisms. One of the most prominent molecule in thepostsynaptic density is CaMKII, that is described in molecular biology as a"memory molecule" that can integrate through auto-phosporylation Ca-influxsignals on a relatively large time scale of dozens of seconds. The functionalimpact of this memory mechanism is largely unknown. We show that theexperimental data on the specific role of CaMKII activation in dopamine-gatedspine consolidation suggest a general functional role in speeding upreward-guided search for network configurations that maximize rewardexpectation. Our theoretical analysis shows that stochastic search could inprinciple even attain optimal network configurations by emulating one of themost well-known nonlinear optimization methods, simulated annealing. But thisoptimization is usually impeded by slowness of stochastic search at a giventemperature. We propose that CaMKII contributes a momentum term thatsubstantially speeds up this search. In particular, it allows the network toovercome saddle points of the fitness function. The resulting improvedstochastic policy search can be understood on a more abstract level asHamiltonian sampling, which is known to be one of the most efficient stochasticsearch methods.