# Measuring the State-Observation-Gap in POMDPs: An Exploration of Observation Confidence and Weighting Algorithms

Yide Yu, Yan Ma, Yue Liu, Dennis Wong, Kin Lei, José Vicente Egas-López

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

## To cite this version:

Yide Yu, Yan Ma, Yue Liu, Dennis Wong, Kin Lei, et al., Measuring the State-Observation-Gap in POMDPs: An Exploration of Observation Confidence and Weighting Algorithms. 19th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), Jun 2023, León, Spain. pp.137-148, 10.1007/978-3-031-34111-3_13. [https://inria.hal.science/hal-05449821v1](https://inria.hal.science/hal-05449821v1)

HAL Id: hal-05449821

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

Submitted on 9 Jan 2026

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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_2.png" /></figure>
<figure><img src="image_3.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Measuring the State-Observation-Gap in POMDPs: An Exploration of Observation Confidence and Weighting Algorithms

Yide Yu<fnref n="1" />(✉), Yan Ma<fnref n="1" />, Yue Liu<fnref n="1" />, Dennis Wong<fnref n="1" />, Kin Lei<fnref n="1" />, and José Vicente Egas-López<fnref n="2" />

**Abstract.** The objective of this study is to measure the discrepancy between states and observations within the context of the Partially Observable Markov Decision Process (POMDP). The gap between states and observations is formulated as a State-Observation-Gap (SOG) problem, represented by the symbol $\Delta$, where states and observations are treated as sets. The study also introduces the concept of Observation Confidence (OC) which serves as an indicator of the reliability of the observation, and it is established that there is a positive correlation between OC and $\Delta$. To calculate the cumulative entropy $\lambda$ of rewards in $\langle o, a, \cdot \rangle$, we propose two weighting algorithms, namely Universal Weighting and Specific Weighting. Empirical and theoretical assessments carried out in the Cliff Walking environment attest to the effectiveness of both algorithms in determining $\Delta$ and OC.

**Keywords:** Partially Observable Markov Decision Process · Reinforcement Learning · Information Theory

## 1 Introduction

Partially Observable Markov Decision Process (POMDP) has gained significant attention as a research topic in recent years due to its extensive applications in various fields, including Artificial Intelligence, Data Mining, and Data Analysis. In recent years, POMDPs have been applied to various domains, including robotics, autonomous driving, and swarm robotics. For instance, POMDPs have been used for planning under uncertain object compositions [1], devising behavior planning mechanisms that are cognizant of traffic mirrors [2], and modeling the interaction dynamics between human operators and unmanned aerial vehicle teams [3], among others applications.

<footnote n="1">¹ Faculty of Applied Sciences, Macao Polytechnic University, Macao SAR, China {yide.yu,yue.liu,cwong,liamli}@mpu.edu.mo, mayan@bupt.edu.cn</footnote>

<footnote n="2">² RGAI, University of Szeged, Szeged, Hungary egasj@inf.u-szeged.hu</footnote>
In practice, most real-world scenarios can be described as POMDP problems since it is often impractical to list out all possible states of a complex system. Recent research has focused on developing effective solutions for POMDP problems. For example, Chades et al. [4] introduced three methods to solve the POMDP problem: belief MDP (Markov Decision Process) [5], solution representation [6,7] and interpretation and visualization [8,9].

Nonetheless, it is worth noting that the identification of the POMDP environment cannot be achieved autonomously, as it always necessitates human judgment. Since the development of a POMDP model is heavily reliant on human experience, the model can potentially become unsafe, unpredictable, and unstable. Moreover, distinguishing between fully observable and partially observable environments can pose challenges, as demonstrated by the use of medical devices that monitor patients’ physical indicators in operating rooms. It is plausible that there exist valid indicators that cannot be observed, and their nature and quantity are currently unknown.

Similarly, the gap between the state and observation is critical in applying reinforcement learning (RL) algorithms to POMDP problems. To address this challenge, we propose the concept of Observation Confidence (OC) as a measure of the gap between the state and observation. The larger the gap between the state and observation, the lower the OC, and vice versa. We define the state-observation-gap (SOG) problem, and represent states and observations as sets with multiple dimensions to address the discrepancy between the two. We also provide an algorithm to calculate OC and demonstrate its effectiveness through experiments. Our contributions extend the definition of POMDP and provide a novel approach to addressing the SOG problem.

To the best of our knowledge, this paper represents the first effort to provide a metric that measures the gap between states and observation in the POMDP problem.

## 2 Relative Works and Preliminaries

**Definition 1.** $\mathcal{P}: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \to [0, 1]$ is a set of conditional transition probabilities between states. Formally, a POMDP is a $\gamma$-tuple $\mathcal{G} = (\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \Omega, \mathcal{O}, \gamma)$, where $\mathcal{S}$ is a finite set of states $s$, and $\mathcal{A}$ is a set of actions $a$. $\mathcal{P}: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \to [0, 1]$ is a set of conditional transition probabilities between states. $\mathcal{R}: \mathcal{S} \times \mathcal{A} \to \mathbb{R}$ is the reward function. $\Omega$ is a set of observations $o$, and $\mathcal{O}$: a set of conditional observation probabilities. $\gamma \in [0, 1)$ is a discount factor.

$\mathcal{T}$ represents the set of action-observation histories. At each timestep, the environment is in a state $s \in \mathcal{S}$. The agent then selects an action $a \in \mathcal{A}$, and the environment transitions from $s$ to $s'$ with probability $\mathcal{P}(s'|s, a)$. Subsequently, the agent observes an observation $o$ from $s'$ with probability $\mathcal{O}(o|s', a)$, and receives a reward $r$ according to the reward function $\mathcal{R}(s, a)$. This process is repeated continuously, and all interactions $(o^t, a, r_t)$ are recorded in $\mathcal{T}$. The objective is to maximize the expectation of discounted rewards: $E[\sum_{t=0}^{\infty} \gamma^t r_t]$, where $r_t$ is the reward at time $t$, and $\gamma$ is the discount factor.
There are some approaches to measure the belief of every single state on the decision chain. For instance, the belief state [5] is a well-established probability distribution that captures uncertainty over potential environmental states. The FlOw-based Recurrent BElief State model (FORBES) [10] extends this notion to continuous belief states in POMDPs, while the Moore machine with belief state mapping to an external world [11] represents an additional variation. However, this paper distinguishes itself by computing the discrepancy between state and observation in the environment, as opposed to solely characterizing the belief state or its variations.

The linear weighting algorithm has gained considerable traction in the domain of POMDPs. C. Kavaklioglu et al. [12] employ grid-based approximations and linear programming models to generate approximate policies for CPOMDPs, while Y. Yang et al. [13] address the issue of POMDP model learning for linear Gaussian systems. In addition, Optimistic Linear Support with Alpha Reuse (OLSAR) [14] computes a bound approximation of the optimal solution set for all feasible weightings of the objectives. Analogously, this paper adopts the linear weighting method to solve the SOG.

# 3 Observation Confidence

In this section, we expound on the definition of extended POMDP, OC, and SOG. Following this, we propose two weighting scheme algorithms aimed at quantifying the SOG.

## 3.1 State-Observation-Gap

The following presents an extended definition of the POMDP.

**Definition 2.** The extended POMDP is a $G_{extend} = \langle \hat{S}, \hat{\Omega} \rangle$, where $\hat{S}$ is an estimate state set and $\hat{\Omega}$ is an estimate observation set.

Set $\mathbb{D}$ is a set of dimensions, and $\mathbb{D}$ is composed of dimensions $d \in \mathbb{D}$. $\omega$ is a weight, where $\omega \in \mathbb{R}$. Then, $s_{\mathbb{D}}$ is a state represented by an infinite set of dimensions as

$$s_{\mathbb{D}} = \{\omega_n d_n \mid \omega_n \ge \omega_{n+1}, n \to \infty, \omega_n d_n \ge 0\}, s_{\mathbb{D}} \subset \mathbb{S}$$

$\hat{s}_{\mathbb{D}}$ is an estimated state represented by a finite set of dimensions as

$$\hat{s}_{\mathbb{D}} = \{\omega_m d_m \mid \omega_m \ge \omega_{m+1}, n > m, n > 0, \omega_m d_m \ge 0\}, \hat{s}_{\mathbb{D}} \subset \hat{S} \subset \mathbb{S}$$

$o_{\mathbb{D}}$ is an observation represented by a finite set of dimensions as

$$o_{\mathbb{D}} = \{\omega_k d_k \mid \omega_k \ge \omega_{k+1}, n > k, k > 0\}, o_{\mathbb{D}} \subset \Omega$$

$\hat{o}_{\mathbb{D}}$ is an estimate observation represented by a finite set of dimensions as

$$\hat{o}_{\mathbb{D}} = \{\omega_l d_l \mid \omega_l \ge \omega_{l+1}, k \ge l, l > 0, \omega_l d_l \ge 0\}, \hat{o}_{\mathbb{D}} \subset \hat{\Omega} \subseteq \Omega$$
Definition 2 relies on three implicit assumptions. Firstly, it is assumed that the dimension of state *s* is infinite, and as such, *s*<sub>∞</sub> also constitutes an infinite set. This assumption is deemed to be more realistic. Secondly, the weight *ω* of each dimension reflects its relative importance, and for any given task, not all dimensions are of equal significance. Hence, a zero bound *l* is introduced for *ω*, such that Π<sub>i=1</sub><sup>*l*</sup> *ω*<sub>*i*</sub>*d*<sub>*i*</sub> > 0 and Π<sub>i=1</sub><sup>*m*</sup> *ω*<sub>*i*</sub>*d*<sub>*i*</sub> = 0, where *m* > *i* > 0. We disregard the part of *ω* that is 0 and refer to the set comprising the remaining *ω* as the estimate state *ŝ*. Lastly, while it is not always the case in practice, it is assumed that Ω ⊂ S. There exist instances where it is feasible to observe all states, particularly in simple scenarios.

In Fig. 1, it is postulated that human agents are restricted in their capacity to observe the complete environment and thus, are unable to obtain the full state space S (depicted in pink). Additionally, critical information Ŝ (depicted in green) is often unobserved, and agents can only perceive a limited set of useful information Œ (depicted in blue). Consequently, agents utilize the blue observable subset to construct a simulation of the environment on the right-hand side.

<figure><img src="image_4.png" /><figcaption>**Fig. 1.** This image is an account of the unmanned vehicle task, wherein the left figure represents the observable (blue), latent (green), and irrelevant (pink) aspects of the environment in the real-world, while the right figure depicts a simulator constructed by human observers based on their observations of the former. The table shows the observable information. (Color figure online)</figcaption></figure>

## 3.2 Observation Confidence (OC)

In practical applications, it is frequently uncertain whether the observation corresponds to a complete or partial state, and mistakenly assuming Œ = Ŝ can lead to misinterpretation of a single observation *o* as multiple states *s*₁, *s*₂, ..., *s*<sub>*x*</sub>. This can result in different rewards *r*₁, *r*₂, ..., *r*<sub>*x*</sub> being associated with taking action following the observation, which can cause the RL algorithm to fail and lead to the miscalibration of its *Q*(*a*, *s*) and π(*a*|*s*) [19].
To evaluate the confidence of an observation $o$, we define the Observation Confidence (OC), denoted by $OC = p(s|o)$, and we put forth the subsequent proposition to explicate the correlation between Observation Confidence (OC) and the veritable State-Observation-Gap (SOG), denoted as $\Delta$.

**Proposition 1.** Let $\Delta = \hat{S} - \hat{\Omega}$, then $\forall \Delta, p(s|o) \propto 1/\Delta$.

*Proof.* Set $\Delta = \hat{S} - \hat{\Omega}$ and $p(o|s) = 1$ (according to Definition 2). Because $\hat{s}_{\mathbb{D}} \subset \hat{S}$, $\hat{o}_{\mathbb{D}} \subset \hat{\Omega}$, $s = \hat{s}_{\mathbb{D}}$, $o = \hat{o}_{\mathbb{D}}$. Based on Bayes' theorem, we have the following:

$$ 
\begin{aligned}
p(s|o) &= \frac{p(o|s) \cdot p(s)}{p(o)} \\
&= \frac{p(s)}{p(o)} \\
&= \frac{p(\hat{s}_{\mathbb{D}} | \hat{S})}{p(\hat{o}_{\mathbb{D}} | \hat{\Omega})} \\
&= \frac{p(\hat{s}_{\mathbb{D}} | \hat{\Omega} + \Delta)}{p(\hat{o}_{\mathbb{D}} | \hat{\Omega})} \propto 1/\Delta
\end{aligned} 
\quad (1) $$

Proof finished.

To quantify the plausibility of an observation $o$, we introduce the concept of OC, which measures the discrepancy between the estimated observation space $\hat{\Omega}$ and the estimated state space $\hat{S}$. We have developed two approaches to measure the value of $\Delta$.

## 3.3 Weighting

RL algorithms encounter diverse scenarios across various tasks, and consequently, the estimate of the state space $\hat{S}$, varies accordingly. To account for this variability, we propose two distinct methodologies to adapt the estimate of the state space, $\hat{S}$, to accommodate different types of scenarios, i.e., specialized and general scenarios. Moreover, we evaluate the discrepancy between the true state and the observed state $\Delta$, denoted by $\lambda$.

**Universal Weighting.** The weighting scheme, whereby the weights are set to Boolean values, can be expressed as follows:

$$ w = \begin{cases} 1 & d \in \mathbb{D} \\ 0 & d \notin \mathbb{D} \end{cases} \quad (2) $$

To maintain a generalizable approach, we adopt a straightforward strategy to determine the index set $\hat{o}_{\mathbb{D}}$, as prescribed by (2), which allows for the selection of dimensions to be included in the dimension set. However, in a POMDP, the
reward for $\langle a, s, \cdot \rangle$ may vary. Thus, to address this challenge, we introduce the Boolean weighting parameter, which is defined as follows:

$$ \lambda = \sum_{j=1}^{J} \sum_{i=1}^{I} \theta_{ji}, \qquad (3) $$

where $\theta = 1$. $I \in \mathbb{Z}^+$ is the number of different reward classes in $\langle o, a, \cdot \rangle$, which $\{r_1, r_2, \dots, r_W\}$ is extracted from $\langle o, a, \cdot \rangle$, and $\{\theta_1, \theta_2, \dots, \theta_I\} = \text{de-duplicate}\{r_1, r_2, \dots, r_W\}$ ($\text{de-duplicate}$ is de-duplication operator). $J \in \mathbb{Z}^+$ is the number of tuples $\langle o, a, \cdot \rangle$ in history, and we give a theorem proving its relation with $\lambda$.

**Theorem 1.** Let $\omega$ be the Boolean Weighting from (9), $\lambda$ be a metric from (3). Set $\Delta = \hat{\mathcal{S}} - \hat{\mathcal{O}}$, then $\exists \alpha \ge 0$ such that $\lambda = \alpha |\Delta|$.

*Proof.* According to Definition 2, we know that:

$$ \begin{aligned} \hat{s}_{\mathbb{D}} &= \{\omega_m d_m \mid \omega_m \ge \omega_{m+1}, n > 0, \omega_m d_m \ge 0\}, \\ \hat{o}_{\mathbb{D}} &= \{\omega_l d_l \mid \omega_l \ge \omega_{l+1}, m > l, l > 0, \omega_l d_l \ge 0\} \end{aligned} $$

Then, we donate $\Delta_{sub}$ to measure the gap between a state $s$ and an observation $o$:

$$ \begin{aligned} \Delta_{sub} &= \hat{s}_{\mathbb{D}} - \hat{o}_{\mathbb{D}} \\ &= \{\omega_{l+1}d_{l+1}, \omega_{l+2}d_{l+2}, \dots, \omega_{m-l}d_{m-l}\} \end{aligned} \qquad (4) $$

We assume the $\Theta = \{\theta_1, \theta_2, \dots, \theta_I\} = \text{de-duplicated}\{r_1, r_2, \dots, r_i\}$, where $\{r_1, r_2, \dots, r_i\}$ comes from $\langle o, a, \cdot \rangle$ which the number is $b$ in history $\mathbb{T}$ and $u > v$.

We know $|\Theta| = 1$ in fully observable MDP because $o = s$. More details are:

$$ \begin{aligned} s \times a &= r \\ \Rightarrow \hat{s}_{\mathbb{D}} \times a &= r \\ \Rightarrow \{\omega_1 d_1, \omega_2 d_2, \dots, \omega_m d_m\} \times a &= |\theta_1| \\ \Rightarrow |\Theta| &= 1 \end{aligned} \qquad (5) $$

So, we have:

$$ \begin{aligned} \Delta_{sub} \times a &= (\hat{s}_{\mathbb{D}} - \hat{o}_{\mathbb{D}}) \times a \\ &= \hat{s}_{\mathbb{D}} \times a \\ &= \{\omega_{l+1}d_{l+1}, \omega_{l+2}d_{l+2}, \dots, \omega_{m-l}d_{m-l}\} \times a \\ &= \{\theta_1, \theta_2, \dots, \theta_{m-l}\} \\ \Rightarrow |\Theta| &= m-l \\ \Rightarrow |\Theta| &= |\Delta_{sub}| \end{aligned} \qquad (6) $$

Set $\hat{\mathcal{S}} = \{\hat{s}_{\mathbb{D}_1}, \hat{s}_{\mathbb{D}_2}, \dots, \hat{s}_{\mathbb{D}_g}\}$ and $\hat{\mathcal{O}} = \{\hat{o}_{\mathbb{D}_1}, \hat{o}_{\mathbb{D}_2}, \dots, \hat{o}_{\mathbb{D}_h}\}$, where $g > h$. Then:

$$ \begin{aligned} \Delta &= \hat{\mathcal{S}} - \hat{\mathcal{O}} \\ &= \{\hat{s}_{\mathbb{D}_1}, \hat{s}_{\mathbb{D}_2}, \dots, \hat{s}_{\mathbb{D}_g}\} - \{\hat{o}_{\mathbb{D}_1}, \hat{o}_{\mathbb{D}_2}, \dots, \hat{o}_{\mathbb{D}_h}\} \\ &= \{\Delta_{sub_{h+1}}, \Delta_{sub_{h+2}}, \dots, \Delta_{sub_{g-h}}\} \\ &= \{\Theta_{sub_{h+1}}, \Theta_{sub_{h+2}}, \dots, \Theta_{sub_{g-h}}\} \end{aligned} \qquad (7) $$
Thus,

$$
\begin{align}
\alpha | \Delta | &= \alpha \sum_{c=h+1}^{g-h} | \Theta_{sub_c} | \tag{8} \\
&= \alpha \sum_{c=h+1}^{g-h} \sum_{e=l+1}^{m-l} | \theta_{sub_{ec}} | \propto \lambda_{UW}, \nonumber
\end{align}
$$

where $\lambda_{UW}$ is the $\lambda$ from Universal Weighting and $\alpha > 0$. The proof of Theorem 1 finished.

**Specific Weighting.** The weighting scheme, whereby the weights are assigned continuously, is mathematically expressed as follows:

$$
w = \begin{cases} \beta & d \in \mathbb{D} \\ 0 & d \notin \mathbb{D} \end{cases} \tag{9}
$$

where $\beta \ge 0$ represents the importance of the dimension differently in the specific task or agent. The formula for $\lambda$ is given below:

$$
\lambda = - \sum_{j=1}^{J} \sum_{i=1}^{I} p_{ji} \times \log_{2}(p_{ji}), \qquad (10)
$$

where $J \in \mathbb{Z}^+$ is the number of the tuple $(o, a, \cdot)$ in the history $\mathbb{T}$, and $I \in \mathbb{R}$ is the ratio of different reward classes in a tuple $(o, a, \cdot)$. $p$ is the proportion of a reward in a rewarding class. The formula is:

$$
p = \frac{|\{r_w \mid r_w \in \{r_1, r_2, \dots, r_W\}, r_w = \theta_i, i \le I\}|}{|\{r_1, r_2, \dots, r_W\}|}
$$

We give a theorem proving its relation with $\lambda$.

**Theorem 2.** Let $\omega$ be the Continuous Weighting from (9), $\lambda$ to be a metric from (10). Set $\Delta = \hat{\mathcal{S}} - \hat{\Omega}$, then $\exists \mu \ge 0$ such that $\lambda = \mu |\Delta|$.

*Proof.* Because of $\theta = 1$, we know:

$$
\{\theta_1, \theta_2, \dots, \theta_I\} \propto \{-p_1 \log_2 p_1, -p_2 \log_2 p_2, \dots, -p_I \log_2 p_I\},
$$

where $p \in (0, 1)$ and $-p_i \log_2 p_i > 0$. According to Eq. (8), we have:

$$
\begin{align}
\Delta &= \hat{\mathcal{S}} - \hat{\Omega} \nonumber \\
&= \{\Theta_{sub_{h+1}}, \Theta_{sub_{h+2}}, \dots, \Theta_{sub_{g-h}}\} \tag{11} \\
&\propto \{-p_1 \log_2 p_1, -p_2 \log_2 p_2, \dots, -p_I \log_2 p_I\} \nonumber
\end{align}
$$
Thus, based on Eq. (8),

$$ 
\begin{aligned}
\mu | \Delta | &= \mu \sum_{c=h+1}^{g-h} |-p_{sub_c} \log_2 p_{sub_c}| \\
&= \mu \sum_{c=h+1}^{g-h} \sum_{e=l+1}^{m-l} |-p_{sub_{ec}} \log_2 p_{sub_{ec}}| \propto \lambda_{SW},
\end{aligned} 
\quad (12) $$

where $\lambda_{SW}$ is the $\lambda$ from Specific Weighting and $\mu > 0$. The proof of Theorem 2 finished.

Theorems 2 and 1 concur on the positive correlation between $\lambda$ and $\Delta$. With respect to Universal and Specific Weighting schemes, the former solely focuses on ascertaining the relevance of a dimension, without considering its relative importance, in a generic scenario. Meanwhile, the latter weighs the importance of each dimension based on a specific task or agent in a particular scenario. We present algorithms for the realization of both weighting methodologies as outlined in Algorithms 1 and 2.

## 3.4 Algorithm

**Algorithm 1.** $\lambda$-list Generate Function

**Input:** $T, o_{select}, a_{select}$

**Output:** a $\lambda$-table

**Process:** Function $\lambda$-ListGenerate

Initialisation : Set an empty list $\lambda$-list

1: begin

2: set $H$ is the length of $T$

3: **for** $h := 1$ to $\dots$ $H$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp;**if** $o_h == o_{select}$ and $a_h == a_{select}$ **then**

5: &nbsp;&nbsp;&nbsp;&nbsp;insert $r_h$ into $\lambda$-list

6: **end if**

7: **end for**

Algorithm 1 outlines the methodology for generating the $\lambda$-list, which serves as the preparatory stage for computing $\lambda$. This algorithm takes a tuple $\langle o_{select}, a_{select} \rangle$ as input, selected from the historical data $T$, and subsequently outputs the corresponding $\lambda$-list. Algorithm 1 iterates through $T$ to identify all the matching rewards $\langle o_{select}, a_{select}, \cdot \rangle$, and compiles them into the $\lambda$-list.

Algorithm 2 delineates the process of computing $\lambda$. Initially, it iterates through $T$ and populates the set $U$ with the unique pairs $\langle o_h, a_h \rangle$, while also ensuring that no duplicates exist in $U$. Subsequently, it loops through $U$, utilizing Algorithm 1 to compute the corresponding $\lambda$-list, and applies Eq. 3 or Eq. 10 to determine $\lambda$.
<table><caption>**Algorithm 2.** $\lambda$ Calculation Algorithm</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>Input:</td><td>$\mathbb{T}$</td></tr><tr><td>Output:</td><td>$\lambda$</td></tr><tr><td>Process:</td><td>$\lambda$-Function</td></tr><tr><td>1:</td><td>begin</td></tr><tr><td>2:</td><td>set $U \leftarrow$ empty list.</td></tr><tr><td>3:</td><td>set $H$ is the length of $\mathbb{T}$</td></tr><tr><td>4:</td><td>for $h := 1$ to ... $H$ do</td></tr><tr><td>5:</td><td>if $\langle o_h, a_h \rangle$ not in $U$ then</td></tr><tr><td>6:</td><td>U append $\langle o_h, a_h \rangle$</td></tr><tr><td>7:</td><td>end if</td></tr><tr><td>8:</td><td>end for</td></tr><tr><td>9:</td><td>set $K$ is the length of $U$</td></tr><tr><td>10:</td><td>set $\lambda = 0$</td></tr><tr><td>11:</td><td>for $k := 1$ to ... $K$ do</td></tr><tr><td>12:</td><td>Set $\lambda_{sub} = 0$</td></tr><tr><td>13:</td><td>$\lambda$-list $\leftarrow$ $\lambda$-ListGenerate$\langle o_k, a_k \rangle$</td></tr><tr><td>14:</td><td>calculate $\lambda_{sub}$ using $\lambda$-list (by (3) $\lambda$ for Boolean Weighting, by (10) ($\lambda$ for Continuous Weighting))</td></tr><tr><td>15:</td><td>$\lambda \leftarrow \lambda + \lambda_{sub}$</td></tr><tr><td>16:</td><td>end for</td></tr></tbody></table>

# 4 Experiment

## 4.1 Preparation

In this study, we conducted experiments utilizing the Cliff Walking problem [15] made available by Gym OpenAI [16]. This environment is one of the standard grid-world [17] examples employed for evaluating the effectiveness of on-policy Sarsa [18] and off-policy Q-learning [19] methods. The environment, as shown in Panel A of Fig. 2, is a 4 × 12 grid [20] with cliffs in the fourth row. The agent starts at position $[3, 0]$ and aims to reach the goal at position $[3, 11]$. The agent's action space $\mathcal{A}$ is discrete, with four possible actions: up, down, left, and right. If the agent falls off a cliff, it incurs a penalty of −100, and the episode ends, resetting the agent's position. Additionally, each action results in a penalty of −1. The Cliff Walking task's goal is to minimize the agent's cumulative reward during an episode. Notably, the environment has 3 × 12 + 1 total states, excluding cliff states $[3, 1, \dots, 10]$. We decompose the state and observation into $\hat{s}\mathbb{D} = \omega_1 d_1, \omega_2 d_2, \dots, \omega_{37} d_{37}$ and $\hat{o}\mathbb{D} = \omega_1 d_1, \omega_2 d_2, \dots, \omega_{37} d_{37}$, respectively.

## 4.2 Dimension Melting

We created an innovative experimental approach called **Dimension Melting** to comprehensively study $\Delta$. This approach involves systematically eliminating state dimensions to simulate the impact of $\lambda$. The evaluation of $\Delta$ is achieved by continuously melting dimensions. For the Cliff Walking task, we developed two
<figure><img src="image_5.png" /><figcaption>**Fig. 2.** The explanatory figure portrays the Cliff Walking environment and the experimental design for the Dimension Melting experiments. Panel **A** depicts the base environment of Cliff Walking, with the optimal path for Q-learning and Sarsa illustrated. Panel **B** showcases the experimental design for random melting across six dimensions. In contrast, Panel **C** depicts the row traversal melting methodology with a three-part implementation.</figcaption></figure>

melting schemes for observations. Panel **B** in Fig. 2 randomly selects six dimensions for melting, while Panel **C** gradually and independently melts dimensions along each row.

The experiment comprises 2000 episodes, with a maximum of 50 agent steps per episode. After each episode, we log $\langle s, a, \cdot \rangle$, compute $\lambda$ using Algorithm 2, and determine the reward sum. We conduct ten runs for each melting experiment and average the results. To facilitate the experiment, we employ a *dimension replacement mechanism*, wherein a melted dimension is replaced by one of its adjacent dimensions or a randomly selected available dimension if no adjacent dimensions exist.

# 5 Result

In our experimental results, we employ four algorithms in the dimensional melting experiments design. The four algorithms are Q-learning UW (Q-learning-based $\lambda$ adopting Universal Weighting), Q-learning TW (Q-learning-based $\lambda$ adopting Specific Weighting), Sarsa UW (Sarsa-based $\lambda$ adopting Universal Weighting), Sarsa TW (Sarsa-based $\lambda$ adopting Specific Weighting). Figure 3, the overall trend of $\lambda$ based on Q-learning and Sarsa increases as the dimension melts more. All the $\lambda$ for Universal Weighting are almost close, so indicating that Universal Weighting is a universal solution for $\lambda$ in this task because $\lambda$ does not change with the agent or task changes. The global dimensional stochastic melting apparently has a greater impact on Q-learning, making the observations obtained by the agent based on it even less confident.

The first graph of Fig. 4 is the result of **C** panel of Fig. 2. All $\lambda$ is equal to zero in (1) because row 1 is replaced by row 2 in Fig. 2. This change does not affect Q-learning and Sarsa and even makes Sarsa's results better than the base environment. Sarsa does not detect this change because it chooses a shorter path than the original. In the (2) and (3) graphs of Fig. 4, all $\lambda$ steadily increase with the dimension melting. The reason is that rows 1 and 2 are the critical paths for Sarsa in Fig. 2, so $\lambda$ for Sarsa goes up. For Q-learning, no doubt, row 2 is the optimal route. However, $\lambda$ of Q-learning increases because according to
<figure><img src="image_6.png" /><figcaption>**Fig. 3.** The result of **B** panel of Fig. 2.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>**Fig. 4.** The result of **C** panel of Fig. 2. (1), (2), (3) represent the result of green, blue, pink rows in panel A Fig. 2, respectively. (Color figure online)</figcaption></figure>

*dimension replacement mechanism*, when dimensions in row 2 are deleted, they will be replaced with their lower states in row 1. Row 2 is a mandatory route for Q-learning, so Q-learning detects the change in row 2.

Overall, $\lambda$ performs consistently and can determine $\lambda$ as the dimension melts. However, the weakness exists in the high algorithm dependence (all $\langle o, a, \cdot \rangle$ need to be explored by algorithms) and *dimension replacement mechanism*, they may lead to the malfunction of $\lambda$.

# 6 Conclusion

In this study, we introduce the State-Observation-Gap (SOG) problem in the context of POMDP and devise two distinct weighting methodologies to compute the cumulative entropy $\lambda$. Moreover, we propose two algorithmic approaches and carry out experimental evaluations in the Cliff Walking environment. The extended definition in POMDP serves to enhance the practical applicability of our proposed methodology.

# References

1. Pajarinen, J., Lundell, J., Kyrki, V.: POMDP planning under object composition uncertainty: Application to robotic manipulation. IEEE Trans. Robotics (2022)

2. Zhang, C., et al.: Traffic Mirror-Aware POMDP behavior planning for autonomous urban driving. In: 2022 IEEE Intelligent Vehicles Symposium (IV). IEEE (2022)

3. Singh, G., Roy, R.N., Chanel, C.P.C.: Pomdp-based adaptive interaction through physiological computing (2022)

4. Chadès, I., Pascal, L.V., Nicol, S., Fletcher, C.S., Ferrer-Mestres, J.: A primer on partially observable Markov decision processes (POMDPs). Methods Ecol. Evol. **12**(11), 2058–2072 (2021)

5. Åström, K.J.: Optimal control of Markov processes with incomplete state information. J. Math. Anal. Appl. **10**(1), 174–205 (1965)
6. Smallwood, R.D., Sondik, E.J.: The optimal control of partially observable Markov processes over a finite horizon. Oper. Res. **21**(5), 1071–1088 (1973)

7. Cassandra, A.R.: The POMDP Page (2003). https://www.pomdp.org/. (Accessed 10 Dec 2022)

8. Chadès, I., McDonald-Madden, E., McCarthy, M.A., Wintle, B., Linkie, M., Possingham, H.P.: When to stop managing or surveying cryptic threatened species. Proc. Natl. Acad. Sci. **105**(37), 13936–13940 (2008)

9. Chadès, I., Martin, T.G., Nicol, S., Burgman, M.A., Possingham, H.P., Buckley, Y.M.: General rules for managing and surveying networks of pests, diseases, and endangered species. Proc. Natl. Acad. Sci. **108**(20), 8323–8328 (2011)

10. Chen, X., et al.: Flow-based recurrent belief state learning for pomdps. In: International Conference on Machine Learning. PMLR (2022)

11. Biehl, M., Virgo, N.: Interpreting systems as solving POMDPs: a step towards a formal understanding of agency. arXiv preprint arXiv:2209.01619 (2022)

12. Kavaklioglu, C., Helmeczi, R., Cevik, M.: Linear programming-based solution methods for constrained POMDPs. arXiv preprint arXiv:2206.14081 (2022)

13. Yang, Y., Chen, J., Li, S.: Learning POMDP models with similarity space regularization: a linear gaussian case study. In: Learning for Dynamics and Control Conference. PMLR (2022)

14. Roijers, D.M., Whiteson, S., Oliehoek, F.A.: Point-based planning for multi-objective POMDPs. In: Proceedings of the Twenty-fourth International Joint Conference On Artificial Intelligence (IJCAI) (2015)

15. Demin, V.: Cliff walking problem (2009)

16. Brockman, G., et al.: Openai gym. arXiv preprint arXiv:1606.01540 (2016)

17. Meuth, R.J.: A Survey of Reinforcement Learning Methods in the Windy and Cliff-walking Gridworlds

18. Sutton, R.S., Barto, A.G., et al.: Introduction to reinforcement learning (1998)

19. Watkins, C.J., Dayan, P.: Q-learning. Mach. Learn. **8**(3), 279–292 (1992)

20. Sutton, R.S., Barto, A.G.: Reinforcement learning: An introduction. Robotica **17**(2), 229–235 (1999)