Many real-world systems require making decisions over extended periods of time—whether scheduling data transmissions, managing microgrids, or planning multi-robot paths. However, solving these problems globally over a long time horizon introduces the "curse of dimensionality." As the planning horizon grows, the computational complexity often scales exponentially or cubically, rendering standard optimization techniques intractable.
Temporal decomposition addresses this challenge by breaking a long-horizon problem into a sequence of smaller, localized temporal sub-problems. Instead of optimizing the entire timeline simultaneously, the problem is partitioned into discrete blocks, windows, or stages that can be solved sequentially or in parallel.
The Core Intuition: Why Can We Break Time Apart?
At first glance, temporal decomposition seems risky: decisions made today inevitably affect the state of the world tomorrow. How can we solve individual time steps independently without sacrificing global optimality?
The answer lies in two key mathematical properties: sensitivity decay and state-linked isolation.
Sensitivity Decay (The Forgetting Property)
In many dynamic systems, the impact of a local perturbation or decision decays exponentially as time moves forward. Na et al. provided a theoretical foundation for this by proving that long-horizon nonlinear dynamic programming problems possess an inherent "forgetting" property. Because distant time steps have minimal mutual influence, solvers can utilize limited look-ahead windows, significantly reducing the computational burden without losing global coherence.
State-Linked Isolation
Often, consecutive time periods are only coupled through a single, shared resource state, such as the amount of energy left in a battery or water in a reservoir. As Hannah et al. demonstrate, identifying and isolating this shared resource state allows multi-period decision problems to be decoupled into parallelized sub-problems, enabling sub-second decision speeds. Similarly, Wu et al. use a "one-shot load decomposition" to decouple physical capacity constraints from the temporal sequence, transforming high-dimensional control into independent, single-unit demand tasks.
Mechanisms of Temporal Partitioning
Depending on the problem structure, researchers employ different strategies to slice the time domain:
1. Sliding and Rolling Horizons
Instead of a rigid partition, a window slides forward across the timeline. Youngseo Kim demonstrates this in large-scale pickup and delivery problems, fixing routing assignments for a short duration while maintaining a look-ahead capability to ensure smooth transitions between intervals. In reinforcement learning, Xu et al. apply a sliding-window decomposition to help agents master high-dimensional coordination tasks, such as playing the piano, by focusing on local execution windows.
2. Block Partitioning and Shifting Boundaries
The timeline can be split into contiguous blocks or "busy periods" where a system remains active, as shown by Miao et al. in wireless network scheduling. To handle the loss of optimality at the boundaries of these blocks, Bampis et al. introduce a shifting boundary technique for the multistage knapsack problem. By solving blocks independently and averaging results over different boundary offsets, the total profit loss at transition points is kept negligible. For infinite-horizon planning, Qu et al. group time slices into blocks and optimize them cyclically using block-coordinate descent, accelerating convergence by up to two orders of magnitude.
3. Relaxing Temporal Links
When constraints explicitly bind consecutive time steps together (such as state transition costs), mathematical relaxation can be used to sever them. Hatano et al. apply Lagrangian decomposition to Dynamic SAT problems with decision change costs, relaxing the temporal links to execute sub-problems in parallel across multiple processors. Similarly, Tanaka et al. introduce auxiliary variables to decouple temporal constraints in large-scale semidefinite programs, reducing control synthesis complexity from cubic ($O(T^3)$) to linear ($O(T)$) relative to the time horizon.
Algorithmic Paradigms: Backward Recursion and Policy Gradients
Temporal decomposition fundamentally alters how optimization algorithms traverse the state space. A prominent paradigm is solving the control problem backwards in time, leveraging Bellman's principle of optimality to break a global landscape into a sequence of well-behaved, single-step sub-problems.
Global Optimization Landscape (Doubly Exponential / Non-Convex)
│
▼ [Temporal Decomposition via Backward Recursion]
┌─────────────────────────────────────────────────────────┐
│ Step T: Solve Local Sub-Problem (e.g., Contextual Bandit)│
└───────────────────────────┬─────────────────────────────┘
│ (Passes value-to-go)
▼
┌─────────────────────────────────────────────────────────┐
│ Step T-1: Solve Local Sub-Problem │
└───────────────────────────┬─────────────────────────────┘
│
▼
... Step 1
Mahajan et al. utilize a sequential decomposition method that breaks a global communication optimization problem into a series of nested Bellman equations, reducing complexity from doubly exponential to linear. In game theory, Vasal et al. use a backward recursive algorithm to decompose the problem of finding equilibria in graphon mean field games into a sequence of single-step problems, making computation independent of population size.
This backward-in-time decomposition has recently been adapted to reinforcement learning and policy gradients:
- Dynamic Policy Gradients: Klein et al. decompose a finite-horizon Markov Decision Process into a sequence of nested contextual bandit problems solved backwards. This exploits the fact that single-time-step objectives are smoother than the global objective, allowing for more efficient sample allocation.
- Receding-Horizon Policy Gradients: Basar et al. apply this recursively backward in time to solve infinite-horizon LQR control without requiring a stabilizing initial policy.
- Robust Multi-Agent Games: Koppel et al. solve mean-field type games backwards through a receding horizon, transforming a non-convex global landscape into a sequence of local, easily solvable convex-concave problems.
Decoupling Space and Time
In many large-scale applications, temporal decomposition is paired with spatial or structural decomposition to bypass the curse of dimensionality entirely.
For instance, Pacaud et al. decompose microgrid network optimization across both spatial and temporal dimensions, solving low-dimensional subproblems for individual components to scale linearly with microgrid size. In infrastructure planning, He et al. simplify carbon-efficient resource allocation by decoupling long-term spatial placement decisions from short-term operational dispatch. Once the spatial parameters are fixed, the remaining temporal constraints are solved as independent, parallel sub-problems across discrete time intervals.
Remaining Challenges
While temporal decomposition offers massive computational speedups, it is not a universal remedy. In problems where state variables are tightly coupled across the entire horizon with no decay, breaking the timeline can destroy feasibility or severely degrade solution quality.
For example, in the continent-scale inventory routing problems studied by the authors of the Renault packaging reuse study, early schedule changes create a massive ripple effect across all subsequent days due to strong inventory coupling. In such domains, developing decomposition methods that can handle long-term, non-decaying dependencies remains an active and critical area of research.
Key Foundational Work
Parallel computation of large-scale dynamic market network equilibria via time period decomposition (1991) — contributed 1 concept elements to this direction.