Source-linked AI summary
Thinking Fast and Slow: Optimization Decomposition Across Timescales
Gautam Goel, Niangjun Chen, Adam Wierman
TL;DR
The paper addresses how to jointly design fast local and slow global controllers when multi-timescale separation is usually assumed rather than derived. It adapts optimization decomposition to temporal control, introducing MRPC with a predictive slow controller and reactive fast controller. MRPC maintains per-stage cost within a constant factor of the offline optimum even with adversarial inputs.
Problem
Multi-timescale controllers are typically designed independently, leaving joint performance without guarantees and potentially causing inefficiency.
Method
The paper develops temporal optimization decomposition and introduces MRPC, combining a predictive slow controller with a purely reactive fast controller.
Results
MRPC maintains average per-stage cost within a constant factor of the offline optimum, including under adversarial inputs.
Takeaways & Limitations
A multi-timescale controller can separate planning onto a slow controller and residual correction onto a simple fast controller while retaining a strong optimality guarantee.
Takeaways & Limitations
The model does not consider information-sharing delays and leaves joint spatial and temporal decentralization for future work.
Abstract
from arXiv · showhide
Many real-world control systems, such as the smart grid and human sensorimotor control systems, have decentralized components that react quickly using local information and centralized components that react slowly using a more global view. This paper seeks to provide a theoretical framework for how to design controllers that are decomposed across timescales in this way. The framework is analogous to how the network utility maximization framework uses optimization decomposition to distribute a global control problem across independent controllers, each of which solves a local problem; except our goal is to decompose a global problem temporally, extracting a timescale separation. Our results highlight that decomposition of a multi-timescale controller into a fast timescale, reactive controller and a slow timescale, predictive controller can be near-optimal in a strong sense. In particular, we exhibit such a design, named Multi-timescale Reflexive Predictive Control (MRPC), which maintains a per-timestep cost within a constant factor of the offline optimal in an adversarial setting.
I. INTRODUCTION
Multi-timescale systems commonly combine fast local controllers with slower global controllers, but these timescales are usually designed independently rather than jointly. The paper develops an optimization-decomposition framework for deriving their separation despite dynamic coupling.
- Power grids and software-defined networks use slow planning or dispatch alongside fast regulation or routing controllers.
- Existing designs typically optimize controllers at each timescale independently, without addressing their joint operation.
- Assuming timescale separation rather than deriving it can create inefficiencies even when each timescale problem is solved optimally.
- The paper adapts optimization decomposition from distributed control to decompose a global optimization problem across time.
- Dynamic coupling complicates temporal decomposition because actions at either timescale alter future states and the other controller’s design.
A. Contributions of this paper
The paper introduces a general adversarial-noise model, establishes the necessity of predictions for near-optimality, and proposes MRPC as a strongly competitive multi-timescale policy. MRPC shifts optimization to a predictive slow controller while retaining a simple reactive fast controller.
- The model uses linear dynamics with unrestricted noise, controlled by an immediately reactive fast controller and a slower controller with more information.
- Near-optimal multi-timescale control cannot generally be achieved without predictions of future disturbances.
- MRPC achieves per-step cost within a constant factor of the offline optimum, using a predictive slow controller and a reflexive fast controller.
B. Related literature
The work extends optimization decomposition and temporal control literature by providing guarantees for timescale decomposition in dynamic systems. It differs from related architectural and power-system approaches through its general linear-dynamics setting and provable performance guarantees.
- Optimal-control methods commonly rely on analytical principles or numerical methods because general problems are nonlinear and lack closed-form solutions.
- A prior two-layer trajectory-planning and tracking architecture does not provide optimality guarantees for its decomposition.
- Prior power-system temporal decomposition gives an optimality condition but assumes a problem without dynamics.
- This paper studies timescale decomposition for general optimal control with linear dynamics and provides provable performance guarantees.
II. MODEL
The model combines fast and slow controls in linear dynamical systems, where the slow action changes only every k timesteps and may use predictions and global information. Performance is evaluated competitively against the offline optimum without distributional noise assumptions.
- Base control problem: The base model has state x_t, control f_t, disturbance w_t, linear dynamics, and convex nonnegative state and control costs.
- Scope and assumptions: The model assumes an invertible fast-control matrix and focuses on two timescales for clarity.
- Two-timescale model: A slow control action s_t is added to the dynamics and can change only every k timesteps.
- Two-timescale model: Fast control operates at every timestep, while slow control acts at timesteps {1, k + 1, 2k + 1, ...}.
- Controller roles: The slow controller can exploit centralized information and noisy predictions of future disturbances, while fast controllers remain simple and reactive.
- Performance criterion: Performance is measured by worst-case competitive ratio against the offline optimum, without distributional assumptions on disturbances or prediction errors.
III. HARDNESS OF MULTI-TIMESCALE CONTROL
Without predictions, constant-competitive control is impossible in general, but limited noisy predictions make near-optimal performance achievable through a reduction to smoothed online convex optimization. AFHC attains a competitive ratio of 1 + O(1/w), with performance also shaped by system dynamics.
- Constant-competitive control is impossible in general for the fast control subproblem without noisy predictions about future costs.
- Under norm-cost and equal-gain assumptions, the multi-timescale problem is equivalent to a fast-timescale problem and can be reformulated as SOCO.
- SOCO penalizes both online state costs and changes between successive actions under the system dynamics.
- AFHC averages w + 1 Fixed Horizon Control algorithms, each optimizing over consecutive windows of length w + 1.
- 1 + O(1/w) is the AFHC competitive ratio when costs are strongly convex and bounded below by a positive constant.
- Even with small prediction windows, AFHC can be near-optimal when ∥(Bf)^−1A∥ is sufficiently small, reflecting the fast controller’s ability to counteract system dynamics.
IV. ARCHITECTURAL DECOMPOSITION FOR MULTI-TIMESCALE CONTROL
The paper studies co-design for systems with multiple timescales, where slow controllers may offer greater information or lower operating cost. It introduces MRPC as a near-optimal architecture combining reflexive fast control with predictive slow control.
- Slow controllers can provide more information and computational power or be cheaper to operate than fast controllers.
- MRPC combines a simple reflexive fast-timescale controller with a predictive slow-timescale controller and has a derived performance bound.
A. An overview of MRPC
MRPC assigns prediction and optimization to the slow controller while the fast controller reacts locally to revealed disturbances. This creates a clean division consistent with centralized slow control and decentralized fast control.
- The slow controller chooses actions using predictions under the assumption that the fast controller will keep the state at zero.
- The fast controller myopically corrects each revealed noise increment to keep the state at zero.
- MRPC denotes its fast and slow actions by ˆf and ˆs, respectively.
- The fast controller uses no predictions or optimization, shifting prediction and optimization onto the slow controller.
B. Performance of MRPC
Theorem 2 shows that MRPC achieves a constant-factor average per-stage cost relative to the offline optimum, including under adversarial inputs. Prediction errors contribute additively, and under stated conditions MRPC matches the offline optimum.
- Performance guarantee: A constant-factor average per-stage cost relative to optimal holds for MRPC when the cost functions are norms.The bound applies even though the problem may have adversarial inputs.
- Controller structure: MRPC’s fast-timescale controller is purely reflexive and uses no predictions, despite the strength of the performance bound.The slow controller uses predictions, while the fast controller continually reacts to residual deviations.
- Prediction error: Prediction error has only an additive effect on the bound, and the result allows adversarial or stochastic prediction errors.With perfect lookahead, the prediction-error term disappears.
- Scope of comparison: Theorem 2 is incomparable to Theorem 1 because the two theorems compare against different offline optima.Theorem 2 uses the multi-timescale offline optimum, whereas Theorem 1 uses the single-stage offline optimum.
C. Proof of Theorem 2
The proof establishes Theorem 2 by lower-bounding the offline optimum and matching that structure with MRPC’s separated slow and fast actions. The resulting decomposition treats the slow action as the optimization variable and the fast action as residual correction.
- Model and timescales: The model evolves according to xt = Axt−1 + Bfft + Bsst + wt, with slow actions changeable only at steps in S.S = {1, k + 1, 2k + 1, . . .} identifies the slow-timescale decision points.
- Lower bound construction: The analysis begins by lower-bounding the offline optimal cost, using norm inequalities and the model’s dynamics.The proof introduces a technical lemma about norms and invertible matrices before deriving the lower bound.
- Decomposition: After fixing each slow action sr, the remaining optimization over fast actions resembles the single-timescale problem and leads directly to the theorem.This structural resemblance connects the lower-bound optimization to the performance result.
- Decomposition: The lower bound interprets the fast action as (Bf)−1(Bssr + wt), continually correcting residual noise while keeping the state at zero.The slow controller chooses the higher-level action, while the fast controller corrects the remaining deviation.
- Conclusion of proof: Combining the lower- and upper-bound lemmas yields Theorem 2.The proof obtains the upper bound by substituting MRPC’s control actions and handling prediction estimates with triangle inequalities.
V. CONCLUDING REMARKS
The paper develops a general multi-timescale control model, proves that predictions are necessary for constant competitiveness, and proposes MRPC with a predictive slow controller and reactive fast controller. Open directions include delays and systems decomposed across both time and space.
- Contributions: The framework models multi-timescale control generally and uses a blackbox reduction to online convex optimization for a hardness result.The analysis shows that predictions are necessary for constructing a constant competitive algorithm.
- MRPC: MRPC separates a predictive slow controller from a simple reactive fast controller using only a small number of noisy predictions.This architecture mirrors systems with centralized slow control and decentralized fast responses.
- Open problems: The model does not consider delay, although real-world systems may impose information-sharing constraints arising from delay.Adding such constraints to the slow controller is identified as a natural open problem.
- Open problems: A hybrid model combining decentralization across space with multiple timescales remains an open direction.Many systems, including the smart grid, feature both centralized and localized controllers.