Online Planning with Offline Forecasting

One of the central issues in online planning is to incorporate forecast information in real time decision making. This often leads to intractable dynamic programming problems. In this work, we study a general class of online planning problems with concave objective functions and global feasibility constraints under non-stationary environments. Leveraging on offline forecast information, we develop an offline-to-online allocation mechanism to facilitate online planning for this class of problems. With perfect forecast, our proposed mechanism is shown to be near-optimal in terms of regret, and satisfies the feasibility constraints with high probability. With imperfect forecast, the optimality gap of the mechanism scales naturally with the discrepancy between actual and forecast models. Our algorithmic framework provides a theoretical justification for the efficacy of "randomized bid price" approach, which is often used in the airlines for network revenue management.