Asymptotic optimality of finite models in stochastic control
Abstract: For stochastic control problems with uncountable state and action spaces, the computation of optimal policies is known to be prohibitively hard. In this talk, we will present conditions under which finite models obtained through quantization of the state and action sets can be used to construct approximately optimal policies. Under further conditions, we obtain explicit rates of convergence to the optimal cost of the original problem as the quantization rate increases. We consider various setups for the continuity conditions imposed on the transition kernels, the state and action spaces, and the partially observed case (where the relaxed nature of our assumptions finds particularly important applications). Our approximation results may be considered to be complete in that whenever we could state the existence of optimal policies, an approximation result follows; thus providing relaxed conditions compared with existing results in the literature. Using information theoretic methods, we show that the convergence rates are order-optimal for a further class of problems.
We then extend our analysis to decentralized stochastic control problems, also known as team problems, which are increasingly important in the context of networked control systems. We present new existence results for optimal policies, and building on these show that for a large class of sequential dynamic team problems one can construct a sequence of finite models obtained through the quantization of measurement and action spaces whose solutions constructively converge to the optimal cost. Some examples will be provided; the celebrated counterexample of Witsenhausen is an important special case that will be discussed. (Joint work with Naci Saldi and Tamas Linder).