In all tables the number of motion and observation model calls does not
include belief update calls but only the calls for reward or bounds
calculation. The number of accesses to the observation model is always the
same for all three algorithms (column $8$). This agrees with the structure of
the bounds (56) and (57). For the baseline SS, up to rounding errors, the
number of motion model accesses, as we anticipated, is the squared number of
unsimplified belief particles multiplied by number belief nodes in the tree
minus one for root belief, multiplied by number of planning sessions (column
$7$ in the tables). This is in agreement with (54). Also, for all three
algorithms the number of accesses to the observation model was the number of
particles of unsimplified belief minus one for root belief, multiplied by the
number of belief nodes in the tree, multiplied by the number of planning
sessions.

We see that, while having larger particle speedup (column $3$), LAZY-BSP makes
more resimplification calls (column $6$) than SITH-BSP. Observing the
histograms of simplification levels in Fig. 12, we understand that LAZY
variant of resimplification strategy leads to lower simplification levels of
the rewards at the deepest level of a given belief tree. This was expected
since the rewards at the upper levels of the belief tree participate in more
laces and therefore their simplification level is promoted more times (See
Alg. 5). In addition at the lowest levels reside more beliefs and
corresponding rewards. This fact is corroborated by Table 3 where we witness
that LAZY-BSP yields more beliefs, in the given in belief tree, with lower
simplification levels than SITH-BSP.

(a)

(b)

Figure 12:  Simplification levels at each depth of the given belief tree of
Light Dark Problem (Section 7.1.1) after determining best action for one of
the planning sessions. Here we present planning session $6$ of the first trial
of configuration $\lambda=0.5$ of Table 1. The radius of circles represents
the fraction of all nodes at a particular depth that have a particular
simplification level. This figure is associated with Table 3. (a) LAZY-SITH-
BSP Alg 5 (b) SITH-BSP Alg 1.  Table 3: This table displays the numbers of the
beliefs at each simplification level in a given tree after the identification
of optimal action at the root $b_{k}$. Here we investigate Light Dark problem
and belief tree as in Fig. 12. The given belief tree has $4809$ belief nodes.

BSP Alg. | $n_{x}$ | $n^{1}_{z}$ | $n^{2}_{z}$ | $n^{3}_{z}$ | $\lambda$ | $L$ | simpl. level, particles
---|---|---|---|---|---|---|---
$\begin{subarray}{c}{s=1}\\\ {n^{s}_{x}=10}\end{subarray}$ | $\begin{subarray}{c}{s=2}\\\ {n^{s}_{x}=20}\end{subarray}$ | $\begin{subarray}{c}{s=3}\\\ {n^{s}_{x}=30}\end{subarray}$ | $\begin{subarray}{c}{s=4}\\\ {n^{s}_{x}=40}\end{subarray}$ | $\begin{subarray}{c}{s=5}\\\ {n^{s}_{x}=50}\end{subarray}$ | $\begin{subarray}{c}{s=6}\\\ {n^{s}_{x}=60}\end{subarray}$ | $\begin{subarray}{c}{s=7}\\\ {n^{s}_{x}=70}\end{subarray}$ | $\begin{subarray}{c}{s=8}\\\ {n^{s}_{x}=80}\end{subarray}$ | $\begin{subarray}{c}{s=9}\\\ {n^{s}_{x}=90}\end{subarray}$ | $\begin{subarray}{c}{s=10}\\\ {n^{s}_{x}=100}\end{subarray}$
Alg 5 LAZY | $100$ | $1$ | $3$ | $3$ | $0.5$ | $3$ | $2103$ | $666$ | $91$ | $47$ | $14$ | $10$ | $15$ | $88$ | $1094$ | $680$
Alg 1 SITH | $30$ | $61$ | $241$ | $618$ | $696$ | $567$ | $576$ | $465$ | $684$ | $870$

####  7.3.3 Results for 2D Continuous Target Tracking in the Setting of a
Given Belief Tree

Our action space is
$\mathcal{A}=\\{\rightarrow,\nearrow,\uparrow,\nwarrow,\leftarrow,\swarrow,\downarrow,\searrow,Null\\}$,
where action $Null$ means that agent doesn’t take any action. In this problem
we selected the parameters to be $d_{\text{min}}=0.0001$,
$\Sigma_{T}=I\cdot\sigma_{T}$ where $\sigma_{T}=0.1$ and
$\sigma_{\mathcal{O}}=0.1$, $\gamma=0.95$.

We simulate $15$ trials of $15$ consecutive alternating planning sessions and
the executions by the robot of the selected optimal action. Fig. 13 shows an
exemplary trial. We show the agent particles in Fig. 13 and the target
particles in Fig. 13. Similar to the previous section, we study speedup with
growing $\lambda$ in Table 4 and as function of various amounts of belief
particles in Table 5. Again we observe that speedup diminishes with growing
$\lambda$; LAZY-BSP (Alg. 5) produces a larger speedup in terms of particles
(column $4$) and time (column $5$) than SITH-BSP (Alg. 1); accesses to motion
and observation models are as expected; the return is identical for three
algorithms.

In Fig. 14, which is associated with Table 6, we observe that to select an
optimal action LAZY-BSP leaves more beliefs with lower simplification levels
at the bottom of the given belief tree and produces more beliefs with lower
simplification levels than SITH-BSP. A significant time speedup is obtained in
the range of $30\%-70\%$ for LAZY-BSP depending on the values of $\lambda$.
For the SITH-BSP we see less time speedup ranging from $60\%$ to $2\%$ with
increasing $\lambda$. The same best action was identified by SITH-BSP, LAZY-
BSP and SS in all cases. Interestingly, in configuration $n_{x}=350$ of Table.
5, for the first time we obtained that time speedup (62) is larger than
particle speedup (61). This points to the fact that this run was so long due
to large number of unsimplified belief particles $n_{x}=350$ so that the time
of access to motion and observation models varied.

(a)

(b)

Figure 13:  In this illustration we show second trial of Table. 5,
configuration $n_{x}=250$. The canvas color here is
$\sigma_{\mathcal{O}}=\sigma_{T}=0.1$. (a) Agent particles (b) Target
Particles.  Table 4: This table shows cumulative results of $15$ consecutive
alternating planning and action execution sessions averaged over $15$ trials
of Continuous Target Tracking problem. The given in a single planning session
belief tree has $6814$ belief nodes. Overall, in $15$ planning sessions, we
have $102210$ belief nodes. The horizon in each planning session is $L=3$. The
number of observations sampled from each belief action node is $n^{1}_{z}=1$,
$n^{2}_{z}=3$, $n_{z}^{3}=3$ at corresponding to superscripts depths $1,2,3$.
In this table we examine influence of various values of $\lambda$.

BSP Alg. | $n_{x}$ | $\lambda$ | particles speedup (61) | time speedup (62) | resimpl. calls (recursive) | motion model calls | obs. model calls | return ($\hat{V}$)
---|---|---|---|---|---|---|---|---
Alg 1 SITH | $100$ | $0.1$ | $77.43\pm 0.26$ | $60.3\pm 2.21$ | $1.69\cdot 10^{5}\pm 0.04\cdot 10^{5}$ | $3.48\cdot 10^{8}\pm 0.03\cdot 10^{8}$ | $10.22\cdot 10^{6}\pm 0.0$ | $-79.87\pm 9.69$
Alg 5 LAZY | $86.97\pm 1.28$ | $71.18\pm 2.42$ | $7.44\cdot 10^{5}\pm 3.09\cdot 10^{5}$ | $2.32\cdot 10^{8}\pm 0.16\cdot 10^{8}$ | $10.22\cdot 10^{6}\pm 0.0$ | $-79.87\pm 9.69$
SS |  |  |  | $10.22\cdot 10^{8}\pm 0.0$ | $10.22\cdot 10^{6}\pm 0.0$ | $-79.87\pm 9.69$
Alg 1 SITH | $100$ | $0.2$ | $64.64\pm 0.57$ | $46.39\pm 2.27$ | $2.60\cdot 10^{5}\pm 0.04\cdot 10^{5}$ | $5.03\cdot 10^{8}\pm 0.07\cdot 10^{8}$ | $10.22\cdot 10^{6}\pm 0.0$ | $-73.38\pm 9.8$
Alg 5 LAZY | $83.52\pm 1.7$ | $67.24\pm 2.62$ | $16.52\cdot 10^{5}\pm 5.56\cdot 10^{5}$ | $2.75\cdot 10^{8}\pm 0.22\cdot 10^{8}$ | $10.22\cdot 10^{6}\pm 0.0$ | $-73.38\pm 9.8$
SS |  |  |  | $10.22\cdot 10^{8}\pm 0.0$ | $10.22\cdot 10^{6}\pm 0.0$ | $-73.38\pm 9.8$
Alg 1 SITH | $100$ | $0.3$ | $49.57\pm 0.93$ | $29.25\pm 2.39$ | $3.14\cdot 10^{5}\pm 0.05\cdot 10^{5}$ | $6.86\cdot 10^{8}\pm 0.10\cdot 10^{8}$ | $10.44\cdot 10^{6}\pm 0.0$ | $-66.29\pm 9.3$
Alg 5 LAZY | $79.83\pm 2.55$ | $63.34\pm 3.45$ | $26.61\cdot 10^{5}\pm 8.41\cdot 10^{5}$ | $3.21\cdot 10^{8}\pm 0.30\cdot 10^{8}$ | $10.44\cdot 10^{6}\pm 0.0$ | $-66.29\pm 9.3$
SS |  |  |  | $10.22\cdot 10^{8}\pm 0.0$ | $10.44\cdot 10^{6}\pm 0.0$ | $-66.29\pm 9.3$
Alg 1 SITH | $100$ | $0.4$ | $35.75\pm 1.09$ | $14.45\pm 2.85$ | $3.61\cdot 10^{5}\pm 0.06\cdot 10^{5}$ | $8.33\cdot 10^{8}\pm 0.09\cdot 10^{8}$ | $10.44\cdot 10^{6}\pm 0.0$ | $-59.99\pm 8.05$
Alg 5 LAZY | $74.38\pm 3.5$ | $55.69\pm 4.38$ | $42.74\cdot 10^{5}\pm 12.16\cdot 10^{5}$ | $3.90\cdot 10^{8}\pm 0.38\cdot 10^{8}$ | $10.44\cdot 10^{6}\pm 0.0$ | $-59.99\pm 8.05$
SS |  |  |  | $10.22\cdot 10^{8}\pm 0.0$ | $10.44\cdot 10^{6}\pm 0.0$ | $-59.99\pm 8.05$
Alg 1 SITH | $100$ | $0.5$ | $25.51\pm 1.04$ | $6.44\pm 2.49$ | $4.05\cdot 10^{5}\pm 0.06\cdot 10^{5}$ | $9.18\cdot 10^{8}\pm 0.08\cdot 10^{8}$ | $10.44\cdot 10^{6}\pm 0.0$ | $-53.15\pm 7.03$
Alg 5 LAZY | $67.76\pm 3.88$ | $47.94\pm 5.08$ | $63.18\cdot 10^{5}\pm 15.71\cdot 10^{5}$ | $4.75\cdot 10^{8}\pm 0.44\cdot 10^{8}$ | $10.44\cdot 10^{6}\pm 0.0$ | $-53.15\pm 7.03$
SS |  |  |  | $10.22\cdot 10^{8}\pm 0.0$ | $10.44\cdot 10^{6}\pm 0.0$ | $-53.15\pm 7.03$
Alg 1 SITH | $100$ | $0.6$ | $18.06\pm 1.0$ | $2.63\pm 2.32$ | $4.43\cdot 10^{5}\pm 0.06\cdot 10^{5}$ | $9.65\cdot 10^{8}\pm 0.06\cdot 10^{8}$ | $10.44\cdot 10^{6}\pm 0.0$ | $-46.97\pm 7.14$
Alg 5 LAZY | $59.53\pm 3.78$ | $38.14\pm 4.69$ | $89.27\cdot 10^{5}\pm 15.03\cdot 10^{5}$ | $5.77\cdot 10^{8}\pm 0.43\cdot 10^{8}$ | $10.44\cdot 10^{6}\pm 0.0$ | $-46.97\pm 7.14$
SS |  |  |  | $10.22\cdot 10^{8}\pm 0.0$ | $10.44\cdot 10^{6}\pm 0.0$ | $-46.97\pm 7.14$

Table 5: This table shows cumulative results of $15$ consecutive alternating
planning and execution sessions averaged over $15$ trials of Continuous Target
Tracking problem. The given belief tree has $6814$ belief nodes. Overall, in
$15$ planning sessions, we have $102210$ belief nodes. The horizon in each
planning session is $L=3$. The number of observations sampled from each belief
action node is $n^{1}_{z}=1$, $n^{2}_{z}=3$, $n_{z}^{3}=3$ at corresponding to
superscripts depths $1,2,3$. In this table we examine various numbers of
belief particles.

BSP Alg. | $n_{x}$ | $\lambda$ | particles speedup (61) | time speedup (62) | resimpl. calls (recursive) | motion model calls | obs. model calls | return ($\hat{V}$)
---|---|---|---|---|---|---|---|---
Alg 1 SITH | $150$ | $0.5$ | $25.19\pm 0.94$ | $8.72\pm 2.4$ | $4.03\cdot 10^{5}\pm 0.03\cdot 10^{5}$ | $20.71\cdot 10^{8}\pm 0.15\cdot 10^{8}$ | $15.33\cdot 10^{6}\pm 0.0$ | $-54.0\pm 8.16$
Alg 5 LAZY | $68.36\pm 2.66$ | $50.23\pm 3.2$ | $63.14\cdot 10^{5}\pm 9.15\cdot 10^{5}$ | $10.55\cdot 10^{8}\pm 0.65\cdot 10^{8}$ | $15.33\cdot 10^{6}\pm 0.0$ | $-54.0\pm 8.16$
SS |  |  |  | $22.10\cdot 10^{8}\pm 0.0$ | $15.33\cdot 10^{6}\pm 0.0$ | $-54.0\pm 8.16$
Alg 1 SITH | $250$ | $0.5$ | $23.87\pm 0.98$ | $11.01\pm 3.93$ | $4.11\cdot 10^{5}\pm 0.05\cdot 10^{5}$ | $58.10\cdot 10^{8}\pm 0.40\cdot 10^{8}$ | $25.55\cdot 10^{6}\pm 0.0$ | $-55.57\pm 9.59$
Alg 5 LAZY | $66.18\pm 3.35$ | $51.51\pm 3.83$ | $70.02\cdot 10^{5}\pm 12.74\cdot 10^{5}$ | $30.79\cdot 10^{8}\pm 2.37\cdot 10^{8}$ | $25.55\cdot 10^{6}\pm 0.0$ | $-55.57\pm 9.59$
SS |  |  |  | $63.88\cdot 10^{8}\pm 0.0$ | $25.55\cdot 10^{6}\pm 0.0$ | $-55.57\pm 9.59$
Alg 1 SITH | $350$ | $0.5$ | $23.95\pm 1.07$ | $40.18\pm 10.29$ | $4.11\cdot 10^{5}\pm 0.03\cdot 10^{5}$ | $113.81\cdot 10^{8}\pm 0.89\cdot 10^{8}$ | $35.77\cdot 10^{6}\pm 0.0$ | $-55.62\pm 8.73$
Alg 5 LAZY | $66.36\pm 2.58$ | $67.17\pm 4.86$ | $69.40\cdot 10^{5}\pm 10.08\cdot 10^{5}$ | $60.19\cdot 10^{8}\pm 3.62\cdot 10^{8}$ | $35.77\cdot 10^{6}\pm 0.0$ | $-55.62\pm 8.73$
SS |  |  |  | $125.21\cdot 10^{8}\pm 0.0$ | $35.77\cdot 10^{6}\pm 0.0$ | $-55.62\pm 8.73$

(a)

(b)

Figure 14:  Simplification levels at each depth of the given belief tree of
Target Tracking problem (Section 7.1.2) after determining best action for one
of the planning sessions.. Here we present planning session $6$ of the first
trial of configuration $n_{x}=250$ of Table 5. The radius of circles represent
the fraction of all nodes at particular depth that have a particular
simplification level. This figure is associated with Table 6. (a) LAZY-SITH-
BSP Alg 5 (b) SITH-BSP Alg 1.  Table 6: This table displays the numbers of the
beliefs at each simplification level in given tree after the identification of
optimal action at the root $b_{k}$. Here we investigate Target Tracking
problem and belief tree as in Fig. 14. The size of given belief tree is $6814$
belief nodes.

BSP Alg. | $n_{x}$ | $n^{1}_{z}$ | $n^{2}_{z}$ | $n^{3}_{z}$ | $\lambda$ | $L$ | simpl. level, particles
---|---|---|---|---|---|---|---
$\begin{subarray}{c}{s=1}\\\ {n^{s}_{x}=25}\end{subarray}$ | $\begin{subarray}{c}{s=2}\\\ {n^{s}_{x}=50}\end{subarray}$ | $\begin{subarray}{c}{s=3}\\\ {n^{s}_{x}=75}\end{subarray}$ | $\begin{subarray}{c}{s=4}\\\ {n^{s}_{x}=100}\end{subarray}$ | $\begin{subarray}{c}{s=5}\\\ {n^{s}_{x}=125}\end{subarray}$ | $\begin{subarray}{c}{s=6}\\\ {n^{s}_{x}=150}\end{subarray}$ | $\begin{subarray}{c}{s=7}\\\ {n^{s}_{x}=175}\end{subarray}$ | $\begin{subarray}{c}{s=8}\\\ {n^{s}_{x}=200}\end{subarray}$ | $\begin{subarray}{c}{s=9}\\\ {n^{s}_{x}=225}\end{subarray}$ | $\begin{subarray}{c}{s=10}\\\ {n^{s}_{x}=250}\end{subarray}$
Alg 5 LAZY | $250$ | $1$ | $3$ | $3$ | $0.5$ | $3$ | $3487$ | $949$ | $776$ | $884$ | $379$ | $106$ | $48$ | $34$ | $11$ | $139$
Alg 1 SITH | $10$ | $19$ | $46$ | $144$ | $538$ | $966$ | $1266$ | $1208$ | $1164$ | $1452$

####  7.3.4 Experiments with MCTS

(a) SITH-PFT

(b) PFT-DPW

(c) IPFT

Figure 15: 2D Continuous Light Dark. The agent starts from an initial unknown
location and is given an initial belief. The goal is to get to location
$(0,0)$ (circled in red) and execute the terminal action. Near the beacon
(white light) the observations are less noisy. We consider multi-objective
function, accounting for the distance to the goal and the differential entropy
approximation (with the minus sign for reward notation). Executing the
terminal action inside the red circle gives the agent a large positive reward
but executing it outside it, will yield a large negative reward.

In an anytime setting of MCTS we focus on the $2D$-continuous light dark
problem from Section 7.1.1. We place a single “light beacon” in the continuous
world. Here we changed the reward. The agent’s goal is to get to location
$(0,0)$ and execute the terminal action - $Null$. Executing it within a radius
of $0.5$ from $(0,0)$ will give the agent a reward of $200$, and executing it
outside the radius will yield a negative reward of $-200$. For all other
actions the multi-objective reward function is
$\rho(b,a,z,b^{\prime})=-\underset{x\sim
b^{\prime}}{\mathbb{E}}[\|x\|_{2}]-\hat{\mathcal{H}}(b,a,z,b^{\prime})$. The
agent can move in eight evenly spread directions
$\mathcal{A}=\\{\rightarrow,\nearrow,\uparrow,\nwarrow,\leftarrow,\swarrow,\downarrow,\searrow,Null\\}$.
Motion and observation models, and the initial belief are
$\mathbb{P}_{T}(\cdot|x_{,}a)=\mathcal{N}(x+a,\Sigma_{T})$,
$\mathbb{P}_{Z}(z|x)=\mathcal{N}(x,\min\\{1,\parallel
x-x^{b}\parallel^{2}_{2}\\}\cdot\Sigma_{\mathcal{O}})$,
$b_{0}=\mathcal{N}(x_{0},\Sigma_{0})$ respectively. $x^{b}$ is the 2D location
of the beacon and all covariance matrices are diagonal (i.e.
$\Sigma=I\cdot\sigma^{2}$).

Table 7: Time speedup (62) obtained SITH-PFT versus PFT-DPW. The rows are different configurations of the number of belief particles $n_{x}$, maximal tree depth $L$, and the number of iterations per planning session. In all simulations SITH-PFT and PFT-DPW declared _identical_ actions as optimal and exhibited _identical_ belief trees in terms of connectivity and visitation counts. ($n_{x}$, $L$, `#`iter.) | mean $\pm$std | max. | min.
---|---|---|---
(50, 30, 200) | $19.35\pm 6.34$ | $30.17$ | $7.99$
(50, 50, 500) | $17.43\pm 5.4$ | $33.49$ | $10.72$
(100, 30, 200) | $21.97\pm 8.74$ | $49.24$ | $7.36$
(100, 50, 500) | $22.54\pm 6.33$ | $36.09$ | $13.65$
(200, 30, 200) | $26.27\pm 9.36$ | $42.43$ | $11.17$
(200, 50, 500) | $26.17\pm 7.64$ | $44.31$ | $14.43$
(400, 30, 200) | $21.88\pm 8.47$ | $37.04$ | $10.34$
(400, 50, 500) | $21.71\pm 6.01$ | $32.69$ | $9.67$
(600, 30, 200) | $20.27\pm 7.38$ | $32.95$ | $8.77$
(600, 50, 500) | $19.93\pm 6.48$ | $31.26$ | $6.49$
Table 8: Total runtime of $25$ repetitions of two algorithms. ($n_{x}$, $L$, `#`iter.) | Algorithm | tot. plan. time [sec]
---|---|---
(50, 30, 200) | PFT-DPW | $49.7$
SITH-PFT | $40.25$
(50, 50, 500) | PFT-DPW | $125.05$
SITH-PFT | $103.71$
(100, 30, 200) | PFT-DPW | $185.47$
SITH-PFT | $145.08$
(100, 50, 500) | PFT-DPW | $460.29$
SITH-PFT | $357.57$
(200, 30, 200) | PFT-DPW | $709.66$
SITH-PFT | $526.18$
(200, 50, 500) | PFT-DPW | $1755.08$
SITH-PFT | $1298.86$
(400, 30, 200) | PFT-DPW | $2672.56$
SITH-PFT | $2099.0$
(400, 50, 500) | PFT-DPW | $6877.24$
SITH-PFT | $5403.91$
(600, 30, 200) | PFT-DPW | $6335.09$
SITH-PFT | $5056.96$
(600, 50, 500) | PFT-DPW | $15682.47$
SITH-PFT | $12602.09$

We selected the following parameters $x_{0}=\begin{pmatrix}-5.5\\\
0.0\end{pmatrix},\Sigma_{0}=\begin{pmatrix}0.2&0.0\\\
0.0&0.2\end{pmatrix},\sigma_{T}=\sigma_{\mathcal{O}}=0.075$. We experiment
with $10$ different configurations (rows of Table 7) that differ in $n_{x}$
(number of particles), $L$ (MCTS simulation depth), and $\\#$iter (number of
MCTS simulation iterations per planning session). Each scenario comprises $10$
planning sessions, i.e. the agent performs up to $10$ planning action-
executing iterations. The scenario stops if the best action determined in
planning is $Null$. We repeat each experiment 25 times. In each such
repetition we run PFT-DPW and SITH-PFT with the same seed and calculate the
relative time speedup in percentage according to (62) where $t_{\mathrm{PFT-
DPW}}$ and $t_{\mathrm{SITH-PFT}}$ are running times of a baseline and our
methods respectively.

In all different configurations, we obtained significant time speedup of
approximately $20\%$ while achieving the exact same solution compared to PFT.
In Table 7 we report the mean and standard error of (62) as well as maximum
and minimum value. Remarkably, we observe that we never slowdown the PFT-DPW
with SITH-PFT. We also present total running times of $25$ repetitions of at
most $10$ (the simulation stops if best identified action is $Null$) planning
sessions in Table 8. Note that we divided the total planning time by the
number of planning sessions in each repetition.

An illustration of evaluated scenario can be found in Fig. 15. Note that SITH-
PFT (Fig. 15(a)) yields an identical to PFT solution (Fig. 15(b)) while IPFT
demonstrates a severely degraded behavior. We remind the purpose of our work
is to speedup the PFT approach when coupled with information-theoretic reward.
Since the two algorithms produce identical belief trees and action at the end
of each planning session, there is no point reporting the algorithms
_identical_ performances (apart from planning time).

###  7.4 Discussion

Although the speedup was significant and steady for all simulations, we did
not observe growth in speed-up with growth of number of belief particles in
any simulation. This can be explained by the fact that the estimators are far
from convergence and increasing number of particles just randomly changes the
estimator itself due to sampling induced variance. The limitation of our
approach is that it leans on converging bounds, which are not trivial to
derive and specific for a particular reward function. In addition, it requires
slightly more caching than the baseline. Our simplification approach may still
be ill-timed, since the resimplifications take an additional toll in terms of
running time.

##  8 Conclusions

We contributed a rigorous provable theory of adaptive multilevel
simplification that accelerates solution of belief-dependent fully continuous
POMDP. Our theory always identifies the same optimal action or policy as the
unsimplified analog. Our theoretical approach receives as input adaptive
bounds over the belief dependent reward. Using the suggested theory and these
bounds we formulated three algorithms, considering a given belief tree and an
anytime MCTS setting. We also contributed a specific simplification
considering nonparametric beliefs represented by weighted particles, and
derived novel bounds over a differential entropy estimator, which only utilize
a subset of the particles and are computationally cheaper than the latter. Our
experiments demonstrate that our algorithms are paramount in terms of
computation time while guaranteed to have the same performance as the
baselines. In the setting of given belief tree we achieved a speedup up to
$70\%$. In an anytime MCTS setting, our algorithm enjoyed the speedup of
$20\%$.

##  9 Funding

This research was supported by the Israel Science Foundation (ISF) and by a
donation from the Zuckerman Fund to the Technion Artificial Intelligence Hub
(Tech.AI).

##  10 APPENDIX

###  10.1 Proof for Theorem 1

To shorten the notations we prove the theorem for value function under
arbitrary policy. Note that by substituting the policy $\pi_{(\ell)+}$ by
$\\{\pi_{\ell}(b_{\ell}),\pi^{*}_{(\ell+1)+}\\}$ where
$a_{\ell}=\pi_{\ell}(b_{\ell})$ we always can obtain action-value function.
Without loosing generality assume the resimplifciation hits an arbitrary
belief action node. The new upper bound will be

$\displaystyle\\!\\!\overline{\hat{V}}(b_{\ell},\pi_{\ell+})\\!+\\!\frac{1}{M}\Bigg{(}\\!\\!\underbrace{\overline{\Delta}^{s+1}(b,a,b^{\prime})\\!-\\!\overline{\Delta}^{s}(b,a,b^{\prime})}_{\leq
0}\\!\\!\Bigg{)}\\!\\!\leq\\!\overline{\hat{V}}(b_{\ell},\pi_{\ell+})\\!\\!\\!$
(63)

The new lower bound will be

$\displaystyle\\!\underline{\hat{V}}(b_{\ell},\pi_{\ell+})\\!-\\!\frac{1}{M}\Bigg{(}\\!\\!\underbrace{\underline{\Delta}^{s+1}(b,a,b^{\prime})\\!-\\!\underline{\Delta}^{s}(b,a,b^{\prime})}_{\leq
0}\\!\\!\Bigg{)}\\!\\!\geq\\!\underline{\hat{V}}(b_{\ell},\\!\pi_{\ell+})\\!\\!\\!$
(64)

where $M=n_{z}^{d}$ depending on the depth $d$ of resimplified reward bound.
Moreover if the inequalities involving increments are strict
$\overline{\Delta}^{s}(b,a,b^{\prime})>\overline{\Delta}^{s+1}(b,a,b^{\prime})$
and $\underline{\Delta}^{s}(b,a)>\underline{\Delta}^{s+1}(b,a,b^{\prime})$
also the retracting the bounds over Value function inequalities are strict. In
case of MCTS, we have that $M=\frac{N(ha)}{N(h^{\prime})}$ where history $ha$
corresponds to $b_{\ell}$ and action $a$, and $h^{\prime}$ corresponds to
$b^{\prime}$. $\blacksquare$

###  10.2 Proof of Lemma 1

Recall that the bounds $\overline{\rho},\underline{\rho}$ of belief nodes and
”weakest link” rollout nodes are refined when the inequality (50) is
encountered.

Assume in contradiction that the resimplifciation strategy does not promote
any reward level and $G(ha)>0$. This means that $\nicefrac{{G(ha)}}{{d}}>0$
and for all reward bounds the inequality
$\gamma^{d-d^{\prime}}\cdot(\overline{\rho}-\underline{\rho})<\frac{1}{d}G(ha)$.
This is not possible since $\nicefrac{{G(ha)}}{{d}}$ is the mean gap with
respect to simulations of MCT and the depth of the belief tree, multiplied by
the appropriate discount factor, over all the nodes that are the descendants
to $ha$ . See equation (32). $\blacksquare$

###  10.3 Proof of Lemma 2

Observe that

$\displaystyle\overline{\mathrm{UCB}}(ha)\\!-\\!\underline{\mathrm{UCB}}(ha)=\overline{\hat{Q}}(ha)-\underline{\hat{Q}}(ha).$
(65)

We already proved the desired for
$\overline{\hat{Q}}(ha),\underline{\hat{Q}}(ha)$ in Theorem 1. Using the
convergence
$\underline{\hat{Q}}(\cdot)=\hat{Q}(\cdot)=\overline{\hat{Q}}(\cdot)$ we
obtain

$\displaystyle\underline{\hat{Q}}(\cdot)+c\\!\cdot\\!\sqrt{\nicefrac{{\log(N(h))}}{{N(ha)}}}=$
$\displaystyle\hat{Q}(\cdot)+c\\!\cdot\\!\sqrt{\nicefrac{{\log(N(h))}}{{N(ha)}}}=$
(66)
$\displaystyle\overline{\hat{Q}}(\cdot)+c\\!\cdot\\!\sqrt{\nicefrac{{\log(N(h))}}{{N(ha)}}}.$

The proof is completed. $\blacksquare$

###  10.4 Proof of Theorem 2

We provide proof by induction on the belief tree structure.
Base: Consider an initial given belief node $b_{0}$. No actions have been
taken and no observations have been made. Thus, both the PFT tree and the
SITH-PFT tree contain a single identical belief node, and the claim holds.
Induction hypothesis: Assume we are given two identical trees with $n$ nodes,
generated by PFT and SITH-PFT. The trees uphold the terms of Definition 2.
Induction step: Assume in contradiction that different nodes were added to the
trees in the next simulation (expanding the belief tree by one belief node by
definition). Thus, we got different trees.
Two scenarios are possible:

######  Case 1.

The same action-observation sequence $a_{0},z_{1},a_{1},z_{2}...a_{m}$ was
chosen in both trees, but different nodes were added.

######  Case 2.

Different action-observation sequences were chosen for both trees, and thus,
we got different trees structure.

Since the Induction hypothesis holds, the last action $a_{m}$ was taken from
the same node denoted $h^{\prime}$ shared and identical to both trees. Next,
the same observation model is sampled for a new observation, and a new belief
node is added with a rollout emanating from it. The new belief nodes and the
rollout are identical for both trees since both algorithms use the same
randomization seed and observation and motion models. Case 2 must be true
since we showed Case 1 is false. There are two possible scenarios such that
different action-observation sequences were chosen:

######  Case 2.1.

At some point in the actions-observations sequence, different observations
$z_{i},z^{\prime}_{i}$ were chosen.

######  Case 2.2.

At some point in the actions-observations sequence, PFT chose action
$a^{\dagger}$ while SITH-PFT chose a different action, $\tilde{a}$, or got
stuck without picking any action.

Case 2.1 is not possible since if new observations were made, they are the
same one by reasons contradicting Case 1. If we draw existing observations
(choose some observation branch down the tree) the same observations are drawn
since they are drawn with the same random seed and from the same observations
“pool”. It is the same “pool” since the Induction hypothesis holds. Case 2.2
must be true since we showed Case 2.1 is false, i.e., when both algorithms are
at the identical node denoted as $h$ PFT chooses action $a^{\dagger}$, while
SITH-PFT chooses a different action, $\tilde{a}$, or even got stuck without
picking any action. Specifically, PFT chooses action
$a^{\dagger}=\underset{a}{\mathrm{\operatorname*{arg\,max}}}\ \text{UCB}$ and
SITH-PFT’s candidate action is
$\tilde{a}=\underset{a\in\mathcal{A}}{\mathrm{\operatorname*{arg\,max}}}\
\underline{\mathrm{UCB}}(ha)$. Three different scenarios are possible:

######  Case 2.2.1.

the $\overline{\mathrm{UCB}},\underline{\mathrm{UCB}}$ bounds over
$h\tilde{a}$ were tight enough and $\tilde{a}$ was chosen such that
$a^{\dagger}\neq\tilde{a}$.

######  Case 2.2.2.

SITH-PFT is stuck in an infinite loop. It can happen if the
$\overline{\mathrm{UCB}},\underline{\mathrm{UCB}}$ bounds over $h\tilde{a}$,
and at least one of its sibling nodes $ha$, are not tight enough. However, all
tree nodes are at the maximal simplification level. Hence, resimplification is
triggered over and over without it changing anything.

Case 2.2.1 is not possible as the bounds are analytical (always true) and
converge to the actual reward
($\underline{\mathrm{UCB}}=\text{UCB}=\overline{\mathrm{UCB}}$) for the
maximal simplification level. Case 2.2.2 is not possible. If the bounds are
not close enough to make a decision, resimplification is triggered. Each time
some $ha$ node - sibling to $h\tilde{a}$ and maybe even $h\tilde{a}$ itself is
chosen in SelectBest to over-go resimplification. According to lemmas 1 and 2,
after some finite number of iterations for all of the sibling $ha$ nodes
(including $h\tilde{a}$) it holds
$\underline{\mathrm{UCB}}(ha)=\text{UCB}(ha)=\overline{\mathrm{UCB}}(ha)$ and
some action can be picked. If different actions have identical values we
choose one by the same rule UCB picks actions with identical values (e.g.
lower index/random). Since Case 2.2.2 is false, after some finite number of
resimplification iterations, SITH-PFT will stop with bounds sufficient enough
to make a decision; as Case 2.2.1 is false it holds that
$a^{\dagger}=\tilde{a}$. Thus we get a contradiction and the proof is
complete. $\blacksquare$

###  10.5 Proof of Theorem 3

Since same tree is built according to Theorem 2, the only modification is the
final criteria at the end of the planning session at the root of the tree:
$a^{*}=\underset{a}{\mathrm{\operatorname*{arg\,max}}}\ Q(ha)$. Note we can
set the exploration constant of UCB to $c=0$ and we get that UCB is just the
$Q$ function. Thus if the bounds are not tight enough at the root to decide on
an action, resimplification will be repeatedly called until SITH-PFT can make
a decision. The action will be identical to the one chosen by UCB at PFT from
similar arguments in the proof of Theorem 2. Note that additional final
criteria for action selection could be introduced, but it would not matter as
tree consistency is kept according to Theorem 2 and the bounds converge to the
immediate rewards and $Q$ estimations. $\blacksquare$

###  10.6 Proof for Theorem 4

Let us first prove that $u+\hat{\mathcal{H}}\geq 0$. the It holds

$\displaystyle u+\hat{\mathcal{H}}=\sum_{i\notin
A^{s}_{k+1}}\\!\\!\\!w_{k+1}^{i}\\!\cdot\\!\log\left[m\cdot\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\right]+$
(67) $\displaystyle\sum_{i\in
A^{s}_{k+1}}\\!\\!\\!\\!w_{k+1}^{i}\\!\cdot\\!\log\\!\\!\left[\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\\!\\!\sum_{j=1}^{n_{x}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}\right]\\!\\!-$
$\displaystyle\sum_{i=1}^{n_{x}}\\!w_{k+1}^{i}\\!\cdot\\!\log\\!\\!\left[\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\\!\\!\sum_{j=1}^{n_{x}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}\right]\\!\\!=$

The Eq. (67) equals to

$\displaystyle\sum_{i\notin
A^{s}_{k+1}}\\!\\!\\!w_{k+1}^{i}\\!\cdot\\!\log\left[m\cdot\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\right]-$
$\displaystyle\sum_{i\notin
A^{s}_{k+1}}\\!\\!\\!w_{k+1}^{i}\\!\cdot\\!\log\\!\left[\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\sum_{j=1}^{n_{x}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}\right]$

Fix arbitrary index $i\notin A^{s}_{k+1}$. The $\log$ is monotonically
increasing function so it is left to prove that

$\displaystyle
m\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\\!\\!\geq\\!\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\\!\\!\sum_{j=1}^{n_{x}}\\!\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}$

If $\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})=0$, we finished. Assume
$\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\neq 0$. It holds that

$\displaystyle\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\sum_{j=1}^{n_{x}}\max_{\begin{subarray}{c}x_{k+1}\\\
x_{k},a_{k}\end{subarray}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}\geq$
(68)
$\displaystyle\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\sum_{j=1}^{n_{x}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}$
(69)

We reached the desired result. Now let us show the second part
$\ell+\hat{\mathcal{H}}\leq 0$. Observe, that

$\displaystyle 0\geq\ell+\hat{\mathcal{H}}=$ (70)
$\displaystyle\sum_{i=1}^{n_{x}}w_{k+1}^{i}\log\\!\\!\left[\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\\!\\!\sum_{j\in
A^{s}_{k}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}\right]\\!\\!-$
$\displaystyle\sum_{i=1}^{n_{x}}w_{k+1}^{i}\log\\!\\!\left[\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\\!\\!\sum_{j=1}^{n_{x}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}\right]$

Select arbitrary index $i$. We shall prove that

$\displaystyle\log\left[\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\sum_{j\in
A^{s}_{k}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}\right]-$
$\displaystyle\log\left[\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\sum_{j=1}^{n_{x}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}\right]\leq
0$

Again use that $\log$ is monotonically increasing and assume that
$\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\neq 0$. We have that

$\displaystyle\sum_{j\in
A^{s}_{k}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}-\sum_{j=1}^{n_{x}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}=$
(71) $\displaystyle-\sum_{j\notin
A^{s}_{k}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}\leq 0$

$\blacksquare$

###  10.7 Proof for Theorem 5

We first prove that

$\displaystyle\overline{\Delta}^{s}(b,a,b^{\prime})\geq\overline{\Delta}^{s+1}(b,a,b^{\prime})\geq
0$ (72)

Recall that from the previous proof equation (67)

$\displaystyle\overline{\Delta}^{s}(b,a,b^{\prime})=$
$\displaystyle\sum_{i\notin
A^{s}_{k+1}}\\!\\!\\!w_{k+1}^{i}\log\\!\left[m\cdot\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\right]-$
(73) $\displaystyle\sum_{i\notin
A^{s}_{k+1}}\\!\\!\\!w_{k+1}^{i}\log\\!\left[\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\\!\\!\sum_{j=1}^{n_{x}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}\right]$

Suppose we promote the simplification level. Without loss of generality assume
that $A^{s+1}_{k+1}=A^{s}_{k+1}\cup\\{q\\}$. From the above we conclude that
$q\notin A^{s}_{k+1}$

$\displaystyle\overline{\Delta}^{s+1}(b,a,b^{\prime})=\overline{\Delta}^{s}(b,a,b^{\prime})-$
$\displaystyle-
w_{k+1}^{q}\Bigg{(}\log\left[m\cdot\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{q})\right]-$
(74)
$\displaystyle-\log\left[\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{q})\sum_{j=1}^{n_{x}}\mathbb{P}_{T}(x_{k+1}^{q}|x_{k}^{j},a_{k})w_{k}^{j}\right]\Bigg{)}$

It is left to prove that

$\displaystyle m\cdot\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{q})\geq$ (75)
$\displaystyle\geq\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{q})\sum_{j=1}^{n_{x}}\mathbb{P}_{T}(x_{k+1}^{q}|x_{k}^{j},a_{k})w_{k}^{j}$

We already done that in previous theorem. Now we prove the second part

$\displaystyle\underline{\Delta}^{s}(b,a,b^{\prime})\geq\underline{\Delta}^{s+1}(b,a,b^{\prime})\geq
0$ (76)

The next equation is minus the equation (70)

$\displaystyle\underline{\Delta}^{s}(b,a,b^{\prime})=$ (77)
$\displaystyle\sum_{i=1}^{n_{x}}w_{k+1}^{i}\log\\!\left[\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\\!\\!\sum_{j=1}^{n_{x}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}\right]\\!\\!-$
$\displaystyle\sum_{i=1}^{n_{x}}w_{k+1}^{i}\log\\!\left[\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\\!\\!\sum_{j\in
A^{s}_{k}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}\right]$

Assume again without loosing generality that
$A^{s+1}_{k}=A^{s}_{k}\cup\\{q\\}$. In that case

$\displaystyle\underline{\Delta}^{s}(b,a,b^{\prime})-\underline{\Delta}^{s+1}(b,a,b^{\prime})=$
(78)
$\displaystyle-\sum_{i=1}^{n_{x}}\\!w_{k+1}^{i}\log\\!\\!\left[\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\\!\\!\\!\sum_{j\in
A^{s}_{k}}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}\right]$ (79)
$\displaystyle+\sum_{i=1}^{n_{x}}\\!w_{k+1}^{i}\log\\!\\!\left[\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\\!\\!\\!\sum_{j\in
A^{s+1}_{k}}\\!\\!\\!\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}\right]$
(80)

Select arbitrary index $i$. We got back to end to previous theorem. Note that
by definition the bounds are convergent since we are using all the particles.
To see it explicitly suppose that $\\{i\notin A^{s}_{k+1}\\}=\emptyset$ and
$\\{i\notin A^{s}_{k}\\}=\emptyset$. We have that

$\displaystyle\overline{\Delta}^{s}(b,a,b^{\prime})=\underline{\Delta}^{s}(b,a,b^{\prime})=0.$
(81)

This concludes the proof. $\blacksquare$

###  10.8 Bounds time complexity analysis

We turn to analyze the time complexity of our method using the chosen bounds
(56) and (57). We assume the significant bottleneck is querying the motion
$\mathbb{P}_{T}(x^{\prime}|x,a)$ and observation $\mathbb{P}_{Z}(z|x)$ models
respectively. Assume the belief is approximated by a set of $n_{x}$ weighted
particles,

$\displaystyle b=\\{x^{i},w^{i}\\}_{i=1}^{n_{x}}.$ (82)

Consider the Boers et al. (2010) differential entropy approximation for belief
at time $k+1$,

$\displaystyle\hat{\mathcal{H}}(b_{k},a_{k},z_{k+1},b_{k+1})\triangleq\underbrace{\log\left[\sum_{i}\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})w_{k}^{i}\right]}_{(a)}+$
(83)
$\displaystyle\underbrace{\sum_{i}w_{k+1}^{i}\cdot\log\left[\mathbb{P}_{Z}(z_{k+1}|x_{k+1}^{i})\sum_{j}\mathbb{P}_{T}(x_{k+1}^{i}|x_{k}^{j},a_{k})w_{k}^{j}\right]}_{(b)}$
(84)

Denote the time to query the observation and motion models a single time as
$t_{obs},t_{mot}$ respectively. It is clear from (82), (83) (term a) and, (84)
(term b) that:

$\displaystyle\forall b\text{ as in \eqref{eq:BeliefParticlesApp}
}\Theta(\hat{\mathcal{H}}(b))=\Theta(n_{x}\cdot t_{obs}+n_{x}^{2}\cdot
t_{mot}).$ (85)

Since we share calculation between the bounds, the bounds’ time complexity,
for some level of simplification $s$, is:

$\displaystyle\Theta(\ell^{s}+u^{s})=\Theta(n_{x}\cdot t_{obs}+n_{x}^{s}\cdot
n_{x}\cdot t_{mot}),$ (86)

where $n_{x}^{s}$ is the size of the particles subset that is currently used
for the bounds calculations, e.g. $n_{x}^{s}=|A^{s}|$ ($A^{s}$ is as in (56)
and (57)) and $\ell^{s},u^{s}$ denotes the immediate upper and lower bound
using simplification level $s$. Further, we remind the simplification levels
are discrete, finite, and satisfy

$\displaystyle s\in\\{1,2,\ldots,n_{\mathrm{max}}\\},\ \
\ell^{s=n_{\mathrm{max}}}=-\hat{\mathcal{H}}=u^{s=n_{\mathrm{max}}}.$ (87)

Now, assume we wish to tighten $\ell^{s},u^{s}$ and move from simplification
level $s$ to $s+1$. Since the bounds are updated incrementally (as introduced
by Sztyglic and Indelman (2022)), when moving from simplification level $s$ to
$s+1$ the only additional data we are missing are the new values of the
observation and motion models for the newly added particles. Thus, we get that
the time complexity of moving from one simplification level to another is:

$\displaystyle\Theta(\ell^{s}+u^{s}\rightarrow\ell^{s+1}+u^{s+1})=\Theta((n_{x}^{s+1}-n_{x}^{s})\cdot
n_{x}\cdot t_{mot}),$ (88)

where $\Theta(\ell^{s}+u^{s}\rightarrow\ell^{s+1}+u^{s+1})$ denotes the time
complexity of updating the bounds from one simplification level to the
following one. Note the first term from (86), $n_{x}\cdot t_{obs}$, is not
present in (88). This term has nothing to do with simplification level $s$ and
it is calculated linearly over all particles $n_{x}$. Thus, it is calculated
once at the beginning (initial/lowest simplification level).

We can now deduce using (86) and (88)

$\displaystyle\Theta(\ell^{s+1}+u^{s+1})=$ (89)
$\displaystyle\Theta(\ell^{s}+u^{s})+\Theta(\ell^{s}+u^{s}\rightarrow\ell^{s+1}+u^{s+1}).$

Finally, using (85), (86), (87), (88), and (89), we come to the conclusion
that if at the end of a planning session, a node’s $b$ simplification level
was $1\leq s\leq n_{\mathrm{max}}$ than the time complexity saved for that
node is

$\displaystyle\Theta((n_{x}-n_{x}^{s})\cdot n_{x}\cdot t_{mot}).$ (90)

This makes perfect sense since if we had to resimplify all the way to the
maximal level we get $s=n_{\mathrm{max}}\Rightarrow
n_{x}^{s=n_{\mathrm{max}}}=n_{x}$ and by substituting $n_{x}^{s}=n_{x}$ in
(90) we saved no time at all.

To conclude, the total speedup of the algorithm is dependent on how many
belief nodes’ bounds were not resimplified to the maximal level. The more
nodes we had at the end of a planning session with lower simplification
levels, the more speedup we get according to (90).

## References

  * Araya et al. (2010) Araya M, Buffet O, Thomas V and Charpillet F (2010) A pomdp extension with belief-dependent rewards.  In: _Advances in Neural Information Processing Systems (NIPS)_. pp. 64–72.
  * Auer et al. (2002) Auer P, Cesa-Bianchi N and Fischer P (2002) Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ 47(2): 235–256.
  * Auger et al. (2013) Auger D, Couetoux A and Teytaud O (2013) Continuous upper confidence trees with polynomial exploration–consistency.  In: _Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part I 13_. Springer, pp. 194–209.
  * Boers et al. (2010) Boers Y, Driessen H, Bagchi A and Mandal P (2010) Particle filter based entropy.  In: _2010 13th International Conference on Information Fusion_. pp. 1–8.  10.1109/ICIF.2010.5712013.
  * Burgard et al. (1997) Burgard W, Fox D and Thrun S (1997) Active mobile robot localization.  In: _Intl. Joint Conf. on AI (IJCAI)_. Citeseer, pp. 1346–1352.
  * Crisan and Doucet (2002) Crisan D and Doucet A (2002) A survey of convergence results on particle filtering for practitioners.  _IEEE Trans. Signal Processing_ .
  * Dressel and Kochenderfer (2017) Dressel L and Kochenderfer MJ (2017) Efficient decision-theoretic target localization.  In: Barbulescu L, Frank J, Mausam and Smith SF (eds.) _Proceedings of the Twenty-Seventh International Conference on Automated Planning and Scheduling, ICAPS 2017, Pittsburgh, Pennsylvania, USA, June 18-23, 2017_. AAAI Press, pp. 70–78.
  * Egorov et al. (2017) Egorov M, Sunberg ZN, Balaban E, Wheeler TA, Gupta JK and Kochenderfer MJ (2017) Pomdps. jl: A framework for sequential decision making under uncertainty.  _The Journal of Machine Learning Research_ 18(1): 831–835.
  * Elimelech and Indelman (2022) Elimelech K and Indelman V (2022) Simplified decision making in the belief space using belief sparsification.  _The International Journal of Robotics Research_ 41(5): 470–496.
  * Farhi and Indelman (2021) Farhi E and Indelman V (2021) ix-bsp: Incremental belief space planning.  _https://arxiv.org/abs/2102.09539_ .
  * Farhi and Indelman (2019) Farhi EI and Indelman V (2019) ix-bsp: Belief space planning through incremental expectation.  In: _IEEE Intl. Conf. on Robotics and Automation (ICRA)_.
  * Fehr et al. (2018) Fehr M, Buffet O, Thomas V and Dibangoye J (2018) rho-pomdps have lipschitz-continuous epsilon-optimal value functions.  In: Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N and Garnett R (eds.) _Advances in Neural Information Processing Systems 31_. Curran Associates, Inc., pp. 6933–6943.
  * Fischer and Tas (2020) Fischer J and Tas OS (2020) Information particle filter tree: An online algorithm for pomdps with belief-based rewards on continuous domains.  In: _Intl. Conf. on Machine Learning (ICML)_. Vienna, Austria.
  * Garg et al. (2019) Garg NP, Hsu D and Lee WS (2019) Despot-$\alpha$: Online pomdp planning with large state and observation spaces.  In: _Robotics: Science and Systems (RSS)_.
  * Hoerger and Kurniawati (2021) Hoerger M and Kurniawati H (2021) An on-line pomdp solver for continuous observation spaces.  In: _IEEE Intl. Conf. on Robotics and Automation (ICRA)_. IEEE, pp. 7643–7649.
  * Hoerger et al. (2020) Hoerger M, Kurniawati H, Bandyopadhyay T and Elfes A (2020) Linearization in motion planning under uncertainty.  In: _Algorithmic Foundations of Robotics XII: Proceedings of the Twelfth Workshop on the Algorithmic Foundations of Robotics_. Springer, pp. 272–287.
  * Hoerger et al. (2019) Hoerger M, Kurniawati H and Elfes A (2019) Multilevel monte-carlo for solving pomdps online.  In: _Proc. International Symposium on Robotics Research (ISRR)_.
  * Hollinger and Sukhatme (2014) Hollinger GA and Sukhatme GS (2014) Sampling-based robotic information gathering algorithms.  _Intl. J. of Robotics Research_ : 1271–1287.
  * Indelman et al. (2015) Indelman V, Carlone L and Dellaert F (2015) Planning in the continuous domain: a generalized belief space approach for autonomous navigation in unknown environments.  _Intl. J. of Robotics Research_ 34(7): 849–882.
  * Kearns et al. (2002) Kearns M, Mansour Y and Ng AY (2002) A sparse sampling algorithm for near-optimal planning in large markov decision processes.  _Machine learning_ 49(2): 193–208.
  * Kochenderfer et al. (2022) Kochenderfer M, Wheeler T and Wray K (2022) _Algorithms for Decision Making_.  MIT Press.
  * Kocsis and Szepesvári (2006) Kocsis L and Szepesvári C (2006) Bandit based monte-carlo planning.  In: _European conference on machine learning_. Springer, pp. 282–293.
  * Kurniawati et al. (2008) Kurniawati H, Hsu D and Lee WS (2008) SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces.  In: _Robotics: Science and Systems (RSS)_.
  * Papadimitriou and Tsitsiklis (1987) Papadimitriou C and Tsitsiklis J (1987) The complexity of Markov decision processes.  _Mathematics of operations research_ 12(3): 441–450.
  * Platt et al. (2010) Platt R, Tedrake R, Kaelbling L and Lozano-Pérez T (2010) Belief space planning assuming maximum likelihood observations.  In: _Robotics: Science and Systems (RSS)_. Zaragoza, Spain, pp. 587–593.
  * Shienman and Indelman (2022) Shienman M and Indelman V (2022) Nonmyopic distilled data association belief space planning under budget constraints.  In: _Proc. of the Intl. Symp. of Robotics Research (ISRR)_.
  * Silver and Veness (2010) Silver D and Veness J (2010) Monte-carlo planning in large pomdps.  In: _Advances in Neural Information Processing Systems (NIPS)_. pp. 2164–2172.
  * Smith and Simmons (2004) Smith T and Simmons R (2004) Heuristic search value iteration for pomdps.  In: _Conf. on Uncertainty in Artificial Intelligence (UAI)_. pp. 520–527.
  * Spaan et al. (2015) Spaan MT, Veiga TS and Lima PU (2015) Decision-theoretic planning under uncertainty with information rewards for active cooperative perception.  _Autonomous Agents and Multi-Agent Systems_ 29(6): 1157–1185.
  * Stachniss et al. (2005) Stachniss C, Grisetti G and Burgard W (2005) Information gain-based exploration using Rao-Blackwellized particle filters.  In: _Robotics: Science and Systems (RSS)_. pp. 65–72.
  * Sunberg and Kochenderfer (2018) Sunberg Z and Kochenderfer M (2018) Online algorithms for pomdps with continuous state, action, and observation spaces.  In: _Proceedings of the International Conference on Automated Planning and Scheduling_ , volume 28.
  * Sutton and Barto (2018) Sutton RS and Barto AG (2018) _Reinforcement learning: An introduction_.  MIT press.
  * Sztyglic and Indelman (2022) Sztyglic O and Indelman V (2022) Speeding up online pomdp planning via simplification.  In: _IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS)_.
  * Thrun et al. (2005) Thrun S, Burgard W and Fox D (2005) _Probabilistic Robotics_.  The MIT press, Cambridge, MA.
  * Van Den Berg et al. (2012) Van Den Berg J, Patil S and Alterovitz R (2012) Motion planning under uncertainty using iterative local optimization in belief space.  _Intl. J. of Robotics Research_ 31(11): 1263–1278.
  * Walsh et al. (2010) Walsh T, Goschin S and Littman M (2010) Integrating sample-based planning and model-based reinforcement learning.  In: _Nat. Conf. on Artificial Intelligence (AAAI)_ , volume 24.
  * Ye et al. (2017) Ye N, Somani A, Hsu D and Lee WS (2017) Despot: Online pomdp planning with regularization.  _JAIR_ 58: 231–266.
  * Zhitnikov and Indelman (2022) Zhitnikov A and Indelman V (2022) Simplified risk aware decision making with belief dependent rewards in partially observable domains.  _Artificial Intelligence, Special Issue on “Risk-Aware Autonomous Systems: Theory and Practice”_ .


# HFLIC: Human Friendly Perceptual Learned
Image Compression with Reinforced Transform

Peirong Ning
Shenzhen Graduate School,
Peking University
<EMAIL_ADDRESS>Wei Jiang
Shenzhen Graduate School,
Peking University
<EMAIL_ADDRESS>Ronggang Wang
Shenzhen Graduate School,
Peking University
<EMAIL_ADDRESS>
###### Abstract

In recent years, there has been rapid development in learned image compression
techniques that prioritize rate-distortion-perceptual compression, preserving
fine details even at lower bit-rates. However, current learning-based image
compression methods often sacrifice human-friendly compression and require
long decoding times. In this paper, we propose enhancements to the backbone
network and loss function of existing image compression model, focusing on
improving human perception and efficiency. Our proposed approach achieves
competitive subjective results compared to state-of-the-art end-to-end learned
image compression methods and classic methods, while requiring less decoding
time and offering human-friendly compression. Through empirical evaluation, we
demonstrate the effectiveness of our proposed method in achieving outstanding
performance, with more than $25\%$ bit-rate saving with comparable perceptual
quality.

##  1 Introduction

Over the last few years, reducing bit rates while maintaining detail has
become increasingly challenging. This concept is formalized in the fundamental
rate-distortion trade-off, where ”rate” refers to bit rate, and ”distortion”
refers to the pairwise comparison between the input image and the
reconstruction. Classical image compression standards include JPEG [31], BPG
[4], and progressing Versatile Video Coding (VVC) [5], which try to minimize
this trade-off. These years, learned image compression (LIC), [15], [10] and
[16] has outperformed traditional methods, base on variation auto-encoders
with analysis transform, synthesis transform and entropy model. However,
purely rate-distortion optimized systems will produce artifacts in the
reconstruct images both in traditional hand-craft method or learning based
neural approaches. An increasing amount of interest has been given to
examining the reconstruction ”realistically” or ”perceptually quality”.

Existing methods [11] have accomplish pretty good performance, [25] and [3]
introduce generative adversarial network (GAN) to enhance realism in
hyperprior-based compression architecture. Additionally, [23], [24] and [19]
introduce importance maps and region-of-interest (ROI) masks to allocate more
bits to important areas, or combine multiple loss terms during the training
phase. In [1],a method which is capable of outputting a single representation
for compressed images, from which a receiver can either decode a high-realism
reconstruction or a high-PSNR reconstruction. And [28] introduce a non-binary
discriminator that is conditioned on quantized local image representations
obtained via VQ-VAE autoencoders. However, these method haven’t combine the
human friend perceptual and efficient decoding time.

Figure 1:  Diagram of the adopted framework. The right part is our enhancement
LIC. We use the same architecture of $g_{a}$, $g_{s}$, $h_{a}$ and $h_{s}$ as
the original paper ELIC[10]. SCCTX denotes the spatial-channel context model.
We use the uneven 5-group scheme with parallel context models [12]. The left
part shows the adversarial training. We use the same discriminator ($g_{d}$)
structure as HiFiC [25].

Our goal is bridge the decoding efficient and reconstruction perceptual
quality. Channel-wise auto-regressive entropy model[27] will improve
compression so much, but it will bring more time into decoding part. For most
of compression tasks, they will more care about decoding time rather than
decoding time, this inspire us to bring more expressive transforms to get
compact latent to simplify the decoder. At the same time, humans are very
sensitive to the areas where face parts appear, and distortion from perceptual
loss will distort these parts, which requires us to optimize the face parts.
Toward this goal, we explore two aspect enhancement : reinforced synthesis
transform with inverted bottleneck block and content adaptive loss. The
combined effect of these improvement is help us get a compact latent in and
simplify the decoding process, and utilize lower bit-rate to achieve
comparable visual quality against previous approaches. Our mse outperforms
recently proposed model ELIC [10] by 3.95% on Kodak[17], and save more than
$20\%$ decoding time. Additionally, we get more than $25\%$ bitrate saving on
qualitative compare with former methods.

##  2 Reinforced synthesis transform with inverted bottleneck block

Lossy image compression aims to optimize the rate distortion function
$\mathcal{R}+\lambda\mathcal{D}$. Denoting the image as $x$, encoder as
$g_{a}$ and decoder as $g_{s}$, the neural network has the following
objective:

$\mathcal{L}=\mathbb{E}[-\log p(g_{a}(x))+\lambda d(x,g_{s}(ga(x)))]$ (1)

where $\mathbb{E}$ is the expectation over $p(x)$,$g_{a}$ extracts the input
image $x$ as latent variable $\hat{y}=g_{a}(x)$ and $g_{s}$ transforms it into
reconstruction $\hat{x}$. $\mathcal{D}$, $\mathcal{R}$ are the reconstruction
distortion loss and bit-rate computed via learned prior. Auto-regressive
context model [26] is the key factor to promote compression performance by
more accurately modeling symbol probability. To be specific, the estimation of
current symbol $y_{i}$ can leverage previous symbols $y_{<i}$:

$p(y_{i}|y_{<i})=p(y_{i}|\Phi y_{<i}))$ (2)

where $\Phi$ is context model of various form [10], utilizes a spatial-channel
context modelling, using decoded point as the the reference point, uneven
grouping for channel-conditional(CC) adaptive coding. Since the later groups
need to refer to the previous decoded channel groups, more group divisions
will slower down the decoding time due to the sequential reference
relationship. For this reason, we reinforced analysis and synthesis transform.
Previous [13] inverted bottleneck in compression model method use bottleneck
block as hidden dimension is 1/2 narrower than the input dimension from ResNet
[13], and spare the latent feature. One important design from transformer
block is creates an inverted bottleneck, and the hidden dimension of MLP block
is four times wider than input dimension. And this Transformer design is
connected to the inverted bottleneck design with an expansion ratio of 4 used
in ConvNets [22]. ConvNext also illustrate how it gets the decrease in runtime
while flops increase. Inspired by this idea, we expand inverted bottleneck
design with an expansion ratio of 2, which enlarge our hidden layer and
efficiently encode the latent feature bottleneck to produce more compact
latent features with less group divisions. 111Here
https://github.com/JiangWeibeta/ELIC we borrow ELIC code, Enh-POELIC and HFLIC
code is available at https://github.com/beiluo97/HFLIC.

Figure 2:  Left one is the block designs for ResNet, which ELIC has adopted.
Middle one is our, right one is architecture of $g_{a}$ amd $g_{s}$.

##  3 Human Friendly Perceptual Loss

We take the rate-constrained RD optimization from HiFiC [25] and POELIC [11]:

$\mathcal{L}=\mathcal{D}+\lambda\cdot\mathcal{R}$ (3)

where $D$ and $R$ are (perceptual) distortion and rate terms. To focus on, Our
summarized perceptual $D$ loss function is

$\mathcal{D}=M_{perc}\circ\mathcal{L}_{perc}+M_{face}\circ\mathcal{L}_{face}$
(4)

where the perceptual region loss $\mathcal{L}_{perc}$ contain a pixel-wise
reconstruction loss $L_{recon}$ Charbonnier [18] loss, adversarial loss
$\mathcal{L}_{adv}$ [25] ,perceptual loss LPIPS-VGG $L_{lpips}$ [32], and the
style loss $\mathcal{L}_{sty}$ [9]constraining the texture consistency. We
will discuss these loss terms in detail in this section.

###  3.1 Perceptual Texture and Structure Loss

Texture and structure regions tend to have more details, and existing methods
based on perceptual optimization [20] have achieved compelling results in
texture reconstruction. Therefore, we use perceptual loss(chabonnier loss
[18], lpips [32], adversarial loss [25]) in texture regions. At the same time,
perceptual loss functions such as LPIPS, which have a large receptive field,
can introduce additional noise that is not acceptable for precise edge
reconstruction. Hence, we combine patched style loss from [11] with the
existing texture loss method. For adversarial loss, we apply hinge loss to
train a synthesizer with PatchGAN [7] discriminator. The perceptual texture
and structure formulation can be expressed as follows:

$\mathcal{L}_{perc}=\omega_{rec}\mathcal{L}_{rec}+\omega_{lpips}\mathcal{L}_{lpips}+\omega_{adv}\mathcal{L}_{adv}+\omega_{sty}\mathcal{L}_{sty}$
(5)

where $\omega_{rec}$, $\omega_{lpips}$, $\omega_{adv}$, $\omega_{sty}$ are
weights of corresponding loss metrics. Note that we use VGG as lpips and style
loss pretrained feature extraction network.

###  3.2 Human Friendly Small Face Loss

The human eye is more sensitive to certain regions [19], such as the face,
especially small details. Therefore, strict constraints should be used to
avoid deformation in these areas. In our framework, facial regions are
classified as either texture regions or optimized with perceptual loss if left
unaltered. To address this issue, we adopt a different loss function for small
faces. As people are particularly sensitive to the correctness of facial
structure, accurate reconstruction is crucial. Therefore, we use a stricter
constraint loss, the MSE loss, for facial image reconstruction.

$\mathcal{L}_{face}=\omega_{face}\cdot\mathcal{L}_{mse}$ (6)

where the Msface denotes the mask of the small face regions, and
$\mathcal{L}_{mse}$ is the Mean Squared Error(MSE), We use the well-known
YOLO-v5-face [29]to detect the faces in the image, and $L_{face}$ is only
adopted to small faces. The bitrate of the quantized latent representation
$\hat{y}$ is estimated by the entropy module denoted by
P,$R(\hat{y})=-\log(P(\hat{y}))$. Finally, the total loss function of the
whole image is summaried as:

$\mathcal{L}_{total}=M_{perc}\circ\mathcal{L}_{perc}+M_{sface}\circ\mathcal{L}_{face}+\lambda\cdot\mathcal{R}(\hat{y})$
(7)

We investigate a variety of distortion loss functions wight for all of then ,
and select the most human friendly one. Besides, adding a pixel-level mask to
MSE or MAE is easy with simple pointwise multiplication. But it is a little
harder to used on LPIPS or GAN losses, because these two loss functions
compute the feature losses and cannot correspond to mask pixel-to-pixel. Using
the methods mentioned in the [19], we give an appropriate result.

##  4 Experiments

###  4.1 Datasets and metrics

For training we utilize the train all of the picture bigger than 480x480 form
CLIC profession[30], DIV2k[2], Filckr 2K[20], ImageNet[8] and coco17[21], here
we finally have 61564 images for all models. We used the full-resolution
versions of the images. For evaluation, considering comparing with SOTA
methods, we focus most of our results in the main body on CLIC2022[30] and
kodak[17] because the first is the latest used by the neural image compression
contest, later is always used to evaluation perceptual quality.

Our evaluation metrics are reference-based metrics, computed in the form
$\rho(\hat{x},x)$, where $x$ is a ground-truth image and $\hat{x}$ is a
compressed version of $x$ . The handcrafted reference metrics of MS-SSIM and
PSNR are standards for evaluate image compression methods. A drawback of
optimization for the handcrafted metrics is that it can lead to blurring of
the reconstructed images. For this reason, other reference metrics such as
LPIPS[32], it has been developed that more heavily favor preservation of
texture and are more correlated with human judgment, but it is important to
note that as reference metrics they can still trade off some statistical
fidelity. Beside, IQT[6]and [14] that successfully applies a transformer
architecture to a perceptual full-reference. This method combines a CNN
backbone as a feature extractor, with a Transformer encoder-decoder to compare
a reference and distorted images, and predict the quality score.

Figure 3:  Comparisons of methods across various distortion and statistical fidelity metrics for the CLIC 2022 validation set. Reference models (Enh-POELIC (Ours)) achieve the best IQT score, but display poor objective fidelity as measured by PSNR and MS-SSIM. Ours is able to achieve better subjective fidelity as measured by LPIPS[32] and IQT[6] vs. HiFiC at equivalent distortion levels.. Figure 4: RD and inference time of learned image compression models. The BD-Rate data is calculated relative to VVC (YUV 444) from PSNR-BPP curve on Kodak. 222Implementations for fid, kid, dists, lpips, and iqt can be found at https://github.com/beiluo97/ImageQualityAll. Model | BD-RATE | Enc (ms) | Dec (ms)
---|---|---|---
ELIC | -6.56% | 259.4 | 240.6
ELIC-5 | - | 195.5 | 154.8
OUR | -9.87% | 243.7 | 202.4
VTM | 0 | - | -
Table 1: Rate-distortion curves of ELIC(10-slice CC), ours(5-slice CC), and
VTM[5]. The results are evaluated on Kodak. All shown learned models are
optimized for minimizing MSE. Figure 5:  Qualitative examples of compressed
image kodim18. HiFiC and Enh POELIC optimized without $\mathcal{L}_{sface}$
shows heavily distortion in human face. OUR method shows we achieve more than
$25\%$ bit-saving, and achieve better reconstruction performance. Figure 6:
Qualitative examples of compressed image kodim19. OUR method shows we achieve
more than $25\%$ bit-saving, and achieve better reconstruction performance
compare with former state-of-the-art model.

###  4.2 Baseline models

To reveal the benefits of our enhancement transform while reducing time
complexity, we refer to the training method in the ELIC and use MSE
optimization to derive perceptually base models. In order to train low-rate
models ($\lambda=\\{8,16,32,75\\}\times 10^{-4})$, we train them with a
$\lambda=0.015$ at the beginning for 500 epochs, set the initial learning rate
to 1e-4, set batch size to 8, and adjust them using target $\lambda$ values
with learning rates of 1e-4 for 100 epochs, followed 3e-5, 1e-5, 3e-6, 1e-6
for 30 epochs each. We compare coding speed of our method with ELIC[10] and
ELIC-5(5-slice CC), and the RD performance with ELIC and VTM-17.0. OUR method
out perform ELIC and VTM on RD performance regarding PSNR. And we also follow
[11] use the same loss with our network, train Enh-POELIC for comparison.

###  4.3 Quantitative results

Figure 3 illustrates the comparison of our method with other methods in terms
of statistical fidelity metrics such as PSNR, MS-SSIM, LPIPS, and IQT. Across
all bitrates, our method consistently outperforms previous work, exhibiting
superior statistical fidelity.

###  4.4 Qualitative results

In order to assess the visual quality and fidelity of the reconstructed
images, we conducted a qualitative comparison between enh-POELIC, HiFiC [25],
Content22 [19], and our proposed method. The experiments revealed that our
method achieves higher fidelity even at lower bitrates.

Figure 5 and figure 6 showcases the qualitative comparison results.

##  5 Conculusion

In this study, we propose an enhanced transform approach for human-friendly
Learned Image Compression (LIC). By combining an enhancement transform with a
human-friendly loss, our neural architecture achieves pleasant reconstructions
with fewer bits compared to previous methods. Perceptual metrics validate the
high-fidelity nature of our approach. As future work, we aim to investigate
the adaptability of the perceptual loss function.

## References

  * [1] Eirikur Agustsson, David Minnen, George Toderici, and Fabian Mentzer.  Multi-realism image compression with a conditional generator.  arXiv preprint arXiv:2212.13824, 2022.
  * [2] Eirikur Agustsson and Radu Timofte.  Ntire 2017 challenge on single image super-resolution: Dataset and study.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, July 2017.
  * [3] Eirikur Agustsson, Michael Tschannen, Fabian Mentzer, Radu Timofte, and Luc Van. Gool.  Generative adversarial networks for extreme learned image compression.  In The IEEE International Conference on Computer Vision (ICCV), October 2019.
  * [4] Fabrice Bellard.  BPG Image format.  https://bellard.org/bpg/, 2022.
  * [5] Benjamin Bross, Ye-Kui Wang, Yan Ye, Shan Liu, Jianle Chen, Gary J. Sullivan, and Jens-Rainer Ohm.  Overview of the versatile video coding (vvc) standard and its applications.  IEEE Transactions on Circuits and Systems for Video Technology, 31(10):3736–3764, 2021.
  * [6] Manri Cheon, Sung-Jun Yoon, Byungyeon Kang, and Junwoo Lee.  Perceptual image quality assessment with transformers, 2021.
  * [7] Ugur Demir and Gozde Unal.  Patch-based image inpainting with generative adversarial networks, 2018\.
  * [8] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248–255, 2009.
  * [9] Leon A. Gatys, Alexander S. Ecker, and Matthias Bethge.  Image style transfer using convolutional neural networks.  In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2414–2423, 2016.
  * [10] Dailan He, Ziming Yang, Weikun Peng, Rui Ma, Hongwei Qin, and Yan Wang.  Elic: Efficient learned image compression with unevenly grouped space-channel contextual adaptive coding.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5718–5727, 2022.
  * [11] Dailan He, Ziming Yang, Hongjiu Yu, Tongda Xu, Jixiang Luo, Yuan Chen, Chenjian Gao, Xinjie Shi, Hongwei Qin, and Yan. Wang.  Po-elic: Perception-oriented efficient learned image coding.  In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pages 1763–1768, 2022.
  * [12] Dailan He, Yaoyan Zheng, Baocheng Sun, Yan Wang, and Hongwei. Qin.  Checkerboard context model for efficient learned image compression, 2021\.
  * [13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition, 2015.
  * [14] Wei Jiang, Litian Li, Yi Ma, Yongqi Zhai, Zheng Yang, and Ronggang Wang.  Image quality assessment with transformers and multi-metric fusion modules.  In CVPR, pages 1805–1809, 2022.
  * [15] Wei Jiang, Peirong Ning, and Ronggang Wang.  Slic: Self-conditioned adaptive transform with large-scale receptive fields for learned image compression.  arXiv preprint arXiv:2304.09571, 2023.
  * [16] Wei Jiang, Jiayu Yang, Yongqi Zhai, Peirong Ning, Feng Gao, and Ronggang Wang.  Multi-reference entropy model for learned image compression.  arXiv preprint arXiv:2211.07273, 2022.
  * [17] Kodak PhotoCD dataset.  http://r0k.us/graphics/kodak/, 2022.
  * [18] Wei-Sheng Lai, Jia-Bin Huang, Narendra Ahuja, and Ming-Hsuan Yang.  Deep laplacian pyramid networks for fast and accurate super-resolution.  In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5835–5843, 2017.
  * [19] Meng Li, Shangyin Gao, Yihui Feng, Yibo Shi, and Jing. Wang.  Content-oriented learned image compression.  arXiv preprint arXiv:2207.14168, 2022.
  * [20] Bee Lim, Sanghyun Son, Heewon Kim, Seungjun Nah, and Kyoung Mu Lee.  Enhanced deep residual networks for single image super-resolution.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, July 2017.
  * [21] Tsung-Yi Lin, Michael Maire, Serge Belongie, Lubomir Bourdev, Ross Girshick, James Hays, Pietro Perona, Deva Ramanan, C. Lawrence Zitnick, and Piotr Dollár.  Microsoft coco: Common objects in context, 2014.
  * [22] Zhuang Liu, Hanzi Mao, Chao-Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie.  A convnet for the 2020s, 2022.
  * [23] Yi Ma, Yongqi Zhai, Chunhui Yang, Jiayu Yang, Ruofan Wang, Jing Zhou, Kai Li, Ying Chen, and Ronggang Wang.  Variable rate roi image compression optimized for visual quality.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1936–1940, 2021.
  * [24] Yi Ma, Yongqi Zhai, Jiayu Yang, Chunhui Yang, and Ronggang. Wang.  Afec: adaptive feature extraction modules for learned image compression.  In Proceedings of the 29th ACM International Conference on Multimedia, pages 5436–5444, 2021.
  * [25] Fabian Mentzer, George D Toderici, Michael Tschannen, and Eirikur. Agustsson.  High-fidelity generative image compression.  volume 33, 2020.
  * [26] David Minnen, Johannes Ballé, and George D Toderici.  Joint autoregressive and hierarchical priors for learned image compression.  In Advances in Neural Information Processing Systems, pages 10771–10780, 2018.
  * [27] David Minnen and Saurabh. Singh.  Channel-wise autoregressive entropy models for learned image compression, 2020.
  * [28] Matthew J Muckley, Alaaeldin El-Nouby, Karen Ullrich, Hervé Jégou, and Jakob Verbeek.  Improving statistical fidelity for neural image compression with implicit local likelihood models.  arXiv preprint arXiv:2301.11189, 2023.
  * [29] Delong Qi, Weijun Tan, Qi Yao, and Jingfeng Liu.  Yolo5face: Why reinventing a face detector.  In ArXiv preprint ArXiv:2105.12931, 2021.
  * [30] George Toderici, Wenzhe Shi, Radu Timofte, Lucas Theis, Johannes Ballé, Eirikur Agustsson, Nick Johnston, and Fabian Mentzer.  Workshop and challenge on learned image compression (clic2020), 2020.
  * [31] Gregory K Wallace.  The JPEG still picture compression standard, 1992.
  * [32] Richard Zhang, Phillip Isola, Alexei A. Efros, Eli Shechtman, and Oliver Wang.  The unreasonable effectiveness of deep features as a perceptual metric, 2018.