Online Planning in Nonstationary Environments

• 成果类型: Article; Early Access
• 署名作者: Cheung, Wang Chi; Lyu, Guodong
• 署名单位: National University of Singapore; Hong Kong University of Science & Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0604
• 发表日期: 2025
• 关键词: process flexibility; inventory systems; optimization; EFFICIENCY; policies

摘要

A central issue in (finite horizon) online planning problems is to synthesize the impact of real-time decisions on the subsequent states of the system and the performance in the remaining time horizon (cost-to-go function). A complete resolution often leads to intractable dynamic programming problems. We propose a computationally efficient approach to this problem that attains near-optimal performance in nonstationary environments. More specifically, we study a general class of online planning problems with concave objective functions and convex (global) feasibility constraints. A wide range of operational problems (e.g., coupon assignment with multiple objectives, order fulfillment with service level requirements, and resource allocation with budget constraints) can be appropriately modeled using our online planning framework. We consider two different settings for online planning: the simulation setting (SIMU) where the decision maker (DM) has unlimited access to data samples via a simulator and the sampling-based setting (SAMP) where the DM is constrained to a finite set data samples. Leveraging the value of the gradient information obtained from offline simulation in SIMU or SAMP, we develop a generic offlineto-online approach to facilitate online planning. Our proposed approach produces near optimal solutions in both SIMU and SAMP. Specifically, in SAMP, our performance guarantee improves when the number of data samples or the length of planning horizon increases. We present extensive numerical evidence to validate the performance of our approach in a novel coupon assignment problem and a classic supply chain management problem, and discuss its improvement over existing techniques that assume model stationarity.