Search

We consider the classic stochastic linear quadratic regulator (LQR) problem under an infinite horizon average stage cost. By leveraging recent policy gradient methods from reinforcement learning, we obtain a first-order method that finds a stable feedback law whose objective function gap to the optima is at most $\varepsilon$ with high probability using $\tilde{O}(1/\varepsilon)$ samples, where $\tilde{O}$ hides polylogarithmic dependence on $\varepsilon$. Our proposed method seems to have the best dependence on $\varepsilon$ within the model-free literature without the assumption that all policies generated by the algorithm are stable almost surely, and it matches the best-known rate from the model-based literature, up to logarithmic factors. The improved dependence on $\varepsilon$ is achieved by showing the accuracy scales with the variance rather than the standard deviation of the gradient estimation error. Our developments that result in this improved sampling complexity fall in the category of actor-critic algorithms. The actor part involves a variational inequality formulation of the stochastic LQR problem, while in the critic part, we utilize a conditional stochastic primal-dual method and show that the algorithm has the optimal rate of convergence when paired with a shrinking multi-epoch scheme., Comment: Pre-print. 23 pages, 1 figure. Update fixes some parts of proof that had incorrect constants and addresses stability of policy. Comments are welcome

We address the problems of computing operator norms of matrices induced by given norms on the argument and the image space. It is known that aside of a fistful of "solvable cases," most notably, the case when both given norms are Euclidean, computing operator norm of a matrix is NP-hard. We specify rather general families of norms on the argument and the images space ("ellitopic" and "co-ellitopic," respectively) allowing for reasonably tight computationally efficient upper-bounding of the associated operator norms. We extend these results to bounding "robust operator norm of uncertain matrix with box uncertainty," that is, the maximum of operator norms of matrices representable as a linear combination, with coefficients of magnitude $\leq1$, of a collection of given matrices. Finally, we consider some applications of norm bounding, in particular, (1) computationally efficient synthesis of affine non-anticipative finite-horizon control of discrete time linear dynamical systems under bounds on the peak-to-peak gains, (2) signal recovery with uncertainties in sensing matrix, and (3) identification of parameters of time invariant discrete time linear dynamical systems via noisy observations of states and inputs on a given time horizon, in the case of "uncertain-but-bounded" noise varying in a box.

The focus of this paper is on stochastic variational inequalities (VI) under Markovian noise. A prominent application of our algorithmic developments is the stochastic policy evaluation problem in reinforcement learning. Prior investigations in the literature focused on temporal difference (TD) learning by employing nonsmooth finite time analysis motivated by stochastic subgradient descent leading to certain limitations. These encompass the requirement of analyzing a modified TD algorithm that involves projection to an a-priori defined Euclidean ball, achieving a non-optimal convergence rate and no clear way of deriving the beneficial effects of parallel implementation. Our approach remedies these shortcomings in the broader context of stochastic VIs and in particular when it comes to stochastic policy evaluation. We developed a variety of simple TD learning type algorithms motivated by its original version that maintain its simplicity, while offering distinct advantages from a non-asymptotic analysis point of view. We first provide an improved analysis of the standard TD algorithm that can benefit from parallel implementation. Then we present versions of a conditional TD algorithm (CTD), that involves periodic updates of the stochastic iterates, which reduce the bias and therefore exhibit improved iteration complexity. This brings us to the fast TD (FTD) algorithm which combines elements of CTD and the stochastic operator extrapolation method of the companion paper. For a novel index resetting policy FTD exhibits the best known convergence rate. We also devised a robust version of the algorithm that is particularly suitable for discounting factors close to 1., Comment: arXiv admin note: text overlap with arXiv:2011.02987

In this paper we first present a novel operator extrapolation (OE) method for solving deterministic variational inequality (VI) problems. Similar to the gradient (operator) projection method, OE updates one single search sequence by solving a single projection subproblem in each iteration. We show that OE can achieve the optimal rate of convergence for solving a variety of VI problems in a much simpler way than existing approaches. We then introduce the stochastic operator extrapolation (SOE) method and establish its optimal convergence behavior for solving different stochastic VI problems. In particular, SOE achieves the optimal complexity for solving a fundamental problem, i.e., stochastic smooth and strongly monotone VI, for the first time in the literature. We also present a stochastic block operator extrapolations (SBOE) method to further reduce the iteration cost for the OE method applied to large-scale deterministic VIs with a certain block structure. Numerical experiments have been conducted to demonstrate the potential advantages of the proposed algorithms. In fact, all these algorithms are applied to solve generalized monotone variational inequality (GMVI) problems whose operator is not necessarily monotone. We will also discuss optimal OE-based policy evaluation methods for reinforcement learning in a companion paper.

This work addresses the finite-horizon robust covariance control problem for discrete-time, partially observable, linear system affected by random zero mean noise and deterministic but unknown disturbances restricted to lie in what is called ellitopic uncertainty set (e.g., finite intersection of centered at the origin ellipsoids/elliptic cylinders). Performance specifications are imposed on the random state-control trajectory via averaged convex quadratic inequalities, linear inequalities on the mean, as well as pre-specified upper bounds on the covariance matrix. For this problem we develop a computationally tractable procedure for designing affine control policies, in the sense that the parameters of the policy that guarantees the aforementioned performance specifications are obtained as solutions to an explicit convex program. Our theoretical findings are illustrated by a numerical example., Comment: 29 pages, 1 figure

In this work we provide a computationally tractable procedure for designing affine control policies, applied to constrained, discrete-time, partially observable, linear systems subject to set bounded disturbances, stochastic noise and potentially Markovian switching over a finite horizon. We investigate the situation when performance specifications are expressed via averaged quadratic inequalities on the random state-control trajectory. Our methodology also applies to steering the density of the state-control trajectory under set bounded uncertainty. Our developments are based on expanding the notion of affine policies that are functions of the so-called "purified outputs", to the class of Markov jump linear systems. This re-parametrization of the set of policies, induces a bi-affine structure in the state and control variables that can further be exploited via robust optimization techniques, with the approximate inhomogeneous $S$-lemma being the cornerstone. Tractability is understood in the sense that for each type of performance specification considered, an explicit convex program for selecting the parameters specifying the control policy is provided. Our contributions to the existing literature on the subject of robust constrained control lies in the fact that we are addressing a wider class of systems than the ones already studied, by including Markovian switching, and the consideration of quadratic inequalities rather than just linear ones. Our work expands on the previous investigations on finite horizon covariance control by addressing the robustness issue and the possibility that the full state may not be available, therefore enabling the steering of the state-control trajectory density in the presence of disturbances under partial observation., Comment: 36 pages, 2 figures