Bounded Linear Programs for Data-Driven Optimal Control via Moment-Matching

Imagine trying to steer a ship through a storm without a map, a compass, or even a clear view of the horizon. You can only see the waves as they crash against the hull and feel the wind shifting in your face. This is the reality for many engineers and scientists who must control complex machines, from autonomous vehicles to power grids, when they do not have a complete mathematical model of how those systems behave. Instead of relying on a perfect blueprint, they must learn by doing: observing how the system reacts to different inputs, recording the costs of mistakes, and gradually piecing together a strategy that works. For decades, a powerful mathematical tool called linear programming has offered a way to find the best possible strategy in such situations. However, this tool has a notorious flaw: as the number of variables describing the system grows, the calculations often spiral out of control, producing answers that are infinitely large and therefore useless. It is like trying to balance a scale with weights that keep getting heavier until the beam snaps.

A team of researchers at ETH Zurich has found a way to keep that scale balanced, even when the system is complex and the data is scarce. They developed a new method to guide the mathematical search for an optimal control policy, ensuring that the solution remains finite and practical. By using a technique called moment-matching, which essentially aligns the mathematical "shape" of the desired solution with the patterns found in the observed data, they can guarantee that the computer will find a stable answer. Their work suggests that it is possible to design controllers for high-dimensional, nonlinear systems—machines with many moving parts and complex behaviors—using only a limited amount of data, without needing to know the underlying physics of the system beforehand. This approach transforms a theoretical possibility into a reliable engineering tool, opening the door to smarter, more adaptive control systems for the real world.

The core challenge the researchers addressed is the difficulty of keeping these mathematical calculations from running away. In the world of optimal control, the goal is to find a set of rules that tells a machine what to do at every moment to minimize a cost, such as energy use or travel time. When the system is simple, standard methods work fine. But when the system is complex, with many dimensions like position, velocity, and acceleration all interacting, the number of possible scenarios explodes. The researchers noted that previous attempts to solve this using data-driven methods often failed because the mathematical problem became unbounded. This means the computer would try to find a solution that grew infinitely large, effectively crashing the calculation. While some earlier methods tried to fix this by adding artificial constraints or regularizers, these often distorted the final result, making the controller less effective. Others relied on having massive amounts of data, which is often impossible to gather in real-world scenarios where experiments are expensive or dangerous.

To solve this, the authors introduced a method that uses the data itself to define the boundaries of the search. Instead of guessing where the solution should lie, they looked at the specific patterns in the data collected from the system's movements. They treated the data as a collection of points in a high-dimensional space and asked a simple question: can we find a direction for our search that is supported by these points? If the direction of the search aligns with the "cone" of possibilities created by the data, the calculation is guaranteed to stay finite. They demonstrated that by carefully selecting a cost vector—a mathematical weight that tells the computer what to prioritize—based on the observed data, they could ensure the solution remained bounded. This is akin to setting a destination for a journey that is guaranteed to be reachable given the terrain you have already mapped, rather than aiming for a point that might be off the edge of the world.

The researchers tested this idea on two very different types of systems. First, they looked at linear time-invariant systems, which are machines that behave in a predictable, straight-line fashion. They simulated these systems with increasing complexity, from small setups to ones with thirty different state variables. In these tests, they compared their new method against a standard approach that uses a fixed, unchanging cost vector. The results were striking: while the standard method failed to find a solution for systems with more than two state variables, their moment-matching approach successfully found finite solutions for systems with up to thirty variables, even when using only five hundred data points. The controllers they learned were nearly perfect, performing within one percent of the theoretical best possible outcome.

Next, they pushed the method into much more difficult territory: nonlinear mechanical systems. These are machines where the forces acting on them do not follow simple straight lines; for example, a system with elastic couplings, nonlinear gravity, and drag that increases with the cube of the velocity. These systems are notoriously hard to control because small changes can lead to wildly different behaviors. The researchers simulated these systems with up to ten dimensions and found that their method could still find stable solutions where the standard approach failed. In one specific simulation, they controlled a system with four dimensions that was naturally unstable, meaning it would fall apart without intervention. The controller they learned successfully steered the system to a stable equilibrium, keeping it balanced, while an uncontrolled version of the same system drifted away. The key to this success was not having more data, but having smarter data usage. By matching the moments of the data—essentially the average values and the spread of the observed behaviors—they could construct a cost function that kept the mathematical problem solvable.

The beauty of this approach lies in its efficiency and its reliance on the data at hand. The researchers showed that the method works even when the number of data points is small relative to the complexity of the system. They found that by increasing the size of an auxiliary pool of sample points, they could improve the chances of finding a solution for even larger systems. This suggests that the bottleneck is not the amount of data, but how that data is interpreted. The method does not require the system to be linear or the dynamics to be known; it only requires that the data collected provides enough information to define the shape of the problem. The computational cost of setting up this method is low, involving only a set of linear equations that can be solved quickly on a standard computer.

Ultimately, this work provides a practical path forward for data-driven control in high-dimensional spaces. It moves the field away from the idea that we need massive datasets or perfect models to control complex machines. Instead, it shows that with the right mathematical framework, a relatively small amount of data can be enough to derive a controller that is both stable and effective. The researchers are careful to note that while their simulations are promising, the method is currently proven for deterministic systems with polynomial features. They see a future where this technique is extended to stochastic systems, where randomness plays a larger role, and to even more complex types of functions. For now, however, they have demonstrated that the curse of dimensionality, which has long plagued these types of calculations, can be tamed. By ensuring that the search for the best control policy stays grounded in the reality of the observed data, they have turned a theoretical concept into a tool that can be used to build better, safer, and more intelligent machines.