Regrets only! online stochastic optimization under time constraints

摘要: This paper considers online stochastic optimization problems where time constraints severely limit the number of offline optimizations which can be performed at decision and/or in between decisions. It proposes a novel approach combines salient features earlier approaches: evaluation every on all samples (expectatio0n) and ability to avoid distributing among decisions (consensus). The key idea underlying algorithm is approximate regret d. evaluated two fundamentally different applications: packet scheduling networks multiple vehicle routing with windows. On both applications, it produces significant benefits over prior approaches.