We introduce ergodic stochastic optimization (ESO) algorithms to solve resource allocation problems that involve a random state and where optimality criteria are expressed in terms of long term averages. A policy that observes the state and decides on a resource allocation is proposed and shown to almost surely satisfy problem constraints and optimality criteria. Salient features of the ESO algorithm are that it does not require access to the state's probability distribution, that it can handle non-convex constraints in the resource allocation variables, and that convergence to optimal operating points holds almost surely. The proposed algorithm is applied to determine operating points of a wireless network using an interference limited physical layer. In this example the random state accounts for fading in the wireless channels and non-convex constraints arise due to signal to interference plus noise ratios.