In standard reinforcement learning (RL) and Markov Decision Processes (MDPs), decisions are memoryless. The optimal action at any given moment depends solely on the current state of the environment. This elegant property breaks down the moment we introduce global, trajectory-level constraints.
Consider an autonomous drone with a strict battery budget or a medical robot that must not exceed a specific damage threshold over its entire mission. If the drone encounters an unexpected storm, should it fly through or take a long detour? The answer cannot be determined by its physical location alone. If it has plenty of battery left, it can afford the safe detour; if its battery is nearly depleted, it must take the risky shortcut.
Because the optimal choice depends on the history of resources consumed or costs incurred, the problem becomes non-Markovian. As Agustin Castellano et al. point out in Reinforcement Learning with Almost Sure Constraints, enforcing strict constraints across individual trajectories requires the agent to maintain a memory of accumulated costs rather than relying solely on immediate physical observations.
Restoring the Markov Property via State Augmentation
The core insight that makes these problems tractable is state augmentation. If the history of costs is what matters, we can compress that entire history into a single auxiliary variable and append it directly to the environment's state representation.
Instead of tracking the full sequence of past events, we track a single dynamic scalar or vector: the remaining budget $b_t$ (or equivalently, the accumulated cost-so-far). At each timestep, as the agent incurs a cost $c_t$, the budget updates via a simple local transition rule:
$$b_{t+1} = b_t - c_t$$
By including $b_t$ in the state space, the environment becomes Markovian once again. As Aivar Sootla et al. demonstrate in Enhancing Safe Exploration Using Safety State Augmentation, incorporating the remaining safety budget directly into the observation space transforms a non-Markovian safety problem into a Markovian one. This allows us to use standard, stationary policies $\pi(s, b)$ that condition their actions on both the physical state $s$ and the remaining budget $b$.
Ping Hou proves in Probabilistic Planning with Risk-Sensitive Criterion that this remaining budget serves as a sufficient statistic for the history of costs incurred, allowing risk-sensitive planning problems to be solved as standard reachability problems. Similarly, Dongho Kim et al. utilize this mechanism in partially observable settings in Cost-Sensitive Exploration in Bayesian Reinforcement Learning and Point-Based Value Iteration for Constrained POMDPs, augmenting the agent's belief space with an "admissible cost" to track cumulative resource consumption over a planning horizon.
Decomposing Global Constraints into Local Decisions
This mathematical reformulation shifts the burden of constraint satisfaction from a global, long-horizon optimization problem down to local, step-by-step decision criteria. When a policy is conditioned on the remaining budget, it naturally exhibits dynamic risk-aversion:
- High Budget: When $b_t$ is large, the policy can prioritize maximizing rewards or exploring unknown states, even if those actions carry a high risk of incurring costs.
- Low Budget: As $b_t$ depletes and approaches zero, the policy is forced to become highly risk-averse, shifting its objective entirely toward avoiding further costs or safety violations.
This behavior is explicitly leveraged by Nicolas Carrara et al. in Budgeted Reinforcement Learning in Continuous State Space, showing that budget-conditioned policies allow a single neural network to represent an entire frontier of safety-performance trade-offs. Instead of training separate networks for different safety thresholds, the desired budget is simply passed as an input feature, allowing the policy to dynamically adjust its behavior without retraining.
Furthermore, this decomposition allows global trajectory-level constraints to be managed as instantaneous, per-step action restrictions. Akifumi Wachi et al. illustrate in A Survey of Constraint Formulations in Safe Reinforcement Learning that trajectory-wide safety requirements can be converted into local decision-making constraints by maintaining this dynamic safety budget. In multi-agent settings, Jeremy McMahan leverages this reduction in Anytime-Constrained Equilibria in Polynomial Time to simplify complex history-dependent constraints into per-step action restrictions, enabling polynomial-time approximations for anytime-constrained equilibria.
An alternative but complementary view is proposed by Harsh Satija et al. in Constrained Markov Decision Processes via Backward Value Functions, who use backward value functions to estimate the "cost-so-far" from the start of an episode. By ensuring that the sum of the expected cost-so-far and the expected future cost does not exceed the total budget, global trajectory constraints are successfully decomposed into local, state-wise decisions without needing the full history.
A Unified Paradigm Across Domains
The beauty of budget-augmented state spaces is that the "budget" can represent almost any cumulative metric, leading to its adoption across widely diverse domains:
- Safe Exploration and Reach-Avoid: In high-stakes control, Oswin So et al. expand the state space to include both a remaining cost budget and binary flags tracking obstacle encounters in Solving Minimum-Cost Reach Avoid using Reinforcement Learning and Solving Stabilize-Avoid via Epigraph Form Optimal Control using Deep Reinforcement Learning. This allows policies to be conditioned on historical safety status, successfully solving minimum-cost reach-avoid and stabilize-avoid tasks.
- Resource-Restricted Exploration: Zhihai Wang extends the state space with a dedicated resource vector in Efficient Exploration in Resource-Restricted Reinforcement Learning to scale exploration rewards based on non-replenishable assets like battery life, preventing agents from prematurely exhausting resources during exploration.
- Risk-Sensitive Planning: Ping Hou et al. demonstrate in Revisiting Risk-Sensitive MDPs: New Algorithms and Results and Solving Risk-Sensitive POMDPs With and Without Cost Observations that augmenting the state space with a remaining cost budget shifts the optimization objective from minimizing expected costs to maximizing the explicit probability of satisfying a strict budget constraint.
- Offline RL and Counterfactuals: The paradigm even extends to abstract algorithmic budgets. In offline RL, Yao Liu et al. augment the state representation with a discrete budget tracking the permitted number of deviations from a reference behavior policy in Budgeting Counterfactual for Offline RL. This explicitly models and bounds the risk of future extrapolation errors. Similarly, Stratis Tsirtsis et al. track the cumulative number of deviations from an original sequence in Counterfactual Explanations in Sequential Decision Making Under Uncertainty to generate counterfactual explanations within a strict budget of changes.
- Industrial Infrastructure: Beyond machine learning, Raian Lefgoum et al. apply this in Multistage stochastic optimization of a mono-site hydrogen infrastructure by decomposition techniques, using a cumulative state variable to track and adjust operations against long-horizon carbon limits or subsidy thresholds.
By transforming history-dependent global constraints into a localized, budget-aware state representation, researchers across these domains exploit a unified mechanism: giving the agent a direct, real-time awareness of its remaining capacity to fail or spend, allowing it to safely navigate complex trade-offs step by step.
Key Foundational Work
Point-Based Value Iteration for Constrained POMDPs (2011) — contributed 2 concept elements to this direction.
Cost-Sensitive Exploration in Bayesian Reinforcement Learning (2012) — contributed 1 concept elements to this direction.