The hidden staircase: proving trial-and-error robust control finds the global best

Picture a drone fighting a strong gust of wind. Or an autonomous car steadying itself against a sudden sideways blast from a passing truck. The regulator inside has to do something remarkably hard: make a decision in the moment, with only the information available right then, that is somehow optimal against the worst possible disturbance it might face. It can't predict the future. It just has to be robust to whatever comes.

This is the $H_{\infty }$ (pronounced "H-infinity") control problem, one of the pillars of modern robust control engineering. And for decades, the standard mathematical recipe for solving it was elegant but demanding: you needed a complete, accurate model of the system's dynamics, and then you solved a known equation. That works beautifully in textbooks. In the real world, where systems are messy, partially known, and nonlinear, it often breaks down.

A newer, more flexible philosophy has arisen in recent years: just let an algorithm learn the controller by trial and error, the way reinforcement learning teaches a robot to walk. This "policy optimization" approach needs no model and scales to huge problems. But it comes with a steep theoretical price. The function being optimized—the "worst-case cost" you're trying to shrink—is both nonconvex and nonsmooth, the two traits that make optimization hardest. There are valleys, cliffs, and flat regions where the gradient is undefined. For years, no one could prove that a trial-and-error method would actually converge to the global best controller, rather than getting stuck in some local trap.

Xuhao Wang and Yujie Tang, at Peking University, have now squeezed a guarantee out of this problem. Their new paper proves that a simple derivative-free algorithm—one that works purely by testing candidate controllers and observing their costs, never needing gradients—can find a globally optimal robust controller with a rigorous, high-probability guarantee on the number of trials required. The catch, and the beauty, is that they exploit a "hidden convexity" in the problem: beneath the jagged, nonconvex surface of the cost function lies a smooth, convex landscape, visible only if you know how to lift it into a higher-dimensional space.

The number that makes this concrete: to get within a small tolerance $ϵ$ of the best possible controller, the algorithm needs on the order of $\tilde{O}(d{ϵ}^{-3})$ function evaluations, where $d$ is the dimension of the problem. For the $H_{\infty }$ control case specifically, that's $\tilde{O}(n_u{n}_x{ϵ}^{-3})$—the product of the number of control inputs and state variables. And unlike most optimization methods, it never needs to "project" its iterates back into the feasible region, because that feasible region isn't even convex.

The Science

Let's get precise about what's being optimized. Consider a discrete-time linear system

$$x(t+1)=Ax(t)+Bu(t)+B_{w}w(t),$$

where $x(t)$ is the state, $u(t)$ the control input, and $w(t)$ an adversarial disturbance with bounded energy. The $H_{\infty }$ control problem asks: find the feedback policy $u(t)=Kx(t)$ that minimizes the worst-case quadratic cost over all disturbances of unit bounded energy. Formally, the objective is

$$J_{\infty }(K)={\left[\underset{w:\Vert w{\Vert }_{{\ell }_2}\le 1}{\sup }\sum _{t=0}^{\infty }x(t{)}^{\mathsf{T}}(Q+K^{\mathsf{T}}RK)x(t)\right]}^{1/2},$$

subject to the closed-loop dynamics $x(t+1)=(A+BK)x(t)+B_{w}w(t)$ and $x(0)=0$.

Here's where the trouble begins. Classical control theory tells us the optimal controller exists, and that $J_{\infty }(K)$ is finite if and only if the matrix $A+BK$ is Schur stable—all its eigenvalues strictly inside the unit circle. The set of stabilizing gains,

$$\mathcal{K}=\{K:A+BK\text{ is Schur stable}\},$$

is the domain we must stay inside. And here's the first wall: $\mathcal{K}$ is an open set that can be nonconvex and unbounded. In plain terms, it's a region with no clearly defined boundary you can lean against, and it curves. Almost all optimization machinery assumes you can project onto a closed convex set. Here you can't.

The function $J_{\infty }$ adds a second wall: it's continuous but not everywhere differentiable, and it's coercive—blowing up to infinity as $K$ approaches the boundary of stability or grows large. This is precisely the nightmare scenario for optimization theory: nonconvex, nonsmooth, with an open feasible region.

Yet three recent bodies of work—by [24], [63], and the "Extended Convex Lifting" framework of Tang and others [70]—have revealed that hiding beneath this jagged surface is a convex structure. The trick is to append a Lyapunov variable, lifting the problem into a higher dimension where the epigraph becomes convex. This is the classical LMI (linear matrix inequality) reformulation of $H_{\infty }$ control, which has been known in robotics and aerospace for decades as a way to solve the problem when you have a model. What's new is using it to analyze the landscape of model-free policy optimization.

The key consequence: every Clarke stationary point of $J_{\infty }$ is globally optimal. And if every stationary point is a global solution, then any method that reliably descends the landscape will find the global optimum, no matter how nonconvex the terrain looks. What was missing was a rigorous guarantee.

What They Found

Wang and Tang's contribution is a concrete algorithm with a proven rate. They propose a zero-th-order proximal point algorithm, which sounds forbidding but decomposes into two clean loops.

The outer loop builds a sequence of subproblems. At each step, it takes the current candidate $x^{(k)}$ and constructs a strongly convex surrogate:

$$\underset{y\in \mathcal{K}}{\min }f(y)+\frac{1}{2\eta }\Vert y-x^{(k)}{\Vert }^2.$$

The quadratic penalty term with step size $\eta$ makes this surrogate strongly convex, even though $f$ itself is not. Solving this surrogate pulls the iterates toward the global minimum of $f$, a trick borrowed from the classical proximal point method [52].

The inner loop approximately solves each surrogate using zeroth-order (derivative-free) gradient descent. It never computes a true gradient—which would require model knowledge and, for $H_{\infty }$, is notoriously hard to obtain [2]. Instead, it estimates the gradient by evaluating the function at nearby points, using a central-difference two-point estimator. This is the standard trick of "if you can't differentiate, probe": evaluate $f$ at $y+\delta u$ and $y-\delta u$ along a random direction $u$, and divide the difference by $2\delta$.

The subtlety, and one of the paper's genuine technical contributions, is that the inner loop uses a specially tailored step size rule so that every intermediate iterate stays inside the open, nonconvex feasible region $\mathcal{K}$—with no projection step, because projection is impossible when the region isn't convex. Under randomness from the gradient estimators, keeping the iterates in-bounds requires a cleverly tuned radius, and the authors prove this happens with high probability.

The headline result (Theorem 1): given any sufficiently small tolerance $ϵ$ and failure probability $\delta$, the algorithm returns an $ϵ$-optimal solution—meaning $f(x^{(N)})-f^{\ast }\le ϵ$, where $f^{\ast }$ is the true global optimum—with probability at least $1-\delta$, using

$$\tilde{O}\left(d{ϵ}^{-3}\right)$$

function evaluations, where $d$ is the problem dimension and $\tilde{O}$ hides polylogarithmic factors.

Two things are striking about this number. First, the ${ϵ}^{-3}$ rate matches the best-known first-order complexity for nonsmooth hidden-convex optimization—but achieved here with only function evaluations, no gradients. The only penalty for dropping derivative information is the factor of $d$ (or, for the control application, $n_u{n}_x$). Second, the guarantee is on the objective value gap—how far you are from the global optimum in cost terms—not merely on some technical stationarity measure. That's the distinction the paper is at pains to emphasize, because previous results for $H_{\infty }$ policy optimization ([24], [25], [63]) only certified convergence to stationary points in the sense of the Goldstein subdifferential. Being at a stationary point is encouraging, but it doesn't tell you how good the cost is. Being at a point with $f(x)-f^{\ast }\le ϵ$ tells you exactly.

For the state-feedback $H_{\infty }$ problem itself, the authors verify all the technical assumptions needed for their analysis to hold, yielding a concrete oracle complexity of

$$\tilde{O}\left(n_u{n}_x{ϵ}^{-3}\right)$$

for the feedback gain dimension $n_u\times n_x$. This is the first explicit objective-value-gap complexity guarantee for this problem.

Why This Changes Things

To appreciate why this matters, consider what the alternatives require. The classical approaches to $H_{\infty }$ synthesis—Riccati equations [72] and LMI-based semidefinite programming [7], [20]—both demand an explicit, accurate model of the system. Feed them a real plant with unknown parameters, mismatched dynamics, and calibration drift, and their guarantees evaporate. Direct policy optimization, by contrast, is model-free: it just pokes the system, watches the cost, and adjusts. This is why the control community has increasingly turned to policy optimization for complex, partially known systems.

But model-free policy optimization had a theoretical credibility gap. Before this paper, the rigorous guarantees one could state for $H_{\infty }$ policy optimization were of the form "the algorithm finds a stationary point." That's useful but incomplete: a stationary point of a nonconvex function could, in principle, be a poor local minimum. The paper closes this gap by establishing that, for problems with a convex lifting, you can get a genuine global optimality guarantee with a clean rate.

There's a deeper conceptual point about the nature of the problem. The $H_{\infty }$ cost function is a worst-case quantity: it measures performance against the best possible adversarial disturbance. This makes it fundamentally different from typical machine-learning objectives, which average over a data distribution. The nonsmoothness of $J_{\infty }$ is intrinsic—it comes from the "sup" over disturbances, which creates corners and kinks in the landscape. It's not an artifact of poor formulation. So the fact that a zeroth-order method can navigate it with a provable global rate is a genuine structural insight, not a technical convenience.

The work also sits within a broader recent movement in optimization: the recognition that many seemingly intractable nonconvex problems possess "hidden convexity" that algorithms can exploit. The ECL framework [70] has shown this for LQR, LQG, and both state- and output-feedback $H_{\infty }$ control. This paper converts that structural insight into an algorithmic guarantee with a specific complexity rate, bridging the gap between "the landscape is benign" and "here is an algorithm that provably exploits the benignness."

The zeroth-order aspect deserves emphasis for practical reasons. In real control systems, obtaining gradient information about $J_{\infty }$ is genuinely hard: it requires either an accurate model or sophisticated sensitivity analysis that may be unstable. But function evaluations are easy—you run the controller, subject the system to disturbances, and measure its worst-case cost. Any physical system you can experiment on gives you function evaluations. So a method whose only oracle is function evaluations is one that works with the most primitive, most universally available source of information. This is precisely why derivative-free policy optimization is seen as the promising route to controller synthesis in data-driven settings where models are unavailable or prohibitively expensive to build [25].

What's Next

The paper's results open several natural frontiers, and it's honest about its own limitations. First, the $\tilde{O}(d{ϵ}^{-3})$ complexity, while matching the best first-order bound up to the dimension factor, is not necessarily optimal for zeroth-order methods in this setting. Whether a faster rate is achievable—perhaps $\tilde{O}({ϵ}^{-2})$—remains an open question that would require either a different algorithm or a lower bound argument.

Second, the paper treats state feedback, where the controller observes the full state $x(t)$. Output feedback—where you only observe a noisy function of the state—is strictly harder and is the setting of [69]. Extending the objective-value-gap guarantees there would be a significant step, since most real systems don't grant full state access.

Third, and most importantly for real-world deployment, the guarantee is about sample complexity in the idealized setting where function evaluations are noiseless. Real systems have measurement noise, and the paper's framework doesn't yet address stochastic or noisy oracle models. Bridging to that setting—showing what happens when each evaluation of $J_{\infty }$ carries uncertainty—would be the natural next step toward making these guarantees usable on actual hardware.

There's also a satisfying open thread in the pure-optimization direction. The paper's feasibility-without-projection technique—keeping iterates inside an open, nonconvex region using a carefully tuned step size—is a clever piece of machinery that could generalize. The authors suggest it might apply to other control problems whose feasible regions are open and nonconvex, such as LQR and LQG, whose landscape properties were analyzed in [8], [46], [58]. A unified convex-lifting treatment of all the classical control problems, with matching zeroth-order complexity guarantees, appears within reach.

For the engineer in the field, the significance is a promise: the trial-and-error approach to robust controller design, long practiced because it seemed to work, now has a formal certificate that it works—that it finds the global best robust controller, not just some stopping point. And it does so using only the simplest possible information: the system's measured worst-case cost. That's a quiet theoretical milestone, and it's the kind that eventually makes its way into the drones, cars, and robots that navigate uncertain worlds.