Abstract
Autonomous systems are often deployed in the open world where it is hard to obtain complete specifications of objectives and constraints. Operating based on an incomplete model can produce negative side effects (NSEs), which affect the safety and reliability of the system. We focus on mitigating NSEs in environments modeled as Markov decision processes (MDPs). First, we learn a model of NSEs using observed data that contains state-action trajectories and severity of associated NSEs. Unlike previous works that associate NSEs with state-action pairs, our framework associates NSEs with entire trajectories, which is more general and captures non-Markovian dependence on states and actions. Second, we learn finite state controllers (FSCs) that predict NSE severity for a given trajectory and generalize well to unseen data. Finally, we develop a constrained MDP model that uses information from the underlying MDP and the learned FSC for planning while avoiding NSEs. Our empirical evaluation demonstrates the effectiveness of our approach in learning and mitigating Markovian and non-Markovian NSEs.
Introduction
When AI systems are deployed in the real world, they often operate on incomplete models, leading to unintended and undesirable consequences known as Negative Side Effects (NSEs). For example, a robot might reach its goal efficiently but damage the environment in the process. While prior work has largely focused on Markovian NSEs—those tied to a single state-action pair—real-world NSEs are frequently non-Markovian, meaning they depend on a sequence of actions or an entire trajectory.
To avoid these trajectory-based NSEs, an agent typically needs to maintain a history of its past actions. However, expanding the state representation to track this history often causes a combinatorial explosion, making planning computationally intractable. This paper introduces a framework to predict and avoid these complex, history-dependent NSEs without significantly increasing the state space complexity.
The CASP Framework
The authors propose Controller-Assisted Safe Planning (CASP), a three-step framework designed to handle non-Markovian constraints efficiently:
- Data Collection: The agent gathers state-action trajectories and their associated NSE severity (e.g., mild, severe, or none) via human or oracle feedback.
- Learning the FSC: Instead of using a black-box model, the framework uses a Finite State Controller (FSC) to compactly summarize trajectory history. The FSC parameters are learned using the Expectation-Maximization (EM) algorithm, providing a transparent, graph-based representation of what triggers an NSE.
- Safe Planning via CMDP: The learned FSC is integrated with the original Markov Decision Process (MDP) to create a "cross-product MDP." This is formulated as a Constrained MDP (CMDP) and solved using a modified Dual Linear Program (LP).
Unlike baseline methods that distribute "slack" (allowable performance loss) locally at every state, CASP treats slack globally. This allows the agent to spend its entire safety budget on a single crucial detour rather than being forced into unsafe actions by local constraints.
Experimental Results
The framework was evaluated on simulated grid-world domains involving Boxpushing and Navigation. In the Navigation domain, an autonomous vehicle must reach a destination while avoiding splashing pedestrians—a non-Markovian NSE if it occurs repeatedly over a route.
Key results include:
- High Accuracy: The EM algorithm successfully learned accurate FSCs (~90% accuracy) using very small controllers (7 to 8 nodes) and limited training data.
- NSE Mitigation: As shown in the performance comparison, CASP successfully reduced both Markovian and non-Markovian NSEs to zero, provided sufficient slack was allowed.
- Baseline Comparison: The baseline Lagrangian MDP (LMDP) approach failed to mitigate non-Markovian NSEs, yielding nearly a 100% severe NSE rate in complex navigation scenarios.
Conclusion
CASP provides a robust method for giving agents "memory" of their actions via FSCs, allowing them to avoid complex harms without the computational burden of state-space expansion. The use of FSCs also offers better explainability than deep learning models. Future work will extend this framework to partially observable environments and continuous state spaces.
Summary updated