# Constrained Average-Reward Intermittently Observable MDPs

Konstantin Avrachenkov, Madhu Dhiman, Veeraruna Kavitha

► To cite this version:

Konstantin Avrachenkov, Madhu Dhiman, Veeraruna Kavitha. Constrained Average-Reward Intermittently Observable MDPs. CDC 2025 - IEEE Conference on Decision and Control, Dec 2025, Rio de Janeiro, Brazil. hal-05458150

HAL Id: hal-05458150

https://inria.hal.science/hal-05458150v1

Submitted on 14 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Constrained Average-Reward Intermittently Observable MDPs

Konstantin Avrachenkov, Madhu Dhiman and Veeraruna Kavitha

*Abstract*— In Markov Decision Processes (MDPs) with intermittent state information, decision-making becomes challenging due to periods of missing observations. Linear programming (LP) methods can play a crucial role in solving MDPs, in particular, with constraints. However, the resultant belief MDPs lead to infinite dimensional LPs, even when the original MDP is with finite state and action spaces. The verification of strong duality becomes non-trivial. This paper investigates the conditions for no duality gap in average-reward finite Markov decision process with intermittent state observations. We first establish that in such MDPs, the belief MDP is unichain if the original Markov chain is recurrent. Furthermore, we establish strong duality of the problem, under the same assumption. Finally, we provide a wireless channel example, where the belief state depends on the last channel state received and the age of the channel state. Our numerical results indicate interesting properties of the solution.

# I. INTRODUCTION

Markov Decision Processes (MDPs) provide a rigorous mathematical framework for sequential decision-making under uncertainty. They have been widely applied across various domains, including wireless communication, finance, and supply chain management. Classical MDPs, as described in [1], operate under the fundamental assumption that the decision-maker has full knowledge of the system's state at every decision epoch. However, in many real-world scenarios, this assumption does not hold, as decision-makers often have access to only partial or delayed state information. This challenge gives rise to Partially Observable MDPs (POMDPs), which have been extensively studied, see e.g. [2] and many references therein. Most of the studies have concentrated on the conditions of the existence of the optimal policies and dynamic programming principle, [3], [4], [5], [6], [7], [8], [9]. However, the literature that studies the infinite-dimensional LPs associated with POMDPs is extremely sparse; the LP approach for POMDP with constraints has received even lesser attention.

In many practical applications, such as those discussed in [2], [10], [11], [12], state information is not only partial but also intermittently available due to factors like communication constraints, sensor failures, or energy limitations. This motivates the study of Intermittently Observable MDPs (IOMDPs) [10], where decision-making must proceed despite missing state observations at certain time steps.

A common approach to handling POMDPs is to reformulate them as belief MDPs, where the decision-maker maintains a probability distribution (or belief) over the system states based on past observations and prior knowledge [2], [13]. While this transformation enables decision-making under uncertainty, it significantly increases computational complexity. Unlike classical MDPs with a finite state space, the belief MDP generally has an uncountable state space, calling for various approximation and state aggregation approaches. Furthermore, even in the case of finite state space models, the MDPs with constraints cannot be solved by value iteration or policy iteration. This challenge has led to the development of Linear Programming (LP)-based methods, which have proven effective for solving constrained MDPs [14]. However, extending LP formulations to IOMDPs is non-trivial, as it requires verifying strong duality, a property that is difficult to establish due to the infinite-dimensional nature of the belief space [15], [14]. In particular, the results in [15] require a certain set of measures being tight (see Assumption A.3 there). However, when the cost function is bounded, as considered in this work, the relevant set of measures becomes significantly large, which is not tight with respect to the required weak topology in [15]; and thus one cannot directly apply the results of [15] to our framework.

Ensuring strong duality is crucial, as it facilitates the efficient computation of optimal policies and extends LP methods to constrained IOMDPs, which are relevant in applications requiring adherence to performance guarantees or safety constraints.

Most of the existing literature on POMDPs and IOMDPs [10], [11], [16], [17] focuses on the discounted cost/reward criterion. The discounted objective has several analytical advantages, including contraction properties that simplify the analysis and guarantee the existence of optimal policies. In [10], the authors analyze an IOMDP under a total expected discounted reward criterion. Our work is inspired by this study but differs in that we consider the average-reward criterion, which presents additional challenges due to the absence of discounting-related contraction properties. The POMDP formulation in general leads to a belief MDP with an uncountable state space. However, following the insights from [10], we demonstrate that a countable belief state representation is sufficient in IOMDPs. In particular, this allows us to handle belief MDPs with a convenient approximation, making the problem more tractable.

Specifically, in this paper, we investigate the conditions under which strong duality holds in an average-reward IOMDP with finite state space and intermittent state observations. Assuming that the underlying Markov chain is recurrent, we

K. Avrachenkov is with INRIA Sophia Antipolis, France. Email: k.avrachenkov@inria.fr; M. Dhiman and V. Kavitha are with the Indian Institute of Technology Bombay, India. Emails: {madhu.dhiman,vkavitha}@iitb.ac.in. The authors are listed in alphabetical order. This work is partially supported by DST-INRIA Cefipra project Learning In Operations and Networks (LION). The paper is accepted at IEEE CDC 2025.
first establish that the corresponding belief MDP is unichain. We then prove that the strong duality holds under the same assumption. This establishes that both the constrained and unconstrained LP formulations of 'recurrent' IOMDPs do not exhibit duality gap. Thus, our results provide a solid foundation for applying LP techniques to solve IOMDPs, both in constrained and unconstrained cases.

Finally, we apply our theoretical results to obtain an (approximate) optimal policy for an application with constraints, that observes the state of the system over a lossy wireless channel. By solving the approximate LPs (obtained after excluding the 'large' age states), we compute the optimal policy that depends upon the last observed state and the age of the information; we further discuss the properties of the solution.

## II. CONSTRAINED FINITE MDP MODEL

A discrete time constrained Markov decision process (MDP) is represented by the tuple $(\mathcal{S}, \mathcal{A}, P, r, c, B)$ where $\mathcal{S}$ is a set of states, $\mathcal{A}$ is a set of actions, $r$ is an immediate reward function, $c$ is an immediate cost function, $B$ is a finite bound on the long run average cost (see (2)) and $P$ is a controlled transition kernel $P: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \to [0, 1]$.

The transition kernel $P(s'|s, a)$ represents the probability of arriving in state $s'$ having taken action $a$ in state $s$:

$$P_a(s, s') = P(s' | s, a) = \Pr(s_{t+1} = s' | s_t = s, a_t = a), \forall t,$$

where $s_t$ and $a_t$ denote the state and action at time $t$. We will use $P_a = [P_a(s, s')]_{s, s'}$ to denote the transition matrix associated with action $a$. Note that without loss of generality we are assuming the same action space for each state.

The immediate reward function $r: \mathcal{S} \times \mathcal{A} \to \mathbb{R}$ (set of real numbers), with $r(s, a)$ representing the immediate expected reward of taking action $a$ in state $s$. In a number of applications, it is useful to consider also the immediate cost function $c: \mathcal{S} \times \mathcal{A} \to \mathbb{R}$. In this work, we assume finiteness of the state space and the action space:

### A.1 The state and action spaces, $\mathcal{S}$ and $\mathcal{A}$ are finite.

We also assume the following recurrence condition, which is satisfied in many practical cases:

### A.2 The MDP $(\mathcal{S}, \mathcal{A}, P, r, c, B)$ is recurrent.

Consider a set of stationary Markov and randomized (SMR) policies for such MDPs [1], [14]; any SMR policy is denoted by $\pi: \mathcal{S} \to \mathbb{P}(\mathcal{A})$, a function that maps the set of states to the set of probability measures on $\mathcal{A}$.

The problem of a constrained average-reward MDP can be formulated as follows:

$$\sup_{\pi \in \text{SMR}} \left( \lim_{T \to \infty} \frac{1}{T} \sum_{t=1}^{T} \mathbb{E}[r(s_t, a_t)] \right), \quad (1)$$

subject to

$$\lim_{T \to \infty} \frac{1}{T} \sum_{t=1}^{T} \mathbb{E}[c(s_t, a_t)] \le B. \quad (2)$$

Under assumptions A.1-2, the above problem has a solution in the set of SMR policies (see e.g., [14]).

## III. IOMDP MODEL

In classical MDP, the system executes the optimal policy $\pi$ in the following manner: at every time step, it observes its current state $s_t$, and chooses an action according to the probability measure $\pi(s_t)$. However, in some applications, the system may not be able to observe current state with perfect information (e.g., states observed over wireless medium are prone to erasures and/or errors, estimation methods are prone to errors, less expensive to observe limited information, etc.). In such partially observable MDPs, the system may observe the current state with varying degrees of information; it can observe some partial information about the current state or may observe none. In this paper, we consider a special case where the system either observes the state completely with a fixed probability or receives zero information. Such systems are called Intermittently Observable MDPs (IOMDPs). In [10], the authors consider an IOMDP with discounted rewards, and we consider a similar setup but for average-reward criteria; we further consider a constrained problem.

Namely, at every time step, the controller observes the current state completely with probability $\rho \in (0, 1]$ or does not observe with complementary probability $1 - \rho$. The observation events are independent and identically distributed across the time steps.

### A. Belief MDP

As is usually done in POMDP literature (see e.g., [2]), we reformulate the problem as a belief MDP. Towards this, we consider 'belief states', the conditional distribution of the current state, given the history of observations.

The belief state at time $t$, denoted by $b_t$, represents the probabilistic estimate of the system state at the same time, given all the available information until $t$; this forms a sufficient statistic for the problem (see [2], [13]). Let $\ell_t$ represent the last observation epoch before time $t$. Then, the belief state $b_t$, equals:

$$b_t := \Pr(s_t | s_{\ell_t}, a_{\ell_t}, a_{\ell_t+1}, \dots, a_{t-1}). \quad (3)$$

Basically, by Markovian nature of the problem and under SMR policies, the belief state is just the function of the last observed state $s_{\ell_t}$ and the sequence of actions thereafter, $(a_{\ell_t}, a_{\ell_t+1}, \dots, a_{t-1})$. In other words, the sequence $(s_{\ell_t}, a_{\ell_t}, a_{\ell_t+1}, \dots, a_{t-1})$ represents the sufficient statistic at time $t$.

If state $s_t$ is observed at time $t$ (and say $s_t = i$), then the belief state $b_t$ is updated to the standard basis vector $e_i$ (vector with $i$-th component as one and all other components being zero). And, if state $s_t$ is not observed (which happens with probability $(1 - \rho)$), then the belief state $b_t$ is updated based on the belief $b_{t-1}$ and the action $a_{t-1}$ of the previous epoch. Let $Q$ represent the transition kernel of the belief states. Using the above arguments, $Q$ is given by

$$Q(b_t | b_{t-1}, a_{t-1}) := \begin{cases} 1 - \rho, & \text{if } b_t = P_{a_{t-1}}^{\top} b_{t-1} \\ \rho [P_{a_{t-1}}^{\top} b_{t-1}]_i, & \text{if } b_t = e_i, i \in \mathcal{S} \\ 0, & \text{otherwise.} \end{cases} \quad (4)$$
In the above, $P_{a_{t-1}}^{\top} b_{t-1}$ is the updated belief distribution, and $[P_{a_{t-1}}^{\top} b_{t-1}]_i$ denotes the $i$-th element of vector $P_{a_{t-1}}^{\top} b_{t-1}$; here $(\cdot)^{\top}$ represents the transpose. We note that the evolution of the belief state (4) is similar to the dynamics considered in [12], [18]. Let $\mathcal{B}$ represent the set of belief states. From (4), we have:

$$ \mathcal{B} := \left\{ \prod_{k=0}^{L} P_{a_k}^{\top} \mathbf{b} : a_k \in \mathcal{A}, \forall k \le L, \mathbf{b} \in \mathcal{E} \text{ and } L \in \{0, 1, \dots\} \right\}, $$

where $\mathcal{E} := \{e_i : i \in \mathcal{S}\}$ represents the set of pure (or just observed) states. Define the function $R: \mathcal{B} \times \mathcal{A} \to \mathbb{R}$ as below:

$$ R(\mathbf{b}, a) = \sum_{s \in \mathcal{S}} \mathbf{b}(s)r(s, a), \quad \forall \mathbf{b} \in \mathcal{B}, a \in \mathcal{A}. \quad (5) $$

Observe here that, for IOMDPs, under any SMR policy, the actions chosen depend (only) upon the belief states at the respective decision epochs. Let $\Pi^b$ represent the set of such SMR policies. Consider any $\pi \in \Pi^b$ and then using (5),

$$ \lim_{T \to \infty} \frac{1}{T} \sum_{t=1}^{T} \mathbb{E}[R(\mathbf{b}_t, a_t)] = \lim_{T \to \infty} \frac{1}{T} \sum_{t=1}^{T} \mathbb{E} \left[ \sum_{s \in \mathcal{S}} \mathbf{b}_t(s) r(s, a_t) \right]. \quad (6) $$

By A.1-2, the limit in the above exists<fnref n="1" />, as it equals the average reward of the original MDP under an appropriate history dependent policy $\pi$. Thus, $R$ can be viewed as the immediate reward function defined in terms of the belief states. Further, boundedness of $r(\cdot, \cdot)$ implies that of $R(\cdot, \cdot)$. Finally, the belief MDP is given by tuple $(\mathcal{B}, \mathcal{A}, \mathcal{Q}, \rho, R)$. Now, the unconstrained problem for the IOMDP can be defined by the following:

$$ \sup_{\pi \in \Pi^b} \left( \lim_{T \to \infty} \frac{1}{T} \sum_{t=1}^{T} \mathbb{E}[R(\mathbf{b}_t, a_t)] \right). \quad (7) $$

By Theorem 1 given below, the belief MDP is unichain under A.1-2 and hence the above problem is well defined. Likewise, we also consider the constrained (see (2)) average reward belief MDP, where we aim to solve:

$$ \sup_{\pi \in \Pi^b} \left( \lim_{T \to \infty} \frac{1}{T} \sum_{t=1}^{T} \mathbb{E}[R(\mathbf{b}_t, a_t)] \right), \quad \text{subject to} \\ \lim_{T \to \infty} \frac{1}{T} \sum_{t=1}^{T} \mathbb{E}[C(\mathbf{b}_t, a_t)] \le B, \quad \text{where} \quad (8) \\ C(\mathbf{b}, a) := \sum_{s \in \mathcal{S}} \mathbf{b}(s)c(s, a), \quad \forall \mathbf{b} \in \mathcal{B}, a \in \mathcal{A}. $$

In the above, $C(\cdot, \cdot)$ is defined similarly to (5). We now proceed to proving that the belief MDP is unichain. Towards that, we require some definitions of [14], which we reproduce here in our notations:

* **$\mu$-bounded function space, $F^\mu$:** For given $\mu: \mathcal{B} \to \mathbb{R}$, $F^\mu$ is space of all $\mu$-bounded functions, i.e.,

$$ F^{\mu} := \left\{ q: \mathcal{B} \to \mathbb{R}; \sup_{\mathbf{b} \in \mathcal{B}} \left( \frac{q(\mathbf{b})}{\mu(\mathbf{b})} \right) < \infty \right\}. $$

* **Contracting MDP:** Let $\mathcal{B}'$ and $\mathcal{E}$ be two disjoint sets of states with $\mathcal{B} = \mathcal{B}' \cup \mathcal{E}$. An MDP is said to be contracting (on $\mathcal{B}'$) if there exist a scalar $\xi \in [0, 1)$ (called the contracting factor) and a function $\mu: \mathcal{B} \to [1, \infty)$, such that for all $\mathbf{b} \in \mathcal{B}, a \in \mathcal{A}$,

$$ \sum_{\mathbf{b}' \notin \mathcal{B}} Q(\mathbf{b}'|\mathbf{b}, a)\mu(\mathbf{b}') \le \xi\mu(\mathbf{b}), $$

with additional three conditions on MDP setup:

1) $\langle \beta, \mu \rangle = \int \mu(\mathbf{b})\betadb) < \infty$, where $\beta$ is the initial state distribution;

2) The transition probabilities $Q$ are $\mu$-continuous, i.e., if $a_n \to a$, then for all $\mathbf{b} \in \mathcal{B}$

$$ \lim_{n \to \infty} \sum_{\mathbf{b}' \in \mathcal{B}} |Q(\mathbf{b}'|\mathbf{b}, a_n) - Q(\mathbf{b}'|\mathbf{b}, a)|\mu(\mathbf{b}') = 0; $$

3) $R(\cdot, \cdot)$ is $\mu$-bounded by some finite constant. Additionally, for constrained IOMDP problem, $C(\cdot, \cdot)$ is also $\mu$-bounded by some finite constant.

* **Uniform Lyapunov function:** A function $\mu: \mathcal{B} \to [1, \infty)$ is called a uniform Lyapunov function if there exist constants $\lambda \in (0, 1)$, $B > 0$ and a finite set $\mathcal{C} \subset \mathcal{B}$ such that for all states $\mathbf{b} \in \mathcal{B} \setminus \mathcal{C}$ and all $a \in \mathcal{A}$, the expected drift condition holds:

$$ \sum_{\mathbf{b}' \in \mathcal{B}} Q(\mathbf{b}'|\mathbf{b}, a)\mu(\mathbf{b}') \le \mu(\mathbf{b}) - \lambda. $$

It is clear from [1, Section 8.2]), every SMR policy $\pi$ will generate a belief Markov chain. Now, we show that the belief MDP is unichain and characterize a few properties, which are useful to prove the ensuing results.

**Theorem 1:** [Unichain] Assume A.1-2, then the following are true:

(i) For any SMR policy $\pi$, the belief Markov chain has a single positive recurrent class and absorption into the positive recurrent class takes place in a finite expected time.

(ii) Belief MDP is contracting and has a uniform Lyapunov function.

**Proof** is in Appendix IX. $\square$

Indeed, by part (i), the belief MDP is unichain, which means that (7) and (8) are well defined. And, part (ii) implies that the belief MDP has a uniform Lyapunov function, which will help in proving the strong duality in the following section.

## IV. STRONG DUALITY

It is well known that one can solve perfect information finite MDPs, using linear programming (LP) techniques. In fact, the LP based techniques are extremely useful for solving constrained finite MDPs. The quest in this section is to investigate if the same is possible for the case with intermittent observations.

<footnote n="1">¹Any SMR policy based on belief states is a history dependent policy of the original MDP and by [1, Theorem 6.9.1], see also [14], the performance under each such policy is achieved by that under an SMR policy and hence, the limit exists by A.1-2. Further, the problem in (7) can be seen as a problem under certain 'observability' constraints (see (5)).</footnote>
In the case of IOMDPs, the belief state space is countable. Hence, a priori, it is not evident if the LP based approach can be used here; the primary concern is related to the duality gap. The main aim of the paper is to address this issue. We begin with defining the potential LP for unconstrained IOMDPs in the immediate next.

### A. Unconstrained IOMDPs

The primal linear program (LP) for the belief MDP with objective function as in (7) is given by:

$$ \inf_{\mathbf{x} = \{\mathbf{x}(\mathbf{b},a)\}_{\mathbf{b},a}} \sum_{\mathbf{b},a} -R(\mathbf{b},a)x(\mathbf{b},a) \quad \text{subject to} \\ \sum_{a} x(\mathbf{b}',a) = \sum_{\mathbf{b},a} Q(\mathbf{b}'|\mathbf{b},a)x(\mathbf{b},a), \quad \forall \mathbf{b}' \in \mathcal{B} \\ \sum_{\mathbf{b},a} x(\mathbf{b},a) = 1, \quad x(\mathbf{b},a) \ge 0. \qquad (9) $$

Since our work mostly depends upon the results from [14], we consider now onwards the cost (which is negative of reward) minimization as in [14]. Here, each $\{x(\mathbf{b},a)\}_{\mathbf{b},a}$ vector is supposed to represent the occupancy measures for some policy $\pi \in \Pi^b$, where

$$ x(\mathbf{b},a) := \lim_{T \to \infty} \frac{1}{T} \sum_{t=1}^{T} \Pr(\mathbf{b}_t = \mathbf{b}, a_t = a), \quad \forall \mathbf{b} \in \mathcal{B}, a \in \mathcal{A}. $$

Since $\mathbf{b}' \in \mathcal{B}$ (a countable space), the linear program (9) operates over an infinite-dimensional space, making the solution procedure non-trivial.

Before stating the result, we define the standard average cost optimality equation (ACOE). For that, first we define the gain and the bias functions for the belief MDP. The gain of the Markov chain under policy $\pi$ with the initial state $\mathbf{b}$ is defined by

$$ g^{\pi}(\mathbf{b}) := \lim_{T \to \infty} \frac{1}{T} \mathbb{E}_{\mathbf{b}} \left[ \sum_{t=1}^{T} -R(\mathbf{b}_t, \pi(\mathbf{b}_t)) \right], \quad \forall \mathbf{b} \in \mathcal{B}. $$

Since $R(\cdot, \cdot)$ is a bounded function and $\mathcal{S}, \mathcal{A}$ are finite, $g^\pi$ is well defined and is also bounded, for every SMR policy $\pi$; also observe $g^\pi(\mathbf{b}) = g^\pi$, a constant for all belief states $\mathbf{b}$, by unichain property proved in Theorem 1. Thus the bias function $h^\pi(\cdot)$ is also well defined and is given by:

$$ h^{\pi}(\mathbf{b}) := \lim_{T \to \infty} \frac{1}{T} \sum_{k=1}^{T} \mathbb{E}_{\mathbf{b}} \left[ \sum_{t=1}^{k} \left( -R(\mathbf{b}_t, \pi(\mathbf{b}_t)) - g^{\pi}(\mathbf{b}_t) \right) \right], \quad \forall \mathbf{b} \in \mathcal{B}. \quad (10) $$

Using the unichain property proved in Theorem 1.(i), the ACOE can be written as (see e.g., [1])

$$ \phi(\mathbf{b}) + \psi = \min_{a \in \mathcal{A}} \left( -R(b,a) + \sum_{b' \in \mathcal{B}} Q(b'|b,a)\phi(b') \right), \quad (11) $$

where $\psi$ is some scalar and $\phi: \mathcal{B} \to \mathbb{R}$. If for some SMR policy $\pi$, equation (11) is satisfied with $\psi = g^\pi$ and $\phi(\mathbf{b}) =$

$h^\pi(\mathbf{b})$ for all $\mathbf{b}$, then $g^\pi$ is the optimal value (see e.g., [1], [14]). Now, the dual problem of (9) is given by

$$ \sup_{\psi, \phi} \psi \quad \text{subject to} \qquad (12) \\ \phi(\mathbf{b}) + \psi \leq -R(\mathbf{b}, a) + \sum_{\mathbf{b}' \in \mathcal{B}} Q(\mathbf{b}'|\mathbf{b}, a), \\ \text{for all } \mathbf{b} \in \mathcal{B}, a \in \mathcal{A}, \psi \in \mathbb{R}, \phi(\cdot) \in F^{\mu}. $$

We have the following result:

**Theorem 2:** [Strong duality] Assume A.1-2, then

(i) There exists an average optimal stationary policy;

(ii) The LP (12) is solvable and there is no duality gap.

**Proof:** From Theorem 1, the belief MDP has a uniform Lyapunov function. As the immediate rewards are bounded and by the definition of the dual (12) itself, $\phi(\cdot)$ is restricted to linear space $F^\mu$, then using theorem [14, Theorem 12.4], the dual (12) is feasible and has no duality gap. $\square$

### B. Constrained IOMDPs

In the previous subsection IV-A, we discussed the unconstrained belief MDP with average reward criterion. We establish strong duality for the same in Theorem 2. In this subsection, our aim is to prove the strong duality for the constrained belief MDP. Specifically, we consider the belief MDP problem formulated in (8). Then, one can define the belief states as in the previous section and the LP that can potentially solve the constrained IOMDP problem (8):

$$ \inf_{\mathbf{x} = \{\mathbf{x}(\mathbf{b},a)\}_{\mathbf{b},a}} \sum_{\mathbf{b},a} -R(\mathbf{b},a)x(\mathbf{b},a) \quad \text{subject to} \qquad (13) \\ \sum_{\mathbf{b},a} C(\mathbf{b},a)x(\mathbf{b},a) \leq B, \\ \sum_{a} x(\mathbf{b}',a) = \sum_{\mathbf{b},a} Q(\mathbf{b}'|\mathbf{b},a)x(\mathbf{b},a), \quad \forall \mathbf{b}' \qquad (14) \\ \sum_{\mathbf{b},a} x(\mathbf{b},a) = 1, \quad x(\mathbf{b},a) \geq 0, \quad \forall \mathbf{b},a, $$

where $\mathbf{b} \in \mathcal{B}$ represents the belief state and

$$ C(\mathbf{b},a) := \sum_{s \in \mathcal{S}} \mathbf{b}(s)c(s,a), \qquad (15) $$

which is bounded since $c(\cdot, \cdot)$ is bounded. Now following the same procedure as in the previous subsection IV-A, the dual problem of (13) is given by

$$ \sup_{\psi, \phi, \lambda \geq 0} (\psi - \lambda B) \quad \text{subject to} \qquad (16) \\ \phi(\mathbf{b}) + \psi \leq -R(\mathbf{b}, a) + \lambda C(\mathbf{b}, a) + \sum_{\mathbf{b}' \in \mathcal{B}} Q(\mathbf{b}'|\mathbf{b}, a), \\ \text{for all } \mathbf{b} \in \mathcal{B}, a \in \mathcal{A}, \psi \in \mathbb{R}, \phi(\cdot) \in F^{\mu}. $$

We have the following result:

**Theorem 3:** [Strong duality for constrained IOMDPs]

Assume A.1-2, then:

(i) There exists an average optimal stationary policy;

(ii) The LP (16) is solvable and there is no duality gap.

**Proof:** Here, constraint coefficient $C(\cdot, \cdot)$ is also bounded. Thus, the result is followed using same arguments as in proof of Theorem 2, only the last step is replaced by [14, Theorem 12.9]. $\square$
## V. WIRELESS CHANNEL APPLICATION

Consider a remote control system in which a controller regulates the operation of a dynamic process based on state measurements generated by a spatially separated sensor. The sensor observes the system state perfectly, but the controller receives these observations over a wireless communication channel that is unreliable and time-varying. As a result, the controller does not always have access to the current system state and must operate based on delayed information.

The system state process $\{s_t\}_{t \ge 0}$ evolves on a finite state space $\mathcal{S} := \{1, 2, \dots, k\}$ according to a time-homogeneous Markov chain with transition probabilities $P_W := \{p_W(s' | s)\}_{s,s' \in \mathcal{S}}$. The evolution of the system is autonomous and does not depend on the controller's actions. State 1 represents the least desirable system condition, while state $k$ represents the most desirable condition, with intermediate states ordered accordingly. We assume that $P_W$ is irreducible and positive recurrent.

At each time step, the controller selects an action $a_t \in \mathcal{A}$. If the system is in state $s_t = s$ and action $a_t = a$ is applied, the controller receives a utility $r(s, a)$ and incurs an instantaneous cost $c(a)$. The controller is subject to an average-cost constraint

$$ \limsup_{T \to \infty} \frac{1}{T} \sum_{t=1}^{T} \mathbb{E}[c(a_t)] \le B, \quad (17) $$

for some finite budget $B > 0$.

**Markov-modulated observation delays.** The sensor attempts to transmit the current system state to the controller at every time step. However, whether a transmission is successful depends on the condition of the wireless channel. The channel condition is modeled by an exogenous finite-state Markov chain $\{w_t\}_{t \ge 0}$ taking values in $\mathcal{W} := \{1, 2, \dots, m\}$, with transition matrix $P_M := \{P_M(w' | w)\}_{w,w' \in \mathcal{W}}$. Each channel state $w \in \mathcal{W}$ represents a different quality regime of the communication medium (e.g., good, moderate, or poor).

Conditioned on $w_t = w$, the transmission of the sensor observation at time $t$ is successful with probability $\rho(w) \in (0, 1)$. If the transmission is successful, the controller receives the current state $s_t$ without error. If the transmission fails, no observation is received and the controller must rely on previously received information. Thus, the delay in the controller's information is random and its statistics are governed by the Markov chain $\{w_t\}$.

**Information available to the controller.** At any time $t$, the controller's information can be summarized by the tuple

$$ \theta_t := (s_t^{\text{last}}, \eta_t, w_t), $$

where $s_t^{\text{last}}$ denotes the most recently observed system state, $\eta_t \in \mathbb{N}_0$ denotes the age of the information (i.e., the number of time steps since the last successful observation), and $w_t$ denotes the current channel state. Given $\theta_t = (s, \eta, w)$, the controller's belief about the current system state is

$$ \mathbb{P}(s_t = s' | \theta_t) = [P_W^{\eta}]_{s,s'}, \quad s' \in \mathcal{S}. $$

**Decision-making under delayed information.** Since the controller does not observe the current system state directly, actions must be chosen based on the belief induced by the last observed state and the age of the information. For a belief state $\theta = (s, \eta, w)$ and action $a$, the expected one-step utility is

$$ R(\theta, a) := \sum_{s' \in \mathcal{S}} [P_W^{\eta}]_{s,s'} r(s', a), $$

while the cost remains $C(a) := c(a)$. The control objective is to maximize the long-run average expected utility subject to the average-cost constraint (17), using policies that depend only on the available information $\theta_t$.

This example captures practical situations in remote monitoring and control systems where observation delays are neither independent nor memoryless, but instead are correlated over time through an underlying Markov process modeling the communication environment.

## VI. NUMERICAL RESULTS

In this numerical study, we approximately solve the LP (??) and find a near-optimal policy for the application with wireless observations. The aim here is to understand the properties of the near-optimal policy related to various system parameters; with the more specific focus being on age dependency.

By established strong duality, one can use LP (??) to find the optimal policy. However, the dual LP is infinite dimensional, and hence one needs to truncate (??) appropriately to numerically derive a 'good' or near-optimal policy. The age variables are geometrically distributed, and hence the natural choice is to truncate all the belief states with large age components. Thus, we consider the $K$-truncated approximate LP, with belief states spanning over $\{(s, \eta) : s \in \mathcal{S}, \eta \le K\}$. We leave formal justification of this approximation that can be done with the help of [5], [19], [20] as a topic for future research.

We consider the following set the parameters: $\mathcal{S} = \{1, 2\}$, $\mathcal{A} = \{a_1, a_2\}$, $C(a) = (2+a)^2$, $B = 10.4$, rewards and transition probabilities are (respectively)

$$ [r(s, a)]_{s,a} = \begin{bmatrix} 0 & 1 \\ 1 & 4 \end{bmatrix} \quad \text{and} \quad P_W = \begin{bmatrix} 0.7 & 0.3 \\ 0.1 & 0.9 \end{bmatrix}. $$

The idea here is to consider a skewed system, where state 2 is the first choice with perfect information and limited energy budget, and then understand the age-dependent characteristics of the optimal policy. Further, from the transition matrix $P_W$, the system has higher tendency to prolong in state 2 than in state 1. This aspect can further accentuate the age dependencies and we proceed immediately towards numerically studying the same. In the examples of this section, we consider $\rho \le 0.6$ and hence set $K = 10$; this provides sufficiently good approximation (observe that $0.6^{10} \approx 0.006$, which is sufficiently small).

### A. Study with respect to age

In Tables I-II, we vary the observation probability $\rho$ and study the corresponding variations in the (age-dependent)
optimal policy. In Table I, we tabulate the probability of choosing lower energy $a = a_1$ at different ages and with state 1 (for brevity, we denote $\pi^*(s=1, \eta)$ by $d_{\eta}^*$). As seen from Table I, at $\rho = 0.1$, it is optimal to choose high energy for higher ages; observe $d_{\eta}^* = 0$ for higher ages $\eta$, when $\rho = 0.1$; this is probably due to the fact that the belief of being in state 2 increases with age.

<table><caption>TABLE I
STATE 1: OPTIMAL POLICY (PROBABILITY OF LOW ENERGY $a_1$)</caption><thead><tr><th>ρ</th><th>η=0</th><th>η=1</th><th>η=2</th><th>η=3</th><th>η=4</th></tr></thead><tbody><tr><td>0.1</td><td>1</td><td>1</td><td>1</td><td>0.8208</td><td>0</td></tr><tr><td>0.2</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>0.3</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>0.4</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>0.5</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>0.6</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr></tbody></table>

<table><caption>TABLE II
STATE 2: OPTIMAL POLICY (PROBABILITY OF LOW ENERGY $a_1$)</caption><thead><tr><th>ρ</th><th>η=0</th><th>η=1</th><th>η=2</th><th>η=3</th><th>η=4</th></tr></thead><tbody><tr><td>0.1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>0.2</td><td>0</td><td>0</td><td>0.5786</td><td>1</td><td>1</td></tr><tr><td>0.3</td><td>0</td><td>0.9973</td><td>1</td><td>1</td><td>1</td></tr><tr><td>0.4</td><td>0.3178</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>0.5</td><td>0.4650</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>0.6</td><td>0.5554</td><td>1</td><td>1</td><td>1</td><td>1</td></tr></tbody></table>

More interestingly, this phenomenon is not observed at higher $\rho = 0.6$, $d_{\eta}^* = 1$ for all $\eta$; with larger $\rho$, the chances of observing the true state increase; in other words, $P(s=2, \eta=0) = v(2,0)$ increases and this coupled with the (same) energy constraint could be the cause; basically, with larger $\rho$ high energy $a = a_2$ is chosen for states with more certainty.

In Table II, we tabulate the optimal policy corresponding to state 2. The observations again mirror similar aspects. A notable observation is that with $\rho = 0.6$, at state 2 and age $\eta = 0$ (i.e., with perfect information of being in 'optimal' state) the probability of choosing high energy $a = a_2$ is set at the maximum possible value that satisfies the energy budget constraint.

In summary, with larger $\rho = 0.6$, the high-energy action ($a = a_2$) is chosen only for belief states with more certainty of being in state 2—the optimal probability of spending low energy $a_1$ is one, for state 2 with $\eta \ge 1$ and at all ages with state 1. However, when $\rho$ decreases, the probability of choosing the low energy option $a_1$ decreases with high ages in state 1 and increases with high ages in state 2, where the belief of being in state 2 is higher.

## B. Study with respect to $\rho$

In Tables I-II, we also analyze the optimal policy dependency on the observation probability $\rho$. From the tables, when the age $\eta$ is large, the probability of spending low energy $d_{\eta}^*$ increases with observation probability $\rho$. This is again due to energy budget constraint—as $\rho$ increases, it is optimal to utilize high energy action $a_2$ on belief states with higher certainty of being in state 2.

# VII. CONCLUSION

This paper studies the average reward intermittently observable MDPs. We assumed that the state is observed intermittently with a fixed probability. We first formulated the IOMDP as belief MDP, which has countable state space. We proved that the belief Markov chain is unichain, when the original MDP is recurrent. Under the same recurrence assumption, we have established that the strong duality holds for both unconstrained and constrained belief MDPs.

Finally, a wireless example with observation erasures is provided, where the optimal policy has to choose the energy to be spent on utilizing the system depending upon the age of the information and the last observed state. We solve the problem approximately and numerically using our LP approach and make some interesting observations about the structure of the near-optimal policy.

# VIII. FUTURE WORK

As a first direction, we would like to extend the present results by considering a multi-chain model in place of Assumption A.2. Then, it is interesting to investigate the sensitivity of the proposed framework with respect to variations in system parameters and uncertainty factors that may arise in practical applications. Another line of extension will focus on expanding the numerical experiments to multi-state settings, thereby enabling a more comprehensive evaluation of the policy structure. In addition, we aim to study and compare the performance of different truncation strategies, including adaptive approaches where the truncation level $K$ is dynamically adjusted.

# IX. APPENDIX

**Proof of Theorem 1: Proof of part (i):** Fix any SMR policy $\pi$. Then the following is true.

*Existence of single recurrent class:* To begin with, observe that, under A.2, the pure states, i.e., $b \in \mathcal{C} = \{e_i : i \in \mathcal{S}\}$ are all recurrent. Thus, there exists at least one closed recurrent class. We now prove by contradiction that there exists unique recurrent class. Suppose there exist two closed recurrent classes, say $\mathcal{C}_1$ and $\mathcal{C}_2$, both containing pure belief states. Without loss of generality, assume $\{e_i : i \le n < |\mathcal{S}|\} \subset \mathcal{C}_1$ and $\{e_i : i > n\} \subset \mathcal{C}_2$.

By assumption A.2, there exists an $n > 0$ such that $P_a^n(i, j) > 0$ for all $i, j \in \mathcal{S}$ and all $a \in \mathcal{A}$. Thus, the belief transition probability from (??), satisfies

$$Q^n(e_j | e_i, a) > \rho \min_a P_a^n(i, j) > 0, \text{ for all } i, j \in \mathcal{S} \text{ and } a \in \mathcal{A}.$$

Consequently, there exists a strictly positive probability of transitioning from $\mathcal{C}_1$ to $\mathcal{C}_2$ and vice versa. This contradicts the definition of closed recurrent classes. It is clear (for example) that $\mathcal{C}_2$ is not recurrent if $\mathcal{C} \subset \mathcal{C}_1$.

Let $\mathcal{C}$ be the unique recurrent class. Next, we establish that any state outside $\mathcal{C}$ must be transient. Since $\mathcal{C} \subset \mathcal{C}$, any belief state $b \notin \mathcal{C}$ must satisfy $b \notin \mathcal{C}$. From the belief transition probability (4), there is a strictly positive probability of transitioning from such a belief state $b$ to some $e_i \in \mathcal{C}$. This implies that $b$ is a transient state. Since the time
between two consecutive state observations is geometrically distributed, the absorption expected time to the single class is finite. Hence, the assumption B1 from [14, Chapter 11] is satisfied.

**Positive recurrence:** Now, we consider the closed recurrent class $\mathcal{C}$ and focus on the belief chain evolving only over $\mathcal{C}$ as state space. Take set $\mathcal{C}$ and consider the function $\mu: \mathcal{C} \to [1, \infty)$ such that

$$ \mu(\mathbf{b}) = \begin{cases} 2, & \mathbf{b} \in \mathcal{C} \setminus \mathcal{C}, \\ 1, & \mathbf{b} \in \mathcal{C}. \end{cases} \qquad (18) $$

As $\mathcal{S}$ is finite set, $\mathcal{C}$ is also finite. Using Foster's criteria [21, Theorem 2.6.4], for $\mathbf{b} \in \mathcal{C} \setminus \mathcal{C}$

$$ \begin{aligned} \mathbb{E}[\mu(\mathbf{b}_{t+1}) - \mu(\mathbf{b}_t)|\mathbf{b}_t = \mathbf{b}] &= \sum_{\mathbf{b}' \in \mathcal{C}} Q(\mathbf{b}'|\mathbf{b}, \pi(\mathbf{b})) (\mu(\mathbf{b}') - \mu(\mathbf{b})) \\ &= -\sum_{\mathbf{b}' \in \mathcal{C}} Q(\mathbf{b}'|\mathbf{b}, \pi(\mathbf{b})). \end{aligned} $$

Also, $\mathbb{E}[\mu(\mathbf{b}_{t+1})|\mathbf{b}_t = \mathbf{b}] = \sum_{\mathbf{b}' \in \mathcal{C}} Q(\mathbf{b}'|\mathbf{b}, \pi(\mathbf{b}))\mu(\mathbf{b}') \le 2$, for all $\mathbf{b} \in \mathcal{C}$. As belief chain is irreducible over $\mathcal{C}$, using [21, Theorem 2.6.4], it is positive recurrent.

**Proof of part (ii):** Consider the function $\mu: \mathcal{B} \to [1, \infty)$, such that

$$ \mu(\mathbf{b}) = \begin{cases} 1, & \mathbf{b} \in \mathcal{B} \setminus \mathcal{C}, \\ 2, & \mathbf{b} \in \mathcal{C}. \end{cases} $$

Now, for contraction mapping, we consider for any $\mathbf{b} \in \mathcal{B}$,

$$ \sum_{\mathbf{b}' \notin \mathcal{C}} Q(\mathbf{b}'|\mathbf{b}, a)\mu(\mathbf{b}') = (1-\rho) \le (1-\rho)\mu(\mathbf{b}). $$

Here, $(1-\rho) \in [0, 1)$. Also, 1) $\langle\beta, \mu\rangle < \infty$ as both $\beta$ (initial distribution) and $\mu$ are bounded. 2) As $\mathcal{A}$ set is finite, then under discrete topology, the following condition is also satisfied, as $a_n \to a$

$$ \lim_{n \to \infty} \sum_{\mathbf{b}' \in \mathcal{B}} |Q(\mathbf{b}'|\mathbf{b}, a_n) - Q(\mathbf{b}'|\mathbf{b}, a)|\mu(\mathbf{b}') = 0. $$

3) Now, from the boundness of $R(\cdot, \cdot)$ and the boundness of $\mu(\cdot)$ (see (18)), we conclude that $R(\cdot, \cdot)$ is $\mu$-bounded. Thus, all the conditions for the contracting MDP are satisfied.

**Proof of uniform Lyapunov function:** Now, by [14, Lemma 11.5], the following conditions are satisfied (equivalent to B2 and B3 in [14, Chapter 11]):

1) Given a policy $\pi$ and initial distribution $\beta$, the expected occupation measures $\{f^t(\beta, \pi)\}_t$ are tight, where

$$ f^t(\beta, \pi)(\mathbf{b}, a) := \frac{1}{t} \sum_{s=1}^{t} Q_{\beta}^{\pi}(\mathbf{b}_s = \mathbf{b}, a_s = a), $$

with $Q_{\beta}^{\pi}$ is probability generated by initial distribution $\beta$ and policy $\pi$.

2) Given a policy $\pi$ and initial distribution $\beta$, the expected occupation measures $\{f^t(\beta, \pi)\}_t$ are integrable with respect to the absolute value of the immediate reward $R$, uniformly in $t$.

As both the above conditions are satisfied, by [14, Theorem 11.14], the belief MDP has a uniform Lyapunov function. $\square$

REFERENCES

[1] M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, 2nd ed. Hoboken, NJ: John Wiley & Sons, 2014.

[2] V. Krishnamurthy, Partially observed Markov decision processes. Cambridge University Press, 2016.

[3] V. S. Borkar, "Average cost dynamic programming equations for controlled Markov chains with partial observations," SIAM Journal on Control and Optimization, vol. 39, no. 3, pp. 673–681, 2000.

[4] — "Dynamic programming for ergodic control of Markov chains under partial observations: A correction," SIAM Journal on Control and Optimization, vol. 45, no. 6, pp. 2299–2304, 2007.

[5] Y. E. Demirci, A. D. Kara, and S. Yüksel, "Average cost optimality of partially observed MDPs: Contraction of nonlinear filters and existence of optimal solutions and approximations," SIAM Journal on Control and Optimization, vol. 62, no. 6, pp. 2859–2883, 2024.

[6] S.-P. Hsu, D.-M. Chuang, and A. Arapostathis, "On the existence of stationary optimal policies for partially observed MDPs under the long-run average cost criterion," Systems & Control Letters, 2006.

[7] A. Kara and S. Yüksel, "Near optimality of finite memory feedback policies in partially observed Markov decision processes," Journal of Machine Learning Research, vol. 23, no. 11, pp. 1–46, 2022.

[8] L. K. Platzman, "Optimal infinite-horizon undiscounted control of finite probabilistic systems," SIAM Journal on Control and Optimization, vol. 18, no. 4, pp. 362–380, 1980.

[9] W. J. Runggaldier and L. Stettner, "Nearly optimal controls for stochastic ergodic problems with partial observation," SIAM Journal on Control and Optimization, vol. 31, no. 1, pp. 180–218, 1993.

[10] G. Chen and S.-C. Liew, "Intermittently observable Markov decision processes," arXiv preprint arXiv:2302.11761, 2023.

[11] N. Khan and V. Subramanian, "Cooperative multi-agent constrained POMDPs: Strong duality and primal-dual reinforcement learning with approximate information states," arXiv preprint arXiv:2307.16536.

[12] D. Shuman and et al, "Measurement scheduling for soil moisture sensing: From physical models to optimal control," Proceedings of the IEEE, vol. 98, no. 11, pp. 1918–1933, 2010.

[13] D. Bertsekas and S. E. Shreve, Stochastic optimal control: The discrete-time case. Athena Scientific, 1996, vol. 5.

[14] E. Altman, Constrained Markov decision processes. CRC, 1999.

[15] J. B. Lasserre, "Average optimal stationary policies and linear programming in countable space Markov decision processes," Journal of Mathematical Analysis and Applications, vol. 183, no. 1, pp. 233–249.

[16] M. H. Lim and et al, "Optimality guarantees for particle belief approximation of POMDPs," Journal of Artificial Intelligence Research, vol. 77, pp. 1591–1636, 2023.

[17] M. Ahmadi, N. Jansen, B. Wu, and U. Topcu, "Control theory meets POMDPs: A hybrid systems approach," IEEE Transactions on Automatic Control, vol. 66, no. 11, pp. 5191–5204, 2020.

[18] N. Akbarzadeh and A. Mahajan, "Two families of indexable partially observable restless bandits and Whittle index computation," Performance Evaluation, vol. 163, p. 102394, 2024.

[19] O. Hernández-Lerma, Adaptive Markov control processes. Springer, 2012.

[20] O. Hernández-Lerma and J. B. Lasserre, Further topics on discrete-time Markov control processes. Springer, 2012.

[21] M. Menshikov, S. Popov, and A. Wade, Non-homogeneous random walks: Lyapunov function methods for near-critical stochastic systems. Cambridge University Press, 2016.