- 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 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
-
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?
-
Can the authors provide stronger baselines? How does PRAM compare with simpler shared-randomness coding schemes or existing communication methods under comparable assumptions?
-
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?
-
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
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 . In DPIC, the encoder selects actions , whereas the decoder observes only the resulting states , generated through the transition kernel . 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 in DPIC, its detector could not be directly applied to the observed states , 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 policy | Method | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| PRAM | 0.012 | 0.012 | 0.010 | 0.011 | 0.011 | 0.010 | 0.010 | 0.009 | |
| Act2Comm | 0.227 | 0.223 | 0.224 | 0.224 | 0.224 | 0.224 | 0.230 | 0.230 | |
| PRAM | 0.015 | 0.011 | 0.010 | 0.010 | 0.011 | 0.011 | 0.012 | 0.011 | |
| Act2Comm | 0.287 | 0.283 | 0.292 | 0.292 | 0.284 | 0.289 | 0.293 | 0.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. denotes blocklength
| n | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Bits | Method | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 | 100 |
| 4 | PRAM | 0.657 | 0.922 | 0.983 | 0.997 | 0.999 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 |
| 4 | Baseline | 0.430 | 0.675 | 0.821 | 0.910 | 0.951 | 0.981 | 0.990 | 0.994 | 0.996 | 0.998 |
| 6 | PRAM | 0.416 | 0.788 | 0.939 | 0.985 | 0.997 | 0.999 | 1.000 | 1.000 | 1.000 | 1.000 |
| 6 | Baseline | 0.175 | 0.335 | 0.486 | 0.611 | 0.702 | 0.783 | 0.833 | 0.874 | 0.896 | 0.930 |
| 8 | PRAM | 0.227 | 0.616 | 0.857 | 0.953 | 0.988 | 0.997 | 1.000 | 1.000 | 1.000 | 1.000 |
| 8 | Baseline | 0.057 | 0.119 | 0.188 | 0.240 | 0.313 | 0.359 | 0.416 | 0.475 | 0.499 | 0.537 |
| 10 | PRAM | 0.114 | 0.437 | 0.729 | 0.907 | 0.963 | 0.989 | 0.994 | 0.999 | 1.000 | 1.000 |
| 10 | Baseline | 0.018 | 0.037 | 0.063 | 0.086 | 0.111 | 0.130 | 0.153 | 0.180 | 0.200 | 0.219 |
In our experiments, decoding accuracy is estimated from 4,000 trials. We have clarified this in the updated manuscript.
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, denotes the blocklength per 8-bit block.
| 32 bits (4 blocks) | 64 bits (8 blocks) | |||
|---|---|---|---|---|
| n | Total blocklength | Accuracy | Total blocklength | Accuracy |
| 10 | 40 | 0.1905 | 80 | 0.0470 |
| 20 | 80 | 0.6145 | 160 | 0.3665 |
| 30 | 120 | 0.8345 | 240 | 0.6980 |
| 40 | 160 | 0.9480 | 320 | 0.8650 |
| 50 | 200 | 0.9800 | 400 | 0.9465 |
| 60 | 240 | 0.9925 | 480 | 0.9835 |
| 70 | 280 | 0.9985 | 560 | 0.9965 |
| 80 | 320 | 0.9995 | 640 | 0.9975 |
| 90 | 360 | 1.0000 | 720 | 1.0000 |
| 100 | 400 | 1.0000 | 800 | 1.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.
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∗) and sought to establish that Lt→∞. Condition C1 was introduced to handle finite-time elimination, where ρ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.