{"id":"fa5d0258-67ca-428f-bd21-380c21dd55cb","arxiv_id":"2502.03335","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"For an MDP whose states are observed by a receiver, the capacity of communication through actions equals a conditional mutual information, and the rate-reward trade-off is a convex program; Act2Comm is a practical transformer-based coding policy for this trade-off.","lead":"An agent can hide messages in its own behavior: it picks actions to earn rewards, while a watcher who only sees the environment's changing states decodes the message. This paper finds the mathematical limit of how many messages can be hidden per action while keeping rewards high, and builds a learning-based system that works in small simulations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Appendix B.1 derives Theorem 1 from the no-feedback FSC capacity formula (14), although the model explicitly allows output feedback; the entropy step (a) is invalid for feedback codes, so the proof as written establishes only an achievable rate unless an external POST-channel result is invoked.","rationale":"The reader's weakest_assumption targets the stationary-deterministic step in eq. (16) and the unproved achievability of C(V). The stationary-deterministic concern is probably not the right place to press: the DP action q(s) is a point in the simplex Δ(X), so a deterministic policy for the DP is already a stationary, possibly randomized, policy of the original MDP; continuity on a compact simplex plus the unichain assumption is the standard setting for such an optimum. The genuinely load-bearing gap is earlier, at eq. (14): the capacity formula used is the no-feedback FSC expression, while the model and Act2Comm use output feedback. With feedback, future U's carry information about current S_{i+1}, so the entropy equality at step (a) fails. Hence B.1 as written proves at most an achievability bound unless the paper invokes the POST-channel result it cites but never connects. The same pattern affects Theorem 2: the convex program is derived as an optimization identity, but no coding theorem shows that for every feasible occupation measure w the rate I(w,T) is achievable with average reward at least V. These are repairable gaps, and the claims are likely true for POST channels, but they are exactly the load-bearing support for the paper's central claim. I therefore keep the reader's conditional verdict: the paper should be accepted only after the proof of Theorem 1 is corrected or re-anchored to the POST-channel literature and the achievability half of Theorem 2 is supplied.","tokens_in":27985,"tokens_out":17491,"duration_ms":177250,"concrete_test":"Independently derive the feedback capacity of the action-state channel for the 3-state 'Lucky Wheel' MDP (Appendix D.2) using the POST-channel capacity theorem of Permuter et al. (2014), and compare it with max_π I(X;S+|S) computed by solving the convex program over occupation measures. If the two values differ on any transition law, Theorem 1 is false; if they coincide, Theorem 1 can be repaired by replacing the no-feedback formula (14) with the appropriate feedback-capacity argument or by explicitly invoking the POST-channel result, and by adding the missing reward-constrained achievability proof for Theorem 2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing gap is in the proof of Theorem 1, Appendix B.1. Equation (14) starts from C(s1)=max_{p(u_i|u^{i-1})} lim (1/N) I(U^N; S_2^{N+1} | s1), which is the standard capacity formula for an FSC without feedback. However, the system model in Section 3 explicitly includes output feedback: the encoder mapping is E_t : M × S^t × X^{t-1} × Y^{t-1} → X, and Act2Comm is built on feedback blocks. Under feedback, U_{i+1} may depend on S_{i+1}, so the identity used at step (a), H(S_{i+1}|S_2^i,U^N,s1)=H(S_{i+1}|S_i,U_i,s1), does not hold; future inputs can carry information about the current output. The subsequent inequalities therefore bound the no-feedback capacity, not the feedback capacity. At best, the derivation shows that max_π I(X;S+|S) is an achievable rate for the action-state channel with feedback; the converse is missing. The paper cites Permuter et al. (2014) on POST channels, whose results may supply the missing equality, but it never states how that theorem applies or why feedback does not increase capacity here. This gap is load-bearing because Theorem 2's convex program and the entire capacity-reward trade-off rest on Theorem 1. A second, related gap is that Appendix B.2 proves only the optimization identity for the unconstrained capacity; it does not prove achievability of the reward-constrained C(V), so the equality in Theorem 2 is currently supported only as an upper bound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies implicit communication through actions in an MDP: the controller embeds messages into actions, and a receiver observes only the resulting state sequence. The MDP is modeled as a finite-state channel (specifically a POST channel) with output feedback and with the state available to the encoder. The main theoretical claims are Theorem 1, that the unconstrained capacity of this action-state channel is C = max over stationary randomized policies of I(X; S+ | S), and Theorem 2, that the capacity under an average-reward constraint V equals the optimal value of a convex program over occupation measures, C(V) = max_{w in W} I(w,T) subject to the linear reward constraint. The paper also proposes Act2Comm, a transformer-based finite-blocklength coding scheme with a critic network and iterative training, and reports BER-versus-reward experiments on three MDPs. Appendix B contains the proofs: Theorem 1 is derived through an extended action-state channel and a no-feedback FSC capacity formula, with reductions from history-dependent to Markov and stationary encoders; Theorem 2 is derived using occupation measures, a log-sum inequality, and a tangent-line lemma.","tokens_in":28181,"tokens_out":16409,"duration_ms":158923,"significance":"If the theoretical claims are fully established, the single-letter expression for the capacity of action-state channels and the convex characterization of the rate-reward trade-off would be a valuable information-theoretic result, providing a fundamental benchmark for implicit communication through actions in MDPs. The convexity proof is self-contained, and Lemma 2 gives a closed-form gradient that makes the convex program in Theorem 2 numerically tractable. Act2Comm is a substantial engineering contribution: it addresses a non-differentiable finite-state channel with a critic-based gradient estimator, supports block-feedback coding, and is evaluated across three environments with ablations on feedback, message length, and target policy. The main weakness is that the proof of Theorem 1 does not currently handle the output feedback explicitly present in the model, and the proof of Theorem 2 establishes only the upper-bound direction of the claimed equality. These gaps are load-bearing for the central claims and must be closed or made precise before the theoretical contribution can be accepted as stated.","major_comments":[{"comment":"The proof of Theorem 1 starts from Eq. (14), C(s1) = max_{p(u_i|u^{i-1})} lim (1/N) I(U^N; S_2^{N+1} | s1), which is the standard capacity formula for a finite-state channel without feedback. However, the system model in Section 3 explicitly includes output feedback: the encoder is defined as E_t : M x S^t x X^{t-1} x Y^{t-1} -> X, and Act2Comm's encoder is fed feedback blocks C^(tau). Under feedback, U_{i+1} may depend on S_{i+1}, so the equality labelled (a), H(S_{i+1} | S_2^i, U^N, X_i, s1) = H(S_{i+1} | S_i, U_i, s1), is not valid in general. The subsequent inequalities therefore bound the no-feedback capacity, not the capacity of the model studied, and the converse direction of Theorem 1 is missing. The paper cites Permuter et al. (2014) for the fact that this is a POST channel, but it never states which POST-channel theorem closes the gap. The authors must either prove that feedback does not increase capacity for this channel, invoke and state precisely a known result that does so, or revise the model and Theorem 1 to the no-feedback setting.","section":"Appendix B.1, Eq. (14) and Section 3"},{"comment":"Theorem 2 asserts equality between C(V), the capacity under reward constraint V, and the value of the convex program max_{w in W} I(w,T) subject to sum w(s,x) r(s,x) >= V. Appendix B.2 proves only the unconstrained identity C = max_{w in W} I(w,T) and the concavity of I(w,T). It does not prove achievability for the constrained problem: for a fixed stationary occupation measure w with reward at least V, the paper never constructs a code family achieving rate arbitrarily close to I(w,T) with vanishing error probability and long-term average reward at least V. Since the reward constraint is linear in the occupation measure, the upper-bound direction is straightforward, but the reverse direction is essential for the claimed exact trade-off. The definition of C(V) itself, as an infinite-horizon limit of problem P3, is also never formally given; this should be stated before the equality in Theorem 2 can be assessed.","section":"Theorem 2 and Appendix B.2"}],"minor_comments":[{"comment":"The domain of E_i is written as \"M x S_i^i x X^{i-1}\" (typeset as \"M x S_i^i\" or \"M x S_i\"), which appears to be a typo for the full state history S^i; in addition, to match the earlier FSC definition, the encoder domain should include the output feedback history Y^{i-1}.","section":"Section 3, Controller & Encoder paragraph"},{"comment":"For the \"Catch the Ball\" environment, the main text refers to the noisy case as p = 0.2, while Appendix D.3 sets the failure probability to p = 0.8; this inconsistency should be reconciled.","section":"Section 6 and Appendix D.3"},{"comment":"The reduction from the time-varying DP in Eq. (16) to the stationary expression in Eq. (17) should state precisely which theorem of Fainberg or Hernandez-Lerma and Lasserre is being applied, and should verify its hypotheses explicitly, since the action space is the simplex of distributions and the per-step reward r(s_i, q_i(s_i)) is concave rather than linear in q_i.","section":"Appendix B.1, Eqs. (16)-(17)"},{"comment":"There is a stray closing parenthesis in the line \"x_t^(tau) = U^(tau)[s_t, t])\"; this should be corrected.","section":"Algorithm 2, line 9"},{"comment":"The experimental section does not plot the theoretical C(V) from Theorem 2; adding such a comparison would clarify how close Act2Comm's finite-blocklength curves come to the fundamental rate-reward bound.","section":"Section 6, Figures 3-5"},{"comment":"The name \"Act2cComm\" appears in the first paragraph; this is a typo for Act2Comm.","section":"Appendix D.4"}],"recommendation":"major_revision","confidential_remarks":"For an information-theory journal, the manuscript needs to be held to the standards of the field. The two major gaps above are fixable in principle: the feedback issue may be resolvable by a precise application of the POST-channel results of Permuter et al. (2014), and the constrained achievability in Theorem 2 can potentially be supplied by a standard random-coding argument over stationary policies. Because Theorem 2 inherits its validity from Theorem 1, both issues are load-bearing. It would also be useful for the authors to state explicitly how their Theorem 1 relates to existing POST-channel capacity results, both for correctness and for novelty disclosure. The Act2Comm part is a solid engineering contribution and should remain in the paper, but it does not by itself validate the asymptotic information-theoretic claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new piece here is Theorem 2's convex-program characterization of the rate-reward trade-off, plus the Act2Comm learning scheme. The occupation-measure formulation, the concavity proof via the log-sum inequality, and the tangent-line lemma are correct as written, and the gradient formula is useful. Act2Comm's critic-based gradient routing through a non-differentiable channel is a sensible engineering contribution, and the ablations plus promised source code are points in its favor; the trade-off curves look directionally reasonable.\n\nThe soft spot is in the proof of Theorem 1. Equation (14) is the standard capacity formula for an FSC without feedback, but the system model explicitly allows output feedback—the encoder at time t sees Y^{t-1}. Under feedback, step (a) of the entropy decomposition does not hold, because future channel inputs can carry information about the current output. So the derivation as written bounds the no-feedback capacity, not the feedback capacity. The achievability half is fine: stationary randomized policies are valid codes even with feedback, so C ≥ max I(X;S+|S). But the converse is missing unless you invoke an external POST-channel result, and the paper only cites Permuter et al. without stating how it applies. That is load-bearing, because Theorem 2 rests on Theorem 1.\n\nTheorem 2 has a second gap: Appendix B.2 proves the unconstrained identity max_w I(w,T) = C, but the constrained equality C(V) = max_{w: reward≥V} I(w,T) is asserted without a full converse. You need to show no code with reward at least V can beat the best stationary occupation measure, which is not immediate. This is fixable but currently only half-established.\n\nOn novelty, I suspect Theorem 1 is a re-derivation of known POST-channel capacity. The paper should state explicitly whether it differs from Permuter et al. and, if so, how. The experimental section would also be much stronger with a numerical solution of the Theorem 2 program overlaid on the BER curves, plus at least one baseline and error bars; right now the reader cannot judge how close Act2Comm is to the claimed fundamental limit. The unichain assumption is stated for deterministic policies but used for stationary randomized ones; that is a minor tightening, not a fatal issue.\n\nWho is this for? Researchers working on implicit communication, joint control and coding, or FSC coding with learned schemes. It deserves a serious referee: the gaps are real but addressable, and the convex-program formulation plus Act2Comm are worth engaging with. I would accept it for review, but the revision needs to close the feedback gap, prove or properly import the constrained capacity result, and add the missing experimental comparisons.","headline":"The convex-program formulation and Act2Comm are real contributions, but the proof of Theorem 1 as written covers only the no-feedback channel and leaves the flagship capacity formula under-proved for the paper's own model.","tokens_in":28920,"tokens_out":4992,"would_cite":true,"duration_ms":52412,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94A17","90C40","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that when an MDP controller embeds messages into its actions and a receiver reads them from the observed state sequence, the infinite-horizon rate-reward trade-off is exactly the value of a convex program over occupation…","keywords":["action-state channel","finite-state channel","implicit communication","capacity-reward trade-off","occupation measure","Markov decision process","channel coding","transformer coding"],"falsifier":"Take a small MDP, for example a two-state, two-action variant of the paper's Lucky Wheel environment, and compare the maximum average mutual information over all history-dependent encoders, computed by dynamic programming over a long finite horizon, against the value of the convex program in Theorem 2. If any history-dependent or randomized time-varying encoder strictly exceeds the stationary deterministic optimum, or if the convex-program value cannot be approached by any code sequence with vanishing error probability, then Theorem 1's single-letter formula is an upper bound rather than the exact capacity.","tokens_in":27584,"feed_emoji":"📡","tokens_out":9097,"duration_ms":74907,"temperature":0.7,"pith_summary":"This paper treats the state transitions of a Markov decision process as a communication channel: the controller's actions are the channel input and the states observed by another agent are the output. It claims that the maximum rate at which messages can be reliably sent this way, in the infinite-horizon regime, is the conditional mutual information $I(X; S^+ \\mid S)$ maximized over stationary randomized policies—a single-letter formula. Under a constraint that the long-run average reward stay above $V$, the same rate becomes the value of a convex program over occupation measures, so the full rate-reward trade-off is a concave curve that can be computed numerically. The paper also introduces Act2Comm, a transformer-based feedback coding scheme for finite blocklengths that learns to embed messages into actions while approximating a target reward-achieving policy, and shows in three small MDPs that it trades reward for reliability in the predicted direction.","feed_headline":"Exact rate-reward limit found for communicating through MDP actions","feed_subtitle":"A single-letter formula fixes the capacity of MDP action channels; a learned coder trades reward for reliability.","key_machinery":"The central objects are the action-state channel, where the MDP transition kernel $T(s' \\mid s,x)$ acts as the channel law with the action as input and next state as output; the occupation measure $w(s,x) = \\rho_\\pi(s)\\pi(x \\mid s)$, which linearizes the reward constraint; and the function $I(w,T)$, a concave mutual-information functional on the occupation-measure polytope whose tangent lines are given explicitly by Lemma 2, yielding a closed-form gradient for ascent. The proof chain converts the channel to Shannon's extended action-state (EAS) channel, reduces history-dependent encoders to Markov encoders via Puterman's theorem, then invokes average-reward MDP theory to argue that a stationary deterministic policy attains the optimum. Act2Comm's machinery is a transformer encoder-decoder pair with block-attention feedback, a hard quantizer mapping beliefs to decision rules, and a critic network trained on noisy neighbors of the belief map to provide gradients through the non-differentiable channel.","core_discovery":"The central claim is that for a finite-state MDP observed by a receiver, the capacity of the action-state channel with reward constraint $V$ is $C(V) = \\max_{w \\in W} I(w,T)$ subject to $\\sum_{s,x} w(s,x) r(s,x) \\ge V$, where $W$ is the polytope of occupation measures and $I(w,T)$ is a concave function, making this a convex optimization (Theorem 2). Without the reward constraint, capacity equals $\\max_{\\pi} I(X; S^+ \\mid S)$ over stationary policies (Theorem 1). The paper highlights that this implies history does not increase the infinite-horizon rate: a stationary randomized policy suffices to achieve capacity. The trade-off function $C(V)$ is concave, so the achievable region of rate-reward pairs is convex. The authors also claim that Act2Comm is a practical finite-blocklength policy that approaches this trade-off, as validated by bit-error-rate versus reward curves in three environments.","pith_inferences":["If the receiver could also observe the controller's actions, the same setting would become a source-coding problem in which messages are compressed into action sequences; the gap between that rate and the action-state channel capacity derived here would measure the value of action observability.","The convex program in Theorem 2 has a natural dual: its Lagrange multiplier prices the reward constraint, giving a marginal cost of communication that a system designer could use to decide how much control performance to sacrifice for each additional unit of rate.","Beyond the unichain assumption, one could formulate the same trade-off over convex hulls of recurrent-class occupation measures; the structure would likely persist, but the single-letter capacity formula would need re-derivation because the limiting state distribution need not be unique."],"forward_implications":["The rate-reward trade-off for communication through actions is computable: for any finite MDP the capacity under reward constraint $V$ can be found by convex optimization, so system designers can know the fundamental limit before choosing a coding scheme.","Because a stationary randomized policy achieves unconstrained capacity, infinite-horizon communication through actions requires no memory of past states or actions, a structural simplification relative to general finite-state channels.","The achievable region of rate-reward pairs is convex, so convex combinations of control-optimal and communication-oriented policies fill in intermediate points of the trade-off.","Act2Comm provides a finite-blocklength construction that empirically approaches the trade-off: lower reward constraints yield lower bit error rates at fixed rate, and lower rates yield higher reward at fixed bit error rate."],"supporting_citations":[{"why":"Supplies the multi-letter capacity formula for finite-state channels from which the proof of Theorem 1 starts.","marker":"Gallager, 1968"},{"why":"Gives the channel-transform method used to convert the action-state channel into the extended action-state channel with decision rules as inputs.","marker":"Shannon, 1958"},{"why":"Theorem 5.5.1 is invoked to reduce history-dependent encoders to Markov encoders while preserving the joint state-action distributions.","marker":"Puterman, 2014"},{"why":"Cited to justify that the average-reward dynamic program in equation (16) has a stationary deterministic optimal policy.","marker":"Fainberg, 1976"},{"why":"Also cited for the existence of a stationary deterministic optimal policy in the availability-average Markov decision process.","marker":"Hernandez-Lerma & Lasserre, 2012"},{"why":"Provides the notion of occupation measures and the polytope structure used to formulate the convex program in Theorem 2.","marker":"Altman, 2021"},{"why":"Gives the definitions of conditional mutual information and entropy used throughout the capacity analysis.","marker":"Cover, 1999"}],"fun_headline_variants":["Exact rate-reward trade-off for MDP action communication","Act2Comm: balancing control and communication in MDPs","Actions speak louder: optimal rate-reward limit in MDPs","Capacity-reward trade-off for MDP action channels solved"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The exact capacity formula collapses if the unichain assumption fails or if a history-dependent or randomized policy strictly outperforms every stationary deterministic policy for the communication objective—a real risk because the per-step reward in the dynamic-programming reduction is concave, not linear, in the action distribution.","fun_headline_variants_meta":{"raw":{"variants":["Exact rate-reward trade-off for MDP action communication","Act2Comm: balancing control and communication in MDPs","Actions speak louder: optimal rate-reward limit in MDPs","Capacity-reward trade-off for MDP action channels solved"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000705,"raw_usage":{"total_tokens":3225,"prompt_tokens":1036,"completion_tokens":2189,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":652,"completion_tokens_details":{"reasoning_tokens":2118}},"tokens_in":652,"tokens_out":2189,"duration_ms":15902,"temperature":1.0,"reasoning_tokens":2118,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T05:09:04.478940+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small MDP, for example a two-state, two-action variant of the paper's Lucky Wheel environment, and compare the maximum average mutual information over all history-dependent encoders, computed by dynamic programming over a long finite horizon, against the value of the convex program in Theorem 2. If any history-dependent or randomized time-varying encoder strictly exceeds the stationary deterministic optimum, or if the convex-program value cannot be approached by any code sequence with vanishing error probability, then Theorem 1's single-letter formula is an upper bound rather than the exact capacity.","supporting_citations":[{"cited_title":"Information theory and reliable communication, volume 588","cited_arxiv_id":null,"evidence_quote":"Supplies the multi-letter capacity formula for finite-state channels from which the proof of Theorem 1 starts."},{"cited_title":"Channels with side information at the transmitter","cited_arxiv_id":null,"evidence_quote":"Gives the channel-transform method used to convert the action-state channel into the extended action-state channel with decision rules as inputs."},{"cited_title":"On controlled finite state markov processes with compact control sets","cited_arxiv_id":null,"evidence_quote":"Cited to justify that the average-reward dynamic program in equation (16) has a stationary deterministic optimal policy."}],"review_version":1}