Distributionally Robust Regret Optimal Control Under Moment-Based Ambiguity Sets

1. Problem Formulation

The paper addresses the design of control policies for finite-horizon, linear-quadratic stochastic systems subject to additive disturbances with unknown probability distributions.

• System Dynamics: The system evolves as $x_{t+1} = A_t x_t + B_t u_t + w_t$, where $w_t$ represents the disturbance. The initial state and disturbances are potentially dependent random variables with an unknown joint distribution $P$.
• Control Objective: The goal is to design causal affine control policies (specifically, disturbance feedback controllers of the form $u = Kw + v$) that minimize the worst-case expected regret.
• Regret Definition: Regret is defined as the difference between the cost incurred by the causal controller and the minimum cost achievable by an optimal noncausal (clairvoyant) controller that knows the entire disturbance trajectory in advance.
  $$\mathcal{R}(u, w) = J(u, w) - J(u^o(w), w)$$
• Ambiguity Set: Instead of assuming a specific distribution, the true distribution is assumed to belong to an ambiguity set $\mathcal{P}$. This set contains all distributions whose mean ($\mu$) and covariance ($\Sigma$) lie within specific norm-bounded balls centered at nominal estimates $(\hat{\mu}, \hat{\Sigma})$:
  • Mean uncertainty: $\|\mu - \hat{\mu}\|_2^2 \leq r_1$ (Euclidean norm ball).
  • Covariance uncertainty: $\|\Sigma - \hat{\Sigma}\|_p \leq r_2$ (Schatten $p$-norm ball).
  • The Schatten $p$-norm generalizes the nuclear norm ($p=1$), Frobenius norm ($p=2$), and spectral norm ($p=\infty$).

2. Methodology

The authors develop a framework to transform the inherently difficult minimax problem into a tractable convex optimization problem and propose a scalable algorithm to solve it.

A. Convex Reformulation

The core theoretical contribution is showing that the distributionally robust regret optimal control problem can be reformulated as a finite-dimensional convex program.

• Decomposition: The worst-case expected regret is decomposed into two separate maximization problems: one over the disturbance mean and one over the covariance.
• Lemma 1: The authors utilize a minimax lemma to handle the non-convexity arising from maximizing a quadratic function over a Euclidean ball. This allows the mean uncertainty term to be expressed as a spectral norm penalty.
• Theorem 2 (Main Result): The optimal control policy is shown to be of the form $\phi^*(w) = K^*(w - \hat{\mu}) + K_o \hat{\mu}$, where $K_o$ is the optimal noncausal gain. The feedback gain $K^*$ is the solution to:
  $$\min_{K \in \mathcal{L}} \left\{ \text{Tr}(\hat{\Sigma} C(K)) + r_1 \|C(K)\|_\infty + r_2 \|C(K)\|_q \right\}$$
  where $C(K) = (K - K_o)^\top D (K - K_o)$, $D$ is a positive definite matrix derived from system dynamics, and $\|\cdot\|_q$ is the dual norm of the Schatten $p$-norm ($1/p + 1/q = 1$).

B. Interpretation as Regularized Control

The reformulated problem is interpreted as a regularized linear-quadratic stochastic control problem:

1. Nominal Term: $\text{Tr}(\hat{\Sigma} C(K))$ represents the expected regret under the nominal distribution.
2. Mean Regularization: $r_1 \|C(K)\|_\infty$ penalizes sensitivity to mean uncertainty (spectral norm penalty).
3. Covariance Regularization: $r_2 \|C(K)\|_q$ penalizes sensitivity to covariance uncertainty.
   • If $p=1$ (nuclear norm), $q=\infty$, combining with the mean term to form a single spectral norm penalty.
   • If $p=\infty$ (spectral norm), $q=1$, the term becomes a trace penalty ($r_2 \text{Tr}(C(K))$), which corresponds to the classical Linear Quadratic Regulator (LQR) under isotropic noise.

C. Scalable Algorithm: Dual Projected Supergradient

While the problem can be cast as a Semidefinite Program (SDP), solving large-scale SDPs is computationally expensive. The authors propose a Dual Projected Supergradient Method:

• Dual Formulation: They derive the dual of the convex program, which involves maximizing a concave dual function $g(\Lambda)$ over a product of norm balls.
• Algorithm: An iterative algorithm (Algorithm 1) is developed:
  1. Compute the supergradient $G(K_i)$ by solving a convex quadratic subproblem.
  2. Update the dual variables $\Lambda_{i+1}$ via a projected supergradient step: $\Lambda_{i+1} = \Pi_{\mathcal{C}}(\Lambda_i + \eta_i G(K_i))$.
  3. The projection onto the Schatten norm ball is efficiently computed using eigendecomposition and vector projection onto $\ell_p$-norm balls.
• Convergence: The method is proven to converge to the optimal solution. If the nominal covariance is positive definite, the dual function becomes differentiable, reducing the method to a Projected Gradient Ascent method, allowing for faster convergence techniques (e.g., momentum, line search).

3. Key Contributions

1. Novel Ambiguity Set: Introduction of ambiguity sets based on Schatten $p$-norms for covariance uncertainty, allowing for flexible modeling of distributional shifts beyond standard Wasserstein distances.
2. Tractable Reformulation: Proof that the minimax regret problem admits an equivalent convex reformulation with explicit regularization terms, bridging the gap between robust control and regularized stochastic control.
3. Scalable Solver: Development of a Dual Projected Supergradient algorithm that avoids the memory bottlenecks of interior-point SDP solvers, making the approach applicable to large-scale systems.
4. Generalization: The framework generalizes existing robust regret optimal control methods (which assume norm-bounded disturbances) and classical LQR as special cases.

4. Numerical Results

The authors conducted experiments on a damped double integrator system with an AR(1) disturbance process.

• Baselines: Compared against Wasserstein-based distributionally robust methods (WASS-REGRET, WASS-COST), Sample Average Approximation (SAA), and the optimal causal controller with true parameters (OPT-CAUSAL).
• Performance vs. Radius:
  • As the ambiguity radius increases, robust controllers outperform SAA (which is sensitive to estimation errors) but eventually become overly conservative.
  • The proposed SPEC-REGRET controller (using spectral norm for covariance) consistently achieved the lowest out-of-sample expected cost, often matching the performance of the OPT-CAUSAL controller.
• Correlation Sensitivity: The proposed methods maintained low regret across varying temporal correlation coefficients ($\rho$), whereas Wasserstein-based cost-minimizing controllers (WASS-COST) became overly conservative in high-correlation regimes.
• Scalability: The projected supergradient method solved problems with horizon $T=80$ in under 8 seconds, whereas the SDP interior-point solver took over 16 minutes and failed to solve problems with $T > 80$ due to memory constraints.

5. Significance

This paper provides a significant advancement in data-driven control design by offering a method that is both computationally scalable and statistically robust.

• Practicality: By replacing expensive SDP solvers with a first-order method, the approach enables the application of distributionally robust control to larger, real-world systems.
• Flexibility: The use of Schatten norms allows practitioners to tune the controller's sensitivity to different types of distributional shifts (e.g., rank-deficient covariance changes vs. full-rank spectral changes).
• Regret vs. Cost: The focus on regret minimization rather than worst-case cost minimization yields controllers that are less conservative, providing a better balance between performance under nominal conditions and robustness against distributional shifts.

In summary, the paper establishes a rigorous theoretical foundation for moment-based distributionally robust regret control and delivers a practical algorithm that outperforms state-of-the-art methods in both accuracy and computational efficiency.