Asymptotic Optimality of Semi-Open-Loop Policies in Markov Decision Processes with Large Lead Times

• 成果类型: Article
• 署名作者: Bai, Xingyu; Chen, Xin; Li, Menglong; Stolyar, Alexander
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; University System of Georgia; Georgia Institute of Technology; City University of Hong Kong; University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.0088
• 发表日期: 2023
• 关键词: open-loop policy; asymptotic analysis; Markov Decision Process; lead time; inventory

摘要

We consider a generic Markov decision process (MDP) with two controls: one control taking effect immediately and the other control whose effect is delayed by a positive lead time. As the lead time grows, one naturally expects that the effect of the delayed action only weakly depends on the current state, and decoupling the delayed action from the current state could provide good controls. The purpose of this paper is to substantiate this decoupling intuition by establishing asymptotic optimality of semi-open-loop policies, which specify open-loop controls for the delayed action and closed-loop controls for the immediate action. For MDPs defined on general spaces with uniformly bounded cost functions and a fast mixing property, we construct a periodic semi-open-loop policy for each lead time value and show that these policies are asymptotically optimal as the lead time goes to infinity. For MDPs defined on Euclidean spaces with linear dynamics and convex structures (convex cost functions and constraint sets), we impose another set of conditions under which semi-open-loop policies (actually, constant delayed-control policies) are asymptotically optimal. Moreover, we verify that these conditions hold for a broad class of inventory models, in which there are multiple controls with nonidentical lead times.