Theory and Applications of Approximate Dynamic Programming

本课题研究经典动态规划方法无法解决的不确定性过大的顺序决策问题。近似动态规划是一个丰富的领域，它结合了经典动态规划、强化学习和其他人工智能方法、近似理论和神经网络以及仿真。本研究的目的如下：(1)。解决与涉及查找表表示的基于模拟的方法相关的几个突出问题。(2)。提供近似动态规划方法的理论理解，当使用成本函数的紧凑表示时。特别是，识别保证收敛的算法/体系结构组合的类别，以及错误界限。(3)。发展了平均成本近似动态规划的理论和算法。(4)。发展马尔可夫对策的近似动态规划理论和算法。(5)。进行一些案例研究，以便更好地了解不同方法的比较性能，并证明这些方法在解决具有现实重要性的现实问题上的有用性。三个案例研究涉及：(a)卡车车队的动态调度(b)复杂衍生金融工具的定价。(c)足球运动。总体目标是为近似动态规划领域提供一个全面的数学基础，同时成功地解决一些困难和重要的问题。

9625489 Tsitsiklis This project deals with problems of sequential decision making under uncertainty that are too large for the classical methods of dynamic programming. The focus is on approximate dynamic programming which is a rich field that combines classical dynamic programming, reinforcement learning and other methods from artificial intelligence, approximation theory and neural networks, and simulation. The objectives of the research are as follows: (1). Resolve several outstanding question related to simulation-based methods involving lookup table representations. (2). Provide a theoretical understanding of approximate dynamic programming methods, when a compact representation of the cost-to-go function is employed. In particular, identifying classes of algorithm/architecture combinations for which convergence is guaranteed, together with error bounds. (3). Develop the theory and algorithms for average cost approximate dynamic programming. (4). Develop the theory and algorithms for approximate dynamic programming for the case of Markov games. (5). Carry out a number of case studies that will provide a better understanding of the comparative performance of different methods, and to demonstrate the usefulness of the methods on realistic problems of real-world importance. Three case studies involve: (a) Dynamic scheduling of a fleet of trucks (b) Pricing of complex derivative financial instruments. (c) The game of football. The overall objectives are to provide a comprehensive mathematical foundation for the field of approximate dynamic programming and at the same time succeed in solving some difficult and important problems.