PaperlayerView exact revision on arXiv

Source-linked AI summary

Embedding Information in Policy Randomness: Distribution-Preserving Implicit Communication in MDPs

Gongpu Chen, Deniz Gündüz

arXiv:2610.15976v1cs.ITcs.AImath.IT

TL;DR

The paper asks how an agent can communicate through a stochastic policy without changing its prescribed action distribution. It introduces PRAM, which uses common randomness to select message-dependent action realizations while preserving that distribution; the paper proves asymptotic reliability and reports applications including watermarking and trajectory provenance.

  • Problem

    The paper asks how an agent can embed a message in its actions while following a prescribed stochastic policy and preserving its action distribution.

    Source: §1 · p. 1, §3.1 · p. 4

  • Method

    PRAM uses common randomness to select message-dependent action realizations and enable decoding from the observed state trajectory while preserving the prescribed action distribution.

    Source: §1 · p. 2, §3.2 · p. 5

  • Results

    PRAM preserves the prescribed action distribution for every state and message, and its message-recovery error becomes arbitrarily small as trajectory length increases.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The framework is demonstrated for multi-bit policy watermarking and trajectory provenance, including under model mismatch.

    Source: §1 · p. 2, §6 · p. 10

    The asymptotic reliability guarantee is established under Assumptions 1 and 2.

    Source: §4.2 · p. 7

Abstract

from arXiv · show

This paper investigates a new role of randomness in stochastic policies--as a medium for embedding and communicating information. Specifically, we consider an agent interacting with an environment according to a prescribed stochastic policy. By carefully modulating the random action realizations of the policy, information can be embedded into the agent's behavior without altering the prescribed action distribution. We cast this problem as a channel coding problem, in which the controlled system implicitly serves as a communication channel. We then propose a coding scheme, termed posterior-matching randomness modulation (PRAM), that selects actions according to the message to be transmitted. With the aid of common randomness independent of the control system, PRAM preserves the prescribed action distribution for every state and every message. We further prove that PRAM is asymptotically reliable: the message can be decoded with arbitrarily small error probability as the observed state trajectory becomes sufficiently long. Experiments demonstrate the effectiveness of the proposed framework in applications including multi-bit policy watermarking and trajectory provenance.

1 INTRODUCTION

The paper proposes using stochastic-policy randomness to embed messages in behavior while preserving the prescribed action distribution. Its PRAM scheme uses common randomness to enable per-message distribution preservation and asymptotically reliable recovery, with applications including multi-bit watermarking and trajectory provenance.

1 INTRODUCTION

  • DPIC embeds richer, multi-bit information for policy identification and attribution, beyond existing methods that mainly detect whether a watermark is present.The same mechanism is also proposed for trajectory provenance and behavioral metadata embedding.Source: §1 · pp. 1–2
  • The paper formulates message embedding as communication through an MDP, with actions as channel inputs and resulting states as outputs.Embedding a B-bit message is treated as transmitting it through this state-dependent channel.Source: §1 · p. 2
  • Because fixed-message applications need more than message-averaged preservation, DPIC requires the prescribed action distribution for every state and message.Common randomness enables message-dependent action selection while keeping the marginal action distribution unchanged.Source: §1 · p. 2
  • PRAM preserves the prescribed action distribution for every state and message while enabling asymptotically reliable recovery as the observed trajectory grows.The paper also reports effectiveness under model mismatch and in multi-bit policy watermarking and trajectory provenance.Source: §1 · p. 2

2 RELATED WORK

Prior policy-watermarking work mainly supports zero-bit detection, while multi-bit watermarking and decoding from state trajectories remain distinct challenges. DPIC differs from related communication schemes through its per-message action-distribution constraint and uses shared randomness in a posterior-matching approach.

2 RELATED WORK

  • Existing policy-watermarking methods mainly verify watermark presence; TRACE supports multi-bit embedding but assumes the detector observes executed actions.DPIC instead considers decoding from the resulting state trajectory.Source: §2 · p. 2
  • Multi-bit watermarking for generative models controls token sampling but assumes generated tokens are directly observable, unlike the state-trajectory decoding setting considered here.The passage says this difference prevents those methods from applying to general policy-watermarking problems.Source: §2 · p. 3
  • Related implicit-communication methods, including Act2Comm, constrain input distributions after averaging over messages, whereas DPIC requires preservation for every state and message.The distinction matters when the same identifier is embedded repeatedly.Source: §2 · p. 3
  • PRAM draws on posterior matching, using shared randomness to enable message-dependent actions while preserving the prescribed action distribution for each message.Posterior matching uses the encoder’s shared view of the decoder’s posterior to adapt what information is conveyed next.Source: §2 · p. 3

3 PROBLEM STATEMENT

The problem assumes an agent already follows a suitable stochastic reference policy and asks whether it can communicate a message through its actions without changing that policy’s action distribution. The formulation treats the MDP as a communication channel and introduces shared randomness to reconcile message transmission with per-message distribution preservation.

3.1 SYSTEM MODEL

  • The system is a finite MDP in which the agent observes each state, chooses an action, and induces the next state; a passive observer sees the state.The model is specified by state and action spaces, a transition kernel, and a reward function.Source: §3.1 · p. 3
  • The agent is assumed to have a suitable stationary reference policy, and the central question is whether its message can be decoded from the resulting state sequence while it follows that policy.The objective is not to optimize the policy’s cumulative or average reward.Source: §3.1 · p. 4
  • For a finite message set, the encoder chooses actions using the message and available histories, while the observer decodes from the state sequence; actions must retain the reference-policy distribution for each message.The setup considers a fixed horizon and decoding error probability.Source: §3.1 · p. 4

3.2 PROBLEM FORMULATION

  • The MDP is modeled as a finite-state channel: actions are inputs, states are channel states and outputs, and the reference policy specifies the desired input distribution.The encoder maps messages and histories to actions; the decoder estimates the message from observed states.Source: §3.2 · p. 4
  • Per-message preservation makes the action conditionally independent of the message given the state, so the action alone conveys no additional message information under that conditioning.The formulation notes that conventional message-averaged input constraints are weaker than this requirement.Source: §3.2 · p. 4
  • Shared randomness, independent of the message and histories, allows actions to depend on the message once that randomness is known while retaining the prescribed marginal distribution.The same construction lets the encoder and observer share random variables and supports decoding from states and shared randomness.Source: §3.2 · pp. 4–5

4 DISTRIBUTION-PRESERVING IMPLICIT COMMUNICATION

The section presents a coding scheme that preserves the reference policy’s conditional action distribution for every message while enabling communication through the MDP. It introduces PRAM and establishes asymptotic reliability under stated assumptions.

4.1 CODING SCHEME

  • PRAM adapts posterior matching with common randomness: it constructs information points within posterior intervals, then selects actions to match the reference policy.The interval-position parameter sets information-point spacing; the independent uniform random variable supplies a cyclic shift.Source: §4.1 · pp. 5–6
  • After each action, the MDP transitions to an observed state; the observer updates the message posterior and decodes from it at the transmission horizon.The described decoder uses a maximum a posteriori estimate.Source: §4.1 · p. 6
  • PRAM preserves the reference policy’s action distribution for every message, so communication does not degrade expected control reward.The preservation follows when averaging over the common random variable.Source: §4.1 · p. 6

4.2 RELIABILITY ANALYSIS

  • The reliability guarantee assumes an irreducible reference-policy Markov chain and a recurrent state where stochastic actions induce distinguishable transition distributions.At that state, the reference policy must be nondegenerate and distinct supported actions must have distinct transition distributions in the stated KL-divergence sense.Source: §4.2 · p. 7
  • Under Assumptions 1 and 2, the observer’s decoding error probability vanishes as the blocklength grows.The transmitted message’s posterior converges to one almost surely.Source: §4.2 · p. 7
  • Common randomness couples message-dependent action selection to shared randomization, enabling reliable communication despite per-message distribution preservation.Conditioned on the current state, the action alone reveals no additional information about the message.Source: §4.2 · p. 7

5 EXPERIMENTS

Experiments test PRAM’s per-message distribution preservation, communication performance in two applications, sensitivity to randomness, and robustness to model mismatch. Across these settings, decoding improves with longer trajectories, while empirical action distributions remain close to the reference policy.

Experimental setup

  • The experiments evaluate PRAM in ReFrozenLake (64 states, 4 actions), ConTaxi (500 states, 6 actions), and Stochastic Battery Management (1,000 states, 5 actions).The application tests use ReFrozenLake and SBM for watermarking and ConTaxi for trajectory provenance.Source: §5 · pp. 7–8

Distribution preservation

  • TV distance stays close to zero across all eight tested messages and environments, empirically confirming PRAM’s per-message action-distribution preservation.The experiment uses B = 3 bits and blocklength n = 20.Source: §5 · p. 7, Table 1 · p. 8

Applications

  • Decoding accuracy rises with blocklength and approaches one for all tested message lengths at trajectory lengths of about 40–50.The evaluation covers multi-bit watermarking in ReFrozenLake and SBM and trajectory provenance in ConTaxi.Source: §5 · p. 8, Figure 3 · p. 8

Effect of randomness

  • Greater policy randomness generally leads to higher decoding accuracy, while lower transition uncertainty generally improves recovery from the state trajectory.Policy randomness is varied through temperature in ReFrozenLake and SBM; system randomness is varied through rainy probability in ConTaxi.Source: §5 · pp. 8–9, Figure 4 · p. 9

Model mismatch

  • Across tested mismatch levels, decoding accuracy improves with blocklength and approaches one, including under moderate model mismatch.The mismatch is between the true transition kernel and the estimated kernel used for PRAM; Figure 5 measures it with TV distance.Source: §5 · p. 9, Figure 5 · p. 9

6 CONCLUSION

The conclusion frames DPIC as communication through an MDP, with actions as channel inputs and resulting states as outputs. PRAM uses common randomness to preserve action distributions while supporting reliable recovery; extending the framework to partially observable settings is future work.

6 CONCLUSION

  • DPIC treats the MDP as a communication channel, with actions as inputs and resulting states as outputs, and imposes per-message distribution preservation.The conclusion contrasts this requirement with conventional channel coding.Source: §6 · p. 9
  • PRAM uses shared common randomness to couple messages with action realizations, preserving prescribed action distributions while enabling recovery from state trajectories.The paper reports a proof of per-message preservation and asymptotic reliability, alongside experiments in watermarking and trajectory provenance.Source: §6 · p. 10
  • Extending DPIC to partially observable settings with incomplete or noisy state information remains an important and challenging direction for future work.Source: §6 · p. 10

A.1 PROOF OF THEOREM 1

The proof invokes an argument analogous to Lemma II.1 of Shayevitz and Feder. Its stated steps rely on CDF properties and uniformity of the auxiliary variable.

A.1 PROOF OF THEOREM 1

  • The proof derives the desired result by an argument analogous to Lemma II.1 of Shayevitz and Feder (2011).Source: §A.1 · p. 13
  • Step (a) uses that a CDF is non-decreasing and continuous from the right.Source: §A.1 · p. 13
  • Step (b) uses that w_t(m) is uniformly distributed on [0, 1] for every message m.Source: §A.1 · p. 13

A.2 PROOF OF THEOREM 2

The proof handles each competing message by showing that it is either eliminated in finite time or its log-posterior ratio diverges. It establishes finite-time elimination when a transition impossible under a candidate message can occur, and uses martingale bounds for the other case.

A.2 PROOF OF THEOREM 2

  • Non-deterministic actions give a positive probability of disagreement between message-conditioned actions for every circular distance in (0, 1).The disagreement probability is continuous in that distance.Source: §A.2 · p. 14
  • Almost surely, each competing message is either assigned zero posterior at a finite time or has a log-posterior ratio that diverges.Once its posterior reaches zero, the update rule keeps it at zero, which also makes the log-posterior ratio diverge.Source: §A.2 · p. 15
  • When C1 holds, recurrence and a transition impossible under the competing message make that message’s posterior zero in finite time almost surely.The true message can generate the action and observed transition with positive probability when the process visits the specified state.Source: §A.2 · p. 15
  • When C1 fails, the proof uses bounded martingale increments, Azuma–Hoeffding, and Borel–Cantelli to control fluctuations and establish log-posterior-ratio growth.The argument first bounds the martingale deviations, then combines the resulting convergence with a positive lower bound on the drift.Source: §A.2 · pp. 16–17

B.1 EXPERIMENTAL ENVIRONMENTS

The experimental environments adapt familiar continuing-control settings and include a finite-state battery-management task. Their dynamics and rewards provide settings for evaluating PRAM.

B.1 EXPERIMENTAL ENVIRONMENTS

  • ReFrozenLake retains FrozenLake’s grid and slippery dynamics but makes holes nonterminal, allowing long-horizon communication experiments.A hole incurs a penalty and sends the agent to another valid grid position; reaching the goal still terminates the trajectory.Source: §B.1 · p. 17
  • ConTaxi turns Taxi-v4 into a continuing task by sampling a new passenger origin and destination after each successful drop-off.It preserves the original state and action spaces and Taxi-v4’s reward structure, with optional rainy-mode dynamics.Source: §B.1 · p. 17
  • SBM is a continuing finite-state battery-management environment with 1,000 states and five charging or discharging actions.Its commanded action executes as intended with probability 0.8 and shifts by −1 or +1 with probability 0.1 each, subject to constraints; reward reflects energy costs, sales, and battery degradation.Source: §B.1 · pp. 17–18

B.2 ADDITIONAL EXPERIMENTAL RESULTS

Across three environments, PRAM rewards remain nearly identical across transmitted messages and closely match the corresponding reference-policy rewards. The accompanying pseudocode outlines the encoder’s inputs and its repeated action, observation, and posterior-update steps.

B.2 ADDITIONAL EXPERIMENTAL RESULTS

  • PRAM rewards are nearly identical across messages and closely match the corresponding reference-policy rewards in all three environments.The figure compares rewards for different transmitted messages with average rewards for selected reference policies, shown as dashed lines.Source: §B.2 · p. 18

C ALGORITHM PSEUDOCODE

  • Algorithm 1 takes the transition kernel, blocklength, transmitted message, and message prior, then initializes the posterior and observes the initial state.The encoder iterates over the blocklength.Source: C ALGORITHM PSEUDOCODE · p. 18
  • At each step, the encoder draws common randomness, determines an information point, applies an action, observes the next state, and updates the posterior.These are the repeated operations shown in the encoder pseudocode.Source: C ALGORITHM PSEUDOCODE · p. 18
Loading 2610.15976v1…