Non-Stationary Representations for Finite Horizon Reinforcement Learning

26 concepts15 papers1 proposal

In standard reinforcement learning (RL), we often assume an infinite horizon where an agent's optimal strategy is stationary—meaning the best action to take depends solely on the current state, regardless of when that state is visited. However, real-world tasks are bound by deadlines, time limits, and fixed durations.

In a finite-horizon setting, stationarity breaks down. If you are playing a sports match with ten minutes left on the clock, your strategy will look vastly different than if there are only ten seconds left. To act optimally, an agent must utilize a non-stationary policy: a sequence of distinct, time-indexed decision rules where the remaining time directly dictates behavior.

Why Stationary Models Fail: Value Leakage and Poor Fit

When standard infinite-horizon algorithms are applied to finite-horizon tasks, they suffer from structural mismatches that severely degrade performance.

The first issue is value leakage. In Time Limits in Reinforcement Learning, Fabio Pardo demonstrates that when an agent is unaware of an impending time limit, it cannot distinguish whether a state has low utility because it is inherently bad, or simply because there is insufficient time remaining to reach the goal from that state. Providing explicit temporal information plugs this leakage, allowing the value function to accurately track reward reachability.

The second issue is function approximation error. In a finite-horizon task, expected returns naturally fluctuate and decay as the episode nears its end. Forcing a stationary value function to map these dynamics results in severe estimation noise. As George Tucker et al. show in The Mirage of Action-Dependent Baselines in Reinforcement Learning, ignoring the remaining time leads to a fundamentally poor value function fit. By explicitly incorporating the remaining horizon into the value function parameterization, we stabilize policy updates and eliminate systematic bias.

Without this temporal awareness, agents cannot balance immediate risks with long-term objectives. For instance, Akhil Agnihotri et al. demonstrate that in constrained environments, stationary policies frequently violate safety boundaries because they fail to adapt their risk tolerance as a deadline approaches.

Structuring Time-Aware Architectures

To inject temporal context, an agent needs architectures designed to handle time-varying dynamics. A naive approach might simply append the current time step $t$ as a state feature, but the relationship between time and value is often highly non-linear and discontinuous.

Instead, more effective frameworks maintain separate policy and value representations for distinct time intervals. In DyETC: Dynamic Electronic Toll Collection for Traffic Congestion Alleviation, Haipeng Chen et al. show that treating time intervals independently allows an RL system to capture the fluctuating value of traffic states across a peak period, leading to far more precise control than a unified stationary model could provide.

Stationary Approach:     [State s] ──────────────────────────► [Single Policy π(s)]
                                                                        ▲
                                                                  Ignores urgency!

Non-Stationary Approach: [State s] ───┬─► Time t = 1 ──────────────► [Policy π_1(s)]
                                      ├─► Time t = T-1 (Urgent) ───► [Policy π_{T-1}(s)]
                                      └─► Time t = T (Deadline) ───► [Policy π_T(s)]

To prevent the parameter explosion that comes with tracking separate functions for every single timestep, Sergio Rozada and Antonio G. Marques introduce a tensor low-rank approximation method in Tensor Low-Rank Approximation of Finite-Horizon Value Functions. This approach compresses the time-dependent value functions into a low-rank structure, capturing non-stationary dynamics while drastically reducing the number of parameters required for estimation.

Leveraging Dynamic Programming Backwards in Time

While non-stationarity introduces representational overhead, it offers a massive algorithmic advantage: it allows us to exploit the sequential structure of time by training backwards.

In Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methods, Sara Klein et al. introduce "Dynamic Policy Gradient." Instead of updating all time steps simultaneously, the algorithm optimizes policies sequentially from the final deadline backward to the initial step. Because the optimal action at the final step $T$ depends only on the immediate reward, it can be solved cleanly. Once optimized, step $T-1$ can be solved by bootstrapping off the known optimal future, resulting in significantly faster convergence and tighter theoretical bounds.

This sequential optimization is highly potent in complex or restricted information spaces. In Policy Search by Dynamic Programming, J. Andrew Bagnell et al. demonstrate that generating a time-indexed sequence of distinct policies allows agents to solve challenging Partially Observable Markov Decision Processes (POMDPs). In these environments, temporal flexibility allows non-stationary policies to achieve goals that are mathematically impossible for any fixed, stationary policy to reach.

The Complexity Trade-Off

If non-stationary policies are fundamentally more capable in the real world, why does the broader RL literature remain anchored to stationary assumptions? The answer lies in a steep trade-off between performance and complexity.

As Gellért Weisz et al. point out in Confident Approximate Policy Iteration for Efficient Local Planning in $q^\pi$-realizable MDPs, storing, evaluating, and propagating errors through a unique policy for every single timestep is significantly more resource-intensive than maintaining a single stationary mapping. This scaling hurdle is echoed by Yuda Song et al., who note that while non-stationary policies are necessary to optimize sample complexity in hybrid learning frameworks, they present a major deployment barrier in memory-constrained systems.

However, ignoring this complexity creates a dangerous gap between theory and practice. In Open Problem: The Dependence of Sample Complexity Lower Bounds on Planning Horizon, Nan Jiang et al. argue that many theoretical proofs rely on environments with stationary optimal policies to artificially bypass temporal complexity. To accurately model and solve the inherent difficulty of long-horizon tasks, researchers must explicitly construct and evaluate environments that force agents to learn non-stationary, time-dependent strategies.

Key Foundational Work

Policy Search by Dynamic Programming (2003) — contributed 3 concept elements to this direction.
Reinforcement Learning with Time (1997) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_policy_stationarity_loophole_7ea3a7a9,
  title = {policy stationarity loophole},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/policy-stationarity-loophole/rdr_7ea3a7a9b5fc464eae771442c2251f61},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_policy_stationarity_loophole_7ea3a7a9_v1,
  title = {policy stationarity loophole},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/policy-stationarity-loophole/rdr_7ea3a7a9b5fc464eae771442c2251f61/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake