We present a technique to construct very fast message passing algorithms to find approximate solutions of optimization problems under uncertainty, well suited to solve online problems. As a real world example, we apply it to the online AdWords problem, a family of variants of the maximum weight bipartite b-matching with some special budget constraints. This method does not rely explicitly on sampling, but it is capable of estimating the statistics of optimal configurations of instances from a given ensemble.