CS Paper Radar

Weak Convexity and Proximal Bundle Methods for Nonsmooth Policy Optimization in Robust Control

Yuto Watanabe, Feng-Yi Liao, Yang Zheng

eess.SY math.OC ·submitted 2026-09-05 17:43 UTC · v1

Abstract

We study policy optimization for discrete-time robust $\mathcal{H}_\infty$ control with static output-feedback, and present the first feasibility-preserving algorithm with a deterministic, non-asymptotic complexity guarantee. This problem naturally leads to a nonsmooth and nonconvex optimization over the set of stabilizing feedback gains. We first establish several structural properties of the $\mathcal{H}_\infty$ cost. In particular, we show that the cost is weakly convex on every convex subset of a sublevel set. For the state-feedback case, we further establish a weak Polyak--Łojasiewicz inequality, which ensures that every stationary point is globally optimal. Building on these properties, we develop a proximal bundle method for $\mathcal{H}_\infty$ policy optimization. The proposed method can be viewed as an implementable approximation of the proximal point method and uses only function value and subgradient information. We show that all iterates remain stabilizing and establish a deterministic non-asymptotic complexity bound of $\mathcal{O}(\max\{η^{-4},ε^{-2}\})$ for finding an $(η,ε)$-stationary point. Numerical experiments illustrate our theoretical results.

Comment
36 pages, 15 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Zeroth-Order Nonsmooth Nonconvex Optimization with Convex Liftings and Its Application to State-Feedback $H_\infty$ Policy Optimization

eess.SY math.OC ·2026-08-24 ·Xuhao Wang, Yujie Tang
similarity 0.75
Abstract

Direct policy optimization is widely used in reinforcement learning and control, but generally leads to nonconvex optimization problems. For state-feedback $H_\infty$ control, the policy objective is also nonsmooth, despite possessing a benign landscape whose hidden convexity can be revealed by the recently developed extended convex lifting framework. Motivated by recent advances in hidden convex optimization, we study zeroth-order optimization of nonsmooth, nonconvex problems admitting a convex lifting. We propose a zeroth-order proximal point algorithm: An inexact proximal-point outer loop constructs strongly convex subproblems, while an inner loop approximately solves each subproblem using only function evaluations. With probability at least $1-δ$, our proposed algorithm returns an $ε$-optimal solution using $\widetilde{O}\left(dε^{-3}\right)$ function evaluations, while all iterates remain feasible without explicit projection. Finally, we verify that the assumptions underlying our analysis hold for discrete-time state-feedback $H_\infty$ policy optimization, yielding an oracle complexity of $\widetilde{O}\left(n_u n_xε^{-3}\right)$ for attaining a prescribed objective value gap, where $n_u\times n_x$ is the dimension of the feedback gain to be optimized over.

0.52

Algorithmic Optimality Guarantees for Nonsmooth $H_\infty$ Output-Feedback Policy Search

cs.LG math.OCeess.SY ·2026-09-05 ·Ashkan Soleymani, Patrick Jaillet
publishedbenchmarktheory similarity 0.73
Abstract · Appeared at The 65th IEEE Conference on Decision and Control (CDC), 2026

We study continuous-time full-order dynamic output-feedback $H_\infty$ policy search, a nonconvex and nonsmooth problem. Direct policy search is a central paradigm in reinforcement learning and continuous control, but rigorous guarantees remain scarce in robust output-feedback settings. The $H_\infty$ problem is a canonical benchmark because it captures disturbance attenuation and robustness while exposing the hard nonsmooth geometry of policy-space optimization. We prove that on the exact identity-gauge slice of the extended convex lift, $\varepsilon$-stationarity yields $O(\varepsilon)$-suboptimality on compact exact slices, which in turn yields convergence-rate guarantees for nonsmooth policy-search methods. This result addresses the finite-time optimality-gap question raised by Guo and Hu [2022] in the more general dynamic output-feedback $H_\infty$ policy-search setting. We further use the established value equivalence supplied by extended convex lifting to formulate a nonstrict-feasibility bisection method with one final strict-feasibility recovery step, yielding an explicit $\varepsilon$-optimal stabilizing controller. These results provide a quantitative and algorithmic strengthening of prior qualitative optimality theory for nonsmooth $H_\infty$ policy search.

0.17

Minimax optimal dual control of positive systems: an exact solution for scalar input-sign uncertainty

eess.SY math.OC ·2026-08-15 ·Fethi Bencherki, Tomas J. Meijer, Anders Rantzer
similarity 0.64
Abstract

While recent advances in minimax dual control have led to exact solutions for uncertain general linear time-invariant systems as well as (sub)optimal dual controllers, corresponding results for linear positive systems are still lacking. This paper aims to fill this gap and thereby pave the way toward scalable dual control algorithms. We study the general minimax optimal dual control problem for positive linear systems with unknown dynamics and reformulate it as a standard zero-sum dynamic game. By allowing randomized control inputs, we solve the corresponding Bellman equation exactly for the scalar case with sign uncertainty in the input. This yields an implicit dual control policy that is optimal both in terms of cost and $\ell_1$-gain. The optimal dual policy uses exploration in a specific region of the hyperstate space to conduct optimal probing. Outside this exploration regime, the controller reduces to a deterministic certainty equivalence policy, indicating that sufficient information has been obtained to identify the correct input direction. In addition, these results allow us to analyze fundamental limitations of minimax dual control for positive systems and provide a foundation for more general dual control problems for positive systems for future work.

0.04

Incremental Stability of Gradient Flows under Generalized Polyak-Łojasiewicz Inequalities and Its Implications for General Systems

eess.SY math.OC ·2026-10-29 ·Andreas Oliveira, Arthur C. B. de Oliveira, Mario Sznaier, Eduardo Sontag
similarity 0.63
Abstract

Gradient flows of twice continuously differentiable strongly convex and convex objectives are, respectively, incrementally exponentially stable and non-expansive in the Euclidean metric. In this work, we investigate to what extent these properties extend to nonconvex objectives satisfying generalized Polyak-Łojasiewicz inequalities. For objectives with a unique minimizer, we establish conditions under which the gradient flow is contracting in a state-dependent Riemannian metric and incrementally exponentially stable. For objectives with nonunique minimizers, we generalize the non-expansivity of convex objectives to incremental stability for more general nonconvex objectives. We focus on incremental stability due to its implication to convergence to equilibrium points; when paired with a Lyapunov function it implies pointwise convergence to a minimizer and continuity of the endpoint map. Along the way, we derive new structural results for incrementally stable nonlinear systems and extend the analysis to Heavy-Ball and Dynamical Inertial Newton flows.

0.28

First-order smoothed exact-penalty methods for equality-constrained regularized nonconvex optimization

cs.LG math.OC ·2026-11-15 ·Shiji Zuo, Qihang Lin, Wei Liu, Yangyang Xu
theory similarity 0.62
Abstract

We consider regularized nonconvex optimization over a closed convex set $\mathcal{X} \subseteq \mathbb{R}^d$, which involves a convex nonsmooth regularizer $r$ in the objective and $n$ smooth equality constraints. To find a near-KKT point of the problem, we propose a prox-linear first-order method, named as SEPi-Prox, based on a smoothed exact-penalty formulation. At each outer iteration of SEPi-Prox, a strongly convex prox-linear subproblem is formed and solved inexactly to a sufficient accuracy. Under a local non-singularity condition that is weaker than some other commonly used regularity conditions or constraint qualifications, SEPi-Prox finds an $ε$-KKT point within $O(ε^{-2})$ first-order oracle calls, matching the lower bound for unconstrained smooth nonconvex optimization. We employ Nesterov's accelerated proximal-gradient method (APG) and a dual cutting-plane method (DCP) for the prox-linear subproblems. Let $\mathcal{C}_{\mathrm{FO}}$ and $\mathcal{C}_r$ denote the numbers of arithmetic operations of evaluating one first-order oracle and one proximal mapping of $r$ over $\mathcal{X}$, respectively. Then SEPi-Prox requires $\widetilde{O}(\mathcal{C}_{\mathrm{FO}}ε^{-2} + (dn + \mathcal{C}_r)ε^{-5/2})$ and $\widetilde{O}((\mathcal{C}_{\mathrm{FO}} + dn^2 + n\mathcal{C}_r + n^{3.373})ε^{-2})$ total arithmetic operations to produce an $ε$-KKT point, respectively by using APG and DCP as the subsolver. The latter result is preferable when $n$ is small and nearly matches the optimal dependence on $ε$. Numerical experiments on instances of the multi-class Neyman-Pearson classification demonstrate the efficiency of SEPi-Prox with both subsolvers.

0.04

Sharp Critical Minimax Laws and No-Learning Thresholds in Continuous-Time Adaptive Control

cs.LG math.OC ·2026-09-27 ·Chen Jia
theory similarity 0.62
Abstract

We study episodic continuous-time control with an unknown vector control gain, scalar state, quadratic action cost, and smooth convex terminal cost. In the scalar Gaussian experiment, let $Δ(H)$ denote the minimax improvement over zero control and set $δ=\sqrt2H^2-1$. We prove the critical law $$ Δ(H)\asymp δ^4\sqrt{\log(1/δ)} \qquad (δ\downarrow0), $$ with a matching lower and upper bound. The lower bound follows from a uniform deficit--energy inequality valid for fully adaptive controls with unbounded amplitudes, while a moving soft-threshold feedback attains the rate. For local parameters $θ=N^{-1/4}h$, $|h|\le H$, we show that the normalized minimax regret over $N$ episodes is within $O(N^{-1/2})$ of a fixed-horizon Gaussian sequential control problem, without an additional dimension factor. The terminal task enters the limit only through $c_g=\operatorname{Var}(g(Z))$. The Gaussian problem exhibits an exact no-learning phase transition: $$ C_d^T(H)=TH^2/2 \iff H^4T\le d^2/2, $$ yielding the asymptotic task boundary $c_gH^4=d^2/2$.

0.27

ALDER: A Single-Loop Augmented-Lagrangian Damped Extragradient Method for Nonconvex--Concave Minimax Problems with Nonlinear Coupled Constraints

cs.LG math.OCstat.ML ·2026-10-31 ·H. Zhang, M. Zhang, Z. Xu, Y. -H. Dai
similarity 0.61
Abstract

ALDER, a single-loop augmented-Lagrangian damped extragradient method, is proposed for smooth nonconvex--concave minimax problems with nonlinear coupled inequality constraints. Within an augmented-Lagrangian framework, ALDER combines prediction--correction steps for the primal variables with explicit projected-and-relaxed multiplier updates in a single loop. The penalty parameter is fixed throughout each run, eliminating inner-loop subproblem solves and iterative penalty updates. We establish uniform boundedness of the relaxed multiplier sequence and, under an extended Mangasarian--Fromovitz constraint qualification, boundedness of the projected output multiplier. Building on these bounds, we show that ALDER finds an $\varepsilon$-KKT point within $\mathcal{O}(\varepsilon^{-7/2})$ complete first-order oracle evaluations in the strongly concave setting and $\mathcal{O}(\varepsilon^{-4})$ in the concave setting. These bounds improve upon the best known complexity bounds for multi-loop algorithms for this problem class, achieved by FAL, by removing a $\log(1/\varepsilon)$ factor, while retaining a single-loop update structure.

0.18

Finite-Time Guarantees for Constrained Reinforcement Learning under Partial Observability

cs.LG ·2026-10-15 ·Valentina Zaccaria, Philip Jordan, Tingting Ni, Gian Antonio Susto, Maryam Kamgarpour
similarity 0.61
Abstract

We study reinforcement learning in constrained partially observable Markov decision processes (CPOMDPs), where an agent maximizes reward subject to a cost constraint using only incomplete information about the underlying state. The lack of state observability may require optimal policies to depend on arbitrarily long observation-action histories, making planning and learning challenging. We leverage recent advances in finite-memory approximations of POMDPs and represent finite history windows as states of a constrained MDP. We then develop a primal--dual algorithm that provides the first non-asymptotic guarantees that jointly bound average reward suboptimality and constraint violation in the original CPOMDP. A key challenge is that this finite-window approximation affects both reward values and the set of feasible policies. Under a filter-stability assumption, we derive bounds relating optimality and feasibility in the finite-state model to those in the original CPOMDP, with approximation errors that decay geometrically with the window length. Experiments in partially observable gridworlds demonstrate the effectiveness of our approach.

0.10