Construction of Belief MDP

Construction of the Filter Process

Let $Q(B\mid x):=P(y_{t}\in\cdot \mid x_{t}=x)$ and assuming $Q\ll\lambda$ we define the Radon-Nikodym Derivative $g$: $$g(x,y)=\frac{dG(y_{n}\in\cdot \mid x_{n}=x)}{d\lambda}(y)$$We can then describe $\pi_{n+1}$ in terms of $\pi_{n},y_{n+1},u_{n}$ using the kernel $\mathcal{T}$ and $g$: $$\begin{align*} \pi_{n+1}(dx_{n+1})&:=F(\pi_{n},y_{n+1},u_{n})(dx_{n+1})\\\\ &=\frac{\int\limits _{\mathbb{X}}g(x_{n+1},y_{n+1})\mathcal{T}(dx_{n+1}\mid x_{n},u_{n})\,\pi_{n}(dx_{n})}{\int\limits _{\mathbb{X}}\int\limits _{\mathbb{X}}g(x_{n+1},y_{n+1})\mathcal{T}(dx_{n+1}\mid x_{n},u_{n}) \, \pi_{n}(dx_{n}) } \end{align*}$$where we integrate over $dx_{n}$ in both and denominator integrates over $dx_{n+1}$ as well.

Transition Kernel of the Filter Process

We define the transition probability $\eta$ of the filter process as follows: $$\eta(\cdot \mid \pu{ ,u }):=\int\limits _{\mathbb{Y}}\mathbb{1}_{\{ F(\pi,u,y)\in \cdot \}} \, P(dy\mid \pi,u)$$where $$F(\pi,u,y):=F(\cdot \mid y,u,\pi)$$

Cost Function of the Filter Process

Assuming we want to minimize the Finite Horizon Optimization problem $$E_{x_{0}}^{\gamma}\left[ \sum_{k=0}^{N-1}c(X_{k},U_{k})+c_{N}(X_{N}) \right]$$we define the cost function $\tilde{c}:\mathcal{P}(\mathbb{X})\times \mathbb{U}\to[0,\infty)$ as $$\tilde{c}(\pi,u)=\int\limits _{\mathbb{X}}c(x,u) \, \pi(dx)$$ >[!thm] Filter process is a CMC >Let $(\mathbb{X}, \mathbb{U}, \mathbb{Y}, \mathbb{K},\mathcal{T}, Q,c)$ be a POMDP with filter process $\pi_{t}$. Then, $\{ \pi_{t},u_{t} \}$ is a Controlled Markov Chain.

Weak Feller Continuity of Belief MDP

\begin{proof} See Kara yuksel 2019 \end{proof} >[!assumption|1] >1. The transition probability $\mathcal{T}(\cdot\mid x,u)$ is weakly continuous in $(x,u)$. >2. The observation channel $Q(\cdot\mid x,u)$ is continuous in total variation.

\begin{proof} This proof consists of showing that for every $(\pi_{0}^{n},u_{n})\to(\pi_{0},u)$ in $\mathcal{P}(\mathbb{X})\times \mathbb{U}$ we have $$\sup_{\lVert f \rVert _{BL}\le 1}\left| \int\limits _{\mathcal{P}(\mathbb{X})}f(\pi_{1}) \, \eta(d\pi_{1}\mid \pi_{0}^{n},u_{n})-\int\limits _{\mathcal{P}(\mathbb{X})}f(\pi_{1}) \, \eta(d\pi_{1}\mid \pi_{0},u) \right| \to{0},$$where we equip $\mathcal{P}(\mathbb{X})$ with the Metric $\rho$ to define the Bounded-Lipschitz Norm $\lVert f \rVert_{BL}$ of any Borel function $f:\mathcal{P}(\mathbb{X})\to \mathbb{R}$. We can equivalently write this as $$\sup_{\lVert f \rVert _{BL}\le 1}\left| \int\limits _{\mathbb{Y}}f(\pi_{1}(\pi_{0}^{n},u_{n},y_{1})) \, P(dy_{1}\mid \pi_{0}^{n},u_{n}) -\int\limits _{\mathbb{Y}}f(\pi_{1}(\pi_{0},u,y_{1})) \, P(dy_{1}\mid \pi_{0},u) \right| \to0$$we can then upper bound the above term: $$\begin{align*} &\sup_{\lVert f \rVert _{BL}\le 1}\left| \int\limits _{\mathbb{Y}}f(\pi_{1}(\pi_{0}^{n},u_{n},y_{1})) \, P(dy_{1}\mid \pi_{0}^{n},u_{n}) -\int\limits _{\mathbb{Y}}f(\pi_{1}(\pi_{0},u,y_{1})) \, P(dy_{1}\mid \pi_{0},u) \right|\\ &\le \sup_{\lVert f \rVert _{BL}\le 1}\left| \int\limits _{\mathbb{Y}}f(\pi_{1}(\pi_{0}^{n},u_{n},y_{1})) \, P(dy_{1}\mid \pi_{0}^{n},u_{n}) -\int\limits _{\mathbb{Y}}f(\pi_{1}(\pi_{0}^{n},u,y_{1})) \, P(dy_{1}\mid \pi_{0},u) \right|\\ &\quad+ \sup_{\lVert f \rVert _{BL}\le 1} \int\limits _{\mathbb{Y}}\left|f(\pi_{1}(\pi_{0}^{n},u_{n},y_{1})) - f(\pi_{1}(\pi_{0},u,y_{1})) \right| \,P(dy_{1}\mid \pi_{0},u) \\ &\le \lVert P(\cdot\mid \pi_{0}^{n},u_{n})-P(\cdot\mid \pi_{0},u) \rVert _{TV}+\sup_{\lVert f \rVert _{BL}\le 1} \int\limits _{\mathbb{Y}}\left|f(\pi_{1}(\pi_{0}^{n},u_{n},y_{1})) - f(\pi_{1}(\pi_{0},u,y_{1})) \right| \,P(dy_{1}\mid \pi_{0},u)\tag{8}\\ \end{align*}$$where in $(8)$ we use the fact that $\lVert f \rVert_{\infty}\le\lVert f \rVert_{BL}\le 1$.
To prove $(8)\to0$ it is sufficient to prove:

1. $P(dy_{1}\mid \pi_{0},u_{0})$ is Continuous in Total Variation
2. $$(\pi_{0}^{n},u_{n})\to(\pi_{0},u)\implies\int\limits _{\mathbb{Y}}\rho(\pi_{1}(\pi_{0}^{n},u_{n}y_{1}),\pi_{1}(\pi_{0},u,y_{1})) \, P(dy_{1}\mid \pi_{0},u) \to 0\tag{9}$$since $(\text{second term of }8)\le(9)$. >[!claim] >$P(dy_{1}\mid \pi_{0},u_{0})$ is Continuous in Total Variation

Let $(\pi_{0}^{n},u_{n})\to(\pi_{0},u)$. Then $$\begin{align*} &\sup_{A\in \mathcal{B}(\mathbb{Y})}\left| P(A\mid \pi_{0}^{n},u_{n})-P(A\mid \pi_{0},u) \right| \\ &=\sup_{A\in \mathcal{B}(\mathbb{Y})}\left| \int\limits _{\mathbb{X}}Q(A\mid x_{1},u_{n}) \, \mathcal{T}(dx_{1}\mid \pi_{0}^{n},u_{n})-\int\limits _{\mathbb{X}}Q(A\mid x_{1},u) \, \mathcal{T}(dx_{1}\mid z_{0},u) \right| , \end{align*}$$where $$\mathcal{T}(dx_{1}\mid \pi_{0}^{n},u_{n}):=\int\limits _{\mathbb{X}}\mathcal{T}(dx_{1}\mid x_{0},u_{n}) \, \pi_{0}^{n}(dx_{0}) .$$Note that, by , we can show that $\mathcal{T}(dx_{1}\mid \pi_{0}^{n},u_{n})\to \mathcal{T}(dx_{1}\mid \pi_{0},u)$ weakly.

Indeed, let $g\in C_{b}(\mathbb{X})$, then define $r_{n}(x_{0})=\int\limits _{\mathbb{X}}g(x_{1}) \, \mathcal{T}(dx_{1}\mid x_{0},u_{n})$ and $r(x_{0})=\int\limits _{\mathbb{X}}g(x_{1}) \, \mathcal{T}(dx_{1}\mid x_{0},u)$. Since $\mathcal{T}(dx_{1}\mid x_{0},u)$ is Weak Feller, we have $r_{n}(x_{0})\to r(x_{0})$ when $x_{0}^{n}\to x_{0}$. Hence, by we have that $$\lim_{ n \to \infty } \left| \int\limits _{\mathbb{X}}r_{n}(x_{0}) \, \pi _{0}^{n}(dx_{0})-\int\limits _{\mathbb{X}}r(x_{0}) \, \pi_{0}(dx_{0}) \right|$$Hence $\mathcal{T}(dx_{1}\mid \pi_{0}^{n},u_{n})\to \mathcal{T}(dx_{1}\mid \pi_{0},u)$ weakly. Moreover the families of functions $\{ Q(A\mid \cdot,u_{n}) \}_{n\ge 1,A\in \mathcal{B}(\mathbb{Y})}$ and $\{ Q(A\mid \cdot,u) \}_{A\in \mathcal{B}(\mathbb{Y})}$ satisfy the conditions of as $Q$ is Continuous in Total Variation. Therefore yields $$\lim_{ n \to \infty } \sup_{A\in \mathcal{B}(\mathbb{Y})}\left| \int\limits _{\mathbb{X}}Q(A\mid x_{1},u_{n}) \, \mathcal{T}(dx_{1}\mid \pi_{0}^{n},u_{n}) -\int\limits _{\mathbb{X}}Q(A\mid x_{1},u) \, \mathcal{T}(dx_{1}\mid \pi_{0},u) \right| =0$$Thus, $P(dy_{1}\mid \pi_{0},u)$ is Continuous in Total Variation.

\end{proof}

Comparison of Conditions on Observation Channels

\begin{proof} We begin by fixing any $(\pi,u)\in\mathcal{P}(\mathbb{X})\times \mathbb{U}$. >[!clm] >$$Q(dy\mid x,u)\ll P(dy\mid \pi,u),\,\mathcal{T}(\cdot\mid \pi,u)\text{-a.s.}$$

Note that (by definition of Absolute Continuity) $Q(dy\mid x,u)\ll P(dy\mid \pi,u)$ if and only if $$\forall\epsilon>0,\exists\delta>0:P(A\mid \pi,u)<\delta\implies Q(A\mid x,u)<\epsilon$$For each $n\ge 1$ let $K_{n}\subset\mathbb{X}$ be Compact such that $$\mathcal{T}(K_{n}\mid \pi,u)>1-\frac{1}{3n}$$which can be done due to Prokhorov (i.e. since $\mathcal{T}$ is Weak Feller then it is necessarily Relatively Compact hence it is also Tight.

As $Q(dy\mid x,u)$ is continuous in total variation, the Image of $K_{n}\times \{ u \}$ under $Q(dy\mid x,u)$ is compact in $\mathcal{P}(\mathbb{Y})$ (this is by Heine-Borel Theorem). Hence, there exists $\{ \nu_{1},\dots,\nu_{l} \}\subset \mathcal{P}(\mathbb{Y})$ such that $$\max_{x \in K_{n}}\min_{i=1,\dots,l}\lVert Q(\cdot\mid x,u)-\nu_{i} \rVert _{TV}< \frac{1}{3n}$$ Define the following Stochastic Kernel: $$\nu_{n}(\cdot\mid x,u)=\underset{ \nu_{i} }{ \arg\min }\lVert Q(\cdot\mid x,u)-\nu_{i} \rVert _{TV}$$Then, we define $$P_{n}(\cdot\mid \pi,u)=\int\limits _{\mathbb{X}}\nu_{n}(\cdot\mid x,u) \, \mathcal{T}(dx\mid \pi,u).$$ One can prove that $\lVert P(\cdot\mid \pi,u)-P_{n}(\cdot\mid \pi,u) \rVert_{TV}< \frac{1}{n}.$ Moreover, since $P_{n}(\cdot\mid \pi,u)$ is a mixture of finite Probability Measures $\{ \nu_{1},\dots,\nu_{l} \}$, we have that $\nu_{n}(\cdot\mid x,u)\ll P_{n}(\cdot\mid \pi,u)$, $\forall x \in C_{n}$, where $\mathcal{T}(C_{n}\mid \pi,u)=1$. Let $C=\bigcap_{n}C_{n}$, and so, $\mathcal{T}(C\mid \pi,u)=1$. >[!clm] >$$x \in C\implies Q(dy\mid x,u)\ll P(dy\mid \pi,u)$$

To prove this claim we fix any $\epsilon>0$ and choose $n\ge 1$ s.t. $\epsilon> \frac{2}{3n}$. Then, $\exists\delta>0$ s.t. $\nu_{n}(A\mid x,u)< \frac{\epsilon}{2}$ whenever $P_{n}(A\mid \pi,u)<\delta$. This gives us that $Q(A\mid x,u)<\epsilon$ whenever $P(A\mid \pi,u)<\delta+ \frac{1}{n}$. Hence $Q(dy\mid x,u)\ll P(dy\mid \pi,u)$. \end{proof}