On the Taylor Expansion of Value Functions
On the Taylor Expansion of Value Functions
复制标题
DOI：
10.1287/opre.2019.1903
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Anton Braverman;I. Gurvich;Jun-fei Huang
中科院分区：
文献类型：
--
作者：
Anton Braverman;I. Gurvich;Jun-fei Huang
我们引入了一个近似动态规划框架，将其应用于具有可数动作集的 $\mathbb{Z}_+^d$ 上的离散时间链。我们的方法基于另一个马尔可夫过程的（受控）链生成器的近似。简单来说，我们的方法规定对值函数应用二阶泰勒展开，以将贝尔曼方程替换为连续空间和时间中的方程，其中转移矩阵减少到其一阶矩和二阶矩。在某些情况下，所得方程（我们将其标记为 {\bf TCP}）可以解释为对应于布朗控制问题。当易于处理时，TCP 可以作为一种有用的建模工具。更一般地说，TCP 是近似算法的起点。我们开发了最优性差距的界限——通过使用“Taylored”方程产生的控制引入的次优性。这些界限可以被视为概念基础、分析性基础，而不是依赖于弱收敛论证，以实现源自布朗控制问题的控制的良好性能。我们证明，在适当的条件下，对于适当“大”的初始状态，(i) 最优性差距小于最优值的 $1-\alpha$ 分数，其中 $\alpha\in (0,1)$ 是折扣因子，并且 (ii) 差距可以进一步表示为无限范围折扣值，每个周期奖励具有“低阶”。在计算上，我们的框架导致了具有性能保证的“聚合”方法。虽然这些保证是以偏微分方程理论为基础的，但这种方法的实际使用不需要该理论的知识。
We introduce a framework for approximate dynamic programming that we apply to discrete time chains on $\mathbb{Z}_+^d$ with countable action sets. Our approach is grounded in the approximation of the (controlled) chain's generator by that of another Markov process. In simple terms, our approach stipulates applying a second-order Taylor expansion to the value function to replace the Bellman equation with one in continuous space and time where the transition matrix is reduced to its first and second moments. In some cases, the resulting equation (which we label {\bf TCP}) can be interpreted as corresponding to a Brownian control problem. When tractable, the TCP serves as a useful modeling tool. More generally, the TCP is a starting point for approximation algorithms. We develop bounds on the optimality gap---the sub-optimality introduced by using the control produced by the "Taylored" equation. These bounds can be viewed as a conceptual underpinning, analytical rather than relying on weak convergence arguments, for the good performance of controls derived from Brownian control problems. We prove that, under suitable conditions and for suitably "large" initial states, (i) the optimality gap is smaller than a $1-\alpha$ fraction of the optimal value, where $\alpha\in (0,1)$ is the discount factor, and (ii) the gap can be further expressed as the infinite horizon discounted value with a "lower-order" per period reward. Computationally, our framework leads to an "aggregation" approach with performance guarantees. While the guarantees are grounded in PDE theory, the practical use of this approach requires no knowledge of that theory.