# Indexability and Rollout Policy for Multi-State Partially Observable
Restless Bandits

Rahul Meshram Kesav Kaza Deptt. of Elect. Comm. Engg. Deptt. of Elecl. Engg.
IIIT Allahabad Polytechnique Montreal INDIA CANADA

###### Abstract

Restless multi-armed bandits with partially observable states has applications
in communication systems, age of information and recommendation systems. In
this paper, we study multi-state partially observable restless bandit models.
We consider three different models based on information observable to decision
maker—1) no information is observable from actions of a bandit 2) perfect
information from bandit is observable only for one action on bandit, there is
a fixed restart state, i.e., transition occurs from all other states to that
state 3) perfect state information is available to decision maker for both
actions on a bandit and there are two restart state for two actions. We
develop the structural properties. We also show a threshold type policy and
indexability for model $2$ and $3.$ We present Monte Carlo (MC) rollout
policy. We use it for whittle index computation in case of model $2.$ We
obtain the concentration bound on value function in terms of horizon length
and number of trajectories for MC rollout policy. We derive explicit index
formula for model $3.$ We finally describe Monte Carlo rollout policy for
model $1$ when it is difficult to show indexability. We demonstrate the
numerical examples using myopic policy, Monte Carlo rollout policy and Whittle
index policy. We observe that Monte Carlo rollout policy is good competitive
policy to myopic.

##  I Introduction

Restless multi-armed bandits with partially observable states have been
recently found applications in online recommendation systems [1],
opportunistic communication systems [2, 3, 4], machine maintenance [5], age of
information, [6]. Restless multi-armed bandits (RMABs) are class of sequential
decision problem with multiple independent Markov processes which are coupled
via number of independent process that are activated simultaneously, [7]. In a
partially observable model, states of Markov chains are not observable at time
of decision making but signals are observable. The solution of RMAB are
computationally challenging and known to be PSPACE Hard problem, [8]. In fact
a popular heuristic Whittle index based policy have been studied and it has
shown to be asymptotically optimal, [9]. The essential idea of index policy is
to decouple the independent Markov processes (arms) by solving relaxed
constrained problem with Lagrangian method. Later one need to show
indexability for each processes and has to provide computational method for
index which maps the state of each process to a real number. The process (arm)
with the highest index is played at each time instant.

Most of RMAB problems with partially observable states are studied for two
state model with various assumptions on transition probabilities, reward
structure and observation probabilities, [1, 10, 2, 3, 4, 11, 12]. Much less
attention is given to more than two state model. Multi-state partially
observable RMAB has been studied in [13, 14, 15, 6]. In [13, 14], the
optimality of myopic policy is shown under specific model assumption for
identical communication channels. In [6], authors have proposed and analyzed
greedy policy for age of information problem. In [15], authors have studied a
pilot allocation problem in wireless networks over partially observable fading
channel with approximation on multi state model. Further, they analyzed index
policy and asymptotic optimality is proved. To derive obtain indexability, one
require to study a single armed bandit model and it is partially observable
Markov decision process (POMDP). The properties of POMDP are derived in [16].

In this paper, we study partially observable RMAB with more than two state
model. We consider three different models based on information observable to
decision maker. In first model we study with no state is observable for any
actions. In second model the decision maker can observe the perfect state for
one of the actions. In third model we assume that decision maker observes
perfect state for both actions. We obtain structural properties and discuss
about indexability for these models. We discuss simulation based MC rollout
policy. In first model, indexability is very difficult to obtain and hence use
rollout policy. In second model, we show indexability but difficult to derive
index, this motivated rollout policy based index computation method. We obtain
the concentration bound for rollout policy with threshold type structure. In
third model, we show indexability and derive explicit index formula. Finally
we illustrate performance of proposed policy using numerical examples.

The paper is organized as follows. We present model descriptions and
preliminaries in Section II. The structural properties and indexability are
developed in Section III. Monte Carlo rollout policy is discussed in Section
IV. Numerical examples and discussion are presented in Section V.

##  II Model Description

Consider $N$ partially observable restless multi-armed bandits, where
$\mathbf{M}_{i}=\\{\mathcal{S}_{i},\mathcal{A}_{i},\mathcal{P}_{i},\mathcal{R}_{i},\mathcal{O}_{i},\mathcal{Q}_{i},\beta\\},$
$i=1,2,\cdots,N.$ Let $\mathcal{S}_{i}$ be the state space,
$\mathcal{S}_{i}=\\{1,2,\cdots,n\\},$ $\mathcal{A}_{i}=\\{0,1\\}$ is action
space, $\mathcal{P}_{i}=\\{[[p_{jk}^{a}]]\\}_{\\{a\in\mathcal{A}\\}}$ is the
transition probability matrix and $p_{jk}^{a}$ is the transition probability
from state $j$ to $k$ when action $a$ is applied. The decision maker (DM) does
not observe the state of systems but makes his decisions based on the
information obtained via evolution of states. Based on this observed
information, the decision maker selects action $a_{t,i}\in\mathcal{A}_{i}$ at
time $t=1,2,\cdots.$ The state of system $i$ at time $t$ is denoted by
$s_{t,i}\in\mathcal{S}.$ A DM receives a real valued reward $r_{i}(j,a)$ if
$a_{t,i}=a$ and $s_{t,i}=j.$ The system $i$ make transition to state
$s_{t+1,i},$ and
$p_{jk}^{a}=\mathsf{Pr}\left(s_{t+1,i}=j~{}|~{}s_{t,i}=i,a_{t,i}=a\right).$ A
DM perceives one of finite number of messages. Assume that
$\mathcal{O}=\\{1,2,3,\cdots,K\\}$ represents the set of messages111Example is
a google news recommendation system, where different messages correspond to
actions of a user—like, dislike, watch later etc. The user takes different
actions with some probability based on user interest state. This generates
reward to RS based on user behavior. If the message $k\in\mathcal{O}$ is
observed with known probability from state $j$ under action $a$ for systen $i$
and this is denoted by
$q_{i,jk}^{a}=\mathsf{Pr}\left(k~{}|~{}s_{t,i}=j,a_{t,i}=a\right).$ Thus
$\mathcal{Q}_{i}=[[q_{i,jk}^{a}]]_{\\{a\in\mathcal{A}\\}}.$ The discount
parameter is denoted by $\beta.$ Each bandit evolves in discrete time steps.

An infinite horizon discounted problem with a policy $\phi$ is given as
follows.

$\displaystyle
V_{\phi}(s)=\mathrm{E}_{\phi}\left(\sum_{t=0}^{\infty}\sum_{i=1}^{N}\beta^{t}r_{i}(s_{t,i},a_{t,i})\right).$
(1)

There is an activation constrained on bandits, i.e.,
$\sum_{i=1}^{N}a_{t,i}=1.$ The policy
$\phi:H_{t}\rightarrow\\{1,2,,3,\cdots,N\\},$ where $H_{t}$ denotes the
history upto time $t,$ and $H_{t}:=\\{a_{1},o_{1},\cdots,a_{t-1},o_{t-1}\\}.$
The Markov stationary deterministic policy is studied. $V_{\phi}(s)$ is the
value function for given initial state $s.$ DM’s goal is to choose the
strategy $\phi$ to optimize $V_{\phi}(s),$ subject to constraint
$\sum_{i=1}^{N}a_{t,i}=1.$ Thus, the optimal value function is denoted by
$V^{*}.$ The discounted relaxed constrained problem using Lagrangian method is
written as follows.

$\displaystyle V_{\phi}(s)$ $\displaystyle=$
$\displaystyle\mathrm{E}_{\phi}\left(\sum_{i=1}^{N}\sum_{t=0}^{\infty}\beta^{t}\left[r_{i}(s_{t,i},a_{t,i})+W(1-a_{t,i})\right]\right).$
$\displaystyle V^{*}(s)$ $\displaystyle=$
$\displaystyle\max_{\phi\in\Phi}V_{\phi}(s).$ (2)

Here, $\Phi$ is the space of all Markov stationary deterministic policies.

###  II-A A single-armed restless bandit and preliminaries

In this section, a single armed bandit with partially observable state is
discussed and we remove dependence of arm on $i$ for notation simplicity. A
single armed restless bandit is a special case of partially observable Markov
decision processes (POMDPs). We can rewrite problem in (2) for partially
observable with belief $\pi.$ The DM only observes messages (signals) but no
state information. The DM maintains initial belief as prior
$\pi\in\Pi(\mathcal{S}),$ where
$\Pi(\mathcal{S})=\\{\pi=(\pi(1),\pi(2),\cdots,\pi(n))~{}|~{}\sum_{j=1}^{n}\pi(j)=1,0\leq\pi(j)\leq
1,\text{ for all }j\in\mathcal{S}\\}$ is belief space and $\pi(j)$ is
probability of state being $j,$ i.e., $s=j.$ Based on initial belief $\pi,$
the value function under policy $\phi$ is

$\displaystyle
V_{\phi}(\pi)=\mathrm{E}_{\phi}\left(\sum_{t=0}^{\infty}\beta^{t}\left[\sum_{j=1}^{n}r(s_{t}=j,a_{t})\pi(j)+W(1-a_{t,i})\right]\right).$

The DM optimizes the value function and it is given by

$\displaystyle V^{*}(\pi)=\max_{\phi\in\Phi}V_{\phi}(\pi).$ (3)

From [17, 18], we know that the information observed in the history $H_{t}$ is
captured in form of belief $\pi_{t}\in\Pi(\mathcal{S}),$ $\pi_{t}$ is the
Bayesian posterior over states given history

$\displaystyle\pi_{t}(j)$ $\displaystyle=$
$\displaystyle\mathsf{Pr}\left(s_{t}=j~{}|~{}H_{t}\right)$
$\displaystyle\pi_{t}(j)$ $\displaystyle=$
$\displaystyle\mathsf{Pr}\left(s_{t}=j~{}|~{}\pi_{t-1},o_{t}=k,a_{t}=a\right)$
$\displaystyle\pi_{t}$ $\displaystyle=$
$\displaystyle(\pi_{t}(1),\pi_{t}(2),\cdots,\pi_{t}(n)).$

This is shown to be sufficient information which captures all history upto
$t.$ Note that there are two actions are available to a single armed
bandit—play or not play. Corresponding to this, there are actions dependent
transition probabilities. We study the following models for a single armed
bandit based on transition probabilities and information observed from each
action.

####  II-A1 Model $1$

In this model, a decision maker does not observe state from both actions. This
is an example of two action POMDP, where action $a=1$ provides a signals and
other action $a=0$ provides no information to decision maker. For action
$a=1,$ DM observes a signal $k$ and the posterior belief is computed and the
computations are as follows. Let $\xi(j,k~{}|~{}\pi,a)$ be the probability
that the message $k$ is received from state $j$ given prior $\pi_{t}$ and
action $a,$ and $\xi(j,k~{}|~{}\pi,a)=\sum_{i\in
S}\pi_{t}(i)p_{i,j}^{a}q_{i,k}^{a}.$ Define $\sigma(k~{}|~{}\pi,a)$ is the
probability of observing message $k$ given prior $\pi_{t}$ and action $a.$ It
is given by

$\displaystyle\sigma(k~{}|~{}\pi_{t},a)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}\xi(j,k~{}|~{}\pi_{t},a)$ $\displaystyle=$
$\displaystyle\sum_{j\in S}\sum_{i\in S}\pi_{t}(i)p_{i,j}^{a}q_{i,k}^{a}.$

The Bayesian posterior given prior $\pi_{t}$ and action $a$ and signal $k$ is
denoted by $\Gamma(\pi_{t},a,k),$ and
$\Gamma_{j}(\pi,a,k)=\frac{\xi(j,k~{}|~{}\pi_{t},a)}{\sigma(k~{}|~{}\pi_{t},a)},$
$\Gamma(\pi_{t},a,k)=(\Gamma_{1}(\pi_{t},a,k),\cdots,\Gamma_{n}(\pi_{t},a,k))\in\Pi(\mathcal{S}).$
Then

$\displaystyle\pi_{t+1}(l)=\Gamma_{l}(\pi_{t},a_{t},o_{t}=k)$ $\displaystyle=$
$\displaystyle\frac{\sum_{i\in S}\pi_{t}(i)p_{i,l}^{a}q_{i,k}^{a}}{\sum_{j\in
S}\sum_{i\in S}\pi_{t}(i)p_{i,j}^{a}q_{i,k}^{a}}.$

When action $a=0,$ no signal is observed and hence the posterior belief
$\pi_{t+1}=\pi_{t}P^{0}.$

Let $B(\mathcal{S})$ be the set of bounded real valued functions on
$\Pi(\mathcal{S}).$ Define function $g:\Pi(\mathcal{S})\times\mathcal{A}\times
B(\mathcal{S})\rightarrow\mathcal{R}$ and we can write $g(\pi,a,V)$ as
function of immediate reward and future value function, thus

$\displaystyle g(\pi,a=1,V)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}\pi(j)r(j,a=1)+\beta\sum_{k\in\mathcal{O}}\sigma(k~{}|~{}\pi,a)$
$\displaystyle\times V(\Gamma(\pi,a,k))$ $\displaystyle g(\pi,a=0,V)$
$\displaystyle=$ $\displaystyle\sum_{j=1}^{n}\pi(j)r(j,a=0)+W+\beta V(\pi
P^{0})$

for $\pi\in\Pi(\mathcal{S}),$ $a\in\mathcal{A}$ and $V\in B(\mathcal{S}).$
$P^{0}$ is the transition probability for not playing arm.

An optimal dynamic programming algorithm is given as follows.

$\displaystyle V^{*}(\pi)=\max_{a\in\mathcal{A}}g(\pi,a,V^{*}).$ (4)

It is difficult to claim indexability for this model and apply index policy.
Hence we study MC rollout policy in next section.

####  II-A2 Model $2$

In this model, a decision maker takes action $a=1,$ it just provide signals
but does not provide any perfect information about state. The action $a=0$
gives perfect state information. Moreover, the transition occurs to a fixed
state $m$ which is restart state. Then the dynamic program is given as
follows.

$\displaystyle g(\pi,a=1,V)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}\pi(j)r(j,a=1)+\beta\sum_{k\in\mathcal{O}}\sigma(k~{}|~{}\pi,a)$
$\displaystyle\times V(\Gamma(\pi,a,k))$ $\displaystyle g(\pi,a=0,V)$
$\displaystyle=$ $\displaystyle\sum_{j=1}^{n}\pi(j)r(j,a=0)+W+\beta V(e_{m})$

where $e_{m}=[0,0,\cdots,1,0,\cdots,0]^{T},$ $1$ is for state $m.$ The
transition probability matrix of not playing action is $P^{0},$ and $m$th
column of it is a unit vector, i.e., all elements are $1$ and remaining
columns are zero vectors. An optimal dynamic programming algorithm is given by

$\displaystyle V^{*}(\pi)=\max_{a\in\mathcal{A}}g(\pi,a,V^{*}).$ (5)

In next section, we show that a bandit is indexable and but it is difficult to
obtain closed form expression of Whittle index.

####  II-A3 Model $3$

In this model, we further relax assumptions stated in previous models. We
assume that state is perfectly observable for both actions. Moreover for
action $a=1,$ transition from state $i$ to fixed state $m_{1}\in\mathcal{S}$
occurs with probability $1,$ $i=1,2,\cdots,n.$ Similarly, for action $a=0$ a
state transition from state $i$ to a fixed state $m_{2}\in\mathcal{S}$ occurs
with probability $1.$ The dynamic program is

$\displaystyle g(\pi,a=1,V)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}\pi(j)r(j,a=1)+\beta V(e_{m_{1}})$ $\displaystyle
g(\pi,a=0,V)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}\pi(j)r(j,a=0)+W+\beta V(e_{m_{2}})$

where $e_{m_{1}}=[0,0,\cdots,1,0,\cdots,0]^{T},$ $1$ is at position $m_{1}.$
$e_{m_{2}}=[0,0,\cdots,1,0,\cdots,0]^{T},$ $1$ is at position $m_{2}.$ An
optimal dynamic programming algorithm is

$\displaystyle V^{*}(\pi)=\max_{a\in\mathcal{A}}g(\pi,a,V^{*}).$ (6)

We will show that a bandit is indexable and even obtain the closed form
expression of Whittle index.

##  III Structural results and Indexability

In this section we provide structural results, indexability of a restless
bandits and derive index formula. We derive two key results—monotonicity of
optimal value functions and threshold type policy.

###  III-A Structural Properties

######  Lemma 1 (Convexity of value function)

For infinite horizon problem, the optimal value function $V^{*}(\pi)$ is
convex in $\pi$ for $\pi\in\Pi(S).$

Proof of this result using induction method, and it uses [19, Lemma $2$] to
prove convexity of value function. Proof is along lines of [12, Lemma $2$]. We
use maximum likelihood ratio (MLR) order for comparison of belief
$\pi^{\prime}$s MLR order is denoted as $\pi\geq_{r}\widetilde{\pi}.$ Totally
positive order $2$ ($\mathrm{TP}_{2}$) for comparison of transition
probability matrices.

######  Lemma 2 (Monotonicity of value function)

[16]: The optimal value function $V^{*}(\pi)$ is monotone in belief $\pi,$
that is, $V^{*}(\pi)\geq V^{*}(\widetilde{\pi})$ whenever
$\pi\geq_{r}\widetilde{\pi}$ for $\pi,\widetilde{\pi}\in\Pi(S)$ under
following assumptions.

  * •

reward $r(j,a)$ is non decreasing in $j\in\mathcal{S}$ for fixed $a.$

  * •

transition probability matrices $P^{1}$ and $P^{0}$ are $\mathrm{TP}_{2}$
ordered.

  * •

the observation row vector for arm $q(j)\geq q(k)$ for $j\geq i$ and
$i,j\in\mathcal{S}.$

We sketch the proof. The assumptions stated here preserves monotonocity in
belief $\Gamma,$ and $\sigma$ whenever there is ordering in prior $\pi,$
action $a$ and observation $k.$ This preserves the ordering in value functions
in belief $\pi.$ Using induction method on dynamic program and monotonicity of
value functions in belief , we get the desired result.

We note that the Lemma 1 and 2 holds for all models under different
assumptions on model. But threshold policy and indexability holds true only
for model $2$ and $3.$

A threshold type policy provides partition of belief state space $\Pi(S)$ into
three disjoint regions, $\Lambda_{1},\Lambda_{2},\Lambda_{3}\subseteq\Pi(S),$
where $\Lambda_{1}=\\{\pi\in\Pi(S):a^{*}_{t}(\pi)=1\\}$
$\Lambda_{2}=\\{\pi\in\Pi(S):a^{*}_{t}(\pi)=0\\}$ and
$\Lambda_{3}=\\{\pi\in\Pi(S):a^{*}_{t}(\pi)=1~{}\text{and }~{}0\\}.$
$a^{*}_{t}(\pi)\in\\{0,1\\}$ is the optimal action for belief $\pi$ at time
step $t.$ Illustration of this is given in Fig. 1.

$a^{*}_{t}(\pi)=1$$a^{*}_{t}(\pi)=0$$e_{1}$$e_{2}$$e_{3}$$\Lambda_{1}$$\Lambda_{2}$$\Lambda_{3}$
Figure 1: Threshold type policy illustration

######  Definition 1 (Threshold type policy)

The optimal policy is called a threshold type if one of the following holds
true.

  1. 1.

The optimal action $a_{t}^{*}(\pi)=1$ for all $t$ and all $\pi\in\Pi(S),$ that
is $\Lambda_{1}=\Pi(S)$ and $\Lambda_{2}=\Lambda_{3}=\emptyset.$

  2. 2.

The optimal action $a_{t}^{*}(\pi)=0$ for all $t$ and all $\pi\in\Pi(S),$ that
is $\Lambda_{2}=\Pi(S)$ and $\Lambda_{1}=\Lambda_{3}=\emptyset.$

  3. 3.

The optimal action $a_{t}^{*}(\pi)=1$ for all $\pi\in\Lambda_{1},$
$a_{t}^{*}(\pi)=0$ for all $\pi\in\Lambda_{2},$ and $a_{t}^{*}(\pi)=1$ and $0$
for all $\pi\in\Lambda_{3},$ that is,
$\Lambda_{1},\Lambda_{2},\Lambda_{3}\neq\emptyset.$ Also
$\Lambda_{1}\cap\Lambda_{2}\cap\Lambda_{3}=\emptyset.$

We next show a threshold policy result and indexability for model $2$ and $3.$
We make use of same assumption as stated in previous Lemma 2.

######  Lemma 3 (Threshold type policy)

In Model $2$ and Model $3,$ the optimal policy is of threshold type.

We provide a sketch of the proof. Define
$f(\pi,V^{*})=g(\pi,a=1,V^{*})-g(\pi,a=0,V^{*}).$ We show that $f(\pi,V^{*})$
is non decreasing in $\pi.$ In these model, not playing action, i.e., $a=0$
implies restart state where transition occurs to a fixed state. Thus the
future value function for action $a-0$ is constant. From definition of
$f(\pi,V^{*}),$ that term gets canceled, hence using Lemma 2, we show that
$f(\pi,V^{*})$ is non decreasing in $\pi.$ This is sufficient for threshold
type policy. Detailed proof is given in Appendix.

###  III-B Indexability and Whittle index

From threshold policy result in Lemma 3, we define

$\displaystyle
U_{1}(W):=\left\\{\pi\in\Pi(S):V(\pi,a=1,W)>V(\pi,a=0,W)\right\\}$
$\displaystyle U_{0}(W):=\left\\{\pi\in\Pi(S):V(\pi,a=1,W)\leq
V(\pi,a=0,W)\right\\}$

Hence $U_{0}(W)=\Lambda_{2}\cup\Lambda_{3}.$

######  Definition 2 (Indexability [7])

As subsidy $W$ increases from $-\infty$ to $+\infty,$ $U_{0}(W)$ increases
from $\emptyset$ to full set $\Pi(S).$

To show the indexability we require that whenever $W_{2}>W_{1}$ implies
$U_{0}(W_{1})\subseteq U_{0}(W_{2}).$ We use the following result for
indexability.

###### Lemma 4

For $\pi\in\Pi(S)$ if

$\frac{\partial V(\pi,1,W)}{\partial W}\bigg{\rvert}_{\pi=\pi_{T}(W)}\ <\
\frac{\partial V(\pi,0,W)}{\partial W}\bigg{\rvert}_{\pi=\pi_{T}(W)},$ (7)

and $\pi_{T}(W)\in\Lambda_{3},$ then $U_{0}(W)$ is a monotonically increasing
function of $W.$

Proof of this lemma is analogous to [12, Lemma $4$]. We now present main
result.

######  Theorem 1 (Indexable)

The single-armed restless hidden Markov bandit is indexable for $0<\beta<1$
and $W_{a}\leq W\leq W_{b}.$

###### Proof:

From Definition 2, we need to show that $U_{0}(W_{1})\subseteq U_{0}(W_{2})$
whenever $W_{2}>W_{1}.$ Note that $V(\pi,a=1,W)-V(\pi,a=0,W)$ is decreasing in
$W$222By induction method, one can show that $V(\pi,a=1,W)$ is non decreasing
$W$ and $V(\pi,a=0,W)$ is strictly increasing in $W$ for fixed $\beta$ and
$\pi$ for fixed $\pi,\beta.$ Therefore, equation (7) holds true. Using Lemma
4, $U_{0}(W_{1})\subseteq U_{0}(W_{2}).$ whenever $W_{2}>W_{1}$ and
$W_{1},W_{2}\in[W_{a},W_{b}].$ This completes the proof. ∎

We next define the Whittle index.

######  Definition 3 (Whittle index [7])

If an arm is indexable and is in state $\pi\in\Pi(S),$ then its Whittle index,
$W(\pi),$ is $W(\pi):=\inf_{W}\\{W:V(\pi,1,W)=V(\pi,0,W)\\}.$

$W(\pi)$ is a minimum subsidy $W$ such that the optimal action is not to play
the arm at given $\pi.$ The Whittle index formula requires explicit expression
of $V(\pi,1,W)$ and $V(\pi,0,W).$ Then we have to equate and solve this for
$W.$ For Model $2,$ the index formula is not feasible but we will provide
approximate index computation algorithm. For Model $3,$ we obtain closed form
expression of index and this is given in next lemma.

######  Lemma 5 (Whittle index formula for model $3$)

Whittle index for given belief $\pi$ is computed based on region of
$e_{m_{1}}$ and $e_{m_{2}}.$ We assume that $m_{1}>m_{2}.$

  * •

if $e_{m_{1}}\in U_{1}(W)$ and $e_{m_{2}}\in U_{0}(W),$ then

$\displaystyle
W(\pi)=(1-\beta)\left(\sum_{j=1}^{n}\left[r(j,1)-r(j,0)\right]\pi(j)\right)+$
$\displaystyle\beta\left[r(m_{1},1)-r(m_{2},0)\right]$

  * •

if $e_{m_{1}},e_{m_{2}}\in U_{1}(W)$ then

$\displaystyle W(\pi)=\sum_{j=1}^{n}\left[r(j,1)-r(j,0)\right]\pi(j)+$
$\displaystyle\beta[r(m_{1},1)-r(m_{2},1)]$

  * •

if $e_{m_{1}},e_{m_{2}}\in U_{0}(W)$ then

$\displaystyle W(\pi)=\sum_{j=1}^{n}\left[r(j,1)-r(j,0)\right]\pi(j)+$
$\displaystyle\beta\left[r(m_{1},0)-r(m_{2},0)\right].$

Proof of this is given in Appendix. When there is no reward from not playing
except subsidy $W,$ we can have $r(j,0)=0$ for all $j\in\mathcal{S}.$

##  IV Monte Carlo rollout policy

We now discuss Monte Carlo rollout policy algorithm for a single-armed bandit
in case of Model $2.$ Algorithm is based on simulations, where initial belief
state $\pi$ and a subsidy $W$ is given as input. We run multiple-trajectories,
and each trajectory consists of (belief state $\pi$, action $a$, and observed
reward $r$) Thus the information obtained from a single trajectory upto
horizon length $H$ is
$\\{\pi_{1,l},a_{1,l},r_{1,l},\pi_{2,l},a_{2,l},r_{2,l},\cdots,\pi_{H,l},a_{H,l},r_{H,l}\\}$
under policy $\phi.$ Here, $l$ denotes a trajectory. The value estimate of
$k$th trajectory starting from belief state $\pi,$ action $a=1$ and action
$a=0$ is

$\displaystyle Q_{H,l}^{\phi}(\pi,a,W)$ $\displaystyle=$
$\displaystyle\sum_{h=1}^{H}\beta^{h-1}r_{h,l}^{\phi}$ $\displaystyle=$
$\displaystyle\sum_{h=1}^{H}\beta^{h-1}r(\pi_{h,l},a_{h,l}).$

Then value estimate for state $\pi$ and action $a$ over $L$ trajectories under
policy $\phi$ is

$\displaystyle\widetilde{Q}_{H,L}^{\phi}(\pi,a,W)=\frac{1}{L}\sum_{l=1}^{L}Q_{H,l}^{\phi}(\pi,a,W).$

The output of Monte Carlo algorithm is $\widetilde{V}_{\phi,H,L}(\pi,a=1,W)$
and $\widetilde{V}_{\phi,H,L}(\pi,a=0,W).$

$\displaystyle\widetilde{V}_{\phi,H,L}(\pi,a=1,W)=r(\pi,a=1)+\widetilde{Q}_{H,L}^{\phi}(\pi,a=1,W)$
$\displaystyle\widetilde{V}_{\phi,H,L}(\pi,a=0,W)=W+r(\pi,a=0)+$
$\displaystyle\widetilde{Q}_{H,L}^{\phi}(\pi,a=1,W)$

###  IV-A Index computation for Model $2$

We present algorithm for Whittle index computation using Monte Carlo rollout
policy. It is described in Algorithm 1. Input is state $\pi,$ and initialize
value $W.$ We run Monte Carlo rollout policy under threshold policy $\phi$ for
$W$ and state $\pi.$ We obtain approximate value functions
$\widetilde{V}_{\phi,H,L}(\pi,a=1,W)$ and
$\widetilde{V}_{\phi,H,L}(\pi,a=0,W).$ If the difference between these
approximate value functions is higher than $\epsilon>9,$ then we change $W$ to
new value of $W;$ otherwise exit an algorithm with output index $=W.$ The
convergence of this algorithm follows from two-timescales stochastic
approximation algorithms, [20, Chapter $6$]. In our setting, Monte Carlo
rollout policy algorithm runs on faster timescale and the subsidy $W$ is
updated on slower timescale. We use $\gamma$ as learning rate for $W.$

Input: State of arm $\pi$

Initialize $W_{old}=W,$ $\epsilon=0.05$ $\Delta=1,$ and Stepsize $\gamma$

Define:  $W_{new}=W_{old}$

While ($\Delta>\epsilon$)

1\. Use Monte Carlo rollout policy

Compute: $\widetilde{V}_{\phi,H,L}(\pi,a=1,W_{new})$ and

$\widetilde{V}_{\phi,H,L}(\pi,a=0,W_{new})$

2\. Define
$\displaystyle\Delta(\pi,W_{new})=\widetilde{V}_{\phi,H,L}(\pi,a=1,W_{new})-$
$\displaystyle\widetilde{V}_{\phi,H,L}(\pi,a=0,W_{new})$

$W_{old}=W_{new}$

$W_{new}=W_{old}+\gamma\Delta(\pi,W_{new})$

End

3\. Output: $W(\pi)$

Algorithm 1 Whittle index computation algorithm for an arm

We derive following result with Monte Carlo rollout policy assuming there
optimal policy exists and it of threshold type, say, $\phi.$

###### Theorem 2

We assume that $r(s,a)\in[0,1],$ $0\leq W\leq 1.$ For sufficiently large
horizon length $H,$ there exist number $\widetilde{L}$ such that for all
$L>\widetilde{L}$ we have with probability $1-\frac{2}{H^{2}}$

$\displaystyle\bigg{|}V_{\phi}(\pi,a,W)-\widetilde{V}_{\phi,H,L}(\pi,a,W)\bigg{|}\leq\sqrt{\frac{z^{2}\log(H)}{L}}$

for $a\in\\{0,1\\}.$ Here, $z=\frac{(1-\beta^{H})}{1-\beta}.$

We discuss the proof idea. We simulate $L$ number of trajectories which are
are independent and cumulative reward collected along each trajectory is
random. Trajectories are generated using a fixed policy $\phi.$ We use
Hoeffding inequality [21]. The probability of deviation between the infinite
horizon discounted value function under policy $\phi$ and estimated value
function obtained using over $L$ number of simulated trajectories greater than
confidence bound decays exponentially fast. After simplifications we obtain
desired result. Detail steps are given in Appendix.

###  IV-B Monte Carlo rollout policy for Model $1$

As discussed in earlier section index policy is not applicable to Model $1,$
however we can use Monte Carlo rollout policy. Here, arm is selected based on
state-action value estimate obtained using fixed Rollout policy $\phi$ that
selects an arm at each time step. Note that we are directly applying this
policy to RMAB.

Detail of rollout policy is as follows. There are $L$ trajectories simulated
for a fixed horizon length $H$ using a known transition and reward model.
Along each trajectory, a fixed policy $\phi$ is employed according to which
one arm is played at each time step from $N$ arms. The information obtained
from a single trajectory upto horizon length $H$ is

$\displaystyle\\{\pi_{t,j,l},a_{t,j,l},r_{t,j,l}^{\phi}\\}_{j=1,t=1}^{N,H}$
(8)

under policy $\phi.$ Here, $l$ denotes a trajectory, the belief for arm $j$ is
$\pi_{t,j,l}\in\Pi(\mathcal{S}),$ action of arm $j$ is
$a_{t,j,l}\in\mathcal{A},$ moreover it has constraint
$\sum_{j=1}^{N}a_{t,j,l}=1.$ $r_{t,j,l}^{\phi}$ is reward from arm $j$ under
policy $\phi.$ The value estimate of trajectory $l$ starting from belief state
$\pi=(\pi_{1},\cdots,\pi_{N}),$ and $\pi_{j}\in\Pi(\mathcal{S})$ for $N$ arms
and initial action $\alpha\in\\{1,2,\cdots,N\\}$ and is
$Q_{H,l}^{\phi}(\pi,\alpha)=\sum_{h=1}^{H}\beta^{h-1}r_{h,l}^{\phi}=\sum_{h=1}^{H}\beta^{h-1}r(\pi_{h,l},\alpha_{h,l},\phi).$
Then, the value estimate for state $\pi$ and action $a$ over $L$ trajectories
under policy $\phi$ is

$\displaystyle\widetilde{Q}_{H,L}^{\phi}(\pi,\alpha)=\frac{1}{L}\sum_{l=1}^{L}Q_{H,l}^{\phi}(\pi,\alpha).$

We use myopic (greedy) policy as base policy $\phi$ that is implemented for a
trajectory. One step policy improvement is performed, and the optimal action
is selected according follow rule.

$\displaystyle j^{*}(\pi)=\arg\max_{1\leq j\leq
N}\left[r(\pi,\alpha=j)+\beta\widetilde{Q}_{H,L}^{\phi}(\pi,\alpha=j)\right].$
(9)

In each time step, an arm is played based on the above rule. Detailed
discussion on rollout policy for multi-action RMAB and fully observable state
is given in [22]. In next section we present numerical examples using Monte
Carlo rollout policy.

##  V Numerical Results and Discussion

We describe three numerical examples that demonstrate the performance of index
policy, myopic policy and Monte Carlo rollout policy. In the myopic policy,
the arm with highest immediate expected payoff is played at each time step. In
index policy, the arm with highest index is played.

We present first numerical example for model $1.$ We use following parameters.
The number of arms $N=15,$ number of states $n=4,$ discount parameter
$\beta=0.95,$ number of message $K=2$ and binary reward is considered for each
state. Assume that the transition probabilities and observation probabilities
are know. As the states are not observable at all in this model, we do not
make assumption on transition probabilities, i.e. $\mathrm{TP}_{2}$ order. We
compare Monte Carlo rollout policy and myopic policy. We use number of horizon
$H=5$ and number of trajectories $L=100.$ We plot iteration vs discounted
cumulative reward. We observe from Fig. 2 that Monte Carlo rollout policy
performs better than myopic policy up to $25\%.$ Though rollout policy is
computationally expensive it has advantages in terms of higher cumulative
reward.

Figure 2: Model $1:$ Myopic vs Monte Carlo rollout policy

In our second example is for model $2,$ where we consider number of arms
$N=5,$ number of states $n=4,$ $\beta=0.95,$ $K=2$ and binary reward is
obtained from each state after play of arm and no reward is obtained after not
playing of arm. In this example we compare index policy and myopic policy. We
note that index computation is performed using Monte Carlo rollout policy,
where we use $H=5.$ We observe from Fig. 3 that myopic policy performs better
than approximate index policy based algorithm. Myopic performs better by
$5\%.$ This difference is due to approximation in index computation.

Figure 3: Model $2:$ Myopic vs Approximate index policy

In our third example, we present numerical example for model $3.$ Here,
Whittle index formula is explicitly available. We compare myopic policy and
Whittle index policy for $N=15,$ $n=4$ and discount parameter $\beta=0.95.$ We
observe from Fig. 4 that Whittle index policy performs poor that myopic
policy. This is due to myopic policy plays only a fixed arm, $3$ for all times
whereas Whittle index policy plays more than one arm more frequently based on
index. In this example it suggest Whittle index policy is not optimal but it
is fair and plays other arms as well.

Figure 4: Model $3:$ Myopic vs Whittle index policy

##  VI Concluding Remarks

In this paper we studied partially observable restless multi-armed bandits. We
considered three different models based on information observable to decision
maker.

From numerical examples, it suggests that application of directly Monte Carlo
rollout policy on restless multi-armed bandits can have advantages over myopic
policy. In general, an index policy for multi state partially observable
models need not be optimal. We observed that Whittle index policy need not be
optimal even we have index formula. A simple rollout policy is competitive to
myopic policy when no index formula is available.

This opens interesting future direction of work on MC rollout policy for other
partially observable models when indexability and index computations are
infeasible.

## References

  * [1] R. Meshram, D. Manjunath, and A. Gopalan,  “A restless bandit with no observable states for recommendation systems and communication link scheduling,”  in Proc. IEEE CDC, 2015.
  * [2] Q. Zhao, B. Krishnamachari, and K. Liu,  “On myopic sensing for multi-channel opportunistic access: structure, optimality, and performance,”  IEEE Transactions on Wireless Communication, vol. 7, no. 12, pp. 5431–5440, December 2008.
  * [3] Q. Zhao, L. Tong, A. Swami, and Y. Chen,  “Decentralized cognitive MAC for opportunistic spectrum access in ad hoc networks: A POMDP framework,”  IEEE Journal on Selected Areas in Communications, vol. 25, no. 3, pp. 589–600, April 2007.
  * [4] K. Liu and Q. Zhao,  “Indexability of restless bandit problems and optimality of Whittle index for dynamic multichannel access,”  IEEE Transactions Information Theory, vol. 56, no. 11, pp. 5557–5567, November 2010.
  * [5] A. Abbou and V. Makis,  “Group maintenance: A restless bandits approach,”  INFORMS Journal of Computing, pp. 1–13, 2019.
  * [6] Y. Shao, Q.Cao, S. C. Liew, and H. Chen,  “Partially observable minimum-age scheduling: The greedy policy,”  Arxiv, pp. 1–16, 2020.
  * [7] P. Whittle,  “Restless bandits: Activity allocation in a changing world,”  Journal of Applied Probability, vol. 25, no. A, pp. 287–298, 1988\.
  * [8] C. H. Papadimitriou and J. H. Tsitsiklis,  “The complexity of optimal queueing network control,”  Mathematics of Operations Research, vol. 24, no. 2, pp. 293–305, May 1999.
  * [9] W. Ouyang, A. Eyrilmaz, and N. Shroff,  “Asymptotically optimal downlink scheduling over Markovian fading channels,”  in Proceedings of IEEE INFOCOM, 2012, pp. 1224–1232.
  * [10] J. L. Ny, M. Dahleh, and E. Feron,  “Multi-UAV dynamic routing with partial observations using restless bandit allocation indices,”  in Proceedings of American Control Conference (ACC 2008),, 2008, pp. 4220–4225.
  * [11] S. H. A. Ahmad, M. Liu, T. Javidi, and Q. Zhao,  “Optimality of myopic sensing in multichannel opportunistic access,”  IEEE Transactions on Information Theory, vol. 55, no. 9, pp. 4040–4050, September 2009.
  * [12] R. Meshram, D. Manjunath, and A. Gopalan,  “On the Whittle index for restless multi-armed hidden markov bandits,”  IEEE Transactions on Automatic Control, vol. 69, pp. 3046–3053, 2018.
  * [13] Y. Ouyang and D.Teneketzis,  “On the optimality of myopic sensing in multi-state channels,”  IEEE Transactions on Information Theory, vol. 60, pp. 681–696, 2014\.
  * [14] K. Wang, L. Chen, and Q. Liu,  “On optimality of myopic sensing policy with imperfect sensing in multi-channel opportunistic access,”  IEEE Transactions on Communications, vol. 61, no. 9, pp. 3854–3862, September 2013.
  * [15] M. Larranga, M. Assaad, A. Destounis, and G. S. Paschos,  “Asymptotically optimal pilot allocation over markovian fading channels,”  IEEE Transactions on Information Theory, vol. 64, no. 7, pp. 5395–5418, 2018.
  * [16] W. S. Lovejoy,  “Some monotonicity results for partially observed Markov decision processes,”  Operations Research, vol. 35, no. 5, pp. 736–743, October 1987\.
  * [17] D. P. Bertsekas,  Dynamic Programming and Optimal Control, vol. 1,  Athena Scientific, Belmont, Massachusetts, 1st edition, 1995.
  * [18] D. P. Bertsekas,  Dynamic Programming and Optimal Control, vol. 2,  Athena Scientific, Belmont, Massachusetts, 1st edition, 1995.
  * [19] K. J. Astrom,  “Optimal control of Markov processes with incomplete state information II. The convexity of loss function,”  Mathematical Analysis and Applications, vol. 26, no. 2, pp. 403–406, May 1969.
  * [20] V. S. Borkar,  Stochastic Approximation: A Dynamical System Viewpoint,  Cambridge University Press, 2008.
  * [21] W. Hoeffding,  “Probability inequalities for sums of bounded random variables,”  Journal of the American Statistical Association, vol. 58, no. 301, pp. 13–30, March 1963.
  * [22] R. Meshram and K. Kaza,  “Simulation based algorithms for Markov decision processes and multi-action restless bandits,” Arxiv, 2020.

###  -A Proof of Lemma 3

We now define $f$ for finite horizon as follows.

$\displaystyle
f(\pi,V^{*}_{t})=g(\pi,a,V_{t}^{*})-g(\pi,a^{\prime},V_{t}^{*})$ $a\geq
a^{\prime},$ $a,a^{\prime}\in\mathcal{A}$ (10)

We next show a threshold-type policy result and to claim this result, we
require to show that $f(\pi,V^{*}_{t})$ is nondecreasing in $\pi\in\Pi(S).$
This property also referred to as submodularity of function. Even though
optimal value function $V_{t}^{*}(\pi)$ is monotone in $\pi,$ we can not say
about this difference for model $1.$ To see this, we substitute value of $g$
in Eqn. (10), then

$\displaystyle
f(\pi,V^{*}_{t})=\sum_{i=1}^{n}\pi_{i}(r(i,a)-r(i,a^{\prime}))+$
$\displaystyle\beta\sum_{k\in
O}\sigma(k~{}|~{}\pi,a)V_{t}^{*}(\Gamma(\pi,a,k))-$
$\displaystyle\beta\sum_{k\in
O}\sigma(k~{}|~{}\pi,a^{\prime})V_{t}^{*}(\Gamma(\pi,a^{\prime},k))$ (11)

Note that monotonicity of value function, we can say that term $1$ and term
$2$ in Eqn. (11) is monotone but third term has negative sign, which
introduces difficulty for threshold policy behavior.

But in case of model $2$ and $3,$ we can claim threshold policy result. Under
structural assumption on model, i.e., $\Gamma(\pi,a^{\prime},k)=e_{i}$ where
$e_{i}$ is the unit vector of dimension $n$ with $1$ at $i$th position and
zero at remaining position. This simplifies the Eqn, (11) as follows.

$\displaystyle
f(\pi,V^{*}_{t})=\sum_{i=1}^{n}\pi_{i}(r(i,a)-r(i,a^{\prime}))+$
$\displaystyle\beta\sum_{k\in
O}\sigma(k~{}|~{}\pi,a)V_{t}^{*}(\Gamma(\pi,a,k))-$ $\displaystyle\beta
V_{t}^{*}(e_{i})$ (12)

Now observe that third term is just constant and hence we can now claim the
monotonicity of $f(\pi,V^{*}_{t})$ in $\pi$ under assumptions in Lemma 2. This
proves the threshold policy result.

∎

###  -B Proof of Lemma 5

  * •

We first derive index for $e_{m_{1}}\in U_{1}(W)$ and $e_{m_{2}}\in U_{0}(W).$
We define the action value function $V_{1}(\pi)=V(\pi,a=1)$ and
$V_{0}(\pi)=V(\pi,a=0).$

$\displaystyle V(e_{m_{1}})$ $\displaystyle=$ $\displaystyle V_{1}(e_{m_{1}})$
$\displaystyle V_{1}(e_{m_{1}})$ $\displaystyle=$ $\displaystyle
r(m_{1},1)+\beta V_{1}(e_{m_{1}}).$

Thus

$\displaystyle V(e_{m_{1}})=\frac{r(m_{1},1)}{1-\beta}.$

The action value function for action $1$ with belief $\pi$ is

$\displaystyle V_{1}(\pi)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}r(j,1)+\beta V(e_{m_{1}})$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}r(j,1)+\beta\frac{r(m_{1},1)}{1-\beta}.$

We now obtain the $V_{0}(\pi).$

$\displaystyle V_{0}(e_{m_{2}})$ $\displaystyle=$ $\displaystyle
W+r(m_{2},0)+\beta V(e_{m_{2}})$ $\displaystyle=$
$\displaystyle\frac{W+r(m_{2},0)}{1-\beta}.$ $\displaystyle
V_{0}(\pi)=W+\sum_{j=1}^{n}r(j,0)\pi(j)+\beta V(e_{m_{2}})$
$\displaystyle=W+\sum_{j=1}^{n}r(j,0)\pi(j)+\beta\left(\frac{W+r(m_{2},0)}{1-\beta}\right)$

From theshold policy we know that at $\pi$ we have $V_{1}(\pi)=V_{0}(\pi).$
After equating and solving we get

$\displaystyle
W(\pi)=(1-\beta)\left(\sum_{j=1}^{n}\left[r(j,1)-r(j,0)\right]\pi(j)\right)+$
$\displaystyle\beta\left[r(m_{1},1)-r(m_{2},0)\right].$

This is an index formula.

  * •

We now derive the index when $e_{m_{1}},e_{m_{2}}\in U_{1}(W).$ We obtain
value function expression first.

$\displaystyle V(e_{m_{1}})$ $\displaystyle=$ $\displaystyle V_{1}(e_{m_{1}})$
$\displaystyle V_{1}(e_{m_{1}})$ $\displaystyle=$ $\displaystyle
r(m_{1},1)+\beta V(e_{m_{1}})$ $\displaystyle V(e_{m_{1}})$ $\displaystyle=$
$\displaystyle\frac{r(m_{1},1)}{1-\beta},$

and

$\displaystyle V(e_{m_{2}})$ $\displaystyle=$ $\displaystyle r(m_{2},1)+\beta
V(e_{m_{1}})$ $\displaystyle V(e_{m_{1}})$ $\displaystyle=$ $\displaystyle
r(m_{2},1)+\beta\frac{r(m_{1},1)}{1-\beta}.$

Then

$\displaystyle V_{1}(\pi)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}r(j,1)\pi(j)+\beta V(e_{m_{1}})$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}r(j,1)\pi(j)+\beta\frac{r(m_{1},1)}{1-\beta}$

and

$\displaystyle V_{0}(\pi)=W+\sum_{j=1}^{n}r(j,0)\pi(j)+\beta V(e_{m_{2}})$
$\displaystyle=W+\sum_{j=1}^{n}r(j,0)\pi(j)+\beta\left[r(m_{2},1)+\beta\frac{r(m_{1},1)}{1-\beta}\right]$

After equating $V_{1}(\pi)$ and $V_{0}(\pi)$ and solving for $W,$ we have

$\displaystyle W(\pi)=\sum_{j=1}^{n}\left[r(j,1)-r(j,0)\right]\pi(j)+$
$\displaystyle\beta[r(m_{1},1)-r(m_{2},1)].$

  * •

We now derive index formula when $e_{m_{1}},e_{m_{2}}\in U_{0}(W).$ We obtain

$\displaystyle V(e_{m_{2}})$ $\displaystyle=$ $\displaystyle V_{0}(e_{m_{2}})$
(13) $\displaystyle=$ $\displaystyle W+r(m_{2},0)+\beta V(e_{m_{2}})$ (14)
$\displaystyle=$ $\displaystyle\frac{W+r(m_{2},0)}{1-\beta}.$ (15)

$\displaystyle V(e_{m_{1}})=W+r(m_{1},0)+\beta V(e_{m_{2}}).$

Then

$\displaystyle V_{1}(\pi)=\sum_{j=1}^{n}r(j,1)\pi(j)+\beta V(e_{m_{1}})$
$\displaystyle V_{2}(\pi)=W+\sum_{j=1}^{n}r(j,1)\pi(j)+\beta V(e_{m_{2}})$

After equating and solving these equations for $W,$ we obtain

$\displaystyle W(\pi)=\sum_{j=1}^{n}\left[r(j,1)-r(j,0)\right]\pi(j)+$
$\displaystyle\beta\left[r(m_{1},0)-r(m_{2},0)\right].$

∎

###  -C Proof of Theorem 2

Initial belief is $\pi_{0}=\pi.$ The immediate expected reward at time $t$ for
action $a=1$ is $r(\pi_{t},a=1)=\sum_{i\in S}\pi_{t}(i)r(i,a=1).$ We have
assumed $0<r(i,a=1)\leq 1$ Then immediate expected reward for action $a=1$ is
bounded, and $0<r(\pi_{t},a=1)\leq 1$ and here $R_{\max}=1$ and $R_{\min}=0.$
Similarly the immediate expected reward for action $a=0$ is
$0<r(\pi_{t},a=0)+W<1$ for any $\pi_{t}.$ We assume that $0\leq W\leq 1.$

We suppose that $V_{\phi}(\pi,a,W)$ is the value function for an arm under
policy $\phi,$ with initial state $\pi,$ action $a$ and subsidy $W.$

Note that $\\{Q_{h,l}^{\phi}(\pi,a,W)\\}_{l=1}^{L}$ are independent random
trajectories generated using policy $\phi$ for horizon length $H$ starting
from state $\pi,$ action $a$ and subsidy $W.$ Thus, for each trajectory $l,$
we have
$Q_{l,H}^{\phi}(\pi,a,W)\in\left[0,\frac{(1-\beta^{H})}{1-\beta}\right].$ This
is due to reward is bounded in each steps by $R_{\max}=1.$ Let
$z=\frac{(1-\beta^{H})}{1-\beta}.$

Define the action value function under policy $\phi$ is $Q^{\phi}(\pi,a,W)$
for starting belief $\pi$ and action $a.$ This is discounted cumulative
expected reward for infinite horizon problem. Thus we utilize the Hoeffding
inequality [21] for independent random bounded random variables. We have
following inequality.

$\displaystyle\mathsf{Pr}\left(\bigg{|}Q^{\phi}(\pi,a,W)-\frac{1}{L}\sum_{l=1}^{L}Q_{H,l}^{\phi}(\pi,a,W)\bigg{|}>\epsilon\right)\leq$
$\displaystyle 2\exp\left(-\frac{2L^{2}\epsilon^{2}}{Lz^{2}}\right)$

Thus RHS of preceding term is

$\displaystyle
2\exp\left(-\frac{2L^{2}\epsilon^{2}}{Lz^{2}}\right)=2\exp\left(-\frac{2L\epsilon^{2}}{z^{2}}\right)$

We want this term to $\delta$ Hence

$\displaystyle 2\exp\left(-\frac{2L\epsilon^{2}}{z^{2}}\right)=\delta$

After rearranging terms, we have

$\displaystyle\epsilon=\sqrt{\frac{z^{2}}{2L}\log\left(2/\delta\right)}$

Setting $\delta=\frac{2}{H^{2}}$ we get following inequality with probability
$1-\frac{2}{H^{2}}$

$\displaystyle\bigg{|}Q^{\phi}(\pi,a,W)-\frac{1}{L}\sum_{l=1}^{L}Q_{H,l}^{\phi}(\pi,a,W)\bigg{|}\leq\sqrt{\frac{z^{2}\log
H}{L}}$

We know that

$\displaystyle V_{\phi}(\pi,W)=\max_{a\in\\{0,1\\}}Q^{\phi}(\pi,a,W)$

Thus we can have following inequality with high probabiliy $1-\frac{2}{H^{2}}$
for sufficiently large horizon $H$ and $L>\widetilde{L}$

$\displaystyle\bigg{|}V_{\phi}(\pi,a,W)-\widetilde{V}_{\phi,H,L}(\pi,a,W)\bigg{|}\leq\sqrt{\frac{z^{2}\log
H}{L}}$

for $a\in\\{0,1\\}.$ This completes the proof.

∎


# Shape-aware Multi-Person Pose Estimation from Multi-View Images

Zijian Dong1 Jie Song1 Xu Chen1,2 Chen Guo1 Otmar Hilliges1
1ETH Zürich 2Max Planck Institute for Intelligent Systems, Tübingen

###### Abstract

In this paper we contribute a simple yet effective approach for estimating 3D
poses of multiple people from multi-view images. Our proposed coarse-to-fine
pipeline first aggregates noisy 2D observations from multiple camera views
into 3D space and then associates them into individual instances based on a
confidence-aware majority voting technique. The final pose estimates are
attained from a novel optimization scheme which links high-confidence multi-
view 2D observations and 3D joint candidates. Moreover, a statistical
parametric body model such as SMPL is leveraged as a regularizing prior for
these 3D joint candidates. Specifically, both 3D poses and SMPL parameters are
optimized jointly in an alternating fashion. Here the parametric models help
in correcting implausible 3D pose estimates and filling in missing joint
detections while updated 3D poses in turn guide obtaining better SMPL
estimations. By linking 2D and 3D observations, our method is both accurate
and generalizes to different data sources because it better decouples the
final 3D pose from the inter-person constellation and is more robust to noisy
2D detections. We systematically evaluate our method on public datasets and
achieve state-of-the-art performance. The code and video will be available on
the project page: https://ait.ethz.ch/projects/2021/multi-human-pose/.

##  1 Introduction

Markerless human motion capture is one of the fundamental problems in computer
vision. In recent years much progress has been made in estimating the
configuration of the human body in 2D [34, 50, 5, 16, 37] and 3D [4, 25, 31,
32, 52] from a single RGB image as input. However, if we consider settings in
which multiple people are depicted and in particular if these people are
interacting with each other at close range, we can expect a multitude of
difficulties due to the heavy and complicated occlusions and depth
ambiguities. To robustly estimate the poses of such groups, multi-camera
setups are indispensable to provide additional observations from different
views which can resolve occlusion and provide stereo cues for 3D estimation.

Figure 1: Shape-aware multi-person pose estimation: We propose a novel
pipeline for robust recovery of 3D poses and shapes of multiple people from a
few camera views. A formulation that links 2D and 3D observations and that is
regularized via a parametric body model is robust to noisy and missing 2D
detections. Articulated poses can even be recovered under heavy occlusion.

Due to the real-world importance of this problem, several recent approaches
have attempted to predict the poses of multiple people, observed from multiple
cameras [6, 10, 18, 54, 46, 45]. Such methods can loosely be categorized into
two groups. The first group formulates the problem as a cross-view matching
and association problem [6, 10, 54]. For example, Zhang et al. [54] introduce
an optimization formulation that attempts to jointly solve the per-view
parsing and cross-view matching problems as an instance of the multicut
problem. The formulation is based on an association graph that links joints
within and across multiple views. While the formulation is elegant, in
practice it requires traversing the dense, cyclic association graph which
results in an NP-hard problem. To attain a computationally tractable approach,
the authors revert to a greedy heuristic which is sensitive to noisy 2D joint
detections and imperfect visual features which limits the accuracy of the
method.

Other methods, such as Tu et al. [46] combine the features from individual
camera views into a 3D voxel space. This volume is then segmented into sub-
volumes by a learned person detector. The final 3D human pose configurations
are regressed from these sub-volumes. Because the pipeline can be trained end-
to-end, high accuracy can be achieved if the training and test distributions
are similar. However, owing to the reliance on the volumetric feature
representation – which encapsulates the joint distribution of different
individuals, their location in 3D space, the camera setup and even the 2D
joint detections – learning such a representation requires a vast amount of
data. In the absence of a large corpus of annotated multi-people, multi-view
data, such methods face generalization issues and are sensitive to
distribution shifts (Tab. 4).

Embracing this challenging problem, we propose a simple yet effective coarse-
to-fine pipeline to estimate 3D multi-person poses from multi-view images. Our
method combines concepts from both bottom-up and top-down methods. To avoid
having to solve the association problem with partial local evidence, we
aggregate initial 3D pose proposals in a 3D feature space. Our first insight
is that, in pose estimation, the uncertainty associated with the 2D features
(i.e., joint detections) can be trusted more than in many other computer
vision domains due to semantics. Thus we forgo neural-network based
classifiers and propose a simple confidence-aware majority voting technique to
obtain initial 3D proposals. We experimentally show that it is more robust to
distribution differences in terms of human poses, location of individuals and
cameras in space and thus leads to better generalization behavior. This coarse
3D localization step is followed by a refinement step to correct poses and
fill in missing joints via an optimization scheme that leverages multi-view
constraints directly, where high confidence 2D observations are available, and
regularizes the 3D pose via a parametric body model.

More precisely, the first part of our pipeline consists of triangulating the
3D coordinates of all pairs of 2D detections with the same part label. This is
followed by a confidence-aware majority voting technique to cluster the
proposals. The technique is based on the insight that if a joint has been seen
and predicted accurately (i.e., with high confidence) in several views, then
there will be a dense cluster of 3D candidates for that joint and low
confidence, isolated candidates can be discarded. Furthermore, we leverage the
observation that certain joints, for example, the hip, are detected more
reliably than end-effectors and can be used as a heuristic to decide the
number and location of individual humans. While simple, experiments (Tab. 1)
show that our approach outperforms the SOTA learning-based method [46] and
matching-based method [54] in terms of the detection performance.

The second part of our pipeline refines the initial 3D estimates based on a
novel 2D-3D objective (Eq.(5)). In our formulation, we optimize the 3D joint
locations directly by minimizing the 2D re-projection error if the
corresponding 2D joint detections are of high confidence (Eq.(1)). To
regularize the fitting procedure and to attain complete and kinematically
plausible poses we leverage SMPL for low-confidence 3D candidates (Eq.(3)).
Importantly, the SMPL parameters are aligned directly to the updated 3D
observations (current state of the 3D joint locations). For this we use the
learned per-parameter gradient method (Eq.(6)). This approach is fundamentally
different from most existing approaches [4] that fit SMPL parameters directly
to 2D observations. We experimentally show that the triangulated 3D joints are
more accurate than the PCA-based SMPL skeleton – if they stem from confident
2D observations (Fig. 4). Both initial 3D pose proposal and SMPL parameters
are optimized in an alternating manner (Alg. 1). This is motivated by the
insight that a good estimate of 3D poses helps in fitting SMPL, while better
SMPL estimates make 3D poses more robust. Finally, detailed experiments are
performed to demonstrate that both components improve the robustness and
accuracy of the pose estimation task. In summary, our main contributions are:

  * •

A coarse-to-fine confidence-aware pipeline to aggregate noisy 2D observations
from all camera views into 3D space and associate them into individual
instances.

  * •

A novel refinement pipeline which optimizes 3D poses and their corresponding
SMPL models in an alternating fashion. The parametric models help in
regularizing low-confidence 3D poses while updated 3D poses in turn guide the
SMPL parameter estimation.

  * •

Our method is general since we only leverage off-the-shelf 2D pose detector
and body pose priors distilled from motion capture datasets. SOTA performance
is achieved on public datasets.

##  2 Related Work

A vast amount of work on single-person 3D pose estimation from monocular [36,
40, 11, 47, 9, 26, 40, 8] and multi-view [20, 17, 39] images exists. Since we
study the setting of multi-person pose estimation from multiple views [28, 23,
10, 54, 24, 1, 2, 12], the focus of this literature review is on multi-person
pose estimation.

Multi-Person 2D Pose Estimation
A natural approach to multi-person 2D pose estimation is to detect people
first and then estimate the body pose independently. Pishchulin et al. [38]
employs a pictorial structure model to locate the person and subsequently
estimate the pose. More recent top-down approaches also follow a similar
strategy but instead use CNN-based person detectors and pose estimation models
[51, 16, 14, 27, 49].

In contrast, bottom-up approaches [37, 33, 35, 5, 7, 43] begin with localizing
identity-free body part proposals and associates them into individual
instances. The seminal work by Pishchulin et al. [37] proposed a framework
that jointly labels part candidates and also associates them into individual
people. More recently, Cao et al. [5] introduced a representation of pairwise
scores via the so-called Part Affinity Fields (PAF). The authors demonstrated
that PAFs are able to provide effective features for the part association that
a simple greedy bipartite parse can be directly applied achieving state-of-
the-art results.

Multi-Person 3D Pose Estimation
When only one camera is available, the problem is under-determined since many
3D poses may correspond to the same 2D pose. Leveraging the learning-based
method, 3D poses can be recovered by lifting detected 2D poses [41, 42, 55],
or directly regressing 3D poses [48, 13, 53, 3], or by fitting parametric
human body models [21, 53]. However, the reconstruction accuracy of these
methods is limited due to the depth ambiguities and strong occlusions when
multiple humans are close to each other.

Most closely related to ours are methods that leverage multi-view images. A
straightforward approach for this problem is to find correspondences across
views, either leveraging high-level features such as human instances, or low-
level features such as joints. Early work implicitly solves this matching and
parsing problem by leveraging 3D pictorial structure models, in which nodes
represent 3D locations of body joints and edges encode pairwise relations
between them [2]. However, such methods are computationally expensive due to
the large state space in 3D. Joo et al. [23] rely on local features from dense
multi-view images to vote for possible 3D joint positions, which can be seen
as an implicit form of matching.

The method proposed by Dong et al. [10] first performs per-view person
parsing, followed by a cross-view person matching via a convex optimization
method constrained by cycle consistency. In [54], the authors formulate
parsing, matching, and tracking in a unified graph optimization framework to
simultaneously address 4D information. In contrast to these matching-based
methods, a recent work [46] directly localizes all people and estimates their
corresponding 3D poses in 3D voxel space. Due to the reliance on the 3D
feature representation as input for subsequent learning-based steps, this
method faces challenges in generalization with different configurations of
people, poses and cameras. In our work, we propose a simple yet effective
pipeline that triangulates joint candidates and associates them into
individual instances via a simple confidence-aware voting scheme. A 2D-3D
optimization technique, optimized via learned gradient descent, produces
highly accurate 3D pose estimates. We show that this pipeline outperforms both
matching-based approaches and end-to-end learning methods.

##  3 Method

Figure 2: Pipeline structure. Stage i@: (a): We apply a 2D human pose
estimation method [5] to obtain 2D joint candidates. (b): 2D candidate pairs
with the same part label are triangulated into 3D space to produce 3D joint
candidates. (c): A confidence-aware voting-based algorithm is used for
clustering joint candidates from partial observations. (d): The position of
human instances can be detected based on a reliable joint. (e): For each 3D
human proposal, we project it back into the image space and leverage the part
affinity field feature (PAF [5]) to filter the joint candidates from closely
interacting people and obtain initial 3D pose proposals. Stage ii@: We refine
the initial 3D poses $X_{0}$ by optimizing a 2D-3D objective. Both 3D poses
$X$ and SMPL parameters $\Theta$ are optimized alternatively. For each
iteration, the 3D joint locations $X$ are optimized by a 2D re-projection
error when the corresponding 2D joint detections are of high confidence. To
obtain kinematically plausible poses, we leverage updated SMPL estimation for
regularizing the low-confidence 3D joint candidates. The SMPL parameters
$\Theta$ are encouraged to align to the updated 3D poses in each iteration via
a learned gradient updating network. After a small number of iteration, our
method can generate complete and accurate 3D human poses and output SMPL
parameters.

Fig. 2 provides an overview of our proposed approach, which contains two
stages: 3D human proposal generation and shape-aware 3D pose optimization.

In the first stage, we generate 3D joint candidates by triangulating 2D human
pose estimates from different views. Then a confidence-aware voting-based
technique is applied to cluster joint candidates from noisy observations and
determine human instances. To generate a pose proposal for each human
instance, a 3D bounding box is placed around its hip and is projected back to
the images. The image observations surrounding the body’s limbs are used to
filter joint candidates from closely interacting people.

In the second stage, an energy formulation which includes a multi-view re-
projection term $E_{2d}(X)$ and a 3D body model fitting term
$E_{shape}(X,\Theta)$ is introduced, to refine the initial pose $X_{0}$. Both
3D poses $X$ and SMPL parameters $\Theta$ are optimized jointly in an
alternating manner. For each iteration, the gradient updating network first
takes current 3D poses $X$ and SMPL estimation $\Theta$ as input to guide
updating SMPL prediction. Then the current 3D poses $X$ are optimized by
minimizing the multi-view re-projection error when they stem from confident 2D
observations and the updated SMPL prediction is leveraged for regularizing
low-confidence or missing 3D joint candidates. After a small number of
iterations, our method can generate complete and accurate 3D human poses.

###  3.1 3D Human Proposal Generation

One of the main challenges for multi-person pose estimation from multiple
views is to associate 2D poses from different views with consistent
identities. Prior matching-based work [54], is sensitive to imperfect 2D
detections due to its local heuristic, and purely learning-based methods [46,
18] are prone to overfitting. In contrast, we propose an effective approach to
generate initial 3D pose proposals based on a confidence-aware voting
technique, operating in the global 3D space of joint candidates that have been
triangulated from pairs of 2D noisy detections.

3D Joint Candidates Reconstruction.
To reconstruct 3D joint candidates, we first run an off-the-shelf 2D human
pose detector [5] on each input image to generate 2D joint detections (Fig. 2,
(a)). Then pairs of joints with the same label from different views are
triangulated into 3D joint candidates (Fig. 2, (b)). We use standard linear
algebraic triangulation [15], solving the linear system defined on the
homogeneous 3D coordinate vector $\tilde{y_{j}}:A_{j}\tilde{y_{j}}=0$, where
$A_{j}\in\mathbb{R}^{(2C,4)}$ is a matrix composed of the components from the
projection matrices and 2D poses. In our case, we perform the triangulation
from each pair of 2D poses and set $C$ to 2.

Candidates Association.
The next step is to associate triangulated 3D joint candidates into individual
instances. Our insight for the association is simple: since we triangulate
pairs of joint detections, joints that are visible in several views produce
dense clusters of 3D candidates. Based on this observation, we propose an
efficient and effective voting-based algorithm.

For the set $C_{i}$ of all the 3D joint candidates with part label $i$, we
initialize an empty set $S_{i}$ and update it iteratively. In each iteration,
we first find the point $p_{k}$ with the highest confidence in $C_{i}$. Next,
a subset $s_{k}\in C_{i}$ containing all the neighboring 3D candidates around
$p_{k}$ with a distance less than threshold $\rho$ is selected. We add $s_{k}$
to $S_{i}$ and remove $s_{k}$ from $C_{i}$. We repeat the above until $C_{i}$
becomes the empty set. Since outliers usually stem from falsely associated 2D
detections or wrong detections in one specific view, there will only be few
neighboring candidates around them. We thus eliminate clusters with less than
three points. For the remaining clusters, we use their center to represent its
position in 3D.

Human Proposal Generation.
The filtered 3D joint candidates need to be associated with individual
instances. We experimentally find that the hip joint is one of the most
reliable parts and can be leveraged to robustly decide the number of instances
and also the location of each instance. Hence, we simply place a 3D bounding
box with fixed size and orientation using the hip candidates as anchors.
Furthermore, we keep the anchors whose corresponding 3D bounding box contains
more than 90% of body parts and whose average confidences are larger than an
empirically derived threshold. These bounding boxes may still contain joints
of other closely interacting people. In order to distinguish them, we project
the 3D bounding box back to the image space and use the part affinity fields
[5] to determine which 3D joints belong to other person instances.

###  3.2 Shape-aware 3D Pose Optimization

The initial pose proposals do not yet adhere to kinematic constraints and may
have missing joints due to imperfect 2D joint detections. We refine these
initial poses $X$ via both multi-view re-projection evidence $E_{2d}(X)$ and a
parametric body model prior $E_{shape}(X,\Theta)$. The 3D poses $X$ and SMPL
parameters $\Theta$ are optimized alternatively. The re-projection term aligns
3D joints $X$ with the 2D observations for high-confidence joint detections.
Whereas missing or low-confidence joints are determined by leveraging the
updated SMPL estimation to regularize the 3D pose, leading to complete and
kinematically plausible 3D pose estimates. For SMPL parameters $\Theta$, they
are optimized to align to the current 3D joints $X$ via a learned gradient
updating network. This refinement finally leads to complete and kinematically
plausible 3D pose estimates after a small number of iterations. The
alternating process is shown in Fig. 2<EMAIL_ADDRESS>
Objectives.
Given an initial 3D pose proposal $X$ and its corresponding 2D observations
$x_{ij}$, where $i\in(1\ldots N)$ stands for the joint label and $j\in(1\ldots
K)$ represents the view indices, we want to refine the 3D pose by leveraging
multi-view constraints where the 2D observations have high confidence:

$E_{2D}(X)=\sum_{i=1}^{N}\sum_{j=1}^{K}w_{ij}\delta_{ij}d_{2D}(\Pi_{j}X_{i},x_{ij})\quad$
(1)

Here $E_{2D}(X)$ denotes the re-projection error between the 2D joint
projections into each view and the detected 2D joints. $\Pi_{j}$ is the
projection matrix of view $j$. $w_{ij}$ is the confidence of detected joint
$i$ in the view $j$ and $\delta_{ij}$ is an indicator function denoting if
joint $i$ in view $j$ is discarded:

$\delta_{ij}=\begin{cases}1,&d_{2D}(\Pi_{j}X_{i},x_{ij})<\rho_{2D}\cr
0,&\text{otherwise}\end{cases}$ (2)

where $\rho_{2D}$ is a threshold for selecting inliers.

To complement $E_{2D}$ we leverage a body shape term $E_{shape}$ to regularize
the 3D pose via a parametric body model when 2D detections are missing or have
low associated confidence. For this purpose, we use the SMPL model[29]. It is
a differentiable function that outputs a triangulated mesh $M(\theta,\beta)$
taking the pose parameters $\theta\in\mathbb{R}^{23\times 3}$ and the shape
parameters $\beta\in\mathbb{R}^{10}$ as input. The 3D body joints can be
obtained by a linear regressor $W$ taking the mesh as input
($\bar{X}(\theta,\beta)=W(M(\theta,\beta))$). We jointly optimize predicted 3D
poses $X$ and SMPL parameters $\theta,\beta$:

$E_{shape}(X,\theta,\beta)=\sum_{i=1}^{N}\delta(w_{i})d_{3D}(X_{i},\bar{X}_{i}(\theta,\beta))$
(3)

where $w_{i}$ is the average confidence of detected 2D joint $i$ across views.
$\delta(w_{i})$ is an indicator function denoting whether the initial 3D
joints $i$ has high enough confidence:

$\delta(w_{i})=\begin{cases}1,&w_{i}<\rho_{3D}\cr 0,&otherwise\end{cases}$ (4)

The final energy is the weighted sum of Eq. (1) and (3):

$E(X,\theta,\beta)=w_{2D}E_{2D}(X)+w_{shape}E_{shape}(X,\theta,\beta).$ (5)

Algorithm 1 \- Alternative Optimization

$X_{0}\leftarrow$ initial 3D pose proposal

$\Theta_{0}\leftarrow\\{\theta_{0},\beta_{0}\\}\leftarrow 0$

for $n=0,...,N-1$ do

$\Theta^{(0)}\leftarrow\Theta_{n}$

for $m=0,...,M-1$ do

$\mathcal{L}_{shape}(\Theta^{(m)})\leftarrow E_{shape}(X_{n},\Theta^{(m)})$

$\Delta\Theta^{(m)}\leftarrow\mathcal{N}_{w}(\frac{\partial\mathcal{L}_{shape}(\Theta^{(m)}}{\partial\Theta^{(m)}},\Theta^{(m)},{X_{n}})$

$\Theta^{(m+1)}\leftarrow\Theta^{(m)}+\Delta\Theta^{(m)}$

end for

$\Theta_{n+1}\leftarrow\Theta^{(M)}$

$\mathcal{L}(X_{n})\leftarrow
w_{2d}E_{2d}(X_{n})+w_{shape}E_{shape}(X_{n},\Theta_{n+1})$

$X_{n+1}=X_{n}+\lambda\frac{\partial\mathcal{L}(X_{n})}{\partial X_{n}}$

end for

Alternating Optimization.
To optimize Eq. (5) we employ a custom gradient descent strategy. We start by
fixing $X$ to its initial value and optimize $\theta,\beta$. Since fitting
SMPL parameters to 3D observations is a non-convex and highly non-linear
problem, this can be slow and error-prone with traditional methods such as
that by Bogo et al. [4]. We take inspiration from a recent 2D-3D lifting
approach [44] that solves the fitting of 3D human body by leveraging a neural
network to predict the parameter update rule. We adopt a similar concept for
fitting the human model to the 3D candidates. To accelerate fitting of
$\Theta=\\{\theta,\beta\\}$ we replace the standard gradient descent rule by a
learned per-parameter update:

$\Theta^{(m+1)}=\Theta^{(m)}+\mathcal{N}_{w}(\frac{\partial
E_{shape}}{\partial\Theta^{(m)}},\Theta^{(m)},X)\quad$ (6)

where $\mathcal{N}_{w}$ is a deep network parameterized by a set of weights
$w$, $\frac{\partial E_{shape}}{\partial\Theta^{(m)}}$ is the partial
derivative wrt $\Theta$ and $X$ is the fitting target. $\mathcal{N}_{w}$ is
trained with samples of poses and shapes from AMASS [30]. Please refer to [44]
and supplementary for more details of the training process.

Once $\Theta$ is optimized, we keep it fixed and optimize $X$ via standard
gradient descent. We optimize $X,\Theta$ in an alternating fashion until
convergence. The overall routine is detailed as pseudo-code in Alg. 1, where
$n$ is the iteration index for the overall optimization routine while $m$ is
for the body fitting process.

##  4 Experiments

###  4.1 Test Datasets

We conduct experiments on two standard datasets for multi-view multi-person 3D
human pose estimation, which consist of challenging scenarios including
interactions between individuals with heavy occlusions.

Shelf [1] contains 3200 frames from 5 cameras. In terms of evaluation setting
and evaluation metric, we follow prior work [1, 46, 54] and test on a separate
test set and report the percentage of correctly estimated parts<EMAIL_ADDRESS>to
measure performance.

Association Dataset [54] is one of the most challenging public datasets for
this task. It contains 3 sequences with 2-4 closely interacting people
observed from 6 cameras. Following [54], we use all the sequences for test and
report the precision, recall and F1-score as evaluation metrics. A joint is
considered correct if its Euclidean distance to the ground truth annotation is
less than 0.2m.

###  4.2 Training Data Comparison

For training, our method only uses AMASS, a collection of 3D human bodies with
varying poses [30]. For clarity, we would like to emphasize that our primary
goal is to boost the robustness and effectiveness to new, entirely unseen
humans and poses. Note that, learning-based methods [46, 18] generally require
direct 3D supervision via annotated pairs of multi-people, multi-view data.

Figure 3:  Comparison between our initial poses and final poses after
optimization. (a) The orange circle is set for missing joints (note that we
set the missing joints to the origin point) (b) The blue circle is set for
incorrect joint predictions;(c) The purple circle is set for abnormal human
poses. After the shape-aware optimization, our method generates more complete
and accurate 3D human poses.

###  4.3 Ablation Study

To validate the effectiveness of our method, we conduct a detailed analysis on
both the initial 3D pose proposal and the shape-aware pose refinement. All the
experiments are conducted on the Association dataset. When comparing with the
learning-based method [46], we deploy its model trained on the CMU Panoptic
Dataset [22], which is the largest training dataset for this task.

####  4.3.1 Evaluation of 3D Human Proposal Generation

To evaluate the effectiveness of our human proposal generation technique, we
compare our method with two SOTA methods [46, 54]. Following the metric of
[54], one human proposal is valid if the error of its hip joint is less than
0.2m. As shown in Tab. 1, our method achieves significantly better performance
compared to [54, 46]. The learning-based method [46] faces generalization
issues to unseen human poses and motion. The bottom-up method [54] suffers
from low recall since the greedy algorithm is sensitive to noisy 2D joint
detections. More ablation study on the proposal generation can be found in the
supplementary.

Method | Precision(%) | Recall(%) | F1-score(%)
---|---|---|---
VoxelPose [46] | 68.8 | 77.3 | 72.8
Zhang _et al._ [54] | 99.6 | 51.2 | 67.6
Ours | 98.8 | 94.2 | 96.4

Table 1: Evaluation of human proposal generation on the Association Dataset. A
human proposal is valid if the error of its hip joint is less than 0.2m. Ours
achieves better performance compared to other SOTA ones especially for recall.

####  4.3.2 Evaluation of Shape-aware Pose Optimization

In this section, we validate the effectiveness of our shape-aware
optimization. As seen in the last two rows in Tab. 4, the initial pose
proposal can be dramatically improved under all metrics by leveraging multi-
view constraints and regularization with the parametric body model. There are
two main reasons for this improvement. First, the full-body constraint of SMPL
can infill missing joints and corrects implausible poses (see orange and
purple circles in Fig. 3). Furthermore, the weighted re-projection error
contributes to refine the joint predictions, shown in blue circles in Fig. 3.

Human Body Constraint. Note that the SMPL model is used as a full-body
constraint to help infill missing joints and also to correct non-kinematic
poses. We conduct the experiment to fit SMPL model to the initial 3D proposal
and draw the MPJPEs of the joints before and after fitting in Fig. 4. For
joints with associated low average confidence, regularizing the 3D pose via a
parametric body model can boost performance. For joints with higher confidence
(confidence$>$0.25), the effect of full-body constraint is not obvious. This
is caused by a slight difference in the skeletal configurations between [5]
and [29], which causes some systematic error. Therefore we only use the multi-
view constraints to optimize high-confidence joints as described in the method
section.

Figure 4:  Comparison of MPJPE (m) between our initial proposals (init) and
the predicted poses after regularizing with SMPL (after smpl). The horizontal
axis represents the associated confidence of the 3D joints from the initial
proposal. When the confidence is under 0.25, our algorithm achieves better
performance after regularizing the 3D pose via a parametric body model.

Comparison with SMPL-only. We compare our method with approaches that optimize
only SMPL parameters to align the joint re-projections with 2D observations
[4, 19]. For a fair comparison, we apply a multi-view variant of SMPLify. The
comparison on the Association dataset is summarized in Tab. 2. Our method
outperforms the SMPL-only baseline by a significant margin. This is in part
due to the inherent approximation error stemming from differences in the
skeletal configurations between [5] and [29] in part due to fitting errors.
This experimental evidence is an important motivation for the design of our 3D
pose fitting formulation. Furthermore, leveraging learned gradient descent for
optimization leads to significant performance increases both in terms of
runtime (20x speed-up, 0.1s vs 2s), convergence rate (14 vs 100 iters) and
precision (90.1% vs 78.3%).

Method | Precision(%) | Recall(%) | F1-score(%)
---|---|---|---
Multi-view SMPLify [4] | 78.3 | 77.4 | 77.8
Ours | 90.1 | 89.0 | 89.2

Table 2: Comparison between our method and the traditional method [4] Our
method outperforms the SMPL-only baseline for both precision and recall.
Figure 5:  Qualitative comparison with VoxelPose [46] and Zhang et al. [54] on
the Association Dataset. Different colors stand for different types of errors:
red rectangles for extra actors; blue circles for incorrect joint positions;
purple circles for abnormal human poses. Each row is an independent sample and
the results are the projected 2D poses from the 3D predictions. Our method is
more accurate compared to others especially in challenging scenarios with
strong occlusions or highly articulated poses.

Method | Anno | A1 | A2 | A3 | Avg
---|---|---|---|---|---
VoxelPose [46] | Yes | 99.3 | 94.1 | 97.6 | 97.0
Huang _et al._ [18] | Yes | 98.8 | 96.2 | 97.2 | 97.3
Belagiannis _et al._ [1] | No | 66.1 | 65.0 | 83.2 | 71.4
Belagiannis _et al._ [2] | No | 75.3 | 69.7 | 87.6 | 77.5
Ershadi-Nasab _et al._ [12] | No | 93.3 | 75.9 | 94.8 | 88.0
*Zhang _et al._ [54] | No | 96.5 | 86.8 | 97.0 | 93.4
Dong _et al._ [10] | No | 98.6 | 93.7 | 97.8 | 96.7(96.9)
Ours(final) | No | 99.1 | 93.5 | 98.1 | 96.9

Table 3: Evaluation on Shelf dataset. Quantitative comparison on the Shelf
dataset using a percentage of correct parts (PCP) metric. ’*’ denotes that the
method discards temporal information from its original setting. ‘A1’-‘A3’
correspond to the results of three actors, respectively. The averaged result
is in column ‘Avg’. The column ’Anno’ indicates if the method relies on 3D
supervision.

Method | Precision(%) | Recall(%) | F1-score(%)
---|---|---|---
VoxelPose [46] | 55.1 | 66.5 | 60.3
*Zhang _et al._ [54] | 97.1 | 48.8 | 65.0
†VoxelPose [46] | 68.8 | 79.2 | 73.6
Dong _et al._ [10] | 71.0 | 80.2 | 75.3
Ours(init) | 83.7 | 82.8 | 83.4
Ours(final) | 90.1 | 89.0 | 89.2

Table 4: Evaluation on the Association Dataset. ’*’ denotes that the method
discards temporal information from its original setting. ’†’ means the method
uses 3D bounding box ground truth.  Figure 6:  Results of our method on (a)
Association Dataset(6 views) and (b) Shelf (5 views). The 2D reprojections of
predicted 3D skeletons and SMPL mesh model are shown in two different views
(left and middle); Skeletons and SMPL models of all the actors in 3D are
demonstrated in the right column. More results can be found in the
supplementary.

###  4.4 Quantitative Results

We compare our method with SOTA methods quantitatively on the Shelf and
Association datasets. The comparison on the Shelf is shown in Tab. 3. We
achieve slightly better results compared to methods [1, 2, 10, 12, 54] which
do not rely on 3D supervision and achieve comparable performance compared to
learning-based methods [46, 18] which train the model based on this dataset.
Since the test frames lack pose variations compared to the training set, this
dataset is considered less challenging than the Association one, which also
has a more strict evaluation metric.

The quantitative result on the Association dataset is shown in Tab. 4. Since
this is a pure test set, for SOTA learning-based method [46], we directly
deploy their trained model for test. As a result, our method outperforms this
learning-based method largely, even when they use ground truth 3D bounding
boxes. This shows that the learning-based method is prone to overfit to the
training distribution. We also compare our algorithm with matching-based
methods [10, 54]. Note that to have a fair comparison with [54], we compare
with its static version only relying on images while it is originally a
tracking method which leverages video information. We can see that these
bottom-up based methods have relatively low recall due to the fact that they
solve the global optimization with a greedy algorithm which is sensitive to
missing 2D joint detections.

###  4.5 Qualitative Comparison

We show qualitative comparison in Fig. 5. Generally, our method is more
accurate and robust compared to others especially in challenging scenarios
with strong occlusions or when highly articulated poses are presented.
Specifically, other methods tend to generate extra actors (red rectangles),
abnormal (purple circles) or incorrect (blue circles) human poses. The reason
is that it is difficult for the learning-based method [46] to generalize to
unseen poses and motions. For the image-based version of [54], without
temporal information, solving the 3D association graph is sensitive to noisy
2D joint detections. In Fig. 6, we demonstrate more results of our method on
both the Association and Shelf datasets. The first row is the predicted 3D
poses and their projections on two views. The second row shows the predicted
SMPL models in 3D space and also their projections in 2D images.

##  5 Conclusion

In this paper, we propose an effective coarse-to-fine pipeline to estimate 3D
multi-person poses from multi-view images. To avoid having to solve the
association problem with local evidence, we aggregate initial 3D pose
proposals in a 3D feature space and associate them into individual instances.
This coarse 3D localization step is followed by a refinement step that
corrects poses and fills in missing joints via an optimization routine
leveraging multi-view constraints directly where high confidence 2D
observations are available and regularizing the 3D pose via a parametric body
model. We systematically evaluate our method on public datasets and SOTA
performance is achieved.

Acknowledgements: Xu Chen was supported by the Max Planck ETH Center for
Learning Systems.

## References

  * [1] Vasileios Belagiannis, Sikandar Amin, Mykhaylo Andriluka, Bernt Schiele, Nassir Navab, and Slobodan Ilic.  3d pictorial structures for multiple human pose estimation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1669–1676, 2014.
  * [2] Vasileios Belagiannis, Sikandar Amin, Mykhaylo Andriluka, Bernt Schiele, Nassir Navab, and Slobodan Ilic.  3d pictorial structures revisited: Multiple human pose estimation.  IEEE transactions on pattern analysis and machine intelligence, 38(10):1929–1942, 2015.
  * [3] Abdallah Benzine, Florian Chabot, Bertrand Luvison, Quoc Cuong Pham, and Catherine Achard.  Pandanet: Anchor-based single-shot multi-person 3d pose estimation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6856–6865, 2020.
  * [4] Federica Bogo, Angjoo Kanazawa, Christoph Lassner, Peter Gehler, Javier Romero, and Michael J Black.  Keep it smpl: Automatic estimation of 3d human pose and shape from a single image.  In European Conference on Computer Vision, pages 561–578. Springer, 2016.
  * [5] Zhe Cao, Gines Hidalgo, Tomas Simon, Shih-En Wei, and Yaser Sheikh.  Openpose: realtime multi-person 2d pose estimation using part affinity fields.  arXiv preprint arXiv:1812.08008, 2018.
  * [6] He Chen, Pengfei Guo, Pengfei Li, Gim Hee Lee, and Gregory Chirikjian.  Multi-person 3d pose estimation in crowded scenes based on multi-view geometry.  arXiv preprint arXiv:2007.10986, 2020.
  * [7] Bowen Cheng, Bin Xiao, Jingdong Wang, Honghui Shi, Thomas S Huang, and Lei Zhang.  Higherhrnet: Scale-aware representation learning for bottom-up human pose estimation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5386–5395, 2020.
  * [8] Stefano Corazza, Lars Mündermann, Emiliano Gambaretto, Giancarlo Ferrigno, and Thomas P Andriacchi.  Markerless motion capture through visual hull, articulated icp and subject specific model generation.  International journal of computer vision, 87(1-2):156, 2010.
  * [9] Edilson De Aguiar, Carsten Stoll, Christian Theobalt, Naveed Ahmed, Hans-Peter Seidel, and Sebastian Thrun.  Performance capture from sparse multi-view video.  In ACM SIGGRAPH 2008 papers, pages 1–10. 2008.
  * [10] Junting Dong, Wen Jiang, Qixing Huang, Hujun Bao, and Xiaowei Zhou.  Fast and robust multi-person 3d pose estimation from multiple views.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7792–7801, 2019.
  * [11] Ahmed Elhayek, Edilson de Aguiar, Arjun Jain, Jonathan Tompson, Leonid Pishchulin, Micha Andriluka, Chris Bregler, Bernt Schiele, and Christian Theobalt.  Efficient convnet-based marker-less motion capture in general scenes with a low number of cameras.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3810–3818, 2015.
  * [12] Sara Ershadi-Nasab, Erfan Noury, Shohreh Kasaei, and Esmaeil Sanaei.  Multiple human 3d pose estimation from multiview images.  Multimedia Tools and Applications, 77(12):15573–15601, 2018.
  * [13] Matteo Fabbri, Fabio Lanzi, Simone Calderara, Stefano Alletto, and Rita Cucchiara.  Compressed volumetric heatmaps for multi-person 3d pose estimation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7204–7213, 2020.
  * [14] Hao-Shu Fang, Shuqin Xie, Yu-Wing Tai, and Cewu Lu.  RMPE: Regional multi-person pose estimation.  In ICCV, 2017.
  * [15] Richard Hartley and Andrew Zisserman.  Multiple view geometry in computer vision.  Cambridge university press, 2003.
  * [16] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In The IEEE International Conference on Computer Vision (ICCV), 2017\.
  * [17] Yihui He, Rui Yan, Katerina Fragkiadaki, and Shoou-I Yu.  Epipolar transformer for multi-view human pose estimation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 1036–1037, 2020.
  * [18] Congzhentao Huang, Shuai Jiang, Yang Li, Ziyue Zhang, Jason Traish, Chen Deng, Sam Ferguson, and Richard Yi Da Xu.  End-to-end dynamic matching network for multi-view multi-person 3d pose estimation.
  * [19] Yinghao Huang, Federica Bogo, Christoph Lassner, Angjoo Kanazawa, Peter V Gehler, Javier Romero, Ijaz Akhter, and Michael J Black.  Towards accurate marker-less human shape and pose estimation over time.  In 2017 international conference on 3D vision (3DV), pages 421–430. IEEE, 2017.
  * [20] Karim Iskakov, Egor Burkov, Victor Lempitsky, and Yury Malkov.  Learnable triangulation of human pose.  In Proceedings of the IEEE International Conference on Computer Vision, pages 7718–7727, 2019.
  * [21] Wen Jiang, Nikos Kolotouros, Georgios Pavlakos, Xiaowei Zhou, and Kostas Daniilidis.  Coherent reconstruction of multiple humans from a single image.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5579–5588, 2020.
  * [22] Hanbyul Joo, Hao Liu, Lei Tan, Lin Gui, Bart Nabbe, Iain Matthews, Takeo Kanade, Shohei Nobuhara, and Yaser Sheikh.  Panoptic studio: A massively multiview system for social motion capture.  In Proceedings of the IEEE International Conference on Computer Vision, pages 3334–3342, 2015.
  * [23] Hanbyul Joo, Tomas Simon, Xulong Li, Hao Liu, Lei Tan, Lin Gui, Sean Banerjee, Timothy Godisart, Bart Nabbe, Iain Matthews, et al.  Panoptic studio: A massively multiview system for social interaction capture.  IEEE transactions on pattern analysis and machine intelligence, 41(1):190–204, 2017.
  * [24] Hanbyul Joo, Tomas Simon, and Yaser Sheikh.  Total capture: A 3d deformation model for tracking faces, hands, and bodies.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8320–8329, 2018.
  * [25] Angjoo Kanazawa, Michael J Black, David W Jacobs, and Jitendra Malik.  End-to-end recovery of human shape and pose.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7122–7131, 2018.
  * [26] Roland Kehl and Luc Van Gool.  Markerless tracking of complex human motions from multiple views.  Computer Vision and Image Understanding, 104(2-3):190–209, 2006\.
  * [27] Jiefeng Li, Can Wang, Hao Zhu, Yihuan Mao, Hao-Shu Fang, and Cewu Lu.  Crowdpose: Efficient crowded scenes pose estimation and a new benchmark.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 10863–10872, 2019.
  * [28] Yebin Liu, Juergen Gall, Carsten Stoll, Qionghai Dai, Hans-Peter Seidel, and Christian Theobalt.  Markerless motion capture of multiple characters using multiview image segmentation.  IEEE transactions on pattern analysis and machine intelligence, 35(11):2720–2735, 2013.
  * [29] Matthew Loper, Naureen Mahmood, Javier Romero, Gerard Pons-Moll, and Michael J Black.  Smpl: A skinned multi-person linear model.  ACM transactions on graphics (TOG), 34(6):1–16, 2015.
  * [30] Naureen Mahmood, Nima Ghorbani, Nikolaus F Troje, Gerard Pons-Moll, and Michael J Black.  Amass: Archive of motion capture as surface shapes.  In Proceedings of the IEEE International Conference on Computer Vision, pages 5442–5451, 2019.
  * [31] Julieta Martinez, Rayat Hossain, Javier Romero, and James J Little.  A simple yet effective baseline for 3d human pose estimation.  In Proceedings of the IEEE International Conference on Computer Vision, pages 2640–2649, 2017.
  * [32] Dushyant Mehta, Srinath Sridhar, Oleksandr Sotnychenko, Helge Rhodin, Mohammad Shafiei, Hans-Peter Seidel, Weipeng Xu, Dan Casas, and Christian Theobalt.  Vnect: Real-time 3d human pose estimation with a single rgb camera.  ACM Transactions on Graphics (TOG), 36(4):1–14, 2017.
  * [33] Alejandro Newell, Zhiao Huang, and Jia Deng.  Associative embedding: End-to-end learning for joint detection and grouping.  arXiv preprint arXiv:1611.05424, 2016.
  * [34] Alejandro Newell, Kaiyu Yang, and Jia Deng.  Stacked hourglass networks for human pose estimation.  In European conference on computer vision, pages 483–499. Springer, 2016.
  * [35] George Papandreou, Tyler Zhu, Liang-Chieh Chen, Spyros Gidaris, Jonathan Tompson, and Kevin Murphy.  Personlab: Person pose estimation and instance segmentation with a bottom-up, part-based, geometric embedding model.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 269–286, 2018.
  * [36] Georgios Pavlakos, Xiaowei Zhou, Konstantinos G Derpanis, and Kostas Daniilidis.  Harvesting multiple views for marker-less 3d human pose annotations.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6988–6997, 2017.
  * [37] Leonid Pishchulin, Eldar Insafutdinov, Siyu Tang, Bjoern Andres, Mykhaylo Andriluka, Peter Gehler, and Bernt Schiele.  Deepcut: Joint subset partition and labeling for multi person pose estimation.  arXiv preprint arXiv:1511.06645, 2015.
  * [38] Leonid Pishchulin, Arjun Jain, Mykhaylo Andriluka, Thorsten Thormählen, and Bernt Schiele.  Articulated people detection and pose estimation: Reshaping the future.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 3178–3185. IEEE, 2012.
  * [39] Haibo Qiu, Chunyu Wang, Jingdong Wang, Naiyan Wang, and Wenjun Zeng.  Cross view fusion for 3d human pose estimation.  In Proceedings of the IEEE International Conference on Computer Vision, pages 4342–4351, 2019.
  * [40] Edoardo Remelli, Shangchen Han, Sina Honari, Pascal Fua, and Robert Wang.  Lightweight multi-view 3d pose estimation through camera-disentangled representation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6040–6049, 2020.
  * [41] Gregory Rogez, Philippe Weinzaepfel, and Cordelia Schmid.  Lcr-net: Localization-classification-regression for human pose.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3433–3441, 2017.
  * [42] Gregory Rogez, Philippe Weinzaepfel, and Cordelia Schmid.  Lcr-net++: Multi-person 2d and 3d pose detection in natural images.  IEEE transactions on pattern analysis and machine intelligence, 42(5):1146–1161, 2019.
  * [43] Jie Song, Bjoern Andres, Michael J Black, Otmar Hilliges, and Siyu Tang.  End-to-end learning for graph decomposition.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10093–10102, 2019.
  * [44] Jie Song, Xu Chen, and Otmar Hilliges.  Human body model fitting by learned gradient descent.  In Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XX 16, pages 744–760. Springer, 2020.
  * [45] Jie Song, Limin Wang, Luc Van Gool, and Otmar Hilliges.  Thin-slicing network: A deep structured model for pose estimation in videos.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4220–4229, 2017.
  * [46] Hanyue Tu, Chunyu Wang, and Wenjun Zeng.  Voxelpose: Towards multi-camera 3d human pose estimation in wild environment.  ECCV, 2020.
  * [47] Daniel Vlasic, Ilya Baran, Wojciech Matusik, and Jovan Popović.  Articulated mesh animation from multi-view silhouettes.  In ACM SIGGRAPH 2008 papers, pages 1–9. 2008.
  * [48] Can Wang, Jiefeng Li, Wentao Liu, Chen Qian, and Cewu Lu.  Hmor: Hierarchical multi-person ordinal relations for monocular multi-person 3d pose estimation.  In European Conference on Computer Vision, pages 242–259. Springer, 2020.
  * [49] Jingdong Wang, Ke Sun, Tianheng Cheng, Borui Jiang, Chaorui Deng, Yang Zhao, Dong Liu, Yadong Mu, Mingkui Tan, Xinggang Wang, et al.  Deep high-resolution representation learning for visual recognition.  IEEE transactions on pattern analysis and machine intelligence, 2020\.
  * [50] Shih-En Wei, Varun Ramakrishna, Takeo Kanade, and Yaser Sheikh.  Convolutional pose machines.  In CVPR, pages 4724–4732, 2016.
  * [51] Shih-En Wei, Varun Ramakrishna, Takeo Kanade, and Yaser Sheikh.  Convolutional pose machines.  In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 4724–4732, 2016.
  * [52] Andrei Zanfir, Elisabeta Marinoiu, and Cristian Sminchisescu.  Monocular 3d pose and shape estimation of multiple people in natural scenes-the importance of multiple scene constraints.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2148–2157, 2018.
  * [53] Andrei Zanfir, Elisabeta Marinoiu, Mihai Zanfir, Alin-Ionut Popa, and Cristian Sminchisescu.  Deep network for the integrated 3d sensing of multiple people in natural images.  Advances in Neural Information Processing Systems, 31:8410–8419, 2018.
  * [54] Yuxiang Zhang, Liang An, Tao Yu, Xiu Li, Kun Li, and Yebin Liu.  4d association graph for realtime multi-person motion capture using multiple video cameras.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1324–1333, 2020.
  * [55] Jianan Zhen, Qi Fang, Jiaming Sun, Wentao Liu, Wei Jiang, Hujun Bao, and Xiaowei Zhou.  Smap: Single-shot multi-person absolute 3d pose estimation.  In European Conference on Computer Vision, pages 550–566. Springer, 2020.