Stochastic Approximation for Nonlinear Discrete Stochastic Control: Finite-Sample Bounds for Exponentially Stable Systems

We consider a nonlinear discrete stochastic control system, and our goal is to design a feedback control policy in order to lead the system to a prespecified state. We adopt a Stochastic Approximation (SA) viewpoint of this problem. It is known that by solving the corresponding continuous-time deterministic system, and using the resulting feedback control policy, one ensures almost sure convergence to the prespecified state in the discrete system. In this paper, we adopt such a control mechanism and provide its finite-sample convergence bounds whenever a Lyapunov function is known for the continuous system. In particular, we establish the rate
$O(1/\varepsilon)$
to guarantee that the mean square error is less than
$\varepsilon$
where the Lyapunov function for the continuous system is non-smooth and gives exponential rates. Our proof relies on constructing a Lyapunov function for the discrete system based on the given Lyapunov function for the continuous system, and then appropriately smoothing the given function using the Moreau envelope. We present a numerical experiment in the selector control example to validate the established rate.