Actions Speak Louder Than Words: Rate-Reward Trade-off in Markov Decision Processes
Authors: Haotian Wu
Gongpu Chen
Deniz Gunduz
Venue: ICLR 2025 Poster (2025)
Keywords: Markov Decision Process
Channel coding
Rate-Reward Trade-off
Finite state channel
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: The impact of communication on decision-making systems has been extensively studied under the assumption of dedicated communication channels. We instead consider communicating through actions, where the message is embedded into the actions of an agent which interacts with the environment in a Markov decision process (MDP) framework. We conceptualize the MDP environment as a finite-state channel (FSC), where the actions of the agent serve as the channel input, while the states of the MDP observed by another agent (i.e., receiver) serve as the channel output. Here, we treat the environment as a communication channel over which the agent communicates through its actions, while at the same time, trying to maximize its reward. We first characterize the optimal information theoretic trade-off between the average reward and the rate of reliable communication in the infinite-horizon regime. Then, we propose a novel framework to design a joint control/coding policy, termed Act2Comm, which seamlessly embeds messages into actions. From a communication perspective, Act2Comm functions as a learning-based channel coding scheme for non-differentiable FSCs under input-output constraints. From a control standpoint, Act2Comm learns an MDP policy that incorporates communication capabilities, though at the cost of some control performance. Overall, Act2Comm effectively balances the dual objectives of control and communication in this environment. Experimental results validate Act2Comm's capability to enable reliable communication while maintaining a certain level of control performance.

Published as a conference paper at ICLR 2025
ACTIONS SPEAK LOUDER THAN WORDS: RATE-REWARD TRADE-OFF IN MARKOV DECISION
PROCESSES
Haotian Wu", Gongpu Chen'l, Deniz Gündüüz Department of Electrical and Electronic Engineering Imperial College London,
London SW7 2A7, U.K. (hactian. wu17, gongpu. chen, d. gunduz) wwwerppela...m uk
ABSTRACT
The impact of communication decision-making systems has been extensively studied under the assumption of dedicated communication channels. We instead consider communicating through actions, where the message is embedded into the actions of an agent which interacts with the environment in a Markov decision process (MDP) framework. We conceptualize the MDP environment as finite- state channel (FSC), where the actions of the agent serve as the channel input, while the states of the MDP observed by another agent (i.e., receiver) serve as the channel output. Here, we treat the environment as a communication channel over which the agent communicates through its actions, while the same time, trying to maximize its reward. We first characterize the optimal information the- oretic trade-off between the average reward and the rate of reliable communica- tion in the infinite-horizn regime. Then, we propose novel framework to de- sign a joint control/coding policy, termed Ac12Comm, which seamlessly embeds messages into actions. From communication perspective, Ac12Comm functions as a learning-based channel coding scheme for non-differentiable FSCs under input-output constraints. From control standpoint, Act2Comm learns an MDP policy that incorporates communication capabilities, though at the cost of some control performance. Overall, Act2Comm effectively balances the dual objectives of control and communication in this environment. Experimental results validate Act2Comm's capability to enable reliable communication while maintaining cer- tain level of control performance.
INTRODUCTION
The role of communication in multi-agent systems has received significant attention as it allows agents with partial view of the system better coordinate and cooperate by exchanging mes- sages in parallel to actions taken in the environment (Foerster et al. 2016)) /Sukhbaatar et al.) 2016). However, these systems rely on dedicated channels for communication. On the other hand, explicit communication channels may not always be available, or may be complemented with other implicit forms of communication. Such examples are abundant in nature. Bacteria communicate through chemical molecules, known as quorum sensing (Waters & Bassler 2005), altering their environ- ment and behavior achieve population- aapulation-wide wide coordination. Ants use pheromones to encode the path to food for other ants (von Thienen et al. 2014). Nen-verbal communication through gestures, gaze, and even physical appearance, is also known to play an important role in human communica- tion (Trenholm) 2020). In the artificial realm, autonomous robots may also need to rely implicit communications when explicit communication channels are not available. In medical nano-robote electromagnetic communication is not feasible due to size and energy limitations, but implicit com- munication can be achieved through molecular communications (Weiss & Knight (0001] Wang et al.) 2023 Even for advanced robots, electromagnetic or other types of explicit communication
'These authors contributed equally to this work. t Corresponding author.

---

Published as a conference paper at ICLR 2025
channels may not be available in harsh or hostile environments; for example, for robots decom- missioning nuclear storage facilities, or those operating in deep space, deep ocean, or subterranean environments, e.g., tunnels and caves (Ebadi et al.] 2024). Moreover, wireless signals are prone to wiretapping due to their broadcast nature (Poor & Schaeter 2017), and can be unreliable in adver-
sarial scenarios due jamming (Pirayesh & Zeng 2022 Martz al. 2020), which are other factors limiting explicit communications.
Motivated by these challenges, this paper explores implicit communication in a Markov Decision Process (MDD)-commnice
through actions-whier facilitates information transmission from the MDP controller to other agents that can observe the MDP states. Effectively utilizing this internal channel has the potential to reduce the dependence on dedicated communication channels. However, such a communication capability comes with inherent trade-offs. As we will demonstrate, using this channel for communication often leads to degradation in MDP control performance. This raises a fundamental challenge in balancing control and communication objectives, underscoring the need for cohesive design that integrates control and communication.
An MDP consists of a controller and an environment (Puterman) 2014p. At each time step, the environment is in some state and the controller selects an action Upon executing action the environment stochastically transitions to a new state and generates a reward. Controller's 's objective is to find an optimal policy for selecting action each time to maximize its accumulated reward over a given time horizon. Consider that the controller wants to communicate with another agent (i.e., the receiver) that can also observe the environment state.
In communication theory, a finite-state channel (FSC) (Gallager) 1968) is an input-output system with states, where the output depends on both the input and the current state. Messages are encoded into the input sequence, resulting in a corresponding output sequence. The receiver decodes the message from this output sequence. From this perspective, the state transition of an MDP from to s' upon taking action a can be viewed as an FSC from the controller to the receiver. We refer to this internal channel within the MDP as an action-state channel. To communicate through the action- state channel, we need an encoder that maps the message to a sequence of actions, and decoder that translates the resulting state sequence back into the original message. However, the objective of this encoder differs from that of the controller: the encoder aims to maximize the transmission rate and reliability of its message, while the controller seeks to maximize the accumulated reward. These two objectives are generally inconsistent, and trade-off between the two must be sought.
In this paper, we first investigate the trade-off between the capacity (i.c., the maximum achievable transmission rate) of the action-state channel and the MDP reward in the infinite horizon regime. We demonstrate that the capacity of this channel can be expressed in a simple form-as as the condi- tional mutual information between the input and output conditioned on the channel state. We also show that the capacity-rewan trade-off can be cast as a convex optimization problem, which can be solved numerically. While the capacity-reward trade-off provides an upper bound on the practically achievable rate under certain reward constraints, solving it does not yield a practical coding scheme. We then propose practical framework for the integrated control and communication task in the finite block-length regime. The challenge in designing such framework is twofold: (1) balancing the control and communication performances; and (2) dealing with the cin-differentiability of the action-state channel. To tackle these issues, we propose Act2Comm, transformer-base coding scheme in which encoder and decoder are trained iteratively.
Contributions. The main contributions of this paper are summarized as follows: (1) We introduce novel paradigm communicating through actions within an MDP environment, framing it as an in- tegrated control and communication problem. (2) We derive the capacity of the action-state channel, and characterize the capacity-reward trade-off as a convex optimization. (3) We propose Ac12Comm, practical transformer- basse coding scheme to learn policy that optimizes communication perfor- mance while maintaining a specified level of MDP reward. Act2Comm can be of independent interest for designing practical channel coding schemes over other non-differentiable FSC scenarios.
2 RELATED WORK
Communication plays a significant role in MDPs, especially in multi-agent reinforcement learning (RI.), where agents exchange messages over dedicated or noisy links achieve common goal
2

---

Published as a conference paper at ICLR 2025
Wang et al., 2020] Chen et al. 2024 Tung et al. 2021). This is known emergent communications [Boldt & Mortensen 2024), but this framework relies on explicit communications over dedicated channels. Implicit communication through actions is considered by Knepper al. (2017) and Tian et al. (2019). The latter also trains a policy, but it focuses on the multi-agent scenarios, and encour- ages communication by appropriately changing the reward function. We do not explicitly specify the communicated information, and instead, take a more fundamental approach by characterizing the information theoretic limits of communication and designing a practical coding policy.
Sokota et al. 2022) explored a similar concept of communication via MDPs. In their study, the receiver can observe the entire trajectory, including both the action and state sequences. This en- ables the controller to encode (compress) messages into the action sequence. and the receiver can subsequently decode the messages from the trajectory. Essentially, this is source coding problem. However, in most practical scenarios, while the MDP state is a physical signal observable by the receiver, the controller's ss actions are typically not directly observable by other agents. Therefore, in our work, we assume the receiver can only observe the state sequence. This shifts the problem from source coding to channel coding. Karabag et al. (2019) also examined a similar system, but their focus was developing policies that restrict the observer's ability to infer transition probabilities.
FSC represents a general class of communication channels, and its study has been a long-standing problem in information and coding theory. [Blackwell et al. (9558) studied the capacity of indecom- posable FSCs without feedback. Subsequent studies in the non-feedback setting include (Verdu & Han 1994) and (Goldsmith & Varaiya 1996). The capacity of FSCs with feedback
examined by Massey (1990) and Permuter et al. (009). More recently, [Shemuel et al.] (022) explored the capacity of FSCs with feedback and state information at the encoder. However, these results express capacity in multi-letter forms, relying on the entire input and output sequences as their lengths ap- proach infinity, Although [aaaag et al. (2017) provided single-letter upper bound for the feedback capacity of unifilar FSCs, exact The action-state channel studied this paper is a special FSC with state and feedback at the encoder. Utilizing the unique structure of this channel, we derive single-letter expression for its capacity.
expressions for FSC capacity are generally unknown.
Machine learning has recently advanced traditional channel coding schemes by replacing linear operations with trainable non-linear neural networks, including Turbo autoencoder (Jiang et al.) 2019). DeepPolar (Hebbar et al. 2024), KO codes (Makkuva et al., [02T], and other approaches (Jiag et al. 2020 Kim et a 2018). However, these are designed for Gaussian channels, which are differentiable and allow joint training of the encoder and decoder. Our channel, in contrast, is non- differentiable, presenting new challenges for the design of the encoder and decoder. Channel coding for FSCs is a challenging task with limited results in the literature. Some existing work focuses only on the design of the decoder (Aharoni et al. 2023). However, the main challenge in our problem lies in designing the encoder to balance control and communication performance.
Notations: For any sequence (#, / 2 1}. æt denotes the sub-sequence {xe, Te+1, , 3x where at is written as * | denotes the cardinality of the set X. A detailed notation table is provided in Table T
3 PRELIMINARIES AND SYSTEM MODEL
Markoy Decision Process (MDP). An MDP can be characterized by tuple (S, X. T, a), where S is the state space, X' is the action space, T is the transition kernel, r S x X - IR is the bounded reward function, and a is the initial state distribution. At each time step t, taking ac- tion I, in state s, results in reward r(st, I2)) and a state transition from 8; to 8141, where 8441 is sampled from the distribution T(+ss,, I.). We assume both S and X' are finite sets. A stationary deterministic policy is mapping S + X' that selects action xa based state st at each time t. The objective is to find an optimal policy that maximizes the long-term average reward, as follows:
N
1 N
P1:
max lim N
E
Σ
r( 21))s1 ~a
In this paper, assume that the MDP is unichain: that is, any deterministic policy induces a Markov chain consisting of a single recurrent class plus some transient states. As a result, the optimality of P1 can be achieved through stationary deterministic policy. The set of stationary deterministic
3

---

Published as a conference paper at ICLR 2025
m
X1
1
Sc+2
m
Encoder
Decoder
Encoder & Controller
P( [1)
Decoder
Yt-1
8t
Unit-Delay
(a) A standard finite-state channel
(b). Action-state channel
Figure 1: From standard finitc-statc channel an action-state channel.
worth noting that the set of admissible policies for an MDP is not restricted to llsp. In general, a policy can be history-dependent, determining Ia using all historical states and actions up to time t. Let IIs and H. denote the sets of stationary (possibly randomized) and history-dependent policies, respectively. It is easy to see that IIsp C Iss C II
policies is denoted by llsp.
Finite-State Channel (FSC). As illustrated in Fig. I an FSC can be characterized by a tuple x Py,stixs 3/x x S), where X' is the input alphabet, y is the output alphabet, S is the channel state alphabet, and Py,s' xx,s is the channel law specifying the probability of the channel outputting Y and transitioning to the new state S*, given that the channel input is X in state S. We consider a time-invariant channel that exhibits the Markov property, which can be formally expressed
P(ye, st-1/0", s² y PY.s" xxs (Btr St+1 12,,, st), Vt.
(2)
To transmit a message m, an encoder generates a sequence of inputs x' as a codeword. When each Fe is input to the channel, the channel transitions to new state St4-1 and produces an output y/. The decoder then collects the output sequence y" to reconstruct m. We suppose that the channel state is available to the encoder but not to the decoder, and that the outputs are fed back to the encoder.
Let M denote the set of messages, with each message uniformly sampled from M. The encoder is defined as a sequence of mappings, E {E,,...,&, }. where each mapping & : .M x St x x yt-1 + X' generates the channel input time f. In other words, the channel input time f, (m, s², x² .y" " is function of m and all the historical information available at the transmitter up time t. The decoder is defined as the mapping. D : y - .M. which reconstructs the message from all channel outputs, vi- D(y"). ). The pair (E, D) constitutes code, where called the code length. Suppose the message set A {1, 21,2,3, ..., 2*) then each message can be represented with l bits. The rate of the code (E, D) is defined as RE = k/n.
The error probability (!") for (E, D) is defined as p!!' = Pr(D(z)" * m m is sent). A rate R is deemed achievable if there exists code (E, D) such that the eπrо probability of the transmission approaches zero as n + co. Consequently, the capacity of the FSC defined as the supremum of all achievable rates. In other words, channel capacity reveals the maximum rate available for error-free transmission when the code length approaches infinity. In practice, however, constructing code with infinite code length is unfeasible. Hence practical channel coding aims to balance the trade-off
between R and (!)) with a finite code length n. For instance, we design codes to maximize the rate while ensuring that the probability of error remains below certain threshold 0:
P2: max Rg
subject p!n)) a.
(3)
E,D
Integrated Control and Communication. We investigate a scenario in which the controller of an MDP aims not only to optimize rewards but also to facilitate communication. Assuming that the receiver can observe the state of the MDP, then the environment can be modeled as a specialized FSC, enabling communication between the transmitter (i.e., the controller) and the receiver.
(a) Action-state channel model: This integrated FSC is referred to as the action-state channel, where the state of the MDP aligns with the state of the FSC. The action and the subsequent state are viewed as the channel input and output, respectively. Upon executing I; in state St, the MDP environment returns a reward r, and transitions a new state $t41. Here S functions as both the channel output and the new channel state, and s represents not only the historical state sequence, but also the historical feedback signal. The channel law of the cation-state channel is given by:
P(8 lx. 8²) PPstjx.s(SH+) (0,, 8t) A T( 1/,, St)-
4

---

Published as a conference paper at ICLR 2025
This type of channel is also referred to a POST channel in the literature PPermuter et al. 2014).
(b) Controller & Encoder: Within this framework, the MDP controller and the FSC encoder rep- resent the two aspects of the same entity, jointly responsible for selecting action Ia X each time step. However, their objectives differ: the controller aims to maximize the reward, while the encoder seeks to maximize the message rate. Unlike the controller, which can focus on stationary deterministic policies, the encoder must account for more complex policy forms. For any message m, the encoder described in the previous part can be viewed as history-dependent policy for the MDP. Therefore, we consider the joint control and coding policy in its most general form. The pol- icy is represented as sequence of mappings {E, 0 S i S n 1}, where & is defined as E, .M x St x X + X. Each message is transmitted via sequence of n actions. For example, if the controller begins to transmit a message m at time t, then Te+i E, sf - for S i S diately after completing the transmission of the previous message, and each message is uniformly sampled from M. The long-term average reward of the MDP under policy & is denoted by Gg.
We assume the controller always has new message ready for transmission imme-
The receiver observes the state sequence associated with message and uses it to decode the message. For example, the state sequence associated with the i-th message is sin in--+1- The decoder, represented as a mapping D S + M,, decodes the message as: = D
(c) Decoder:
In this paper, consider non-terminating MDPs over an infinite time horizon and investigate the trade-off between control and communication performance. As discussed previously, if the code length + the communication performance can be characterized by the channel capacity (i.e., the maximum achievable rate). Here, we consider a practical setting with finite code length n, where the performance of a code (E, D) is characterized by its rate Re and the error probability p(x) We study the trade-off through the following optimization problem with constants V and 0,
P3: max Rg E,D
(5)
s.t. 2 V and p!") S a.
(6)
THE CAPACITY-REWARD TRADE-OFF
In this section, we analyze the trade-off between the capacity of the action-state channel and the MDP reward. While the results may not offer direct guidance for practical coding-since the capac- ity is typically achievable only in the infinite-horizon regime (i.e., when the code length n + oo)- they delineate the fundamental performance limits of communication via actions in MDPs, thus holding substantial theoretical importance. All proofs of this section are detailed in Appendix B
In information theory, the capacity of an FSC is usually expressed in terms of conditional mutual information Shemmeel et al., 2024). Let X, S+ and S denote the random variable associated with the input, output (i.e., the next state), and the current state of the action-state channel, respectively. Then the conditional mutual information of X and S+ given S is defined as (Cover 1999):
T(X;S+IS) Ep(a,st.a) log p(s,st|s) p(zls)p(s+(s)
Let (--ss) denote an input distribution of the channel given that the channel state is s E S. For a given channel. the joint distribution p(z, s is determined by the conditional input distribution π. From the MDP perspective, π (x]ss) represents the probability of selecting action x in state 8; thus, be viewed stationary randomized policy for the MDP. Let Par denote the equilibrium state distribution of the MDP under policy π. We have the following result:
Theorem The capacity of the action-state channel without reward constraint is given by
C=
max ( 1(X:S+1S)
where X, S, and S follow a joint distribution given by
p(5, 8 s) = (==_(=))((l)l))(sttssss x E X, E.
5

---

Published as a conference paper at ICLR 2025
As previously discussed, general encoder for an FSC generates channel input based all the historical state and feedback information. However, Theorem Teevals a surprising fact: the capacity of the action-state channel can be achieved by encoding messages using stationary randomized policy for the MDP, without relying on historical information.
Theorem D presents the capacity of the action-state channel without considering the MDP reward. we want to maintain a certain level of long-term average reward for the MDP, the capacity may generally decrease. Next, we characterize the trade-off between channel capacity and MDP reward.
Given a stationary policy π for the MDP, define wa (ss, a)) = Pa (T) Here, Wr (8, (8) represents the long-term proportion of time that the MDP is in state and takes action æ. In the literature, Wn is referred to as the occupation measure of policy т (Altman (021). Let W denote the set of all occupation measures, then W is the set of w E RRSS x|1] satisfying the following equations:
Σ wo (((s x) - Σ Σ
wols (T(p) ,0') = O, Vs E,
(8)
ZEX
F'ES F'EX
ΣΣ wo(s () = 1, w(s x) 2 0, Vs S
*ES
Clearly, W is polytope. It is well-known that there is a one-to-one mapping between W and lIs. In particular, (z]ss) (s, x / (=,5xz') for any S, x E X. Using this relationship, the problem of computing the capacity with reward constraint V (i.e., ensuring the long-term average reward is not less than V/) reduces to a convex optimization, as stated in the following theorem:
Theorem The capacity of the action-statt channel with reward constraint V is the optimal value of the following convex optimization problem:
max wEW
[w, T)
s.t. Σ Σ
()(s,))
SES ZEX
where [ww, T) a concave function of w E W defined as
T(s'ls, x)) Eno w(s,z") En' (8"1 (')(())
1w, T) 2 Σ Σ w(s
Σ
T( log
xE
S'ES
Denote by C(V) the capacity of the action-state channel with reward constraint V.
Lemma C(V) a concave function.
Since the capacity is an upper bound for the rate of any practical coding scheme, Lemma 1 implies that the achievable region of rate-reward pairs forms convex set.
The convex optimization problem in Theorem 2 can be efficiently solved using the gradient ascent algorithm if the gradient of the objective function has a closed-form expression (Bertsekas) 2016).
Next, we derive the gradient of 7 7ww, T') with respect to w. Define
T(s' 2) Ene Wn (8,2")
Iww Wn, T) a
ΣΣ w(s ET(''ss, log Σn- T(s' Ww x²) w, wn. W.
oES
S'ES
Lemma 2 For any Wn W. I(w, Wny T) is tangent line of Tww, T) point wn. That
(i) IWw, Wn, T) = T).
(ii) I(w, wn T) 2 [w, for all w.
It follows immediately from Lemma 2 that 0l (lw,TT)
T(s'ls x)) log T(s'(s, Ex Wn(s,
V Vh (8)
(10)
Ow(s, s, x))
Σ,- T(s' ((s')s,,'')u (('(s,,"')un(s,r"
w=w.
''ES
for any Wn E W, s E S, and x E X. The gradient 01 /0w = [V (s, 2,,,, then can be used in the gradient ascent method solve the optimization problem in Theorem 2

---

Published as a conference paper at ICLR 2025
Crili
Critic network updaring
Oreaient estiration
step
training
Gride
Fin
Outer training stop
mm
Dairtew
BAB cherrel
Decadar
gl+11
Jeady
gitz
CP
Endironment
Tosal Loss
Benative updating atrategy
Inference workflow
Figure 2: (Left) Workflow diagram of the Ac12Comm scheme, with the dashed line indicating the gradient flow. (Right) Illustration of the iterative training strategy, incorporating critic network.
ACT2COMM: PRACTICAL CODING SCHEME
This section presents Act2Comm, a learning- based practical coding scheme that balances both con- trol and communication objectives. This framework assumes a pre-determined control policy æ that satisfies the reward constraint G 2 V, referred to as the target policy. Such target policy can be easily derived using traditional MDP or RL algorithms. Alternatively, solving the problem in The- orem yields a policy ı that precisely satisfies G, = V. Act2Comm aims to learn a coding policy that: (I) closely mimics the stochastic behavior of the target policy; (2) minimizes the probability of decoding errors for a given coding rate and finite code length. That is, Act2Comm takes a policy achieving the desired reward, and embeds messages into it with the desired reliability. For case of reference, we denote the element of matrix X at the i-th row and j-th column as X(i The sets of states and actions are indexed S (0, 1........ ..... |S| 1} and X {0, 1, 1..1,........ | 1).
Channel transform. Let U & XI Each U is referred as decision rule as the i-th element of u can be viewed as an action prescribed for state i. A deterministic control policy can be defined as a sequence {u, : t 2 1}. where 4t is the decision rule time f. To facilitate block coding, we first convert the action-statt channel into extended action-state (EAS) channel (Fig. in Appendix) using Shannon's 's method (Shannon 1958). We conceptually separate the encoder and controller, considering the controller as part of the EAS channel. Channel state is assumed to be available at the controller, but not the encoder. At each time t. the encoder selects a decision rule ue from U. Then the controller uses and the state s, to determine action 2, u.())). Consequently, the EAS channel has input alphabet U, output alphabet S, and channel law:
Ps+|s (8441881 un) = Ps+|s,x ($141/$2 ux()))) A T( (s))))
(11)
The EAS channel and the action-state channel are equivalent. We will focus on the former to develop coding scheme. This approach allows without knowing the future states. Actions for subsequent time steps can then be determined using these decision rules when the states revealed. In the rest of this section, detail the Ac12Comm framework, which consists of five components.
map data block to a sequence of decision rules
1) Overall workflow. As depicted in Fig. 2. given bitbt message m E 13, the Act2Comm first encodes m into a belief map Z E R
S R. This Z is subsequently mapped into a codeword U E x|S| å by a quantizer. At each time step t, the controller selects an action state st, and the channel transitions into a new state according to the channel law Pst (s.x After k R
Us t] for
time steps, the receiver decodes the message based on the accumulated observations E #
2) Block-attention feedback coding. One of the principal innovations of Ac12Comm is the block- attention coding mechanism, which reduces the coding complexity and enhances the performance.
(a) Message block: Formally, partition message m into / blocks each block b2 {0, 13. contains μ = k/l bits. This allows us to encode m with coding rounds, with each round consisting of μ time steps. For each coding round (1 < 1). the input
[b,; b2; ... br). where
message block is defined (r) [2b 1; .; 2b, RT

---

Published as a conference paper at ICLR 2025
(b) Feedback block:
Although Theorem I shows that the rapacity-achiese code with infinite blocklength can be history-independem,, feedback has demonstrated benefits in simplifying the cod- ing process for better performance in the practical finite blocklength regime (Kostina et al. 2017 Kim et a 2020). Hence, for each time step t. within the 7-th coding round, we introduce the feed- back vector c, & [s[-], _z s E RIx3, which encapsulates the current state, the selected action, and the subsequent state. The feedback matrix for the 7-th round can then be given by C ;...;.... 1 E R x3 Consequently, for each coding round T, we concatenate prior
feedback matrices to construct feedback block: C(r) - [C E RR*xxx
3) Transceiver design.
(a) Encoder: At each coding round transformer-based encoder is utilized to generate belief #1S)
matrix (Tr) E TRTx R using (Tr) and C(r). The detailed architecture is provided in Fig. 8b
with each component illustrated in Appendix C The 7-th row vector of ((7), denoted as ( [7,)] :] R
#! represents the belief vector derived from the 7-th coding round. After completing
all coding rounds, the selected belief vectors are combined to form the final belief map Z [z (z("). :...: 200) E TR x =|d! which is subsequently reshaped into Z RISI t. Each element of this reshaped belief map [(x,,t) t] indicates the action belief at time step &. given state 8t-
Quantizer: Ac12Comm employs quantizer to generate the codeword U E x1 as:
U 2(xx) Sigmoid( Z)),
(12)
where Q :
| + x is the quantization operation that maps the coding result to the
nearest action index in the action space X, and each element of resultant codeword, U U(st. t]. represents the selected action for state 8 at time step t.
(c) Decoder: Given the state observations s [s1;...:;84 E S a transformer- based decoder is utilized to output logits M E A x2" for all blocks. After applying the softmax function, each block is predicted and subsequently transformed into the reconstructed bitstream m.
4) Joint optimization of control and communication. To model the trade-off between control and communication, we utilize a weighted loss function to train the encoder: Lalt = Loom + ALcont- The communication loss Leom is defined the cross-entropy between the predictions from critic network and their corresponding ground-truth which quantifies the message decoding accuracy. To ensure control performance, we aim make the coding policy behave closely the target policy. Therefore, Lcont measures the "distance" between the coding policy and the target policy.
Let denote the target policy, with =<r|s) representing the probability of taking action æ in state 8. Let (x(s) denote the frequency of selecting x in state 8 across all decision rules in U. We then use the mean square error (MSE) between π and fu to measure the control loss for its stabil- ity in experiments. However, fu is non-differentiable during the backpropagation as it is discrete. To address this issue, we estimate (x:ss) using Z in equation 12. Let e denote the all-one row Z
vector, and define (T,, 8, .)) A Sigmoid(=((2//iinnonn (Z(x, :]) ze)). When 7 > a,
suffi- ) is (kRR) vector with elements close to either 0 or 1. Additionally,
ciently large, ( [T
I'z(2 (T, s,z)e" approximates the number of elements in U[s,:) :] that are not less than x. We refer to Y the temperature parameter and estimate fo (z(s) for x > 0 as follows:
1
fu(z]s) re (x(s)) &
[T'(T 5, - l)e (T
(13)
kR For = 0, we have fr. (0)s) 2 1 (T, 0) /kR. As result, we define the control loss Lcont MSE(T,)
5) Iterative training strategy. Given the non-differentiable nature of the EAS channel and quan- tizer, jointly updating the encoder and decoder is infeasible. To address this, we introduce critic network and employ an iterative updating strategy to train Ac12Comm effectively, with the corre- sponding algorithm and architectures detailed in Appendix C22
(a) Critic network. As shown in Fig. 2 a critic network is introduced to estimate the gradient during gradient backpropagation for the encoder optimization, which views the EAS channel and decoder
8

---

Published as a conference paper at ICLR 2025
10
Loge Bok
Tigan
307
Taget
15
304
Targstreward 10
Targstreward 0.5
30
63
07
65
24
Coding rate
Codlngg rate
(a) BER v.s. Reward
(b) Reward v.s. Rate
(c) BER v.s. Rate
Figure 3: Control-communiattio trade-off of Acf2Comm in "Lucky Wheel""
as an unknown environment. Before each update the encoder, a critic network is trained over 8in inner steps to predict the logits for the neighbor belief maps of a given Z. For each inner step k the network is trained to predict the corresponding logits M& as Mc based on the neighbor belief maps sampled from Z Z WK. where W R & (O, a is the Gaussian noise term for neighboring sampling during the k-th inner step. The MSE loss, denoted as Len. is utilized between Mc and Mr to train the critic network. With this design, we aim to obtain precise critic network to estimate gradients from neighbors of Z in given environment, thereby helping update the encoder. Note that this extra training cost is incurred only during the offline training process, this critic network will be removed during the inference phase, as detailed in Appendices C.3 C.4
(b) Iterative updating strategy. As outlined in Fig. 2 at each update step i, we first train a critic network &i.n using 8in inner steps learn to estimate the gradient around the samples. Next, the encoder updated g using the frozen decoder parameters ç and the learned gradient estima- tion. Subsequently, the decoder is directly optimized with the loss function obtain new parameters gi+1 while keeping the encoder frozen at 6'+1, This process iteratively alternates between encoder and decoder updates, freezing one while optimizing the other at each step.
6 EXPERIMENTAL RESULTS
We evaluate Act2Comm across three distinct MDP environments, detailed in Appendix D with communication performance measured by the bit error rate (BER). Due to page limitations, the results of the third environment, "Erratic robot", are provided in the Appendix D.4 D.4
Experiment 1: Lucky Wheel. In this game, the agent keeps spinning a wheel to accumulate rewards by choosing either clockwise counterclockwise direction. It is modeled as an MDP with states and 2 actions, the details of the environment and experimental setting are provided in Appendix D
We examine the trade-off among the three performance metrics in Fig. 3 We set the optimal reward- maximizing policy as the target policy, and consider different code rates, By adjusting A, we can control how closely the coding policy approximates the target policy. The shaded regions figures (a)-(c) represent achievable regions of Act2 with various A. When À is large, regardless of the coding rate, Act2Comm learns policy that mirrors the target policy. In this case, all messages are mapped to the same sequence of decision rules since the target policy is stationary and deterministic. As result, the BER is 0.5, indicating zero communication capability.
Next, we consider different target BERs, resulting in trade-off between the code rate and reward. As shown in Fig. 3h achieving pre-determined BER with a higher coding rate results in a reduced reward. When targeting lower BER, the reward decreases rapidly with the coding rate. Fig, 3c il- lustrates Act2Comm ability to balance BER and coding rate when ensuring specified reward. Our results reveal that reducing the reward constraint leads to more reliable communication at the same rate. In summary, these findings demonstrate that Ac12Comm can communicate messages through its actions at acceptable reliability while satisfying specific reward criteria.
Experiment 2: Catch the Ball. We next evaluate Act2Comm in "Catch the Ball", which is an MDP with 27 states and 3 actions. This MDP includes parameter p that influences its transition matrix

---

Published as a conference paper at ICLR 2025
Ashievabo
R-1/2
T-10
R- 116
R-115
10
Target BE 2m-2
164
03
TaIgEEEER.
come Tegennees
88
2.4
1.2
Reward
Coding rate
(a) BER V.s. Reward
(b) Reward v.s. Rate
(c) BER v.s.
Figure 4: Control-communicttio trade-off of Act2Comm in "Catch the Ball" with 0.
Tape TaggtBeli..
107
12"7
8EN
000
Achlov00
Reward
1.70
Tangtreeaadd
1-1.4
3:15
3-166
03
02 33
68
Reward
Codiigg
Codiigg rate
(a) BER V.S. Reward
(b) Reward v.s. Rate
(c) BER v.s. Rate
Figure 5: Control-communication trade-off of Act2Comm in "Catch the Ball" with p = 0.2.
(see Appendix D for details). When 0, the action-state channel is perfect as each action can be reliably inferred from the resulting state transition, but it becomes noisy for p >> O.
We first consider tain a certain reward while communicating. Act2Comm performs excellently in this environment. As shown in Fig. 4aj with minor reduction in reward from 1.66 to 1.5, Act2Conun communicates at rate of 0.2 with no error. If we relax BER to 10 same rate can be achieved with a reward 1.6. The trade-off between reward and rate is shown in Fig. 4b This experiment highlights our model's capacity to enable efficient communication capabilities with minimal impact on performance. We also applied Act2Comm to this game with p 0.2, in which the action-state channel is noisy and the coding process becomes more complex. As detailed in Fig. 3 we can observe a reduction in the coding rates for the same level of reliability due to the stochasticity in the environment.
O, where no coding is needed since there is no noise. The challenge is to main-
CONCLUSION
We introduced a novel framework of communication through actions, a form of implicit communi- cation from the controller of MDP receiver that observe the states. By treating the MDP environment as a communication channel, messages can be encoded into the action sequence and decoded from the state sequence. Aiming optimize communication performance while ensuring certain MDP reward, we formulated an integrated control and communication problem. We derived the capacity of the action-state channel and demonstrated that the trade-off's between channel capacity and reward can be characterized as convex optimization problem. We then proposed Act2Comm, transformer- based framework for designing joint control and communication policies. Through ex- periments, we demonstrated Ac12Comm's capability communicate reliably through actions while maintaining certain level of MDP reward.
The proposed Ac12Comm framework can be used as plug-in component in various MDP and RL. applications, enabling information transmission by learning a joint control and coding policy that closely mimics the target policy. More importantly. our study demonstrates the potential of commu- nication through actions in multi-agent systems. While this form of implicit communication leads to some loss in control performance, may potentially improve the overall control performance by hancing coordination when applied to multi-agent systems where explicit communication chanmels not available. This presents interesting and challenging direction for future research.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We acknowledge funding from the UKRI for the projects AI-R (ERC Consolidator Grant, EP/X030806/1) and INFORMED-AI (EP/Y028732/1), as well as the SNS JU project 6G-GOALS under the EU's Horizon program (Grant Agreement No. 101139232).
REFERENCES
Ziv Aharoni, Bashar Huleihel, Henry D Pfister, and Haim H Permuter. Data-driven neural polar codes for unknown channels with and without memory. arXiv preprint arXiv:2339.03118, 2023.
Eitan Altman. Constrained Markov decision processes. Routledge, 2021.
Dimiuri Bertsekas. Nonlinear programming. Athena Scientific, 2016.
David Blackwell, Leo Breiman, and Aram J Thomasian. Proof of shannon's transmission theorem for finite-state indecomposable channels. The Annals of Mathematical Statistics, pp. 1209-122) 1220, 1958.
Brendon Boldt and David R Mortensen. review of the applications of deep learning-based emer- gent communication. Transactions Machine Learning Research, 2024. ISSN 2835-8856. URL
Jingdi Chen, Tian Lan, and Carlee Joe-Wong Rgmcomm: Return gap minimization via discrete communications in multi-agent reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 17327-17336. 2024.
Thomas M Cover. Elements of information theory. John Wiley Sons, 1999.
Kamak Ebadi, Lukas Bernreiter, Harel Biggie, Gavin Catt, Yun Chang, Arghya Chatterjee, Christo- pher E. Denniston, Simon-Pierre Deschênes, Kyle Harlow, Shehryar Khattak, Lucas Nogueira, Matteo Palieri, Pavel Petráček, Matěj Petrlík, Andrzej Reinke, Vít Krátký, Shibo Zhao, Ali- akbar Agha-mohammadi, Kostas Alexis, Christoffer Heckman, Kasra Khosoussi, Navinda Kot- tege, Benjamin Morrell, Marco Hutter, Fred Pauling, François Pomericau, Martin Saska, Sebas- tian Scherer, Roland Siegwart, Jason L. Williams, and Luca Carlone. Present and future of slam in extreme environments: The darpa subt challenge. IEEE Transactions on Robotics, 40:936-959, 2024. doi: 10.1
EA Fainberg. On controlled finite state markov processes with compact control sets. Theory of Probability & Its Applications, 20(4):856-86) 1976.
Jakob Foerster, Ioannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning to Communicate with Deep Multi-Agent Reinforcement Learning. In Advances in Neural Informa- tion Processing Systems, volume 29, Curran Associates, Inc., 2016. URL https://papers.niss.om paper
Abstaa html
Robert G Gallager. Information theory and reliable communication, volume 588. Springer, 1968.
A.J. Goldsmith and P.P. Varaiya. Capacity, mutual information, and coding for finite-state markov channels. IEEE Transactions Information Theory, 42(3):868-888 886, 1996. doi: 10.1 109/18. 490551.
S Ashwin Hebbar, Sravan Kumar Ankireddy, Hyeji Kim, Sewoong Oh, and Pramod Viswanath. Deeppolar: Inventing nonlinear large-kernel polar codes via deep learning. arXiv preprint arXiv:2402.08864, 2024.
Onésimo Hernández- and Jean B Lasserre. Discrete-time Markov control processes: basic optimality criteria, volume 30. Springer Science & Business Media, 2012.
Yihan Jiang, Hyeji Kim, Himanshu Asnani, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath. Turbo autoencoder: Deep learning based channel codes for point-to-poin communication chan- nels. Advances in neural information processing systems, 32, 2019.

---

Published as a conference paper at ICLR 2025
Yihan Jiang, Hyeji Kim, Himanshu Asnani, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath. Learn codes: Inventing low-latency codes via recurrent neural networks. IEEE Journal on Se- lected Areas in Information Theory. 1(1):207-216, 2020.
Mustafa O. Karabag, Melkior Ornik, and Ufuk Topcu. Least inferable policies for markov decision processes. In 2019 American Control Conference (ACC), pp. 1224-1231, 2019. doi: 10.23919/ ACC.2019.8815129,
Hyeji Kim, Yihan Jiang, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath. Deepcode: Feed- back codes via deep learning. Advances in neural information processing systems, 31, 2018,
Hyeji Kim, Yihan Jiang, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath. Deepcode: Feed- back codes via deep learning. IEEE Journal on Selected Areas in Information Theory, 1(1): 194-206 2020.
Ross Knepper, Christoforos I. Mavrogiannis, Julia Proft, and Claire Liang. Implicit commu- nication in a joint action. In 2017 12th ACM/IEEE International Conference on Human-Roue Interaction (HRI, pp. 283-292, 2017.
Victoria Kostina, Yury Polyanskiy, and Sergio Verd. Joint source-channel coding with feedback. IEEE Transactions on Information Theory, (3(6):3502-3515 2017.
Ashok V Makkuva, Xiyang Liu, Mohammad Vahid Jamali, Hessam Mahdavifar, Sewoong Oh, and Pramod Viswanath. Ko codes: inventing nonlinear encoding and decoding for reliable wireless communication via deep-learning. In International Conference on Machine Learning, pp. 7368- 7378. PMLR, 2021.
Jeffrey Martz, Wesam Al-Sabban, and Ryan N Smith. Survey of unmanned subterranean explo- ration, navigation, and localisation. IET Cyber-Systems and Robotics, 2(1):1-13, 2020.
James Massey, Causality, feedback and directed information. In Proc. Int. Symp. Inf. Theory (ISSic.())) pp. 303-305, 1990.
Haim Henri Permuter, Himanshu Asnani, and Tsachy Weissman. Capacity of post channel with and without feedback. IEEE Transactions on Information Theory, 60(10):6041-6057, 2014. doi: 10. 10.1109/TTT.2014222
Haim Henry Permuter, Tsachy Weissman, and Andrea J. Goldsmith. Finite state channels with time-invariant deterministic feedback. IEEE Transactions on Information 552)64665 2009. doi: 10.1 10.11000.2200002200999990
Hossein Pirayesh and Huacheng Zeng. Jamming attacks and anti-jamming strategies in wireless networks: A comprehensive survey, IEEE Communications Surveys & Tutorials, 24(2)7667-809 2022. doi: 10. 10.1009/COMMT..02233155555
H. Vincent Poor and Rafael F. Schaefer. Wireless physical layer security. Proceedings of the National Academy of Sciences, 1 11((1):1-266, 2017, doi: 10.1073/pnas.1118101111 URL
10t.://....0///aa..aa...a.. 1618130114
Martin I. Puterman. Markov decision processes: discrete stochastic dynamic programming. John
Wiley Sons, 2014.
Oron Sabag, Haim H. Permuter, and Henry D. Pfister. single-letter upper bound on the feedback capacity of unifilar finite-state channels. IEEE Transactions on Information Theory, 1392 1409, 2017. doi: 10.1109/TT:2201.2222 2636686....
Claude E Shannon. Channels with side information the transmitter. IBM journal of Research and Development, 2(4):289-293, 1958.
Eli Shemuel, Oron Sabag, and Haim H Permuter. Finite-state channels with feedback and state known at the encoder. arXiv preprint arXiv:2212. 12886, 2022.
Eli Shemuel, Oron Sabag, and Haim H. Permuter. Finite-state channels with feedback and state known at the encoder. IEEE Transactions on Information Theory, 7013):6610-1626 2024. doi: 10.1 1.110/9T.222333333999
12

---

Published as a conference paper at ICLR 2025
Samuel Sokota, Christian A Schroeder De Witt, Maximilian Igl, Luisa M Zintgraf, Philip Torr, Mar- tin Strohmeier, Zico Kolter, Shimon Whiteson, and Jakob Foerster. Communicating via markov decision processes. In International Conference Machine Learning, pp. 20314-20328. PMLR, 2022.
Sainbayar Sukhbaatar, arthur szlam, and Rob Fergus. Learning multiagent communica- tion with backpropagation. In D. Lee, M. Sugiyama, U. Luxburg. Guyon, and R. Gamett (eds.). Advances in Neural Information Processing Systems, volume 29. Cur- ran Associates, Inc., 2016. URL. https:/proeeddings.euuisssc//o/o 15h119777iatee33044880b7.b666663 ea00 Paper.pdi]
2iex//pape/2216//hle/
Zheng Tian, Shihao Zou, Ian Davies, Tim Warr, Lisheng Wu, Haitham Bou Ammar, and Jun Wang. Learning to communicate implicitly by actions. arXiv:cs.A1:18110044444 2019. URL https://
hiww.org/bss/1800004a.
S. Trenholm. Thinking Through Communication: An Introduction the Study of Human Commu- nication (9th ed.). Routledge, 2020. doi: 00.4324/9781003011
Tze- Yang Tung, Szymon Kobus, Joan Pujol Roig, and Deniz Gündüz. Effective Communications:
A Joint Learning and Communication Framework for Multi-Agent Reinforcement Learning Over Noisy Channels. IEEE Journal on Selected Areas in Communications, 39(8):5500-203,, August 2021. ISSN 1558-0008.
doi: 10.1009/SAA:2222133877444 URL https://icceeplorr.ieee. /rg/
documen/94466501
S. Verdu and Te Sun Han. A general formula for channel capacity. IEEE Trunsacioos on Information Theory, 144--1177 1994. doi: 10. 109/18.3356..
Wolfhard von Thienen, Dirk Metzler, Dong- Hwan Choe, and Volker Witte. Pheromone communica- tion ants: detailed analysis of seppentrrationdepeeeeee decisions in three species. Behavioral ecology and sociobiology, 68:161 1-1627, 2014.
Jiaming Wang, Sevda Ögüt, Haitham Al Hassanieh, and Bhuvana Krishnaswany, Towards practical and scalable molecular networks. Proceedings of the ACM SIGCOMM 2023 Conference, ACM SIGCOMM '23, pp. 62 22-76. Association for Computing Machinery, 2023. doi: 10.1145/3603269. 3604881.
Rundong Wang, Xu He, Runsheng Yu, Wei Qiu, Bo An, and Zinovi Rabinovich. Learning Efficient Multi-agent Communication: An Information Bottleneck Approach. In Proceedings of the 37th International Conference on Machine Learning, pp. ISSN: 2640-3498.
PMLR, November 2020. URL
https://pooceedingss...ppp http:ppees///1///gg///// 19/
Christopher M Waters and Bonnie L Bassler. Quorum sensing: cell-to-ced communication bacte- ria. Annual Review of Cell and Developmental Biology, 21(1):319-346, 2005.
Ron Weiss and Thomas F. Knight. Engineered communications for microbial robotics. In Anne Condon and Grzegorz Rozenberg (eds.), DNA Computing, pp. 1-16, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg. ISBN 978-3-540-44992-3,
Michael Zhang, James Lucas, Jimmy Ba, and Geoffrey Hinton. Lookahead optimizer: k steps forward, step back. Advances in neural information processing systems, 32, 2019.
13

---

Published as a conference paper at ICLR 2025
APPENDIX
A NOTATION AND DEFINITIONS
To bridge the RL and FSC areas, we list and explain the notations used in this paper. Note that lowercase and uppercase bold letters represent vectors and matrices, respectively,
Table I: Notation table
In general a x X
Sequence { T141y... Znh. sequence { Ik
Cardinality of set
MDP: (T,,),
MDP state and action at Reward function and initial state distribution State and action space for MDP Transition kernel and control policy
r.a
S. X
T.
FSC: (X' x PyS.- S)
Te Vr, $t
Channel input, output, and state at Channel input, output, and state alphabets Future and current state (random variables)
N.Y.S
St.S
E
Encoder and decoder
k
Message bit length and the code length
RE,D = k/n
Rate of code (E,D) D)
Action-state channel:
P |x,, ;*))
8t, Zt S
State and action at
State alphahet, action alphabet
S+,
Future and current state (random variables) Encoder, decoder, transition kernel, average reward
E, D, T, Ge k n,n.H
Message bit length, code length, and rate
S ii-ntt1 EAS channel for Act2Comm: P(s++1 ju" s²)
The state sequence associated with the i-th message
St. Ir, usi St,S
State, action and decision rule at t; Target policy
Future and current state (random variables)
u, X.
Alphabets of decision rule, actions, and states transition kernel and average reward Encoder, decoder, and critic network.
T. Ge
8().
0.E.
Parameters of encoder, decoder, critic network Encoded belief map and codeword Message and feedback block at coding round r Control policy at coding round
Z.U
B(T), (tF)
(()
M
Decoded logits
2(-)
Quantizer
Call
Weighted loss function to update the encoder Communication loss term and Control loss term
Leoms Lcont
MSE loss for critic network
(1(())))
Frequency of selecting action in state across U Estimation temperature for control policy
fu((xs)
Estimation of fo (a]ss)
Zu. WR
Sampled neighbors of Z and its Gaussian
M
The corresponding logits from the frozen decoder
Ma
Predicted logits from the critie network (the k-th step)
14

---

Published as a conference paper at ICLR 2025
Encoder Controtir
P(euua Me)
Pu
Decoder
Encoder
Controllar
P(un))
Decoder
NDP environent
(4), Action channel
(b). Extended acton-state chancel
Figure 6: The action-state channel and equivalent extended action-stati state channel.
B TECHNICAL PROOFS
This section presents the proofs of Section
B.1 PROOF OF THEOREM 1
The proof of Theorem 1 rrelies on converting the action-state channel to an equivalent channel. This equivalence is also stated in Section 5 it is crucial for the design of Ac12Comm. To enhance readability, we present the equivalence here as well.
Let A X15), where each E l referred to as a decision rule because the i-th element of u, de- noted by u(i), be viewed rules spanning the entire time horizon. To facilitate the capacity analysis, we convert the action- state channel into an extended action-state (EAS) channel, depicted in Fig. 6 using Shannon's method (Shannon 1958). In particular, we conceptually separate the encoder and controller, consid- ering the controller as an integral component of the EAS channel. We then assume that the channel state is available at the controller but not the encoder. At each time f, the encoder selects a decision rule ur from U. Then the controller uses u, and the state 8t to determine an action T; = (s.)... Consequently, the EAS channel has an input alphabet U, output alphabet S, and channel law:
action for state i. A control policy is thus collection of decision
|s (9441881,, = Pst (8+41 1s,, us())) T(st+ us(s)).
The EAS channel and the action-state channel equivalent, and we will examine the EAS channel instead of the action-state channel to derive the capacity.
Assume that the initial state of the action-state channel is fixed to be $1. Then it is well-known that the capacity of the EAS channel is (Gallager 1968)
C(si)
max (p(a.la'
lim N
I(UN; ; ; +N
(14)
where ; +SN+1(s) is the mutual information given by
P( P(NN+ +1 I ,1))
:N = Σ Σ
P(uM)
NN+ I 81) log
E.v EuN plz P( 12
a EEU
LESN
For two random variables S and X, let (X|S) denote the conditional entropy Cover 1999 of X given S. Then we have
lim N
S T(U (NN+ 1s1
lim N
[H(++1 - .s1]
N
lim
[H(S I(S5+11S5) U N,,,
N+000
lim
[H(S 81) HS, 81,
N=200
lim
I(X;; (111
N
N
15

---

Published as a conference paper at ICLR 2025
where (a) holds because X, is determined by St and Uz. It follows that
C
max {p(u, /u-
lim 122 N0000
1(0 +s*+)ss)
N
(
lim {p(2, 22 hhs N-
max
1 (X;; S:+1 (1,
N
(6)
max
lim 400
1 N
Σ S(11,,)
(15)
(p(2.)a.)22
In equation 13 (a) follows from the equivalence between the action-state channel and the EAS channel. We next prove (b). Let 7 denote history-dependent encoder and (ny]ss " ,,'-1)) N21 denote the associated input distribution. Furthermore, let (s, x) denote the probability that S; = and X; = s conditioned on the encoder v). Note that can be viewed as history-dependent policy for the MDP. Then according to MDP theory, for any history-dependent policy 17, there exists Markov policy r such that 7) and r/' share the same joint probability distribution of states and actions. In particular, denote by n/ (z; s;)) the probability of selecting action 2; given that the state is at time i. Then of can be seen as Markov encoder with input distribution (1/((((8))) By letting
Σ
ne x0=ls""x''111 x P(s" P(="""1x""1
_x 181),
have
(s 2/81) = P. (8, Vi 1
We omit the proof here. The interested readers referred to Theorem 5.5.1 of (Puterman) 2014) for the formal statement and proof. Consequently, we can verify that for any history-dependent encoder n, there exists a Markov encoder v/ such that they result in the same (Xx;; S s1) for all i:
T ((s:41|s;,1)
Ix(X;; 1S)
= Σ Σ 8.E8 Z,EX
(81,
Σ #++1ES
((s+t1181, 2;) log Σx: T(s+ (m)
(8
= Σ Σ
P. 2:(s1)
Σ $111ES
T(s++1 18;, log
En! ( (s (m)
s,ES 2,EX
We thus conclude that restricting on Markov encoders does not result in any loss of capacity.
Next, we show that, far as finding a capacity-achieving encoder concemed, it is enough to consider stationary encoders. To see this, we reformulate equation 15 as a dynamic programming (DP) defined as follows:
state at time i: s; E S
action at time i given state si (si) E A(X) with (z,ls;) P(æ.(si) being the i-th element transition law: P(5.+1|5(,22) = Enjex (
reward function:
T T(814118i,2)
r(s (s:))
Σ (I.(ss)) Σ
T(s log En: T 1844 21)
xEE
Then the capacity expression given in equation 15
can be written as
N
C= max lim (a:h21 N NO
Σ E P(s.)r(s.
(16)
1=1 SLES
We can think equation a6 as problem of maximizing the long-term average reward of the above DP over the set of Markov deterministic policies. Essentially, the DP is an MDP with finite state space, compact action space, and bounded reward function. We can easily verify the following:
1. The reward function is continuous function of action de.
16

---

Published as a conference paper at ICLR 2025
2. The transition law depends continuously the action d₃.
3. Any stationary policy yields a Markov chain with one ergodic class and possibly empty set of transient states (by our assumption).
Then, according to MDP theory (see, e.g.. (Fainberg 1976) and (Hernández-Lerma & Lasserre) 2012 ) the maximum of equation I6 can be attained by a stationary deterministic policy. Therefore, problem equation 16 equivalent to
1 100 N
C = (((
lim
Σ ((1; s1).
(17)
Note that each (-((-ss) E A(X) : S} corresponds stationary policy for the original MDP. Under the assumption that the MDP is unichain, any stationary policy yields a Markov chain with equilibrium state distribution Pr (s()). Therefore, the following probability converges to probability that is independent of $1
lim P(X: x, S: = 8, S.+1 = ='|ss) p (s) 1)) 1-000
As result, I(X;; SS, $1) also converges to value that is independent of $1. The desired result follows immediately.
B.2 PROOF OF THEOREM 2
We first show that the capacity of the action-state channel without reward constraint can be written as:
C
max [(w, T).
(18)
wEW
To see this, using Theorem and the formula ((nmulax(x(s))) wn (s, ) Wx wx, yields
T(8'1s,
-(:;118)= -E
P+ (s)
Σ
T(s'|s,,2) log Σx T |s, (2)((=))s))
sES&EX
S'ES
T T(s'(s, E.t Wy (s, Σx T(s' (s, x, (s
ΣΣ #ES
(x
Σ S'ES
log T(s(ss,
Then the equivalence between equation
18 and the capacity expression given in Theorem follows immediately from the one-to-one mapping between W and IIs.
It is well-known that the long long-term term average reward of a policy can be expressed as a linear function of its occupation measure:
G
Σ r( 21)(s1 ~
-ΣΣ Wn (5,
(19)
+OC
SES TEA
Since the reward constraint is linear, to show that the optimization problem is a convex optimization, it suffices prove that [w, T) concave function. For any E [0, and À 1 X, let = Aw + Awa, where W1, W. Then we have
Σ., T(s' x')
Σ T( log T(s' T(s'ls, Dgn w(8 ZEN
Σx (s' (s, x )w0(,
Σ ZEA
w(s x:) T (2'1s118,,) 18,2; log
Σ
(18 (()s)))(ssssss log (8'188 x).
En w0s x!)
ZEN
(20)
17

---

Published as a conference paper at ICLR 2025
The second term of equation 20 clearly linear w.r.t. For the first term, application of log-sum inequality gives
Ev 2'5)s,,2))((s_ Exe 2(s
Σ FE
w(s, x T){((s))
log
Ex T [[5|18,27 (u1 Ex" Wi (s, x!1)
Σ
wh (x) x (=((s,)
log
Ex T 2') Exe Why x,) W2(5, (s s, log
(21)
Combining equation 20 and equation 21 yields
((s'(s,2) w(, w(s
Σ ZEX
wrs x. x)
s, log
Σxe T(s' 18, (1)2))0(8820))
ss'' s,
W1 (3,2")
W1 W1 TT [s. log
Σx (s 8, x "',') (s,
aEX
s 8,
W2(5, x") En (ss's,, (32
+ x
x (T(ss,)T(ss\ss,,,)) x) log
(22)
FEX
Summing both sides of the above inequality over and 8' yields
[[w, T) [(Aw] + Xwz, T) 2 (1 T) + ((w,,,
We thus conclude that (w, T) is concave function w. This completes the proof.
B.3
PROOF OF LEMMA
Define
w(s 2)(s,)) )
Wy = w E W: ΣΣ
#ES #ES SEX
For any achievable V1 and V2, let
wi arg max I(w, T), i= 111 wEWy
Then C(V)) [w,, T). i 1, For any 0 [0, 1]. let 0 - Let V 0V1 012 and
W3 = Owl + Owz. Then clearly W3 Wy. We thus have
C(V)- = max (w, T) 2 I(w3, T) 2 (I(w,, T) + (1w,, T) = 0C(V)) + (C((V).
wEWY
We thus conclude that C(V) is concave.
B.4 PROOF OF LEMMA 2
Since 1(w, T) is concave w.r.t. w and l(w, W,, T) linear w.r.t. w, show that l(w, w,, T) is tangent line of I (w, T) at point t., it is enough to prove that statements (i) and (ii) hold. Statement (i) holds trivially by the definitions of the two functions.
For statement (ii), consider
1w, Wn, T)
T(w, T)
En wp(xx"))
Ex
((s, x)
Σ
(s'lss,a log Ex T( (,, Exd w(s x!1)
NES x
s'ES
Define
Pa(ssls) En T(s (sslss, x² )')(w)))2))
Pw. (s'|s)= = Ex, T(s' s, Wen((n)))))
Exd w( x
Ex Wn Wn(s (s,
18

---

Published as a conference paper at ICLR 2025
Note that E. Pu(s'(s) 1. Hence it is indeed a conditional probability. Then
Pur (s)()')s) Par, (5'18)
1(w, Wn: T) - 10,, T)
ΣΣ
Σ w(s
w(s, (s)' log
(w(('ls) log Per (s Pw. (s'(8)
Σ
())
Σ
#ES FEA
s'ES
2 0,
where the inequality follows from the non-negativity of relative entropy. Therefore, Uww Whi T) is tangent line of [ww T) at point w/-
C SYSTEM EXPLANATION AND ALGORITHM DETAILS
In this Appendix. we first clarify the relationship between the theoretical results in Section and the algorithm in Section 5, as this distinction may be unclear to those unfamiliar with information and coding theory. Following this clarification, we provide additional details about the components of Act2Comm.
The concave optimization problem in Theorem characterizes the capacity-reward tradeoff of the action-state channel. It provides upper bound for practically achievable coding rates under certain reward constraint. Solving the concave optimization yields the capacity and the optimal state- action distribution which can be translated to stationary policy for the MDP via the following formula:
(aas)) as Ee a(s
Note that this policy æ can not be directly used as the coding policy for communication, as the coding policy needs generate actions based on both the state and the message. Therefore, in Section 5, we propose Ac12Comm to learn coding policy that mimics the behavior of policy from perspective of MDP control, with the input of message and feedback block.
For practical channel coding in the finite block-length regime, historical feedback has proven ben- eficial based on prior experience with conventional channel coding. To effectively map messages and feedback to actions, the transformer architecture with attention mechanism is naturally well- suited, forming the backbone for both the encoder and decoder components.
The components of communication via actions in MDPs using the proposed Act2Comum summa- rized in Table. 2 In particular,
The encoder encodes belief matrix (r) E R
using message block (T and feed- back block (T) at each coding round After completing all coding rounds, final belief map Z R
ei
! #|s is constructed. Note that instead of directly outputting actions each time step, our encoder generates a continuous belief map, which is subsequently quantized into decision nules. This approach not only enhances performance but also simplifies the training of the critic network.
A quantizer then generates the codeword U SIx & where each element of the resultant codeword, = Us t]. represents the selected action for state 9, at time step t.
Given the action and state, EAS channel then returns the next state.
The decoder collects all states and then performs the decoding process, which outputs logits M
f x2" for the message.
Since the gradient cannot propagate through the EAS and quantizer to the encoder, critic network is introduced to link the belief map Z to the decoded logits M. Specifically, the critic network is trained to predict Mt from Zg. producing Ma each inner optimiza- tion step & within the total 8in steps. Thanks to the introduction the critic network, the gradient can propagate through from logits to the belief map. As shown in the table,
19

---

Published as a conference paper at ICLR 2025
Table 2: Functionality of Each System Component
Model components
Function
Input B(T), C..)
Output
Encoder
Coding the belief matrix
Z
Quantizer
Generate decision rules
2
U
EAS channel
Generate state from actions
U 7 St
81+1
Decoder
Decoding the message
M + m
Critic Network
Estimate decoding logits
Zk
Mck
it effectively "links" the encoder's output to the decoder's output, thereby "skipping" the quantizer, EAS channel and decoder, which are treated as the unknown environment during the training phase.
C.1 QUANTIZER
The quantizer Q R + XIsIx is designed to convert real-valued coding results | Sigmoid(2 Z) into integers corresponding to actions within the channel input alphabet set X' {0. 1..., | - 1). For example, if there exist actions and 1 state, then each element of the coding result | Sigmoid Z) E (0, 5) will be rounded down into the nearest action index.
X Sigmoid Z) = [1.5, 2.1, 3.2, 4.8), it will be rounded down (1, 2, 3, 4] as the channel input via the quantizer Q.
Here, we adopt hard rounding. despite the availability of advanced quantization methods such soft rounding or noise injection during training. The chosen approach is intentionally straightforward, and critic network effectively mitigates the non-differentiabiity introduced by hard rounding.
C.2 CRITIC NETWORK AND ITERATIVE TRAINING
As shown in Fig. 7 a critic network is introduced to facilitate gradient backpropagation for encoder optimization, treating the quantizer, channel, and decoder as an unknown environment. Before up- dating the encoder and decoder, the Critic network is trained over 8in steps capture knowledge of the environment, with the encoder and decoder frozen during this phase. Subsequently, the encoder is updated with the assistance of the Critic network, aiming jointly optimize for control and com- munication, while keeping the decoder frozen. Following this, the optimized encoder is frozen, and the decoder is updated based the newly optimized encoder. With the updated decoder, the Critic network is retrained to adapt to the updated environment, preparing it to support the next round of encoder updates.
This process iteratively alternates between freezing one component while optimizing the other. From the experiment, we observe that the training process is more stable when the encoder updated once for every two updates of the decoder. The effectiveness of this approach is visualized in Fig. and Table The detailed training algorithm is presented in the Algorithm, 7
C.3 TRAINING AND INFERENCE ALGORITIM
To enhance readers' understanding of the training and inference process, provide the pseudocode and illustration figures for (see Fig. 7 Act2Comm, detailing both the training and inference phases, shown in Algorithms [ and 2 Furthermore, Fig. [I visualizes the training process by tracking the loss values throughout the iterative updates. For additional details about the training, the training logs and source code are also available the project page of this paper.
To be more specific for the training phase, we train the encoder first and then train the decoder. The critic network, with control loss, is applied to the encoder. The decoder only considers the communication loss. After training, the critic network is removed, as shown in Fig. 7 (c). Only the encoder and decoder deployed for communication and control, as shown in Fig. 8b
20

---

Published as a conference paper at ICLR 2025
Lall
CritioNet updates
CriticNet
Len
Forward flow
Encoder
Quantizer
Extended action-state channel
Decoder
Encoder updates
Unknown environment
updatas
(a), Gradient flow of Act2Comm
control communication
optimize communication
Decoder
CriticNet
CriticNet updates
Enooder updates
Decoder updates
Decoder
CriticNat
Unknown environment
Unknown environment
Unknown environment
(b). Neeativa training strategy
Receiver
Sequence partition
S
Sequence mergi merging
B
Encoder &g
Z
Quantizer 2(-)
Extended
Decoder
Model workflow when inference
Figure 7: Illustration of the iterative training process: (a) Gradient flow in the proposed method, where blue arrows indicate the gradient flow, and red arrows represent the forward process. (b) Diagram of the update steps, where the red block represents the component being updated, the blue block represents the frozen component, and the grey block indicates an unused component. (c) Inference phase for the well-trained Act2Comm model, where the critic network is removed.
Table 3: Number of parameters, FLOPs, and coding times for the Act2Comm scheme (K 12, μ R 1/3, 8in 20) with varying state numbers and action numbers, where the increased value are colored with orange and red.
Action and state number
Encoder
Decoder
([A), (S]) with [A]
(5, 16)
(20, 16)
(40, 16)
(5, 16)
(20, 16)
(40, 16)
Parameters (k)
32.244
32.244
32.244
50.536
50.536
50.536
FLOPs (millions)
0.3164
0.3164
0.3164
0.1989
0.1989
0.1989
Coding Time (ms)
6.691
6.691
6.691
2.613
2.613
2.613
([,), ST) with [S] 1
(5, 16)
64,
(5, 256)
(5, 16)
(5, 64)
(5, 256)
Parameters (k)
32.244
46.51
103.52
50.536
50.536
50.536
FLOPs (millions)
0.3164
0.4546
1.007
0.1989
0.1989
0.1989
Coding Time (ms)
6.691
6.69
7.04
2.613
2.613
2.613
C.4 COMPLEXITY ANALYSIS
To analyze the complexity of the proposed method, consider input size of 12 bits, blocks, and a rate of R = 1/3. The experimental results, presented Table were obtained using a single GPU-A5000 with 10, 000 runs for the "Erratic Robot" environment.
From the table, we observe that during the training process, the main computational complexity arises from the critic network, needs around 20 iterations for each encoder update. Note
21

---

Published as a conference paper at ICLR 2025
Algorithm Training strategy of the Ac12Comm scheme
Input: The initial MDP state: so, Inner optimization step: Sin.
Learning rates of encoder, decoder, and critic network: 3, a, a, with a = 53,
Target policy: и, balanced parameter X.
Output: Parameters of the encoder and decoder: 0, &.
for the i-th step within the total training steps do
:.:,:.;)) 3: C(2) 11*****0 x3
2: m [b1: b2: by] E (0,1)xx,
// Randomly sample and divide the message
// Initialize the feedback block
4: for each coding round (1 S T S 1) do
5:
B [2b] :; 2b,
RTX,
I/ Construct the message block
6:
C(r) [C1:...: C,] R x3
// Update the feedback block
7:
ZF7 (B((7)) C(T) T
g(r) = [T, E
||ا + R x
Encoding the belief map I/ Quantization, for decision rules
8:
U(r) = 2((2\Sigmoid (T))) E 1
9:
for 1: 7 do
10:
St+1 = T(s++1 St1 U (sc, (5.t]) d]),
Go through the EAS channel for to time steps Il Update the feedback vector
C (T) [st (T( zt (T) (T)
1641 R1x3,
12:
end for
C, [c
(T).
(T) R
I/ Update the feedback matrix
14:
end for
Z [ [1] E R x
s1.....;38 :si....:::]ES8 + S
15:
M D(s) R
// Collect codewords, states, and decode the logits 1f Truin the Critic network
17:
if 122 then
19:
for k 1 1: Sin do
Z = + Wk. with WA E x ~ ~((,000))
20:
// Neighboring sampling
Uk [(iX|Sigmo Zk)) E x1s1xtt
21:
22:
for f = 1:11: 1: : R
&
do
8t-1 T(s++1|s (s, end for
I/ Go through the EAS channel
24:
(()) : E E - S
I/ Collect the observed states
Mr (()( E TR fx2" x2"
26:
|| Decode the logits with frozen decoder // Predict the logits with critic network I/ Compute the critic loss with MSE Il Update the Critic network.
Mck C(Zk) E x222
27:
28:
Len = MSE(McR MR)
29:
Φ6+1 Φh BV Vo Loon
30:
end for
31:
II Train the Encoder with a frozen Decoder I/ Control loss term for the estimated Communication loss term I/ Update the encoder
32:
Lcont MSE π., f)
33:
Lrom cross-entropy (m, Me))
34:
V Ceom + XLcont
35:
end if'
// Train the Decoder with a frozen Encoder
37:
for each coding round and corresponding time step do (T) (B(r)) (T, + U(T),
38:
// Re-encode and re-quantize the decision rules // Re-go through the EAS channel for all time steps
39:
81+1 ((4+1 85, UGr) (12, ())
40:
end for
41: 8 ;s8 M = D(s)
I/ Decode the observed states from forzen encoder 1/ Communication loss term I/ Update the decoder
42:
Loom cross-entropymm., M) E WV
44: end for
22

---

Published as a conference paper at ICLR 2025
Algorithm 2 Inference of the Ac12Comm scheme
Input and output for the encoding:
Input: Initial state: So, k-bits message m, coding rate Rt well-trained encoder: 0"
Output:
Codeword (decision rules) Z E I x
Input and output for the decoding: Input: Observed states S well-trained decoder E*:
Output:
Predicted message: vn.
1: Encoding phase:
2: C(1) E 0|* x3
Initialize the feedback block
3: for each coding round (1 < < 1) do
4: ((r) [2b1 1; 2b,
E RTXP,
// Construct the message block // Update the feedback block
5:
C(r) ;
C+] E RT* x3
Z = (B( CC)) E R #1
6:
z(F) (T, E #18l
+ |2
Encoding the belief map I/ Quantization for decision rules
7:
U
Z)) E X1
8:
for = 1:::: do
E (r) = [s,,)) (J)
9:
(7) T( 8t 2
(r))
11 Go through the EAS channel for H. time steps 1/ Update the feedback vector
841
10:
C
(T) [s( o (7) (T)
841 ERIx
11: end for
12: C, |c
(T),
(T) #3
// Update the feedback matrix
13: end for
14:
()) E R MiSi
RIS
// Collect the final codeword
15: Decoding phase:
16: [s1; :8 S + x
// Collect the observed states
17: M D(s) R
// Decode the logits // Decode each block labels
18: in argmax (Softmax M), dim = -1)
Table 4: Number of parameters, FLOPs, and coding times for the Act2Comm scheme (K = 12, = 3, 1/3, Sin 20) with varying critic network training steps Sin for both training and inference phases. Note that the backpropagation computational complexity is approximately 2 times that of the forward computation.
Training Phase (forward)
CrititNet
CriticNet
CriticNet
Model components
Encoder
Decoder
8in = 5
8in = 10
8in 20
Parameters
32.244
50.536
7.568
7.568
7.568
FLOPs (millions)
0.3164
0.1989
0.1454
0.2909
0.5818
Inference Phase
Model components
Encoder
Decoder
Critic network
Parameters (k)
32.244
50.536
X
FLOPs (millions)
0.3164
0.1989
Coding Time (ms)
6.691
2.613
X
that the back back- propagation FLOPs can be estimated by multiplying the forward FLOPs with a factor (typically 2-3x). During inference, the critic network is removed. We observe that the encoding process can be completed within 10 ms, while the decoding process is even faster, taking less than for the message.
23

---

Published as a conference paper at ICLR 2025
We also analyze the complexity of approach concerning increasing state and action spaces. Specifically, based on the design of Act2Comm, the number of actions does not impact the scaling performance of the model, in terms of the computational complexity. A larger action space primarily contributes to more divensity in decision rules, without increasing the computational complexity of the approach. For increased state spaces, the complexity grows only in the encoder component. This occurs because the computational complexity of the encoder increases as the output matrix size expands with the number of states.
However, environments with more complex action or state spaces may lead to a more challeng- ing learning process, potentially affecting performance. To validate our method in such scenarios, we introduced new environment, the "Erratic Robot," which features a five- space. Results demonstrate that our method remains effective, even in this more complex setting.
C.5 VECTOR REPRESENTATION OF STATES AND ACTIONS
This paper focuses on MDPs with finite state and action spaces, which allows us to represent states and actions as scalar integers by indexing them. This means that even when states and actions are vectors, they can be mapped to scalars. We adopt this approach in the proposed Act2Comm for ease of presentation. However, can be beneficial in some MDPs. This can be implemented with minor adjustments to the feedback structure for the encoder and the input structure for the decoder.
worth noting that using vector representations for states and actions
Specifically, with vector representations, the feedback vector is defined as: c,²") P at (T) Here, st E Sixn, and (() Slix, are the vector representations of states, rather than their scalar counterparts (i.e., indices); similarly, 2²(T) x1 the vector representation of the ac- tion. Accordingly, the feedback matrix is defined as C, = (T) : (T) E R (2n, and the feedback block can be constructed as ((T) & [Ci:...; C+| E R state observations 8 A [s1....;;8.] SSxx, xn, are fed into the decoder to produce logits.
s1t1l IR (2), where n, and n, are the dimensionalities of state and action.
(+)
x t (22, Consequently,
To evaluate the effectiveness of Act2Comm with vector representations, we applied this variant to the "Catch the Ball" scenario with R 1/3 (cf. Fig. 4ap. In this environment, the state is represented as a vector [sa.$)]. where Sa E {0, 1, 2} indicates the position of the board, and 86 {0, 2, 3, 4,5, 6, 8, indicates the position of the ball. The performance of Act2Comm with vector representations in this experiment is very similar to that achieved with scalar state represen- tations, as shown Fig. 4 Notably, we observe that the vector representation offers advantages such as more stable and faster convergence during training. This is illustrated in Fig, Ba] where the loss value decreases and converges more quickly during training compared to the scalar state repre- sentation counterpart. An intuitive explanation for this result is that the vector state representation captures more detailed features of the environment, which may potentially facilitate learning.
D EXPERIMENTAL DETAILS
D. EXPERIMENT SETUP
For the an Adam-based lookahead optimizer (Zhang et al. 2019). The inner-training for the critic network consists of sin 20 steps, with a noise variance of 0.1. Each block has a length of μ 3, and temperature parameter is as 10, 7 50, = 100, 200. The performance presented is averaged over 20, 000 execution times. To investigate the trade-offs, we train the Ac12Comm model with À E [0.01, 20).
scheme, we train the model with batch size of 4096, learning rate of 0.001, and
The detailed architecture of the Act2Comm scheme is provided in Fig. 8b At the transmitter, transformer-based encoder is utilized generate the z()) from (T) and ( for each coding round. Specifically, (T)) and B(r) are firstly processed through multilayer perceptron (MLP) lay- ers, then concatenated for linear projection and positional encoding operations, resulting in Fo e
R where d is the hidden layer dimension. After I., transformer layers, the resultant Fi, E R?
24

---

Published as a conference paper at ICLR 2025
8c 5219
Scalar state representation representation
2.0
tr
Linea Projection
NLP Layer
Transforer Layer
1.5
A
Positional Encoding
Transforeet Layer
LO55
1.0
Postionnl Enceding
Transformer
f f
f Projection
Transfomerr
Layar Horm
ULP Lape pil
Lyue Projection
HL Lppi
2003 Step number
0200
Tranaformer Layer
Bill
Bi cit
Encodar
Decoder
(b)
Figure 8: (a). Training process comparison for scalar state and vector state representations, where 20, 7 50 and 1/3. (b). The architecture of the Act2Comm.
5
22
(a) Lucky wheel.
(b) Catch the Ball.
(c) Erratic robot.
Figure 9: Illustrations of experimental MDP environments
is further transformed by a fully-connected layer into (Tr), The decoding process begins with re- shaping S into S This reshaped S is then processed symmetrically through fully-connected layers, positional encoding, and L, transformer layers, yielding the feature DL, E R Subse- quently, DL. is input into fully-connected layer to generate the logits M E g for each block. After softmax function, predict the label of and transform into bit stream m. Specifically, we set d 32, L, and L = 4 during the experiments.
D.2 LUCKY WHEEL
As illustrated in Fig. Da the wheel is evenly divided into three regions. At each time step, the player can select either action action where action 0 corresponds clockwise rotation of the wheel, and action corresponds to an anti-clockwise rotation. If action 0 is selected, there is probability p 0.2 that the pointer remains in its current region, and probability 1 = 0.8 that moves to the next region in the clockwise direction. Similarly, if action 1 is selected, there is probability
p = 0.2 that the pointer remains in its current region, and probability 1 - = 0.8 that it moves to the next region in the anti-clockwise direction. The rewards for the three regions are 5, -5, and 0. respectively. The player receives a reward at each time step based on the region in which the pointer located.
D.3 CATCH THE BALL
The "Catch the Ball" game is set in a x 3 grid, as illustrated in Fig, 9b A ball randomly appears at the top of the grid and descends one grid space at each time step. Meanwhile, board at the bottom moves horizontally to catch the falling ball. Each time the board successfully catches ball, the player receives a reward r. If the ball falls to the bottom of the grid without being caught, disappears, resulting in penalty of for the player. At all other times, there rewards or
25

---

Published as a conference paper at ICLR 2025
107
0.7
Ootimall
107
93
BER
10+
Achivvbble
107
Re188
R-1/2
Tareet AFR:
10*
10
Re115
Twrgel BER:-
ToggtBER: 2:
Dager mornd
Coding rate
Coding
(a) BER v.s. Reward
(b) Reward v.s. Rate
(c) BER v.s. Rate
Figure 10: Control-communication trade-off of Ac12Comm in 'Erratic Robot".
penalties for the player. After ball disappears or is caught, new ball appears randomly (with equal probability) at one of the three positions at the top of the grid.
The player has three available actions to move the board: move left, move right, remain stationary. If the player chooses to move left or right, there is probability p E [0, 1) that the movement fails (in which case the board remains in its current position), and probability 1 that the board moves for one grid space successfully as intended. Additionally, any action that attempts to move the board outside the grid will always fail. In this experiment, set 5 and p 0.8.
D.4 ERRATIC ROBOT.
The 'Erratic robot' game takes place on 4x4 grid map with 16 states and 5 actions, as shown in Fig. 9c The robot is designed to minimize the number of steps required to collect goods while avoiding obstacle points. Specifically, its primary objective is continuously take goods from designated destination points, earning a reward of +5 for each successful collection. The grid also includes four obstacle points, each incurring penalty of -2 when encountered. The robot has five available actions: move left, move right, move up. move down, or remain stationary. Due to the instability, any movement of the robot has probability p [0, 1) of resulting in an additional unintended step. Actions that would move the robot outside the grid boundaries always fail. In this experiment, the probability of additional operation set to p = 0.2. The results are presented in the Fig. I0
As shown in the Fig. 10 the proposed Act2cComm scheme can achieve perfect communication with R = 1/5, albeit with reduction in the average reward from the optimal value 753 to 0.45. If we relax BER, the same rate can be achieved with better reward. Similarly, for different reward targets, we can obtain different communication performances. This additional experiment also highlights the versatility of the proposed Act2 scheme across various environments.
E ADDITIONAL. ABLATION EXPERIMENTS
This section presents additional ablation experiments for our proposed Ac12Comm framework, using the lucky wheel environment as the default experimental setting with initial state 0.
E. ABLATION STUDY OVER DIFFERENT MECHANISMS
To showcase the efficiency of our approach, present the loss values monitored throughout the iterative training process in Fig. II While the loss value occasionally fluctuates during the training poddates-primarie due to the alternating update scheme between the decoder and encoder- the model exhibits a rapid and consistent convergence.
Additionally, further validate the performance of the Critic Network, compare the estimated loss values generated by the Critic with the true loss during training. As shown in Fig. I1 the Critic Network maintains accurate loss estimation throughout the training phase.
We present a detailed comparative analysis of each mechanism within our method, as shown in Table 5| emphasizing the specific contributions of each component to the cumulative performance
26

---

Published as a conference paper at ICLR 2025
Loss value during the training
Prediction From GillsNel
Model Variant
BER performance vs. Act2Comm
Ac12Comm schome
Feedback coding
00
X Appropriate policy noise
Block-wise coding
09
Lookahead optimizer
/ CritieNet for loss
Not work Not work
00 203
Perfect policy
4933
600
600
3303
Step number
Figure 11: Loss during the training process, where the loss value decreases significantly with each decoder update, while showing a slight increase with each encoder update.
Table 5: Ablation study when sequentially removing one im- provement after another. Note higher BER means worse per- formance for given reward here with R 1/4.
arrgetrent reward
10
10a
1=
Tagg Revia
R-1/5
10
BER
10-3
10"
Act2C
Act2C omm with History---aaao dependetedd
10
0
30
Channel coding rate
Reward
(a)
(b)
Figure 12: (a) Performance for different coding schemes. (b) Approaching a given policy म.
improvements. Notably, utilizing the Critic network to predict the loss directly, or eliminating policy noise during inner-step training can yield failure, underscoring the critical importance of appropriate policy noise and neighboring sampling mechanisms.
All these design elements collectively ensure that our proposed solution consistently delivers robust performance across a wide range of scenarios.
E.2 ABLATION STUDY OVER THE FREDBACK DESIGN
Act2Comm supports both history-dependent coding, which encodes using both message and feed- back blocks, and Markov coding, which encodes using only the message block. We examine Act2Comm scheme with both distory-dependen codes and Markov codes across various coding rates R for a pure communication optimization.
The experimental results are depicted in Fig. 12a is evident that the BER performance improves significantly as the channel coding rate decreases. Specifically, with a coding rate R = 1/6, the BER reaches 10-6 level, indicating a significant enhancement in performance due to the increased number of channel uses. Comparing history-dependent codes with Markov codes reveals that in- corporating feedback blocks can yield substantial performance improvements. Although, from theoretical perspective, channel feedback does not enhance the capacity a memoryless channel, is beneficial for finite block-length coding. The observed benefits may be attributed to the attention mechanism applied to historical states and their corresponding actions. This mechanism effectively utilizes prior coding experience simplify the subsequent coding process.
27

---

Published as a conference paper at ICLR 2025
E.3 ABLATION STUDY OVER THE MESSAGE LENGTH
Additional experiments with Ac12Comm are conducted across different message lengths and coding rates, presented in Table. 6 The results demonstrate that Ac12Comm scheme consistently delivers competitive performance over different message lengths and coding rates. An interesting observa- tion that communication performance generally improves with longer block lengths; however, eventually declines due to the increased learning complexity, Notably, for longer message lengths k adapting a larger block size j can potentially enhance performance while addressing the increased learning complexity.
Coding rate
k = 12
k == 24
36
R = 1/2
1.16e
1.06e. -2
9.15e-
R = 1/3
1.06e
1.02c
1.14e
R = 1/5
2.84e
1.62e 3
2.06e -5
Table BER for Act2Comm across different message length and coding rate, where μ 3.
E.4 ABLATION STUDY OVER A SPECIFIC POLICY
In the previous experiments, we used the optimal control policy as the target policy for training the encoder, as this is better for achieving a higher control reward. However, our approach is highly flexible and can adapted to any control policy, allowing users to tailor the system to align with specific policies for their own tasks.
In the lucky wheel environment, now we consider a sub-optimal policy म as the target policy, given as:
T x 0 0)
<T = 1 s 0) I 100=1p <(
70.7
0.3
x 0. 1)
0.3
0.7
(23)
( 0|s 2)
2)
0.7
0.3
We evaluate the Ac12Comm scheme with different coding rates and consider single message trans- mission with an accumulated reward. The experimental results in Fig. 12b display the curve repre- senting the lower envelope of all possible reR-reward trade-off outcomes for each coding rate. This curve illustrates that the region above it is achievable by our Act2Comm scheme.
Notably, our method can achieve good communication performance, approximately 4 x 10-1, X 10-2, and x 10-3 for R = 1/3, R = 1/4, and R 1/5 respectively, with almost no loss in control performance. This is due to the stochastic nature of our target policy, as opposed to a deterministic one, allowing our method to adaptively learn a similar policy that maintains comparable rewards while being more favorable for channel coding. In summary, the experimental results demonstrate that our Act2Comm framework achieves satisfactory communication performance while maintaining the reward, defined by specific policy, at a certain level in scenarios such as those involving stochastic policies.
28


Reviews:
[{"review_id": "uzWqeedPcj", "reviewer": "Reviewer_dvdt", "summary": "The paper presents an analysis and method to allow RL agents to transmit messages through control actions as sequences of visited states, trading off average reward for information rate of the transmitted message. They provide theoretical results on the maximum information theoretic capacity such transmissions have, and propose a model and algorithm to do this efficiently.", "questions": "- What would be a general motivating example for wanting to trade off rewards for information rates in the state sequences?\n- The theoretical results in page 6 revolve around concavity with respect to the joint stationary distribution. However, we usually cannot directly solve this, since the only control variable is the policy. The stationary state distribution in an mdp is an infinite product of transition matrices, which depend linearly on the policy. How do these results translate to policies? If they don’t, are they really useful?\n- Section 5 needs some intuition. After the theoretical results, the particular model architecture choice is not obvious.\n- In line. 452, it is stated that at each step of the algorithm, a critic needs to be trained to estimate the gradient. How costly is this?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The main strengths of the paper are:\n- The problem and issues addressed are well stated and clear.\n- The theoretical results presented are interesting.\n- To the best of my knowledge, encoding messages in state-action sequences of RL agents is a novel idea.", "weaknesses": "The main weaknesses are:\n- I am not convinced of the significance of the work. Although the problem is relatively interesting, the theoretical results seem to fall a bit short, and the experiments are not very illustrative either (see questions below).\n- The notation is a bit cluttered and makes some technical statements hard to follow. I understand that authors make use simultaneously of RL notation and FSC notation, but as is, it is confusing. Eg: $x$ is used for actions, but in line 170 there is $a_t$ which seems to be used for actions too. $\\Epsilon$ and $\\pi$ seem to be used for policies, sometimes in the same statement. In line 449 there is a $\\mathcal{L}_{cn}$ which is not defined. In Appendix 1, the proof for the main theorem in Section 4 is presented, but immediately after the authors state that this section makes use of results in section 5 for the proof. $s^+$, $s_{t+1}$ and $s^{t+1}$ seem to be used for the same variable.\n- It is not obvious to distinguish whether the experiment environments are a common benchmark in other information theoretic RL work, or they have been specifically selected for this particular application. I understand that the method is novel, and therefore there may not be other benchmarks to compare to, but some justification for the particular choice of the experimental tasks would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "srRwun3Oyh", "reviewer": "Reviewer_m4h4", "summary": "This paper considers the problem of communication in decision-making problems, they consider communicating through actions, where the message is embedded into the actions of the agents for interacting with environments. The authors model the MDP environment as a finite-state channel (FSC), with actions as the input and the states of the receiver as the output. They propose a way to balance the long-term reward and the communication compacity and show that they could achieve both optimal policies for return and minimize the communication cost at the same time.", "questions": "1. The whole process is very similar to some existing works for multi-agent communications, such as: \"Lowe, R., Wu, Y. I., Tamar, A., Harb, J., Pieter Abbeel, O., & Mordatch, I. (2017). Multi-agent actor-critic for mixed cooperative-competitive environments. Advances in neural information processing systems, 30\", these works are also training the messages along with actions as well. Could the author further discuss a bit more about how it differs from the existing implicit communication methods which are training the messages with actions?\n2. This paper models the MDP, if I understand it correctly, it should be a multi-agent MDP, then is this MDP fully observable or partially observable? Then this MDP should be modeled as the multi-agent version, and should define the number of agents and also the joint state, observation, and action space. Could the authors further clarify this part?\n3. How the communication messages like? Are these discrete or continuous?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper is well-written and well-organized.\n2. The proposed Act2Comm effectively balances the dual objectives of control for total return and communication cost.", "weaknesses": "1. Act2Comm assumes a pre-determined control policy $\\pi$, which means it also needs to optimize the gap between this target policy and the Act2Comm learned policies. Could add a return gap part to further stabilize this procedure. Refer to this paper here 'Chen, J., Lan, T., & Joe-Wong, C. (2024). RGMComm: Return Gap Minimization via Discrete Communications in Multi-Agent Reinforcement Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 38(16), 17327-17336. https://doi.org/10.1609/aaai.v38i16.29680'.\n2. I suggest the authors add a pseudo code in the appendix to further assist the readers to know the whole training process. Right now the order of training the control policies and the communication messages is unclear. \n3. The testing environments are too simple for testing MARL-Comm methods, which only consist of 3 states or 27 states, and 2 or 3 discrete actions. The methods should be tested in continuous control environments.\n4. There are no baselines for comparing the Act2Comm algorithms for the empirical evaluation. This may affect the theoretical results' soundness.\n5. I did not find the submitted codebase in this paper's submission files. The reproducibility might be a problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Xa1tAjwLlW", "reviewer": "Reviewer_ej1T", "summary": "The proposed Act2Comm algorithm presents a multi-objective optimization for communication via the MDP state. This can be beneficial e.g. for multi agent scenarios in hostile environments where no dedicated communication infrastructure is available. In this case, the policy acts both as a message encoder as well as a controller. This requires integrating communication (such that a certain code rate and error probability is achieved) and control (such that a minimum return is achieved). Act2Com presents a transformer-based approach to this challenge.", "questions": "Q1: Why is C(\\tau) necessary in the Transceiver, given Theorem 1 states no historical data is required for the encoding?\n\nQ2: Theory (e.g. Theorem 2) is limited to the undiscounted case, which can cause issues in non terminating MDPs as the return values are likely to diverge to plus or minus infinity. At the same time, the communication does not account for terminal states in the MDP, thus I assume the work considers non terminating MDPs. This needs to be clarified or addressed.\n\nQ3: l348 what is L? Generally, I think the introduction of the decision rule U is relatively confusing. From what I understood, U is a rule that given the current channel state provides the corresponding action that results in the required next state the decoder needs to observe to transmit the message according to the code of the EAS channel. Is that correct? If so, I think an introductory sentence along these lines would benefit the paragraph.\n\nQ4: l382 Are the results limited to scalar states and actions? Otherwise I do not understand the dimensionality of c_t^{(\\tau)}.\n\nQ5: l398: I am not really sure how the quantization works. Shouldn't it be something like U = Q(Z) = |x| \\cdot Sigmoid(Z) for all x in X?\n\nQ6: L452 The paragraph is unclear. Is the estimated gradient the one of eq. 10? If so, why does the critic approximate precisely this gradient and not something else?\n\nQ7: How does your work differ from [1]? The paper should discuss this in my opinion.\n\n[1] Communicating via Markov Decision Processes, Sokota et al. ICML 2022", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "S1: The idea appears to be novel and has not yet been addressed before.\n\nS2: The paper is mostly written well.", "weaknesses": "W1: The paper requires further clarification and explanation of several critical aspects as lined out in the questions. \n\nW2: The setting relies on finite state and action spaces and does not yet address multi-agent scenarios. \n\nW3: No code base provided.\n\nW4: The structure is not ideal in that Theorem 1 is introduced in Section 4, but the proof of Theorem 1 requires results from Section 5.\n\nFurther (minor) weaknesses:\n* Figure 1 is pretty crowded and does not look nice\n* Typo l. 131 „Blackwell Blackwell“\n* Typo l. 229 „use“s", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "G4eDNcD9PN", "reviewer": "Reviewer_kFNj", "summary": "This paper studies the fundamental tradeoff between the information content of an agent’s actions and the long-term performance of the agent in an MDP. This tradeoff is formalized as a convex optimization problem in the context of discrete state and action spaces. A transformer-based approach is then presented to approximate policies which solve a variant of the aforementioned problem, and results are presented in two small toy examples.", "questions": "* Reading the discussion around line 227, do we need for the code to be prefix-free for finite n?\n* Do we really need Lemma 2?\n* Why do the authors describe gradient descent for the problem in Theorem 2 when the proposed approach is actually solving a different problem? Theorem 2 is very nice to state, but I suggest the authors consider whether it is really necessary to discuss solving the problem in Thm. 2 in this level of detail if that is not what is actually done later in the paper.\n    * This does beg the question of why not just use some gradient method to solve the problem in Thm. 2 instead of the proposed workflow outlined in section 5? \n    * Put another way: why is the transformer-style approach in section 5 really necessary when the problem in Theorem 2 looks so elegant? \n* Why are the regions in Figure 3b/c shaded? And, how are the target BER and reward handled? I did not pick up on that in the preceding discussion. \n* The test environments are quite small. What is the main limitation in scaling the proposed approach? Specifically, please:\n   1. Discuss the computational complexity of the proposed approach as the state and action spaces grow.\n   2. Identify specific challenges you anticipate in applying the method to larger, more complex environments.\n   3. Suggest potential modifications or extensions to the proposed approach that might address these scalability challenges.\n   4. If possible, provide preliminary results or analysis on a slightly larger environment to demonstrate scalability potential.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The connection between information content and policy performance is of great theoretical and practical interest; this paper appears to provide a clean characterization of the tradeoff in finite state/action MDPs.\n* The paper also proposes a deep learning-based scheme for generating policies which balance transmission rate and policy performance that—due to its use of neural networks—could (optimistically?) scale to larger problems.", "weaknesses": "* I was surprised not to see papers like “Least inferable policies for Markov decision processes” referenced in the related work discussion. There are other papers from some of these authors which, if memory serves, essentially try to find policies which balance entropy of the state distribution with expected future reward. I believe the main difference is that they were trying to maximize entropy of the state distribution, which amounts to making the capacity of your action-state channel very small. But I imagine it’s just a sign flip to get the other direction. I would appreciate some discussion here.\n* Nitpick: line 131 should use \\citep for the Blackwell reference. What does “indecomposable” mean?\n* In the MDP preliminaries, don’t we need r() to be bounded in order to ensure that (1) is well-posed?\n* nitpick: it would be helpful to define “unichain” for unfamiliar readers\n* From only reading the main text, I would assume that Theorem 1 is surely known in the literature, and is a direct corollary of Shannon’s classic 1948 result, but adapted to the EAS channel. However, appendix A.1 presents a fairly involved proof. Please adjust the main text to explain what is new about this result from existing literature.\n    * There should be some statement of proof for every theorem/lemma, or at least a clear statement that proofs can be found in a specific appendix. I did not see such a statement (apologies if I missed it).\n* nitpick: it should be “ascent” not “decent” in line 306. Also some mention should be made of the inequality constraint here.\n* I suggest that the authors have a bit more of a discussion around lemma 1 to explain how the concavity wrt V will be used later. Currently, lemma 1 interrupts the flow a little.\n* nitpick: is the * in (12) multiplication? If so, I suggest using \\cdot. Similar suggestion on line 418.\n* The authors should clarify the discussion of non-differentiability of f_U in line 414 and below. \n* “critic network with 3 linear layers” (line 431) -> does this imply that there are no nonlinearities? Perhaps: “fully-connected layers” is what is meant here?\n* I am having a lot of difficulty following the logic of section 5 and would appreciate it if the authors could revise the presentation to more clearly articulate the key ideas, how they relate to the problem in Theorem 2, why each idea is necessary, etc.\n    * For example, I do not understand what the role of the critic is, i.e. what its inputs and outputs are and how they relate to the problem at hand. \n    * To be blunt, the first part of this paper (through section 4) is lovely, but section 5 is so confusing that it makes me seriously question my understanding of the problem from section 4. If this can be adequately addressed, I am very happy to raise my score. Specifically, I suggest that the authors:\n       1. Provide a high-level overview of how the approach in Section 5 relates to and differs from the problem formulation in Theorem 2.\n       2. Clearly explain the role of each component (e.g., the critic network) in the proposed approach, including its inputs, outputs, and how it contributes to solving the problem.\n       3. Include a diagram or flowchart illustrating the relationships between different components of the proposed method.\n       4. Consider reorganizing the section to first present the overall approach, then dive into the details of each component.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)