Information-Theoretic Opacity-Enforcement in Markov Decision Processes

Chongyang Shi, Yuheng Bu, Jie Fu

Introduction

In the deployment of autonomous systems, such as delivery robots or critical infrastructure controllers, agents often operate under the gaze of external observers. While these agents must fulfill specific tasks, they must also protect sensitive information—or "secrets"—from being inferred by potentially malicious observers. This property is known as opacity. This paper introduces a framework for enforcing quantitative opacity in stochastic systems modeled as Markov Decision Processes (MDPs), moving beyond traditional qualitative (all-or-nothing) definitions of privacy.

The Challenge of Quantitative Opacity

Traditional research has largely focused on qualitative opacity: can an observer determine a secret with absolute certainty? However, in real-world stochastic environments, information leakage is rarely binary. A more robust approach requires a quantitative measure. The authors propose using Shannon conditional entropy $H(Z|Y)$ to measure the observer's uncertainty about a secret $Z$ after receiving a sequence of observations $Y$.

Optimizing for entropy in an MDP context is non-trivial. Unlike standard rewards in reinforcement learning, information-theoretic measures are non-cumulative. One cannot simply sum up "privacy points" at each time step. This non-additivity makes traditional Bellman-based optimization techniques inapplicable.

Methodology

The interaction is modeled as a game between a planning agent (P1) and an observer (P2). P1 aims to maximize the conditional entropy of the secret while ensuring the expected total reward meets a minimum performance threshold $\delta$.

To solve this constrained optimization problem, the authors employ a primal-dual policy gradient method. The core technical innovation lies in the gradient computation. By treating the MDP under a fixed policy as a Hidden Markov Model (HMM), the authors utilize forward-backward (alpha-beta) messages to compute the exact gradient of the non-cumulative entropy metric. This allows for stable and efficient policy optimization using a Lagrangian formulation.

Experimental Setup

The framework was evaluated using a stochastic Grid World environment. As shown in the figure below, the environment consists of a $6 \times 6$ grid where a robot must navigate toward goal states (flags) while keeping its visit to secret states (question marks) opaque. The environment is equipped with noisy colored sensors that provide the observer with imperfect data, including a 10% false-negative rate.

The stochastic Grid World environment used for evaluation, featuring secret states (question marks), goal states (flags), and noisy colored sensors.

Key Results and Insights

The proposed method demonstrates a superior ability to balance task performance with privacy compared to standard baselines, such as entropy-regularized MDPs. While standard regularization encourages general policy randomness, it does not account for what an observer actually perceives. In contrast, this method specifically exploits observation noise to obfuscate the agent's path.

Performance Metrics

  • Last-State Opacity: The algorithm achieved a conditional entropy of 0.930 (near-perfect uncertainty) while maintaining a task return of 0.328, satisfying the performance constraint.
  • Initial-State Opacity: The method reached an entropy of 0.329. While lower than the last-state results, this represents the maximum achievable privacy given the high sensitivity of sensors near the starting positions.
Comparison of the proposed method (dashed lines) against baselines (solid lines) for last-state opacity, initial-state opacity, and policy value across varying parameters.

As illustrated in the baseline comparisons, the proposed method consistently maintains higher levels of opacity (entropy) while adhering to the value constraints, whereas baseline methods fail to provide adequate privacy as task demands increase.

Conclusion and Future Work

This work provides a rigorous foundation for quantitative privacy in automated planning. By bridging control theory and signal processing through HMM-based gradients, the authors enable agents to be intentionally "secretive." Future research will focus on reducing the computational complexity of the forward-backward iterations and exploring scenarios where the observer's knowledge of the agent's policy is imperfect. Additionally, the framework could be inverted to maximize transparency, helping robots become more predictable and understandable to human collaborators.

Summary updated

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.
BibTeX
@inproceedings{shi2024information,
  author = {Chongyang Shi and Yuheng Bu and Jie Fu},
  title = {{Information-Theoretic Opacity-Enforcement in Markov Decision Processes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure