multi-cell network consisting of N cells, Nt antennas per BS and K UTs per cell. Under this set up, we address the following question: given certain time average QoS targets for the users, what is the minimum energy expenditure with which they can be met? Time average QoS constraints can lead to greater energy savings as compared to instantaneous QoS constraints since it provides the flexibility to dynamically allocate resources over the fading channel states. We formulate the problem as a stochastic optimization problem whose solution is the design of the downlink beamforming vectors during each time slot. We first characterize the set of time average QoS targets which is achievable by some feasible control policy. We then use the technique of virtual queue to model the time average QoS constraints and convert the problem into a queue stabilization problem while minimizing the time average energy expenditure. We solve this problem using the approach of Lyapunov optimization and characterize its performance. Interestingly, our solution leads to a decentralized design in which the BSs only have to exchange limited side information. Our simulation results show that solving the problem with time average QoS constraints provide greater energy savings as compared to the instantaneous QoS constraints.