Asynchronous Optimization over Weakly Coupled Renewal Systems

This paper considers optimization over multiple renewal systems coupled by time-average constraints. These systems act asynchronously over variable length frames. When a particular system starts a new renewal frame, it chooses an action from a set of options for that frame. The action determines the duration of the frame, the penalty incurred during the frame (such as energy expenditure), and a vector of performance metrics (such as instantaneous number of job services). The goal is to minimize the time-average penalty subject to time-average overall constraints on the corresponding metrics. This problem has applications to task processing networks and coupled Markov decision processes. We propose a new algorithm so that each system can make its own decision after observing a global multiplier that is updated every slot. We show that this algorithm satisfies the desired constraints and achieves $O\left(ϵ\right)$ near optimality with $O\left(1/{ϵ}^2\right)$ convergence time.