# Markov Decision Processes
with Noisy State Observation

Amirhossein Afsharrad, Sanjay Lall
Department of Electrical Engineering
Stanford University
Stanford, CA
{afsharrad<EMAIL_ADDRESS>
###### Abstract

This paper addresses the challenge of a particular class of noisy state
observations in Markov Decision Processes (MDPs), a common issue in various
real-world applications. We focus on modeling this uncertainty through a
confusion matrix that captures the probabilities of misidentifying the true
state. Our primary goal is to estimate the inherent measurement noise, and to
this end, we propose two novel algorithmic approaches. The first, the method
of second-order repetitive actions, is designed for efficient noise estimation
within a finite time window, providing identifiable conditions for system
analysis. The second approach comprises a family of Bayesian algorithms, which
we thoroughly analyze and compare in terms of performance and limitations. We
substantiate our theoretical findings with simulations, demonstrating the
effectiveness of our methods in different scenarios, particularly highlighting
their behavior in environments with varying stationary distributions. Our work
advances the understanding of reinforcement learning in noisy environments,
offering robust techniques for more accurate state estimation in MDPs.

_K_ eywords MDP, POMDP, reinforcement learning, Bayesian algorithms, state
estimation, system identification

##  1 Introduction

In the landscape of artificial intelligence, Markov Decision Processes (MDPs)
are pivotal in reinforcement learning, providing a structured approach to
tackle sequential decision-making problems under uncertainty [1, 2]. Their
applicability spans a diverse range of fields, including robotics [3, 4],
financial decision-making [5, 6], autonomous navigation [7, 8], healthcare
management [9, 10], supply chain optimization [11, 12], and energy systems
management [13, 14]. MDPs enable the optimization of actions based on
probabilistic state transitions, which is fundamental in these domains.
However, a critical challenge emerges when these theoretical models are
applied to real-world scenarios characterized by noisy observations and
measurements. This is a common occurrence in environments ranging from sensor
data in autonomous vehicles [15] to fluctuating markets in finance [16], from
patient data in healthcare [17] to demand variability in supply chains [18],
and from renewable energy predictions to grid stability in energy systems
[19]. Such inherent uncertainties in observations necessitate sophisticated
methodologies for accurate state estimation, which is essential for making
reliable and informed decisions. Our work addresses this challenge, proposing
advanced techniques to enhance the robustness and effectiveness of MDP-based
reinforcement learning models in the face of noise in state observations.

In this work, we address a particular type of noisy observations by modeling
the uncertainty through a confusion matrix, which represents the probabilities
of observing states incorrectly. Our approach adopts a system identification
perspective, aiming to estimate the inherent measurement noise characterized
by this confusion matrix. The primary contribution of this paper lies in
proposing two categories of algorithms designed to estimate these noise
components, accompanied by a set of conditions and performance guarantees.
Initially, we introduce an innovative method, the method of second-order
repetitive actions. This approach efficiently estimates noise components
within a finite time window, and we specify the conditions for the reliable
identification of the system’s noise characteristics. Subsequently, we
introduce a family of Bayesian algorithms, providing a comparative analysis of
their performance and exploring their potential limitations. Through these
contributions, we aim to enhance the robustness and accuracy of MDPs in
environments with observational noise.

##  2 Problem Formulation

We consider a standard reinforcement learning problem defined by a Markov
Decision Process (MDP). The MDP is characterized by a finite set of states,
denoted as $S=\\{1,\cdots,n\\}$ where $n$ is the number of states, and a
finite set of actions, represented as $A=\\{1,\cdots,m\\}$ with $m$ being the
number of actions. Denoting ${\mathcal{P}}_{n}$ as the set of all $n\times n$
transition probability matrices, the transition probability function
$P:A\to{\mathcal{P}}_{n}$ maps actions to $n\times n$ transition probability
matrices, defined as
$P(a)_{ij}=\mathop{\mathbb{P}}\left[s_{t+1}=j|s_{t}=i,a_{t}=a\right]$, where
$t\in{\mathbb{N}}$ is the time-step, and $a_{t}$ is the action at time $t$.
The reward function $R:S\times A\times{\mathbb{R}}\to{\mathbb{R}}$ determines
the immediate reward, $r_{t}=R(s_{t},a_{t},\eta_{t})$, with $r_{t}$ as the
observed reward at time $t$ and $\eta_{t}$ as a noise variable, incorporated
in $R$ to capture stochastic dependencies of the reward on state-action pairs.

This study focuses on the challenge of noisy state observation in MDPs.
Considering the finite nature of the state space, we explore state observation
noise by defining the probability of observing a state ${\tilde{s}}\in S$
different from the actual state $s\in S$. In this context, ${\tilde{s}}$ and
$s$ represent the observed state and the true state, respectively. This noise
is characterized by the state observation confusion matrix
$C\in{\mathbb{R}}^{n\times n}$, which specifies the probabilities of observing
${\tilde{s}}$ when the actual state is $s$, expressed as
$C_{ij}=\mathop{\mathbb{P}}\left[{\tilde{s}}_{t}=j|s_{t}=i\right]$. This
matrix is assumed to be time-independent, indicating consistent observation
noise characteristics across states. While $S$, $A$, and $P$ are known, the
reward function $R$ and the confusion matrix $C$ are unknown. Our objective is
to estimate $C$, and given our focus on estimating $C$ in settings with absent
or sparse rewards, we do not assume a specific reward model, ensuring that our
algorithms are not dependent on reward dynamics.

##  3 Main Results

###  3.1 The Method of Second-Order Repetitive Actions

######  Theorem 1.

Consider an MDP with noisy observations and observation confusion matrix $C$.
Define $Q^{a}_{t}\in{\mathbb{R}}^{n\times n}$ as the observed state transition
matrix at time $t$, where

$Q^{a}_{t,ij}=\mathop{\mathbb{P}}\left[{\tilde{s}}_{t+1}=j|{\tilde{s}}_{t}=i,a_{t}=a\right].$

Let $\pi_{t}\in{\mathbb{R}}^{n}$ represent the probability distribution over
the true state at time $t$, expressed as

$\pi_{t}=\mathop{\mathbb{P}}\left[s_{t}=i\right].$

Then, the following relationship holds:

$\mathop{\rm diag}(C^{\top}\pi_{t})Q^{a}_{t}=C^{\top}\mathop{\rm
diag}(\pi_{t})P(a)C.$ (1)

Proof provided in Section 4.1.

Our main goal is to deduce $C$ from $Q^{a}_{t}$. An empirical estimate
$\hat{Q}^{a}_{t}$ enables us to solve (1) for $C$. The primary challenge is
the time-dependent nature of $Q^{a}_{t}$, as single observations per time-step
are insufficient for reliable estimation of ${\hat{Q}}^{a}_{t}$.

To address this, we note that the time dependence in $Q^{a}_{t}$ is solely
through $\pi_{t}$. Stabilizing $\pi_{t}$ over a period allows $Q^{a}_{t}$ to
become time-independent, enabling us to empirically estimate $Q^{a}_{t}$ with
${\hat{Q}}^{a}$ and then solve (1) for $C$. We achieve this by repeatedly
selecting an action $a\in A$ for a duration, leading $\pi_{t}$ to converge to
the stationary distribution $\pi^{a}$ of $P(a)$, under the assumption that the
Markov process for $P(a)$ is irreducible and aperiodic. The observed state
transitions then adhere to a constant matrix $Q^{a}$, defined by

$\mathop{\rm diag}(C^{\top}\pi^{a})Q^{a}=C^{\top}\mathop{\rm
diag}(\pi^{a})P(a)C.$ (2)

This allows us to empirically determine ${\hat{Q}}^{a}$ and estimate $C$ by
minimizing the loss function ${\mathcal{L}}_{a}$ defined as

${\mathcal{L}}_{a}(C)=\left\|C^{\top}\mathop{\rm
diag}(\pi^{a})P(a)C-\mathop{\rm
diag}\left(C^{\top}\pi^{a}\right){\hat{Q}}^{a}\right\|^{2}.$ (3)

However, this approach can lead to non-unique solutions for $C$, as
demonstrated with an example for $n=2$ later. Different $C$ matrices can
produce the same $Q^{a}$, making it impossible to uniquely determine $C$ from
(3), even with the perfect esitmate ${\hat{Q}}^{a}=Q^{a}$.

To overcome this, we apply the method across various actions. While each
action might yield multiple solutions, the common solution across different
actions may uniquely identify the actual $C$. We select a subset $A_{0}$ of
$A$ with $|A_{0}|=N$, and for each action in $A_{0}$, repeated for a duration
$T$, we estimate ${\hat{Q}}^{a}$ and solve for $C$ using:

${\hat{C}}=\mathop{\rm argmin}_{C}\frac{1}{N}\sum_{a\in
A_{0}}\left\|C^{\top}\mathop{\rm diag}(\pi^{a})P(a)C-\mathop{\rm
diag}\left(C^{\top}\pi^{a}\right){\hat{Q}}^{a}\right\|^{2}.$ (4)

However, even with multiple actions from $A_{0}$, (4) may have multiple
solutions. As an example, consider two actions $a,a^{\prime}$ with the
following probabilities

$P(a)=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix},\quad
Q^{a}=\begin{bmatrix}0.45&0.55\\\ 0.825&0.175\end{bmatrix},\quad
P(a^{\prime})=\begin{bmatrix}0.3&0.7\\\ 0.7&0.3\end{bmatrix},\quad
Q^{a^{\prime}}=\begin{bmatrix}0.54&0.46\\\ 0.69&0.31\end{bmatrix}.$

Solving (2) for both actions, we find two possible solutions for $C$ given by

$C_{1}=\begin{bmatrix}0.9&0.1\\\ 0.3&0.7\end{bmatrix},\quad
C_{2}=\begin{bmatrix}0.3&0.7\\\ 0.9&0.1\end{bmatrix},$

suggesting that both $C_{1}$ and $C_{2}$ are solutions of (4), illustrating
the non-uniqueness issue. This example illustrates that multiple actions do
not guarantee a unique solution for $C$. Theorem 2 addresses this issue by
providing a necessary and sufficient condition for uniqueness in the $n=2$
case.

######  Theorem 2.

For $n=2$, a unique solution for

$C^{\top}\mathop{\rm diag}(\pi^{a})P(a)C=\mathop{\rm
diag}\left(C^{\top}\pi^{a}\right)Q^{a},\quad a\in\\{a_{1},a_{2}\\}$ (5)

exists iff the stationary distributions of $P(a_{1})$ and $P(a_{2})$ are
distinct, i.e., $\pi^{a_{1}}\neq\pi^{a_{2}}$.

Proof in Section 4.2. Theorem 3 generalizes this condition for
$n\in{\mathbb{N}}$:

######  Theorem 3.

Let $B$ be any non-empty strict subset of
${\mathbb{N}}_{n}=\\{1,2,\cdots,n\\}$, and define
${\mathcal{B}}=\\{B\subset{\mathbb{N}}_{n}|B\neq\emptyset,{\mathbb{N}}_{n}\\}$
as the set of all such subsets. Then, if $C$ is symmetric, the set of
equations

$C^{\top}\mathop{\rm diag}(\pi^{a})P(a)C=\mathop{\rm
diag}\left(C^{\top}\pi^{a}\right)Q^{a},\quad a\in A_{0}$ (6)

has a unique solution if for every $B\in{\mathcal{B}}$, there exist two
actions $a,a^{\prime}\in A_{0}$ such that

$\sum_{i\in B}\pi^{a}_{i}\neq\sum_{i\in B}\pi^{a^{\prime}}_{i}.$ (7)

Proof in Section 4.3. Note that Theorem 3’s uniqueness condition, while
sufficient, is not strictly necessary and can be relaxed in various ways. The
assumption of a symmetric $C$ simplifies the proof but is not essential.

To conclude, the second-order repetitive actions algorithm, involving
repetitive actions and recording the last two observed states, estimates
$Q^{a}$ and $C$. It is called a second-order algorithm as it involves
recording only the last two observations and results in a second order
equation in $C$. Theorems 2 and 3 ensure solution convergence to the true $C$.
The next section introduces other methods for estimating the confusion matrix.

###  3.2 The Bayesian Method

In this section, we apply a Bayesian approach to estimate the confusion matrix
$C$. This method involves maintaining two probability distributions: one over
the unknown parameters characterized by $C$, and the other over the current
state of the system given past observations. We introduce two variants of the
Bayesian method and analyze their performances in Section 5.

####  3.2.1 The First-Order Bayesian Algorithm

The belief state $b_{t}\in{\mathbb{R}}^{n}$ is defined as

$b_{t,i}=\mathop{\mathbb{P}}\left[s_{t}=i|{\tilde{s}}_{t},a_{t-1},\cdots,a_{1},{\tilde{s}}_{0}\right],$
(8)

and the probability density function $p_{t}:{\mathbb{R}}^{n\times
n}\to{\mathbb{R}}^{+}$ gives the probability density at $C$ at time $t$
conditioned on past observations and actions, i.e.,

$p_{t}(C_{0})=\mathop{\mathbb{P}}\left[C=C_{0}|{\tilde{s}}_{t},a_{t-1},\cdots,a_{1},{\tilde{s}}_{0}\right].$
(9)

######  Theorem 4.

Given a history of observations and actions, the belief state $b_{t}$, and the
probability density function $p_{t}$ at $C$, the update rules are as follows:

  1. (a)

The update rule for the probability density function of $C$:

$\displaystyle p_{t+1}(C)$
$\displaystyle=\frac{b_{t}^{\top}PC_{{\tilde{s}}_{t+1}}}{\int_{C^{\prime}}b_{t}^{\top}PC^{\prime}_{{\tilde{s}}_{t+1}}p_{t}(C^{\prime})\mathrm{d}C^{\prime}}p_{t}(C),$
(10)

where $C_{{\tilde{s}}_{t+1}}$ is the ${\tilde{s}}_{t+1}$th column of $C$.

  2. (b)

The belief state update rule:

$b_{t+1,i}=\int_{C}\frac{C_{i,{\tilde{s}}_{t+1}}\sum_{j}P(a_{t})_{ji}b_{t,j}}{\sum_{k}C_{k,{\tilde{s}}_{t+1}}\sum_{j}P(a_{t})_{jk}b_{t,j}}p_{t+1}(C)\mathrm{d}C$
(11)

####  3.2.2 The Second-Order Bayesian Algorithm

The second-order Bayesian algorithm incorporates the last two observed states
into the probability computation. It requires a modified belief state, denoted
by ${\tilde{b}}_{t}$, defined as

${\tilde{b}}_{t,i}=\mathop{\mathbb{P}}\left[s_{t}=i|{\tilde{s}}_{t-1},a_{t-2},\cdots,a_{1},{\tilde{s}}_{0}\right].$

######  Theorem 5.

Given a history of observations and actions, the current belief state
${\tilde{b}}_{t}$, and the probability density function $p_{t}$ at $C$, the
update rules are:

  1. (a)

The update rule for the probability density function of $C$:

$\displaystyle Q(C)$ $\displaystyle=\mathop{\rm
diag}\left(C^{\top}{\tilde{b}}_{t}\right)^{-1}C^{\top}\mathop{\rm
diag}({\tilde{b}}_{t})P(a_{t})C$ (12) $\displaystyle p_{t+1}(C)$
$\displaystyle=\frac{Q(C)_{{\tilde{s}}_{t},{\tilde{s}}_{t+1}}}{\int_{C^{\prime}}Q(C^{\prime})_{{\tilde{s}}_{t},{\tilde{s}}_{t+1}}p_{t}(C^{\prime})\mathrm{d}C^{\prime}}p_{t}(C).$
(13)

  2. (b)

The belief state update rule:

${\tilde{b}}_{t+1,i}=\int_{C}\frac{\sum_{j}P(a_{t})_{ji}C_{j,{\tilde{s}}_{t}}{\tilde{b}}_{t,j}}{\sum_{j}C_{j,{\tilde{s}}_{t}}{\tilde{b}}_{t,j}}p_{t+1}(C)\mathrm{d}C$
(14)

The proof of this theorem, similar to that of Theorems 1 and 4, is omitted for
brevity. Theorems 4 and 5 provide methods for maintaining and updating
probability distributions over $C$ and the true state. Their performance will
be compared in Section 5. The Bayesian approach offers flexibility in action
choice, unlike the second-order repetitive actions method in Section 3.1 that
requires repeating the same action. However, maintaining a probability
distribution over $n\times n$ matrices may be computationally intensive for
large $n$.

##  4 Proofs

###  4.1 Proof of Theorem 1

We derive the relationship between the matrices by conditioning over the
states $s_{t}$ and $s_{t+1}$. For an arbitrary element of $Q^{a}_{t}$, we have

$\displaystyle Q^{a}_{t,ij}$
$\displaystyle=\mathop{\mathbb{P}}\left[{\tilde{s}}_{t+1}=j|{\tilde{s}}_{t}=i,a_{t}=a\right]$
$\displaystyle=\sum_{k=1}^{n}\mathop{\mathbb{P}}\left[s_{t+1}=k|{\tilde{s}}_{t}=i,a_{t}=a\right]\underbrace{\mathop{\mathbb{P}}\left[{\tilde{s}}_{t+1}=j|{\tilde{s}}_{t}=i,s_{t+1}=k,a_{t}=a\right]}_{C_{kj}}$
$\displaystyle=\sum_{k=1}^{n}C_{kj}\sum_{\ell=1}^{n}\mathop{\mathbb{P}}\left[s_{t}=\ell|{\tilde{s}}_{t}=i,a_{t}=a\right]\underbrace{\mathop{\mathbb{P}}\left[s_{t+1}=k|{\tilde{s}}_{t}=i,s_{t}=\ell,a_{t}=a\right]}_{P(a)_{\ell
k}}$ $\displaystyle=\sum_{k=1}^{n}C_{kj}\sum_{\ell=1}^{n}P(a)_{\ell
k}\frac{\mathop{\mathbb{P}}[s_{t}=\ell|a_{t}=a]\mathop{\mathbb{P}}\left[{\tilde{s}}_{t}=i|s_{t}=\ell,a_{t}=a\right]}{\sum_{\ell^{\prime}=1}^{n}\mathop{\mathbb{P}}[s_{t}=\ell^{\prime}|a_{t}=a]{\mathop{\mathbb{P}}\left[{\tilde{s}}_{t}=i|s_{t}=\ell^{\prime},a_{t}=a\right]}}$
$\displaystyle=\sum_{k=1}^{n}C_{kj}\sum_{\ell=1}^{n}P(a)_{\ell
k}\frac{\mathop{\mathbb{P}}[s_{t}=\ell]\mathop{\mathbb{P}}\left[{\tilde{s}}_{t}=i|s_{t}=\ell\right]}{\sum_{\ell^{\prime}=1}^{n}\mathop{\mathbb{P}}[s_{t}=\ell^{\prime}]{\mathop{\mathbb{P}}\left[{\tilde{s}}_{t}=i|s_{t}=\ell^{\prime}\right]}}$
$\displaystyle=\frac{1}{\sum_{\ell^{\prime}=1}^{n}\pi_{t,\ell^{\prime}}C_{\ell^{\prime}i}}\sum_{k=1}^{n}\sum_{\ell=1}^{n}C_{kj}P(a)_{\ell
k}\pi_{t,\ell}C_{\ell i}.$

Multiplying both sides by
$\sum_{\ell^{\prime}=1}^{n}\pi_{t,\ell^{\prime}}C_{\ell^{\prime}i}$ and
expressing in matrix form, we obtain $\mathop{\rm
diag}\left(C^{\top}\pi_{t}\right)Q^{a}_{t}=C^{\top}\mathop{\rm
diag}(\pi_{t})P(a)C$, concluding the proof.

###  4.2 Proof of Theorem 2

Consider

$C=\begin{bmatrix}c&1-c\\\ d&1-d\end{bmatrix},\quad
P(a)=\begin{bmatrix}p&1-p\\\
p^{\prime}&1-p^{\prime}\end{bmatrix},\quad\pi^{a}=\begin{bmatrix}\alpha\\\
1-\alpha\end{bmatrix},$

where $C$ is the confusion matrix, $P(a)$ is the state transition probability
matrix for action $a$, and $\pi^{a}$ is its stationary distribution. Given
$P(a)^{\top}\pi^{a}=\pi^{a}$, we can solve for $p^{\prime}$ in terms of
$\alpha$ and $p$, and rewrite $P(a)$ as

$P(a)=\begin{bmatrix}p&1-p\\\
\frac{\alpha}{1-\alpha}(1-p)&1-\frac{\alpha}{1-\alpha}(1-p)\end{bmatrix}.$

We have $Q^{a}=\mathop{\rm diag}(C^{\top}\pi^{a})^{-1}C^{\top}\mathop{\rm
diag}(\pi^{a})P(a)C$. We are interested in solutions to

$X^{\top}\mathop{\rm diag}(\pi^{a})P(a)X=\mathop{\rm
diag}\left(X^{\top}\pi^{a}\right)Q^{a},$ (15)

where $X$ is the unknown matrix. Representing $X$ as $\begin{bmatrix}x&1-x\\\
y&1-y\end{bmatrix}$, (15) becomes a system of two quadratic equations in
$x,y$. Geometrically, this equates to finding the intersection points of two
ellipsoids in ${\mathbb{R}}^{2}$, each intersection corresponding to a
solution $X$. Let these ellipsoids be represented as

$\begin{cases}A_{xx}x^{2}+A_{yy}y^{2}+A_{xy}xy+A_{x}x+A_{y}y+A_{0}=0\\\
B_{xx}x^{2}+B_{yy}y^{2}+B_{xy}xy+B_{x}x+B_{y}y+B_{0}=0,\end{cases}$ (16)

with coefficients determined in terms of $\alpha,p,c,d$ from (15). Solving the
first ellipsoid equation for $x^{2}$ and substituting it into the second
results in an equation of the form $C_{x}x+C_{y}y+C_{0}=0$. This simplifies
the problem to finding intersections of a line and an ellipsoid, implying at
most two solutions. The intersection points are

$\begin{cases}(x_{1},y_{1})=(c,d)\\\ (x_{2},y_{2})=(2d-c+2\alpha c-2\alpha
d,d+2\alpha c-2\alpha d).\end{cases}$ (17)

These solutions are independent of $p$, depending only on $\pi^{a}$. Thus, if
$P(a_{1})$ and $P(a_{2})$ have the same stationary distributions, both
corresponding confusion matrices from (17) satisfy (5), indicating non-
uniqueness. For different stationary distributions characterized by $\alpha$
and $\alpha^{\prime}$, non-uniqueness implies

$d+2\alpha c-2\alpha
d=d+2\alpha^{\prime}c-2\alpha^{\prime}d\Rightarrow\alpha=\alpha^{\prime}\text{
or }c=d.$

Since $\alpha\neq\alpha^{\prime}$ by assumption, $c=d$ must hold. However, if
$c=d$, then $(x_{1},y_{1})=(x_{2},y_{2})=(c,d)$, leading to unique solutions.
Thus, different stationary distributions of $P(a_{1})$ and $P(a_{2})$ are
necessary and sufficient for the uniqueness of the solution of (5), concluding
the proof.

###  4.3 Proof of Theorem 3

To establish a sufficient condition for the uniqueness of the solution of (6),
we leverage the result of Theorem 2. We consider an MDP with $n$ states and
partition these states into two superstates, ${\bar{s}}_{1}$ and
${\bar{s}}_{2}$. Without loss of generality, let
${\bar{s}}_{1}=\\{s_{1},\cdots,s_{k}\\}$ and
${\bar{s}}_{2}=\\{s_{k+1},\cdots,s_{n}\\}$. The stationary distribution and
confusion matrix for this partitioned MDP are given by:

${\bar{\pi}}=\begin{bmatrix}\pi_{1}+\cdots+\pi_{k}\\\
\pi_{k+1}+\cdots+\pi_{n}\end{bmatrix},\quad{\bar{C}}=\begin{bmatrix}{\bar{C}}_{11}&1-{\bar{C}}_{11}\\\
1-{\bar{C}}_{22}&{\bar{C}}_{22}\end{bmatrix},$ (18)

where

${\bar{C}}_{11}=\sum_{i=1}^{k}\frac{\pi_{i}\sum_{j=1}^{k}C_{ij}}{\sum_{j=1}^{k}\pi_{j}},\quad{\bar{C}}_{22}=\sum_{i=k+1}^{n}\frac{\pi_{i}\sum_{j=k+1}^{n}C_{ij}}{\sum_{j=k+1}^{n}\pi_{j}}.$
(19)

Examples of such partitioning are shown in Figures 2 and 2, representing the
state observation confusion.

$s_{1}$$s_{2}$$s_{3}$$s_{4}$$1-{\bar{C}}_{22}$$1-{\bar{C}}_{11}$${\bar{C}}_{11}=C_{11}$${\bar{C}}_{11}=\frac{\pi_{2}(C_{22}+C_{23}+C_{24})}{\pi_{2}+\pi_{3}+\pi_{4}}+\cdots+\frac{\pi_{4}(C_{42}+C_{43}+C_{44})}{\pi_{2}+\pi_{3}+\pi_{4}}$
Figure 1: Partitioning with ${\bar{s}}_{1}=\\{s_{1}\\}$

$s_{1}$$s_{2}$$s_{3}$$s_{4}$$1-{\bar{C}}_{11}$$1-{\bar{C}}_{22}$${\bar{C}}_{11}=\frac{\pi_{1}(C_{11}+C_{12})}{\pi_{1}+\pi_{2}}+\frac{\pi_{2}(C_{21}+C_{22})}{\pi_{1}+\pi_{2}}$${\bar{C}}_{22}=\frac{\pi_{3}(C_{33}+C_{34})}{\pi_{3}+\pi_{4}}+\frac{\pi_{4}(C_{43}+C_{44})}{\pi_{3}+\pi_{4}}$
Figure 2: Partitioning with ${\bar{s}}_{1}=\\{s_{1},s_{2}\\}$

The assumption in (7) ensures that for any partitioning, the stationary
distributions of the two-state MDP are different for some actions
$a,a^{\prime}$. This, as a result of Theorem 2, implies that ${\bar{C}}_{11}$
and ${\bar{C}}_{22}$ can be uniquely determined for any partitioning. To
uniquely determine $C$, we first find all diagonal elements $C_{ii}$ using the
partitioning
${\bar{s}}_{1}=\\{s_{i}\\},{\bar{s}}_{2}=\\{s_{1},\cdots,s_{n}\\}\setminus\\{s_{i}\\}$.
To find an arbitrary $C_{ij}$, we use the partitioning
${\bar{s}}_{1}=\\{s_{i},s_{j}\\},{\bar{s}}_{2}=\\{s_{1},\cdots,s_{n}\\}\setminus\\{s_{i},s_{j}\\}$.
With ${\bar{C}}_{11}$ being a linear function of
$C_{ii},C_{ij},C_{ji},C_{jj}$, and knowing $C_{ii},C_{jj}$ and the symmetry of
$C$ (i.e., $C_{ij}=C_{ji}$), we can solve for $C_{ij}$. As this applies to any
element of $C$, the entire matrix $C$ can be uniquely determined. This
concludes the proof.

###  4.4 Proof of Theorem 4

The derivation of the two update rules for $p_{t}$ and $b_{t}$ are given
below.

$\displaystyle p_{t+1}(C)$
$\displaystyle=\mathop{\mathbb{P}}\left[C|{\tilde{s}}_{t+1},a_{t},\cdots,a_{1},{\tilde{s}}_{0}\right]$
$\displaystyle=\frac{\mathop{\mathbb{P}}\left[{\tilde{s}}_{t+1}|C,a_{t},{\tilde{s}}_{t},\cdots,{\tilde{s}}_{0}\right]\mathop{\mathbb{P}}\left[C|{\tilde{s}}_{t},a_{t-1},\cdots,{\tilde{s}}_{0}\right]}{\mathop{\mathbb{P}}\left[{\tilde{s}}_{t+1},a_{t},{\tilde{s}}_{t},\cdots,{\tilde{s}}_{0}\right]}$
$\displaystyle=\frac{\sum_{i}\mathop{\mathbb{P}}\left[{\tilde{s}}_{t+1}|s_{t+1}=i,C,a_{t},{\tilde{s}}_{t},\cdots,{\tilde{s}}_{0}\right]\mathop{\mathbb{P}}\left[s_{t+1}=i|C,a_{t},{\tilde{s}}_{t},\cdots,{\tilde{s}}_{0}\right]p_{t}(C)}{\mathop{\mathbb{P}}\left[{\tilde{s}}_{t+1},a_{t},{\tilde{s}}_{t},\cdots,{\tilde{s}}_{0}\right]}$
$\displaystyle=\frac{\sum_{i}C_{i,{\tilde{s}}_{t+1}}\sum_{j}\mathop{\mathbb{P}}\left[s_{t+1}=i|s_{t}=j,C,a_{t},{\tilde{s}}_{t},\cdots,{\tilde{s}}_{0}\right]\mathop{\mathbb{P}}\left[s_{t}=j|C,a_{t},{\tilde{s}}_{t},\cdots,{\tilde{s}}_{0}\right]}{\mathop{\mathbb{P}}\left[{\tilde{s}}_{t+1},a_{t},{\tilde{s}}_{t},\cdots,{\tilde{s}}_{0}\right]}p_{t}(C)$
$\displaystyle=\frac{\sum_{i}C_{i,{\tilde{s}}_{t+1}}\sum_{j}P(a_{t})_{ji}b_{t,j}}{\mathop{\mathbb{P}}\left[{\tilde{s}}_{t+1},a_{t},{\tilde{s}}_{t},\cdots,{\tilde{s}}_{0}\right]}p_{t}(C)=\frac{b_{t}^{\top}P(a_{t})C_{{\tilde{s}}_{t+1}}}{\int_{C^{\prime}}b_{t}^{\top}PC^{\prime}_{{\tilde{s}}_{t+1}}p_{t}(C^{\prime})\mathrm{d}C^{\prime}}p_{t}(C).$
$\displaystyle b_{t+1,i}$
$\displaystyle=\mathop{\mathbb{P}}\left[s_{t+1}=i|{\tilde{s}}_{t+1},a_{t},\cdots,a_{1},{\tilde{s}}_{0}\right]$
$\displaystyle=\int_{C}\mathop{\mathbb{P}}\left[s_{t+1}=i|{\tilde{s}}_{t+1},a_{t},\cdots,a_{1},{\tilde{s}}_{0},C\right]p_{t}(C)\mathrm{d}C$
$\displaystyle=\int_{C}\frac{\mathop{\mathbb{P}}\left[{\tilde{s}}_{t+1}|s_{t+1}=i,a_{t},\cdots,a_{1},{\tilde{s}}_{0}\right]\mathop{\mathbb{P}}\left[s_{t+1}=i|a_{t},{\tilde{s}}_{t},\cdots,a_{1},{\tilde{s}}_{0}\right]}{\mathop{\mathbb{P}}\left[{\tilde{s}}_{t+1},a_{t},\cdots,a_{1},{\tilde{s}}_{0}\right]}p_{t}(C)\mathrm{d}C$
$\displaystyle=\int_{C}\frac{C_{i,{\tilde{s}}_{t+1}}\sum_{j}\mathop{\mathbb{P}}\left[s_{t+1}=i|s_{t}=j,a_{t},{\tilde{s}}_{t},\cdots,a_{1},{\tilde{s}}_{0}\right]\mathop{\mathbb{P}}\left[s_{t}=j|{\tilde{s}}_{t},\cdots,a_{1},{\tilde{s}}_{0}\right]}{\mathop{\mathbb{P}}\left[{\tilde{s}}_{t+1},a_{t},\cdots,a_{1},{\tilde{s}}_{0}\right]}p_{t}(C)\mathrm{d}C$
$\displaystyle=\int_{C}\frac{C_{i,{\tilde{s}}_{t+1}}\sum_{j}P(a_{t})_{ji}b_{t,j}}{\mathop{\mathbb{P}}\left[{\tilde{s}}_{t+1},a_{t},\cdots,a_{1},{\tilde{s}}_{0}\right]}p_{t}(C)\mathrm{d}C=\int_{C}\frac{C_{i,{\tilde{s}}_{t+1}}\sum_{j}P(a_{t})_{ji}b_{t,j}}{\sum_{k}C_{k,{\tilde{s}}_{t+1}}\sum_{j}P(a_{t})_{jk}b_{t,j}}p_{t+1}(C).$

##  5 Simulations

In this section, we present simulations to demonstrate the effectiveness of
the Bayesian approach under various settings. We choose $n=2$ for
visualization purposes. The figures 6, 6, 6, and 6 depict the probability
density at

$C=\begin{bmatrix}1-\alpha&\alpha\\\ \beta&1-\beta\end{bmatrix}$

by plotting $(\alpha,\beta)$ at different time steps, with the true values
generating the observations set at $\alpha=0.4$ and $\beta=0.2$.

The figures illustrate the performance of the first-order and second-order
Bayesian methods in two scenarios: one where the transition probability
matrices for different actions have a common stationary distribution, and
another where they have distinct stationary distributions.

Figure 3: $p_{t}(\alpha,\beta)$ for first-order Bayesian method and common
stationary distributions

Figure 4: $p_{t}(\alpha,\beta)$ for first-order Bayesian method and different
stationary distributions

Figure 5: $p_{t}(\alpha,\beta)$ for second-order Bayesian method and common
stationary distributions

Figure 6: $p_{t}(\alpha,\beta)$ for second-order Bayesian method and different
stationary distributions

The results of our simulations support the theoretical insights from Theorems
2 and 3. Specifically, we observe convergence to the true values
$(\alpha,\beta)=(0.4,0.2)$ in scenarios with distinct stationary
distributions. This is in line with the theoretical predictions for scenarios
where unique solutions are expected. In contrast, in environments with common
stationary distributions, we notice that neither the first-order nor the
second-order Bayesian methods can uniquely pinpoint the correct solution. This
outcome aligns with the theoretical anticipation of non-uniqueness in such
settings. Notably, the first-order method tends to converge to a line in the
$\alpha$-$\beta$ plane, whereas the second-order method exhibits convergence
towards two potential solutions. This empirical observation is particularly
interesting as it is the same as the closed-form solution for the second
possibility outlined in (16) from the proof of Theorem 2. This outcome is
visually evident in the convergence area depicted in Figure 6, showcasing the
practical implications and validity of our theoretical findings.

##  6 Conclusion and Future Work

This paper has tackled a particular class of the significant challenge of
noisy state observations in Markov Decision Processes (MDPs) by employing a
confusion matrix to model this uncertainty. We introduced two novel algorithms
for noise estimation. The first, the method of second-order repetitive
actions, efficiently estimates the confusion matrix $C$ in a finite time
frame. Moreover, our analysis reveals that system identifiability is
contingent upon the dissimilarity of stationary distributions in action
transition probabilities. Our second approach, grounded in Bayesian methods,
focuses on maintaining and updating probability distributions over unknown
parameters and states. This method provides the flexibility to choose actions
freely, yet it faces practical computational challenges, particularly in
maintaining distributions over large $n\times n$ matrices.

Looking to the future, several avenues for research emerge from our findings.
One intriguing direction is extending our approach of second-order observation
recording to higher orders, examining its impact on system identifiability and
efficiency. Further theoretical exploration is needed to address the general
problem of system identifiability. Particularly, A key theoretical question
arises from our observation that non-identifiable systems lead to limited
solution spaces: the first-order Bayesian method reduces options to a line,
whereas the second-order method identifies two distinct solutions. Future
research could explore whether more advanced methods exist that can fully
resolve this issue, or if it can be theoretically proven that no algorithm can
surpass the efficacy of the second-order method. This could significantly
advance our understanding of system identifiability in MDPs with noisy
observations. In addition, there is substantial scope for application-oriented
research. Applying our methodologies to real-world data, exploring other
classes of noisy observations within our framework, and tailoring our
approaches to specific challenges in different applications offer practical
avenues for future exploration.

## References

  * [1] Martijn Van Otterlo and Marco Wiering.  Reinforcement learning and markov decision processes.  In Reinforcement Learning: State-of-the-Art, pages 3–42. Springer, 2012.
  * [2] Olivier Sigaud and Olivier Buffet.  Markov Decision Processes in Artificial Intelligence.  John Wiley & Sons, 2013.
  * [3] Hanna Kurniawati.  Partially observable markov decision processes and robotics.  Annual Review of Control, Robotics, and Autonomous Systems, 5:253–277, 2022.
  * [4] Tengteng Zhang and Hongwei Mo.  Reinforcement learning for robot research: A comprehensive review and open issues.  International Journal of Advanced Robotic Systems, 18(3):17298814211007305, 2021.
  * [5] Nicole Bäuerle and Ulrich Rieder.  Markov Decision Processes with Applications to Finance.  Springer Science & Business Media, 2011.
  * [6] Marek Petrik and Dharmashankar Subramanian.  An approximate solution method for large risk-averse markov decision processes.  arXiv preprint arXiv:1210.4901, 2012.
  * [7] Ken Kinjo, Eiji Uchibe, and Kenji Doya.  Evaluation of linearly solvable markov decision process with dynamic model learning in a mobile robot navigation task.  Frontiers in Neurorobotics, 7:7, 2013.
  * [8] Xinyu Zhang, Chengbo Wang, Yuanchang Liu, and Xiang Chen.  Decision-making for the autonomous navigation of maritime autonomous surface ships based on scene division and deep reinforcement learning.  Sensors, 19(18):4055, 2019.
  * [9] Casey C. Bennett and Kris Hauser.  Artificial intelligence framework for simulating clinical decision-making: A markov decision process approach.  Artificial Intelligence in Medicine, 57(1):9–19, 2013.
  * [10] Yasin Gocgun, Brian W. Bresnahan, Archis Ghate, and Martin L. Gunn.  A markov decision process approach to multi-category patient scheduling in a diagnostic facility.  Artificial Intelligence in Medicine, 53(2):73–81, 2011.
  * [11] Lukas Kemmer, Henrik von Kleist, Diego de Rochebouët, Nikolaos Tziortziotis, and Jesse Read.  Reinforcement learning for supply chain optimization.  In European Workshop on Reinforcement Learning, volume 14, 2018\.
  * [12] S. Sebnem Ahiska, Samyuktha R. Appaji, Russell E. King, and Donald P. Warsing Jr.  A markov decision process-based policy characterization approach for a stochastic inventory control problem with unreliable sourcing.  International Journal of Production Economics, 144(2):485–496, 2013\.
  * [13] Timothy M. Hansen, Edwin K. P. Chong, Siddharth Suryanarayanan, Anthony A. Maciejewski, and Howard Jay Siegel.  A partially observable markov decision process approach to residential home energy management.  IEEE Transactions on Smart Grid, 9(2):1271–1281, 2016.
  * [14] Vishnu Nanduri and Ivan Saavedra-Antolínez.  A competitive markov decision process model for the energy-water-climate change nexus.  Applied Energy, 111:186–198, 2013.
  * [15] Kichun Jo, Yongwoo Jo, Jae Kyu Suhr, Ho Gi Jung, and Myoungho Sunwoo.  Precise localization of an autonomous car based on probabilistic noise models of road surface marker features using multiple cameras.  IEEE Transactions on Intelligent Transportation Systems, 16(6):3377–3392, 2015.
  * [16] Yang Li, Wanshan Zheng, and Zibin Zheng.  Deep robust reinforcement learning for practical algorithmic trading.  IEEE Access, 7:108014–108022, 2019.
  * [17] Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin.  Reinforcement learning in healthcare: A survey.  ACM Computing Surveys (CSUR), 55(1):1–36, 2021.
  * [18] Hongzi Mao, Mohammad Alizadeh, Ishai Menache, and Srikanth Kandula.  Resource management with deep reinforcement learning.  In Proceedings of the 15th ACM Workshop on Hot Topics in Networks, pages 50–56, 2016.
  * [19] ATD Perera and Parameswaran Kamalaruban.  Applications of reinforcement learning in energy systems.  Renewable and Sustainable Energy Reviews, 137:110618, 2021.