Paper deep dive
Embedding Information in Policy Randomness: Distribution-Preserving Implicit Communication in MDPs
Gongpu Chen, Deniz Gündüz
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2610.15976v1
- Canonical: https://arxiv.org/abs/2610.15976v1
Trouble viewing inline? Open PDF directly →
Full Text
65,130 characters extracted from source content.
Expand or collapse full text
Embedding Information in Policy Randomness: Distribution-Preserving Implicit Communication in MDPs Gongpu Chen Deniz Gündüz Affiliation: Department of Electrical and Electronic Engineering Affiliation: Imperial College London, Affiliation: London SW7 2AZ, U.K. Email: gongpu.chen,d.gunduz@imperial.ac.uk 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. 1 Introduction Stochastic policies are widely used in control systems and reinforcement learning (RL), where policy randomness facilitates exploration (Ahmed et al., 2019), enhance robustness (Eysenbach and Levine, 2021), and supports multimodal decision making (Zhao et al., 2019). Under a stochastic policy, actions are sampled from a state-dependent distribution rather than selected deterministically. This paper reveals a new role of policy randomness: it can be exploited to embed information into an agent’s behavior without degrading its control performance. Specifically, we consider a Markov decision process (MDP) in which an agent interacts with the environment according to a prescribed stochastic policy (Puterman, 2014). Our goal is to enable the agent to embed and communicate a message through its action realizations while preserving the prescribed action distribution at every state. In other words, the embedded information should be recoverable from the resulting state trajectory without changing the marginal behavior of the reference policy. We refer to this technique as distribution-preserving implicit communication (DPIC). One important application of this technique is multi-bit policy watermarking. RL has been increasingly deployed in practical decision-making systems, ranging from robotics and autonomous systems to energy management, inventory control, and cyber-defence (Liu et al., 2025; Yu et al., 2021; Nguyen and Reddi, 2021). In many such applications, the resulting policies are trained using valuable data and substantial computational and engineering resources, making them important intellectual property (IP) of the development team. Protecting the IP of these RL policies therefore requires mechanisms that can verify policy ownership and detect unauthorized use or replication. Motivated by this need, recent studies (Amir et al., 2026; Chen et al., 2021; Behzadan and Hsu, 2019; Huang et al., 2025) have investigated digital watermarking methods for policy IP protection. However, existing methods primarily support zero-bit watermarking, where the detector only determines whether a watermark is present. In contrast, the DPIC framework naturally enables multi-bit watermarking, allowing policy owners to embed richer information for identification and attribution. The same information-embedding mechanism can also support closely related tasks such as trajectory provenance (Gao et al., 2026) and more general behavioral metadata embedding (An et al., 2026) for source attribution, authentication, and traceability. As suggested by its name, DPIC casts information embedding as a communication problem, and more specifically, a channel coding problem. Inspired by implicit communication in control systems (Chen and Gündüz, 2025; Wu et al., 2025), we view the MDP environment as a state-dependent communication channel, where the agent’s action serves as the channel input and the resulting state serves as the channel output. Under this interpretation, embedding a B-bit message into the agent’s behavior is equivalent to transmitting the message through this channel. A key objective of DPIC is to enable such communication without degrading the original control performance. This motivates a distribution-preserving requirement on the agent’s actions. Unlike conventional communication, where the input distribution is typically constrained only after averaging over the message distribution (Cover et al., 1991), applications such as policy watermarking may repeatedly embed the same fixed message. Message-averaged preservation is therefore insufficient to guarantee unchanged control performance. We instead require the action distribution to match the prescribed stochastic policy for every state and every message. This requirement poses a fundamental challenge. From an information-theoretic perspective, preserving the same action distribution for every message implies that, conditioned on the current state, the action alone is independent of the message and therefore cannot directly convey information about it. To overcome this limitation, we introduce common randomness shared between the agent (encoder) and the observer (decoder), and select each action based on the message, the observed state history, and the shared random variable. Communication is then enabled through the message-dependent coupling between the action and the common randomness, while the marginal action distribution remains unchanged for every message. Building on this idea, we develop the posterior-matching randomness modulation (PRAM) scheme. The term randomness modulation refers to encoding information by controlling the realization, rather than the distribution, of policy randomness. We show that PRAM preserves the prescribed action distribution for every state and every message, while still enabling reliable information transmission through the MDP dynamics. Under mild conditions, the posterior probability of the transmitted message converges to one as the trajectory length increases, ensuring asymptotically reliable message recovery. We further demonstrate that PRAM remains effective under model mismatch, where the encoder and decoder rely on an estimated transition kernel rather than the true system dynamics, making the method particularly relevant to learning-based systems. Our main contributions are summarized as follows. (i) We introduce the idea of embedding information in policy randomness and formulate it as DPIC. (i) We develop a posterior-matching randomness modulation scheme based on common randomness and prove its per-message distribution-preserving property. (i) We establish the asymptotic reliability of PRAM. (iv) We demonstrate the effectiveness of PRAM in multi-bit policy watermarking and trajectory provenance, including under model mismatch. 2 Related Work Policy watermarking. Existing policy-watermarking methods mainly focus on ownership verification through behavioral signatures. Early work embeds watermarks through designated state-action patterns (Behzadan and Hsu, 2019), while temporal watermarking exploits sequential behaviors for more robust verification (Chen et al., 2021). More recent approaches extend behavioral watermarking to general agents (Huang et al., 2025) and remotely observable robotic policies (Amir et al., 2026). These methods are primarily designed for zero-bit watermark detection, where the detector can only distinguish between the presence and absence of a watermark. In contrast, multi-bit policy watermarking remains largely unexplored. A closely related work on multi-bit behavioral watermarking for LLM-based agents is TRACE (Gao et al., 2026), which also exploits controlled action sampling to embed information. However, its detector relies on direct observation of the executed actions, which is generally unavailable in many MDP and control settings. We therefore consider a more realistic setting in which the observer only observes the resulting state trajectory, and the embedded information must be conveyed through the stochastic system dynamics. Sampling-based watermarking for generative models. Compared with policy watermarking, multi-bit watermarking for generative models, particularly LLMs, has received substantially more attention. Existing methods embed information by modifying or controlling the token-sampling process while attempting to preserve text quality and statistical properties of the original model (Kirchenbauer et al., 2023; Yoo et al., 2024; Wang et al., 2024; Park et al., 2026; Zhu et al., 2026). However, by the nature of autoregressive LLM generation, these methods assume that the generated tokens—the actions under a sequential decision interpretation—are directly observable to the detector. As in (Gao et al., 2026), this leads to a fundamentally different decoding setting from ours and prevents these methods from being applied to general policy watermarking problems. Implicit communication and feedback coding. The idea of DPIC is closely related to communicating via MDPs (Sokota et al., 2022; Karabag et al., 2019) and implicit communication in control systems (Chen and Gündüz, 2025; Chen and Gündüz, 2026; Rips and Sabag, 2025). These works view the controlled system as a communication channel and mainly characterize the tradeoff between communication rate and control performance across different policies. The most relevant work is Act2Comm (Wu et al., 2025), which studies communication through actions in finite-state MDPs, a setting similar to ours. Essentially, Act2Comm addresses the problem of channel coding over a finite-state channel with feedback and, like conventional channel coding, constrains the input distribution only after averaging over the message distribution. In contrast, DPIC imposes a stronger requirement: the prescribed action distribution must be preserved for every state and every message. This distinction is particularly important for applications such as policy watermarking, where the same identifier may be embedded repeatedly, and makes the DPIC problem fundamentally more restrictive. Nevertheless, our method is inspired by feedback channel coding (Gallager and Nakiboğlu, 2010; Tatikonda and Mitter, 2008; Permuter et al., 2009), particularly posterior matching (Shayevitz and Feder, 2011) and its variant (Li and El Gamal, 2015). With feedback, the encoder observes the same channel outputs as the decoder and can therefore track the decoder’s posterior belief over the message. Posterior matching exploits this shared posterior to adaptively determine what information should be conveyed next. Building on this principle, we introduce common randomness shared by the encoder and decoder and develop a posterior-matching-based scheme tailored to DPIC. The common randomness enables message-dependent action selection while preserving the prescribed action distribution for every message, which is the key distinction from conventional schemes. Notations. We use sts^t to denote the sequence (s1,s2,…,st)(s_1,s_2,…,s_t). When it is necessary to distinguish a random variable from its realization, we use boldface notation, e.g., m, for the random variable and the corresponding regular font, e.g., m, for its realization. 3 Problem Statement 3.1 System Model Figure 1: System model. Consider a system in which an agent interacts with its environment by taking actions. We model the system as an MDP defined by a tuple (,,r,T)(S,A,r,T), where S is a finite state space, A is a finite action space, T:×→[0,1]T:S×A×S→[0,1] is the transition kernel, and r:×→ℝr:S×A is the reward function. For simplicity, we index the actions by letting =1,2,⋯,||A=\1,2,·s,|A|\. At each time t, the agent observes the system state sts_t and selects an action ata_t. The environment then transitions to a new state st+1s_t+1 according to the distribution T(⋅|st,at)T(·|s_t,a_t). We further assume the presence of a passive observer that can observe the state sts_t but cannot take actions or otherwise influence the environment. The system model is illustrated in Fig. 1. A stationary control policy π:→Δ()π:S→ (A) is a mapping that specifies an action distribution for each state, where Δ() (A) denote the probability simplex over A. We use π(a|s)π(a|s) to denote the probability that policy π selects action a∈a in state s∈s . Unlike standard MDP or RL problems, our objective is not to identify an optimal policy that maximizes the cumulative or average reward. Instead, we assume that the agent is already equipped with a suitable stationary policy π, referred to as the reference policy. Our central question is: Can the agent encode a message in its actions while following π, such that the observer can accurately decode the message from the resulting sequence of observed states? In particular, let m denote a message drawn from a finite message set ℳ=0,1,⋯,2B−1M=\0,1,·s,2^B-1\ according to a distribution P_m, where B denotes the message length in bits. Conditioned on m, the agent selects an action sequence a1:na_1:n, with each action ata_t determined using the message m and the state history up to the current time step t. After observing the resulting state sequence s1:n+1s_1:n+1, the observer produces an estimate m of the message. The estimation error probability, also referred to as the decoding error probability, is then defined as Pe(n)≜P(^≠)P^(n)_e P( m≠m). Our objective is twofold: (i) to minimize Pe(n)P_e^(n) for a fixed horizon n, and (i) to ensure, for every realization of m, that the agent’s action at each time step remains distributed according to the reference policy, i.e., t∼π(⋅|t),∀ta_t π(·|s_t),∀ t. This model has applications in a range of practical settings, including multi-bit policy watermarking and trajectory provenance, as will be demonstrated in greater detail in the experimental section. 3.2 Problem Formulation In essence, our task is to enable the agent to transmit a message to the observer without relying on an external communication channel, instead using the MDP environment itself as the channel. This problem can be studied through the lens of implicit communication (Chen and Gündüz, 2025). Specifically, the MDP environment can be interpreted as a finite-state channel (FSC) between the agent (encoder) and the observer (decoder): at each time step t, the action ata_t serves as the channel input, and the current state sts_t serves as the channel state. Upon execution of ata_t, the environment transitions to a new state st+1s_t+1, which constitutes the corresponding channel output. Under this interpretation, the reference policy π specifies the desired input distribution of the FSC: conditional on the current channel state sts_t, the channel input should be distributed according to π(⋅|st)π(·|s_t). Within the framework of implicit communication, the problem reduces to designing a channel code for the FSC induced by the MDP. In channel coding, such a code consists of an encoder and a decoder. The encoder is a sequence of mappings ℰ=ℰt:1≤t≤nE=\E_t:1≤ t≤ n\, where ℰt:ℳ×t×t−1→E_t:M×S^t×A^t-1 determines the action ata_t from the message, the state history, and the past actions. After observing the initial channel state s1s_1 and the subsequent n channel outputs s2:n+1s_2:n+1, the observer applies the decoder mapping :n+1→ℳD:S^n+1 to estimate the transmitted message. Here, n denotes the blocklength, corresponding to the number of time steps used to transmit the message. Conventional channel coding requires the channel input to follow a prescribed distribution, such as a capacity-achieving distribution, only after averaging over all messages. Our setting, however, imposes a stronger constraint: for every realization m of m, the channel input at time t must follow the prescribed distribution π(⋅|st)π(·|s_t). At first glance, this requirement appears to preclude communication. Indeed, if P(at|st,m)=π(at|st)P(a_t|s_t,m)=π(a_t|s_t) for every m, then ta_t and m are conditionally independent given sts_t, and hence the conditional mutual information I(t;|st)=0I(a_t;m|s_t)=0. As a result, input ta_t conveys no additional information about the message beyond that already contained in the current state. To address this challenge, we introduce common randomness shared between the agent and the observer. Specifically, let t∈:t≥1\u_t :t≥ 1\ be a sequence of independent and identically distributed (i.i.d.) random variables, with each tu_t drawn from a distribution P_u. At each time t, the realization of tu_t is revealed to both the agent and the observer. We assume that tu_t is independent of the message m, the state history ts^t, and the action history t−1a^t-1. In practice, such common randomness can be generated using a shared random seed derived from a secret key. With the introduction of common randomness, we redefine the encoder as ℰt:ℳ×t×t−1×t→,t≥1. _t:M×S^t×A^t-1×U^t ,\ t≥ 1. Thus, at time t, the agent uses the shared random variables tu^t, together with the message and the available state and action histories, to determine the action ta_t. Correspondingly, the decoder is defined as :n+1×n→ℳD:S^n+1×U^n . The common randomness makes communication possible because the encoder can satisfy I(t;|st)=0I(a_t;m|s_t)=0 while maintaining I(t;|st,ut)>0I(a_t;m|s_t,u_t)>0. In other words, although the action reveals no information about the message when conditioned only on the current state, it can depend strongly on the message once the shared randomness is known. Our objective is to design an encoder–decoder pair (ℰ,)(E,D) that enables efficient message transmission while ensuring that the agent adheres to the reference policy π. Figure 2: An illustration of the coding algorithm. Suppose |ℳ|=4|M|=4 and the message is m∗=2m^*=2, then at(m∗)=4a_t(m^*)=4 in this example. 4 Distribution-preserving Implicit Communication In this section, we introduce a coding scheme that preserves the conditional action distribution t∼π(⋅|t)a_t π(·|s_t) for every message m. We also provide a theoretical guarantee that, under this scheme, the observer’s decoding error probability vanishes as the blocklength n tends to infinity. 4.1 Coding Scheme Our method is largely inspired by posterior matching (Shayevitz and Feder, 2011) and its variant (Li and El Gamal, 2015), both of which are coding schemes for feedback communication. However, these schemes preserve the desired input distribution only after averaging over all messages, rather than for each message individually. To overcome this limitation, we introduce the common randomness tu_t and develop a novel coding scheme that leverages it to preserve the prescribed input distribution π(⋅|t)π(·|s_t) for every message. We first adapt the posterior matching principles introduced by Shayevitz and Feder (2011) to incorporate common randomness. At each time t, the observer has access to the state sequence ts^t and the common random sequence t−1u^t-1, which together provide information about the message m. Let ρt(⋅) _t(·) denote the observer’s posterior distribution over m, defined as ρt(m)≜P(=m|t,t−1),∀m∈ℳ. _t(m) P(m=m|s^t,u^t-1),\ ∀ m . Specifically, ρ1(m)=P(m) _1(m)=P_m(m) as m and 1s_1 are independent. As long as ρt _t is not a point mass, the observer retains some uncertainty about m and therefore requires additional information to identify it. The posterior matching principle addresses the following question: given ts^t and t−1u^t-1, what additional information is needed to determine m? A natural candidate is a random variable tw_t satisfying the following conditions: (i) tw_t is independent of (t,t−1)(s^t,u^t-1); and (i) the message m can be uniquely determined by (t,t,t)(w_t,s^t,u^t). They are referred to as two design principles. Intuitively, the first principle ensures that tw_t does not convey any “old information” already available to the observer, while the second guarantees that (t,t)(w_t,u_t) carries sufficient “new information” to determine the message. Given an appropriate construction of tw_t, the action ta_t is then selected as a function of tw_t while ensuring that its conditional distribution matches the reference policy π(⋅∣t)π(· s_t). Following this idea, we are now ready to introduce our coding scheme. First, define bt(m)≜P(<m|t,t−1)=∑j<mρt(j). b_t(m) P(m<m|s^t,u^t-1)= _j<m _t(j). Note that (t,t−1)(s^t,u^t-1) is also available to the agent; therefore, the agent can also compute ρt _t and btb_t at each time. We then construct the information point at time t as follows: t()=[bt()+lt()ρt()+t]mod1, w_t(m)= [b_t(m)+l_t(m) _t(m)+u_t ] 1, where lt:ℳ→(0,1)l_t:M→(0,1) is a deterministic function and t∼Unif[0,1]u_t [0,1] independent of all the other variables. For each m∈ℳm , the quantity bt(m)+lt(m)ρt(m)b_t(m)+l_t(m) _t(m) lies within the interval (bt(m),bt(m+1))(b_t(m),b_t(m+1)), and t(m)w_t(m) is obtained by applying a random cyclic shift to this point, as illustrated in Figure 2. We write tw_t in place of t()w_t(m) when referring to the random variable induced by m, rather than to its value for a particular realization of m. The choice of ltl_t determines the pairwise distances between information points and thus affects the observer’s decoding error probability. In this paper, we set lt(m)=0.5l_t(m)=0.5 for all m∈ℳm , as this choice simplifies the reliability analysis. It is straightforward to verify that tw_t satisfies the two design principles stated above. First, for every m∈ℳm and any realization (st,ut−1)(s^t,u^t-1), we have t(m)∼Unif[0,1]w_t(m) [0,1], which implies that tw_t is independent of (t,t−1)(s^t,u^t-1). Second, the message m can be uniquely recovered from tw_t, tu_t, ρt _t, and btb_t. Because ρt _t and btb_t are determined by (t,t−1)(s^t,u^t-1), the second design principle also holds. The next step is to select an action based on tw_t while preserving the desired distribution. To this end, let Ft|t(⋅)F_a_t|s_t(·) denote the cumulative distribution function (CDF) of π(⋅|t)π(·|s_t). Its generalized inverse is defined as Ft|t−1(w):=infa∈:Ft|t(a)≥w,∀w∈[0,1]. F^-1_a_t|s_t(w):= \a :F_a_t|s_t(a)≥ w\,∀ w∈[0,1]. The action at time t is then determined by t=Ft|t−1(t)a_t=F^-1_a_t|s_t(w_t). Upon execution of ta_t, the MDP transitions to a new state t+1s_t+1, which is observed by both the agent and the observer. Given any realization st+1s^t+1, the posterior distribution is then updated according to Bayes’ rule: ρt+1(m)=ρt(m)T(st+1|st,at(m))∑jρt(j)T(st+1|st,at(j)),∀m∈ℳ, _t+1(m)= _t(m)T(s_t+1|s_t,a_t(m)) _j _t(j)T(s_t+1|s_t,a_t(j)),\ ∀ m , (1) where at(m)=Ft|t−1(t(m))a_t(m)=F^-1_a_t|s_t(w_t(m)). At the end of the transmission horizon, i.e., time n+1n+1, the observer can decode the message using the posterior distribution ρn+1 _n+1. A natural choice is the maximum a posteriori (MAP) estimator: ^=argmaxm∈ℳρn+1(m). m= _m _n+1(m). We refer to this method as posterior-matching randomness modulation (PRAM). It remains to show that PRAM preserves the prescribed input distribution for every message m; this is formally established in the following result. Theorem 1 (Distribution Preservation). Under the PRAM scheme, the following holds for every realization m∈ℳm of the message m: P(at|st,ut−1,m)=π(at|st),∀at,st. P(a_t|s^t,u^t-1,m)=π(a_t|s_t),\ ∀ a_t,s^t. Proof. The proof is provided in Appendix A.1. ∎ Note that PRAM selects each action ta_t based t,ts^t,u^t, and m. Hence Theorem 1 means that, when averaged over the common random variable tu_t, PRAM preserves the action distribution prescribed by the reference policy. Consequently, the communication capability is achieved without degrading the expected control reward. This distribution-preserving property is a key advantage of PRAM. 4.2 Reliability Analysis According to the design principles of PRAM, tw_t carries information about the message m, and so does the action ta_t, since it is generated as a function of tw_t. However, this information is conveyed to the observer only through the stochastic state transitions of the system and may therefore be corrupted by transition noise. It is thus not immediately clear whether PRAM enables reliable message recovery. In this subsection, we establish a theoretical guarantee of asymptotic reliability: the observer’s decoding error probability can be made arbitrarily small by increasing the blocklength. We first introduce the following assumptions, which are essential for our analysis. Assumption 1. The Markov chain induced by the reference policy π is irreducible. Assumption 2. Under the reference policy π, there exists a state s∗s^* such that π(⋅|s∗)π(·|s^*) is nondegenerate and DKL(T(⋅|s∗,a)||T(⋅|s∗,a′))>0D_KL(T(·|s^*,a)||T(·|s^*,a ))>0 for any pair of distinct actions a and a′a in the support of π(⋅|s∗)π(·|s^*). Irreducibility is a standard assumption in the analysis of finite-state MDPs and naturally yields the property required in Assumption 1. Assumption 2 ensures the existence of at least one recurrent state at which the reference policy is genuinely stochastic and the transition distributions induced by different actions are distinguishable. Now we are ready to present the reliability guarantee. Theorem 2 (Asymptotic Reliability). Let m∗∈ℳm^* be the message transmitted by the agent. Then, under Assumptions 1 and 2, ρn(m∗)→a.s.1 as n→∞. _n(m^*) a.s.1 as n→∞. As a result, the observer’s decoding error probability Pe(n)→0P^(n)_e→ 0 as n→∞n→∞. Proof. The proof is provided in Appendix A.2. ∎ The significance of Theorem 2 lies in the per-message distribution-preserving constraint of PRAM. As discussed earlier, requiring the action distribution to coincide with the reference policy for every message implies I(t;|t)=0I(a_t;m|s_t)=0, meaning that, conditioned on the current state, the action alone reveals no additional information about the message. The introduction of common randomness tu_t, however, creates a message-dependent coupling between the action selection and the shared randomization, making communication possible without altering the prescribed action distribution. Theorem 2 confirms that this mechanism is sufficient for reliable communication: despite the per-message distribution-preserving constraint, the observer can recover the transmitted message with vanishing error probability as the blocklength grows. 5 Experiments This section presents experimental results demonstrating the effectiveness of the proposed PRAM method. We evaluate PRAM in three MDP environments: ReFrozenLake with 64 states and 4 actions, ConTaxi with 500 states and 6 actions, and Stochastic Battery Management (SBM) with 1000 states and 5 actions. Detailed descriptions of these environments are provided in Appendix B.1. Table 1: Total variation (TV) distance between the empirical action distribution induced by PRAM and the corresponding reference policy for different messages. Environment Reference Policy Message 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 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 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 Policy 2 0.029 0.028 0.028 0.029 0.029 0.030 0.028 0.029 Distribution preservation. We first verify whether PRAM preserves the action distribution for every state and every message. To this end, we quantify the total variation (TV) distance between the reference policy π and the empirical action distribution induced by PRAM under each message m∈ℳm . Specifically, we define DTV(m)≜12∑sμ(s)∑a|π(a|s)−P(a|s,m)|D_TV(m) 12 _sμ(s) _a|π(a|s)-P(a|s,m)|, where μ(⋅)μ(·) denotes the stationary state distribution induced by the reference policy, and P(a|s,m)P(a|s,m) is the empirical probability of selecting action a in state s when message m is transmitted using PRAM. We set the message length to B=3B=3 bits and blocklength to n=20n=20, and evaluate DTV(m)D_TV(m) for all eight possible messages. The results are reported in Table 1. The TV distance remains close to zero across all tested messages and environments, empirically confirming the per-message distribution-preserving property of PRAM. Consequently, PRAM can embed information without altering the nominal action distribution and hence without degrading the expected control reward. Additional results in Appendix B.2 further show that the control reward obtained under each transmitted message closely matches that of the reference policy. Applications. The ability of PRAM to embed information into stochastic policy realizations while preserving the prescribed action distribution naturally enables several downstream applications. We consider two representative tasks: multi-bit policy watermarking and trajectory provenance. In policy watermarking, a fixed multi-bit identifier is associated with a policy and repeatedly embedded into its behavior, providing a persistent signature for ownership verification. In contrast, trajectory provenance aims to determine the origin of an observed trajectory, e.g., which deployed agent or execution session produced it; the embedded information may therefore vary across episodes, agents, or deployment instances. We evaluate multi-bit policy watermarking in ReFrozenLake and SBM, and trajectory provenance in ConTaxi. For each task, we vary the message length and report the decoding accuracy as a function of the trajectory blocklength. Although these two applications differ in the semantics of the embedded information, both can be realized through the same PRAM communication mechanism. For the watermarking task, we report performance averaged over different identifiers, making the experimental protocol comparable to that used for trajectory provenance. The results are shown in Figure 3. The decoding accuracy is defined as the fraction of trials in which all message bits are correctly recovered, i.e., 1−Pe(n)1-P_e^(n). As shown in the figure, the decoding accuracy increases monotonically with the blocklength and approaches one for all tested message lengths even at reasonably low trajectory lengths (∼40 40-5050). (a) ReFrozenLake (b) ConTaxi (c) SBM Figure 3: PRAM performance on policy watermarking in ReFrozenLake and SBM, and trajectory provenance in ConTaxi. Effect of randomness. We next investigate how different sources of randomness affect the communication performance of PRAM. In particular, we consider randomness arising from both the stochastic reference policy and the system dynamics. To study the effect of policy randomness, we obtain the reference policy using entropy-regularized value iteration with temperature parameter α, where α=0α=0 corresponds to the optimal deterministic policy and a larger α induces a more stochastic policy. We then evaluate PRAM under reference policies with different temperatures in ReFrozenLake and SBM. The results are shown in Figures 4(a) and 4(c). As expected, greater policy randomness generally leads to higher decoding accuracy, since it provides more degrees of freedom for embedding information. We examine the effect of system randomness in ConTaxi, where the taxi moves in the intended direction with probability p and in either lateral direction with probability (1−p)/2(1-p)/2. Hence the resulting transition uncertainty is characterized by the entropy H(p)=−plogp−(1−p)log1−p2H(p)=-p p-(1-p) 1-p2. We fix the reference policy and evaluate PRAM in ConTaxi under different rainy probabilities p, as shown in Figure 4(b). From a communication perspective, randomness in the system dynamics acts as channel noise and makes the transmitted information more difficult to recover from the state trajectory. Therefore, lower transition uncertainty generally leads to higher decoding accuracy. (a) ReFrozenLake (b) ConTaxi (c) SBM 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. Model mismatch. We further examine the robustness of PRAM to model mismatch. Specifically, suppose that neither the agent nor the observer knows the true transition kernel T of the MDP, and both instead rely on an estimated kernel T^≠T T≠ T. PRAM therefore performs action selection and posterior updates using T T, while the observed state trajectory is generated according to the true kernel T. Such model mismatch naturally arises in RL, where the transition dynamics must typically be estimated from interaction data. We quantify the discrepancy between T and T T using the occupancy-weighted TV distance d(T,T^)≜12∑sμ(s)∑aπ(a|s)∑s′|T(s′|s,a)−T^(s′|s,a)|d(T, T) 12 _sμ(s) _aπ(a|s) _s |T(s |s,a)- T(s |s,a)|, where μ is the stationary state distribution induced by the reference policy π. Figure 5 reports the decoding performance of PRAM under different levels of model mismatch. For each environment, we estimate T T from interaction trajectories, with larger amounts of data yielding more accurate estimates and hence smaller TV distances. We then fix the message length and evaluate the decoding accuracy as a function of the blocklength. The results demonstrate that PRAM is robust to moderate model mismatch: high decoding accuracy can still be achieved even when T T differs noticeably from the true transition kernel. Moreover, across the tested mismatch levels, the decoding accuracy continues to improve with the blocklength and approaches one for sufficiently long trajectories. (a) ReFrozenLake (b) ConTaxi (c) SBM 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. 6 Conclusion This paper studied how to embed information into an agent’s behavior without altering the action distribution prescribed by a stochastic control policy. We introduced the idea of randomness modulation and formulated the problem as DPIC. The key idea is to view the MDP environment as a communication channel, with the agent’s action serving as the channel input and the resulting state as the channel output. Unlike conventional channel coding, DPIC imposes a stronger per-message distribution-preserving requirement. To address this challenge, we introduced common randomness shared by the encoder and decoder and developed the PRAM scheme. By modulating action realizations, PRAM establishes message-dependent couplings between the action and the common random variable, enabling information recovery from the observed state trajectory while preserving the prescribed action distribution. We proved the per-message distribution-preserving property of PRAM and established its asymptotic reliability. Extensive experiments demonstrated reliable message recovery, robustness to model mismatch, and the applicability of PRAM to tasks including multi-bit policy watermarking and trajectory provenance. Extending DPIC to partially observable settings, where the observer has only incomplete or noisy state information (Krishnamurthy, 2016), is an important and challenging direction for future work. References Ahmed et al. (2019) Z. Ahmed, N. Le Roux, M. Norouzi, and D. Schuurmans Understanding the impact of entropy on policy optimization. In International conference on machine learning, p. 151–160. Cited by: §1. Amir et al. (2026) M. Amir, M. Flageat, and A. Prorok Remotely detectable robot policy watermarking. In International Conference on Learning Representations, Vol. 2026, p. 149601–149623. Cited by: §1, §2. An et al. (2026) H. An, S. Park, D. Kim, and Y. Han Sequential behavioral watermarking for llm agents. arXiv preprint arXiv:2605.11036. Cited by: §1. Behzadan and Hsu (2019) V. Behzadan and W. Hsu Sequential triggers for watermarking of deep reinforcement learning policies. arXiv preprint arXiv:1906.01126. Cited by: §1, §2. Chen and Gündüz (2025) G. Chen and D. Gündüz Implicit communication in linear quadratic Gaussian control systems. arXiv preprint arXiv:2509.16146. Cited by: §1, §2, §3.2. Chen and Gündüz (2026) G. Chen and D. Gündüz The control plant as a communication channel: implicit communication for decentralized lqg control. arXiv preprint arXiv:2605.01903. Cited by: §2. Chen et al. (2021) K. Chen, S. Guo, T. Zhang, S. Li, and Y. Liu Temporal watermarks for deep reinforcement learning models. In Proceedings of the 20th international conference on autonomous agents and multiagent systems, p. 314–322. Cited by: §1, §2. Cover et al. (1991) T. M. Cover, J. A. Thomas, and J. Kieffer Elements of information theory. Vol. 2, wiley New York. Cited by: §1. Eysenbach and Levine (2021) B. Eysenbach and S. Levine Maximum entropy RL (provably) solves some robust rl problems. arXiv preprint arXiv:2103.06257. Cited by: §1. Gallager and Nakiboğlu (2010) R. G. Gallager and B. Nakiboğlu Variations on a theme by schalkwijk and kailath. IEEE Transactions on Information Theory 56 (1), p. 6–17. External Links: Document Cited by: §2. Gao et al. (2026) Z. Gao, X. Li, X. Feng, J. Jiang, Y. Song, Y. Sui, Z. Xing, and L. Zhu TRACE: a two-channel robust attribution watermark via complementary embeddings for llm-agent trajectories. arXiv preprint arXiv:2607.08400. Cited by: §1, §2, §2. Hall et al. (1980) P. Hall, C. C. Heyde, Z. Birnbaum, and E. Lukacs Martingale limit theory and its application. Vol. 12, Elsevier. Cited by: §A.2. Huang et al. (2025) K. Huang, Z. Zhang, Z. Yang, and L. Zhou Agent guide: a simple agent behavioral watermarking framework. arXiv preprint arXiv:2504.05871. Cited by: §1, §2. Karabag et al. (2019) M. O. Karabag, M. Ornik, and U. Topcu Least inferable policies for markov decision processes. In 2019 American Control Conference (ACC), Vol. , p. 1224–1231. External Links: Document Cited by: §2. Kirchenbauer et al. (2023) J. Kirchenbauer, J. Geiping, Y. Wen, J. Katz, I. Miers, and T. Goldstein A watermark for large language models. In International conference on machine learning, p. 17061–17084. Cited by: §2. Krishnamurthy (2016) V. Krishnamurthy Partially observed markov decision processes. Cambridge university press. Cited by: §6. Li and El Gamal (2015) C. T. Li and A. El Gamal An efficient feedback coding scheme with low error probability for discrete memoryless channels. IEEE Transactions on Information Theory 61 (6), p. 2953–2963. Cited by: §2, §4.1. Liu et al. (2025) Z. Liu, X. Li, S. Chen, G. Li, J. Jiang, and J. Zhang Reinforcement learning with intrinsically motivated feedback graph for lost-sales inventory control. In International Conference on Artificial Intelligence and Statistics, p. 1657–1665. Cited by: §1. Nguyen and Reddi (2021) T. T. Nguyen and V. J. Reddi Deep reinforcement learning for cyber security. IEEE Transactions on Neural Networks and Learning Systems 34 (8), p. 3779–3795. Cited by: §1. Park et al. (2026) S. Park, H. Park, H. Ahn, and Y. Han WaterMod: modular token-rank partitioning for probability-balanced LLM watermarking. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 40, p. 32683–32691. Cited by: §2. Permuter et al. (2009) H. H. Permuter, T. Weissman, and A. J. Goldsmith Finite state channels with time-invariant deterministic feedback. IEEE Transactions on Information Theory 55 (2), p. 644–662. Cited by: §2. Puterman (2014) M. L. Puterman Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons. Cited by: §1. Rips and Sabag (2025) A. Rips and O. Sabag Communication over lqg control systems: a convex optimization approach to capacity. arXiv preprint arXiv:2509.17002. Cited by: §2. Shayevitz and Feder (2011) O. Shayevitz and M. Feder Optimal feedback communication via posterior matching. IEEE Transactions on Information Theory 57 (3), p. 1186–1222. Cited by: §A.1, §2, §4.1, §4.1. Sokota et al. (2022) S. Sokota, C. A. S. De Witt, M. Igl, L. M. Zintgraf, P. Torr, M. Strohmeier, Z. Kolter, S. Whiteson, and J. Foerster Communicating via markov decision processes. In International Conference on Machine Learning, p. 20314–20328. Cited by: §2. Tatikonda and Mitter (2008) S. Tatikonda and S. Mitter The capacity of channels with feedback. IEEE Transactions on Information Theory 55 (1), p. 323–349. Cited by: §2. Wang et al. (2024) L. Wang, W. Yang, D. Chen, H. Zhou, Y. Lin, F. Meng, J. Zhou, and X. Sun Towards codable watermarking for injecting multi-bits information to llms. In International Conference on Learning Representations, Vol. 2024, p. 39375–39401. Cited by: §2. Wu et al. (2025) H. Wu, G. Chen, and D. Gunduz Actions speak louder than words: rate-reward trade-off in Markov decision processes. In International Conference on Learning Representations, Vol. 2025, p. 37518–37545. Cited by: §1, §2. Yoo et al. (2024) K. Yoo, W. Ahn, and N. Kwak Advancing beyond identification: multi-bit watermark for large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), p. 4031–4055. Cited by: §2. Yu et al. (2021) L. Yu, S. Qin, M. Zhang, C. Shen, T. Jiang, and X. Guan A review of deep reinforcement learning for smart building energy management. IEEE Internet of Things Journal 8 (15), p. 12046–12063. Cited by: §1. Zhao et al. (2019) R. Zhao, X. Sun, and V. Tresp Maximum entropy-regularized multi-goal reinforcement learning. In International Conference on Machine Learning, p. 7553–7562. Cited by: §1. Zhu et al. (2026) J. Zhu, B. Huang, and X. Wan QuantileMark: a message-symmetric multi-bit watermark for llms. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 6790–6806. Cited by: §2. Appendix Appendix A Technical Proofs A.1 Proof of Theorem 1 Proof. The desired result follows from an argument analogous to that used in Lemma I.1 of (Shayevitz and Feder, 2011). In particular, for every m∈ℳm , P(Ft|t−1(t(m))≤a) P(F^-1_a_t|s_t(w_t(m))≤ a) =P(infa′:Ft|t(a′)≥t(m)≤a) =P ( \a :F_a_t|s_t(a )≥w_t(m)\≤ a ) =(a)P(Ft|t(a)≥t(m)) (a)=P (F_a_t|s_t(a)≥w_t(m) ) =(b)Ft|t(a). (b)=F_a_t|s_t(a). Here, (a) holds because a CDF is non-decreasing and continuous from the right, and (b) follows from the fact that t(m)∼Unif[0,1]w_t(m) [0,1] for every m∈ℳm . By definition, the above implies that t=Ft|t−1(t(m))∼π(⋅|t)a_t=F^-1_a_t|s_t(w_t(m)) π(·|s_t) for every realization m of the message. ∎ A.2 Proof of Theorem 2 This part provides the proof of Theorem 2. Before that, we need the following lemma. Lemma 1. Let m∗∈ℳm^* be the message transmitted by the agent. For any m≠m∗m≠ m^*, define Kt(m)=t=s∗,t(m∗)≠t(m). K_t(m)=1\s_t=s^*,a_t(m^*)≠a_t(m)\. Then we have lim infn→∞1nKn(m)≥δm, _n→∞ 1nK_n(m)≥ _m, where δm>0 _m>0 is a constant. Proof. Define the message point before applying random cyclic shift as wt′(m)=bt(m)+12ρt(m). w _t(m)=b_t(m)+ 12 _t(m). Let αt(m)≜min|wt′(m∗)−wt′(m)|,1−|wt′(m∗)−wt′(m)| _t(m) \|w _t(m^*)-w _t(m)|,1-|w _t(m^*)-w _t(m)|\ be the circular distance between wt′(m∗)w _t(m^*) and wt′(m)w _t(m). Then for any time t, we have αt(m)≤0.5 _t(m)≤ 0.5 and αt(m)≥ρt(m∗)+ρt(m)2≥ρt(m∗)2. _t(m)≥ _t(m^*)+ _t(m)2≥ _t(m^*)2. For any m≠m∗m≠ m^*, define the likelihood ratio Rt(m)=P(t,t−1|m)P(t,t−1|m∗) R_t(m)= P(s^t,u^t-1|m)P(s^t,u^t-1|m^*) According to Bayes’ rule, we have ρt(m∗) _t(m^*) =P(t,t−1,m∗)P(t,t−1)=P(m∗)P(t,t−1|m∗)∑m∈ℳP(m)P(t,t−1|m) = P(s^t,u^t-1,m^*)P(s^t,u^t-1)= P_m(m^*)P(s^t,u^t-1|m^*) _m P_m(m)P(s^t,u^t-1|m) =P(m∗)P(m∗)+∑m≠m∗P(m)Rt(m). = P_m(m^*)P_m(m^*)+ _m≠ m^*P_m(m)R_t(m). We next establish a lower bound on ρt(m∗) _t(m^*) by analyzing Rt(m)R_t(m). By definition, Rt+1(m)=Rt(m)T(t+1|t,t(m))T(t+1|t,t(m∗)). R_t+1(m)=R_t(m) T(s_t+1|s_t,a_t(m))T(s_t+1|s_t,a_t(m^*)). Then we can verify that Rt(m)R_t(m) is a nonnegative martingale. To see this, let t=σ(t,t−1)G_t=σ(s^t,u^t-1) denote the sigma-algebra generated by (t,t−1)(s^t,u^t-1). Then [Rt+1(m)|t] [R_t+1(m)|G_t] =Rt(m)∑s∈T(t+1=s|t,t(m∗))T(t+1=s|t,t(m))T(t+1=s|t,t(m∗)) =R_t(m) _s T(s_t+1=s|s_t,a_t(m^*)) T(s_t+1=s|s_t,a_t(m))T(s_t+1=s|s_t,a_t(m^*)) =Rt(m). =R_t(m). Applying the martingale convergence theorem yields Rt(m)→R∞(m)<∞a.s. R_t(m)→ R_∞(m)<∞ .s. Therefore, there exists constants Cm>0C_m>0 and Nm>1N_m>1 such that αt(m)≥Cm,∀t≥Nm. _t(m)≥ C_m, ∀ t≥ N_m. (2) At the state s∗s^* specified in Assumption 2, define f(u)=F|s∗−1(u) f(u)=F^-1_a|s^*(u) Recall that t(m)=f(t+wt′(m))mod1 a_t(m)=f(u_t+w _t(m)) 1 Since t∼Unif[0,1]u_t [0,1], we can shift coordinates and define q(α)≜P(f()≠f(+α)). q(α) P_u(f(u)≠ f(u+α)). Here, q(α)q(α) is the probability that t(m∗)≠t(m)a_t(m^*)≠a_t(m) given that the circular distance between the two message points is α. Since π(⋅|s∗)π(·|s^*) is non-deterministic, we have q(α)>0q(α)>0 for every α∈(0,1)α∈(0,1). Moreover, q(α)q(α) is continuous in α and αt(m)∈[Cm,0.5], _t(m)∈[C_m,0.5], compactness gives qm≜infα∈[Cm,0.5]q(α)>0. q_m _α∈[C_m,0.5]q(α)>0. Therefore, P(t(m∗)≠t(m)|t=s∗)≥qm>0 P(a_t(m^*)≠a_t(m)|s_t=s^*)≥ q_m>0 (3) for sufficiently large t. Define the state visitation frequency under the coding scheme as θn(s)=1n∑t=1nP(t=s). _n(s)= 1n _t=1^nP(s_t=s). Then Assumption 1 guarantees that θ(s∗)≜limn→∞θn(s∗)>0. θ(s^*) _n→∞ _n(s^*)>0. (4) Now, [Kt(m)|t]=t=s∗q(αt(m)) [K_t(m)|G_t]=1\s_t=s^*\q( _t(m)) For sufficiently large t, we have [Kt(m)|t]≥qmt=s∗E[K_t(m)|G_t]≥ q_m1\s_t=s^*\. Now define the martingale difference Zt(m)=Kt(m)−[Kt(m)|t]. Z_t(m)=K_t(m)-E[K_t(m)|G_t]. Since Kt(m)∈0,1K_t(m)∈\0,1\, [Kt(m)|t]∈[0,1]E[K_t(m)|G_t]∈[0,1]. We thus have |Zt(m)|<1|Z_t(m)|<1. The martingale strong law (Hall et al., 1980) gives 1n∑t=1nZt(m)→0a.s. 1n _t=1^nZ_t(m)→ 0 .s. This implies that lim infn→∞1nKn(m)=lim infn→∞1n[Kn(m)]≥qmθ(s∗)>0. _n→∞ 1nK_n(m)= _n→∞ 1nE[K_n(m)]≥ q_mθ(s^*)>0. This completes the proof. ∎ Now we are ready to establish Theorem 2. Proof of Theorem 2. Fix an arbitrary message m≠m∗m≠ m^* and define the log-posterior ratio Lt(m)=logρt(m∗)ρt(m),t≥1. L_t(m)= _t(m^*) _t(m),\ t≥ 1. By definition, ρ1(m)=P(m)>0 _1(m)=P_m(m)>0 for every m∈ℳm ; hence, L1(m)<∞L_1(m)<∞ for every m. Because Lt(m)L_t(m) is determined by (t−1,t)(u^t-1,s^t), it can be viewed as a random variable. Define the stopping time τm≜inft:ρt(m)=0. _m \t: _t(m)=0\. To establish the desired result, it suffices to show that, almost surely, either (i) τm<∞ _m<∞; or (i) Lt(m)→∞L_t(m)→∞ as t→∞t→∞. Indeed, the posterior update rule in (1) implies that once ρi(m)=0 _i(m)=0, it remains zero for all t≥it≥ i. Thus, under the convention log(x/0)=∞ (x/0)=∞, case (i) also yields Lt(m)→∞L_t(m)→∞. Because ρ1(m)>0 _1(m)>0, case (i) can occur only under the following condition: C1. There exists a tuple (s,a,s′)∈×(s,a,s ) ×A×S such that T(s′∣s,a)=0T(s s,a)=0. We consider the two settings separately: first, we analyze case (i) when Condition C1 holds; we then establish case (i) when Condition C1 does not hold. Suppose that Condition C1 holds. Because t(m)a_t(m) is generated using the uniform common randomness tu_t, see Figure 2 for an illustration, it can take any action in the support of π(⋅|t)π(·|s_t) with positive probability. Consequently, when the process visits state s, there is a positive probability that t(m)=aa_t(m)=a while the transition generated under the true message m∗m^* yields t+1=s′s_t+1=s . Since T(s′|s,a)=0T(s |s,a)=0, the observed transition is impossible under the candidate message m, and the posterior update therefore gives ρt+1(m)=0 _t+1(m)=0. Under the assumption that the Markov chain induced by the reference policy π is recurrent, this elimination event occurs within a finite time almost surely, implying that τm<∞ _m<∞ almost surely. We next show that case (i) is true when Condition C1 does not hold. Define βt(m)=logT(t+1|t(m∗),t)T(t+1|t(m),t),m∈ℳ. _t(m)= T(s_t+1|a_t(m^*),s_t)T(s_t+1|a_t(m),s_t),\ m . Then we have Lt+1(m)=Lt(m)+βt(m). L_t+1(m)=L_t(m)+ _t(m). As a result, Ln(m)=L1(m)+∑t=1n−1βt(m) L_n(m)=L_1(m)+ _t=1^n-1 _t(m) Let t:=σ(t+1,t)G_t:=σ(s^t+1,u^t) denote the sigma-algebra generated by t+1s^t+1 and tu^t. Define the conditional mean dt(m)=[βt|t]. d_t(m)=E[ _t|G_t]. Since t+1∼T(⋅|t,t(m∗))s_t+1 T(·|s_t,a_t(m^*)), dt(m) d_t(m) =∑sT(t+1=s|t,t(m∗))logT(t+1=s|t(m∗),t)T(t+1=s|t(m),t) = _sT(s_t+1=s|s_t,a_t(m^*)) T(s_t+1=s|a_t(m^*),s_t)T(s_t+1=s|a_t(m),s_t) =DKL(T(⋅|t,t(m∗))||T(⋅|t,t(m))) =D_KL (T(·|s_t,a_t(m^*))||T(·|s_t,a_t(m)) ) ≥0. ≥ 0. Now, let φt(m)=βt(m)−dt(m). _t(m)= _t(m)-d_t(m). Then by construction, [φt(m)|t]=0. [ _t(m)|G_t]=0. Then ϕi(m)=∑t=1i−1φt(m). _i(m)= _t=1^i-1 _t(m). is a martingale with respect to the natural filtration. Specifically, ϕ1(m)=0 _1(m)=0. We can decompose Ln(m)L_n(m) as follows: Ln(m)=L1(m)+∑t=1n−1dt(m)+ϕn(m). L_n(m)=L_1(m)+ _t=1^n-1d_t(m)+ _n(m). (5) When Condition C1 does not hold, we have |βt(m)|≤C | _t(m)|≤ C for some positive constant C. It follows that 0≤dt(m)=[βt|t]≤C. 0≤ d_t(m)=E[ _t|G_t]≤ C. Applying the triangle inequality yields |φt(m)|=|βt(m)−dt(m)|≤2C. | _t(m)|=| _t(m)-d_t(m)|≤ 2C. Hence the martingale ϕn(m) _n(m) has bounded increments. The Azuma-Hoeffding inequality then gives that, for any ϵ>0ε>0, P(|ϕn(m)−ϕ1(m)|≥ϵn)≤2exp(−ϵ2n8C2). P (| _n(m)- _1(m)|≥ε n )≤ 2 (- ε^2n8C^2 ). Since ϕ1(m)=0 _1(m)=0 and the RHS tends to zero as n→∞n→∞, we obtain ∑n=1∞P(|ϕn(m)|≥ϵn)<∞. _n=1^∞P (| _n(m)|≥ε n )<∞. Then, by Borel-Cantelli lemma, we know that the event |ϕn(m)|≥ϵn | _n(m)|≥ε n occurs only finitely often almost surely. Since this holds for any ϵ>0ε>0, we have limn→∞|ϕn(m)|n=0, _n→∞ | _n(m)|n=0, almost surely. We next focus on the second term of equation (5). By definition, ∑t=1n−1dt(m) _t=1^n-1d_t(m) =∑t=1n−1DKL(T(⋅|t,t(m∗))||T(⋅|t,tm)) = _t=1^n-1D_KL (T(·|s_t,a_t(m^*))||T(·|s_t,a_tm) ) ≥∑t=1n−1t=s∗,t(m∗)≠t(m)DKL(T(⋅|t,t(m∗))||T(⋅|t,tm)) ≥ _t=1^n-11\s_t=s^*,a_t(m^*)≠a_t(m)\D_KL (T(·|s_t,a_t(m^*))||T(·|s_t,a_tm) ) ≥dmin∑t=1n−1t=s∗,t(m∗)≠t(m), ≥ d_min _t=1^n-11\s_t=s^*,a_t(m^*)≠a_t(m)\, where dmin=mina,a′:a≠a′DKL(T(⋅|s∗,a)||T(⋅|s∗,a′)). d_min= _a,a :a≠ a D_KL (T(·|s^*,a)||T(·|s^*,a ) ). Combining the above arguments yields limn→∞1nLn(m) _n→∞ 1nL_n(m) =limn→∞[L1(m)n+1n∑t=1n−1dt(m)+ϕn(m)n] = _n→∞ [ L_1(m)n+ 1n _t=1^n-1d_t(m)+ _n(m)n ] =limn→∞1n∑t=1n−1dt(m) = _n→∞ 1n _t=1^n-1d_t(m) ≥δm>0. ≥ _m>0. The last line follows from Lemma 1. As a result, almost surely, Ln(m)=logρn(m∗)ρn(m)→∞as n→∞. L_n(m)= _n(m^*) _n(m)→∞ n→∞. Since the above statement holds for all m≠m∗m≠ m^*, we conclude that ∑m≠m∗ρn(m)→a.s.0,ρn(m∗)→a.s.1,as n→∞. _m≠ m^* _n(m) a.s.0, _n(m^*) a.s.1, n→∞. This completes the proof. ∎ Appendix B Experiment Details B.1 Experimental environments This section provides brief descriptions of the experimental environments used to evaluate the proposed PRAM method. Detailed Python implementations of these environments are included in the supplementary material and will be open-sourced after the review process. ReFrozenLake. The Revised FrozenLake (ReFrozenLake) is a variant of FrozenLake in Gymnasium, modified to provide a continuing finite-state MDP suitable for long-horizon communication experiments. The environment retains the original grid layout and slippery transition dynamics, but removes terminal states before reaching the goal. In particular, reaching a hole no longer terminates the episode; instead, the agent incurs a penalty and is randomly transitioned to another valid position in the grid. Reaching the goal yields a positive reward and terminates the trajectory. ConTaxi. The Continuing Taxi (ConTaxi) is a variant of Taxi-v4 in Gymnasium that transforms the original episodic task into a continuing environment. It preserves the original state and action spaces, including the taxi’s location, passenger location, destination, and six available actions. When the taxi successfully drops off a passenger, the episode does not terminate; instead, the taxi remains at the drop-off location and a new passenger origin and destination are sampled uniformly from all valid pairs. The environment therefore supports an uninterrupted sequence of trips while retaining Taxi-v4’s reward structure and optional rainy-mode dynamics. SBM. Stochastic Battery Management (SBM) is a customized finite-state, finite-action energy-management environment designed to model stochastic battery charging and discharging. The state is s=(b,d,p)s=(b,d,p), where b∈0,…,19b∈\0,…,19\ denotes the battery level, d∈−4,…,5d∈\-4,…,5\ denotes the net electricity demand, and p∈1,…,5p∈\1,…,5\ denotes the electricity-price level, resulting in 10001000 states in total. The action space is =−2,−1,0,1,2A=\-2,-1,0,1,2\, corresponding to different charging and discharging rates. The commanded battery action is executed with stochastic perturbation: with probability 0.80.8 it is executed as intended, while with probability 0.10.1 it is shifted by −1-1 or +1+1, respectively, subject to the action and battery-capacity constraints. The net demand and electricity price independently evolve according to nearest-neighbor Markov chains. The overall transition kernel therefore factorizes into the battery, demand, and price transition probabilities. The reward reflects the electricity purchasing cost, revenue from selling excess energy, and battery degradation cost. Let x=b′−bx=b -b denote the realized battery change and g=d+xg=d+x the resulting grid electricity exchange. The instantaneous reward is r=−p[g]++βp[−g]+−λ|x|,r=-p[g]^++β p[-g]^+-λ|x|, where [z]+=maxz,0[z]^+= \z,0\, β=0.5β=0.5 is the selling-price ratio, and λ=0.1λ=0.1 controls the battery degradation penalty. The environment is continuing and contains no terminal states. B.2 Additional experimental results In DPIC, the per-message distribution-preserving requirement is motivated by the need to maintain control performance while embedding watermarks or other information into the agent’s behavior. Table 1 has shown that the empirical action distributions induced by PRAM closely match the corresponding reference policies. Here, we further verify that PRAM indeed preserves the control reward. Specifically, in each of the three environments, we select two or three reference policies and evaluate their average rewards, shown as dashed lines in the figure. For each reference policy, we then evaluate the reward achieved by PRAM when transmitting different messages. As shown in the figure, the rewards under PRAM are nearly identical across messages and closely match those of the corresponding reference policies. (a) ReFrozenLake (b) ConTaxi (c) SBM Figure 6: Control reward of transmitting different messages using PRAM. Appendix C Algorithm Pseudocode The encoding procedure of PRAM at the agent is summarized in Algorithm 1. Algorithm 1 Posterior-matching randomness modulation (PRAM): Encoder 0: Transition kernel T, blocklength n, message m∗∈ℳm^* , message prior distribution P_m 1: Initialization: Let ρ1=P _1=P_m. Observe the initial state s1s_1 2: for t=1t=1 to n do 3: Compute for every m: bt(m)≜P(<m|t,t−1)=∑j<mρt(j)b_t(m) P(m<m|s^t,u^t-1)= _j<m _t(j) 4: Draw a sample of the common random variable t∼Unif[0,1]u_t [0,1] 5: Determine the information point: t=[bt(m∗)+lt(m∗)ρt(m∗)+t]mod1,w_t= [b_t(m^*)+l_t(m^*) _t(m^*)+u_t ] 1, 6: Compute the action at=Ft|t−1(t):=infa∈:Ft|t(a)≥ta_t=F^-1_a_t|s_t(w_t):= \a :F_a_t|s_t(a)≥w_t\ 7: Apply action ata_t and observe the next state st+1s_t+1. Then update the posterior ρt+1(m)=ρt(m)T(st+1|st,at(m))∑jρt(j)T(st+1|st,at(j)),∀m∈ℳ _t+1(m)= _t(m)T(s_t+1|s_t,a_t(m)) _j _t(j)T(s_t+1|s_t,a_t(j)),\ ∀ m 8: end for