acceptodds
Under review as a conference paper at ICLR 2027

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

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.

Primary area:
reinforcement learning
Keywords:
Information embedding, multi-bit policy watermarking, randomness modulation, implicit communication, distribution-preserving, MDP

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_m1VnOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes distribution-preserving implicit communication (DPIC), which embeds information into the random actions of a stochastic policy without changing its action distribution. The authors introduce PRAM, a posterior-matching coding method that uses shared randomness between the agent and an observer. The paper proves a distribution-preservation property and claims asymptotically reliable message recovery. Experiments on three MDP environments demonstrate multi-bit watermarking, trajectory provenance, and robustness to model mismatch.

Critical strengths

Using policy randomness as a communication channel while preserving the original action distribution is an interesting problem. The experiments show that messages can be recovered with high accuracy from relatively short state trajectories.

Critical weaknesses

1. Concerns about the theoretical proof.

I have concerns about the proof of asymptotic reliability in Theorem 2. In Appendix A.2, the proof considers the case where the transition kernel contains zero-probability transitions and argues that an incorrect message will eventually be eliminated. However, the existence of a zero-probability transition does not necessarily imply that it can distinguish two messages or even that the corresponding action is selected by the policy. There also appears to be an issue with the conditional expectation used in the log-likelihood analysis. The conditioning sigma-algebra includes the next observed state, but the conditional expectation is then written as a KL divergence, which normally requires averaging over that state. These steps need clarification or correction, since asymptotic reliability is one of the paper's main theoretical contributions.

2. The experiments lack meaningful baselines.

The experiments mainly demonstrate PRAM under different settings without comparing it against alternative communication or watermarking methods. The authors discuss related work such as Act2Comm and TRACE, but provide no quantitative comparisons. Even if those methods operate under different constraints, simpler shared-randomness encoding schemes or adapted posterior-matching baselines would help establish the benefit of the proposed method. Furthermore, the experiments are limited to three relatively small MDP environments. The paper does not report statistical uncertainty or sufficiently explain the number of trials used to estimate decoding accuracy.

3. The practical watermarking application is not convincing enough.

The proposed approach requires the encoder and decoder to share synchronized randomness and maintain a posterior over all possible messages. Since the message space contains 2B2^B candidates, the computational cost grows exponentially with the number of embedded bits. More importantly, the watermark is embedded during policy execution rather than in the policy parameters. It is unclear how this protects policy ownership if an attacker copies the original policy but does not use the watermarking mechanism. The paper also does not evaluate watermark robustness against trajectory modifications, observation noise, or deliberate removal attempts. These experiments are important for demonstrating practical usefulness.

Questions for authors
  1. Can the authors clarify the proof of Theorem 2? In particular, why does the existence of a zero-probability transition guarantee message elimination? Is the conditional expectation in Appendix A.2 defined using the correct filtration?

  2. Can the authors provide stronger baselines? How does PRAM compare with simpler shared-randomness coding schemes or existing communication methods under comparable assumptions?

  3. How does the method scale to longer messages? What are the computational and shared-randomness costs for practical watermark identifiers, such as 32 or 64 bits?

  4. How does this protect policy ownership? If an attacker copies the policy without the watermarking code, can the owner still verify ownership? How robust is the watermark to trajectory manipulation or noisy observations?

4 comments
AuthorsOpenReview ↗

Part 1: Proof correction

We thank the reviewer for the valuable comments.

1. Response to W1 and Q1

Thank you for pointing out the gap in the original proof of Theorem 2. We have corrected the proof in the updated manuscript. We now briefly explain the correction.

Our previous proof focused on the log-posterior ratio Lt=log⁡ρt(m∗)ρt(m)L_t=\log\frac{\rho_t(m^*)}{\rho_t(m)} and sought to establish that Lt→∞L_t\to\infty. Condition C1 was introduced to handle finite-time elimination, where ρt(m)=0\rho_t(m)=0. As the reviewer and another reviewer both correctly pointed out, however, C1 does not guarantee that the action pair required for elimination occurs. We have therefore replaced this argument entirely.

The revised proof considers the square-root likelihood ratio

=\sqrt{\frac{P(s^t,u^{t-1}\mid m)} {P(s^t,u^{t-1}\mid m^*)}},$$ where $R_t(m)$ is already defined and analyzed in the proof of Lemma 1. By Bayes’ rule, $$\rho_t(m^\ast)= \frac{P_m(m^\ast)} {P_m(m^\ast)+\sum_{m\ne m^\ast}P_m(m)R_t(m)},$$ so it suffices to show that $L_t(m)\to0$ almost surely for every $m\ne m^*$. We show that $L_t(m)$ is a nonnegative supermartingale and therefore converges almost surely. Assumption 2, together with the repeated occurrence of distinct candidate actions established by the revised Lemma 1, then implies that its limit must be zero. Please refer to the updated manuscript for details. Unlike the log-posterior ratio, the square-root likelihood ratio remains finite when the candidate likelihood vanishes: it simply becomes zero. **The revised argument therefore handles both finite-time elimination and asymptotic discrimination without requiring C1 or a separate elimination argument**. The issue related to the conditional expectation is also addressed accordingly in the new proof. We thank the reviewer again for pointing out these issues.
AuthorsOpenReview ↗

Part 2: No existing method is directly applicable to our problem

2. Response to W2 and Q2

To the best of our knowledge, no existing method is directly applicable to the problem (i.e., DPIC) studied in our paper. In the Related Work section, we discussed TRACE, a watermarking method for LLM-agent trajectories, and explained why it is not directly applicable. Although multi-bit LLM watermarking also embeds recoverable information into generated outputs, DPIC introduces an additional challenge: communication through environment dynamics when the decoder cannot observe the encoder’s actions.

Specifically, in LLM text watermarking, the decoder directly observes the encoder’s output sns^n. In DPIC, the encoder selects actions ana^n, whereas the decoder observes only the resulting states sn+1s^{n+1}, generated through the transition kernel T(st+1∣st,at)T(s_{t+1}\mid s_t,a_t). The MDP therefore acts as a potentially noisy communication channel. Recovering the message requires coding that accounts for information lost through these transitions while satisfying the distribution-preservation constraint. This channel-coding challenge is absent from the LLM text-watermarking formulation. As a result, if TRACE were used to select the actions ana^n in DPIC, its detector could not be directly applied to the observed states sn+1s^{n+1}, which need not uniquely determine those actions. Therefore, TRACE cannot serve as a baseline in our experiments.

Another related work discussed in our paper is Act2Comm, a method for implicit communication in MDPs. Act2Comm is not a valid baseline under the DPIC constraints because it does not enforce per-message distribution preservation. Like conventional feedback communication schemes, it targets an input distribution averaged over messages. DPIC, however, requires the action distribution to match the reference policy for every message in every state. This constraint is motivated by applications in which the message remains fixed throughout an episode, making it necessary to preserve control performance for each message individually.

We implemented Act2Comm in the ReFrozenLake environment and obtained its induced policy for each message. We then computed the divergence between each message-conditioned policy and the reference policy. The results are reported in the table below.

Table: Policy divergence under PRAM and Act2Comm.

m
Reference policyMethod01234567
π1\pi_1PRAM0.0120.0120.0100.0110.0110.0100.0100.009
π1\pi_1Act2Comm0.2270.2230.2240.2240.2240.2240.2300.230
π2\pi_2PRAM0.0150.0110.0100.0100.0110.0110.0120.011
π2\pi_2Act2Comm0.2870.2830.2920.2920.2840.2890.2930.294

As shown in the table, PRAM achieves very small divergence from the reference policy for all message-conditioned policies, whereas Act2Comm’s divergence is approximately 20 times higher. Because Act2Comm does not satisfy the distribution-preservation constraint, a direct comparison of communication performance would not assess the methods under the same requirements. Moreover, Act2Comm does not scale well to MDPs with large state spaces, which prevented us from evaluating it in the other two environments.

Nevertheless, we constructed a baseline by removing the encoder’s posterior updates from PRAM. In this variant, the encoder uses fixed message points without adapting them to state feedback. This ablation isolates the contribution of feedback adaptation through posterior updates. For brevity, we report only the ConTaxi results in the table below; results for the other two environments are provided in the appendix of the updated manuscript.

Table: Decoding accuracy versus blocklength in ConTaxi. nn denotes blocklength

n
BitsMethod102030405060708090100
4PRAM0.6570.9220.9830.9970.9991.0001.0001.0001.0001.000
4Baseline0.4300.6750.8210.9100.9510.9810.9900.9940.9960.998
6PRAM0.4160.7880.9390.9850.9970.9991.0001.0001.0001.000
6Baseline0.1750.3350.4860.6110.7020.7830.8330.8740.8960.930
8PRAM0.2270.6160.8570.9530.9880.9971.0001.0001.0001.000
8Baseline0.0570.1190.1880.2400.3130.3590.4160.4750.4990.537
10PRAM0.1140.4370.7290.9070.9630.9890.9940.9991.0001.000
10Baseline0.0180.0370.0630.0860.1110.1300.1530.1800.2000.219

In our experiments, decoding accuracy is estimated from 4,000 trials. We have clarified this in the updated manuscript.

AuthorsOpenReview ↗

Part 3: Watermarking application and additional experiments on long bit streams

This part addresses the reviewer's concern about the policy watermarking application and scalability to long bit streams.

3. Response to W3 and Q4

We agree that our original use of “policy watermarking” was too broad and that the distinction between policy ownership verification and trajectory watermarking should be made explicit. PRAM embeds information through action selection during execution, rather than embedding a persistent signature in the reference policy parameters. Consequently, an attacker who copies the reference policy and executes it with an independent sampler can bypass the watermark. We will revise the terminology and clarify this limitation.

Nevertheless, PRAM can still support IP protection in specific scenarios. For example, it can help trace unauthorized use of a remotely hosted controller. In this setting, the provider retains the proprietary policy and supplies actions in response to a client’s state reports. By embedding a client- or session-specific identifier through PRAM, the provider enables an authorized monitor to associate an observed trajectory with the service session that supplied its actions. For example, an unauthorized agent accessing the controller through another client’s credentials can produce trajectories carrying that client’s identifier. Combined with authorization records, this association can help identify misuse of the controller service.

More broadly, PRAM provides a mechanism for embedding information in an agent’s behavior while preserving the prescribed action distribution. Beyond tracing controller-service use, potential applications include labeling simulation rollouts, associating robot trajectories with deployment sessions, and communicating auxiliary information to an observer through the environment. We will revise the application discussion to distinguish these uses from policy ownership verification and to state their assumptions explicitly.

4. Response to Q3

We acknowledge the reviewer’s concern about scalability to long bit streams. PRAM requires updating the posterior distribution over messages at each time step. As the message length increases, the message space grows exponentially, making these updates costly in both computation and storage. However, this does not prevent PRAM from transmitting long bit streams: we can partition the stream into short blocks (e.g., 8 bits each) and transmit them sequentially, keeping the cost of each posterior update fixed regardless of the total stream length. We have implemented this approach and tested it in all three environments. The results in the table below demonstrate its performance in the SBM environment; results for the other two environments are provided in the updated manuscript.

Table: Whole-message decoding accuracy in SBM using sequential 8-bit blocks. Each point uses 2,000 trials. A message is correct only if all blocks are decoded correctly. Here, nn denotes the blocklength per 8-bit block.

32 bits (4 blocks)64 bits (8 blocks)
nTotal blocklengthAccuracyTotal blocklengthAccuracy
10400.1905800.0470
20800.61451600.3665
301200.83452400.6980
401600.94803200.8650
502000.98004000.9465
602400.99254800.9835
702800.99855600.9965
803200.99956400.9975
903601.00007201.0000
1004001.00008001.0000

Thank you for the detailed rebuttal and additional experiments. I appreciate the authors' efforts in addressing my concerns, especially the revised theoretical proof and additional baseline comparisons.

However, I still have some concerns about the correctness of the revised proof, which is a central contribution of the paper. While the new experiments demonstrate the benefit of posterior updates, the evaluation is still limited to relatively small environments. I also remain concerned about the practical watermarking application, particularly its robustness against watermark removal and its ability to protect policy ownership.

Overall, I think the rebuttal addresses some of my concerns, but the main limitations remain. I will maintain my original rating and leave the final assessment to the AC.

Reviewer_SHk7OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes posterior-matching randomness modulation (PRAM), a method for embedding a small message in an agent’s behavior while preserving the action probabilities of an existing stochastic policy for every message, after averaging over shared randomness. The agent and decoder share random values, which PRAM uses to map message-dependent positions into actions; the decoder then updates its beliefs about the message by observing the resulting state transitions. These updated beliefs guide subsequent encoding. The paper establishes an elegant distribution-preservation guarantee, claims eventual reliable decoding of a fixed payload, and demonstrates the method in three finite environments for policy watermarking and trajectory provenance.

Critical strengths
  1. The problem is well motivated. Embedding information while preserving an existing policy’s behavior is a useful objective for attribution and metadata transmission without sacrificing expected control performance.
  2. Clean preservation guarantee. The shared uniform shift provides a simple and convincing argument that the prescribed action probabilities are preserved for each message under fresh independent shared randomness.
  3. Meaningful observation setting. Decoding from states alone addresses the challenge of recovering information through the environment’s potentially noisy response to actions.
Critical weaknesses
  1. The proof of Theorem 2 has gaps. The proof of Theorem 2 incorrectly assumes that the existence of a zero transition probability guarantees finite-time elimination of an incorrect message. Different actions can share the same impossible transitions while assigning positive probability to every observable outcome, so no observation needs to eliminate a candidate message completely. The proof also conditions its expected information gain on information that already includes the observed next state, and Lemma 1 states its frequency claim using a single indicator instead of a cumulative count.

  2. Insufficient positioning against secure steganography, distortion-free watermarking, and randomized posterior matching. The novelty discussion should distinguish PRAM more clearly from established methods for embedding information through shared-key-controlled sampling. Meteor [1] already encodes messages through sampling randomness, while Discop [2] uses message-dependent cyclic shifts of shared random draws, which is particularly close to the predecessor of PRAM’s sampling mechanism. Exact per-message distribution preservation also has an established interpretation in perfectly secure steganography, including coupling-based constructions. Furthermore, Kuditipudi et al. [3] use shared-key-driven inverse-transform sampling for distortion-free watermarking, and Christ et al. [4] develop closely related undetectable watermarking constructions. These connections make the broad randomness-modulation principle insufficient to establish novelty.

  3. The experiments do not establish the benefit of posterior adaptation. The experiments lack of baseline and do not isolate the advantage of updating message positions according to the decoder’s beliefs. A direct comparison would use fixed message positions, the same shared random shifts, and the same Bayesian decoder, which also preserves the action distribution. Furthermore, the asymptotic theorem concerns eventual recovery of a fixed payload, so it does not establish an advantage in transmission speed or a positive communication rate as payload size grows.

  4. The model-mismatch results are difficult to interpret. The paper does not adequately specify how transition models are estimated, how much training data is used, or how zero probabilities are handled. An estimated zero can permanently eliminate the correct message, making smoothing and support assumptions consequential. Moreover, a large overall transition-model error need not imply a large error in distinguishing actions: if the estimated model shares SBM’s factorized structure, positive action-independent factors cancel from the Bayesian update. The reported total-variation discrepancies therefore do not by themselves establish robustness to the model errors that matter most for decoding.

[1] G. Kaptchuk, T. M. Jois, M. Green, and A. D. Rubin, “Meteor: Cryptographically Secure Steganography for Realistic Distributions,” Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, Nov. 2021, doi: 10.1145/3460120.3484550.

[2] J. Ding, K. Chen, Y. Wang, N. Zhao, W. Zhang and N. Yu, "Discop: Provably Secure Steganography in Practice Based on "Distribution Copies"," 2023 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA, 2023, pp. 2238-2255, doi: 10.1109/SP46215.2023.10179287.

[3] R. Kuditipudi, J. Thickstun, T. Hashimoto, and P. Liang, "Robust distortion-free watermarks for language models," Trans. Mach. Learn. Res., 2024.

[4] Christ, M., Gunn, S., & Zamir, O. (2024, June). Undetectable watermarks for language models. In The Thirty Seventh Annual Conference on Learning Theory (pp. 1125-1139). PMLR.

Questions for authors
  1. Can you provide a corrected reliability proof that handles common zeros and differing transition supports, conditions on information available before the next transition, and rigorously establishes sufficiently frequent informative observations?
  2. How does PRAM differ from existing technically, and which new analysis or measurable benefit arises specifically from state-only observations, noisy MDP dynamics, and posterior-matching feedback?
  3. At matched payload, policy, transition model, and shared randomness, how many transitions do PRAM and a fixed-position baseline require to reach the same decoding accuracy?
  4. How are the estimated models trained and smoothed, and does decoding remain robust when model errors specifically distort the action-dependent probabilities used to distinguish messages?
5 comments
AuthorsOpenReview ↗

Part 1: Proof Correction and Experimental Evaluation of the Suggested Baseline

We thank the reviewer for the valuable comments. This part addresses concerns related to W1 and W3

1. Response to W1 and Q1

Thank you for pointing out the gap in the original proof of Theorem 2. We have corrected the proof in the updated manuscript. We now briefly explain the correction, which only involves modifying several lines. The key step of the proof is to establish that, almost surely, either (i) τm<∞\tau_m<\infty or (ii) Lt(m)→∞L_t(m)\to\infty as t→∞t\to\infty. Here, τm\tau_m denotes the first time tt at which ρt(m)=0\rho_t(m)=0, meaning that a message candidate mm can be eliminated. Our original argument introduced a condition C1 and asserted that τm<∞\tau_m<\infty when C1 holds, whereas Lt(m)→∞L_t(m)\to\infty when C1 does not hold.

The error in our original proof comes from the formulation of C1. As the reviewer correctly observed, the original condition C1 does not imply τm<∞\tau_m<\infty. We have therefore revised condition C1 as follows:

C1: There exists a tuple $ (s,a,a',s')\in\mathcal{S}\times\mathcal{A}\times\mathcal{A}\times\mathcal{S}$ such that T(s′∣s,a)=0T(s'\mid s,a)=0 and T(s′∣s,a′)>0T(s'\mid s,a')>0.

The revised C1 provides the required mechanism for eliminating a candidate message. Specifically, when the process visits state ss, the random cyclic shift gives positive probability to the event at(m)=aa_t(m)=a and at(m∗)=a′a_t(m^{\ast})=a^{\prime}. Since T(s′∣s,a′)>0T(s'\mid s,a')>0, the transition under the true message m∗m^{\ast} can then yield st+1=s′s_{t+1}=s'. This observed transition is impossible under the candidate message mm, because T(s′∣s,a)=0T(s'\mid s,a)=0. Consequently, the posterior update gives ρt+1(m)=0\rho_{t+1}(m)=0, eliminating mm.

When C1 does not hold, the argument establishing Lt(m)→∞L_t(m)\to\infty relies on the uniform bound ∣βt(m)∣≤C,|\beta_t(m)|\le C, where

\frac{T(s_{t+1} | a_t(m^{\ast}),s_t)} {T(s_{t+1} | a_t(m),s_t)} \right).$$ **The revised condition preserves this bound**: when C1 fails, for each state pair $(s,s')$, either $T(s'\mid s,a)>0$ for every action $a$, or $T(s'\mid s,a)=0$ for every action $a$. Thus, every realized transition has positive likelihood under both the true and candidate messages. Together with the recurrence assumption, this implies the desired result. In summary, the correction replaces C1 with the revised condition above; the remaining proof arguments are essentially unchanged. As also pointed out by the reviewer, **there is a typo in the original Lemma 1**. We defined $K_t(m)$ as the indicator of the event $s_t=s^{\ast}$, $a_t(m^{\ast})\neq a_t(m)$ and intended to state that $$\liminf_{n\to\infty}\frac{1}{n}\sum_{t=1}^{n}K_t(m)\ge\delta_m.$$ However, the summation was inadvertently omitted in the original manuscript, resulting in the incorrect expression $$\liminf_{n\to\infty}\frac{1}{n}K_n(m)\ge\delta_m.$$ We have corrected this error and a similar typographical error in equation (5). ## 2. Response to W3 and Q3 We thank the reviewer for this suggestion. **We have implemented the baseline with fixed message points**, as suggested by the reviewer, and compared it with PRAM in different environments. For brevity, we present only the SBM results in the table below. Comparisons in the other two environments show the same trend and are provided in Appendix B of the updated manuscript. As shown in the table, for 4-bit messages, the baseline achieves the same decoding accuracy as PRAM but requires a longer blocklength. As the message length increases, however, its accuracy remains low even at large blocklengths, despite improving with blocklength. For example, for 10-bit messages, the baseline achieves approximately 0.25 accuracy at a blocklength of 100, whereas PRAM achieves 0.99 accuracy at a blocklength of only 50. **These results demonstrate the benefit of adapting to feedback through posterior updates, a key component of PRAM’s feedback coding mechanism.** **Table: Decoding accuracy versus blocklength in SBM.** $n$ denotes blocklength | | | | | | | |n | | | | | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | **Bits** | **Method** | **10** | **20** | **30** | **40** | **50** | **60** | **70** | **80** | **90** | **100** | | 4 | **PRAM** | 0.843 | 0.964 | 0.990 | 0.997 | 0.999 | 0.999 | 1.000 | 1.000 | 1.000 | 1.000 | | 4 | Baseline | 0.728 | 0.912 | 0.970 | 0.991 | 0.997 | 0.999 | 0.999 | 1.000 | 1.000 | 1.000 | | 6 | **PRAM** | 0.720 | 0.921 | 0.976 | 0.992 | 0.997 | 0.999 | 1.000 | 1.000 | 1.000 | 1.000 | | 6 | Baseline | 0.332 | 0.563 | 0.712 | 0.812 | 0.876 | 0.916 | 0.947 | 0.961 | 0.972 | 0.982 | | 8 | **PRAM** | 0.577 | 0.866 | 0.955 | 0.984 | 0.995 | 0.998 | 1.000 | 1.000 | 1.000 | 1.000 | | 8 | Baseline | 0.101 | 0.200 | 0.286 | 0.360 | 0.423 | 0.484 | 0.549 | 0.593 | 0.634 | **0.680** | | 10 | **PRAM** | 0.436 | 0.791 | 0.925 | 0.972 | **0.990** | 0.997 | 0.999 | 1.000 | 1.000 | 1.000 | | 10 | Baseline | 0.027 | 0.055 | 0.082 | 0.110 | 0.136 | 0.158 | 0.187 | 0.212 | 0.235 | **0.251** |
AuthorsOpenReview ↗

Part 2: Novelty Relative to Existing Methods: They Do Not Apply to DPIC

3. Response to W2 and Q2

We thank the reviewer for highlighting these related works. Below, we compare steganography and distortion-free watermarking with DPIC to explain why our setting is more general and challenging, why existing methods do not directly apply, and what distinguishes PRAM. We begin with their mathematical formulations:

  • Steganography [1,2]: Given a message set M\mathcal{M} and a covertext channel distribution PP over the covertext space S∗\mathcal{S}^{\ast}, a stegosystem consists of a key generator, an encoder f:M→S∗f:\mathcal{M}\to\mathcal{S}^{\ast} and a decoder g:S∗→Mg:\mathcal{S}^{\ast}\to\mathcal{M}, with auxiliary inputs (e.g., shared keys and message history) omitted for simplicity. The encoder transforms a message into a stegotext sn∈S∗s^n\in\mathcal{S}^{\ast}, from which the decoder reconstructs the message.

  • Distortion-free watermarking: Watermarking methods are commonly classified as zero-bit or multi-bit. Zero-bit watermarking enables a detector to determine whether a text is watermarked, without conveying an additional recoverable message, and is therefore less directly relevant to our problem. By contrast, multi-bit watermarking embeds a recoverable message into the text. In the distortion-free setting, this can be viewed as a form of linguistic steganography.

It therefore suffices to clarify the distinction between steganography and DPIC.

  • DPIC: Given a message set M\mathcal{M} and an MDP with transition kernel TT and reference policy π\pi, a DPIC system consists of an encoder and decoder. The encoder comprises a sequence of mappings $ E_{t}:\mathcal{M}\times\mathcal{S}^{t}\to\mathcal{A} $ that encode a message into an action sequence ana^n, which induces a state sequence sn+1s^{n+1} through the MDP dynamics. The decoder $ \mathcal{D}:\mathcal{S}^{n+1}\to\mathcal{M} $ reconstructs the message from the observed state sequence. Let μ(a∣s,m)\mu(a\mid s,m) denote the probability of selecting action aa in state ss when transmitting message mm. The per-message distribution-preservation constraint requires $ D_{\mathrm{KL}}\left(\pi(\cdot\mid s),|,\mu(\cdot\mid s,m)\right)=0 $ for every state ss and message mm.

Although both problems concern implicit communication, there is a key distinction in what the decoder observes. In steganography, the encoder directly produces the stegotext sns^n observed by the decoder. In DPIC, the encoder produces actions ana^n, whereas the decoder observes only the resulting states sn+1s^{n+1}, generated through the transition kernel T(st+1∣st,at)T(s_{t+1}\mid s_t,a_t). The MDP therefore acts as a communication channel between the encoder and decoder. Recovering the message requires coding that accounts for information lost through these potentially noisy transitions, while satisfying the distribution-preservation constraint. This channel-coding challenge is absent from the steganography formulations considered in [1] and [2]; consequently, these methods do not directly address the general DPIC setting.

We have revised the related work section to discuss relevant studies on steganography and watermarking and clarify their distinctions from DPIC. Here, we briefly address the four papers highlighted by the reviewer. Works [3] and [4] study zero-bit watermarking, which concerns watermark detection rather than message recovery and is therefore less directly relevant to DPIC. We have cited these works without an extended discussion. Works [1] and [2] study secure steganography, but their methods are not directly applicable to DPIC for the reasons discussed above.

Specifically, Discop [2] encodes symbols by sampling from distribution copies constructed through cyclic shifts of sampling intervals. Its decoder directly observes the generated text and uses shared sampling information to recover the embedded symbol. This decoding mechanism does not directly extend to general DPIC, where the decoder observes only the state trajectory: the system dynamics can obscure the information embedded in the encoder’s sampled actions. PRAM, by comparison, is a feedback coding scheme for communication over noisy channels. Its communication mechanism relies on posterior matching, while the random cyclic shift serves primarily to preserve the action distribution. Thus, despite both using cyclic shifts, the two methods rely on different coding mechanisms.

Finally, the key novelty of PRAM relative to classical posterior matching lies in its distribution-preservation guarantee. Classical posterior matching is designed for feedback communication and matches the target channel-input distribution after averaging over messages; it does not generally guarantee distribution preservation for each message individually. PRAM combines the posterior-matching mechanism with a shared random variable and a random cyclic shift to preserve the reference action distribution for every message, thereby satisfying the additional constraint imposed by DPIC.

AuthorsOpenReview ↗

Part 3: Details of model mismatch experiments

4. Response to W4 and Q4

We have added a subsection in Appendix B detailing the model mismatch experiments. We execute the reference policy π\pi to collect trajectories from the agent’s interactions with the environment. After each episode, we extract the transition tuples (s,a,s′)(s,a,s^{\prime}), consisting of the current state, action, and next state, and add them to a dataset D\mathcal{D}. Let κ(s,a,s′)\kappa(s,a,s^{\prime}) denote the number of occurrences of transition (s,a,s′)(s,a,s^{\prime}) in D\mathcal{D}, and let κ(s,a)=∑s′κ(s,a,s′)\kappa(s,a)=\sum_{s^{\prime}}\kappa(s,a,s^{\prime}) denote the total number of transitions associated with state-action pair (s,a)(s,a). We then estimate the transition kernel as

\frac{\kappa(s,a,s^{\prime})+\kappa_0} {\kappa(s,a)+\kappa_0|S|},$$ where $\kappa_0$ is a smoothing constant, set to $1$ in our experiments. In Figure 5, each curve $l$ corresponds to a transition kernel $\hat{T}$ estimated from a dataset $\mathcal{D}_l$. We quantify the estimation error using the previously defined TV distance between $T$ and $\hat{T}$, which generally decreases as the dataset grows. **The following tables report the number of data-collection episodes and the corresponding estimation errors**. The number of episodes varies across environments because they have different state spaces. SBM has the largest state space (1,000 states) and therefore requires more episodes to obtain a good estimate. **ReFrozenLake:** Each episode contains approximately 100 steps. | Number of episodes | 20 | 50 | 100 | 200 | 500 | | --- | --- | --- | --- | --- | --- | | TV distance | 0.64 | 0.47 | 0.32 | 0.21 | 0.10 | **ConTaxi:** Each episode contains 200 steps. | Number of episodes | 200 | 1000 | 3000 | 10000 | | --- | --- | --- | --- | --- | | TV distance | 0.73 | 0.44 | 0.26 | 0.13 | **SBM:** Each episode contains 130 steps. | Number of episodes | 1000 | 5000 | 10000 | 50000 | | --- | --- | --- | --- | --- | | TV distance | 0.83 | 0.59 | 0.47 | 0.20 | We use no additional mechanism to handle zero transition probabilities. **The smoothing term ensures that every transition receives a strictly positive estimated probability with finite data. This prevents candidate messages from being erroneously eliminated because of an estimated zero**. Other estimation errors may slow the accumulation of evidence without necessarily preventing correct decoding. For example, assigning positive probability to an impossible transition may prevent the decoder from eliminating an incorrect candidate with certainty based on a single observation. Nevertheless, the decoder can still accumulate evidence to identify the correct message, provided that the resulting likelihood updates favor it over incorrect candidates in the long run. **We understand the reviewer’s concern to relate partly to the role of transitions that immediately eliminate incorrect candidates in the proof of Theorem 2**. The proof considers two cases, depending on whether condition C1 holds. When C1 holds, certain transitions can immediately eliminate an incorrect candidate upon observation. When C1 does not hold, such transitions are unavailable, but the second part of the proof establishes that the decoder can nevertheless identify the correct message through gradual evidence accumulation. Thus, **immediate elimination is not essential for correct decoding under the assumed model**. Overall, these experiments assess PRAM’s robustness across a range of model mismatch settings. PRAM performs robustly in all tested settings, but these empirical results do not establish robustness in every possible scenario, nor do we intend to make such a claim.
Reviewer_pn4WOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The authors claim to introduce the use of stochastic policy randomness as a covertext distribution for hiding information. They introduce a steganographic framework, PRAM, that can encode information into state trajectories and decode them while maintaining the distribution over actions given a fixed stochastic policy. The authors conduct evaluation of their method on a number of toy tasks.

Critical strengths

The paper is well-written and the setting studied is interesting. The theoretical analysis of communication under state-only observations may be potentially valuable.

Critical weaknesses

The paper has several fatal weaknesses that have significant implications for its stated novelty, as well as its guarantees.

  • Most importantly, the authors do not cite nor compare to arguably the most centrally-related literature: neural linguistic steganography [1]. In particular, work on perfectly secure steganography [2] already demonstrates perfect security and near-optimal efficiency when encoding into arbitrary autoregressive stochastic policies.

  • Secondly, how do your security guarantees compare to existing notions of steganographic security?

As a result, this paper cannot be accepted without the following:

a) a thorough theoretical and empirical comparison to the existing literature, in particular [2], and a resultant clarification of the degree of novelty of the authors' contribution, b) including a thorough theoretical and empirical comparative analysis of security and efficiency properties.

My understanding is that the novelty of the authors' introduced method then seems to lie in blinding the actions. In this case, a relevant baseline is applying iMEC [2] or similar to a state-transition distribution.

[1] Ziegler et al, Neural Linguistic Steganography, EMNLP-IJCNLP 2019, https://aclanthology.org/D19-1115/ [2] Schroeder de Witt and Sokota et al, Perfectly Secure Steganography Using Minimum Entropy Coupling, ICLR 2023

Questions for authors
  1. What is the relationship to existing steganographic methods?
  2. How do your claimed security properties relate to existing notions of steganographic security?
  3. What exactly does PRAM offer over existing steganographic methods (e.g. iMEC [2]) and is there any advantage in theoretical guarantees or communication efficiency?

RAISED score from 1 to 2 post-rebuttal

4 comments
AuthorsOpenReview ↗

Part 1: Our work addresses a more general and more challenging problem than linguistic steganography

We thank the reviewer for their comments and for bringing these works to our attention. After carefully studying these two papers and the broader literature, we would like to emphasize that our work addresses a more general and more challenging problem than linguistic steganography. Existing results therefore do not directly apply to our setting or diminish the novelty of our contribution. Below, we explain this distinction and its implications for our method’s novelty and efficiency.

1. Problem distinction: reverse source coding versus joint source-channel coding

Let us first briefly review the mathematical model of generation-based linguistic steganography studied in [1] and [2]:

  • Linguistic steganography: Given a message set M\mathcal{M} and a language model with output distribution PP over the text space S∗\mathcal{S}^{\ast}, a stegosystem consists of an encoder f:M→S∗f:\mathcal{M}\to\mathcal{S}^{\ast} and a decoder g:S∗→Mg:\mathcal{S}^{\ast}\to\mathcal{M}, with auxiliary inputs (e.g., shared keys) omitted for simplicity. The encoder transforms a message into a stegotext sn∈S∗s^n\in\mathcal{S}^{\ast}, from which the decoder reconstructs the message. Let QQ denote the induced stegotext distribution. Security of a stegosystem is measured by the discrepancy between PP and QQ, for example, DKL(P∥Q)D_{\mathrm{KL}}(P\|Q), with perfect security corresponding to Q=PQ=P.

In [1], the message is assumed to be uniformly distributed. Linguistic steganography therefore admits a reverse source coding interpretation: it converts uniform bits into text following a prescribed distribution QQ. Accordingly, [1] applies arithmetic coding in reverse. In [2], the plaintext need not be uniform, but is first transformed into uniformly distributed ciphertext using standard methods. Hence, [2] addresses essentially the same underlying problem as [1], but from the perspective of minimum entropy coupling.

Our problem, termed distribution-preserving implicit communication (DPIC), is essentially a joint source-channel coding problem with an additional distribution-preservation constraint. Specifically:

  • DPIC: Given a message set M\mathcal{M} and an MDP with transition kernel TT and reference policy π\pi, a DPIC system consists of an encoder and decoder. The encoder comprises a sequence of mappings Et:M×St→AE_t : \mathcal{M} \times \mathcal{S}^{t} \to \mathcal{A} that encode a message into an action sequence ana^n, which induces a state sequence sn+1s^{n+1} through the MDP dynamics. The decoder D:Sn+1→M\mathcal{D}:\mathcal{S}^{n+1}\to\mathcal{M} reconstructs the message from the observed state sequence. Let μ(a∣s,m)\mu(a\mid s,m) denote the probability of selecting action aa in state ss when transmitting message mm. The per-message distribution-preservation constraint requires DKL(π(⋅∣s)∥μ(⋅∣s,m))=0D_{\mathrm{KL}}(\pi(\cdot\mid s)\|\mu(\cdot\mid s,m))=0 for every state ss and message mm.

Although both problems concern communicating implicitly/covertly, there is a key distinction in what the decoder observes. In linguistic steganography, the encoder directly produces the stegotext sns^n observed by the decoder. In DPIC, the encoder produces actions ana^n, whereas the decoder observes only the resulting states sn+1s^{n+1}, generated through the transition kernel T(st+1∣st,at)T(s_{t+1}\mid s_t,a_t). The MDP therefore acts as a communication channel between the encoder and decoder. Recovering the message requires coding that accounts for information lost through these potentially noisy transitions, while satisfying the distribution-preservation constraint. This channel-coding challenge is absent from the linguistic steganography formulations considered in [1] and [2].

DPIC can thus be viewed as a generalization of linguistic steganography, recovering the latter when the channel is noiseless (i.e., when the next state uniquely identifies the action given the current state) and the distribution-preservation constraints coincide. Our method therefore applies to this special case, whereas existing linguistic steganography methods do not directly address the general DPIC setting.

2. Constraint distinction: perfect security versus distribution preservation

DPIC does not explicitly require concealing the existence of communication, since its target applications, such as watermarking and trajectory provenance, do not necessarily require this property. Instead, our constraint is motivated by preserving the MDP’s control performance. Specifically, we require π(a∣s)=μ(a∣s,m)\pi(a\mid s)=\mu(a\mid s,m) for every state ss and message mm, so that the action distribution matches the reference policy separately for each message. By contrast, perfect security in linguistic steganography requires the induced stegotext distribution to match the reference distribution, i.e., P(sn)=Q(sn)P(s^n)=Q(s^n). For general MDPs, our distribution-preservation condition is stronger than preserving the distribution of state sequences (i.e., perfect security).

AuthorsOpenReview ↗

Part 2: Existing methods are not applicable to our problem

We next explain why existing methods are not applicable to our problem.

The distinction discussed in part 1 prevents a direct application of existing linguistic steganography methods to DPIC. Consider iMEC [2], which constructs couplings to maximize the mutual information between the message mm and the generated covertext sns^n. Its sequential procedure specifies conditional distributions P(st∣m,st−1)P(s_t\mid m,s^{t-1}), from which the encoder can directly sample text.

However, iMEC cannot be directly applied to DPIC. In principle, we still seek to maximize the mutual information I(m;sn+1)I(m;s^{n+1}), so a minimum entropy coupling between messages and state trajectories is desirable. Such a coupling, however, does not provide an executable encoding policy: iMEC specifies a conditional state distribution P(st+1∣m,st)P(s_{t+1}\mid m,s^t), whereas the encoder requires an action distribution P(at∣m,st)P(a_t\mid m,s^t) from which to sample an action. The environment then determines the next state through its transition kernel. Crucially, a state distribution prescribed by iMEC need not be realizable by any action policy, let alone one satisfying our distribution-preservation constraint. Therefore, applying iMEC to state-transition distributions does not directly provide a valid DPIC baseline.

In summary, we agree that clarifying the relationship between DPIC and linguistic steganography will help delineate our contributions. We have revised the manuscript to explicitly discuss the differences in problem formulations, constraints, and the applicability of existing methods.

Thanks for the reply. I am increasing my rating from 1 to 2 in response. The reason for my increase is that the authors have clarified how their state-only decoding through noisy dynamics distinguishes DPIC from settings in [1,2]. However, I still see three gaps keeping the paper from being accepted: iMEC can serve as a baseline when applied to the action distribution with the posterior updated from observed states - iMEC is agnostic to where the covertext distribution comes from as long as it is with discrete support and in autoregressive form. Your security guarantees only seem to coincide with perfect security if there is a shared OTP, and even then, it is never a stronger guarantee than perfect security - none of this is discussed in the paper. I would also like to see an independent verification of Theorem 2 for which a further peer review process would be mandatory.

AuthorsOpenReview ↗

We respectfully disagree that these three points constitute unresolved gaps

We thank the reviewer for the follow-up. We respectfully disagree that these three points constitute unresolved gaps and offer the following clarifications.

1. Applicability of the suggested iMEC baseline

Our understanding is that iMEC seeks to maximize the mutual information between the message and the decoder's observations. In DPIC, the relevant objective is therefore I(M;Sn+1)I(M;S^{n+1}). The reviewer's suggested adaptation, as we understand it, instead couples messages with actions, targeting max⁡I(M;An)\max I(M;A^n). However, information encoded in actions may be lost through the MDP dynamics, which act as channel noise. Maximizing I(M;An)I(M;A^n) therefore does not generally maximize I(M;Sn+1)I(M;S^{n+1}). Without an additional channel-coding mechanism that accounts for these dynamics, the adaptation does not by itself establish reliable recovery from state-only observations. This is analogous to applying source coding alone to a joint source--channel coding problem. We therefore do not consider the unmodified adaptation a directly applicable DPIC baseline.

2. Security versus distribution preservation

As clarified in our previous response, DPIC does not require concealing the existence of communication and therefore imposes no steganographic security requirement. Its per-message distribution-preservation constraint is motivated by maintaining control performance, although it is related to distributional security in steganography. We have explicitly discussed this relationship and the differences between the requirements. We therefore do not see why the absence of a separate security discussion constitutes a major gap in addressing our stated problem.

3. Correction to the proof

We acknowledge the error in the original proof and have provided a corrected argument in the revised manuscript, together with a high-level explanation in our response. We have also carefully rechecked the proof. If the reviewer believes a gap remains, could they identify the specific step or claim that is still problematic? This would allow us to address the concern precisely and further improve the paper.

Thank you again for the continued discussion.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.