Abstract
The paper studies information-theoretic opacity, an information-flow privacy property, in a setting involving two agents: A planning agent who controls a stochastic system and an observer who partially observes the system states. The goal of the observer is to infer some secret, represented by a random variable, from its partial observations, while the goal of the planning agent is to make the secret maximally opaque to the observer while achieving a satisfactory total return. Modeling the stochastic system using a Markov decision process, two classes of opacity properties are considered -- Last-state opacity is to ensure that the observer is uncertain if the last state is in a specific set and initial-state opacity is to ensure that the observer is unsure of the realization of the initial state. As the measure of opacity, we employ the Shannon conditional entropy capturing the information about the secret revealed by the observable. Then, we develop primal-dual policy gradient methods for opacity-enforcement planning subject to constraints on total returns. We propose novel algorithms to compute the policy gradient of entropy for each observation, leveraging message passing within the hidden Markov models. This gradient computation enables us to have stable and fast convergence. We demonstrate our solution of opacity-enforcement control through a grid world example.
Introduction
In autonomous systems like delivery drones or warehouse robots, an agent's trajectory can inadvertently leak sensitive information to an observer. This is the problem of opacity. Traditional "qualitative" opacity is binary: a secret is either hidden or it isn't. However, real-world stochastic environments require a "quantitative" measure to determine how much uncertainty an observer actually has.
This paper introduces a framework for enforcing quantitative opacity in stochastic systems. The objective is to ensure a planning agent can hide sensitive information (such as its starting point or destination) from a partial observer. This involves a fundamental trade-off: an agent typically wants to reach a goal efficiently (maximizing reward), but efficiency often makes its path predictable, thereby destroying privacy (minimizing opacity).
Methods
The authors model the system as a Markov Decision Process (MDP) where a planning agent is monitored by an observer with noisy sensors. They focus on two types of secrets: last-state opacity (where am I now?) and initial-state opacity (where did I start?).
Optimization Framework
The problem is formulated as a constrained optimization: maximize Shannon conditional entropy (privacy) subject to a minimum total return (task performance). This is solved using a primal-dual gradient descent-ascent algorithm.
HMM Gradient Computation
A major challenge is that information-theoretic metrics like conditional entropy are non-cumulative. Unlike standard rewards in Reinforcement Learning, entropy depends on the entire sequence of observations. To calculate the gradient of conditional entropy, the authors bridge the gap between RL and Hidden Markov Models (HMMs). They utilize:
- Forward $\alpha$ messages to track state probability over time for last-state opacity.
- Backward $\beta$ messages for initial-state opacity.
Experimental Setup
The proposed algorithms are evaluated in a custom Stochastic Grid World environment.
The environment consists of a 6x6 grid with stochastic movement (10% drift). Four colored sensor zones (blue, red, yellow, green) detect the agent with 90% accuracy. Specific cells are designated as "secrets" to be hidden or "goals" to be reached.
Key Results
The primal-dual policy gradient method demonstrates stable and fast convergence across both opacity types.
- Last-State Opacity: The agent achieved a conditional entropy of 0.930 (where 1.0 is perfect uncertainty) while maintaining a reward of 0.328, staying above the 0.3 threshold.
- Initial-State Opacity: The agent reached an entropy of 0.329. This lower value is attributed to high sensor sensitivity at starting corners, making the initial state inherently harder to hide.
- Baseline Comparison: The method significantly outperformed standard entropy-regularized MDPs, which failed to reach high opacity levels and often violated reward constraints.
A key insight is that simple randomness is insufficient for privacy. To be truly opaque, an agent must specifically exploit observer sensor noise and environmental layout to maximize confusion.
Conclusion
This research provides a robust mathematical framework for balancing privacy and utility in stochastic planning. By leveraging HMM message-passing for gradient computation, the authors enable efficient opacity enforcement. Future work may address the high computational cost of forward-backward iterations for larger state spaces and explore "imprecise" observers who have a flawed understanding of the agent's strategy. Interestingly, this framework could also be used to minimize entropy, making robots more transparent and predictable for human collaborators.
Summary updated