I am reading papers about I-POMDP. I cant understand the finitely nested I-POMDPs given in these papers.


The belief update of the algorithm has a problem that agents' belief updates mutually depend on each others. For instance, the update functions for a system containing agent i and agent j are list as follows.
\begin{equation}
b\_i^t(is\_i^t) = \tau\_{m\_j^{t-1}} (b\_i^{t-1}(is\_i^{t-1});o\_i^t,a\_i^{t-1}) = \beta \sum\_{is\_i^{t-1} \vert \hat{\theta}\_j^{t-1} = \hat{\theta}\_j^t} {b\_i^{t-1}(is\_i^{t-1}) \sum\_{a\_j^{t-1}}{P(a\_j^{t-1}\vert m\_j^{t-1})P(o\_i^t \vert s^t,a^{t-1})P(s^t \vert a^{t-1},s^{t-1})\sum\_{o\_j^t}{\delta\_K(\tau\_{m\_i^{t-1}}(b\_j^{t-1} ; o\_j^t , a\_j^{t-1})-b\_j^t) P(o\_j^t \vert s^t , a^{t-1})}}}
\end{equation}
\begin{equation}
b\_j^t(is\_j^t) = \tau\_{m\_i^{t-1}} (b\_j^{t-1}(is\_j^{t-1});o\_j^t,a\_j^{t-1}) = \beta \sum\_{is\_j^{t-1} \vert \hat{\theta}\_i^{t-1} = \hat{\theta}\_i^t} {b\_j^{t-1}(is\_j^{t-1}) \sum\_{a\_i^{t-1}}{P(a\_i^{t-1}\vert m\_i^{t-1})P(o\_j^t \vert s^t,a^{t-1})P(s^t \vert a^{t-1},s^{t-1})\sum\_{o\_i^t}{\delta\_K(\tau\_{m\_j^{t-1}}(b\_i^{t-1} ; o\_i^t , a\_i^{t-1})-b\_i^t) P(o\_i^t \vert s^t , a^{t-1})}}}
\end{equation}
As you can see above, calculation of $\tau\_{m\_j^{t-1}} (b\_i^{t-1}(is\_i^{t-1});o\_i^t,a\_i^{t-1})$ and $\tau\_{m\_i^{t-1}} (b\_j^{t-1}(is\_j^{t-1});o\_j^t,a\_j^{t-1})$ depend on the outcome of each other. 


The papers discussing this topic give a solution called finitely nested I-POMDPs. The solution update the belief with subintentional model first for level 0. The belief update is as follows.
\begin{equation}
b\_{i,0}^t(is\_{i,0}^t) = b^t\_{i,0}(s^t) = \beta \sum\_{is\_i^{t-1} \vert \hat{\theta}\_j^{t-1} = \hat{\theta}\_j^t} {b\_{i,0}^{t-1}(is\_{i,0}^{t-1}) \sum\_{a\_j^{t-1}}{P(a\_j^{t-1}\vert m\_j^{t-1})P(o\_i^t \vert s^t,a^{t-1})P(s^t \vert a^{t-1},s^{t-1})\sum\_{o\_j^t}{\delta\_K(\text{APPEND}(h\_j^{t-1},o\_j^t),h\_j^t) P(o\_j^t \vert s^t , a^{t-1})}}}
\end{equation}
\begin{equation}
b\_{j,0}^t(is\_{j,0}^t) = b^t\_{j,0}(s^t) = \beta \sum\_{is\_j^{t-1} \vert \hat{\theta}\_i^{t-1} = \hat{\theta}\_i^t} {b\_{j,0}^{t-1}(is\_{j,0}^{t-1}) \sum\_{a\_i^{t-1}}{P(a\_i^{t-1}\vert m\_i^{t-1})P(o\_j^t \vert s^t,a^{t-1})P(s^t \vert a^{t-1},s^{t-1})\sum\_{o\_i^t}{\delta\_K(\text{APPEND}(h\_i^{t-1},o\_i^t),h\_i^t) P(o\_i^t \vert s^t , a^{t-1})}}}
\end{equation}
Seemingly, the two update functions dont depend on each other now. But how could I do for level 1? I know I should solve the following updates for level 1.
\begin{equation}
b\_{i,1}^t(is\_{i,1}^t) = b\_{i,1}(s^t, \langle b\_{j,0}^t , \hat{m}\_j^t \rangle)
\end{equation}
\begin{equation}
b\_{j,1}^t(is\_{j,1}^t) = b\_{j,1}(s^t, \langle b\_{i,0}^t , \hat{m}\_i^t \rangle)
\end{equation}
How to do the update on level 1 to avoid mututal dependence? I can't understand the solution from the papers. Thanks for any hints.



how to resolve the infinite nesting of interactive POMDP
The seeming circular dependence of belief update of agent i and agent j can be better understood when you refer to section 6 of the paper. There, the finitely nested IPOMDPs are introduced. One can see that agent i's beliefs nested down to level l are spanned over the physical states S and models of the agent j, M\_{j,l-1}, i.e., models of j nested down to level l-1. So, for finitely nested IPOMDPs the belief update is recursive: agent i models agent j's belief update 
at level l-1, and j models i's belief update at level l-2, etc. Recursion bottoms out at the "flat", 0-level POMDP belief update.


Hope this helps!


--Piotr 


