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

Gongpu Chen; Deniz Gündüz

cs.ITOct 11, 2026

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

Authors: Gongpu Chen, Deniz Gündüz

Organizations: Department of Electrical and Electronic Engineering Imperial College London, London SW7 2AZ, U.K.

Abstract

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.

Figures & tables

Figure 2: An illustration of the coding algorithm. Suppose

|\mathcal{M}|=4

and the message is

m^{*}=2

, then

a_{t}(m^{*})=4

in this example.

Environment	Reference Policy	Message
Environment	Reference Policy	0	1	2	3	4	5	6	7
ReFrozenLake	Policy 1	0.012	0.012	0.010	0.011	0.011	0.010	0.010	0.009
ReFrozenLake	Policy 2	0.015	0.011	0.010	0.010	0.011	0.011	0.012	0.011
ConTaxi	Policy 1	0.007	0.006	0.006	0.007	0.006	0.007	0.007	0.006
ConTaxi	Policy 2	0.008	0.008	0.008	0.009	0.008	0.008	0.008	0.008
SBM	Policy 1	0.023	0.023	0.023	0.023	0.023	0.023	0.023	0.023

Table 1: Total variation (TV) distance between the empirical action distribution induced by PRAM and the corresponding reference policy for different messages.

Panel of Figure 3 — Figure 3: PRAM performance on policy watermarking in ReFrozenLake and SBM, and trajectory provenance in ConTaxi.

Panel of Figure 4 — Figure 4: Effect of randomness on PRAM. (a) and (c): Policy randomness is varied through the temperature parameter. (b) System randomness is varied through the rainy probability.

Panel of Figure 5 — Figure 5: Performance of PRAM under model mismatch. The TV distance measures the discrepancy between the true transition kernel and the estimated kernel used by PRAM.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 6 — Figure 6: Control reward of transmitting different messages using PRAM.

b_{t}(m)\triangleq P({\mathbf{m}}<m|{\mathbf{s}}^{t},{\mathbf{u}}^{t-1})=\sum_{j<m}\rho_{t}(j)

Appendix

Algorithm 1 Posterior-matching randomness modulation (PRAM): Encoder

Calculating Mutual Information between a Reward Maximizer and its Environment
Feb 13, 2026Alfred Harwood, Jose Faustino, Alex AltairMarkov Decision Processes Reinforcement Learning
1Dovetail Research · University of Sao Paulo
MDP Planning as Policy Inference
Feb 19, 2026David TolpinVariational Monte Carlo Markov Decision Processes
Offtopia
Dissimilarity-Based Markov Decision Processes for Stabilizing State Distributions
Oct 21, 2026Xun Shen, Yuepeng Wang, Daniyal Sajedi-Hosseini +6RL Control Markov Decision Processes
Tokyo University of Agriculture and Technology, Japan · LY Corporation, Japan · Institute of Science Tokyo, Japan +2

Feb 13, 2026J/K move · Enter open · S save

Calculating Mutual Information between a Reward Maximizer and its Environment

Alfred Harwood, Jose Faustino, Alex Altair

1Dovetail Research · University of Sao Paulo

Markov Decision Processes Reinforcement Learning World Models Information-Theoretic Lower Bounds Mutual Information

Open paper AskPDF arXiv

An important question in the field of AI is the extent to which successful behaviour requires an internal representation of the world. In this work, we quantify the amount of information an optimal policy provides about the underlying environment. We consider a Controlled Markov Process (CMP) with

n

states and

m

actions, assuming a uniform prior over the space of possible transition dynamics. We prove that observing a deterministic policy that is optimal for any non-constant reward function then conveys exactly

n \log m

bits of information about the environment. Specifically, we show that the mutual information between the environment and the optimal policy is

n \log m

bits. This bound holds across a broad class of objectives, including finite-horizon, infinite-horizon discounted, and time-averaged reward maximization. These findings provide a precise information-theoretic lower bound on the ``implicit world model'' necessary for optimality.

Abstract

Explore similar work

Calculating Mutual Information between a Reward Maximizer and its Environment

MDP Planning as Policy Inference

Dissimilarity-Based Markov Decision Processes for Stabilizing State Distributions