Search for: All records

Zeroth-order optimization (ZO) is widely used for solving black-box optimization and control problems. In particular, single-point ZO (SZO) is well-suited to online or dynamic problem settings due to its requirement of only a single function evaluation per iteration. However, SZO suffers from high gradient estimation variance and slow convergence, which severely limit its practical applicability. To overcome this limitation, we propose a novel yet simple SZO framework termed regression-based SZO (ReSZO), which substantially enhances the convergence rate. Specifically, ReSZO constructs a surrogate function via regression using historical function evaluations and employs the gradient of this surrogate function for iterative updates. Two instantiations of ReSZO, which fit linear and quadratic surrogate functions respectively, are introduced. Moreover, we provide a non-asymptotic convergence analysis for the linear instantiation of ReSZO, showing that its convergence rates are comparable to those of two-point ZO methods. Extensive numerical experiments demonstrate that ReSZO empirically converges two to three times faster than two-point ZO in terms of function query complexity. 

Network Markov Decision Processes (MDPs), which are the de-facto model for multi-agent control, pose a significant challenge to efficient learning caused by the exponential growth of the global state-action space with the number of agents. In this work, utilizing the exponential decay property of network dynamics, we first derive scalable spectral local representations for multiagent reinforcement learning in network MDPs, which induces a network linear subspace for the local $$Q$$-function of each agent. Building on these local spectral representations, we design a scalable algorithmic framework for multiagent reinforcement learning in continuous state-action network MDPs, and provide end-to-end guarantees for the convergence of our algorithm. Empirically, we validate the effectiveness of our scalable representation-based approach on two benchmark problems, and demonstrate the advantages of our approach over generic function approximation approaches to representing the local $$Q$$-functions. 

The problem of controller reduction has a rich history in control theory. Yet, many questions remain open. In particular, there exist very few results on the order reduction of general non-observer based controllers and the subsequent quantification of the closed-loop performance. Recent developments in model-free policy optimization for Linear Quadratic Gaussian (LQG) control have highlighted the importance of this question. In this paper, we first propose a new set of sufficient conditions ensuring that a perturbed controller remains internally stabilizing. Based on this result, we illustrate how to perform order reduction of general (non-observer based) output feedback controllers using balanced truncation and modal truncation. We also provide explicit bounds on the LQG performance of the reduced-order controller. Furthermore, for single-input-single-output (SISO) systems, we introduce a new controller reduction technique by truncating unstable modes. We illustrate our theoretical results with numerical simulations. Our results will serve as valuable tools to design direct policy search algorithms for control problems with partial observations.