History Dependent Policies for Risk and Safety Constraints

95 concepts71 papers2 proposals

In standard Markov Decision Processes (MDPs), we rely on a beautiful simplification: the Markov property. It states that the future depends only on the current state, not on the history of how we got there. This property guarantees that the optimal policy is memoryless—an agent only needs to look at the present moment to make the perfect choice.

But what happens when our goals extend beyond maximizing simple, additive expected rewards? When we introduce risk sensitivity, strict safety budgets, or non-linear utilities, the memoryless assumption shatters. To make optimal decisions in these complex scenarios, the agent must remember its past.

Why Risk and Safety Break the Markov Property

To understand why history matters, let's build intuition with a simple example. Suppose an autonomous delivery drone has a strict safety budget: it must not sustain more than a certain amount of wear-and-tear during a single flight. If the drone is near the end of its trip and has taken zero damage, it can safely choose a risky, high-reward shortcut. However, if it has already exhausted most of its safety budget due to early turbulence, that same shortcut becomes an unacceptable risk.

As shown by Agustin Castellano et al. in the context of "almost sure" constraints, and explored in Anytime-Constrained Reinforcement Learning, enforcing strict safety guarantees at every point in time requires tracking the cumulative history of resource consumption. A stationary policy that only looks at the drone's current physical location cannot distinguish between these two scenarios, leading to either catastrophic failure or extreme over-conservatism.

A similar breakdown occurs when we optimize for risk-sensitive objectives like Conditional Value-at-Risk (CVaR) or quantiles. In standard reinforcement learning, we maximize the expected (average) return over many trials. But in high-stakes domains like finance or medicine, we care deeply about the tail-end risk of a single execution.

Aviv Tamar et al. demonstrated that optimizing CVaR inherently requires non-Markovian decision-making. Why? Because evaluating a global risk threshold or a quantile objective depends on the total distribution of the trajectory's rewards. As Kaiwen Wang et al. and Erick Delage et al. point out, the optimal action at any given step must dynamically adjust based on the rewards already accumulated earlier in the episode. If you have already secured a high return, you can minimize variance to protect your gains; if you are far behind, you must gamble on high-variance actions to meet your target. This path-dependency violates the standard recursive optimality equations of dynamic programming.

Restoring Optimality via State Augmentation

If the optimal policy must depend on history, do we need to track an ever-growing sequence of every state, action, and reward? Doing so would cause an exponential explosion in computational complexity, making reinforcement learning completely intractable.

The key insight that makes history-dependent decision-making practical is state augmentation. Instead of remembering the entire history, we identify a compact, sufficient statistic of the past and append it directly to the environment's state space.

For example, in constrained or risk-sensitive settings, this sufficient statistic is often a dynamic "budget" or "remaining risk tolerance" variable. The authors of A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents utilize a reductions framework that augments the state space with a budget variable, effectively transforming a complex, non-Markovian risk-sensitive problem into a standard, risk-neutral MDP.

Similarly, Arnob Ghosh et al. track a running budget to handle non-linear risk measures under constraints, while Maryam Kamgarpour et al. use state augmentation to track safety histories in reach-avoid scenarios. By expanding the state space to include this running tally, the environment becomes Markovian once again with respect to the augmented state, allowing researchers to deploy standard, off-the-shelf RL algorithms to find optimal history-dependent strategies.

History in Exploration and Strategic Environments

The necessity of history-dependence extends beyond risk and safety into exploration and game-theoretic settings.

Consider the problem of exploring an environment to maximize state entropy within a single trial. Mirco Mutti et al. proved that while optimal Markovian exploration policies must be highly stochastic to handle uncertainty, there always exists a deterministic non-Markovian policy that achieves the same or better exploration efficiency. By remembering where it has already been during a single execution, an agent can make purposeful, non-random decisions to strike out into unvisited territory.

In strategic interactions, history acts as a mechanism for credibility and coordination. Hanrui Zhang 0001 et al. show that in dynamic mechanism design, an optimal principal must condition actions on the entire history of an agent's reports to prevent strategic manipulation over time.

In a similar vein, Martino Bernasconi et al. demonstrate that in Bayesian persuasion within MDPs, memoryless policies are strictly suboptimal because they cannot track the history of interactions required to build trust. By using history-dependent "promise-form" policies, a sender can make honest promises about future rewards based on past interactions, rendering the complex strategic problem computationally tractable.

Key Foundational Work

The Robustness-Performance Tradeoff in Markov Decision Processes (2006) — contributed 2 concept elements to this direction.
Model checking discounted temporal properties (2005) — 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_history_dependent_decision_making_e85bfbd3,
  title = {history-dependent decision making},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/history-dependent-decision-making/rdr_e85bfbd3643f496ebabb5aff5b4269bc},
  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_history_dependent_decision_making_e85bfbd3_v1,
  title = {history-dependent decision making},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/history-dependent-decision-making/rdr_e85bfbd3643f496ebabb5aff5b4269bc/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