Stochastic learning and optimization — Ideas vs mathematics?

Abstract

What are the roles that ideas and mathematics play in research of engineering subjects? This article tries to answer this question with the author’s own research experience. In the past 30 years, the author’s research started from perturbation analysis (PA) of queueing networks, to PA of Markov systems, to Markov decision processes (MDP), and to stochastic control; and based on these research, the author has successfully developed a sensitivity-based optimization approach to the area of learning and optimization of stochastic systems, leading to a simple and unified framework for the area, new research directions, and new results in the area. This paper reviews the above research topics and the history of their development with an emphasis on what the roles that ideas and mathematics play in each of the advances along the path.

Keywords

perturbation analysis (PA) / Markov decision processes (MDP) / sensitivity-based optimization / perturbation realization factors / performance potentials

References

[1] Ho Y C, Eyler A, Chien T T. A gradient technique for general buffer-storage design in a serial production line. International Journal of Production Research, 1979, 17(6): 557-580

[2] Ho Y C, Eyler A, Chien T T. A new approach to determine parameter sensitivities on transfer lines. Management Science, 1983, 29(6): 700-714

[3] Bryson A E, Ho Y C. Applied Optimal Control: Optimiza tion, Estimation, and Control. Waltham, MA: Blaisdell, 1969

[4] Ho Y C, Cao X R. Perturbation analysis and optimization of queueing networks. Journal of Optimization Theory and Applications, 1983, 40(4): 559-582

[5] Cao X R. Stochastic Learning and Optimization — A Sensitivity-Based Approach. New York, NY: Springer, 2007

[6] Xia L, Cao X R. Performance optimization of queueing systems with perturbation realization. European Journal of Operations Research, invited survey paper, 2011 (submitted)

[7] Cao X R. First-order perturbation analysis of a single multiclass finite source queue. Performance Evaluation, 1987, 7(1): 31-41

[8] Cao X R. First-order perturbation analysis of a single multiclass finite source queue. Performance Evaluation, 1987, 7(1): 31-41

[9] Heidelberger P, Cao X R, Zazanis M A, Suri R. Convergence properties of infinitesimal rerturbation analysis estimates. Management Science, 1988, 34(11): 1281-1302

[10] Cao X R. A Sample performance function of Jackson queueing networks. Operations Research, 1988, 36(1): 128-136

[11] Cao X R. Realization Probabilities — The Dynamics of Queueing Systems. New York, NY: Springer Verlag, 1994

[12] Cao X R. Convergence of parameter sensitivity estimates in a stochastic experiment. IEEE Transactions on Automatic Control, 1985, 30(9): 834-843

[13] Glasserman P. Gradient Estimation via Perturbation Analysis. Boston, MA: Kluwer Academic Publishers, 1991

[14] Cao X R. Realization probability in closed Jackson queueing networks and its application. Advances in Applied Probability, 1987, 19(3): 708-738

[15] Fu M C, Hu J Q. Conditional Monte Carlo: Gradient Estimation and Optimization Applications. Boston, MA: Kluwer Academic Publishers, 1997

[16] Gong W B, Ho Y C. Smoothed (conditional) perturbation analysis for discrete event dynamic systems. IEEE Transactions on Automatic Control, 1987, 32(10): 858-866

[17] Ho Y C, Cao X R, Cassandras C G. Infinitesimal and finite perturbation analysis for queueing networks. Automatica, 1983, 19(4): 439-445

[18] Ho Y C, Cao X R. Perturbation Analysis of Discrete Event Systems. Norwell, MA: Kluwer Academic Publishers, 1991

[19] Cassandras C G, Wardi Y, Melamed B, Sun G, Panayiotou C G. Perturbation analysis for online control and optimization of stochastic fluid models. IEEE Transactions on Automatic Control, 2002, 47(8): 1234-1248

[20] Liu Y, Gong W B. Perturbation analysis for stochastic fluid queueing systems. Discrete Event Dynamic Systems: Theory and Applications, 2002, 12(4): 391-416

[21] Wardi Y, Melamed B, Cassandras C G, Panayiotou C G. Online IPA gradient estimators in stochastic continuous fluid models. Journal of Optimization Theory and Applications, 2002, 115(2): 369-405

[22] Cao X R, Chen H F. Perturbation realization, potentials, and sensitivity analysis of Markov processes. IEEE Transactions on Automatic Control, 1997, 42(10): 1382-1393

[23] Cao X R, Yuan X M, Qiu L. A single sample path-based performance sensitivity formula for Markov chains. IEEE Transactions on Automatic Control, 1996, 41(12): 1814-1817

[24] Cao X R. The potential structure of sample paths and performance sensitivities of Markov systems. IEEE Transactions on Automatic Control, 2004, 49(12): 2129-2142

[25] Cao X R. A unified approach to Markov decision problems and performance sensitivity analysis. Automatica, 2000, 36(5): 771-774

[26] Cao X R. From perturbation analysis to Markov decision processes and reinforcement learning. Discrete Event Dynamic Systems: Theory and Applications, 2003, 13(1-2): 9-39

[27] Fang H T, Cao X R. Potential-based on-line policy iteration algorithms for Markov decision processes. IEEE Transactions on Automatic Control, 2004, 49(4): 493-505

[28] Marbach P, Tsitsiklis T N. Simulation-based optimization of Markov reward processes. IEEE Transactions on Automatic Control, 2001, 46(2): 191-209

[29] Zhang J Y, Cao X R. Continuous-time Markov decision processes with nth-bias optimality criteria. Automatica, 2009, 45(7): 1628-1638

[30] Cao X R, Zhang J Y. The nth-order bias optimality for multichain Markov decision processes. IEEE Transactions on Automatic Control, 2008, 53(2): 496-508

[31] Puterman M L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. New York, NY: John Wiley & Sons, 1994

[32] Veinott A F. Discrete dynamic programming with sensitive discount optimality criteria. The Annals of Mathematical Statistics, 1969, 40(5): 1635-1660

[33] Cao X R. Basic ideas for event-based optimization of Markov systems. Discrete Event Dynamic Systems: Theory and Applications, 2005, 15(2): 169-197

[34] Cao X R, Zhang J Y. Event-based optimization of Markov systems. IEEE Transactions on Automatic Control, 2008, 53(4): 1076-1082

[35] Xu Y K, Cao X R. Optimal control with Lebesgue sampling and time aggregation. IEEE Transactions on Automatic Control (to appear)

[36] Xia L, Chen X, Cao X R. Policy iteration for customeraverage performance optimization of closed queueing systems. Automatica, 2009, 45(7): 1639-1648

[37] Xia L, Cao X R. Aggregation of perturbation realization factors and service rate-based policy iteration for queueing systems. In: Proceedings of the 45th IEEE Conference on Decision and Control. 2006, 1063-1068

[38] Xia L, Cao X R. Relationship between perturbation realization factors with queueing models and Markov models. IEEE Transactions on Automatic Control, 2006, 51(10): 1699-1704

[39] Cao X R. Stochastic control of continuous-time and continuous-state systems via direct comparison. In: Proceedings of the 48th IEEE Conference on Decision and Control. 2009, 1593-1598

[40] Cao X R. A new model of continuous-time Markov processes and impulse stochastic control. In: Proceedings of the 48th IEEE Conference on Decision and Control. 2009, 525-530

[41] Cao X R, Wang D X, Lu T, Xu Y F. Stochastic control via direct comparison. 2011 (submitted)

[42] Oksendal B, Sulem A. Applied Stochastic Control of Jump Diffusions. 2nd ed. Berlin: Springer, 2007

[43] Ho Y C. What is experimental system engineering? ScienceNet, 2010. http://www.sciencenet.cn/m/user content. aspx?id=382212

[44] Cao X R. Mathematics, analysis, and engineering. Guest article, Prof. Y. C. Ho’s blog at ScineceNet, 2008. http://www.sciencenet.cn/m/user content.aspx?id=38753

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg