Online fractional programming for Markov decision systems

We consider a system with K states which operates over frames with different lengths. Every frame, the controller observes a new random event and then chooses a control action based on this observation. The current state, random event, and control action together affect: (i) the frame size, (ii) a vector of penalties incurred over the frame, and (iii) the transition probabilities to the next state visited at the end of the frame. The goal is to minimize the time average of one penalty subject to time average constraints on the others. This problem has applications to task scheduling in computer systems and wireless networks, where each task can take a different amount of time and may change the state of the network. An example is energy-optimal scheduling in a system with several energy-saving transmission modes, where transitions to a different mode incur energy and/or delay penalties. We pose the problem as a stochastic linear fractional program and present an online Lyapunov drift method for solving it. For large classes of problems, the solution can be implemented without any knowledge of the random event probabilities.