# Weighted Moment-SoS approach to POMDPs with polynomial data

Konstantin Avrachenkov, Lucas Gamertsfelder, Bernard Mourrain

► To cite this version:

Konstantin Avrachenkov, Lucas Gamertsfelder, Bernard Mourrain. Weighted Moment-SoS approach to POMDPs with polynomial data. 2025. hal-05355845

HAL Id: hal-05355845

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

Preprint submitted on 12 Nov 2025

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 Attribution 4.0 International License
# Weighted Moment-SoS approach to POMDPs with polynomial data

Konstantin Avrachenkov<fnref n="1" />, Lucas Gamersfelder<fnref n="2" /> and Bernard Mourrain<fnref n="2" />

**Abstract**—We present a novel infinite-dimensional linear programming (IDLP) based method for solving Partially Observable Markov Decision Processes (POMDPs) via Moment-SoS hierarchies. Standard belief-state IDLP formulations yield rational dynamics via the Bayesian filter, obstructing direct use of Moment-SoS relaxations. To address this, we reformulate the POMDP over unnormalized beliefs, yielding polynomial system dynamics. This formulation, however, breaks contractivity of the Bellman operator, rendering conventional IDLPs ill-posed. Our key contribution is to restore contractivity by introducing an $l_1$-based Lyapunov weight and formulating the control problem in a weighted Banach space. The resulting Bellman operator becomes contractive, yielding a well-posed IDLP with strong duality. This leads to a generalized moment problem (GMP) formulation, solvable via Moment-SoS relaxations. We validate the method on the two-armed bandit and tiger problems, generating approximations for optimal policies and optimal values.

## I. INTRODUCTION

Partially Observable Markov Decision Processes (POMDPs) provide a framework for decision-making under uncertainty, with numerous applications such as controlled sensing, machine learning, and economics. A well-established approach for continuous-state optimal control problems is to formulate them as infinite-dimensional linear programs (IDLPs) over occupational measures [FGL08], [GR06], [HLL02], [BB96], [Bor88], [BGQ11], [KS98]. LP-based optimal control problems can be approached either through grid-based discretization of the state space (see, e.g., [GR06], [GQ09], [GRT12]) or via grid-free relaxations such as the Moment-Sum-of-Squares (SoS) hierarchy (see e.g. [HP14], [KHJ17], [HKL20]). While Moment-SoS methods have been successfully applied to continuous-state control problems, extending them to POMDPs is nontrivial because the belief-state dynamics are rational rather than polynomial. To address this issue, we reformulate the control problem over unnormalized beliefs, converting the rational belief dynamics into a polynomial. This transformation, however, breaks the contractivity of the Bellman operator, rendering standard IDLP formulations ill-posed. We resolve this by developing a weighted IDLP framework. In contrast to existing weighted-space formulations designed for unbounded costs [HLL12], we introduce an $l_1$-norm weighting for the

purpose of restoring the contractivity lost in our polynomial reformulation.

To solve the weighted IDLP, we employ a two-level approximation scheme. First, we truncate the infinite constraint set of the weighted IDLP to $N$ polynomial test functions, yielding a semi-infinite linear program (SILP). This SILP is then approximately solved via a degree-$\ell$ Moment-SoS relaxation of its corresponding generalized moment problem (GMP). The dual solutions yield polynomial value function approximations, from which approximate costs and feedback policies are derived. We validate this procedure on the classical two-armed bandit problem [DY79, p. 209] and tiger problem [KLC98].

## II. PRELIMINARIES

We adopt the belief-state MDP formulation of POMDPs from [Kri16]. The system has a finite hidden state space $X = \{0, 1, \dots, n\}$, a compact control space $U$, and a finite observation space $S$. The belief state $b \in \Delta_n$, the $n$-dimensional simplex, evolves under the Bayesian filter:

$$ 
\begin{aligned}
b(t+1) &= F(b(t), u(t), s(t+1)) \\
&= \frac{B_{s(t+1)}(u(t))[P(u(t))]^T b(t)}{1^T B_{s(t+1)}(u(t))[P(u(t))]^T b(t)},
\end{aligned} 
\quad (1) $$

where:

* $B_s(u) = \text{diag}(B_{0s}(u), \dots, B_{ns}(u))$, with $B_{is}(u) = P(s | x = i, u)$.

* The numerator $B_s(u)[P(u)]^T b$ gives the unnormalized posterior belief, whose $i$-th component is

$$ 
\begin{aligned}
(B_s(u)[P(u)]^T b)_i \\
&= P(s | x_{t+1} = i, u) \sum_{j=0}^{n} P(x_{t+1} = i | x_t = j, u) b_j.
\end{aligned} 
$$

* The denominator $1^T B_s(u)[P(u)]^T b$ normalizes to ensure $b(t+1) \in \Delta_n$.

* Controls $u(t)$, $t = 0, 1, \dots$, are defined by a sequence of functions $\pi \stackrel{\text{def}}{=} \{\pi_t(b), t = 0, 1, \dots\}$ that are Borel-measurable selections of a set-valued map $U(\cdot) : \Delta_n \rightsquigarrow U$, such that

$$ u(t) = \pi_t(b(t)) \in U(b(t)), \quad t = 0, 1, \dots, \quad (2) $$

where $U(\cdot)$ is upper semicontinuous and each $U(b)$ is nonempty and compact for $b \in \Delta_n$.

Let II denote the set of all sequences of measurable selections of $U(\cdot)$:

$$ \Pi \stackrel{\text{def}}{=} \{ \pi = \{\pi_t(\cdot), t = 0, 1, \dots\} \mid \pi_t(b) \in U(b), \forall b \in \Delta_n, $$

<footnote n="1">¹K. Avrachenkov is with Team NEO, INRIA Sophia Antipolis, 2004 Route des Lucioles, 06902 Valbonne, France. k.avrachenkov@inria.fr</footnote>

<footnote n="2">²L. Gamersfelder and B. Mourrain are with Team AROMATH, INRIA Sophia Antipolis, 2004 Route des Lucioles, 06902 Valbonne, France, lucas.gamersfelder@inria.fr, bernard.mourrain@inria.fr. L. Gamersfelder is the corresponding author.</footnote>
$\pi_t(\cdot)$ Borel measurable}.

The objective is to minimize the expected discounted cost

$$h_{\epsilon}(b_0) = \min_{\pi \in \Pi} E \left[ \sum_{t=0}^{\infty} \epsilon(1-\epsilon)^t c(b(t), u(t)) \right]$$

where $c(b, u) = \bar{c}_u^T b$, with $\bar{c}_u$ the vector of real-valued costs associated with each hidden state. The optimal value function $V_\epsilon(b)$ is the unique fixed point of the Bellman operator $\mathcal{T}(\cdot)$:

$$\mathcal{T}(q(b)) = \min_{u \in \mathcal{U}(b)} \{c(b, u) + (1-\epsilon) \sum_{s \in S} P(s|b, u)q(F(b, u, s))\} \quad (3)$$

where $P(s|b, u) = \mathbf{1}^T B_s(u)[P(u)]^T b$.

**Proposition 2.1:** Assume an optimal control plan $\pi^*$ exists for the $\epsilon$-discounted cost problem. The fixed point $V_\epsilon(b)$ of (3) satisfies

$$\epsilon V_{\epsilon}(b) = h_{\epsilon}(b). \quad (4)$$

The normalization in the belief update makes $F(b, u, s)$ a rational function, so the belief dynamics cannot be represented as a polynomial system, preventing a direct application of Moment-SoS based methods

To obtain a polynomial system, we consider the dynamics on the unnormalized belief state $y \in Y \subset \mathbb{R}_+^{n+1}$:

$$\begin{aligned} y(t+1) &= f(y(t), u(t), s(t+1)) \\ &= B_{s(t+1)}(u(t))[P(u(t))]^T y(t). \end{aligned} \quad (5)$$

We set $Y = [0, 1]^{n+1}$, noting that monotonicity of $B_s(u)[P(u)]^T$ with stochastic $P(u)$ implies $y(t) \in Y$ for all $t$.

For each $y \in Y$, controls are selected according to the normalized belief $b = y/\|y\|_1$:

$$u(t) \in \tilde{U}(y(t)) \quad \text{with} \quad \tilde{U}(y) \stackrel{\text{def}}{=} U\left(\frac{y}{\|y\|_1}\right), \quad \tilde{U}(0) \stackrel{\text{def}}{=} U.$$

Hence, policies in $\Pi$ act on the normalized projection of $y(t)$, and the optimization remains over the same set $\Pi$.

Let the set of feasible state-control pairs be the graph of the induced correspondence:

$$G \stackrel{\text{def}}{=} \{(y, u) : y \in Y, u \in \tilde{U}(y)\},$$

which is a compact subset of $Y \times U$.

For any control plan $\pi \in \Pi$ and any initial condition $y(0) = y_0 \in Y$, let $(y^{\pi, y_0}(\cdot), u^{\pi, y_0}(\cdot))$ stand for the state-control trajectory obtained in accordance with (5) and (2).

We define the Bellman operator $\tilde{\mathcal{T}}(\cdot)$ acting on functions $q: Y \to \mathbb{R}$ by

$$\tilde{\mathcal{T}}(q)(y) = \min_{u \in \tilde{U}(y)} \left\{ c(y, u) + (1-\epsilon) \sum_{s \in S} q(f(y, u, s)) \right\}. \quad (6)$$

where $c(y, u) = \bar{c}_u^T y$. While $\tilde{\mathcal{T}}$ is not a contraction in the standard sup-norm when $(1 - \epsilon)|S| \ge 1$, we will show that it becomes a contraction under a suitably chosen weighted norm (see Lemma 3.2).

Denote by $V_\epsilon(b)$ and $\tilde{V}_\epsilon(y)$ the optimal value functions of the normalized problem (3) and the unnormalized problem (5), respectively. They are directly related as follows:

**Lemma 2.1:** For any unnormalized belief $y \in Y$ and its corresponding normalized belief $b = y/\|y\|_1$,

$$\tilde{V}_{\epsilon}(y) = \|y\|_{1} V_{\epsilon}(b). \quad (7)$$

Moreover, the corresponding optimal feedback policies coincide.

*Proof:* Let $\tilde{V}_0(y) = 0$ and $V_0(b) = 0$. The relationship holds for the base case: $\tilde{V}_1(y) = \min_u c(y, u) = \|y\|_1 \min_u c(b, u) = \|y\|_1 V_1(b)$. Assume $\tilde{V}_n(y) = \|y\|_1 V_n(b)$ for some $n \ge 1$. Then,

$$\begin{aligned} \tilde{V}_{n+1}(y) &= \min_{u \in \tilde{U}(y)} \{c(y, u) + (1 - \epsilon) \sum_{s \in S} \tilde{V}_n(f(y, u, s))\} \\ &= \min_{u \in \tilde{U}(y)} \{\|y\|_1 c(b, u) + (1 - \epsilon) \sum_{s \in S} \|f(y, u, s)\|_1 V_n(F(b, u, s))\} \\ &= \min_{u \in \tilde{U}(y)} \{\|y\|_1 c(b, u) + (1 - \epsilon) \sum_{s \in S} \|y\|_1 P(s|b, u) V_n(F(b, u, s))\} \\ &= \|y\|_1 \min_{u \in \tilde{U}(b)} \{c(b, u) + (1 - \epsilon) \sum_{s \in S} P(s|b, u) V_n(F(b, u, s))\} \\ &= \|y\|_1 V_{n+1}(b). \end{aligned}$$

The relation holds by induction. Taking the limit as $n \to \infty$, the unique fixed points satisfy $\tilde{V}_\epsilon(y) = \|y\|_1 V_\epsilon(b)$. Since $\|y\|_1$ is positive and independent of $u$, the minimizers coincide at each step. Thus, the optimal policies coincide. ■

### III. IDLP FORMULATION

In the fashion of [HLL12], [Put90], [Kri16], consider the linear program derived from the unnormalized Bellman equation (6):

$$\begin{array}{ll} \mathbf{P}^* = & \sup_{\varphi \in C(Y)} \epsilon \varphi(y_0) \\ \text{s.t.} & c(y, u) + (1-\epsilon) \sum_{s \in S} \varphi(f(y, u, s)) - \varphi(y) \ge 0, \forall (y, u) \in G \end{array}$$

with dual program

$$\mathbf{D}^* = \inf_{\gamma \in \mathcal{M}_+(G)} \int_G c(y, u)\gamma(dy, du)$$

where

$$\begin{aligned} \mathcal{W}(\epsilon, y_0) = & \{\gamma \in \mathcal{M}_+(G) \mid \\ & \int_G \varphi(y) - (1-\epsilon) \sum_{s \in S} \varphi(f(y, u, s))\gamma(dy, du) = \\ & \epsilon\varphi(y_0) \quad \forall \varphi \in C(Y) \}, \end{aligned} \quad (8)$$

with $\mathcal{M}_+(G)$ the cone of finite nonnegative Borel measures on $G$. The set $\mathcal{W}(\epsilon, y_0)$ admits a nontrivial element $\gamma \in \mathcal{M}_+(G)$ only if the discount factor satisfies $(1 - \epsilon) < 1/|S|$, where $|S|$ is the cardinality of the observation space $S$. Indeed, taking the test function $\varphi(y) = 1$, we have

$$\gamma(G) - (1 - \epsilon)|S|\gamma(G) = \epsilon,$$

implying $\gamma(G) = \epsilon/(1 - (1 - \epsilon)|S|)$, which is positive iff $(1 - \epsilon)|S| < 1$.

This restriction in the standard unweighted formulation motivates the introduction of an $\ell_1$-weighted framework, developed presently.
Define the weight function $w: Y \to \mathbb{R}_+$ by

$$w(y) \stackrel{\text{def}}{=} \|y\|_1,$$

which satisfies a Lyapunov-like condition for the unnormalized POMDP dynamics.

**Proposition 3.1:** For the unnormalized belief dynamics $f(y, u, s)$ defined in (5) and weight $w(y) = \|y\|_1$, the following equality holds for all $(y, u) \in G$:

$$\sum_{s \in S} w(f(y, u, s)) = w(y). \quad (9)$$

*Proof:* The probability of a specific observation $s$ given a belief $b$ is

$$P(s|b, u) = \mathbf{1}^T B_s(u) [P(u)]^T b = \|B_s(u)[P(u)]^T b\|_1.$$

Hence,

$$\begin{aligned} \sum_{s \in S} w(f(y, u, s)) &= \sum_{s \in S} \|B_s(u)[P(u)]^T y\|_1 \\ &= \|y\|_1 \sum_{s \in S} \|B_s(u)[P(u)]^T b\|_1 \\ &= \|y\|_1 \sum_{s \in S} P(s|b, u) = \|y\|_1 = w(y). \end{aligned}$$

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

This property of the unnormalized POMDP dynamics enables the Bellman equation (3) to be reformulated as an infinite-dimensional linear program in a weighted function space.

Let $w(y) \stackrel{\text{def}}{=} \|y\|_1$ and define the weighted semi-norm $\|\cdot\|_{w,Y}$:

$$\|q\|_{w,Y} = \sup_{y \in Y, w(y) \neq 0} |q(y)|/w(y).$$

Define also the weighted lower semi-continuous functions $LS_w(Y)$ on $Y$ by

$$LS_w(Y) = \{q \in LS(Y) \mid \|q\|_{w,Y} < \infty\},$$

where $LS(Y)$ denotes the set of bounded lower semi-continuous functions. The condition that $q(y) = 0$ when $w(y) = 0$ ensures that $\|\cdot\|_{w,Y}$ is a norm on $LS_w(Y)$, not merely a semi-norm. Thus $(LS_w(Y), \|\cdot\|_{w,Y})$ is a metric space under the distance $d(q_1, q_2) \stackrel{\text{def}}{=} \|q_1 - q_2\|_{w,Y}$.

**Lemma 3.1:** The metric space $(LS_w(Y), \|\cdot\|_{w,Y})$ is complete.

The loss of contractivity caused by unnormalization is restored through this weighted space, as shown below.

**Lemma 3.2:** The operator $\tilde{T}$ satisfies the following properties:

(i) $\tilde{T}$ maps $LS_w(Y)$ into itself.

(ii) $\tilde{T}$ is a contraction on the complete metric space $(LS_w(Y), \|\cdot\|_{w,Y})$.

(iii) $\tilde{T}$ admits a unique fixed point $\tilde{V}_\epsilon(\cdot) \in LS_w(Y)$.

(iv) The fixed point satisfies

$$\epsilon \tilde{V}_\epsilon(y_0) = \|y_0\|_1 h_\epsilon(b_0), \quad (10)$$

where $b_0 = y_0/\|y_0\|_1$.

*Proof:* (i) Follows from (9) and the upper semicontinuity of the compact-valued map $U(\cdot)$ by Berge's Maximum Theorem. (ii) Proof follows similar steps to [Kri16, Thm.

7.6.2]. (iii) Follows from (i), (ii), and the Contraction Mapping Theorem [Lue97, Sec. 10]. (iv) Follows from (4) and (7). ■

Having confirmed the Bellman operator is well-behaved in $LS_w(Y)$, we now construct the functional spaces that underpin the weighted IDLP formulation. For any continuous function $q: G \to \mathbb{R}$, define the weighted norm

$$\|q\|_w \stackrel{\text{def}}{=} \sup_{(y,u) \in G, w(y) \neq 0} \frac{|q(y, u)|}{w(y)}.$$

Let $C_w(Y)$ (resp. $C_w(G)$) be the space of continuous functions on $Y$ (resp. on $G$) with finite $\|\cdot\|_{w,Y}$ (resp. $\|\cdot\|_w$) norm.

The dual space to $C_w(G)$, denoted $C_w(G)^*$, is the set of all bounded linear functionals $\lambda: C_w(G) \to \mathbb{R}$. It is a normed vector space equipped with the standard operator norm induced by $\|\cdot\|_w$:

$$\|\lambda\|_w \stackrel{\text{def}}{=} \sup_{q \in C_w(G), \|q\|_w \le 1} |\langle \lambda, q \rangle|, \quad (11)$$

where $\langle \lambda, q \rangle$ denotes the action of the functional $\lambda$ on the function $q$.

**Proposition 3.2:** The space $(C_w(G), \|\cdot\|_w)$ is a Banach space. Consequently, its dual space $(C_w(G)^*, \|\cdot\|_w)$ is also a Banach space.

We equip $C_w(G)^*$ with its weak* topology: a sequence of functionals $\{\lambda_n\}$ converges to $\lambda$ in the weak* topology if and only if it converges pointwise on the pre-dual space $C_w(G)$:

$$\lim_{n \to \infty} \langle \lambda_n, q \rangle = \langle \lambda, q \rangle \quad \text{for all } q \in C_w(G).$$

Let $C_{w,+}(G)^*$ denote the cone of positive linear functionals in $C_w(G)^*$, that is,

$$C_{w,+}(G)^* \stackrel{\text{def}}{=} \{\lambda \in C_w(G)^* \mid \langle \lambda, q \rangle \ge 0 \text{ for all } q \in C_w(G), q \ge 0\}.$$

**Lemma 3.3:** Let $\lambda \in C_{w,+}(G)^*$ be a positive linear functional. Then its operator norm, defined in (11), satisfies

$$\|\lambda\|_w = \langle \lambda, w \rangle.$$

*Proof:* For any $q \in C_w(G)$ with $\|q\|_w \le 1$, we have $|q(y, u)| \le w(y)$, which implies $-w(y) \le q(y, u) \le w(y)$. By positivity of $\lambda$, this gives $-\langle \lambda, w \rangle \le \langle \lambda, q \rangle \le \langle \lambda, w \rangle$, so $|\langle \lambda, q \rangle| \le \langle \lambda, w \rangle$. Taking the supremum over all such $q$ yields $\|\lambda\|_w \le \langle \lambda, w \rangle$. For the other direction, note that $w \in C_w(G)$ and $\|w\|_w = 1$. Thus, $\|\lambda\|_w \ge |\langle \lambda, w \rangle| = \langle \lambda, w \rangle$. ■
Given a control plan $\pi \in \Pi$ and an initial condition $y_0 \in Y$, we define the corresponding occupational functional, $\lambda^{\pi,y_0,\epsilon} \in (C_w(G))^*$ by its action on any test function $q \in C_w(G)$:

$$\langle \lambda^{\pi,y_0,\epsilon}, q \rangle \stackrel{\text{def}}{=} \epsilon \sum_{t=0}^{\infty} (1-\epsilon)^t \sum_{s(0), \dots, s(t-1) \in S} q(y(t), u(t)). \quad (12)$$

where the inner sum runs over all length $t$ observation sequences. Let $\Lambda_\epsilon(y_0) \stackrel{\text{def}}{=} \bigcup_{\pi \in \Pi} \{\lambda^{\pi,y_0,\epsilon}\}$ be the set of all such functionals. By Lemma 2.1 and 3.2, $\forall y_0 \in Y$ and $b_0 = y_0/\|y_0\|_1$,

$$\|y_0\|_1 h_\epsilon(b_0) = \min_{\lambda \in \Lambda_\epsilon(y_0)} \langle \lambda, c \rangle. \quad (13)$$
The following lemma confirms that the occupational functions are bounded linear functionals.

**Lemma 3.4:** The set of occupational functionals $\Lambda_{\epsilon}(y_0)$ is contained in $(C_w(G))^*$.

*Proof:* Let $\lambda \in \Lambda_{\epsilon}(y_0)$ be an arbitrary occupational functional. It is readily seen to be linear and non-negative by definition.

Since $\lambda$ is a positive linear functional, by Lemma 3.3, its operator norm is given by $\|\lambda\|_w = \langle\lambda, w\rangle$. By (12),

$$ \|\lambda\|_w = \langle\lambda, w\rangle = \epsilon \sum_{t=0}^{\infty} (1-\epsilon)^t \sum_{s(0), \dots, s(t-1) \in S} w(y^{\pi,y_0}(t)). \quad (14) $$

From the fact $y^{\pi,y_0}(t+1) = f(y^{\pi,y_0}(t), u^{\pi,y_0}(t), s(t))$, and by repeated application of (9), we attain

$$ \sum_{s(0), \dots, s(t-1) \in S} w(y(t)) = w(y_0) \quad \forall t \ge 0. \quad (15) $$

Combining (14) and (15), we have

$$ \|\lambda\|_w = \epsilon \sum_{t=0}^{\infty} (1-\epsilon)^t w(y_0) = w(y_0). \quad (16) $$

Since $w(y_0)$ is finite, the operator norm is finite, confirming that $\lambda \in (C_w(G))^*$.

We now introduce the weighted infinite-dimensional linear program (IDLP):

$$ c^*(\epsilon, y_0) = \inf_{\lambda \in W(\epsilon, y_0)} \langle \lambda, c \rangle, \quad (17) $$

where the feasible set is

$$ W(\epsilon, y_0) = \{ \lambda \in C_{w,+}(G)^* \mid \langle \lambda, \mathcal{L}\varphi \rangle = \epsilon\varphi(y_0), \forall \varphi \in C_w(Y) \}, \quad (18) $$

and the linear operator $\mathcal{L}: C_w(Y) \to C_w(G)$ is defined by

$$ (\mathcal{L}\varphi)(y, u) \stackrel{\text{def}}{=} \varphi(y) - (1-\epsilon) \sum_{s \in S} \varphi(f(y, u, s)). $$

By Theorem 3.1, the set $W(\epsilon, y_0)$ is nonempty since $\tilde{U}(y)$ is nonempty for all $y \in Y$. Moreover, it is also straightforward to verify that $W(\epsilon, y_0)$ is convex and weak* compact in $C_w(G)^*$.

Unlike the unweighted feasibility set (8), the feasible set of (17) is not necessarily empty even when $(1-\epsilon) \ge 1/|S|$, since $1 \notin C_w(Y)$. Taking $\phi(y) = w(y)$ as a test function in (17) and using (9) yields

$$ \langle \lambda, w(y) - (1-\epsilon) \sum_{s \in S} w(f(y, u, s)) \rangle = \langle \lambda, \epsilon w(y) \rangle = \epsilon w(y_0). $$

Hence, by Lemma 3.3, any $\lambda \in C_{w,+}(G)^*$ satisfies

$$ \|\lambda\|_w = \langle\lambda, w\rangle = w(y_0), $$

providing a uniform bound on the weighted norm of feasible functionals.

The corresponding dual program to (17) is

$$ \begin{array}{ll} \mu^*(\epsilon, y_0) = \sup_{\psi \in C_w(Y)} & \epsilon\psi(y_0) \\ \text{s.t.} \quad c(y, u) - (\mathcal{L}\psi)(y, u) \ge 0, \quad \forall (y, u) \in G. & (19) \end{array} $$

A related weighted primal-dual pair was considered in [HLL12], where weighting was introduced to accommodate functions unbounded in the sup-norm. In contrast, our framework employs weighting to counteract the expansive effect of the operator $\mathcal{L}$.

**Proposition 3.3:** The following strong duality relation holds:

$$ c^*(\epsilon, y_0) = \mu^*(\epsilon, y_0) \quad \forall \epsilon \in (0, 1). \quad (20) $$

*Proof:* Proceeds in the same fashion as [AGG22, Prop. 3.1]. The proof is given in Appendix I.

**Theorem 3.1:** The following properties hold

(i) The following sets are equal

$$ \bar{c} \circ \Lambda_{\epsilon}(y_0) = W(\epsilon, y_0) \quad \forall \epsilon \in (0, 1), \quad (21) $$

where $\bar{c} \circ$ stands for the closed convex hull in the weak* topology.

(ii) For any $y_0 \in Y$ and $b_0 = y_0/\|y_0\|_1$

$$ \|y_0\|_1 h_{\epsilon}(b_0) = c^*(\epsilon, y_0) \quad \forall \epsilon \in (0, 1), \quad (22) $$

(iii) The function $\tilde{V}_{\epsilon}(y_0)$ attains the supremum in (19).

*Proof:* The proofs are given in Appendix II.

The following theorem shows that the solution $\psi^* \in C_w(Y)$ to the dual problem $\mu^*(\epsilon, y_0)$ serves the same role as the value function in the dynamic programming formulation.

**Theorem 3.2:** Let $\psi^* \in C_w(Y)$ be an optimal solution to the dual problem (19). A control plan $\pi \in \Pi$ is optimal if and only if the corresponding state-control trajectory $(y^{\pi,y_0}(t), u^{\pi,y_0}(t))$ generated from the initial state $y_0$ satisfies the Bellman equality for all $t = 0, 1, \dots$:

$$ \begin{aligned} \psi^*(y^{\pi,y_0}(t)) = c(y^{\pi,y_0}(t), u^{\pi,y_0}(t)) \\ + (1-\epsilon) \sum_{s \in S} \psi^*(f(y^{\pi,y_0}(t), u^{\pi,y_0}(t), s)). \end{aligned} \quad (23) $$

Equivalently, the action $u^{\pi,y_0}(t)$ minimizes the right-hand side at the state $y^{\pi,y_0}(t)$:

$$ u^{\pi,y_0}(t) \in \underset{u \in U(y^{\pi,y_0}(t))}{\operatorname{argmin}} \left\{ c(y^{\pi,y_0}(t), u) + (1-\epsilon) \sum_{s \in S} \psi^*(f(y^{\pi,y_0}(t), u, s)) \right\}. \quad (24) $$

*Proof:* The proof is given in Appendix III.

## IV. SILP RELAXATION

To connect our IDLP framework to polynomial tools, we first establish that the feasible set $W(\epsilon, y_0)$ can be fully characterized by weighted polynomial test functions:

$$ \begin{aligned} & w * P(Y) \\ & \stackrel{\text{def}}{=} \{ q \in C(Y) \mid \exists p \in P(Y), \quad q(y) = w(y)p(y), \quad \forall y \in Y \}. \end{aligned} $$

Define

$$ W_P(\epsilon, y_0) \stackrel{\text{def}}{=} \{ \lambda \in C_w(G)^* \mid \langle \lambda, \mathcal{L}\varphi \rangle = \epsilon\varphi(y_0), \quad \forall \varphi \in w * P(Y) \}. $$

**Lemma 4.1:** The equality

$$ W(\epsilon, y_0) = W_P(\epsilon, y_0) $$
holds.

*Proof:* The inclusion

$$W(\epsilon, y_0) \subseteq W_P(\epsilon, y_0)$$

holds trivially. To prove the converse, let $\lambda \in W_P(\epsilon, y_0)$. By definition,

$$\langle \varphi(y) - (1 - \epsilon) \sum_{s \in S} \varphi(f(y, u, s)), \lambda \rangle = \epsilon \varphi(y_0) \quad (25)$$

holds for all weighted polynomials $\varphi(y) = p(y)w(y)$ with $p \in P(Y)$. Define the two linear functionals on $C(Y)$:

$$L_1(h) \stackrel{\text{def}}{=} \langle \lambda, h(y)w(y) \rangle - \epsilon h(y_0)w(y_0),$$

$$L_2(h) \stackrel{\text{def}}{=} \langle \lambda, (1 - \epsilon) \sum_{s \in S} h(f(y, u, s))w(f(y, u, s)) \rangle.$$

These linear functionals are bounded, and therefore continuous, since for any $h \in C(Y)$,

$$\|h(y)w(y)\|_w = \|h\|_{\infty}$$

and

$$| \sum_{s \in S} h(f)w(f) |_{w} \leq |h|_{\infty},$$

by Equation (9). By (25), the continuous functionals $L_1$ and $L_2$ agree on the space of polynomials $P(Y)$. By the Stone-Weierstrass theorem, we have further that

$$L_1(h) = L_2(h) \quad \text{for all } h \in C(Y).$$

By the Riesz-Markov-Kakutani theorem, $L_1$ and $L_2$ are represented by unique finite signed Borel measures, $\nu_1$ and $\nu_2$, on $Y$. As $L_1(h) = L_2(h)$ for all $h \in C(Y)$, uniqueness implies

$$\nu_1 = \nu_2.$$

Consequently, the corresponding integrals agree for all bounded Borel measurable functions $h: Y \to \mathbb{R}$.

Now, for an arbitrary $\psi \in C_w(Y)$, define the bounded function

$$h_{\psi}(y) \stackrel{\text{def}}{=} \begin{cases} \psi(y)/w(y) & \text{if } w(y) \neq 0, \\ 0 & \text{if } w(y) = 0. \end{cases}$$

This function is measurable as it is continuous on the open set $\{y | w(y) \neq 0\}$ and its closed complement. Note, by definition of $C_w(Y)$,

$$h_{\psi}(y)w(y) = \psi(y) \quad \forall y \in Y.$$

The equality $L_1(h_\psi) = L_2(h_\psi)$ is therefore equivalent to

$$\langle \lambda, h_{\psi}(y)w(y) \rangle - \epsilon h_{\psi}(y_0)w(y_0) \\ = \langle \lambda, (1 - \epsilon) \sum_{s \in S} h_{\psi}(f(y, u, s))w(f(y, u, s)) \rangle.$$

Since $h_\psi(y)w(y) = \psi(y)$, this simplifies to the constraint equation for $\psi$. As $\psi \in C_w(Y)$ was arbitrary, we conclude that $\lambda \in W(\epsilon, y_0)$.

Choose a countable basis of weighted polynomials

$$\{\varphi_i(y)\}_{i=1}^{\infty} \quad \text{with} \quad \varphi_i(y) \stackrel{\text{def}}{=} w(y)p_i(y). \quad (26)$$

and noting that each $\varphi_i \in C_w(Y)$, we define an $N$-th order finite-dimensional relaxation to the primal IDLP (17). Let

$$c_N^*(\epsilon, y_0) \stackrel{\text{def}}{=} \min_{\lambda \in W_N(\epsilon, y_0)} \langle \lambda, c \rangle \quad (27)$$

where

$$\begin{align}
W_N(\epsilon, y_0) &\stackrel{\text{def}}{=} \left\{ \lambda \in C_{w,+}(G)^* \mid \right. \nonumber \\
&\qquad \langle \lambda, \varphi_i(y) - (1-\epsilon) \sum_{s \in S} \varphi_i(f(y, u, s)) \rangle = \epsilon \varphi_i(y_0), \tag{28} \\
&\qquad \left. \forall i = 1, \dots, N \right\}. \nonumber
\end{align}$$

*Proposition 4.1:* The following relations hold:

(i) $\lim_{N \to \infty} \rho_H(W_N(\epsilon, y_0), W(\epsilon, y_0)) = 0$

(ii) $\lim_{N \to \infty} c_N^*(\epsilon, y_0) = \|y_0\|_1 h_\epsilon(b_0)$

(iii) If the optimal solution $\lambda^*$ of problem (17) is unique, then $\lim_{N \to \infty} \lambda^N = \lambda^*$, where $\lambda^N$ is any optimal solution of (27),

where $b_0 = y_0/\|y_0\|_1$ and $\rho_H$ denotes the Hausdorff distance in the weak* topology.

*Proof:* (i) Since $W(\epsilon, y_0) \subset W_N(\epsilon, y_0)$, it suffices to show that

$$\lim_{N \to \infty} \sup_{\lambda \in W_N(\epsilon, y_0)} \rho(\gamma, W(\epsilon, y_0)) = 0.$$

Assume this is not true. Then, there exists a sequence $\{\lambda_{N_k}\} \in W_{N_k}(\epsilon, y_0)$ and a number $\delta > 0$ such that $\rho(\lambda_{N_k}, W) \ge \delta$ for all $N_k$. As $W_{N_k}(\epsilon, y_0) \subseteq B(G) \stackrel{\text{def}}{=} \{\lambda \in C_w(G)^* \mid \langle \lambda, w \rangle \le w(y_0)\}$ for all $k$, we have from the weak* compactness of $B(G)$ that there exists $\bar{\lambda} \in B(G)$ and a subsequence (which we still denote with $\{\lambda_{N_k}\}$) such that

$$\lim_{k \to \infty} \lambda_{N_k} = \bar{\lambda},$$

therefore

$$\rho(\bar{\gamma}, W(\epsilon, y_0)) \geq \delta. \quad (29)$$

On the other hand, since $\gamma_{N_k} \in W_{N_k}(\epsilon, y_0)$, we have

$$\langle \lambda_{N_k}, \varphi_i(y) - (1 - \epsilon) \sum_{s \in S} \varphi_i(f(y, u, s)) \rangle = \epsilon \varphi_i(y_0)$$

for all $i = 1, \dots, N_k$. Hence, by weak* convergence,

$$\langle \bar{\lambda}, \varphi_i(y) - (1 - \epsilon) \sum_{s \in S} \varphi_i(f(y, u, s)) \rangle = \epsilon \varphi_i(y_0)$$

for all $i = 1, \dots, N_k$, and all $N_k$. That is,

$$\langle \bar{\lambda}, \varphi_i(y) - (1 - \epsilon) \sum_{s \in S} \varphi_i(f(y, u, s)) \rangle = \epsilon \varphi_i(y_0) \quad \forall i = 1, \dots$$

That is, $\bar{\gamma} \in W(\epsilon, y_0)$ (see Lemma 4.1). This contradicts (29) and completes the proof of statement (i). Note (i) implies $\lim_{N \to \infty} c_N^*(\epsilon, y_0) = c^*(\epsilon, y_0)$ which, due to (22), proves the validity of statement (ii). The validity of (iii) follows from the fact that, due to (i), any partial limit of an optimal solution $\gamma^N$ of (27) belongs to $W(\epsilon, y_0)$ and by (ii) is an optimal solution of (17).
Motivated by Theorem 3.2, define the control $u^N$ by the equation

$$u^N(y) \stackrel{\text{def}}{=} \underset{u \in U(y)}{\operatorname{argmin}} \{c(y, u) + (1-\epsilon) \sum_{s \in S} \psi^N(f(y, u, s))\} \quad (30)$$

To ensure that the argmin operators in the policy definition are well-behaved, and that the resulting approximate trajectories converge, we require the following standard assumptions, adapted from [GPS17]:

**Assumption 4.1:** The following conditions hold:

(i) Where $R_{y0} \stackrel{\text{def}}{=} \{y \in Y \mid y = y^{\pi, y0}(t) \text{ for some } \pi \in \Pi, t \ge 0\}$, we have $\{y \in \text{int}(\text{cl}R_{y0}) \mid w(y) > 0\} \ne \emptyset$.

(ii) There exists an optimal control plan $\pi$ with corresponding trajectory $(y^{\pi, y0}(t), u^{\pi, y0}(t))$,

(iii) For any $t = 0, 1, \dots$, there exists an open ball $Q_t$ centered at $y^{\pi, y0}(t)$ such that the minimizer $u^N(y)$ in the right-hand side of (30) is uniquely defined for $y \in Q_t$,

(iv) $u^N(\cdot)$ is Lipschitz continuous on $Q_t$ with Lipschitz constant independent of $N$ and $t$,

(v) $y^N(t) \in Q_t$, for all $t = 0, 1, \dots$, for sufficiently large $N$.

(vi) $f(y, u, s)$ and $c(y, u)$ are Lipschitz continuous in $y$ and $u$.

(vii) The optimal solution $\lambda^*$ of problem (17) is unique and has support only where $w(y) \ne 0$.

**Theorem 4.1:** Let Assumption 4.1 hold. Then for any realization of the stochastic process $\{s(t)\}_{t=0}^{\infty}$, the following pathwise convergence holds:

$$\lim_{N \to \infty} u^N(y^N(t)) = u^{\pi, y_0}(t) \qquad (31) \\ \lim_{N \to \infty} y^N(t) = y^{\pi, y_0}(t).$$

where $(y^N(t), u^N(y^N(t)))$ is the trajectory generated by the control in (30).

**Proof:** The proof is contained in Appendix V.

The $N$-th order relaxation $c_N^*(\epsilon, y_0)$ is thus formulated as a generalized moment problem (GMP):

$$\mathbf{p}_d \stackrel{\text{def}}{=} \inf_{\lambda \in C_{w,+}(G)^*} \langle \lambda, c \rangle \\ \text{s.t.} \quad \langle \lambda, h_i \rangle = t_i, \quad i = 1, \dots, N \qquad (32)$$

where

$$h_i(y, u) \stackrel{\text{def}}{=} (\mathcal{L}\phi_i)(y, u) = \phi_i(y) - (1-\epsilon) \sum_{s \in S} \phi_i(f(y, u, s)), \\ t_i \stackrel{\text{def}}{=} \epsilon \phi_i(y_0).$$

Since all problem data are polynomial, the GMP is solvable via the Moment-SoS hierarchy of SDP relaxations. By Theorem 4.1, the trajectory $(y^N(\cdot), u^N(\cdot))$ derived from the dual solution $\psi_N$ through (30) approximates the unnormalized POMDP.

The time-discounted control problem $h_\epsilon(\cdot)$ is addressed through a two-level approximation scheme. First, truncating the infinite constraint set in (17) to $N$ polynomial test functions yields the SILP (27), whose value $c_N^*$ converges

to $h_\epsilon$ as $N \to \infty$ (Proposition 4.1). Second, for fixed $N$, the SILP is solved via Moment-SoS relaxations of increasing degree $\ell$, whose values provide certified lower bounds on $c_N^*$. The next section presents numerical results demonstrating the effectiveness of this two-level $(N, \ell)$ scheme.

## V. NUMERICAL EXAMPLES

We illustrate the proposed two-level approximation framework on two canonical POMDPs. All relaxations are implemented in Julia using the `MomentPolynomialOpt.jl` package and solved with the Mosek SDP solver on a standard desktop computer.

### A. The Two-Armed Bandit Problem

The state, action and observation spaces are given by

$$X = U = S = \{0, 1\}.$$

The hidden state $x = i$ indicates that arm $i$ has the higher success probability $p_0 > p_1$. The state is static:

$$P(u) = I.$$

An observation $s = 0$ indicates success. If we choose $u = x$, we observe $s = 0$ with probability $p_0$. Otherwise, we observe $s = 0$ with probability $p_1$. This is encoded in the observation probability $B_{js}(u) = P(s|x = j, u)$ for $j \in \{0, 1\}$:

$$B_{js}(u) = ((1-u)(1-j) + uj)[s + (1-2s)p_0] + (u(1-j) + (1-u)j)[s + (1-2s)p_1].$$

These polynomials form the diagonal of $B_s(u)$, making the dynamics function

$$f(y, u, s) = B_s(u)y$$

polynomial. The immediate cost represents the negative reward, and is also expressible as a polynomial in $u$:

$$c(y, u) = y_0(-up_1 - (1-u)p_0) + y_1(-up_0 - (1-u)p_1).$$

assigning a cost of $-p_0$ when the good arm is pulled and $-p_1$ otherwise. With this polynomial cost-dynamics pair, the control problem fits the GMP (32). We set $\epsilon = 0.1$, $p_0 = 0.75$, $p_1 = 0.25$, and solve the Moment-SoS relaxation of degree $\ell = 10$. The dual optimizer $\psi_N^*$ is obtained, and used to generate a control policy via (30). Figure 1 displays the simulation starting from an indifferent belief $b(0) = y(0) = [0.5, 0.5]^T$. The obtained heuristic policy correctly implements the optimal myopic strategy observed in [DY79].

### B. The Tiger Problem

The state space, control and observation space are given by

$$X = S = \{0, 1\}, \quad U = \{0, 1, 2\}.$$

The hidden state $x \in \{0, 1\}$ is the tiger's location, and the control $u \in \{0, 1, 2\}$ is to open door 0, 1, or listen. If a door is opened (i.e., $u \in \{0, 1\}$), the state resets according to a
<figure><img src="image_3.png" /><figcaption>Fig. 1. Two-armed bandit. Top: Belief $b_1 = y_1/\|y\|_1$ (prob. arm 1 is better). Bottom: Control $u$. The policy selects $u = 0$ when $y_1 \ge y_2$, and $u = 1$ when $y_2 > y_1$.</figcaption></figure>

The ($N = 2, \ell = 10$)-approximation provides $-0.2395$ for the value of the $N = 2$ SILP. A 20-step simulation using the extracted heuristic policy yielded a discounted cost of $-0.0937$.

<figure><img src="image_4.png" /><figcaption>Fig. 2. Tiger problem simulation with $\ell = 18$ and $N = 2$. Top: Belief $b_1 = y_1/\|y\|_1$ (prob. tiger at door 1). Red dashed lines indicate the optimal action thresholds computed via value iteration. Bottom: Corresponding control $u$. The policy listens until the belief exceeds the optimality thresholds. The ($N = 2, \ell = 18$)-approximation gives $-0.9760$ (true value $\approx -0.8507$). The extracted policy's simulated cost is $-0.6536$. The performance gap is expected from the finite ($N, \ell$)-approximation.</figcaption></figure>

uniform distribution. If listening (i.e., $u = 2$), the state is unchanged. This is encoded in the polynomial matrix:

$$P(u) = \begin{pmatrix} \frac{u^2-u+2}{4} & \frac{-u^2+u+2}{4} \\ \frac{-u^2+u+2}{4} & \frac{u^2-u+2}{4} \end{pmatrix}.$$

The observation probabilities $B_{js}(u)$ are defined to be uninformative for $u \in \{0, 1\}$, and reliable with probability $LR$ for $u = 2$. It is encoded by the following polynomial:

$$B_{js}(u) = \left( \frac{(1-2j)(LR - 0.5)(1-2s)}{2} \right) u(u-1) + 0.5.$$

These polynomials form the diagonal of matrix $B_s(u)$. The immediate cost

$$c(y, u) = y_0 c_0(u) + y_1 c_1(u)$$

is defined by a quadratic polynomial that yields a cost of 100 for finding the tiger, $-10$ for the prize, and $1$ for listening:

$$c_0(u) = \frac{121}{2}u^2 - \frac{341}{2}u + 100,$$

$$c_1(u) = -\frac{209}{2}u^2 + \frac{429}{2}u - 10.$$

With this polynomial cost-dynamics pair, the control problem fits the GMP (32). We analyze the ($N = 2, \ell = 18$)-approximation, again using $N = 2$ polynomial test functions. We set $\epsilon = 0.1$ and $LR = 0.85$. The dual optimizer $\psi_N^*$ is obtained, and used to generate a control policy via (30). Figure 2 displays the simulation starting from an indifferent belief $b(0) = y(0) = [0.5, 0.5]^T$. The obtained heuristic policy listens until the belief surpasses a certainty threshold, then opens the door perceived as safe.

## VI. CONCLUSION

This paper establishes a connection between the Moment-SOS optimization framework and partially observable Markov decision processes (POMDPs). While the rational belief update normally prevents polynomial optimization, reformulation over unnormalized beliefs yields polynomial dynamics. Introducing an $\ell_1$-norm Lyapunov weight restores contractivity and enables a well-posed weighted IDLP for the unnormalized POMDP. Numerical results on the bandit and tiger problems show that the method produces approximate feedback policies aligning with the structure of optimal strategies. Future work will relax the assumptions in Theorem 4.1, formalize convergence of the weighted Moment-SOS relaxation, and compare performance against established POMDP solvers.

## REFERENCES

[AGG22] Konstantin Avrachenkov, Vladimir Gaitsgory, and Lucas Gamertsfelder. Lp based upper and lower bounds for cesàro and abel limits of the optimal values in problems of control of stochastic discrete time systems. *Journal of Mathematical Analysis and Applications*, 512(1):126121, 2022.

[And83] Edward J Anderson. A review of duality theory for linear programming over topological vector spaces. *Journal of mathematical analysis and applications*, 97(2):380-392, 1983.

[Ash14] Robert B Ash. *Measure, integration, and functional analysis*. Academic Press, 2014.

[BB96] Abhay G Bhatt and Vivek S Borkar. Occupation measures for controlled markov processes: Characterization and optimality. *The Annals of Probability*, pages 1531-1562, 1996.

[BGQ11] Rainer Buckdahn, Dan Goreac, and Marc Quincampox. Stochastic optimal control and linear programming approach. *Applied Mathematics & Optimization*, 63(2):257-276, 2011.
[Bor88] Vivek S Borkar. A convex analytic approach to markov decision processes. *Probability Theory and Related Fields*, 78(4):583–602, 1988.

[Con19] John B Conway. *A course in functional analysis*, volume 96. Springer, 2019.

[DY79] Evgenïi Borisovich Dynkin and Alexander Adolph Yushkevich. *Controlled markov processes*, volume 235. Springer, 1979.

[FGL08] Luke Finlay, Vladimir Gaitsgory, and Ivan Lebedev. Duality in linear programming problems related to deterministic long run average problems of optimal control. *SIAM journal on control and optimization*, 47(4):1667–1700, 2008.

[GPS17] Vladimir Gaitsgory, Alex Parkinson, and Ilya Shvartsman. Linear programming formulations of deterministic infinite horizon optimal control problems in discrete time. *arXiv preprint arXiv:1702.00857*, 2017.

[GQ09] Vladimir Gaitsgory and Marc Quincampoix. Linear programming approach to deterministic infinite horizon optimal control problems with discounting. *SIAM Journal on Control and Optimization*, 48(4):2480–2512, 2009.

[GR06] Vladimir Gaitsgory and Sergey Rossomakhine. Linear programming approach to deterministic long run average problems of optimal control. *SIAM journal on control and optimization*, 44(6):2006–2037, 2006.

[GRT12] Vladimir Gaitsgory, Serguei Rossomakhine, and N Thatcher. Approximate solution of the HJB inequality related to the infinite horizon optimal control problem with discounting. *Dynamics of Continuous, Discrete and Impulsive Systems Series B: Applications and Algorithms*, 19(1-2):65–92, 2012.

[HKL20] Didier Henrion, Milan Korda, and Jean Bernard Lasserre. *Moment-sos Hierarchy, The: Lectures In Probability, Statistics, Computational Geometry, Control And Nonlinear Pdes*, volume 4. World Scientific, 2020.

[HLL02] Onésimo Hernández-Lerma and Jean B Lasserre. The linear programming approach. In *Handbook of Markov decision processes: methods and applications*, pages 377–407. Springer, 2002.

[HLL12] Onésimo Hernández-Lerma and Jean B Lasserre. *Discrete-time Markov control processes: basic optimality criteria*, volume 30. Springer Science & Business Media, 2012.

[HP14] Didier Henrion and Edouard Pauwels. Linear conic optimization for nonlinear optimal control. *arXiv preprint arXiv:1407.1650*, 2014.

[KHJ17] Milan Korda, Didier Henrion, and Colin N Jones. Convergence rates of moment-sum-of-squares hierarchies for optimal control problems. *Systems & Control Letters*, 100:1–5, 2017.

[KLC98] Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. *Artificial intelligence*, 101(1-2):99–134, 1998.

[Kri16] Vikram Krishnamurthy. *Partially observed Markov decision processes*. Cambridge university press, 2016.

[KS98] Thomas G Kurtz and Richard H Stockbridge. Existence of markov controls and characterization of optimal markov controls. *SIAM Journal on Control and Optimization*, 36(2):609–653, 1998.

[Lue97] David G Luenberger. *Optimization by vector space methods*. John Wiley & Sons, 1997.

[Put90] Martin L Puterman. Markov decision processes. *Handbooks in operations research and management science*, 2:331–434, 1990.

[PZ11] Alexey Piunovskiy and Yi Zhang. Discounted continuous-time markov decision processes with unbounded rates: the convex analytic approach. *SIAM journal on control and optimization*, 49(5):2032–2061, 2011.

# APPENDIX I
## PROOF OF PROPOSITION 3.3.

In this section, we prove strong duality for the weighted IDLP by verifying the conditions of the general infinite-dimensional LP duality theorem.

Let $C_w(Y)^*$ stand for the space of continuous linear functionals on the Banach space $C_w(Y)$. For any $\epsilon \in [0, 1)$, define a linear operator $A_\epsilon(\cdot) : C_w(G)^* \mapsto C_w(Y)^*$ as follows: for any $\lambda \in C_w(G)^*$,

$$A_\epsilon(\lambda)(\varphi) \stackrel{\text{def}}{=} \langle \lambda, \varphi(y) - (1-\epsilon) \sum_{s \in S} \varphi(f(y, u, s)) \rangle. \quad (33)$$

This operator is well-defined because, for any $\varphi \in C_w(Y)$, the integrand is an element of $C_w(G)$.

Let $b_{\epsilon,y_0} \in C_w(Y)^*$ be the functional defined by its action on any $\varphi \in C_w(Y)$ as:

$$b_{\epsilon,y_0}(\varphi) \stackrel{\text{def}}{=} \epsilon\varphi(y_0).$$

In these notations, the set $W(\epsilon, y_0)$ from (18) is

$$W(\epsilon, y_0) = \{ \lambda \in C_{w,+}(G)^* : A_\epsilon(\lambda) = b_{\epsilon,y_0} \},$$

where $C_{w,+}(G)^*$ is the cone of positive measures in $C_w(G)^*$. Problem (17) takes the form

$$\min_{\gamma \in W(\epsilon, y_0)} \langle \lambda, c \rangle = c^*(\epsilon, y_0). \quad (34)$$

Note $c(y, u) = \tilde{c}_u^T y \in C_w(G)$ by definition. The dual problem involves the adjoint operator $A_\epsilon^*(\cdot) : C_w(Y) \mapsto C_w(G)$. For any $\psi \in C_w(Y)$, the pairing $\langle A_\epsilon(\gamma), \psi \rangle = \langle \gamma, A_\epsilon^*(\psi) \rangle$ defines the adjoint as

$$A_\epsilon^*(\psi)(y, u) \stackrel{\text{def}}{=} \psi(y) - (1-\epsilon) \sum_{s \in S} \psi(f(y, u, s)). \quad (35)$$

The problem dual to (34) is of the form (see [And83])

$$\sup_{\psi \in C_w(Y)} \langle b_{\epsilon,y_0}, \psi \rangle = \sup_{\psi \in C_w(Y)} \epsilon \psi(y_0) = \mu^*(\epsilon, y_0) \quad (36)$$

subject to

$$A_\epsilon^*(\psi)(y, u) \le c(y, u) \quad \forall (y, u) \in G. \quad (37)$$

This constraint is equivalent to

$$c(y, u) + (1-\epsilon) \sum_{s \in S} \psi(f(y, u, s)) - \psi(y) \ge 0 \quad \forall (y, u) \in G,$$

which is precisely the dual problem (19) defined over the correct space $C_w(Y)$.

**Proof of Proposition 3.3.** Strong duality holds if the set

$$D_\epsilon \stackrel{\text{def}}{=} \{ (A_\epsilon(\gamma), \langle \gamma, c \rangle) : \gamma \in C_{w,+}(G)^* \} \subset C_w(Y)^* \times \mathbb{R}$$

is closed in the weak* topology of $C_w(Y)^* \times \mathbb{R}$ [And83, Thm. 3.10]. The proof of closure relies on two properties.

**Property A.** The cone $C_{w,+}(G)^*$ has a weak* compact base. Let $\mathcal{L}_w \stackrel{\text{def}}{=} \{ \lambda \in C_{w,+}(G)^* : \|\lambda\|_w = \langle \lambda, w \rangle = 1 \}$. By the Banach-Alaoglu theorem, the unit ball in $C_w(G)^*$ is weak* compact, and $\mathcal{L}_w$ is a weak* closed subset of it, making $\mathcal{L}_w$ compact. Any $\lambda \in C_{w,+}(G)^*$ can be written as $\lambda = \eta\bar{\lambda}$ for $\eta = \|\lambda\|_w \ge 0$ and $\bar{\lambda} \in \mathcal{L}_w$ (if $\lambda \ne 0$).

**Property B.** For any non-zero $\lambda \in C_{w,+}(G)^*$, $A_\epsilon(\lambda) \ne 0$. To see this, let $\lambda \in C_{w,+}(G)^*$ be non-zero and choose the test function $\varphi(y) = w(y) \in C_w(Y)$. Then

$$A_\epsilon(\lambda)(w) = \langle \lambda, w(y) - (1-\epsilon) \sum_{s \in S} w(f(y, u, s)) \rangle$$

Let $\phi(y, u) \stackrel{\text{def}}{=} w(y) - (1-\epsilon) \sum_{s \in S} w(f(y, u, s))$. By Equation (9), we have $\sum_{s \in S} w(f(y, u, s)) = w(y)$, which implies

$$\phi(y, u) = w(y) - (1-\epsilon)w(y) = \epsilon w(y).$$

By monotonicity of positive functionals, we get:

$$A_\epsilon(\lambda)(w) = \langle \lambda, \phi \rangle = \langle \lambda, \epsilon w \rangle = \epsilon \langle \lambda, w \rangle.$$
By Lemma 3.3, we have established the equality:

$$
\langle \mathcal{A}_{\epsilon}(\lambda), w \rangle = \epsilon \|\lambda\|_{w}.
$$

If $\lambda$ is a non-zero functional, then by the definition of a norm,
$\|\lambda\|_w > 0$. Since $\epsilon \in (0, 1)$, $\langle \mathcal{A}_\epsilon(\lambda), w \rangle > 0$. Thus $\mathcal{A}_\epsilon(\lambda)$
cannot be the zero functional.

Let us now prove that $D_\epsilon$ is closed. Let $\lambda_l \in C_{w,+}(G)^*$ be such that

$$
\mathcal{A}_{\epsilon}(\lambda_l) - \mathbf{z} \to \mathbf{0}, \quad \langle \lambda_l, c \rangle - \beta \to 0 \quad \text{as} \quad l \to \infty, \quad (38)
$$

where $\mathbf{z} \in C_w(Y)^*$ and $\beta \in \mathbb{R}$. By Property A, $\lambda_l = \eta_l \bar{\lambda}_l$,
where $\lambda_l \ge 0$ and $\bar{\lambda}_l \in \mathcal{L}$. Due to compactness of $\mathcal{L}$, one
may assume (without loss of generality) that $\bar{\lambda}_l \to \bar{\lambda} \in \mathcal{L}$.

Note that, due to Property B, the sequence $\eta_l$ is bounded.
Indeed, assuming that this is not the case and there exists
a subsequence $\{l'\}$ of $\{l\}$ such that $\eta_{l'} \to \infty$ as $l' \to \infty$,
one would obtain (via substitution of $\eta_{l'} \bar{\lambda}_{l'}$ into (38) and
passing to the limit with $l' \to \infty$) that

$$
\begin{align*}
\mathcal{A}_{\epsilon}(\bar{\lambda}_{l'}) - \frac{1}{\eta_{l'}} \mathbf{z} &\to \mathbf{0}, \quad \langle \bar{\lambda}_{l'}, c \rangle - \frac{1}{\eta_{l'}} \beta \to 0 \quad \text{as } l \to \infty. \\
\Rightarrow \quad &\mathcal{A}_{\epsilon}(\bar{\lambda}) = \mathbf{0}, \quad \langle \bar{\lambda}, c \rangle = 0.
\end{align*}
$$

According to Property B, the latter implies that $\bar{\lambda} = 0$. This
contradicts to the fact that $\bar{\lambda} \in \mathcal{L}$. Thus, the sequence $\{\eta_l\}$
is bounded and therefore one may assume (without loss of
generality) that $\eta_l \to \eta$ as $l \to \infty$. Consequently, $\lambda_l \to \eta\bar{\lambda}$
as $l \to \infty$, and, by (38),

$$
\mathcal{A}_{\epsilon}(\eta \bar{\lambda}) = \mathbf{z}, \quad \langle \eta \bar{\lambda}, c \rangle = \beta \quad \Rightarrow \quad (\mathbf{z}, \beta) \in D_{\epsilon}.
$$

This proves that $D_\epsilon$ is closed for any $\epsilon \in [0, 1)$. $\square$

Remark I.1: Note that the proof above is similar to the
proof of the absence of the duality gap in [PZ11].

APPENDIX II

PROOF OF THEOREM 3.1

We prove the three parts of Theorem 3.1 in sequence. To
do so, we require the following lemma concerning denseness
in of $LS_w(Y)$ in $C_w(Y)$.

Lemma II.1: For any function $\psi \in LS_w(Y)$, there exists a sequence of functions $\{\psi_n\}_{n=1}^{\infty} \subset C_w(Y)$ such that $\psi_n(y) \uparrow \psi(y)$ for all $y \in Y$.

Proof: Let $\psi \in LS_w(Y)$. Let $Z \stackrel{\text{def}}{=} \{y \in Y \mid w(y) \neq 0\}$. Since $w$ is a continuous function on the compact set $Y$, $Z$ is open. We define a function $g: Z \to \mathbb{R}$ by

$$
g(y) \stackrel{\text{def}}{=} \frac{\psi(y)}{w(y)} \quad \forall y \in Z.
$$

Note this function is bounded by definition of the weighted
norm: for any $y \in Z$, we have

$$
|g(y)| = |\psi(y)/w(y)| \le \|\psi\|_{w,Y} < \infty.
$$

Further, it is lower semi-continuous: let {$y_k$}$_{k=1}^{\infty}$ $\subset$ Z be
a sequence converging to $y_0$. By the continuity of w and
the lower semi-continuity of $\psi$, we have $\lim_{k \to \infty} w(y_k) =$
$w(y_0)$ and $\liminf_{k \to \infty} \psi(y_k) \ge \psi(y_0)$. It follows that

$$
\liminf_{k \to \infty} g(y_k) = \liminf_{k \to \infty} \frac{\psi(y_k)}{w(y_k)} = \frac{\liminf_{k \to \infty} \psi(y_k)}{\lim_{k \to \infty} w(y_k)}
$$

$$
\geq \frac{\psi(y_0)}{w(y_0)} = g(y_0).
$$

By a standard result (e.g., [Ash14, Theorem A6.6]), there ex-
ists an increasing sequence of bounded, continuous functions
{$g_n$}$_{n=1}^{\infty} \subset C_b(Z)$ such that $g_n(y) \uparrow g(y)$ for all $y \in Z$. Now
define

$$
\psi_n(y) \stackrel{\text{def}}{=} \begin{cases} g_n(y)w(y) & \text{if } y \in Z, \\ 0 & \text{if } y \notin Z. \end{cases}
$$

We verify that {$\psi_n$} has the required properties. Note the
sequence is increasing because for $y \in Z$,

$$
\psi_{n+1}(y) - \psi_n(y) = (g_{n+1}(y) - g_n(y))w(y) \ge 0 \quad \forall y \in Z
$$

and

$$
\psi_{n+1}(y) - \psi_n(y) = 0 \quad \forall y \notin Z
$$

Hence, $\psi_n \le \psi_{n+1}$ on $Y$. The sequence converges pointwise
to $\psi$ because

$$
\lim_{n \to \infty} \psi_n(y) = \lim_{n \to \infty} g_n(y)w(y) = g(y)w(y) = \psi(y), \quad \forall y \in Z
$$

and

$$
\lim_{n \to \infty} \psi_n(y) = 0 = \psi(y), \quad \forall y \notin Z,
$$

since $\psi \in LS_w(Y)$. Lastly, each $\psi_n$ is in $C_w(Y)$ since the
weighted norm is finite:

$$
\begin{align*}
\|\psi_n\|_{w,Y} &= \sup_{y \in Z} |\psi_n(y)/w(y)| = \sup_{y \in Z} |g_n(y)| \\
&= \|g_n\|_{\infty,Z} < \infty
\end{align*}
$$

The function $\psi_n$ is clearly continuous on $Z$. Since $w$ is
continuous, for any $y_0 \in Y \setminus Z$, we have $\lim_{y \to y_0} w(y) =
w(y_0) = 0$. On the other hand, $|\psi_n(y)| \le \|g_n\|_{\infty,Z} w(y)$ for
all $y \in Y$, which implies that $\lim_{y \to y_0} \psi_n(y) = 0 = \psi_n(y_0)$.
Thus, $\psi_n$ is continuous on all of $Y$. ■

**Proof of Theorem 3.1(i):** Let us first demonstrate that the
following inclusion holds:

$$
\bar{c} \Omega_{\epsilon}(y_0) \subset W(\epsilon, y_0) \quad \forall \epsilon \in (0, 1). \quad (39)
$$

Since $W(\epsilon, y_0)$ is convex and weak* closed, it suffices to
show that $\Lambda_\epsilon(y_0) \subset W(\epsilon, y_0)$. Let $\lambda \in \Lambda_\epsilon(y_0)$. That is, $\lambda$
is the occupational functional generated by a control plan
$\pi \in \Pi$: $\lambda = \lambda^{\pi, y_0, \epsilon}$. We must show that for any test function
$\varphi \in C_w(Y)$, the constraint for $W(\epsilon, y_0)$ is satisfied. The
constraint is:

$$
\langle \lambda, \varphi(y) - (1-\epsilon) \sum_{s \in S} \varphi(f(y, u, s)) \rangle = \epsilon \varphi(y_0).
$$

Letting $y(t) = y^{\pi,y_0}(t)$ and $u(t) = u^{\pi,y_0}(t)$, the left-hand
side is, by definition of the occupational functional:

$$
\begin{align*}
& \langle \lambda, \varphi(y) - (1-\epsilon) \sum_{s \in S} \varphi(f(y, u, s)) \rangle \\
&= \epsilon \sum_{t=0}^{\infty} (1-\epsilon)^t \sum_{s(0), \dots, s(t-1) \in S} [\varphi(y(t)) - (1-\epsilon) \sum_{s \in S} \varphi(f(y(t), u(t), s))] \\
&= \epsilon \sum_{t=0}^{\infty} (1-\epsilon)^t \sum_{s(0), \dots, s(t-1) \in S} \varphi(y(t)) - (1-\epsilon) \sum_{s(0), \dots, s(t) \in S} \varphi(y(t+1)).
\end{align*}
$$
Letting $A_t = (1 - \epsilon)^t \sum_{s(0),...,s(t-1) \in S} \varphi(y(t))$, the sum becomes a telescoping series:

$$ \langle \lambda, \varphi(y) - (1 - \epsilon) \sum_{s \in S} \varphi(f(y, u, s)) \rangle \\ \epsilon \sum_{t=0}^{\infty} (A_t - A_{t+1}) = \epsilon(A_0 - \lim_{t \to \infty} A_{t+1}). $$

We have $A_0 = \varphi(y_0)$. Since $\varphi \in C_w(Y)$, we have $|\varphi(y)| \le \|\varphi\|_{w,Y} w(y)$. Thus,

$$ |A_t| \le (1 - \epsilon)^t \sum_{s(0),...,s(t-1) \in S} |\varphi(y(t))| \\ \le (1 - \epsilon)^t \|\varphi\|_{w,Y} \sum_{s(0),...,s(t-1) \in S} w(y(t)). $$

Then by repeated applications of Equation (9), $\sum_{s(0),...,s(t-1) \in S} w(y(t)) = w(y_0)$. Therefore,

$$ |A_t| \le (1 - \epsilon)^t \|\varphi\|_{w,Y} w(y_0). $$

Since $0 < \epsilon < 1$, $\lim_{t \to \infty} A_t = 0$. This implies

$$ \langle \lambda, \varphi(y) - (1 - \epsilon) \sum_{s \in S} \varphi(f(y, u, s)) \rangle = \epsilon(\varphi(y_0) - 0) = \epsilon\varphi(y_0), \quad (40) $$

which proves that $\lambda \in W(\epsilon, y_0)$.

Let us now show the converse inclusion, $W(\epsilon, y_0) \subseteq \bar{c}\bar{o}\Lambda_{\epsilon}(y_0)$. By the separation theorem for convex sets, this is equivalent to proving that for any $k \in C_w(G)$:

$$ \min_{\lambda \in \bar{c}\bar{o}\Lambda_{\epsilon}(y_0)} \langle \lambda, c \rangle \le \min_{\lambda \in W(\epsilon, y_0)} \langle \lambda, c \rangle. \quad (41) $$

The left-hand side is $\|y_0\|_1 h_{\epsilon}(b_0)$ (by Proposition 2.1, Equation (7) and linearity of the functional). The right-hand side is the value of the primal LP, $c^*(\epsilon, y_0)$. Thus, (41) is equivalent to

$$ \|y_0\|_1 h_{\epsilon}(b_0) \le c^*(\epsilon, y_0). \quad (42) $$

Consider the problem

$$ \mu_{LS}^*(\epsilon, y_0) \stackrel{\text{def}}{=} \sup_{\psi \in LS_w(Y)} \epsilon\psi(y_0) \quad (43) $$

such that

$$ c(y, u) + (1 - \epsilon) \sum_{s \in S} \psi(f(y, u, s)) - \psi(y) \ge 0 \quad (44) $$

Obviously (compare with (19)),

$$ \mu_{LS}^*(\epsilon, y_0) \ge \mu^*(\epsilon, y_0). \quad (45) $$

Let $\psi(y) \stackrel{\text{def}}{=} \tilde{V}_{\epsilon}(y)$. By Lemma 3.2, $\psi \in LS_w(Y)$ and, as the fixed point of $\tilde{T}$, it satisfies the Bellman equation (6). Hence, $\psi$ is feasible for the dual program (43) - (44), with dual value $\epsilon\psi(y_0) = \epsilon\tilde{V}_{\epsilon}(y_0)$. Using (4) and (7),

$$ \epsilon \tilde{V}_{\epsilon}(y_0) = \|y_0\|_1 (\epsilon V_{\epsilon}(b_0)) = \|y_0\|_1 h_{\epsilon}(b_0). $$

Therefore,

$$ \|y_0\|_1 h_{\epsilon}(b_0) \le \mu_{LS}^*(\epsilon, y_0). \quad (46) $$

Take an arbitrary $\gamma \in W(\epsilon, y_0)$ and an arbitrary $\psi \in LS_w(Y)$ satisfying the dual constraint (44). Let $\{\psi_n\}_{n=1}^{\infty}$ be

a bounded sequence of $C_w(Y)$ functions such that $\psi_n(y) \to \psi(y)$ point-wise on $Y$ as $n \to \infty$ (such a sequence exists by Lemma II.1). From Lebesgue's dominated convergence theorem (see, e.g., Theorem 1.6.9, p. 49 in [Ash14]), it follows that

$$ \begin{align*} \psi(y) - (1 - \epsilon) \sum_{s \in S} \psi(f(y, u, s)) &\le c(y, u) \\ \langle \lambda, \psi(y) - (1 - \epsilon) \sum_{s \in S} \psi(f(y, u, s)) \rangle &\le \langle \lambda, c \rangle \\ \lim_{n \to \infty} \langle \lambda, \psi_n(y) - (1 - \epsilon) \sum_{s \in S} \psi_n(f(y, u, s)) \rangle &\le \langle \lambda, c \rangle \\ \lim_{n \to \infty} \epsilon \psi_n(y_0) &\le \langle \lambda, c \rangle \\ \epsilon \psi(y_0) &\le \langle \lambda, c \rangle. \end{align*} $$

Taking sup with respect to feasible $\psi \in LS_w(Y)$ in the left-hand side and then taking min with respect to $\gamma \in W(\epsilon, y_0)$ in the right-hand side allows us to conclude that

$$ \mu_{LS}^*(\epsilon, y_0) \le c^*(\epsilon, y_0). \quad (47) $$

The latter and (46) prove (42). Note that (47) along with (20), (45) imply also that $\mu_{LS}^*(\epsilon, y_0) = \mu^*(\epsilon, y_0)$. Thus, the validity of (21) is established. ■

**Proof of Theorem 3.1(ii):** (22) is implied by (21) due to the validity of the equalities

$$ \|y_0\|_1 h_{\epsilon}(b_0) = \min_{\lambda \in \Lambda_{\epsilon}(y_0)} \langle \lambda, c \rangle = \min_{\lambda \in \bar{c}\bar{o}\Lambda_{\epsilon}(y_0)} \langle \lambda, c \rangle \quad (48) $$

(see (13) and (17)).

**Proof of Theorem 3.1(iii):** By definition,

$$ \tilde{V}_{\epsilon}(y) = \min_{u \in U(y)} \{c(y, u) + (1 - \epsilon) \sum_{s \in S} \tilde{V}_{\epsilon}(f(y, u, s))\} \quad \forall y \in Y, $$

implying

$$ \tilde{V}_{\epsilon}(y) \le c(y, u) + (1 - \epsilon) \sum_{s \in S} \tilde{V}_{\epsilon}(f(y, u, s)) \quad \forall (y, u) \in G. $$

Comparing the above with (19), we see that $\tilde{V}_{\epsilon}(y)$ is feasible in the dual problem. By Lemma 2.1, Proposition 3.3 Theorem 3.1(ii)

$$ \begin{align*} \epsilon \tilde{V}_{\epsilon}(y_0) &= \epsilon \|y_0\|_{V_{\epsilon}(b_0)} = \|y_0\|_1 h_{\epsilon}(b_0) = c^*(\epsilon, y_0) \\ &= \mu^*(\epsilon, y_0), \end{align*} $$

thus $\tilde{V}_{\epsilon}(y_0)$ is optimal in $\mu^*(\epsilon, y_0)$. ■

## APPENDIX III
### PROOF OF THEOREM 3.2

(⇒) **An optimal plan must satisfy (23) on its trajectory.** Let $\psi^* \in C_w(Y)$ be an optimal solution to the dual problem (19), and let $\lambda^{\pi^*, y_0, \epsilon} \in W(\epsilon, y_0)$ be the occupational functional corresponding to $\pi^*$. Note that this functional is optimal in (17) by Theorem 3.1. From the strong duality result (Proposition 3.3) and the equivalence established in Theorem 3.1(ii), the optimal primal and dual values are equal:

$$ \langle \lambda^{\pi^*, y_0, \epsilon}, c \rangle = \epsilon \psi^*(y_0). \quad (48) $$
The dual solution $\psi^*$ is feasible and satisfies the dual constraint in (19) for all $(y, u) \in G$:

$$ \psi^*(y) \le c(y, u) + (1 - \epsilon) \sum_{s \in S} \psi^*(f(y, u, s)). \quad (49) $$

We define the non-negative slack function $L(y, u) \ge 0$ for this inequality:

$$ L(y, u) \stackrel{\text{def}}{=} c(y, u) + (1 - \epsilon) \sum_{s \in S} \psi^*(f(y, u, s)) - \psi^*(y). $$

Applying the optimal occupational functional $\lambda^{\pi^*, y_0, \epsilon}$ to either side:

$$ \begin{aligned} & \langle \lambda^{\pi^*, y_0, \epsilon}, L(y, u) \rangle + \langle \lambda^{\pi^*, y_0, \epsilon}, \psi^*(y) \rangle \\ & = \langle \lambda^{\pi^*, y_0, \epsilon}, c(y, u) + (1 - \epsilon) \sum_{s \in S} \psi^*(f(y, u, s)) \rangle. \end{aligned} \quad (50) $$

The solution $\lambda^{\pi^*, y_0, \epsilon}$ is feasible, so it satisfies the primal constraint (17) for the test function $\phi(y) = \psi^*(y)$:

$$ \langle \lambda^{\pi^*, y_0, \epsilon}, \psi^*(y) - (1 - \epsilon) \sum_{s \in S} \psi^*(f(y, u, s)) \rangle = \epsilon \psi^*(y_0). $$

Using the strong duality equality (48), we can replace $\epsilon\psi^*(y_0)$ with the optimal primal objective value:

$$ \begin{aligned} & \langle \lambda^{\pi^*, y_0, \epsilon}, \psi^*(y) - (1 - \epsilon) \sum_{s \in S} \psi^*(f(y, u, s)) \rangle \\ & = \langle \lambda^{\pi^*, y_0, \epsilon}, c(y, u) \rangle. \end{aligned} \quad (51) $$

Rearranging this yields:

$$ \begin{aligned} & \langle \lambda^{\pi^*, y_0, \epsilon}, \psi^*(y) \rangle \\ & = \langle \lambda^{\pi^*, y_0, \epsilon}, c(y, u) + (1 - \epsilon) \sum_{s \in S} \psi^*(f(y, u, s)) \rangle. \end{aligned} $$

Substituting this back into (50), we observe that

$$ \langle \lambda^{\pi^*, y_0, \epsilon}, L(y, u) \rangle = 0. \quad (52) $$

By the definition of the occupational functional (12),

$$ \begin{aligned} & \langle \lambda^{\pi^*, y_0, \epsilon}, L \rangle \\ & = \epsilon \sum_{t=0}^{\infty} (1 - \epsilon)^t \sum_{s(0), \dots, s(t-1) \in S} L(y^{\pi^*, y_0}(t), u^{\pi^*, y_0}(t)) = 0. \end{aligned} $$

Since all summands are nonnegative and the weights are strictly positive, each summand must be zero. Hence, for every $t \ge 0$ and every history $s(0), \dots, s(t-1)$,

$$ L(y^{\pi^*, y_0}(t), u^{\pi^*, y_0}(t)) = 0. $$

This gives precisely the equality stated in (23) for all points along any realized optimal trajectory. Since $L(y, u) \ge 0$ for all $u \in U(y)$, having $L(y^{\pi^*, y_0}(t), u^{\pi^*, y_0}(t)) = 0$ directly implies that $u^{\pi^*, y_0}(t)$ achieves the minimum in (24). This proves the necessity.

(=$\Leftarrow$) A plan satisfying (23) on its trajectory is optimal. Let $\pi$ be a control plan such that

$$ \begin{aligned} & \psi^*(y^{\pi^*, y_0}(t)) = c(y^{\pi^*, y_0}(t), u^{\pi^*, y_0}(t)) \\ & + (1 - \epsilon) \sum_{s \in S} \psi^*(f(y^{\pi^*, y_0}(t), u^{\pi^*, y_0}(t), s)). \end{aligned} \quad (53) $$

Using the definition of $f(y, u, s)$ in (5), we can rearrange:

$$ \begin{aligned} & c(y^{\pi^*, y_0}(t), u^{\pi^*, y_0}(t)) \\ & = \psi^*(y^{\pi^*, y_0}(t)) - (1 - \epsilon) \sum_{s(0), \dots, s(t-1)} \psi^*(y^{\pi^*, y_0}(t+1)). \end{aligned} \quad (54) $$

This equality holds for each step $t$ along the trajectory. We now use it to evaluate the cost of the policy $\pi^*$, which is defined as $J_{\epsilon}^{\pi^*}(y_0) = \epsilon \sum_{t=0}^{\infty} (1 - \epsilon)^t \sum_{s(0), \dots, s(t-1)} c(y^{\pi^*, y_0}(t), u^{\pi^*, y_0}(t))$.

Substituting (54) into this formula gives:

$$ \begin{aligned} & \frac{J_{\epsilon}^{\pi^*}(y_0)}{\epsilon} \\ & = \sum_{t=0}^{\infty} (1 - \epsilon)^t \sum_{s(0), \dots, s(t-1)} \psi^*(y^{\pi^*, y_0}(t)) - (1 - \epsilon) \sum_{s \in S} \psi^*(y^{\pi^*, y_0}(t+1)). \end{aligned} $$

Let $A_t \stackrel{\text{def}}{=} (1 - \epsilon)^t \sum_{s(0), \dots, s(t-1)} \psi^*(y^{\pi^*, y_0}(t))$. Note that the second term in the sum is $A_{t+1}$. The sum becomes a telescoping series:

$$ \frac{J_{\epsilon}^{\pi^*}(y_0)}{\epsilon} = \sum_{t=0}^{\infty} (A_t - A_{t+1}) = A_0 - \lim_{t \to \infty} A_t. $$

The initial term is

$$ A_0 = (1 - \epsilon)^0 \sum_{s(0), \dots, s(t-1)} \psi^*(y^{\pi^*, y_0}(0)) = \psi^*(y_0). $$

Since $\psi^* \in C_w(Y)$, we have $|\psi^*(y)| \le \|\psi^*\|_{w,Y} w(y)$. Thus,

$$ \begin{aligned} & |A_t| \le (1 - \epsilon)^t \sum_{s(0), \dots, s(t-1)} |\psi^*(y(t))| \\ & \le (1 - \epsilon)^t \|\psi^*\|_{w,Y} \sum_{s(0), \dots, s(t-1)} w(y^{\pi^*, y_0}(t)). \end{aligned} $$

By repeated applications of Equation (9), $\sum_{s(0), \dots, s(t-1)} w(y^{\pi^*, y_0}(t)) = w(y_0)$. Therefore,
$$ |A_t| \le (1 - \epsilon)^t \|\psi^*\|_{w,Y} w(y_0). $$

Since $0 < \epsilon < 1$, $\lim_{t \to \infty} A_t = 0$. The telescoping sum thus evaluates to $A_0 = \psi^*(y_0)$, giving

$$ \frac{J_{\epsilon}^{\pi^*}(y_0)}{\epsilon} = \psi^*(y_0) \implies J_{\epsilon}^{\pi^*}(y_0) = \epsilon\psi^*(y_0). $$

From Proposition 3.3, Theorem 3.1, and since $\psi^*$ is a solution to the dual problem, we have

$$ J_{\epsilon}^{\pi^*}(y_0) = \epsilon\psi^*(y_0) = \mu^*(\epsilon, y_0) = \|y_0\|_1 h_{\epsilon}(b_0). $$

The cost incurred by policy $\pi^*$ is equal to the optimal cost. Thus, the policy $\pi^*$ is optimal, as required.

## APPENDIX IV
### STONE-ČECH COMPACTIFICATION

We present here an auxiliary compactification result required in Proposition V.1 to formalize trajectory convergence of the relaxed SILP formulations.

**Lemma IV.1:** Let $Z = \{(y, u) \in G \mid w(y) \ne 0\}$ and $C_b(Z)$ be the space of bounded continuous functions on $Z$ equipped with the standard supremum norm. The space
$C_w(G)$ is isometrically isomorphic to $C_b(Z)$ under the map
$T: C_w(G) \to C_b(Z)$ defined by

$$
T(f) = f/w.
$$

Proof: We prove that $T$ is a well-defined isometry satisfying surjectivity. $T$ is well-defined: For any $f \in C_w(G)$, $T(f)$ is continuous on $Z$ since $f$ and $w$ are continuous and $w(y) \neq 0$ on $Z$. Further, by definition of $\|\cdot\|_w$,

$$
\left| \frac{f(y, u)}{w(y)} \right| \le \|f\|_w < \infty,
$$

implying $\|T(f)\|_{\infty} \le \|f\|_{w}$.
$T$ is an isometry: By definition,

$$
\|T(f)\|_{\infty} = \sup_{(y,u) \in Z} \left| \frac{f(y,u)}{w(y)} \right| = \|f\|_{w}.
$$

T is surjective: Let $f \in C_b(Z)$. Define

$$
g(y, u) = \begin{cases} f(y, u)w(y) & \text{if } w(y) \neq 0, \\ 0 & \text{if } w(y) = 0. \end{cases}
$$

We verify that $g \in C_w(G)$. Clearly for $w(y) \neq 0$, it is continuous. Let $(y_0, u_0)$ be such that $w(y_0) = 0$ and $(y_n, u_n) \to (y_0, u_0)$. Since $f \in C_b(Z)$, $\exists M$ such that

$$
\|f\|_{\infty} \le M \quad \forall (y, u) \in Z.
$$

Note if any $y_n$ in the sequence is such that $w(y_n) = 0$, then $g(y_n, u_n) = 0$. Otherwise, if $w(y_n) \ne 0$, then $|g(y_n, u_n)| = |f(y_n, u_n)w(y_n)| \le Mw(y_n)$. Since $w(\cdot)$ is continuous, $w(y_n) \to w(y_0) = 0$. Therefore, $|g(y_n, u_n)| \to 0 = g(y_0, u_0)$, thus $g(y, u)$ is continuous.

For boundedness of $g$, note that

$$
\begin{align*}
\|g\|_w &= \sup_{(y,u) \in G, w(y) \neq 0} \frac{|g(y,u)|}{w(y)} \\
&= \sup_{(y,u) \in Z} \frac{|f(y,u)w(y)|}{w(y)} = \sup_{(y,u) \in Z} |f(y,u)| = \|f\|_{\infty}.
\end{align*}
$$

Since $f \in C_b(Z)$, $\|f\|_{\infty}$ is finite. Thus, $g \in C_w(G)$.
Finally, $T(g)(y, u) = \frac{g(y, u)}{w(y)} = \frac{f(y, u)w(y)}{w(y)} = f(y, u)$ for
$(y, u) \in Z$. So $T(g) = f$, which proves surjectivity. Since
$T$ is a surjective linear isometry, $C_w(G)$ and $C_b(Z)$ are
isometrically isomorphic. $\square$

Lemma IV.2: The space $(C_w(G))^*$ is isometrically isomorphic to the space of signed Borel measures $M(\beta Z)$, where $\beta Z$ is the Stone-Čech compactification of $Z$.

Proof: Follows from Lemma IV.1 and [Con19, Corol-
lary 6.4].
■

APPENDIX V
PROOF OF THEOREM 4.1

Proposition V.1: Assume

$$
\{y \in \text{int}(\text{cl}\mathcal{R}_{y_0}) \mid w(y) > 0\} \neq \emptyset. \quad (55)
$$

Then for any $N \ge 1$:

(i) Any maximizing sequence of coefficient vectors
$\{v_k\}_{k=1}^\infty \subset \mathbb{R}^N$ for the dual problem (61) is
bounded.

(ii) An optimal solution to the dual problem (61) exists.

Proof: Let us consider a maximizing sequence in the problem $\mu_N^*(\epsilon, y_0)$, that is, for $k = 1, 2, \dots$ let $v_k = (v_k^1, \dots, v_k^N) \in \mathbb{R}^N$ be such that the function

$$
\psi_k(y) \stackrel{\text{def}}{=} \sum_{i=1}^{N} v_k^i \varphi_i(y)
$$

satisfies the inequality

$$
c(y, u) + (1 - \epsilon) \sum_{s \in S} \psi_k(f(y, u, s)) - \psi_k(y) \geq 0 \quad \forall (y, u) \in G \quad (56)
$$

and we have

$$
\mu_N^*(\epsilon, y_0) - \epsilon\psi_k(y_0) \le \frac{1}{k}. \quad (57)
$$

We will show that the sequence $v_k$, $k = 1, 2, \dots$ is bounded and, therefore, has a convergent subsequence. Assume to the contrary that there exists a subsequence $v_{k'}$ such that

$$
\lim_{k' \to \infty} |v_{k'}| = \infty, \quad \lim_{k' \to \infty} \frac{v_{k'}}{|v_{k'}|} \stackrel{\text{def}}{=} \tilde{v}, \quad |\tilde{v}| = 1.
$$

Dividing (56) and (57) by $|v_k|$ and passing to the limit along
the subsequence $\{k'\}$, we obtain

$$
(1 - \epsilon) \sum_{s \in S} \tilde{\psi}_k(f(y, u, s)) - \tilde{\psi}_k(y) \geq 0 \quad \forall (y, u) \in G \quad (58)
$$

and

$$
-\epsilon \tilde{\psi}_k(y_0) \le 0, \quad (59)
$$

where

$$
\tilde{\psi}_k \stackrel{\text{def}}{=} \sum_{i=1}^{N} \tilde{v}_i \varphi_i(y).
$$

We verify now that condition (55) and (58) - (59) imply
that $\tilde{\psi}_k = 0$, thereby contradicting the linear independence
of the polynomial basis $\{\varphi_i\}_{i=1}^N$. Let $\lambda \in \Lambda_\epsilon(y_0)$ arbitrarily
and define $q(y, u) \stackrel{\text{def}}{=} (1 - \epsilon) \sum_{s \in S} \tilde{\psi}_k(f(y, u, s)) - \tilde{\psi}_k(y)$.
From (58), we have

$$
q(y, u) \geq 0 \quad \forall (y, u) \in G.
$$

By Theorem 3.1, $\lambda \in W(\epsilon, y_0)$. Hence, since $\tilde{\psi}_k \in C_w(Y)$, we have

$$
\langle \lambda, -q \rangle = \epsilon \tilde{\psi}_k(y_0).
$$

Since $\lambda$ is positive and $-q \le 0$, we have

$$
\epsilon \tilde{\psi}_k(y_0) = \langle \lambda, -q \rangle \le 0.
$$

The above combined with (59) implies $\epsilon\tilde{\psi}_k(y_0) = 0$. Furthermore, by definition of the occupational functional,

$$
\begin{align*}
& \langle \lambda, q \rangle \\
&= \epsilon \sum_{t=0}^{\infty} (1-\epsilon)^t \sum_{s(0), \dots, s(t-1)} q(y^{\pi, y_0}(t), u^{\pi, y_0}(t)) \\
&= -\epsilon \tilde{\psi}_k(y_0) \\
&= 0.
\end{align*}
$$

As this is a sum of non-negative terms, each term must be
zero. Since this holds for an arbitrary control plan $\pi$, we
have that $q(y, u) = 0$ for any $(y, u)$ on any trajectory with initial condition $y_0$. Thus, for all $y \in \text{cl}(\mathcal{R}_{y_0})$ and $u \in U(y)$,

$$ \tilde{\psi}_k(y) = (1 - \epsilon) \sum_{s \in S} \tilde{\psi}_k(f(y, u, s)). \quad (60) $$

We now show that $\tilde{\psi}_k = 0$. Consider the weighted norm of $\tilde{\psi}_k$ restricted to the compact set $\text{cl}(\mathcal{R}_{y_0})$:

$$ \|\tilde{\psi}_k\|_{w,\text{cl}(\mathcal{R}_{y_0})} \stackrel{\text{def}}{=} \sup_{y \in \text{cl}(\mathcal{R}_{y_0}), w(y) \neq 0} \frac{|\tilde{\psi}_k(y)|}{w(y)}. $$

Applying this norm to both sides of (60):

$$ \begin{aligned} & \|\tilde{\psi}_k\|_{w,\text{cl}(\mathcal{R}_{y_0})} \\ &= (1 - \epsilon) \sup_{y \in \text{cl}(\mathcal{R}_{y_0}), w(y) \neq 0} \frac{|\sum_{s \in S} \tilde{\psi}_k(f(y, u, s))|}{w(y)} \\ &\le (1 - \epsilon) \sup_{y \in \text{cl}(\mathcal{R}_{y_0}), w(y) \neq 0} \frac{\sum_{s \in S} |\tilde{\psi}_k(f(y, u, s))|}{w(y)}. \end{aligned} $$

By definition of the weighted norm, $|\tilde{\psi}_k(z)| \le \|\tilde{\psi}_k\|_{w,\text{cl}(\mathcal{R}_{y_0})} w(z)$ for any reachable state $z$. Substituting this into the expectation:

$$ \begin{aligned} & \|\tilde{\psi}_k\|_{w,\text{cl}(\mathcal{R}_{y_0})} \\ &\le (1 - \epsilon) \sup_{y \in \text{cl}(\mathcal{R}_{y_0}), w(y) \neq 0} \frac{\sum_{s \in S} \|\tilde{\psi}_k\|_{w,\text{cl}(\mathcal{R}_{y_0})} w(f(y, u, s))}{w(y)} \\ &= (1 - \epsilon) \|\tilde{\psi}_k\|_{w,\text{cl}(\mathcal{R}_{y_0})} \sup_{y \in \text{cl}(\mathcal{R}_{y_0}), w(y) \neq 0} \frac{\sum_{s \in S} w(f(y, u, s))}{w(y)}. \end{aligned} $$

By 9, $\sum_{s \in S} w(f(y, u, s)) = w(y)$, so the supremum is at most 1. This yields:

$$ \|\tilde{\psi}_k\|_{w,\text{cl}(\mathcal{R}_{y_0})} \le (1 - \epsilon) \|\tilde{\psi}_k\|_{w,\text{cl}(\mathcal{R}_{y_0})}. $$

Since $\epsilon \in (0, 1)$ and the norm is non-negative, this inequality holds only if $\|\tilde{\psi}_k\|_{w,\text{cl}(\mathcal{R}_{y_0})} = 0$. This implies $\tilde{\psi}_k(y) = 0$ for all $y \in \text{cl}(\mathcal{R}_{y_0})$ where $w(y) \neq 0$. For points where $w(y) = 0$, $\tilde{\psi}_k(y) = w(y)\tilde{p}(y)$ (see (26)) is also zero. Thus, $\tilde{\psi}_k(y) = 0$ for all $y \in \text{cl}(\mathcal{R}_{y_0})$.

From (55), $\text{cl}(\mathcal{R}_{y_0})$ has a non-empty interior. Since $\tilde{\psi}_k(y) = w(y)\tilde{p}(y) = 0$ and $w(y) > 0$ on this set, the polynomial $\tilde{p}(y)$ must be zero on a set with a non-empty interior, which implies $\tilde{p} \equiv 0$. Consequently, $\tilde{\psi}_k \equiv 0$. This contradicts that $|\tilde{v}| = 1$ and that the basis functions $\{\varphi_i\}$ are linearly independent. Thus, the sequence $\{v_k\}$ must be bounded.

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

The dual to (27) is given by:

$$ \mu_N^*(\epsilon, y_0) \stackrel{\text{def}}{=} \sup_{\psi \in D_N} \epsilon \psi(y_0) \quad (61) $$

subject to the constraint

$$ c(y, u) + (1 - \epsilon) \sum_{s \in S} \psi(f(y, u, s)) - \psi(y) \ge 0, \quad \forall (y, u) \in G, \quad (62) $$

where $D_N$ is the finite-dimensional subspace of $C_w(Y)$ spanned by the first $N$ basis functions:

$$ D_N \stackrel{\text{def}}{=} \left\{ \psi \in C_w(Y) \mid \psi(y) = \sum_{i=1}^{N} v_i \varphi_i(y); v_i \in \mathbb{R} \right\}. \quad (63) $$

We verify that strong duality holds between (27) and (61):

**Lemma V.1:** Let Assumption 4.1(i) hold. The optimal value of problem (27) is equal to the optimal value of problem (61). That is,

$$ c_N^*(\epsilon, y_0) = \mu_N^*(\epsilon, y_0) $$

*Proof:* First, we establish weak duality: $c_N^*(\epsilon, y_0) \ge \mu_N^*(\epsilon, y_0)$. For any feasible $\lambda \in W_N(\epsilon, y_0)$ and $\psi \in D_N$, the dual constraint (62) gives

$$ c(y, u) \ge \psi(y) - (1 - \epsilon) \sum_{s \in S} \psi(f(y, u, s)). $$

Applying the positive functional $\lambda$ and using the primal constraint (28) yields:

$$ \langle \lambda, c \rangle \ge \langle \lambda, \psi(y) - (1 - \epsilon) \sum_{s \in S} \psi(f(y, u, s)) \rangle = \epsilon \psi(y_0). \quad (64) $$

Taking the infimum over all feasible $\lambda$ and the supremum over all feasible $\psi$ establishes the inequality.

To prove the reverse inequality, we use a convex separation argument. Define the set $\hat{Q} \subset \mathbb{R} \times \mathbb{R}^N$ by

$$ \hat{Q} \stackrel{\text{def}}{=} \left\{ (\langle \lambda, c \rangle, \langle \lambda, x_1 \rangle, \dots, \langle \lambda, x_N \rangle) \mid \lambda \in C_{w,+}(G)^* \right\}, $$

where $x_i(y, u) \stackrel{\text{def}}{=} \varphi_i(y) - (1 - \epsilon) \sum_{s \in S} \varphi_i(f(y, u, s))$. The set $\hat{Q}$ is a closed convex cone. Let $x_0 \stackrel{\text{def}}{=} (\epsilon\varphi_1(y_0), \dots, \epsilon\varphi_N(y_0))$. By definition of the primal optimum, the point $(c_N^*(\epsilon, y_0) - \delta, x_0)$ for any $\delta > 0$ is not in $\hat{Q}$.

By the Hahn-Banach separation theorem, there exists a non-zero vector $(v_0, v) \in \mathbb{R} \times \mathbb{R}^N$ such that

$$ v_0(c_N^*(\epsilon, y_0) - \delta) + \sum_{i=1}^{N} v_i(\epsilon\varphi_i(y_0)) \le 0 \le \inf_{(\theta, x) \in \hat{Q}} \{v_0\theta + \sum_{i=1}^{N} v_i x_i\}. \quad (65) $$

Note the 0 in the middle of the inequality follows since $\hat{Q}$ is a cone. Further, by taking the element in $\hat{Q}$ corresponding to the optimizer $\lambda_N^*$, we get $v_0 \ge 0$.

We show $v_0 > 0$ by contradiction. Assume $v_0 = 0$. Then $v \ne 0$, and defining

$$ \psi(y) \stackrel{\text{def}}{=} - \sum_{i=1}^{N} v_i \varphi_i(y), $$

we have

$$ \begin{aligned} & v_0\theta + \sum_{i=1}^{N} v_i x_i \\ &= (1 - \epsilon) \sum_{s \in S} \psi(f(y, u, s)) - \psi(y) \ge 0, \quad \forall (y, u) \in G \end{aligned} $$
and

$$v_0(c_N^*(\epsilon, y_0) - \delta) + \sum_{i=1}^N v_i(\epsilon\varphi_i(y_0)) = -\epsilon\psi(y_0) \le 0$$

As shown in the proof of Proposition V.1, these conditions together with Assumption 4.1(i) imply $\psi \equiv 0$. This requires $v = 0$ due to the linear independence of the basis $\{\varphi_i\}$.

Thus, $v_0 > 0$ and we can normalize it to $v_0 = 1$. Let $\psi(y) \stackrel{\text{def}}{=} -\sum v_i\varphi_i(y)$. By the second inequality in (65), we have for any $\lambda \in C_{w,+}(G)^*$ that

$$\begin{aligned} & v_0\langle\lambda, c\rangle + \sum_{i=1}^N v_i\langle\lambda, x_i\rangle \\ & = \langle\lambda, c(y, u) + (1-\epsilon)\sum_{s \in S} \psi(f(y, u, s)) - \psi(y)\rangle \ge 0. \end{aligned}$$

Therefore

$$c(y, u) + (1 - \epsilon) \sum_{s \in S} \psi(f(y, u, s) - \psi(y)) \ge 0 \quad \forall (y, u) \in G.$$

By the first inequality in (65), we have

$$c_N^*(\epsilon, y_0) - \delta \le -\sum_{i=1}^N v_i \epsilon \varphi_i(y_0) = \epsilon \psi(y_0) \le \mu_N^*(\epsilon, y_0).$$

Since this holds for any $\delta > 0$, we have $c_N^*(\epsilon, y_0) \le \mu_N^*(\epsilon, y_0)$. Combined with (64), this completes the proof. ■

**Lemma V.2:** Let $\lambda^N \in C_w(G)^*$ be an optimal solution to the primal SILP (27) and $\psi^N$ be an optimal solution to its dual (61). Define

$$S^N(y, u) \stackrel{\text{def}}{=} c(y, u) + (1 - \epsilon) \sum_{s \in S} \psi^N(f(y, u, s)) - \psi^N(y).$$

Then $S^N \ge 0$ on $Z = \{(y, u) \in G \mid w(y) \ne 0\}$ and its continuous extension $\tilde{S}^N$ to $\beta Z$ satisfies

$$\int_{\beta Z} \tilde{S}^N d\lambda^N = 0,$$

hence $\tilde{S}^N$ vanishes on $\text{supp}_{\beta Z}(\lambda^N)$.

*Proof:* By strong duality (Lemma V.1),

$$\langle \lambda^N, k \rangle = \epsilon \psi^N(y_0). \quad (66)$$

By primal feasibility,

$$\langle \lambda^N, \psi^N(y) - (1 - \epsilon) \sum_{s \in S} \psi^N(f(y, u, s)) \rangle = \epsilon \psi^N(y_0). \quad (67)$$

Subtracting (67) from (66) yields

$$\langle \lambda^N, S^N \rangle = 0.$$

Dual feasibility implies $S^N \ge 0$ on $Z$. As $\lambda^N$ is a positive measure on $\beta Z$, this implies $\tilde{S}^N = 0$ on $\text{supp}_{\beta Z}(\lambda^N)$. ■

**Lemma V.3:** Let $(\lambda^N, \psi^N)$ be an optimal primal-dual pair. Let $Q \stackrel{\text{def}}{=} \bigcup_{t=0}^{\infty} Q_t$ be the open neighborhood of the optimal trajectory from Assumption 4.1(iii). Then

$$\text{supp}_{\beta Z}(\lambda^N) \cap (Q \times U \cap Z) \subseteq \{(y, u^N(y)) : y \in Q \cap Z\}$$

where $u^N(\cdot)$ is as defined in (30).

*Proof:* Let $(y, u) \in \text{supp}_{\beta Z}(\lambda^N) \cap (Q \times U \cap Z)$. By Lemma V.2,

$$S^N(y, u) = 0.$$

Dual feasibility implies $S^N(y, u') \ge 0$, for all $u' \in U(y)$. Thus,

$$\min_{u' \in U(y)} S^N(y, u') = 0.$$

Since $u \in U(y)$ and $S^N(y, u) = 0$, the minimum is attained at $u$:

$$S^N(y, u) = \min_{u' \in U(y)} S^N(y, u') = 0.$$

By Assumption 4.1(iii), the minimizer is unique, so $u = u^N(y)$. ■

**Lemma V.4:** Let $\{\lambda^N\}$ be a sequence of positive finite measures on the compact space $\beta Z$ converging weak* to $\lambda^*$. Then for any $p^* \in \text{supp}_{\beta Z}(\lambda^*)$ there exists a sequence $\{p_N\}$ with $p_N \in \text{supp}_{\beta Z}(\lambda^N)$ and $p_N \to p^*$ in $\beta Z$.

*Proof:* For each integer $m \ge 1$, define an open neighborhood

$$U_m \stackrel{\text{def}}{=} B_{1/m}(p^*).$$

Since $p^* \in \text{supp}(\lambda^*)$ we have $\lambda^*(U_m) > 0$ for every $m$. By the Portmanteau theorem of weak* convergence of positive finite measures, we have

$$\liminf_{N \to \infty} \lambda^N(U_m) \ge \lambda^*(U_m) > 0.$$

So for each $m$ there exists $N'_m$ with $\lambda^N(U_m) > 0$ for all $N \ge N'_m$. Define

$$N_m \stackrel{\text{def}}{=} \max\{N'_1, \dots, N'_m\}$$

to obtain an increasing sequence $N_1 < N_2 < \dots$ with the property: for every $m$ and every $N \ge N_m$,

$$\lambda^N(U_m) > 0.$$

For every $N \ge N_1$, define

$$m(N) \stackrel{\text{def}}{=} \max\{m : N_m \le N\}.$$

Since $\lambda^N(U_{m(N)}) > 0$ we may choose

$$p_N \in \text{supp}(\lambda^N) \cap U_{m(N)}.$$

Hence $d(p_N, p^*) \le 1/m(N) \to 0$, so $p_N \to p^*$. ■

**Theorem V.1:** Let Assumption 4.1 hold. Then for any realization of the stochastic process $\{s(t)\}_{t=0}^{\infty}$, the following pathwise convergence holds:

$$\begin{aligned} \lim_{N \to \infty} u^N(y^N(t)) &= u^{\bar{\pi}, y_0}(t) \\ \lim_{N \to \infty} y^N(t) &= y^{\bar{\pi}, y_0}(t). \end{aligned} \quad (68)$$

where $(y^N(t), u^N(y^N(t)))$ is the trajectory generated by the approximate control (see Equation (30)).

*Proof:* Let $\{\lambda^N\}$ be a sequence of optimal solutions to (27). By Proposition 4.1, $\lambda^N \to \lambda^*$, where $\lambda^*$ is the unique primal optimizer by Assumption 4.1(vii). Let $\bar{\pi}$ be an optimal control plan. The associated occupational functional $\lambda^{\bar{\pi}}$ is
feasible for the IDLP (by Theorem 3.1) and achieves the
optimal value

$$
\langle \lambda^{\bar{\pi}}, k \rangle = \|y_0\|_1 h_{\epsilon}(b_0) = c^*(\epsilon, y_0),
$$

by Theorem 3.1.

Fix $t \ge 0$ and let $p_t^* \stackrel{\text{def}}{=} (y^{\bar{\pi}, y_0}(t), u^{\bar{\pi}, y_0}(t))$. We have
$p_t^* \in \text{supp}_{\beta Z}(\lambda^*) \cap Z$. By Lemma V.4, there exists $p_N =$
$(y_N, u_N) \in \text{supp}_{\beta Z}(\lambda^N)$ such that $p_N \to p_t^*$. For $N$ large
enough, we have $y_N \in \mathcal{Q}$, so Lemma V.3 implies

$$
u_N = u^N(y_N).
$$

Thus $y_N \to y^{\bar{\pi}}(t)$ and $u^N(y_N) = u_N \to u^{\bar{\pi}}(t)$. Using Lipschitz continuity of $u^N$,

$$
\begin{align*}
& |u^N(y^{\bar{\pi}}(t)) - u^{\bar{\pi}}(t)| \\
\le {} & |u^N(y^{\bar{\pi}}(t)) - u^N(y_N)| + |u^N(y_N) - u_N| + |u_N - u^{\bar{\pi}}(t)| \\
\le {} & L_u |y^{\bar{\pi}}(t) - y_N| + |u_N - u^{\bar{\pi}}(t)| \to 0.
\end{align*}
$$

Thus $u^N(y^{\bar{\pi}}(t)) \to u^{\bar{\pi}}(t)$ as $N \to \infty$. Let $e_N(t) = |y^N(t) - y^{\bar{\pi}}(t)|$. By definition and Lipschitz continuity of $f$, we have

$$
\begin{align*}
e_N(t+1) &\le L_f (|y^N(t) - y^{\bar{\pi}}(t)| + |u^N(y^N(t)) - u^{\bar{\pi}}(t)|) \\
&= L_f (e_N(t) + |u^N(y^N(t)) - u^{\bar{\pi}}(t)|).
\end{align*}
$$

Lipschitz property of $u^N$ then yields

$$
\begin{align*}
& |u^N(y^N(t)) - u^{\bar{\pi}}(t)| \\
\le {} & |u^N(y^N(t)) - u^N(y^{\bar{\pi}}(t))| + |u^N(y^{\bar{\pi}}(t)) - u^{\bar{\pi}}(t)| \\
\le {} & L_u e_N(t) + |u^N(y^{\bar{\pi}}(t)) - u^{\bar{\pi}}(t)|,
\end{align*}
$$

implying

$$
e_N(t+1) \le L_f(1+L_u)e_N(t) + L_f|u^N(y^{\bar{\pi}}(t)) - u^{\bar{\pi}}(t)|.
$$

Set $C = L_f(1+L_u)$ and $\eta_N(t) = L_f|u^N(y^{\bar{\pi}}(t)) - u^{\bar{\pi}}(t)| \to$
0. By the discrete Gronwall-Bellman lemma,

$$
e_N(t) \le \sum_{k=0}^{t-1} C^{t-1-k} \eta_N(k),
$$

which tends to 0 for each fixed $t$. Thus $y^N(t) \to y^{\bar{\pi}}(t)$
pointwise, and the convergence of controls $u^N(y^N(t)) \to$
$u^{\bar{\pi}}(t)$ follows.
$\blacksquare$