Optimal Economic Change Detection with Imperfect Information

我们建议解决最常遇到的随机优化问题之一，即最优经济变化检测。简而言之，这个问题旨在检测给定随机（奖励或成本）过程中的变化，以最大化（或最小化）给定的最优性标准（总奖励或成本）。不确定性可能来自多种来源，包括系统状态及其演化、状态变化前的停留时间、可观测信号中的白噪声等。最优变更检测问题具有广泛的应用，包括：生产系统控制（Chryssolouris 2006, Zhang 2005）、库存管理、医疗保健系统（Woodall 2006）、维护优化和财务，仅举几例。具体的例子可能包括动态生产批量，其中生产运行将不得不停止以最小化生产成本；最优库存控制，其中必须找到订货的库存阈值；金融资产的最优交易，一旦价格超过预设的阈值，资产头寸就可以出清。尽管有广泛的应用，但相关文献却令人惊讶地有限。大部分的工作是计算和分析的结果，只有在简单的情况下。特别是，对于不超过两个状态的问题，最优策略的结构性质是可用的。现有文献可以通过将基本问题（具有完全信息的两个状态）推广到多个方向：多系统状态、有限信息可用性、有限或无限优化视界、可选停止行为和自适应采样来扩展。我们的长期目标是：(1)通过描述最优策略和利用加速算子，为具有不完全信息的经济变化检测问题的整个范围开发计算效率高的算法；(2)将开发的模型应用于各种应用，如维护优化、生产系统控制、财务优化、安全系统控制和医疗保健提供优化。经济检测问题谱中的具体问题包括(1)有限与无限视界问题，(2)有或没有吸收态的n态过渡结构，(3)过渡结构的完全（或尽可能完整）图扩展，(4)多个停止动作，(5)多种类型的样本，以及(6)可变采样间隔。作为第一步，我们的短期目标是解决贝叶斯经济停止问题谱系中两个尚未开发的问题，并将该模型应用于应用程序。首先，我们将描述具有最优自适应采样和具有多个后变化行为的经济检测的最优策略结构。这些任务将包括对价值函数的分析调查，对价值函数边界的推导，对策略映射的凹凸性和/或凹性的调查，理解策略参数之间的关系，如超级和/或子模块性，以及对抽样率对价值函数的影响的分析。最终目标是为一般类型的经济检测问题设计计算效率高的算法。其次，在应用方面，我们将利用从第一个短期目标中获得的知识来解决一个现实世界的问题：算法交易。具体地说，我们将把当前对配对交易的发展扩展到更一般的动态投资组合管理模型。交易问题需要持续控制，因为资产价格不断变化，因此将作为连续时间马尔可夫决策过程来解决。

We propose to address one of the most commonly encountered stochastic optimization problems, known as the optimal economic change detection. Briefly stated, this problem aims to detect changes in the given stochastic (reward or cost) process to maximize (or minimize) the given optimality criterion (total reward or cost). Uncertainties may come from a variety of sources including system state and its evolution, sojourn times before state change, white noise in the observable signal, and so on.The optimal change detection problem has a wide range of applications, including: production system control (Chryssolouris 2006, Zhang 2005), inventory management, healthcare system (Woodall 2006), maintenance optimization, and finance, to name just a few. Specific examples may include the dynamic production lot sizing, in which a production run will have to be stopped to minimize the production cost; the optimal inventory control, in which inventory threshold for ordering will have to be found; and optimal trading of financial assets, in which an asset position can be cleared once the price rises above a pre-set threshold.Despite the ample applications, the relevant literature is surprisingly limited. Most of the work is computational and analytical results are available only for simple cases. In particular, structural properties of optimal policy are available for problems with no more than two states. The existing literature can be extended by generalizing the basic problem (two states with complete information) in many directions: multiple system states, limited availability of information, finite or infinite optimization horizon, alternative stopping actions, and adaptive sampling.Our long-term objectives are (1) to develop computationally efficient algorithms for the whole spectrum of the economic change detection problem with imperfect information by characterizing the optimal policy and by utilizing the acceleration operators, and (2) to apply the developed model(s) to diverse applications such as maintenance optimization, production system control, financial optimization, security system control, and healthcare delivery optimization. Specific problems in the economic detection problem spectrum include (1) finite vs. infinite horizon problem, (2) N-state transition structure with or without an absorbing state(s), (3) complete (or as complete as possible) graph extension of the transition structure, (4) multiple stopping actions, (5) multiple types of samples, and (6) variable sampling interval. As a first step, our short-term objectives are to address two untapped problems in spectrum of Bayesian economic stopping problem and apply the model to an application. First, we will characterize the structure of optimal policy for the economic detection with optimal adaptive sampling and that with multiple post-change actions. These tasks will involve analytical investigation of the value function, derivation of bounds for the value function, investigation of the convexity and/or concavity of policy maps, understanding the relations among policy parameters such as super- and/or sub-modularity, and the analysis of impact of sampling rate on the value function. The eventual goal is to design computationally efficient algorithms for general classes of the economic detection problems. Second, on the application side, we will utilize the gained knowledge from the first short-term goal in tackling a real world problem: algorithmic trading. Specifically, we will extend the current development on pair trading to a more general dynamic portfolio management model. The trading problem requires continuous control as asset prices changing continuously and as a result will be tackled as continuous time Markov decision processes.