WorksEngineering
On the Optimality of Implicit Feedback in Markov Decision Processes over Imperfect Links
Abstract
Goal-oriented communication protocols are explicitly designed to support the objectives of target applications, such as the monitoring and control of remote processes, while minimizing data traffic. This study considers a transmitter node that observes the environment state and sends it to a remote agent, which then performs control actions. This problem can be modeled as a remote Partially Observable Markov Decision Process (POMDP), a subclass of decentralized POMDPs. Existing studies limit transmissions through communication costs, but neglect the effect of channel impairments and non-ideal or delayed feedback. In this work, we study the optimal joint transmission and control policies over lossy forward channels without explicit acknowledgments. We introduce revealing policies, under which the receiver's action, observed directly by the transmitter, discloses the outcome of the forward transmission, keeping the two agents synchronized without a feedback channel. We derive sufficient conditions for the optimality of time-invariant policies in this implicit feedback regime for general POMDPs, along with strictly weaker sufficient conditions in the special case of contextual bandits. Our simulations over a family of remote POMDPs show that these conditions are conservative, and revealing policies are optimal over a substantially wider parameter range than the conditions warrant.
This manuscript is curently under review.
Introduction
The sixth generation of cellular networks (6G) foresees an ever tighter integration between the physical and digital worlds [1]. Enabling the control of cyber-physical systems via emerging paradigms such as digital twins [2] is a major expected benefit of 6G for industrial automation and robotics. However, the level of safety and efficiency that these applications demand requires throughput, latency, and reliability that already approach the network’s Shannon capacity limits [3].
The goal-oriented communication (GoC) paradigm allows system designers to sidestep the issue by jointly optimizing the end applications and the network protocols: delivering information about the state of the system only when it is needed by the control or estimation algorithm substantially reduces the burden on the network without affecting the performance of the end applications [4, 5, 6]. On the other hand, GoC optimization is often difficult, as the usefulness of a single update may depend on the entire history of transmitted messages and the current state of the environment [7, 8].
To optimize two-agent GoC systems, we can take advantage of the remote partially observable Markov decision process (POMDP) model [9, 10], capturing scenarios in which a transmitter acquires the state of an environment and decides whether to send an update to a receiver, which cannot observe the environment directly, but can perform control actions on it. Explicit communication in a remote POMDP happens over a forward channel, over which the transmitter sends updates to the receiver, and a backward channel, over which the receiver sends acknowledgment (ACK) packets. A key feature of remote POMDPs is that the absence of an update provides implicit information to the receiver, which can infer that the transmitter chose to remain silent, and refine its own state estimate through Bayesian reasoning [9, 11].
If either of the communication channels is ideal, the transmitter always knows exactly what observations have been delivered to the receiver and, consequently, what the receiver knows. In these conditions, the globally optimal policy in a remote POMDP is always time-invariant [9]: this greatly reduces the complexity of finding it and allows it to be stored in finite memory. This is not true for the wider class of decentralized POMDPs, of which remote POMDPs represent a special case and which can model a wide class of distributed control problems [12]. In the general case, the optimal strategy always exists [13], but it may not be time-invariant, i.e., it may depend on the full history of past observations [14].
An ideal backward channel is necessary to maintain an information hierarchy between the transmitter and receiver, i.e., for the former to always know exactly what the latter knows. This hierarchy can be exploited to simplify the optimization problem [15], but real communication scenarios must consider feedback packet losses or delays due to, e.g., wireless access and propagation issues. The propagation delay of the backward channel is a major issue in real-time control systems [16], and particularly in industrial automation networks with strict latency requirements [17], and delays in the reception of ACKs can affect the sampling strategy in monitoring tasks [18]. In extreme scenarios, such as underwater and satellite networks, the backward channel may be very inconvenient due to high delay and frequent packet losses [19], or even entirely absent, such as in covert communication scenarios [20]. To the best of our knowledge, realistic remote POMDPs with imperfect
We acknowledge funding from the UKRI for the projects AI-R (ERC Consolidator Grant, EP/X030806/1) and Smart Networks and Services Joint Undertaking (SNS JU) projects 6G-GOALS (Grant Agreement No. 101139232) and MAGIC-6G (Grant Agreement No. 101292933) under the EU’s Horizon Europe research and innovation program. forward and backward channels remain intractable, and the existence of optimal time-invariant policies is open. This work is a first step toward solving this fundamental problem.
We consider a remote POMDP with imperfect forward and backward channels and assume that the transmitter can observe the receiver’s actions at each time step. While the considered scenario can be optimized through the general decentralized POMDPs paradigm [21], the resulting policies will be history-dependent. Hence, we introduce the concept of revealing policies, i.e., communication and control policies that maintain the information hierarchy between transmitter and receiver without ACKs by using the receiver’s actions as implicit feedback. We prove that revealing policies have time-invariant equivalents that can be computed using frameworks for standard remote POMDPs and stored in finite memory. We analyze their performance against their counterparts with an explicit ACK mechanism over an ideal backward channel.
Our main result shows that, under a wide range of system parameters, the optimal transmission and control policies are always revealing, making the backward channel unnecessary and allowing for optimization considering only time-invariant policies. We also extend our results in the case of remote contextual multi-armed bandits (CMABs), in which the actions performed by the receiver do not affect the environment’s state. For this class of problems, which includes remote estimation as a special case [22, 23], the set of system parameters under which revealing policies are optimal is even wider.
The contributions of this work are summarized as follows:
We provide a rigorous analysis of the remote POMDP problem with imperfect communication, extending existing results with ideal channels to more general cases;
We introduce revealing communication and control policies, which can exploit implicit feedback to operate over an unreliable channel without ACKs, proving that they have time-invariant equivalents;
We derive a sufficient condition for the global optimality of time-invariant revealing policies, proving a stronger result in the special case of remote CMABs;
We derive upper and lower performance bounds for generic optimal policies, showing that the gap between the optimal policy with perfect ACKs and an intuitive heuristic is small over a family of remote POMDPs.
The rest of this paper is organized as follows: first, Sec. II presents the state of the art on remote POMDPs; Sec. III then introduces the remote POMDPs model. Sec. IV presents our theoretical results, which are verified by simulation in Sec. V. Finally, Sec. VI concludes the paper.
Related Work
The decentralized POMDP problem [12] has been widely studied in the communication and control literature due to its highly general nature, which includes a number of useful subclasses. In a decentralized POMDP, multiple agents can both act in a shared environment and communicate part of their observations to other agents [13], yielding complex information structures [24]. In the most general case, while some elements of the knowledge of the agents may be reduced to a belief distribution, the full history of observations and communications must be maintained in each agent’s memory to avoid losing useful information [15]. Although many Bayesian reasoning strategies have been developed to solve decentralized POMDP problems [11], the lack of any recognized information structure significantly hinders their analysis and optimization in practical use cases [25].
The remote POMDP problem is a subclass of decentralized POMDPs that considers only two agents with distinct roles, often admitting a strong information hierarchy. The transmitter is constrained to only communicate and never act, while the receiver can act, but communication is limited to acknowledging the successful reception of an update. These assumptions reduce the degrees of freedom of the problem. In particular, under ideal communication, the strategy space coincides with the set of time-invariant communication and control policies, whose input state can be stored in finite memory. Although finding the optimal joint policies for this scenario is still computationally hard [9], efficient heuristics that can achieve near-optimal performance [26] or local optimality guarantees [27] have been developed. Particular subclasses of remote POMDPs, such as linear systems [28], admit even more efficient solutions, which have been thoroughly investigated in the recent literature, considering both continuous [29] and discrete [26] state spaces. In recent years, remote POMDPs with capacity-limited channels have also been analyzed, and several learning-based solutions have been developed to encode information or schedule transmissions [30, 31].
The remote estimation problem, in which the receiver does not affect the evolution of the process, represents a subclass of remote POMDPs that has attracted significant interest. In particular, in this scenario, maximizing performance in the worst case rather than average yields a much simpler optimization, as the resulting problem has an open-loop optimal strategy [32]. Capacity-limited remote estimation problems have been largely studied considering both continuous [33, 34] and discrete [35, 36] state spaces. However, the complexity of these problems has been shown to be the same as for the general case of remote POMDPs [9].
The optimization of remote POMDPs with unreliable feedback, which is the focus of the present work, has been limited development in the literature. To the best of our knowledge, aside from some early work considering Kalman filter estimation of a linear system [37], only one recent work [38] considered the remote POMDP case with imperfect ACKs. Even this work focused on a simple estimation scenario, optimizing packet scheduling for a linear dynamic system with Gaussian noise that affects the state evolution. Therefore, the case of arbitrary remote POMDPs with an imperfect or missing backward channel remains unsolved in the current literature.
System Model
In the following, we denote sets using calligraphic letters, e.g., , while vector is shortened to . Finally, we write to indicate the probability simplex over .
The Remote POMDP Model
We consider an infinite-horizon remote POMDP, in which a receiver agent must control a process without being able to observe the state directly [9], while a transmitter agent can see the process state and the receiver’s actions, and is allowed to communicate the state of the process to the receiver over a packet erasure channel. Each transmission incurs a communication cost and, if not erased, elicits an ACK packet, which is cost-free but also subject to potential erasures.
Definition 1. A remote POMDP model is characterized by the tuple , whose elements are:
The state space , with cardinality ;
The receiver’s action space , with cardinality ;
The transition function , which provides the distribution of the next state given that the receiver takes action in state ;
The task reward function , which denotes the reward for transition ;
The exponential discount factor over future rewards;
The communication cost of packet transmissions;
The forward channel erasure probability ;
The ACK channel erasure probability .
Time is discretized into steps and, at each step , the transmitter observes the receiver’s previous action and the current state of the process, then decides a communication action , which may be to transmit the state value to the receiver () or remain silent ().
We assume that the receiver cannot distinguish between erasures or skipped transmissions. We then denote by the decoding outcome at the receiver at time slot . In case of a successful transmission, . Otherwise, is set to a null symbol , so that . For the sake of simplicity, in the following we refer to as the received message even when no update is actually received. If , the receiver acknowledges the correct reception of the state update by sending an ACK to the transmitter through the backward channel. Otherwise, it does not return any message. The receiver then takes an action , which affects the evolution of the process according to the transition probability function , yielding the immediate reward at time
We denote the explicit feedback observation at the transmitter by , with if the transmitter receives an ACK, and otherwise, that is, if either the update or the feedback packet was erased. Note that these two events are indistinguishable to the transmitter when considering only the information from the data channels. However, as explained in the following, the transmitter can also infer the outcome of the transmission by observing the action taken by the receiver.
Transmitter and Receiver Histories and Policies
The possibility of erasures in the forward and ACK channels completely changes the nature of the problem compared to that addressed in [9], [26], where the communication channels were ideal (). Specifically, erasures introduce uncertainty in the transmitter’s knowledge of the information possessed by the receiver. This prevents the transmitter from maintaining a compact representation of the receiver’s belief state, ultimately disrupting the information hierarchy between the transmitter and receiver that underpins prior solutions.
We assume that, at the beginning of step , the transmitter knows the current process state and the result of the previous interaction, which includes the transmission decision , the action performed by the receiver, and the feedback observation . We collect these observed variables in the tuple . The full knowledge of the transmitter at time is then given by the cumulative history of these variables, which we denote as , taking values in the set . The transmitter can then implement a time-dependent communication policy, denoted as , that maps each possible history to a probability distribution over the action space.
Similarly, we denote the new information available at the receiver at the beginning of time step as . The knowledge of the receiver is represented as the history tuple , which belongs to space . The receiver knows both and the received message , so its time-dependent control policy is .
Definition 2. The joint policy space is the combination of the two policy sets containing all possible transmitter and receiver policies, respectively:
Value Functions
Our goal is to find the combination of communication and control policies that maximizes the long-term performance, quantified by the value function
In the rest of the paper, for the sake of readability, we will denote the expected long-term value of a joint policy starting at time and with a state distribution as
Theoretical Analysis
We first define a condition that establishes whether the two agents maintain an information hierarchy. If the transmitter knows exactly what the receiver knows, the two agents can exploit the Markov property to find an equivalent time-invariant representation of their knowledge over the environment’s state. In particular, under these conditions, the full knowledge of the agents depends only on the current state (which is known only to the transmitter), the last successfully transmitted state, and the time since the last successful reception of the update, i.e., age of information (AoI) [39], defined as
The transmitter’s history at time is then represented by the tuple and the receiver’s history at time by . Note that this representation of the knowledge of the two agents is time-invariant, as the number and nature of the elements in the tuples do not vary with . While this is not necessary to find the global optimum, which can be computed by applying the joint policy optimization (JPO) algorithm [9 Alg. 3], reducing the search space significantly improves its computational efficiency, and optimal time-invariant policies can be stored in finite memory without approximations.
Time-Invariant Policies
If the two agents maintain the information hierarchy, they can exploit time-invariant policies, which present a finite input space and thus can be stored in finite memory.
Definition 3. The time-invariant policy space is the combination of the two policy sets containing all possible transmitter and receiver policies that reset the nodes’ memories after each successful transmission:
Restricting the problem to time-invariant policies raises optimality concerns, as the optimal solution may not be time-invariant. In the following, we will define sufficient conditions for time-invariant policies to have optimality guarantees, including the need for the agents to be synchronized.
Definition 4. Given the joint policy at time , a transmitter-side history is synchronized if there exists one receiver-side history such that
In the general case, synchronization depends on the joint policy of the transmitter and receiver, as they make take actions that break synchronization, causing the information hierarchy between the transmitter and receiver to break down.
Theorem 1. If all possible transmitter-side histories are synchronized under the optimal policy , time-invariant policies are globally optimal:
Proof. Consider a case in which the optimal policy only uses the time-invariant information starting from time . For an arbitrary , we consider the steps between and . Thanks to the policy-independence property of beliefs [21], we can find a joint policy that only uses the time-invariant tuple between and and maintains the same long-term value, as future rewards are not affected by information before time . We can thus proceed by backward induction until we reach step 0, and the joint policy has been substituted by a policy in with no change in the reward. We now consider the initial assumption. The difference between the optimal policy and a policy that is identical up to time , but changes from step onward, is bounded by , and the time-invariant policy is equivalent to the latter. By increasing the value of , we can reduce the optimality gap between the two policies at will, and taking the limit for , the optimality gap reaches 0. ▪
Theorem 1 allows us to restrict our optimization problem to the time-invariant policy space, as long as we can guarantee synchronization under the optimal policy. If either the communication or the backward channel is ideal, i.e., if , this is always the case, as the outcome of each transmission is known, ensuring synchronization for any joint policy.
Nash Equilibria
As the complexity of JPO is still a significant issue, we can use sub-optimal heuristics as an alternative. For instance, alternate policy iteration (API) [9 Alg. 2] reaches local optimality in remote POMDPs by iterative optimization, adopting a game theoretical approach. The two agents of our model share the same reward and can be thought of as players in a fully cooperative game, a subclass of exact potential games. Therefore, local optimality corresponds to the concept of Nash equilibrium (NE) in this class of games, and we can consider the properties of NEs in .
Definition 5. A joint policy is a NE over policy space if no unilateral deviation from either agent improves the policy’s expected value, that is
We denote the set of NEs in as . As the problem is an exact potential game, the price of anarchy (PoA) [40] is the difference between the global optimum, which is always an NE, and the worst possible NE, and we have
Theorem 2. If the time-invariant joint policy is an NE over , and all possible transmitter-side histories are synchronized under it, then is an NE over , i.e., in the full-history dependent game.
Proof. In order for the joint policy to be an NE, neither agent must have regrets, i.e., it must not be able to improve the reward by unilaterally changing its actions. Since all possible transmitter-side histories are synchronized, the Markov property allows us to say that any element of the history aside from the time-invariant state is irrelevant, i.e., it does not affect future rewards. Therefore, any history-dependent unilateral change in the policy will not improve the overall reward, and the NE over is also an NE over . ▪
Corollary 2.1. If all possible transmitter-side histories are synchronized, .
Proof: By Theorem 2, all NEs in are NEs in , i.e., . The bound then trivially follows from the definition of the PoA in (9). ■
Corollary 2.1 ensures that running API over preserves its local optimality properties even when considering the full policy space . In particular, restricting the space of solutions to time-invariant policies may remove some low-reward equilibria, leading to a lower PoA.
We note that restricting to time-invariant policies does not, by itself, ensure that their input space is finite; the AoI may grow unboundedly under policies that transmit rarely. To store policies in finite memory and run API, we therefore need to cap AoI to a value . This truncation is asymptotically lossless; the performance gap introduced by the cap decays geometrically in , and can be made arbitrarily small.
Revealing Policies under Imperfect Communication
In the rest of the section, we will restrict our analysis to deterministic policies without loss of optimality, and consider the general case in which neither the forward nor the backward channels are ideal. As the optimality of time-invariant policies is guaranteed for synchronized policies, our aim is to ensure synchronization without the need for ACKs. This can be done through implicit feedback: under some conditions, the receiver’s actions may reveal its knowledge to the transmitter, which will then be able to unequivocally identify the outcome of a transmission even without an ACK.
Definition 6. Under the restriction to deterministic policies, the receiver policy is revealing at history and state if the action taken upon successful reception differs from that taken in case of erasure, i.e., .
In cases in which the receiver policy is revealing, receiving a message leads the receiver to select a different control action, and the transmitter can deduce from observing . On the other hand, if the transmitter does not send an update at step , synchronization is maintained independently from , since the receiver will always get symbol .
Lemma 3.1. If transmissions up to time only occur in states and histories in which the receiver’s policy is revealing, all possible transmitter-side histories up to time are synchronized for any value of .
Proof: We prove the Lemma by induction. By the definition of the model, the initial transmitter history is synchronized, as the receiver history at is empty. If history is synchronized up to time , we have two possible cases for step . In the case in which , the receiver must observe , as there is no transmission, and the history is still synchronized. On the other hand, if , the receiver may observe either or . However, its action is different in these two cases, as stated by the definition of revealing policies. Since is part of the transmitter-side observation , the transmitter can determine whether the message was received or not, maintaining history synchronization. ■
We can then extend the definition to a space of revealing policies, which maintain this property for any time step :
Definition 7. The set of revealing policies is:
If the receiver policy is revealing whenever the transmitter updates the state to the receiver, we can eliminate the need for a backward channel while still ensuring synchronization. Hence, under any policy , the system is indistinguishable from the case with , as the transmitter can always recover the value of , and substituting with this value yields the same results of the ideal feedback case.
Lemma 3.2. If the optimal policy with ideal feedback is revealing, it is also optimal for any .
Proof: If we have , then the system while using the optimal policy is indistinguishable from the case with , which means that is a valid policy for any . Moreover, , as a perfect feedback channel policy can always be replaced by discarding information. ■
We note that Theorem 1 ensures that we can compute the optimal policy with ideal feedback using the JPO algorithm, while Lemma 3.2 allows us to extend its optimality to any case as long as is revealing. As the next step, we look for sufficient conditions under which NEs, which correspond to local optima, are associated with revealing policies. Under these conditions, policy , which is also a NE, is optimal for any value of .
Theorem 3. If the joint policy is an NE, it must be revealing for any value of if the remote POMDP respects condition
Proof: The proof is presented as Appendix A. ■
Corollary 3.1. Under the condition in (11), Theorem 1 and Theorem 2 hold in the general case.
Proof: The corollary follows trivially from Lemma 3.1: as revealing policies maintain synchronization, the conditions of the two theorems are verified. ■
The result of Theorem 3 is sufficient for time-invariant policies to be optimal and for the PoA to be lower than in the full policy space. This allows us to compute the optimal policies using any method developed for ideal ACK channels without any modifications, as observing the receiver’s actions provides an ideal implicit feedback mechanism.
The minimum value that satisfies (11) is shown in Figure 1 for several practical values of the discount factor . We note that the values are shown for , as the condition is symmetrical and . Under realistic erasure probabilities , the condition is not too restrictive for and . On the other hand, the condition quickly becomes very restrictive in the case with , requiring values of that will often lead the transmitter never to communicate at all. This can be partially

Figure 1. Minimum value that satisfies the condition for all NE policies to be revealing as a function of the erasure probability .
mitigated by substituting the factor with the highest possible long-term value in the selected POMDP , which can be computed efficiently by setting and may be much lower. Finally, we observe that the condition in (11) is sufficient, but may not be necessary, and, therefore, Corollary 3.1 may hold for a wider class of remote POMDPs.
Special Case: The Remote Contextual Bandit
In the remainder of the section, we extend our analysis to remote CMABs, which represent a subclass of remote POMDPs in which the control actions do not affect the system evolution. Notably, remote monitoring applications, whose goal is only to track the state of the process and not to control it, are a special case of remote CMABs in which and the reward function represents the quality of the estimate.
Definition 8. A remote CMAB is a special case of remote POMDP in which the receiver’s actions do not affect future state transitions, i.e.,
Theorem 4. In the remote CMAB special case, if the joint policy is an NE and the problem respects condition
must be revealing for any value of .
Proof. The proof is presented as Appendix B.
In the remote CMAB scenario, the value of from (11) can be divided by a factor with respect to the general condition, which corresponds to almost halving the value of required for the optimality of revealing policies. The value of the minimum communication cost as a function of the forward channel erasure probability is reported in Figure 1, with dashed lines indicating the values obtained when applying (13). The condition is independent of the value of , as revealing policies completely obviate the need for an explicit feedback mechanism. We finally observe that all our considerations on further improvements for specific remote POMDPs and a wider applicability of Corollary 3.1 are valid in the remote CMAB scenario as well.
Simulation Settings and Results
In this section, we verify the correctness of our theoretical analysis and examine how conservative the sufficient conditions for optimality are through Monte Carlo simulations in a family of remote POMDPs.
We first note that the performance of the optimal policy with ideal feedback represents an upper bound to the performance of the system. Lemma 3.2 ensures that, if the optimal policy is revealing, it will also be playable for any , making the upper bound valid for all such conditions. Notably, if the optimal policy in the case is not revealing and the condition in Theorem 3 is not verified, we do not have an efficient strategy to find an optimal policy for .
We then consider an implementable scheme, which provides a lower bound for optimal performance. We consider a case in which the two nodes continue using but, whenever the transmitter sends a message for which the receiver policy is non-revealing at the current history , the receiver applies the action prescribed by the original policy, but updates its effective history with instead of . In other words, the transmitter ignores messages that could lead to ambiguity, and since the transmitter knows this rule, it can track the same effective history. The two nodes therefore remain synchronized, even though the action does not reveal the channel outcome. We make no claims as to the optimality of this strategy, but note that it represents a simple lower bound to optimal performance.
MDP Generation
We consider a family of Markov decision process (MDPs) with states and control actions to drive the evolution of the system. For each state and action, we then define a target state such that we have the following transition probability function:
In this way, each action has 3 possible outcomes, which correspond to the target state and its neighbors when considering circular coordinates. In all cases, the transition matrices are checked to ensure that the MDP is recurrent, i.e., each state is reachable from any other state with a non-zero probability under a random policy. The receiver reward is defined as , where is a randomly picked state. By randomly selecting the parameters and , we thus generate a family of random MDPs with similar characteristics, corresponding to the one studied in [9] for the ideal communication case.
In order to examine the CMAB case, we maintain the same transition probability matrix and examine two separate cases. Firstly, we consider a remote estimation task, in which and is if and otherwise. Secondly, we define a CMAB with two actions , defining by sampling a uniform distribution . In both cases, actions do not affect state transitions.
Revealing Policy Conditions
We first consider the optimal policy resulting from JPO in the ideal case with : following Lemma 3.2, if revealing, it will remain optimal for any . We thus analyze the class belongs to over an MDP defined as above, checking whether the revealing condition holds. Naturally, this is not representative of all possible MDPs, but it can provide a qualitative idea of the conservativeness of Theorem 3 and the optimality of revealing policies.
Figure 2 shows the nature of , obtained through JPO, for different values of and , setting . Theorem 3 is quite conservative, as non-revealing policies appear only for very low values of , as the zoomed-in plot show, and so is the tighter bound obtained by computing the highest possible long-term reward of the MDP with ideal communication. We also observe that the optimal policy is never to transmit if and is sufficiently high: this policy is still revealing, albeit with degenerate properties.

Figure 2. Analysis of the conditions for revealing policy optimality in a specific remote POMDP with .
The region of revealing policies is even larger in the remote estimation case, shown in Figure 3, where we obtain non-revealing policies only for : in this scenario, the larger number of actions makes it easier for the transmitter to distinguish between different states. We have a few more non-revealing policies in the two-action CMAB case, shown in Figure 4, but the region in which is revealing is

Figure 3. Analysis of the conditions for revealing policy optimality in a specific remote monitoring problem with .

Figure 4. Analysis of the conditions for revealing policy optimality in a specific two-action remote CMAB with .
significantly larger than in the control scenario. Therefore, the condition for the CMAB case is also extremely conservative, and the applicability of ACK-free GoC strategies is thus much wider than the sufficient theoretical condition would suggest.
Optimality Performance Gap
The results we presented above confirm that there is a wide set of parameters and for which policies that are optimal under perfect feedback are revealing. However, we also investigate settings in which this is not the case, using performance with an ideal ACK channel as an upper bound and the lower bound scheme we described above. By evaluating the gap between these bounds, we can know the potential gain of optimizing complex history-dependent strategies.
We fix and consider two possible communication costs: for the control problem, and for the CMAB problem. Hence, we vary and compute the performance of and the lower bound scheme for each configuration, considering 60 random MDP instances from the same family. The results are shown in Figure 5 for the control scenario. We can see that, even in the worst case, i.e., the MDP with the biggest gap, the performance loss is below 3% for . In 75% of cases, the two are actually identical, i.e., is revealing even under these settings. In the CMAB case, shown in Figure 6, about two thirds of cases have a non-zero optimality gap, but even in the worst case the gap is close to 1%. This corroborates our view that revealing policies represent an effective solution to the imperfect feedback problem, allowing for time-invariant representations without affecting performance.

Figure 5. Analysis of the optimality gap over 60 instances of remote POMDPs with and .

Figure 6. Analysis of the optimality gap over 60 instances of CMAB random reward with and .
Conclusion and Future Work
In this work, we presented a theoretical analysis of remote POMDPs with unreliable communication, considering scenarios with an imperfect ACK channel. We introduced the notion of revealing policies, which allow the system agents to preserve an information hierarchy even without relying on explicit ACKs, and studied their optimality. We showed that revealing policies, which always have a time-invariant equivalent, are optimal for a wide range of system parameters, even wider for remote contextual bandits, deriving analytical bounds and discussing their conservative nature.
Our theoretical results pave the way for new approaches for optimizing remote POMDPs, and this study can be extended in several ways: on the practical side, applying these results to modern remote reinforcement learning schemes would be extremely interesting. On the theoretical side, the analysis could extend to settings where the receiver can distinguish silence from channel erasures, which introduces an additional side channel between the agents.
Use of AI Disclosure
The AI system GPT-5.6 Sol was used to implement parts of the simulation code for the results in Sec. V. The code was then checked for correctness by the authors and will be published upon acceptance for reproducibility.
Appendix
Proof of Theorem 3
We prove the Theorem by induction: if its statement is true up to step , Lemma 3.1 allows us to state that any possible transmitter-side history up to time is synchronized. If there is at least one state in which the transmitter sends an update but the receiver policy is not revealing, we define a new transmitter policy , and show that . The new policy is
where is a fictitious history which is identical to except for step , in which . This ensures that the two policies behave identically from step onward. In other words, the modified policy removes the transmission attempt at time , forcing a transmission at time . This is equivalent to removing a redundant transmission if the original policy would have transmitted in step , and to delaying the transmission by one step otherwise. We then decompose :
where is the receiver’s action at time . We now define utility variable . We can then give the probability that the transmitter will send another update in step after transitioning to state , given that the message at time was correctly received, as
Let us now consider the value improvement , defined as
We first note that the two only differ if the message at time is correctly receive, aside from the additional cost which is incurred by the original policy in any case.
We define a post-decision state [41], which describes the system after the transmitter’s action but before the receiver’s. The post-decision state at any time step is characterized by tuple : naturally, if , the message received is with probability 1. The value of the post-decision state at time is
We can compute the value improvement by conditioning on the outcome of and considering post-decision states, obtaining
where and . We first note that, due to the Markov property, receiving a message at time cannot decrease future value with respect to receiving it at time , as the receiver has better information about the state: accordingly, policy always improves the long-term value if the original policy does not transmit in step , and we get condition
Thanks to the Markov property, receiving both and provides the receiver with the same information as only receiving . If is the best response to , the first two terms of the sum must thus be identical, and we obtain
We denote the minimum and maximum possible long-term rewards for the MDP with ideal communication by and , respectively. Since the instantaneous reward is in interval , we know that and . We thus compute a more conservative condition that holds for any MDP definition:
As , we obtain
It is thus easy to see that, under the condition in (11), the value difference is positive, and is not the best response to . We can repeat this for all values of in which is not revealing, obtaining a new transmission policy that maintains synchronization at step . We can thus extend the result to any time step .
Proof of Theorem 4
As we did in the proof of Theorem 3, we consider a policy such that any history is synchronized up to time , and a state in which is not revealing, but for which . We define a new transmitter policy and show that . The new policy is
where, as in the proof of Theorem 3, is a fictitious history. In this case, it identical to except for step , in which , and . This ensures that the two policies behave identically from step onward.
In other words, policy forces a transmission at step , while its behavior in step mirrors what the original policy would have done in step . If , we know that the modified policy always improves the expected value, as it was part of the proof of the general case in Appendix A. On the other hand, if , we need to consider two cases, depending on the actions in step . As the selected action depends on the outcomes of transmissions at steps and , we cannot compute the probability of these two cases. We thus impose the value improvement condition in both cases.
We first consider the case in which : in this case, the original policy transmits at steps and , while the modified policy transmits at steps and . The transmission cost is then reduced by due to the discount. Furthermore, since the action of the receiver in step does not affect , the modified policy will provide the receiver with better information about the state in that step, as its transmissions are more recent, and future values will be improved thanks to the Markov property.
In step , the modified policy is at a disadvantage if the transmission made by the original policy at time step succeeds, while its own transmission fails. This happens with probability , and the maximum reward loss is , discounted by . Putting it all together, we get the following condition for being positive:
Setting returns the condition in (13).
On the other hand, in the case in which , the transmission cost is reduced by for the modified policy. However, in addition to the cost at time step , we have to consider that it may maintain a disadvantage even after step : this occurs if both transmissions made by the modified policy fail, while the extra transmission made at time step by the original policy is successful. In all other cases, the performance of the two policies from step onward is matched. Following the same strategy as in the previous proof, we set an upper bound to the value difference as . The value difference is then
where the first negative term comes from the possible loss in step , while the second comes from losses from step onward. Setting then yields condition
We can easily prove that this is always a looser condition than (13) through some algebraic manipulation. Repeating this substitution process extends the result to any state and time step , thus proving the Theorem.
References
- [1]H. Pennanen, T. Hänninen, O. Tervo, A. Tölli, and M. Latva-Aho, “6G: The intelligent network of everything,” IEEE Access, vol. 13, pp. 1319–1421, Jan. 2025.DOI
- [2]L. U. Khan, W. Saad, D. Niyato, Z. Han, and C. S. Hong, “Digital-twin-enabled 6G: Vision, architectural trends, and future directions,” IEEE Commun. Mag., vol. 60, no. 1, pp. 74–80, Jan. 2022.arxiv.org/abs/2102.12169
- [3]P. Zhang, K. Niu, Z. Liang, C. Wang, J. W. Yu, L. Liu, W. Xu, N. Ma, X. Xu, and R. Zhang, “Beyond Shannon: Semantic information theory and methodology,” IEEE Trans. Netw. Sci. & Engineering, vol. 13, pp. 8062–8079, Mar. 2026.DOI
- [4]Y. Shi, Y. Zhou, D. Wen, Y. Wu, C. Jiang, and K. B. Letaief, “Task-oriented communications for 6G: Vision, principles, and technologies,” IEEE Wireless Commun., vol. 30, no. 3, pp. 78–85, Jun. 2023.arxiv.org/abs/2303.10920
- [5]D. Gündüz, Z. Qin, I. E. Aguerri, H. S. Dhillon, Z. Yang, A. Yener, K. K. Wong, and C.-B. Chae, “Beyond transmitting bits: Context, semantics, and task-oriented communications,” IEEE J. Sel. Areas Commun., vol. 41, no. 1, pp. 5–41, Jan. 2023.arxiv.org/abs/2207.09353
- [6]D. Gündüz, F. Chiarotti, K. Huang, A. E. Kalør, S. Kobus, and P. Popovski, “Timely and massive communication in 6G: Pragmatics, learning, and inference,” IEEE BITS Information Theory Mag., vol. 3, no. 1, pp. 27–40, Mar. 2023.arxiv.org/abs/2306.17580
- [7]J. Luo and N. Pappas, “On the role of age and semantics of information in remote estimation of Markov sources,” IEEE Trans. Commun., vol. 74, pp. 7406–7419, Apr. 2026, Early Access.arxiv.org/abs/2507.18514
- [8]J.-M. Bismut, “An example of interaction between information and control: The transparency of a game,” IEEE Trans. Autom. Control, vol. 18, no. 5, pp. 518–522, Oct. 1973.DOI
- [9]P. Talli, E. D. Santi, F. Chiarotti, T. Soleymani, F. Mason, A. Zanella, and D. Gündüz, “Pragmatic communication for remote control of finite-state Markov processes,” IEEE J. Sel. Areas Commun., vol. 43, no. 7, pp. 2589–2603, Jul. 2025.arxiv.org/abs/2405.10672
- [10]A. Li, S. Wu, G. C. F. Lee, and S. Sun, “From freshness to effectiveness: Goal-oriented sampling for remote decision making,” IEEE Trans. Information Theory, vol. 72, no. 4, pp. 2237–2276, Apr. 2026.
- [11]B. Bozkurt, A. Mahajan, A. Nayyar, and Y. Ouyang, “Generalized certainty equivalence based policies in partially observable systems,” in Proc. 64th Conf. Decision & Control (CDC). Rio de Janeiro, Brazil: IEEE, Dec. 2025, pp. 317–322.DOI
- [12]C. V. Goldman and S. Zilberstein, “Decentralized control of cooperative systems: categorization and complexity analysis,” J. Artif. Int. Res., vol. 22, no. 1, pp. 143–174, Nov. 2004.DOI
- [13]A. Nayyar, A. Mahajan, and D. Teneketzis, “Decentralized stochastic control with partial history sharing: A common information approach,” IEEE Trans. Autom. Control, vol. 58, no. 7, pp. 1644–1658, Jul. 2013.arxiv.org/abs/1209.1695
- [14]C. Amato, G. Chowdhary, A. Geramifard, N. K. Üre, and M. J. Kochenderfer, “Decentralized control of partially observable Markov decision processes,” in Proc. 52nd Conf. Decision & Control (CDC). Firenze, Italy: IEEE, Dec. 2013, pp. 2398–2405.DOI
- [15]A. Nayyar and D. Teneketzis, “Common knowledge and sequential team problems,” IEEE Trans. Autom. Control, vol. 64, no. 12, pp. 5108–5115, Dec. 2019.DOI
- [16]J. Cao, X. Zhu, S. Sun, P. Popovski, S. Feng, and Y. Jiang, “Age of loop for wireless networked control system in the finite blocklength regime: Average, variance and outage probability,” IEEE Trans. Wireless Commun., vol. 22, no. 8, pp. 5306–5320, Aug. 2023.DOI
- [17]H. Yu, P. Zeng, and C. Xu, “Industrial wireless control networks: From wia to the future,” Engineering, vol. 8, pp. 18–24, Jan. 2022.DOI
- [18]S. Liyanaarachchi and S. Ulukus, “The role of early sampling in age of information minimization in the presence of ACK delays,” IEEE Trans. Information Theory, vol. 70, no. 9, pp. 6665–6678, Sep. 2024.arxiv.org/abs/2308.07905
- [19]F. Campagnaro, F. Favaro, P. Casari, and M. Zorzi, “On the feasibility of fully wireless remote control for underwater vehicles,” in Proc. 48th Asilomar Conf. Signals, Sys., & Comput. (SSC). Pacific Grove (CA), USA: IEEE, Nov. 2014, pp. 33–38.
- [20]W. Lucia and A. Youssef, “Covert channels in stochastic cyber-physical systems,” IET Cyber-Physical Sys.: Theory & Appl., vol. 6, no. 4, pp. 228–237, Jul. 2021.DOI
- [21]H. Tavafoghi, Y. Ouyang, and D. Teneketzis, “A unified approach to dynamic decision problems with asymmetric information: Nonstrategic agents,” IEEE Trans. Autom. Control, vol. 67, no. 3, pp. 1105–1119, Mar. 2022.DOI
- [22]F. Pase, D. Gündüz, and M. Zorzi, “Rate-constrained remote contextual bandits,” IEEE J. Sel. Areas Information Theory, vol. 3, no. 4, pp. 789–802, Dec. 2022.arxiv.org/abs/2204.12620
- [23]V. Gupta and V. B. S., “Remote control of bandits over queues - relevance of information freshness,” in Proc. 21st Int. Symp. Modeling & Optim. Mobile, Ad Hoc, & Wireless Netw. (WiOpt). Singapore: IEEE, Aug. 2023, pp. 619–626.DOI
- [24]A. A. Malikopoulos, “On team decision problems with nonclassical information structures,” IEEE Trans. Autom. Control, vol. 68, no. 7, pp. 3915–3930, Jul. 2023.DOI
- [25]S. Sudhakara, D. Kartik, R. Jain, and A. Nayyar, “Optimal communication and control strategies in a cooperative multiagent MDP problem,” IEEE Trans. Autom. Control, vol. 69, no. 10, pp. 6959–6966, Oct. 2024.
- [26]M. Salimnejad, M. Kountouris, and N. Pappas, “Real-time reconstruction of Markov sources under remote actuation over wireless channels,” IEEE Trans. Commun., vol. 72, no. 5, pp. 2701–2715, May 2024.arxiv.org/abs/2302.13927
- [27]F. Chiarotti, F. Talli, F. Mason, and A. Zanella, “Solving the goal-oriented communication problem through policy-level constrained programming,” in Proc. 59th Asilomar Conf. Signals, Sys., & Comput. (SSC). Pacific Grove (CA), USA: IEEE, Oct. 2025, pp. 1157–1161.
- [28]G. M. Lipsa and N. C. Martins, “Remote state estimation with communication costs for first-order LTI systems,” IEEE Trans. Autom. Control, vol. 56, no. 9, pp. 2013–2025, Sep. 2011.DOI
- [29]A. Molin and S. Hirche, “Event-triggered state estimation: An iterative algorithm and optimality properties,” IEEE Trans. Autom. Control, vol. 62, no. 11, pp. 5939–5946, Nov. 2017.DOI
- [30]R. Wang, X. He, R. Yu, W. Qiu, B. An, and Z. Rabinovich, “Learning efficient multi-agent communication: an information bottleneck approach,” in Proc. 37th Int. Conf. Machine Learning (ICML), Virtual, Jul. 2020, pp. 9908–9918.arxiv.org/abs/1911.06992
- [31]T.-Y. Tung, S. Kobus, J. P. Roig, and D. Gündüz, “Effective communications: A joint learning and communication framework for multi-agent reinforcement learning over noisy channels,” IEEE J. Sel. Areas Commun., vol. 39, no. 8, pp. 2590–2603, Aug. 2021.arxiv.org/abs/2101.10369
- [32]M. Gragnani, Y. Ouyang, M. Rasouli, and A. Nayyar, “Worst-case guarantees for remote estimation of an uncertain source,” IEEE Trans. Autom. Control, vol. 66, no. 4, pp. 1794–1801, Apr. 2021.
- [33]S. Dey, A. Chiuso, and L. Schenato, “Remote estimation with noisy measurements subject to packet loss and quantization noise,” IEEE Trans. Control Netw. Sys., vol. 1, no. 3, pp. 204–217, Sep. 2014.DOI
- [34]A. Khina, V. Kostina, A. Khisti, and B. Hassibi, “Tracking and control of Gauss–Markov processes over packet-drop channels with acknowledgments,” IEEE Trans. Control Netw. Sys., vol. 6, no. 2, pp. 549–560, Jun. 2019.arxiv.org/abs/1702.01779
- [35]S. S. Vilni, A. Zakeri, M. Molfatef, and R. Wichman, “Real-time tracking in a pull-based status update system with unreliable command channel,” IEEE Internet Things J., vol. 13, no. 14, pp. 32169–32184, Jul. 2026.DOI
- [36]S. S. Vilni, A. Zakeri, M. Molfatef, and M. Codreanu, “Real-time tracking in a status update system with an imperfect feedback channel,” IEEE Trans. Veh. Tech., vol. 75, no. 5, pp. 8064–8079, May 2026.arxiv.org/abs/2407.06749
- [37]M. Nourian, A. S. Leong, and S. Dey, “Optimal energy allocation for Kalman filtering over packet dropping links with imperfect acknowledgments and energy harvesting constraints,” IEEE Trans. Autom. Control, vol. 59, no. 8, pp. 2128–2143, Apr. 2014.DOI
- [38]T. Soleymani, M. Assaad, and J. S. Baras, “Remote state estimation over unreliable channels with unreliable feedback: Strategies and limits,” IEEE Trans. Information Theory, vol. 72, no. 8, pp. 5776–5795, Aug. 2026.arxiv.org/abs/2501.13192
- [39]R. D. Yates, Y. Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” IEEE J. Sel. Areas Commun., vol. 39, no. 5, pp. 1183–1210, May 2021.arxiv.org/abs/2007.08564
- [40]E. Koutsoupias and C. Papadimitriou, “Worst-case equilibria,” Comput. Science Rev., vol. 3, no. 2, pp. 65–69, May 2009.
- [41]N. Salodkar, A. Bhorkar, A. Karandikar, and V. S. Borkar, “An on-line learning algorithm for energy efficient delay constrained scheduling over a fading channel,” IEEE J. Sel. Areas Commun., vol. 26, no. 4, pp. 732–742, May 2008.DOI