弱耦合随机动态规划的松弛强度-研究论文

许多随机动态程序 (DP) 具有弱耦合结构，因为每个周期中的一组链接约束耦合了原本独立的子问题集合。 此类问题的两个广泛研究的近似是近似线性规划 (ALP)，它涉及优化在子问题之间相加分离的值函数近似，以及拉格朗日松弛，其中涉及放宽链接约束。 众所周知，这两种近似都提供了所有状态下最优值函数的上限，而 ALP 在初始状态下提供了更严格的上限。 这篇短文的目的是为这些上限即使不相同也常常接近这一事实提供理论依据。 我们表明： (i) 对于任何弱耦合 DP，这两个上限之间的差异 --- 松弛间隙 --- 根据 ALP 内约束分离问题的完整性间隙从上方有界； (ii) 如果子问题奖励是统一有界的，并且链接约束上的一些广泛适用的条件成立，则松弛间隙由与子问题数量无关的常数从上方限定； (iii) 当子问题动作是二元的并且链接约束具有单模结构时，松弛间隙为零。 (iii) 的条件在几个广泛研究的问题中成立：不安分的强盗问题、在线随机匹配问题、网络收入管理问题和重新定位资源的价格导向控制。 这些发现概括并统一了现有的结果。