betaFeedback

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.

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., S\mathcal{S}, while vector (x0,…,xt)(x_0,\ldots,x_t) is shortened to x0:tx_{0:t}. Finally, we write Φ(S)\Phi(\mathcal{S}) to indicate the probability simplex over S\mathcal{S}.

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 ⟨S,A,P,r,γ,β,ε,φ⟩\langle\mathcal{S},\mathcal{A},P,r,\gamma,\beta,\varepsilon,\varphi\rangle, whose elements are:

  • The state space S\mathcal{S}, with cardinality SS;

  • The receiver’s action space A\mathcal{A}, with cardinality AA;

  • The transition function P:S×A→Φ(S)P:\mathcal{S}\times\mathcal{A}\to\Phi(\mathcal{S}), which provides the distribution of the next state s′∈Ss^{\prime}\in\mathcal{S} given that the receiver takes action a∈Aa\in\mathcal{A} in state s∈Ss\in\mathcal{S};

  • The task reward function r:S×A×S→[0,1]r:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\to[0,1], which denotes the reward for transition ⟨s,a,s′⟩\langle s,a,s^{\prime}\rangle;

  • The exponential discount factor γ\gamma over future rewards;

  • The communication cost β\beta of packet transmissions;

  • The forward channel erasure probability ε\varepsilon;

  • The ACK channel erasure probability φ\varphi.

Time is discretized into steps and, at each step tt, the transmitter observes the receiver’s previous action at−1a_{t-1} and the current state sts_t of the process, then decides a communication action ct∈{0,1}c_t\in\{0,1\}, which may be to transmit the state value to the receiver (ct=1c_t=1) or remain silent (ct=0c_t=0).

We assume that the receiver cannot distinguish between erasures or skipped transmissions. We then denote by mt∈Mm_t\in\mathcal{M} the decoding outcome at the receiver at time slot tt. In case of a successful transmission, mt=stm_t=s_t. Otherwise, mtm_t is set to a null symbol χ\chi, so that M=S∪{χ}\mathcal{M}=\mathcal{S}\cup\{\chi\}. For the sake of simplicity, in the following we refer to mtm_t as the received message even when no update is actually received. If mt≠χm_t\ne\chi, 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 at∈Aa_t\in\mathcal{A}, which affects the evolution of the process according to the transition probability function PP, yielding the immediate reward at time tt

R(st,ct,at,st+1)=r(st,at,st+1)−βct.(1)R(s_t,c_t,a_t,s_{t+1})=r(s_t,a_t,s_{t+1})-\beta c_t. \tag*{(1)}

We denote the explicit feedback observation at the transmitter by ft∈{0,1}f_t\in\{0,1\}, with ft=1f_t=1 if the transmitter receives an ACK, and ft=0f_t=0 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 ata_t 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 (ε=φ=0\varepsilon=\varphi=0). 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 tt, the transmitter knows the current process state sts_t and the result of the previous interaction, which includes the transmission decision ct−1c_{t-1}, the action at−1a_{t-1} performed by the receiver, and the feedback observation ft−1f_{t-1}. We collect these observed variables in the tuple ox,t=⟨ct−1,at−1,ft−1,st⟩o_{x,t}=\langle c_{t-1},a_{t-1},f_{t-1},s_t\rangle. The full knowledge of the transmitter at time tt is then given by the cumulative history of these variables, which we denote as Hx,0:t=⟨ox,0:t−1,a0:t−1,f0:t−1,s0:t⟩\mathcal{H}_{x,0:t}=\langle o_{x,0:t-1},a_{0:t-1},f_{0:t-1},s_{0:t}\rangle, taking values in the set Hx,t={0,1}t×At×Ft×St+1\mathcal{H}_{x,t}=\{0,1\}^{t}\times\mathcal{A}^{t}\times\mathcal{F}^{t}\times\mathcal{S}^{t+1}. The transmitter can then implement a time-dependent communication policy, denoted as πx,t:Hx,t→Φ({0,1})\pi_{x,t}:\mathcal{H}_{x,t}\to\Phi(\{0,1\}), 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 tt as or,x=⟨mt−1,at−1⟩o_{r,x}=\langle m_{t-1},a_{t-1}\rangle. The knowledge of the receiver is represented as the history tuple Hr,x,0:t=⟨m0:t−1,a0:t−1⟩\mathcal{H}_{r,x,0:t}=\langle m_{0:t-1},a_{0:t-1}\rangle, which belongs to space Hr,x,t=Mt×At\mathcal{H}_{r,x,t}=\mathcal{M}^{t}\times\mathcal{A}^{t}. The receiver knows both Hrx,0:t\mathcal{H}_{rx,0:t} and the received message mtm_t, so its time-dependent control policy is πrx,t:Hrx,t×M→Φ(A)\pi_{rx,t}:\mathcal{H}_{rx,t}\times\mathcal{M}\to\Phi(\mathcal{A}).

Definition 2. The joint policy space Π\Pi is the combination of the two policy sets containing all possible transmitter and receiver policies, respectively:

Π=(Htx,t→Φ({0,1}))×(Hrx,t×M→Φ(A)).(2)\Pi=(\mathcal{H}_{tx,t}\to\Phi(\{0,1\}))\times(\mathcal{H}_{rx,t}\times\mathcal{M}\to\Phi(\mathcal{A})). \tag*{(2)}

Value Functions

Our goal is to find the combination of communication and control policies π=⟨πtx,πrx⟩∈Π\pi=\langle\pi_{tx},\pi_{rx}\rangle\in\Pi that maximizes the long-term performance, quantified by the value function

Vsπtx,πrx(htx,hrx)=E[∑τ=t∞γ−τ∑a∈A,c∈{0,1}R(sτ,πtx,τ(c∣Htx,0:τ),πrx,τ(a∣Hrx,0:τ,mt),sτ+1)|st=s,Htx,0:t=htx,Hrx,0:t=hrx].(3)V_s^{\pi_{tx},\pi_{rx}}(h_{tx},h_{rx})=\mathbb{E}\left[\sum_{\tau=t}^{\infty}\gamma^{-\tau}\sum_{a\in\mathcal{A},c\in\{0,1\}}R(s_\tau,\pi_{tx,\tau}(c\mid\mathcal{H}_{tx,0:\tau}),\pi_{rx,\tau}(a\mid\mathcal{H}_{rx,0:\tau},m_t),s_{\tau+1})\middle|s_t=s,\mathcal{H}_{tx,0:t}=h_{tx},\mathcal{H}_{rx,0:t}=h_{rx}\right]. \tag*{(3)}

In the rest of the paper, for the sake of readability, we will denote the expected long-term value of a joint policy π\pi starting at time 00 and with a state distribution μ0\mu_0 as

Vπ=Es∼μ0[V0π(s,O)].V^\pi=\mathbb{E}_{s\sim\mu_0}[V_0^\pi(s,\mathcal{O})].

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) Δt\Delta_t [39], defined as

Δt=t−sup⁡{τ∈{0,…,t−1}:mτ=sτ}.(4)\Delta_t = t - \sup\{\tau\in\{0,\ldots,t-1\}: m_\tau= s_\tau\}. \tag*{(4)}

The transmitter’s history at time tt is then represented by the tuple ⟨st,Δt,st−Δt⟩\langle s_t,\Delta_t,s_{t-\Delta_t}\rangle and the receiver’s history at time tt by ⟨Δt,st−Δt⟩\langle\Delta_t,s_{t-\Delta_t}\rangle. 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 tt. 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 ΠTI⊂Π\Pi^{TI} \subset\Pi is the combination of the two policy sets containing all possible transmitter and receiver policies that reset the nodes’ memories after each successful transmission:

ΠTI=(S×S×N→Φ({0,1}))×(M×S×N→Φ(A)).(5)\Pi^{TI} = (\mathcal{S} \times\mathcal{S} \times\mathbb{N} \to\Phi(\{0,1\})) \times(\mathcal{M} \times\mathcal{S} \times\mathbb{N} \to\Phi(\mathcal{A})). \tag*{(5)}

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 πt=⟨πtx,t,πrx,t⟩\pi_t = \langle\pi_{\mathrm{tx},t},\pi_{\mathrm{rx},t}\rangle at time tt, a transmitter-side history htxh_{\mathrm{tx}} is synchronized if there exists one receiver-side history hrxh_{\mathrm{rx}} such that

Pr⁡[Hrx,0:t=hrx∣Htx,0:t=htx,πtx,t,πrx,t]=1.(6)\Pr[H_{\mathrm{rx},0:t}=h_{\mathrm{rx}}\mid H_{\mathrm{tx},0:t}=h_{\mathrm{tx}},\pi_{\mathrm{tx},t},\pi_{\mathrm{rx},t}]=1. \tag*{(6)}

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 π∗=arg⁡max⁡π∈ΠVπ\pi^*=\arg\max_{\pi\in\Pi}V^\pi, time-invariant policies are globally optimal:

max⁡π∈ΠVπ=max⁡π′∈ΠTIVπ′.(7)\max_{\pi\in\Pi}V^\pi=\max_{\pi'\in\Pi^{TI}}V^{\pi'}. \tag*{(7)}

Proof. Consider a case in which the optimal policy only uses the time-invariant information starting from time T>0T>0. For an arbitrary hrx∈Hrx,th_{\mathrm{rx}}\in\mathcal{H}_{\mathrm{rx},t}, we consider the steps between T−ΔtT-\Delta_t and TT. Thanks to the policy-independence property of beliefs [21], we can find a joint policy that only uses the time-invariant tuple between T−ΔtT-\Delta_t and TT and maintains the same long-term value, as future rewards are not affected by information before time TT. We can thus proceed by backward induction until we reach step 0, and the joint policy has been substituted by a policy in ΠTI\Pi^{TI} 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 TT, but changes from step TT onward, is bounded by γT(1−γ)−1\gamma^T(1-\gamma)^{-1}, and the time-invariant policy is equivalent to the latter. By increasing the value of TT, we can reduce the optimality gap between the two policies at will, and taking the limit for T→∞T\to\infty, 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 ϵ=0∨φ=0\epsilon=0\lor\varphi=0, 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 ΠTI\Pi^{TI}.

Definition 5. A joint policy π=⟨πtx,πrx⟩\pi=\langle\pi_{\mathrm{tx}},\pi_{\mathrm{rx}}\rangle is a NE over policy space Π\Pi if no unilateral deviation from either agent improves the policy’s expected value, that is

∄πtx′∈Πtx:Vπtx′,πrx>Vπ∧∄πrx′∈Πrx:Vπtx,πrx′>Vπ.(8)\not\exists\pi'_{\mathrm{tx}}\in\Pi_{\mathrm{tx}}:V^{\pi'_{\mathrm{tx}},\pi_{\mathrm{rx}}}>V^\pi\land\not\exists\pi'_{\mathrm{rx}}\in\Pi_{\mathrm{rx}}:V^{\pi_{\mathrm{tx}},\pi'_{\mathrm{rx}}}>V^\pi. \tag*{(8)}

We denote the set of NEs in Π\Pi as E(Π)\mathcal{E}(\Pi). As the problem is an exact potential game, the price of anarchy (PoA) [40] σ(Π)\sigma(\Pi) is the difference between the global optimum, which is always an NE, and the worst possible NE, and we have

σ(Π)=sup⁡π∈E(Π)Vπ−inf⁡π′∈E(Π)Vπ′.(9)\sigma(\Pi)=\sup_{\pi\in\mathcal{E}(\Pi)}V^\pi-\inf_{\pi'\in\mathcal{E}(\Pi)}V^{\pi'}. \tag*{(9)}

Theorem 2. If the time-invariant joint policy π∈ΠTI\pi\in\Pi^{TI} is an NE over ΠTI\Pi^{TI}, and all possible transmitter-side histories are synchronized under it, then π\pi is an NE over Π\Pi, 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 ΠTI\Pi^{TI} is also an NE over Π\Pi. ▪

Corollary 2.1. If all possible transmitter-side histories are synchronized, σ(ΠTI)≤σ(Π)\sigma(\Pi^{TI})\leq\sigma(\Pi).

Proof: By Theorem 2, all NEs in ΠTI\Pi^{\mathrm{TI}} are NEs in Π\Pi, i.e., E(ΠTI)⊆E(Π)\mathcal{E}(\Pi^{\mathrm{TI}}) \subseteq\mathcal{E}(\Pi). The bound σ(ΠTI)≤σ(Π)\sigma(\Pi^{\mathrm{TI}}) \leq\sigma(\Pi) then trivially follows from the definition of the PoA in (9). ■

Corollary 2.1 ensures that running API over ΠTI\Pi^{\mathrm{TI}} preserves its local optimality properties even when considering the full policy space Π\Pi. 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 Δt\Delta_t 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 Δmax⁡\Delta_{\max}. This truncation is asymptotically lossless; the performance gap introduced by the cap decays geometrically in Δmax⁡\Delta_{\max}, 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 πrx\pi_{\mathrm{rx}} is revealing at history hrxh_{\mathrm{rx}} and state ss if the action taken upon successful reception differs from that taken in case of erasure, i.e., πrx(hrx,s)≠πrx(hrx,χ)\pi_{\mathrm{rx}}(h_{\mathrm{rx}},s) \ne\pi_{\mathrm{rx}}(h_{\mathrm{rx}},\chi).

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 mtm_t from observing ata_t. On the other hand, if the transmitter does not send an update at step tt, synchronization is maintained independently from πrx\pi_{\mathrm{rx}}, since the receiver will always get symbol χ\chi.

Lemma 3.1. If transmissions up to time t−1t-1 only occur in states and histories in which the receiver’s policy is revealing, all possible transmitter-side histories up to time tt are synchronized for any value of φ\varphi.

Proof: We prove the Lemma by induction. By the definition of the model, the initial transmitter history is synchronized, as the receiver history at t=0t=0 is empty. If history is synchronized up to time τ\tau, we have two possible cases for step τ+1\tau+1. In the case in which cτ=0c_\tau=0, the receiver must observe mτ=χm_\tau=\chi, as there is no transmission, and the history is still synchronized. On the other hand, if cτ=1c_\tau=1, the receiver may observe either στ\sigma_\tau or χ\chi. However, its action aτa_\tau is different in these two cases, as stated by the definition of revealing policies. Since aτa_\tau is part of the transmitter-side observation otx,τo_{\mathrm{tx},\tau}, 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 tt:

Definition 7. The set of revealing policies ΠRV⊂Π\Pi^{\mathrm{RV}} \subset\Pi is:

ΠRV={(πtx,πrx)∈Π:πtx(htx)=0 ∀ πrx(hrx,s)≠πrx(hrx,χ), ∀s∈S,htx,hrx}.(10)\Pi^{\mathrm{RV}} = \left\{(\pi_{\mathrm{tx}},\pi_{\mathrm{rx}}) \in\Pi: \pi_{\mathrm{tx}}(h_{\mathrm{tx}})=0 \ \forall\ \pi_{\mathrm{rx}}(h_{\mathrm{rx}},s) \ne\pi_{\mathrm{rx}}(h_{\mathrm{rx}},\chi),\ \forall s \in\mathcal{S}, h_{\mathrm{tx}},h_{\mathrm{rx}}\right\}. \tag*{(10)}

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 π∈ΠRV\pi\in\Pi^{\mathrm{RV}}, the system is indistinguishable from the case with φ=0\varphi=0, as the transmitter can always recover the value of mtm_t, and substituting ftf_t with this value yields the same results of the ideal feedback case.

Lemma 3.2. If the optimal policy with ideal feedback πφ=0⋆\pi^{\star}_{\varphi=0} is revealing, it is also optimal for any φ>0\varphi>0.

Proof: If we have πφ=0⋆∈ΠRV\pi^{\star}_{\varphi=0} \in\Pi^{\mathrm{RV}}, then the system while using the optimal policy is indistinguishable from the case with φ=0\varphi=0, which means that πφ=0⋆\pi^{\star}_{\varphi=0} is a valid policy for any φ\varphi. Moreover, ∀φ,Vφ⋆≤Vφ=0⋆\forall\varphi, V^{\star}_{\varphi} \leq V^{\star}_{\varphi=0}, 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 πφ=0⋆\pi^{\star}_{\varphi=0} using the JPO algorithm, while Lemma 3.2 allows us to extend its optimality to any case φ>0\varphi>0 as long as πφ=0⋆\pi^{\star}_{\varphi=0} 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 πφ=0⋆\pi^{\star}_{\varphi=0}, which is also a NE, is optimal for any value of φ\varphi.

Theorem 3. If the joint policy π\pi is an NE, it must be revealing for any value of φ\varphi if the remote POMDP respects condition

β>γε(1−ε)(1−γ)−1,(11)\beta> \gamma\varepsilon(1-\varepsilon)(1-\gamma)^{-1}, \tag*{(11)}

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 βmin⁡(ε)\beta_{\min}(\varepsilon) that satisfies (11) is shown in Figure 1 for several practical values of the discount factor γ\gamma. We note that the values are shown for ε∈[0,0.5]\varepsilon\in[0,0.5], as the condition is symmetrical and βmin⁡(ε)=βmin⁡(1−ε)\beta_{\min}(\varepsilon)=\beta_{\min}(1-\varepsilon). Under realistic erasure probabilities ε∈[0.1,0.1]\varepsilon\in[0.1, 0.1], the condition is not too restrictive for γ=0.9\gamma=0.9 and γ=0.95\gamma=0.95. On the other hand, the condition quickly becomes very restrictive in the case with γ=0.99\gamma=0.99, requiring values of β\beta that will often lead the transmitter never to communicate at all. This can be partially

Minimum value $\beta_{\min}$ as a function of the erasure probability $\varepsilon$

Figure 1. Minimum value βmin⁡\beta_{\min} that satisfies the condition for all NE policies to be revealing as a function of the erasure probability ε\varepsilon.

mitigated by substituting the (1−γ)−1(1-\gamma)^{-1} factor with the highest possible long-term value in the selected POMDP Vmax⁡V_{\max}, which can be computed efficiently by setting β=ε=φ=0\beta=\varepsilon=\varphi=0 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 A=S\mathcal{A}=\mathcal{S} 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.,

Ps,s′a=Ps,s′a′,∀s,s′∈S,a,a′∈A.(12)P^{a}_{s,s'}=P^{a'}_{s,s'},\quad\forall s,s'\in\mathcal{S},a,a'\in\mathcal{A}. \tag*{(12)}

Theorem 4. In the remote CMAB special case, if the joint policy π\pi is an NE and the problem respects condition

β>γε(1−ε)(1−γ2)−1,(13)\beta>\gamma\varepsilon(1-\varepsilon)(1-\gamma^2)^{-1}, \tag*{(13)}

π\pi must be revealing for any value of φ\varphi.

Proof. The proof is presented as Appendix B.

In the remote CMAB scenario, the value of βmin⁡\beta_{\min} from (11) can be divided by a factor 1+γ1+\gamma with respect to the general condition, which corresponds to almost halving the value of β\beta required for the optimality of revealing policies. The value of the minimum communication cost βmin⁡(ε)\beta_{\min}(\varepsilon) as a function of the forward channel erasure probability ε\varepsilon is reported in Figure 1, with dashed lines indicating the values obtained when applying (13). The condition is independent of the value of φ\varphi, 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 πφ=0∗\pi_{\varphi=0}^{*} 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 φ>0\varphi>0, making the upper bound valid for all such conditions. Notably, if the optimal policy in the φ=0\varphi=0 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 φ>0\varphi>0.

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 πφ=0∗\pi_{\varphi=0}^{*} but, whenever the transmitter sends a message mtm_t for which the receiver policy is non-revealing at the current history hRXh_{RX}, the receiver applies the action prescribed by the original policy, but updates its effective history with χ\chi instead of ss. 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 S=6\mathcal{S}=6 states and A=2\mathcal{A}=2 control actions to drive the evolution of the system. For each state and action, we then define a target state ζ(s,a)\zeta(s,a) such that we have the following transition probability function:

Ps,s′a={914,if s′=ζ(s,a);528,if ∣s′−ζ(s,a)∣∈{1,S−1}.(14)P^{a}_{s,s'}= \begin{cases} \frac{9}{14}, & \text{if }s'=\zeta(s,a);\\ \frac{5}{28}, & \text{if }\lvert s'-\zeta(s,a)\rvert\in\{1,\mathcal{S}-1\}. \end{cases} \tag*{(14)}

In this way, each action has 3 possible outcomes, which correspond to the target state ζ(s,a)\zeta(s,a) 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 r(s,a,s′)=exp⁡(−∣s′−s∗∣)r(s,a,s')=\exp(-\lvert s'-s^{*}\rvert), where s∗s^{*} is a randomly picked state. By randomly selecting the parameters ζ\zeta and s∗s^{*}, 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 A=S\mathcal{A}=\mathcal{S} and r(s,a,s′)r(s,a,s') is 11 if a=sa=s and 00 otherwise. Secondly, we define a CMAB with two actions A={0,1}\mathcal{A}=\{0,1\}, defining r(s,a,⋅)r(s, a, \cdot) ∀a∈A\forall a \in\mathcal{A} by sampling a uniform distribution U(0,1)\mathcal{U}(0, 1). 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 φ=0\varphi= 0: following Lemma 3.2, if πφ=0∗\pi^{*}_{\varphi=0} revealing, it will remain optimal for any φ>0\varphi> 0. We thus analyze the class πφ=0∗\pi^{*}_{\varphi=0} 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 πφ=0∗\pi^{*}_{\varphi=0}, obtained through JPO, for different values of β\beta and ε\varepsilon, setting γ=0.95\gamma= 0.95. Theorem 3 is quite conservative, as non-revealing policies appear only for very low values of β\beta, as the zoomed-in plot show, and so is the tighter bound obtained by computing the highest possible long-term reward Vmax⁡V_{\max} of the MDP with ideal communication. We also observe that the optimal policy is never to transmit if β>1\beta> 1 and ε\varepsilon is sufficiently high: this policy is still revealing, albeit with degenerate properties.

Analysis plots of revealing conditions for a specific remote POMDP

Figure 2. Analysis of the conditions for revealing policy optimality in a specific remote POMDP with γ=0.95\gamma= 0.95.

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 β=0\beta= 0: 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 πφ=0∗\pi^{*}_{\varphi=0} is revealing is

Analysis plots of revealing conditions for a specific remote monitoring problem

Figure 3. Analysis of the conditions for revealing policy optimality in a specific remote monitoring problem with γ=0.95\gamma= 0.95.

Analysis plots of revealing conditions for a specific two-action remote CMAB

Figure 4. Analysis of the conditions for revealing policy optimality in a specific two-action remote CMAB with γ=0.95\gamma= 0.95.

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 ε\varepsilon and β\beta 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 γ=0.95\gamma= 0.95 and consider two possible communication costs: β=0.05\beta= 0.05 for the control problem, and β=0.02\beta= 0.02 for the CMAB problem. Hence, we vary ε∈[0,0.1]\varepsilon\in[0, 0.1] and compute the performance of πφ=0∗\pi^{*}_{\varphi=0} 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 ε≤0.1\varepsilon\leq0.1. In 75% of cases, the two are actually identical, i.e., πφ=0∗\pi^{*}_{\varphi=0} 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.

Analysis of the optimality gap over 60 instances of remote POMDPs

Figure 5. Analysis of the optimality gap over 60 instances of remote POMDPs with γ=0.95\gamma= 0.95 and β=0.05\beta= 0.05.

Analysis of the optimality gap over 60 instances of CMAB random reward

Figure 6. Analysis of the optimality gap over 60 instances of CMAB random reward with γ=0.95\gamma= 0.95 and β=0.02\beta= 0.02.

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 t−1t-1, Lemma 3.1 allows us to state that any possible transmitter-side history htxh_{\mathrm{tx}} up to time tt is synchronized. If there is at least one state ss in which the transmitter sends an update but the receiver policy is not revealing, we define a new transmitter policy πtx\pi_{\mathrm{tx}}, and show that Vsπtx,πrx(htx,hrx)>Vsπtx,πrx(htx,hrx)V_s^{\pi_{\mathrm{tx},\pi_{\mathrm{rx}}}}(h_{\mathrm{tx}},h_{\mathrm{rx}}) > V_s^{\pi_{\mathrm{tx},\pi_{\mathrm{rx}}}}(h_{\mathrm{tx}},h_{\mathrm{rx}}). The new policy is

πtx,τ′(htx′)={πtx,τ(htx′),τ<t∨htx⊄htx′;0,τ=t;1,τ=t+1;πtx,τ(htx′′),otherwise,(15)\pi'_{\mathrm{tx},\tau}(h'_{\mathrm{tx}})= \begin{cases} \pi_{\mathrm{tx},\tau}(h'_{\mathrm{tx}}), & \tau< t \lor h_{\mathrm{tx}}\not\subset h'_{\mathrm{tx}};\\ 0, & \tau=t;\\ 1, & \tau=t+1;\\ \pi_{\mathrm{tx},\tau}(h''_{\mathrm{tx}}), & \text{otherwise}, \end{cases} \tag*{(15)}

where htx′′h''_{\mathrm{tx}} is a fictitious history which is identical to htx′h'_{\mathrm{tx}} except for step tt, in which c′′=1c''=1. This ensures that the two policies behave identically from step t+2t+2 onward. In other words, the modified policy removes the transmission attempt at time tt, forcing a transmission at time t+1t+1. This is equivalent to removing a redundant transmission if the original policy would have transmitted in step t+1t+1, and to delaying the transmission by one step otherwise. We then decompose Vsπtx,πrx(htx,hrx)V_s^{\pi_{\mathrm{tx},\pi_{\mathrm{rx}}}}(h_{\mathrm{tx}},h_{\mathrm{rx}}):

Vsπtx,πrx(htx,hrx)=−β+∑s′∈SPs,s′a[r(s,a,s′)+γVs′πtx,πrx([htx,⟨1,a,ft,s′⟩],[hrx,⟨mt,a⟩])].(16)V_s^{\pi_{\mathrm{tx},\pi_{\mathrm{rx}}}}(h_{\mathrm{tx}},h_{\mathrm{rx}})=-\beta+\sum_{s'\in\mathcal{S}}P^a_{s,s'}\left[r(s,a,s')+\gamma V_{s'}^{\pi_{\mathrm{tx},\pi_{\mathrm{rx}}}}\left([h_{\mathrm{tx}},\langle1,a,f_t,s'\rangle],[h_{\mathrm{rx}},\langle m_t,a\rangle]\right)\right]. \tag*{(16)}

where a=πrx,t(hrx,χ)=πrx,t(hrx,s)a=\pi_{\mathrm{rx},t}(h_{\mathrm{rx}},\chi)=\pi_{\mathrm{rx},t}(h_{\mathrm{rx}},s) is the receiver’s action at time tt. We now define utility variable ots,s′=⟨1,a,f,s′⟩o_{t}^{s,s'}=\langle1,a,f,s'\rangle. We can then give the probability ptx(s′)p_{\mathrm{tx}}(s') that the transmitter will send another update in step t+1t+1 after transitioning to state s′s', given that the message at time tt was correctly received, as

ptx(s′)=(1−φ)πtx,t+1([htx,otx1,s′])+φπtx,t+1([htx,otx0,s′]).(17)p_{\mathrm{tx}}(s')=(1-\varphi)\pi_{\mathrm{tx},t+1}\left([h_{\mathrm{tx}},o_{\mathrm{tx}}^{1,s'}]\right)+\varphi\pi_{\mathrm{tx},t+1}\left([h_{\mathrm{tx}},o_{\mathrm{tx}}^{0,s'}]\right). \tag*{(17)}

Let us now consider the value improvement ΔV\Delta V, defined as

ΔV=Vsπtx,πrx′(htx,hrx)−Vsπtx,πrx(htx,hrx).(18)\Delta V=V_s^{\pi'_{\mathrm{tx},\pi_{\mathrm{rx}}}}(h_{\mathrm{tx}},h_{\mathrm{rx}})-V_s^{\pi_{\mathrm{tx},\pi_{\mathrm{rx}}}}(h_{\mathrm{tx}},h_{\mathrm{rx}}). \tag*{(18)}

We first note that the two only differ if the message at time tt is correctly receive, aside from the additional cost β\beta which is incurred by the original policy πtx\pi_{\mathrm{tx}} 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 ⟨s,c,m⟩\langle s,c,m\rangle: naturally, if c=0c=0, the message received is m=χm=\chi with probability 1. The value of the post-decision state ⟨s,c,m⟩\langle s,c,m\rangle at time tt is

Us,c,mπtx,πrx(htx,hrx)=∑a∈Aπrx,t(a∣hrx,m)∑s′∈SPs,s′a[r(s,a,s′)+γVs′πtx,πrx([htx,⟨c,a,s′⟩],[hrx,⟨m,a⟩])].(19)U_{s,c,m}^{\pi_{\mathrm{tx},\pi_{\mathrm{rx}}}}(h_{\mathrm{tx}},h_{\mathrm{rx}})=\sum_{a\in\mathcal{A}}\pi_{\mathrm{rx},t}(a\mid h_{\mathrm{rx}},m)\sum_{s'\in\mathcal{S}}P^a_{s,s'}\left[r(s,a,s')+\gamma V_{s'}^{\pi_{\mathrm{tx},\pi_{\mathrm{rx}}}}\left([h_{\mathrm{tx}},\langle c,a,s'\rangle],[h_{\mathrm{rx}},\langle m,a\rangle]\right)\right]. \tag*{(19)}

We can compute the value improvement by conditioning on the outcome of mtm_t and considering post-decision states, obtaining

ΔV=β+γ(1−ε)∑s′∈SPs,s′aptx(s′)((1−ε)[Us′,1,s′πtx,πrx([htx,otx0,s′],[hrx(χ)])−Us′,1,s′πtx,πrx([htx,otxft,s′],[hrx(s)])]+ε[Us′,1,χπtx,πrx([htx,otx0,s′],[hrx(χ)])−Us′,1,χπtx,πrx([htx,otxft,s′],[hrx(s)])])+Ps,s′a(1−ptx(s′))([Us′,1,s′πtx,πrx([htx,otx0,s′],[hrx(χ)])−Us′,0,χπtx,πrx([htx,otxft,s′],[hrx(s)])]−β].(20)\begin{aligned} \Delta V={}&\beta+\gamma(1-\varepsilon)\sum_{s'\in\mathcal{S}}P^a_{s,s'}p_{\mathrm{tx}}(s')\left((1-\varepsilon)\left[U_{s',1,s'}^{\pi_{\mathrm{tx},\pi_{\mathrm{rx}}}}\left([h_{\mathrm{tx}},o_{\mathrm{tx}}^{0,s'}],[h_{\mathrm{rx}}^{(\chi)}]\right)-U_{s',1,s'}^{\pi_{\mathrm{tx},\pi_{\mathrm{rx}}}}\left([h_{\mathrm{tx}},o_{\mathrm{tx}}^{f_t,s'}],[h_{\mathrm{rx}}^{(s)}]\right)\right]\right.\\ &\left.+\varepsilon\left[U_{s',1,\chi}^{\pi_{\mathrm{tx},\pi_{\mathrm{rx}}}}\left([h_{\mathrm{tx}},o_{\mathrm{tx}}^{0,s'}],[h_{\mathrm{rx}}^{(\chi)}]\right)-U_{s',1,\chi}^{\pi_{\mathrm{tx},\pi_{\mathrm{rx}}}}\left([h_{\mathrm{tx}},o_{\mathrm{tx}}^{f_t,s'}],[h_{\mathrm{rx}}^{(s)}]\right)\right]\right)\\ &+P^a_{s,s'}(1-p_{\mathrm{tx}}(s'))\left(\left[U_{s',1,s'}^{\pi_{\mathrm{tx},\pi_{\mathrm{rx}}}}\left([h_{\mathrm{tx}},o_{\mathrm{tx}}^{0,s'}],[h_{\mathrm{rx}}^{(\chi)}]\right)-U_{s',0,\chi}^{\pi_{\mathrm{tx},\pi_{\mathrm{rx}}}}\left([h_{\mathrm{tx}},o_{\mathrm{tx}}^{f_t,s'}],[h_{\mathrm{rx}}^{(s)}]\right)\right]-\beta\right]. \tag*{(20)} \end{aligned}

where hrx(s)=[hrx,⟨s,a⟩]h_{\mathrm{rx}}^{(s)}=[h_{\mathrm{rx}},\langle s,a\rangle] and hrx(χ)=[hrx,⟨χ,a⟩]h_{\mathrm{rx}}^{(\chi)}=[h_{\mathrm{rx}},\langle\chi,a\rangle]. We first note that, due to the Markov property, receiving a message at time t+1t+1 cannot decrease future value with respect to receiving it at time tt, as the receiver has better information about the state: accordingly, policy πtx′\pi'_{\mathrm{tx}} always improves the long-term value if the original policy does not transmit in step t+1t+1, and we get condition

ΔV=β+γ(1−ε)∑s′∈SPs,s′aπtx(s′)((1−ε)×[Us′,1,s′πtx,πrx([htx,otx0,s′],hrx(χ))−Us′,1,s′πtx,πrx([htx,otxft,s′],hrx(s))]+ε[Us′,1,χπtx,πrx([htx,otx0,s′],hrx(χ))−Us′,1,χπtx,πrx([htx,otxft,s′],hrx(s))]).(21)\begin{aligned} \Delta V ={}& \beta+\gamma(1-\varepsilon)\sum_{s'\in\mathcal{S}}P^{a}_{s,s'}\pi_{\mathrm{tx}}(s')\Bigl((1-\varepsilon)\\ &\quad\times\left[U^{\pi_{\mathrm{tx}},\pi_{\mathrm{rx}}}_{s',1,s'}([h_{\mathrm{tx}},o_{\mathrm{tx}}^{0,s'}],h_{\mathrm{rx}}^{(\chi)})-U^{\pi_{\mathrm{tx}},\pi_{\mathrm{rx}}}_{s',1,s'}([h_{\mathrm{tx}},o_{\mathrm{tx}}^{f t,s'}],h_{\mathrm{rx}}^{(s)})\right]\\ &\quad+\varepsilon\left[U^{\pi_{\mathrm{tx}},\pi_{\mathrm{rx}}}_{s',1,\chi}([h_{\mathrm{tx}},o_{\mathrm{tx}}^{0,s'}],h_{\mathrm{rx}}^{(\chi)})-U^{\pi_{\mathrm{tx}},\pi_{\mathrm{rx}}}_{s',1,\chi}([h_{\mathrm{tx}},o_{\mathrm{tx}}^{f t,s'}],h_{\mathrm{rx}}^{(s)})\right]\Bigr). \tag*{(21)} \end{aligned}

Thanks to the Markov property, receiving both sts_t and st+1s_{t+1} provides the receiver with the same information as only receiving st+1s_{t+1}. If πtx\pi_{\mathrm{tx}} is the best response to πrx\pi_{\mathrm{rx}}, the first two terms of the sum must thus be identical, and we obtain

ΔV≥β+γ∑s′∈SPs,s′aπtx(s′)ε(1−ε)[Us′,1,χπtx,πrx([htx,otx0,s′],hrx(χ))−Us′,1,χπtx,πrx([htx,otxft,s′],hrx(s))].(22)\Delta V\geq\beta+\gamma\sum_{s'\in\mathcal{S}}P^{a}_{s,s'}\pi_{\mathrm{tx}}(s')\varepsilon(1-\varepsilon)\left[U^{\pi_{\mathrm{tx}},\pi_{\mathrm{rx}}}_{s',1,\chi}([h_{\mathrm{tx}},o_{\mathrm{tx}}^{0,s'}],h_{\mathrm{rx}}^{(\chi)})-U^{\pi_{\mathrm{tx}},\pi_{\mathrm{rx}}}_{s',1,\chi}([h_{\mathrm{tx}},o_{\mathrm{tx}}^{f t,s'}],h_{\mathrm{rx}}^{(s)})\right]. \tag*{(22)}

We denote the minimum and maximum possible long-term rewards for the MDP with ideal communication by Vmin⁡V_{\min} and Vmax⁡V_{\max}, respectively. Since the instantaneous reward is in interval [0,1][0,1], we know that Vmin⁡≥0V_{\min}\geq0 and Vmax⁡≤(1−γ)−1V_{\max}\leq(1-\gamma)^{-1}. We thus compute a more conservative condition that holds for any MDP definition:

ΔV≥β−γ∑s′∈Sε(1−ε)Ps,s′aπtx(s′)(1−γ)−1.(23)\Delta V\geq\beta-\gamma\sum_{s'\in\mathcal{S}}\varepsilon(1-\varepsilon)P^{a}_{s,s'}\pi_{\mathrm{tx}}(s')(1-\gamma)^{-1}. \tag*{(23)}

As ∑s′∈StxPs,s′aπtx(s′)≤1\sum_{s'\in\mathcal{S}_{\mathrm{tx}}}P^{a}_{s,s'}\pi_{\mathrm{tx}}(s')\leq1, we obtain

ΔV≥β−γε(1−ε)(1−γ)−1.(24)\Delta V\geq\beta-\gamma\varepsilon(1-\varepsilon)(1-\gamma)^{-1}. \tag*{(24)}

It is thus easy to see that, under the condition in (11), the value difference is positive, and πtx\pi_{\mathrm{tx}} is not the best response to πrx\pi_{\mathrm{rx}}. We can repeat this for all values of ss in which πrx\pi_{\mathrm{rx}} is not revealing, obtaining a new transmission policy that maintains synchronization at step tt. We can thus extend the result to any time step tt.

Proof of Theorem 4

As we did in the proof of Theorem 3, we consider a policy such that any history htxh_{\mathrm{tx}} is synchronized up to time tt, and a state st=ss_t=s in which πrx\pi_{\mathrm{rx}} is not revealing, but for which πtx(htx)=1\pi_{\mathrm{tx}}(h_{\mathrm{tx}})=1. We define a new transmitter policy πtx′\pi'_{\mathrm{tx}} and show that Vs,tπtx′,πrx(htx,hrx)>Vs,tπtx,πrx(htx,hrx)V^{\pi'_{\mathrm{tx}},\pi_{\mathrm{rx}}}_{s,t}(h_{\mathrm{tx}},h_{\mathrm{rx}})>V^{\pi_{\mathrm{tx}},\pi_{\mathrm{rx}}}_{s,t}(h_{\mathrm{tx}},h_{\mathrm{rx}}). The new policy is

πtx,τ′(htx′)={πtx,τ(htx′),τ<t∨htx⊄htx′,0,τ=t,1,τ=t+1,πtx,t+1(htx,0:t+1′),τ=t+2,πtx,τ(htx′),otherwise,(25)\pi'_{\mathrm{tx},\tau}(h'_{\mathrm{tx}})= \begin{cases} \pi_{\mathrm{tx},\tau}(h'_{\mathrm{tx}}), & \tau<t\lor h_{\mathrm{tx}}\not\subset h'_{\mathrm{tx}},\\ 0, & \tau=t,\\ 1, & \tau=t+1,\\ \pi_{\mathrm{tx},t+1}(h'_{\mathrm{tx},0:t+1}), & \tau=t+2,\\ \pi_{\mathrm{tx},\tau}(h'_{\mathrm{tx}}), & \text{otherwise}, \end{cases} \tag*{(25)}

where, as in the proof of Theorem 3, htx′′h''_{\mathrm{tx}} is a fictitious history. In this case, it identical to htx′h'_{\mathrm{tx}} except for step tt, in which ct′′=1c''_t=1, and ct+1′′=πtx,t+1(htx,0:t+1′)c''_{t+1}=\pi_{\mathrm{tx},t+1}(h'_{\mathrm{tx},0:t+1}). This ensures that the two policies behave identically from step t+3t+3 onward.

In other words, policy πtx,τ′(htx′)\pi'_{\mathrm{tx},\tau}(h'_{\mathrm{tx}}) forces a transmission at step t+1t+1, while its behavior in step t+2t+2 mirrors what the original policy would have done in step t+1t+1. If πtx,t+1(htx,0:t+1′)=0\pi_{\mathrm{tx},t+1}(h'_{\mathrm{tx},0:t+1})=0, 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 πtx,t+1(htx,0:t+1′)=1\pi_{\mathrm{tx},t+1}(h'_{\mathrm{tx},0:t+1})=1, we need to consider two cases, depending on the actions in step t+2t+2. As the selected action depends on the outcomes of transmissions at steps tt and t+1t+1, 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 ct+2=0c_{t+2}=0: in this case, the original policy transmits at steps tt and t+1t+1, while the modified policy transmits at steps t+1t+1 and t+2t+2. The transmission cost is then reduced by (1−γ2)β(1-\gamma^2)\beta due to the discount. Furthermore, since the action of the receiver in step t+1t+1 does not affect st+2s_{t+2}, 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 t+1t+1, the modified policy is at a disadvantage if the transmission made by the original policy at time step tt succeeds, while its own transmission fails. This happens with probability ε(1−ε)\varepsilon(1-\varepsilon), and the maximum reward loss is 11, discounted by γ\gamma. Putting it all together, we get the following condition for ΔV\Delta V being positive:

ΔV≥(1−γ2)β−γε(1−ε).(26)\Delta V\geq(1-\gamma^2)\beta-\gamma\varepsilon(1-\varepsilon). \tag*{(26)}

Setting ΔV>0\Delta V>0 returns the condition in (13).

On the other hand, in the case in which ct+2=1c_{t+2}=1, the transmission cost is reduced by β\beta for the modified policy. However, in addition to the cost at time step t+1t+1, we have to consider that it may maintain a disadvantage even after step t+2t+2: this occurs if both transmissions made by the modified policy fail, while the extra transmission made at time step tt by the original policy is successful. In all other cases, the performance of the two policies from step t+2t+2 onward is matched. Following the same strategy as in the previous proof, we set an upper bound to the value difference as (1−γ)−1(1-\gamma)^{-1}. The value difference is then

ΔV≥β−γε(1−ε)−γ2ε2(1−ε)(1−γ)−1,(27)\Delta V\geq\beta-\gamma\varepsilon(1-\varepsilon)-\gamma^2\varepsilon^2(1-\varepsilon)(1-\gamma)^{-1}, \tag*{(27)}

where the first negative term comes from the possible loss in step t+1t+1, while the second comes from losses from step t+2t+2 onward. Setting ΔV>0\Delta V>0 then yields condition

β>γε(1−ε)+γ2ε2(1−ε)(1−γ)−1.(28)\beta>\gamma\varepsilon(1-\varepsilon)+\gamma^2\varepsilon^2(1-\varepsilon)(1-\gamma)^{-1}. \tag*{(28)}

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 ss and time step tt, thus proving the Theorem.

References

  1. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [40]E. Koutsoupias and C. Papadimitriou, “Worst-case equilibria,” Comput. Science Rev., vol. 3, no. 2, pp. 65–69, May 2009.
  41. [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

Paper details

vlnc:W_jn4ev7ac
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Engineering

GPT-5.6 Sol (bare)

View statement
Looking for related papers…
Contents