Stochastic Control and Optimization problems have become increasingly important for Big Data and Robotic applications. Almost all stochastic control and optimization problem are solved via stochastic iterative algorithms. Often, this is due to the solution being the fixed point of a non-expansive operator. For example, dynamic programming algorithms find the fixed point of the Bellman operator which is a contraction. Gradient descent algorithms are also monotone operators. For large scale problems, exact dynamic programming or gradient descent can’t be performed, and one must use simulation-based approximations. This leads to each iteration being a random operator, which is no longer a contraction operator. We introduce several notions of probabilistic fixed points of random operators, and show their asymptotic equivalence. The stochastic iterative algorithms can now be seen as iteration of a random operator. We develop a stochastic dominance-based technique for analysis of iterated random operators. We show how various approximate dynamic programming, reinforcement learning and variations of stochastic gradient descent algorithms fit within this common framework. We also propose `empirical’ variants of primal-dual algorithms for constrained stochastic optimization. The overarching goal is to develop a common mathematical framework, and analysis tools, within which a large class of iterative algorithms for stochastic control and optimization fit.
Rahul Jain is the Kenneth C. Dahlberg Early Career Chair and Associate Professor of Electrical Engineering and Computer Science at the University of Southern California, Los Angeles. He also has a courtesy appointment in the ISE department. He received a B.Tech (EE) from the Indian Institute of Technology, Kanpur, an MS (ECE) from Rice University, and an MA in Statistics and a PhD in EECS from the University of California, Berkeley. He also spent time in the industry at the IBM T J Watson Research Center, Yorktown Heights, NY. He has received many awards including the ONR Young Investigator award in 2012, the NSF CAREER award in 2010, an IBM Faculty award in 2010, etc. His interests span stochastic control and optimization, statistical learning, risk-aware optimization, stochastic networks, and game theory. He currently serves as an Associate Editor for the IEEE Trans. on Network Science and Engineering and the IEEE Control Systems Society.