Adaptive Optimization for Stochastic Renewal Systems

This paper considers online optimization for a sequence of tasks. Each task can be processed in one of multiple processing modes that affect the duration of the task, the reward earned, and an additional vector of penalties (such as energy or cost). Let A[k] be a random matrix that specifies the parameters of task k. The goal is to observe A[k] at the start of task k and then choose a processing mode for the task so that, over time, time average reward is maximized subject to time average penalty constraints. This is a renewal optimization problem. It is challenging because the probability distribution for the A[k] sequence is unknown. Efficient decisions must be learned in a timely manner. Prior work shows that any algorithm that comes within ϵ of optimality must have Ω(1/ϵ2) convergence time. The only known algorithm that can meet this bound operates without time average penalty constraints and uses a diminishing stepsize that cannot adapt when probabilities change. This paper develops a new algorithm that is adaptive and comes within Θ(ϵ) of optimality for any interval of Θ(1/ϵ2) tasks over which probabilities are held fixed.