\documentclass[11pt,twoside]{article}
\usepackage{jair}
\usepackage{theapa}
\input epsf
%\usepackage{proceed2e}
\usepackage{graphicx}
\usepackage{times}
\usepackage{latexsym}
\usepackage{helvet}
\usepackage{courier}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
% ----------------------------------------------------------------
\vfuzz2pt % Don't report over-full v-boxes if over-edge is small
\hfuzz2pt % Don't report over-full h-boxes if over-edge is small
% THEOREMS -------------------------------------------------------
\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}{Lemma}
\newtheorem{prop}{Proposition} 
\newtheorem{defn}{Definition}
\newtheorem{rem}[thm]{Remark}
% MATH -----------------------------------------------------------
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}
\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\Real}{\mathbb R}
\newcommand{\eps}{\varepsilon}
\newcommand{\To}{\longrightarrow}
\newcommand{\BX}{\mathbf{B}(X)}
\newcommand{\A}{\mathcal{A}}
\def\Sym#1{{\mbox{\it #1}}}

\jairheading{24}{2005}{49-79}{09/04}{07/05}
\ShortHeadings{A  Framework for Sequential  Planning in  Multi-Agent Settings}
{Gmytrasiewicz \& Doshi}
\firstpageno{49}


%\input{../psfig.sty}
\newcommand{\xyfig}[4]{
\begin{figure}[htp]
\centerline{\psfig{figure=#1,width=#3in,height=#4in}}
\caption{#2}
\label{fig:#1}
\end{figure}
}

% ---------------------------------------------------------------
%\oddsidemargin=0in \topmargin=0.0in \textwidth=6.0in
%\textheight=9.0in
%\pagestyle{empty}
% ----------------------------------------------------------------
\begin{document}

\title{A  Framework for Sequential  Planning in  Multi-Agent Settings}
%\author{Piotr   J.   Gmytrasiewicz and Prashant  Doshi\thanks{This
%research is supported by  the National Science Foundation CAREER %award
%IRI-9702132,  and NSF  award IRI-0119270.}\\ Department  of %Computer
%Science\\    University     of    Illinois    at     Chicago \\
%\{piotr,pdoshi\}@cs.uic.edu
%}
\author{\name Piotr  J. Gmytrasiewicz \email  piotr@cs.uic.edu\\ \name
Prashant  Doshi
\email pdoshi@cs.uic.edu\\ \addr Department of Computer
Science\\  University of  Illinois at  Chicago \\  851 S.  Morgan St\\
Chicago, IL 60607}
\maketitle
%\thispagestyle{empty}
% ----------------------------------------------------------------
\begin{abstract}

This  paper  extends  the  framework of  partially  observable  Markov
decision processes  (POMDPs) to multi-agent  settings by incorporating
the  notion of  agent models  into the  state space.   Agents maintain
beliefs over  physical states  of the environment  and over  models of
other agents, and they use  Bayesian updates to maintain their beliefs
over time. The solutions map belief states to actions. Models of other
agents may include their belief  states and are related to agent types
considered in games of incomplete information.  We express the agents'
autonomy by postulating that their models are not directly manipulable
or observable by  other agents.  We show that  important properties of
POMDPs,  such   as  convergence  of  value  iteration,   the  rate  of
convergence,  and  piece-wise linearity  and  convexity  of the  value
functions  carry over to  our framework.   Our approach  complements a
more  traditional approach  to  interactive settings  which uses  Nash
equilibria  as a  solution paradigm.   We seek  to avoid  some  of the
drawbacks of  equilibria which  may be non-unique  and do  not capture
off-equilibrium  behaviors.   We  do  so  at the  cost  of  having  to
represent,  process and  continuously  revise models  of other  agents.
Since  the  agent's beliefs  may  be  arbitrarily  nested, the  optimal
solutions  to   decision  making  problems   are  only  asymptotically
computable.   However, approximate  belief  updates and  approximately
optimal  plans are  computable. We  illustrate our  framework  using a
simple application domain, and we  show examples of belief updates and
value functions. 
\end{abstract}

%----------------------------------------------------------------------
\section{Introduction}
\label{sec:intro}
%----------------------------------------------------------------------

We develop a framework for sequential rationality of autonomous agents
interacting with other agents within a common, and possibly uncertain,
environment.   We  use the  normative  paradigm of  decision-theoretic
planning under  uncertainty formalized as  partially observable Markov
decision                       processes                      (POMDPs)
\cite{Boutilier99:Decision,Kaelbling98:Planning,Russell03:Artificial}
as  a point of  departure. Solutions  of POMDPs  are mappings  from an
agent's beliefs  to actions. The drawback  of POMDPs when  it comes to
environments populated  by other agents is that  other agents' actions
have to  be represented implicitly as environmental  noise within the,
usually  static, transition  model.   Thus, an  agent's beliefs  about
another agent are not part of solutions to POMDPs.

The main  idea behind our  formalism, called {\bf  interactive POMDPs}
(I-POMDPs), is to allow agents to use more sophisticated constructs to
model and predict behavior of other agents.  Thus, we replace ``flat''
beliefs about  the state space used  in POMDPs with  beliefs about the
physical environment  {\em and} about the other  agent(s), possibly in
terms of  their preferences, capabilities, and  beliefs.  Such beliefs
could include others' beliefs about  others, and thus can be nested to
arbitrary  levels.  They  are called  interactive beliefs.   While the
space of interactive  beliefs is very rich and  updating these beliefs
is more complex than updating  their ``flat'' counterparts, we use the
value function plots  to show that solutions to  I-POMDPs are at least
as good  as, and in usual  cases superior to,  comparable solutions to
POMDPs. The reason is intuitive -- maintaining sophisticated models of
other agents allows more refined analysis of their behavior and better
predictions of their actions.

I-POMDPs  are  applicable  to  autonomous self-interested  agents  who
locally  compute what actions  they should  execute to  optimize their
preferences given what they believe while interacting with others with
possibly   conflicting   objectives.    Our   approach  of   using   a
decision-theoretic  framework  and  solution concept  complements  the
equilibrium approach  to analyzing  interactions as used  in classical
game  theory \cite{Fudenberg91:Game}.  The  drawback of  equilibria is
that  there could  be many  of  them (non-uniqueness),  and that  they
describe agent's optimal actions only if, and when, an equilibrium has
been reached  (incompleteness). Our approach, instead,  is centered on
optimality and best response  to anticipated action of other agent(s),
rather then  on stability \cite{Binmore90:Essays,Kadane82:Subjective}.
The question  of whether, under  what circumstances, and what  kind of
equilibria could arise from solutions to I-POMDPs is currently open.

Our   approach   avoids  the   difficulties   of  non-uniqueness   and
incompleteness  of   traditional  equilibrium  approach,   and  offers
solutions  which  are  likely  to  be better  than  the  solutions  of
traditional  POMDPs   applied  to  multi-agent   settings.  But  these
advantages  come at the  cost of  processing and  maintaining possibly
infinitely nested interactive beliefs.  Consequently, only approximate
belief  updates  and   approximately  optimal  solutions  to  planning
problems are  computable in  general.  We define  a class  of finitely
nested  I-POMDPs to  form  a basis  for  computable approximations  to
infinitely  nested ones.   We show  that a  number of  properties that
facilitate solutions of POMDPs carry over to finitely nested I-POMDPs.
In particular,  the interactive beliefs are  sufficient statistics for
the  histories  of  agent's  observations,  the  belief  update  is  a
generalization  of  the  update  in  POMDPs,  the  value  function  is
piece-wise  linear  and  convex,  and the  value  iteration  algorithm
converges at the same rate.

The remainder of this paper is structured as follows.  We start with a
brief review  of related work  in Section~\ref{sec:rel-work}, followed
by an  overview of partially  observable Markov decision  processes in
Section~\ref{sec:pomdps}.   There, we  include a  simple example  of a
tiger   game.   We   introduce   the  concept   of   agent  types   in
Section~\ref{sec:type}.       Section~\ref{sec:ipomdps}     introduces
interactive POMDPs  and defines  their solutions. The  finitely nested
I-POMDPs,   and   some  of   their   properties   are  introduced   in
Section~\ref{sec:finite}.  We continue  with an example application of
finitely nested I-POMDPs to a multi-agent version of the tiger game in
Section~\ref{sec:tiger}. There, we show examples of belief updates and
value functions.   We conclude with  a brief summary and  some current
research  issues  in  Section~\ref{sec:conclusion}.   Details  of  all
proofs are in the Appendix.

%-------------------------------------------------------------------
\section{Related Work}
\label{sec:rel-work}
%-------------------------------------------------------------------

Our  work draws  from prior  research on  partially  observable Markov
decision processes,  which recently gained  a lot of  attention within
the                            AI                            community
\cite{Smallwood73:Optimal,Monahan82:Survey,Lovejoy91:Survey,Hauskrecht97:Planning,Kaelbling98:Planning,Boutilier99:Decision,Hauskrecht00:Value}.

The  formalism  of Markov  decision  processes  has  been extended  to
multiple  agents  giving rise  to  stochastic  games  or Markov  games
\cite{Fudenberg91:Game}.  Traditionally, the solution concept used for
stochastic games is  that of Nash equilibria.  Some  recent work in AI
follows                         that                         tradition
\cite{Littman94:Markov,Hu98:Theoretical,Boutilier99:Sequential,Koller01:Multi-Agent}.
However, as we  mentioned before, and as has been  pointed out by some
game theorists \cite{Binmore90:Essays,Kadane82:Subjective}, while Nash
equilibria are  useful for describing  a multi-agent system  when, and
if,  it has  reached  a stable  state,  this solution  concept is  not
sufficient as a  general control paradigm.  The main  reasons are that
there may  be multiple  equilibria with no  clear way to  choose among
them  (non-uniqueness), and the  fact that  equilibria do  not specify
actions in cases in which agents believe that other agents may not act
according to their equilibrium strategies (incompleteness).

Other  extensions  of  POMDPs   to  multiple  agents  appeared  in  AI
literature recently \cite{Bernstein02:Complexity,Nair03:Taming}.  They
have been called decentralized POMDPs (DEC-POMDPs), and are related to
decentralized control  problems \cite{Ooi96:Decentralized}.  DEC-POMDP
framework assumes  that the agents  are fully cooperative,  i.e., they
have  common reward  function  and  form a  team.  Furthermore, it  is
assumed that the optimal joint solution is computed centrally and then
distributed among  the agents for execution.  
%This method is  related to multi-body planning
%\cite{Russell03:Artificial}.

From  the game-theoretic  side,  we are  motivated  by the  subjective
approach to probability  in games \cite{Kadane82:Subjective}, Bayesian
games    of   incomplete    information    \cite<see>[and   references
therein]{Fudenberg91:Game,Harsanyi67:Games},   work   on   interactive
belief                                                          systems
\cite{Harsanyi67:Games,Mertens85:Formulation,Brandenburger93:Hierarchies,Fagin95:Reasoning,Aumann99:Interactive,Fagin99:Hierarchical},
and   insights   from   research    on   learning   in   game   theory
\cite{Fudenberg98:Theory}.    Our   approach,   closely   related   to
decision-theoretic       \cite{Myerson91:Game},      or      epistemic
\cite{Ambruster79:Bayesian,Battigalli99:Hierarchies,Brandenburger02:Power}
approach  to game  theory,  consists of  predicting  actions of  other
agents  given all  available  information, and  then  of choosing  the
agent's own action  \cite{Kadane82:Subjective}.  Thus, the descriptive
aspect of decision theory is  used to predict others' actions, and its
prescriptive aspect is used to select agent's own optimal action.

The  work presented here also  extends previous
work       on        Recursive       Modeling       Method       (RMM)
\cite{Gmytrasiewicz00:RationalCoord}, but  adds elements of belief 
update and sequential planning.

%-------------------------------------------------------------------
\section{Background: Partially Observable Markov Decision Processes}
\label{sec:pomdps}
%-------------------------------------------------------------------

A   partially    observable   Markov   decision    process  (POMDP)
\cite{Monahan82:Survey,Hauskrecht97:Planning,Kaelbling98:Planning,Boutilier99:Decision,Hauskrecht00:Value}
of an agent $i$ is defined as
\begin{equation}
\mbox{\textit{POMDP}}_i =  \langle S, A_i, T_i, \Omega_i, O_i,  R_i \rangle
\end{equation}
\noindent  where:
%\begin{itemize}
$S$ is a set of possible states  of the environment. $A_i$ is a set of
actions agent $i$ can execute. $T_i$ is a transition function -- $T_i:
S \times A_i  \times S \rightarrow [0, 1]$  which describes results of
agent $i$'s actions.  $\Omega_i$ is  the set of observations the agent
$i$ can  make. $O_i$  is the agent's  observation function --  $O_i: S
\times  A_i  \times  \Omega_i  \rightarrow  [0,  1]$  which  specifies
probabilities  of  observations given  agent's  actions and  resulting
states. Finally,  $R_i$ is the reward function  representing the agent
$i$'s preferences -- $R_i: S \times A_i \rightarrow \Re$.

In  POMDPs, an  agent's belief  about the  state is  represented  as a
probability distribution over  $S$. Initially, before any observations
or actions  take place,  the agent has  some (prior)  belief, $b_i^0$.
After  some  time steps,  $t$,  we assume  that  the  agent has  $t+1$
observations  and has performed  $t$ actions{\footnote{We  assume that
action is taken  at every time step; it is  without loss of generality
since any  of the  actions maybe a  No-op.}}.  These can  be assembled
into {\em  agent $i$'s observation history}: $h_i^t  = \{o_i^0, o_i^1,
.., o_i^{t-1}, o_i^t\}$ at time $t$.   Let $H_i$ denote the set of all
observation  histories  of agent  $i$.   The  agent's current  belief,
$b_i^t$ over  $S$, is continuously  revised based on  new observations
and  expected results  of performed  actions.  It  turns out  that the
agent's  belief state  is  sufficient  to summarize  all  of the  past
observation  history  and  initial   belief;  hence  it  is  called  a
sufficient   statistic.{\footnote{See  \cite{Smallwood73:Optimal}  for
proof.}}

The  belief  update takes  into  account  changes  in initial  belief,
$b_i^{t-1}$, due  to action, $a_i^{t-1}$, executed at  time $t-1$, and
the  new observation,  $o_i^t$.   The new  belief,  $b_i^t$, that  the
current state is $s^t$, is:


\begin{eqnarray}
b_i^t(s^t) = \beta O_i(o_i^t,   s^t,  a_i^{t-1})  \sum_{s^{t-1}  \in   S} b_i^{t-1}(s^{t-1})
T_i(s^t,  a_i^t,  s^{t-1})
\label{eqn:pomdp-bu}
\end{eqnarray}

\noindent where $\beta$ is the normalizing constant.

It  is convenient  to summarize  the  above update  performed for  all
states   in    $S$   as \newline  $b_i^t   =    SE(b_i^{t-1},   a_i^{t-1},   o_i^t)$
\cite{Kaelbling98:Planning}.

%Each belief state $b$ has  a value which reflects the maximum expected
%payoff    the    agent    can     get    in    this    belief    state
%\cite{Boutilier99:Decision,Hauskrecht00:Value,Kaelbling98:Planning,Monahan82:Survey}:

%\begin{eqnarray}
%U(b) = \underset{a_i \in A_i}{max} \bigg\{ sum_{s \in S} R_i(s,a_i)b(s) + 
%\gamma \underset{o_i \in \Omega_i}{\sum} Pr(o_i|a_i, b)U(SE(b, a, o))\bigg\}
%\end{eqnarray}



%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\subsection{Optimality Criteria and Solutions}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The  agent's optimality criterion,  $OC_i$, is  needed to  specify how
rewards  acquired  over  time  are handled.   Commonly  used  criteria
include:

\begin{itemize}

\item A  finite horizon  criterion, in which  the agent  maximizes the
expected   value  of   the   sum  of   the   following  $T$   rewards:
$E(\sum_{t=0}^T r_t)$.  Here,  $r_t$ is a reward obtained  at time $t$
and $T$ is the length of the horizon. We will denote this criterion as
$\textit{fh}^T$.

\item  An infinite  horizon criterion  with discounting,  according to
which  the  agent  maximizes  \newline  $E(\sum_{t=0}^\infty  \gamma^t
r_t)$, where $ 0  < \gamma < 1$ is a discount  factor.  We will denote
this criterion as $\textit{ih}^\gamma$.

\item An infinite horizon criterion with averaging, according to which
the agent maximizes  the average reward per time  step. We will denote
this as $\textit{ih}^{AV}$.

\end{itemize}

In what follows, we concentrate on the infinite horizon criterion with
discounting,  but our  approach can  be  easily adapted  to the  other
criteria.

The utility associated  with a belief state, $b_i$  is composed of the
best of the immediate rewards  that can be obtained in $b_i$, together
with the  discounted expected sum of utilities  associated with belief
states following $b_i$:

\begin{eqnarray}
U(b_i)  =  \underset{a_i \in A_i}{max}\bigg\{\underset{s \in S}{\sum} b_i(s)R_i(s,a_i)  +  \gamma \underset{o_i \in \Omega_i}{\sum} Pr(o_i|a_i,b_i) U(SE_i(b_i,a_i,o_i))\bigg\}
\label{eqn:pomdp-valufunct}
\end{eqnarray}

Value    iteration    uses   the    Equation~\ref{eqn:pomdp-valufunct}
iteratively  to  obtain  values  of  belief  states  for  longer  time
horizons.   At each  step  of the  value  iteration the  error of  the
current value estimate  is reduced by the factor  of at least $\gamma$
\cite<see  for example>[Section 17.2.]{Russell03:Artificial}   The
optimal  action, $a_i^*$, is  then an  element of  the set  of optimal
actions, $OPT(b_i)$, for the belief state, defined as:

\begin{eqnarray}
OPT(b_i)  =  \underset{a_i \in A_i}{argmax}\bigg\{ \underset{s \in S}{\sum} b_i(s)R_i(s, a_i) 
 +  \gamma \underset{o_i \in \Omega_i}{\sum} Pr(o_i|a_i, b_i) U(SE(b_i, a_i, o_i))\bigg\}
\label{eqn:pomdp-optaction}
\end{eqnarray}

%---------------------------------------------------------------------
\subsection{Example: The Tiger Game}
\label{sec:pomdp-tiger}
%---------------------------------------------------------------------

We   briefly    review   the POMDP    solutions   to   the    tiger   game
\cite{Kaelbling98:Planning}. Our  purpose is to build  on the insights
that  POMDP  solutions  provide  in  this simple  case  to  illustrate
solutions to interactive versions of this game later.

The traditional  tiger game resembles  a game-show situation  in which
the decision maker has to choose to open one of two doors behind which
lies either a valuable prize  or a dangerous tiger. Apart from actions
that  open doors,  the subject  has the  option of  listening  for the
tiger's growl coming  from the left, or the  right, door. However, the
subject's hearing is imperfect,  with given percentages (say, 15\%) of
false   positive    and   false   negative    occurrences.   Following
\cite{Kaelbling98:Planning}, we assume that  the value of the prize is
10,  that the  pain  associated  with encountering  the  tiger can  be
quantified as -100, and that the cost of listening is -1.

\begin{figure}
\begin{centering}
\includegraphics[width=4.0in]{tiger.1.comp.alpha.eps}
\caption{The  value function  for single  agent tiger  game  with time
  horizon of length 1, $OC_i = \textit{fh}^1$. Actions are: open right
  door - OR,  open left door - OL,  and listen - L. For  this value of
  the time horizon the value function for a POMDP with noise factor is
  identical to single agent POMDP.}\
\label{fig:tiger1comp}
\end{centering}
\end{figure} 

The  value function, in  Figure~\ref{fig:tiger1comp}, shows  values of
various belief  states when  the agent's time  horizon is equal  to 1.
Values of  beliefs are based on  best action available  in that belief
state,  as specified in  Eq.~\ref{eqn:pomdp-valufunct}.  The  state of
certainty is most valuable -- when the agent knows the location of the
tiger it can open the opposite door and claim the prize which certainly
awaits.  Thus, when  the probability of tiger location is  0 or 1, the
value  is 10.   When the  agent  is sufficiently  uncertain, its  best
option is to play it safe and listen; the value is then -1.  The agent
is  indifferent between opening  doors and  listening when  it assigns
probabilities of 0.9 or 0.1 to the location of the tiger.

Note that,  when the time  horizon is equal  to 1, listening  does not
provide any  useful information  since the game  does not  continue to
allow for the  use of this information.  For  longer time horizons the
benefits of results of listening  results in policies which are better
in some ranges of initial belief. Since the value function is composed
of values corresponding to actions, which are linear in probability of
tiger  location,  the  value   function  has  the  property  of  being
piece-wise linear and convex (PWLC) for all horizons.  This simplifies
the computations substantially. 

\begin{figure}
\begin{centering}
\includegraphics[width=4.5in]{tiger.2.comp.alpha.eps}
\caption{The value function for single agent tiger game compared to an
  agent  facing a  noise factor,  for  horizon of  length 2.  Policies
  corresponding to value lines  are conditional plans.  Actions, L, OR
  or OL,  are conditioned  on observational sequences  in parenthesis.
  For   example   L$\backslash$();L$\backslash$(GL),OL$\backslash$(GR)
  denotes a plan to perform  the listening action, L, at the beginning
  (list  of  observations  is  empty),  and  then  another  L  if  the
  observation is growl from the left (GL), and open the left door, OL,
  if  the observation  is  GR. $\ast$  is  a wildcard  with the  usual
  interpretation.}
\label{fig:ValTigerCompT2}
\end{centering}
\end{figure} 

\begin{figure}
\begin{centering}
\includegraphics[width=5.5in]{tiger.3.comp.alpha.eps}
\caption{The value function for single agent tiger game compared to an
  agent facing a  noise factor, for horizon of length  3. The ``?'' in
  the  description  of a  policy  stands  for  any of  the  perceptual
  sequences not yet listed in the description of the policy.}
\label{fig:ValTigerCompT3}
\end{centering}
\end{figure} 

In  Figure~\ref{fig:ValTigerCompT2} we present  a comparison  of value
functions for horizon of length 2 for a single agent, and for an agent
facing a more noisy environment.   The presence of such noise could be
due  to  another  agent  opening  the doors  or  listening  with  some
probabilities.{\footnote{We  assumed that,  due to  the  noise, either
door opens with probabilities of 0.1 at each turn, and nothing happens
with the probability 0.8.  We explain the origin of this assumption in
Section~\ref{sec:tiger}.}}   Since  POMDPs  do  not  include  explicit
models of other agents, these  noise actions have been included in the
transition model, $T$.

Consequences  of folding  noise  into $T$  are  two-fold.  First,  the
effectiveness of the agent's optimal policies declines since the value
of    hearing    growls    diminishes    over   many    time    steps.
Figure~\ref{fig:ValTigerCompT3}   depicts   a   comparison  of   value
functions for horizon of length 3.  Here, for example, two consecutive
growls in  a noisy environment are  not as valuable as  when the agent
knows it is acting alone since  the noise may have perturbed the state
of the  system between the  growls. For time  horizon of length  1 the
noise  does  not   matter  and  the  value  vectors   overlap,  as  in
Figure~\ref{fig:tiger1comp}.

\begin{figure}
\centerline{\includegraphics[width=4.5in]{pomdp.noise.policy.3.eps}}
\caption{The policy  graph corresponding to value function of POMDP
  with noise depicted in
Fig.~\ref{fig:ValTigerCompT3}.}
\label{fig:pomdp.noise.policy.3}
\end{figure}

Second, since the presence of  another agent is implicit in the static
transition  model, the  agent cannot  update  its model  of the  other
agent's actions during repeated interactions. This effect becomes more
important as time horizon increases. Our approach addresses this issue
by allowing explicit modeling of  the other agent(s).  This results in
policies     of     superior     quality,     as    we     show     in
Section~\ref{sec:tiger}. 
%As we mentioned, as one considers longer and longer time horizons with
%discounting, the computation of  the value function converges with the
%rate of  at least $\gamma$.   In case of  the tiger game,  the optimal
%pattern of  agent's long-term  behavior is to  listen enough  times to
%build up its  confidence in the tiger's location  beyond 90\% and then
%open the appropriate door. If  the agent's hearing is 85\% accurate it
%is sufficient  for the agent to  wait for two  consecutive growls from
%the  same  direction.   
Figure~\ref{fig:pomdp.noise.policy.3}  shows  a  policy for  an  agent
facing a noisy environment for time horizon of 3. We compare it to the
corresponding I-POMDP policy in Section~\ref{sec:tiger}.  Note that it
is slightly different than the  policy without noise in the example by
Kaelbling,  Littman and Cassandra  \citeyear{Kaelbling98:Planning} due
to differences in value functions.

%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\section{Agent Types and Frames}
\label{sec:type}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The POMDP definition includes parameters  that permit us to compute an
agent's  optimal  behavior,{\footnote{The  issue of  computability  of
solutions   to  POMDPs   has   been  a   subject   of  much   research
\cite{Papadimitriou87:Complexity,Madani03:On}.    It  is   of  obvious
importance when  one uses  POMDPs to model  agents; we return  to this
issue  later.}} conditioned  on  its beliefs.   Let  us collect  these
implementation independent  factors into a construct we  call an agent
$i$'s {\em type}.

\begin{defn}[Type]
A type of  an agent $i$ is, $\theta_i = \langle  b_i, A_i, \Omega_i,
T_i,  O_i, R_i, OC_i  \rangle$, where  $b_i$ is  agent $i$'s  state of
belief  (an   element  of  $\Delta(S)$),  $OC_i$   is  its  optimality
criterion, and  the rest  of the elements  are as defined  before. Let
$\Theta_i$ be the set of agent $i$'s types.
\end{defn}

Given  type,  $\theta_i$,  and   the  assumption  that  the  agent  is
Bayesian-rational, the set of  agent's optimal actions will be denoted
as $OPT(\theta_i)$. In  the next section, we generalize  the notion of
type to  situations which include  interactions with other  agents; it
then  coincides  with  the  notion  of type  used  in  Bayesian  games
\cite{Fudenberg91:Game,Harsanyi67:Games}.

It is convenient to define the notion of a  {\em   frame},
$\widehat{\theta}_i$, of agent $i$:

\begin{defn}[Frame]
A   frame  of   an  agent   $i$  is, $\widehat{\theta}_i   =  \langle
A_i,\Omega_i,T_i,O_i,R_i,OC_i  \rangle$.  Let  $\widehat{\Theta}_i$ be
the set of agent $i$'s frames.
\end{defn}

For brevity  one can write a  type as consisting of  an agent's belief
together with  its frame: $\theta_i =  \langle b_i, \widehat{\theta}_i
\rangle$.

In the  context of the tiger  game described in  the previous section,
agent  type  describes the  agent's  actions  and  their results,  the
quality of the agent's hearing,  its payoffs, and its belief about the
tiger location.

Realistically,  apart from implementation-independent  factors grouped
in    type,    an    agent's    behavior   may    also    depend    on
implementation-specific parameters,  like the processor  speed, memory
available,  etc.   These  can   be  included  in  the  (implementation
dependent,  or  {\em  complete})  type,  increasing  the  accuracy  of
predicted  behavior,  but  at   the  cost  of  additional  complexity.
Definition and use of complete types is a topic of ongoing work.

%\vspace{0.3in}

%----------------------------------------------------------------------
\section{Interactive POMDPs}
\label{sec:ipomdps}
%----------------------------------------------------------------------

As  we mentioned,  our intention  is  to generalize  POMDPs to  handle
presence  of other  agents. We  do this  by including  descriptions of
other  agents (their  types  for  example) in  the  state space.   For
simplicity  of  presentation,  we  consider  an  agent  $i$,  that  is
interacting  with   one  other  agent,  $j$.    The  formalism  easily
generalizes to larger number of agents.

\begin{defn}[I-POMDP]  An   {\em  interactive  POMDP}  of  agent
$i$, $\mbox{\textit{I-POMDP}}_i$, is:
\begin{equation}
\mbox{\textit{I-POMDP}}_i = \langle IS_i, A, T_i, \Omega_i, O_i, R_i \rangle
\end{equation}
\end{defn}
\noindent  where:

\vspace{0.1in}

$\bullet$ $IS_i$ is a set of {\bf interactive} states defined as $IS_i
= S  \times M_j$,{\footnote{If there are  more agents, say  $N > 2$,
then $IS_i  = S  \times_{j=1}^{N-1}M_j$}} interacting with  agent $i$,
where $S$ is the set of  states of the physical environment, and $M_j$
is the set of possible models of agent $j$. Each model, $m_j \in M_j$,
is defined  as a triple $m_j  = \langle h_j, f_j,  O_j \rangle$, where
$f_j: H_j  \rightarrow \Delta(A_j)$  is agent $j$'s  function, assumed
computable,  which maps  possible histories  of $j$'s  observations to
distributions over  its actions.   $h_j$ is an  element of  $H_j$, and
$O_j$ is  a function specifying  the way the environment  is supplying
the agent  with its input.  Sometimes  we write model $m_j$  as $m_j =
\langle h_j, \widehat{m}_j \rangle$, where $\widehat{m}_j$ consists of
$f_j$ and $O_j$.  It is convenient to subdivide the set of models into
two  classes.   The  subintentional  models,  $SM_j$,  are  relatively
simple,  while  the intentional  models,  $IM_j$,  use  the notion  of
rationality to model the other agent.  Thus, $M_j = IM_j \cup SM_j$.

Simple  examples  of subintentional  models  include a  no-information
model  and  a  fictitious  play  model,  both  of  which  are  history
independent.              A            no-information            model
\cite{Gmytrasiewicz00:RationalCoord}  assumes that  each of  the other
agent's actions  is executed with equal  probability.  Fictitious play
\cite{Fudenberg98:Theory} assumes that the other agent chooses actions
according to a  fixed but unknown distribution, and  that the original
agent's  prior  belief  over  that  distribution takes  a  form  of  a
Dirichlet   distribution.{\footnote{Technically,   according  to   our
notation,  fictitious play  is actually  an ensemble  of  models.}} An
example  of a  more powerful  subintentional model  is a  finite state
controller. 

The intentional models are more  sophisticated in that they ascribe to
the  other  agent  beliefs,  preferences  and  rationality  in  action
selection.{\footnote{Dennet \citeyear{Dennett86:Intentional} advocates
ascribing  rationality to other  agent(s), and  calls it  "assuming an
intentional stance towards them".}}  Intentional models are thus $j$'s
types, $\theta_j = \langle b_j, \widehat{\theta}_j \rangle$, under the
assumption  that agent  $j$ is  Bayesian-rational.{\footnote{Note that
the space  of types is by  far richer than that  of computable models.
In particular, since the set of computable models is countable and the
set of types  is uncountable, many types are  not computable models.}}
Agent $j$'s  belief is a  probability distribution over states  of the
environment and the models of the agent $i$; $b_j \in \Delta (S \times
M_i)$.  The notion of a type  we use here coincides with the notion of
type in game  theory, where it is defined as consisting  of all of the
agent  $i$'s  private  information  relevant to  its  decision  making
\cite{Harsanyi67:Games,Fudenberg91:Game}.   In particular,  if agents'
beliefs  are private  information, then  their types  involve possibly
infinitely nested  beliefs over others' types and  their beliefs about
others
\cite{Mertens85:Formulation,Brandenburger93:Hierarchies,Aumann99:Interactive,Aumann02:Incomplete}.{\footnote{Implicit
in  the  definition  of  interactive  beliefs  is  the  assumption  of
coherency~\cite{Brandenburger93:Hierarchies}.}}   They are  related to
recursive     model      structures     in     our      prior     work
\cite{Gmytrasiewicz00:RationalCoord}.   The definition  of interactive
state space  is consistent with  the notion of a  completely specified
state  space  put  forward by  Aumann~\citeyear{Aumann99:Interactive}.
Similar    state    spaces    have    been    proposed    by    others
\cite{Mertens85:Formulation,Brandenburger93:Hierarchies}.

\vspace{0.1in}

$\bullet$ $A =  A_i \times A_j$ is  the set of joint moves  of all agents.

\vspace{0.1in}

$\bullet$ $T_i$ is the transition  model.  The usual way to define the
transition  probabilities in  POMDPs  is to  assume  that the  agent's
actions can  change any aspect of  the state description.   In case of
I-POMDPs,  this  would  mean  actions  modifying  any  aspect  of  the
interactive states, including  other agents' observation histories and
their functions, or, if  they are modeled intentionally, their beliefs
and reward  functions.  Allowing  agents to directly  manipulate other
agents in such ways, however, violates the notion of agents' autonomy.
Thus, we make the following simplifying assumption:

%\begin{defn}{
{\bf Model Non-manipulability Assumption (MNM):}
Agents'   actions   do   not   change   the   other   agents'   models
directly. 

Given  this simplification,  the transition  model can  be  defined as
$T_i: S \times A \times S \rightarrow [0, 1]$
%\end{defn}

Autonomy, formalized  by the  MNM assumption, precludes,  for example,
direct ``mind control'', and  implies that other agents' belief states
can be changed only  indirectly, typically by changing the environment
in a way observable to  them.  In other words, agents' beliefs change,
like in POMDPs, but as a result of belief update after an observation,
not as  a direct result  of any of the  agents' actions.{\footnote{The
possibility that  agents can influence  the observational capabilities
of other agents can be  accommodated by including the factors that can
change sensing capabilities in the set $S$.}}



%\item

\vspace{0.1in}

$\bullet$ $\Omega_i$  is defined as before in the POMDP model.

\vspace{0.1in}

$\bullet$ $O_i$ is an observation  function.  In defining this
function we make the following assumption:

%\begin{defn}{
{\bf Model Non-observability (MNO):} Agents cannot observe other's
models directly.  

Given this assumption  the observation function is defined  as $O_i: S
\times A \times \Omega_i \rightarrow [0, 1]$.
%\end{defn}

The MNO assumption formalizes another aspect of autonomy -- agents are
autonomous in  that their observations  and functions, or  beliefs and
other properties, say preferences,  in intentional models, are private
and  the other agents  cannot observe  them directly.{\footnote{Again,
the possibility that agents can observe factors that may influence the
observational  capabilities of  other agents  is allowed  by including
these factors in $S$.}}

\vspace{0.1in}

$\bullet$ $R_i$ is defined as $R_i: IS_i \times A \rightarrow \Re$. We
allow the agent to have preferences over physical states and models of
other agents, but usually only the physical state will matter.

%\item

%\end{itemize}

As we mentioned, we see interactive POMDPs as a subjective counterpart
to    an    objective    external    view    in    stochastic    games
\cite{Fudenberg91:Game},  and also  followed   in  some  work  in  AI
\cite{Boutilier99:Sequential}  and \cite{Koller01:Multi-Agent}  and in
decentralized    POMDPs   \cite{Bernstein02:Complexity,Nair03:Taming}.
Interactive POMDPs  represent an individual  agent's point of  view on
the  environment and  the other  agents, and  facilitate  planning and
problem solving at the agent's own individual level.

%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\subsection{Belief Update in \mbox{\textit{I-POMDPs}}}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

We  will  show that,  as  in POMDPs,  an  agent's  beliefs over  their
interactive  states  are   sufficient  statistics,  i.e.,  they  fully
summarize the agent's observation histories.  Further, we need to show
how beliefs are updated after  the agent's action and observation, and
how solutions are defined.

The new  belief state, $b_i^t$, is  a function of  the previous belief
state,  $b_i^{t-1}$,  the  last   action,  $a_i^{t-1}$,  and  the  new
observation, $o_i^t$,  just as in  POMDPs.  There are  two differences
that complicate  belief update when compared to  POMDPs.  First, since
the state of the physical environment depends on the actions performed
by both agents the prediction of how the physical state changes has to
be made  based on  the probabilities of  various actions of  the other
agent.   The probabilities of  other's actions  are obtained  based on
their models.   Thus, unlike in  Bayesian and stochastic games,  we do
not assume that actions are fully observable by other agents.  Rather,
agents can attempt  to infer what actions other  agents have performed
by sensing  their results on  the environment. Second, changes  in the
models  of other  agents have  to be  included in  the  update.  These
reflect   the  other's   observations   and,  if   they  are   modeled
intentionally, the update of the other agent's beliefs.  In this case,
the agent  has to update  its beliefs about  the other agent  based on
what it anticipates  the other agent observes and  how it updates.  As
could be expected, the update of the possibly infinitely nested belief
over other's types is, in general, only asymptotically computable.

\begin{prop}{{\bf (Sufficiency)}}
In an interactive POMDP of  agent $i$, $i$'s current belief, i.e., the
probability  distribution  over the  set  $S  \times  M_j$, is  a
sufficient statistic for the past history of $i$'s observations.
\end{prop}

The next  proposition defines the agent $i$'s  belief update function,
$b_i^t(is^t) =  Pr(is^t|o_i^t, a_i^{t-1}, b_i^{t-1})$,  where $is^t\in
IS_i $  is an interactive state.   We use the  belief state estimation
function, $SE_{\theta_i}$,  as an abbreviation for  belief updates for
individual states so that $b_i^t = SE_{\theta_i}(b_i^{t-1}, a_i^{t-1},
o_i^t)$.   \newline   $\tau_{\theta_i}(b_i^{t-1},  a_i^{t-1},   o_i^t,
b_i^{t})$  will stand  for $Pr(b_i^{t}|b_i^{t-1},  a_i^{t-1}, o_i^t)$.
Further below we also define the set of type-dependent optimal actions
of an agent, $OPT(\theta_i)$.

\begin{prop}{{\bf (Belief Update)}} Under  the MNM and  MNO assumptions,  the
belief update  function for an interactive  POMDP $\langle IS_i,  A, T_i,
\Omega_i, O_i, R_i \rangle$, when $m_j$ in $is^t$ is intentional, is:

\begin{equation}\begin{array}{ll}
b_i^t(is^t)  &=  \beta  \underset{is^{t-1}:\widehat{m}_j^{t-1}  = \widehat{\theta}_j^t}{\sum}b_i^{t-1}(is^{t-1})\underset{a_j^{t-1}}{\sum}Pr(a_j^{t-1}|\theta_j^{t-1})O_i(s^t,a^{t-1},o_i^t)\\
  &\times T_i(s^{t-1},a^{t-1},s^t) \underset{o_j^t}{\sum}
  \tau_{\theta_j^t}(b_j^{t-1},a_j^{t-1},o_j^t,b_j^t)
  O_j(s^t,a^{t-1},o_j^t)
\end{array}\label{eqn:bu}\end{equation}

\noindent When  $m_j$ in $is^t$ is subintentional  the first summation
extends   over   $is^{t-1}:\widehat{m}_j^{t-1}   =   \widehat{m}_j^t$,
\newline     $Pr(a_j^{t-1}|\theta_j^{t-1})$    is     replaced    with
$Pr(a_j^{t-1}|m_j^{t-1})$,                                          and
$\tau_{\theta_j^t}(b_j^{t-1},a_j^{t-1},o_j^t,b_j^t)$  is replaced with
the               Kronecker               delta               function
$\delta_K(\mbox{APPEND}(h_j^{t-1},o_j^t),h_j^t)$.

%\begin{equation}\begin{array}{ll}
%b_i^t(is^t)  &=  \beta  \underset{is^{t-1}:\widehat{m}_j^{t-1} = \widehat{m}_j^t}{\sum}b_i^{t-1}(is^{t-1})\underset{a_j^{t-1}}{\sum}Pr(a_j^{t-1}|m_j^{t-1})O_i(s^t,a^{t-1},o_i^t)\\
%  &\times      T_i(s^{t-1},a^{t-1},s^t) \underset{o_j^t}{\sum} O_j(s^t,a^{t-1},o_j^t)\tau(\mbox{APPEND}(h_j^{t-1},o_j^t),h_j^t)
%  \end{array}\label{eqn:bu1}\end{equation}

\end{prop}
\noindent %For Eq.~\ref{eqn:bu}, $is  =  (s,\theta_j)$,
%$is_j   =  (s,  \theta_i)$,
Above,   $b_j^{t-1}$  and   $b_j^t$   are  the   belief  elements   of
$\theta_j^{t-1}$   and  $\theta_j^t$,   respectively,  $\beta$   is  a
normalizing   constant,  and  $Pr(a_j^{t-1}|\theta_j^{t-1})$   is  the
probability that $a_j^{t-1}$ is  Bayesian rational for agent described
by   type   $\theta_j^{t-1}$.     This   probability   is   equal   to
$\frac{1}{|OPT(\theta_j)|}$ if  $a_j^{t-1} \in OPT(\theta_j)$,  and it
is    equal    to    zero    otherwise.    We    define    $OPT$    in
Section~\ref{subsec:value}.{\footnote{If the agent's prior belief over
$IS_i$  is   given  by  a   probability  density  function   then  the
$\sum_{is^{t-1}}$  is   replaced  by   an  integral.   In   that  case
$\tau_{\theta_j^t}(b_j^{t-1},a_j^{t-1},o_j^t,b_j^t)$ takes the form of
Dirac      delta     function      over      argument     $b_j^{t-1}$:
$\delta_D(SE_{\theta_j^t}(b_j^{t-1},a_j^{t-1},o_j^t) - b_j^t)$.}}  For
the case  of $j$'s subintentional  model, $is =  (s,m_j)$, $h_j^{t-1}$
and  $h_j^t$   are  the  observation  histories  which   are  part  of
$m_j^{t-1}$,  and  $m_j^t$  respectively,  $O_j$  is  the  observation
function in $m_j^t$,  and $Pr(a_j^{t-1}|m_j^{t-1})$ is the probability
assigned by  $m_j^{t-1}$ to $a_j^{t-1}$. APPEND returns  a string with
the  second  argument  appended  to  the  first.  The  proofs  of  the
propositions are in the Appendix.

%\begin{prop}{{\bf (Belief Update)}} Under  the MNM and  MNO assumptions,  the
%belief update  function for interactive  POMDP $\langle IS_i,  A, T_i,
%\Omega_i, O_i, R_i \rangle$ is:
%%\begin{small}
%\begin{equation}\begin{array}{ll}
%b_i^t(is^t)  &=  \beta  \underset{is^{t-1}:\widehat{\theta}_j^{t-1}  =
%  \widehat{\theta}_j^t}{\sum}b_i^{t-1}(is^{t-1})\underset{a_j^{t-1}}{\sum}Pr(a_j^{t-1}|\theta_j^{t-1})O_i(s^t,a^{t-1},o_i^t)\\
%  &\times        T_i(s^{t-1},a^{t-1},s^t)       \underset{o_j^t}{\sum}
%  \tau_{\theta_j^t}(b_j^{t-1},a_j^{t-1},o_j^t,b_j^t)
%  O_j(s^t,a^{t-1},o_j^t)
%\end{array}\label{eqn:bu}\end{equation}
%%\end{small}
%\end{prop}
%\begin{eqnarray}
%\begin{small}
%&b&_i^t(is') = \sum_{a_j^{t-1}}  \beta
%O_i(is',a^{t-1},o_i^t)\Biggl\{  \sum_{o_j^t} \times \nonumber \\  &\times&
%\biggl[\sum_{is}b_i^{t-1}(is)\sum_{is''}T_i(is,a^{t-1},is'')\tau_{\theta_j}(b_j^{t-1},a_j^{t-1},o_j^t,b_j^{t})
%\biggr]  \times  \nonumber \\
% &\times&  \sum_{is}b_i^{t-1}(is)\sum_{is''}
%O_j''((s'',\theta'_i),a^{t-1},o_i^t)T_i(is,a^{t-1},is'')
%\Biggr\} \times \nonumber \\
% &\times&  \sum_{is}b_i^{t-1}(is) P(a_j^{t-1}|M_j)
%\end{small}
%\end{eqnarray}
%\noindent  where   $is  =  (s,\theta_j)$,  
%$is_j   =  (s,  \theta_i)$,
%$b_j^{t-1}$ and  $b_j^t$ are  the belief elements  of $\theta_j^{t-1}$
%and  $\theta_j^t$, respectively,  $\beta$ is  a  normalizing constant,
%$O_j$   is    the   observation   function    in   $\theta_j^t$,   and
%$Pr(a_j^{t-1}|\theta_j^{t-1})$ is the  probability that $a_j^{t-1}$ is
%Bayesian rational  for agent described by  type $\theta_j^{t-1}$. This
%probability is equal  to $\frac{1}{|OPT(\theta_j)|}$ if $a_j^{t-1} \in
%OPT(\theta_j)$, and it is equal to zero otherwise.  We define $OPT$ in
%Section~\ref{subsec:value}.   {\footnote{If the  agent's  prior belief
%over  $IS_i$ is  given  by  a probability  density  function then  the
%$\sum_{is^{t-1}}$  is   replaced  by   an  integral.   In   that  case
%$\tau_{\theta_j^t}(b_j^{t-1},a_j^{t-1},o_j^t,b_j^t)$ takes the form of
%Dirac      delta     function      over      argument     $b_j^{t-1}$:
%$\delta(SE_{\theta_j^t}(b_j^{t-1},a_j^{t-1},o_j^t) - b_j^t)$.}}


%Intuitively,  proposition  1 holds
%since,  as in  POMDPs \cite{Smallwood73:Optimal},  all of  the dynamic
%elements (state  transitions and observations) of the  model depend on
%the previous intentional state, not on prior observations and actions.

Proposition 2  and Eq.~\ref{eqn:bu} have  a lot in common  with belief
update in POMDPs,  as should be expected.  Both  depend on agent $i$'s
observation  and  transition functions.   However,  since agent  $i$'s
observations also depend on  agent $j$'s actions, the probabilities of
various  actions of  $j$ have  to be  included (in  the first  line of
Eq.~\ref{eqn:bu}.)   Further, since  the update  of agent  $j$'s model
depends   on  what   $j$  observes,   the  probabilities   of  various
observations  of  $j$ have  to  be included  (in  the  second line  of
Eq.~\ref{eqn:bu}.) The  update of $j$'s beliefs is  represented by the
$\tau_{\theta_j}$ term.
%Since the agent  $i$'s beliefs could be infinitely  nested, the belief
%update in I-POMDPs can, in general, be calculated only asymptotically.
The belief update can easily  be generalized to the setting where more
than one other agents co-exist with agent $i$.

%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\subsection{Value Function and Solutions in I-POMDPs}
\label{subsec:value}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Analogously to POMDPs, each belief  state in I-POMDP has an associated
value  reflecting the  maximum payoff  the  agent can  expect in  this
belief state:
\begin{equation}\begin{array}{l}
U(\theta_i) = \underset{a_i \in A_i}{max} \bigg\{ \underset{is}{\sum} ER_i(is,a_i)b_i(is) + 
\gamma \underset{o_i \in \Omega_i}{\sum} Pr(o_i|a_i, b_i)U(\langle SE_{\theta_i}(b_i, a_i, o_i),\widehat{\theta}_i\rangle)\bigg\}
\end{array}\label{eqn:valuefunc}\end{equation}
where,    $ER_i(is,a_i)    =    \sum_{a_j}R_i(is,a_i,a_j)Pr(a_j|m_j)$.
Eq.~\ref{eqn:valuefunc} is a basis for value iteration in I-POMDPs.

Agent $i$'s  optimal action, $a_i^*$,  for the case of  infinite horizon
criterion  with discounting,  is  an  element of  the  set of  optimal
actions for the belief state, $OPT(\theta_i)$, defined as:
\begin{equation}\begin{array}{l}
OPT(\theta_i)  =  \underset{a_i \in  A_i}{argmax}\bigg\{\underset{is}{\sum}
ER_i(is, a_i)b_i(is) + 
\gamma \underset{o_i \in \Omega_i}{\sum}
Pr(o_i|a_i, b_i) U(\langle SE_{\theta_i}(b_i, a_i, o_i),\widehat{\theta}_i\rangle)\bigg\}
\end{array}\label{eqn:optaction}\end{equation}

As in  the case  of belief update,  due to possibly  infinitely nested
beliefs,  a step  of value  iteration  and optimal  actions are  only
asymptotically  computable.  

%A  reasonable  approximation may  involve
%terminating the  nesting of beliefs with a  {\em no-information} model
%which  assumes that  each  of  the other  agent's  actions is  equally
%likely. If nesting of beliefs is finite, and assuming that the sets of
%possible frames of both agents are finite, solving an I-POMDP involves
%solving a finite number of  traditional POMDPs.  In such cases solving
%an   I-POMDP    for   a    finite   time   horizon    is   PSPACE-hard
%\cite{Papadimitriou87:Complexity}.     Including    more   information
%residing in deeper levels of nesting results in better approximations.
%We investigated error bounds  of such approximations experimentally in
%\cite{Noh01:Identifying} in myopic settings; formal proof of the error
%bounds for longer time horizons remain subject of future work.

%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\section{Finitely Nested  I-POMDPs}
\label{sec:finite}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Possible  infinite nesting  of agents'  beliefs in  intentional models
presents  an obvious  obstacle  to computing  the  belief updates  and
optimal solutions.  Since the  models of agents with infinitely nested
beliefs correspond to  agent functions which are not  computable it is
natural  to consider finite  nestings.  We  follow approaches  in game
theory
\cite{Aumann99:Interactive,Brandenburger93:Hierarchies,Fagin99:Hierarchical},
extend  our  previous  work \cite{Gmytrasiewicz00:RationalCoord},  and
construct  finitely  nested  I-POMDPs  bottom-up.   Assume  a  set  of
physical states of  the world $S$, and two agents  $i$ and $j$.  Agent
$i$'s  0-th level  beliefs, $b_{i,0}$,  are  probability distributions
over  $S$.  Its  0-th level  types, $\Theta_{i,0}$,  contain  its 0-th
level beliefs, and its frames, and analogously for agent $j$.  0-level
types  are, therefore,  POMDPs.{\footnote{In 0-level  types  the other
agent's  actions are folded  into the  $T$, $O$  and $R$  functions as
noise.}}   0-level  models include  0-level  types (i.e.,  intentional
models) and  the subintentional models, elements of  $SM$.  An agent's
first level beliefs are probability distributions over physical states
and 0-level models  of the other agent.  An  agent's first level types
consist of its first level  beliefs and frames. Its first level models
consist  of the  types upto  level  1 and  the subintentional  models.
Second level beliefs are defined in terms of first level models and so
on.  Formally, define spaces:

\begin{centering}
\( \begin{array}{lllcclccl} IS_{i,0} & = &  S, & \Theta_{j,0} & = & \{
\langle    b_{j,0},   \widehat{\theta}_{j}   \rangle:    b_{j,0}   \in
\Delta(IS_{j,0})\}, & M_{j,0} & = &  \Theta_{j,0} \cup SM_j \\
IS_{i,1}  & = &  S \times  M_{j,0}, &  \Theta_{j,1} &  = &  \{ \langle
b_{j,1},  \widehat{\theta}_j \rangle: b_{j,1}  \in \Delta(IS_{j,1})\},
& M_{j,1} & = & \Theta_{j,1} \cup M_{j,0} \\ &  . &&& . & \\ & . &&& . & \\
& . &&& . & \\ IS_{i,l} & = & S \times M_{j,l-1}, & \Theta_{j,l} &
=  &  \{  \langle  b_{j,l}, \widehat{\theta}_j  \rangle:  b_{j,l}  \in
\Delta(IS_{j,l})\}, & M_{j,l}  & = & \Theta_{j,l}  \cup M_{j,l-1}
\end{array} \)
\end{centering}


\begin{defn}{{\bf (Finitely Nested I-POMDP)}}  A     finitely
    nested I-POMDP  of  agent
$i$, $\mbox{\textit{I-POMDP}}_{i,l}$, is:
\begin{equation}
\mbox{\textit{I-POMDP}}_{i,l} = \langle IS_{i,l}, A, T_i, \Omega_i, O_i, R_i \rangle
\end{equation}
\end{defn}

\noindent The parameter $l$ will be called the {\em strategy level} of
the finitely  nested I-POMDP.  The belief update,  value function, and
the optimal  actions for finitely  nested I-POMDPs are  computed using
Equation~\ref{eqn:bu} and  Equation~\ref{eqn:optaction}, but recursion
is guaranteed to terminate at  0-th level and subintentional models. 

Agents  which are  more strategic  are capable  of modeling  others at
deeper levels (i.e.,  all levels up to their  own strategy level $l$),
but are  always only boundedly  optimal.  As such, these  agents could
fail to  predict the strategy  of a more sophisticated  opponent.  The
fact  that the  computability of  an agent  function implies  that the
agent may  be suboptimal during  interactions has been pointed  out by
Binmore  \citeyear{Binmore90:Essays},  and  proved  more  recently  by
Nachbar   and   Zame   \citeyear{Nachbar96:Non}.    Intuitively,   the
difficulty  is that  an  agent's unbounded  optimality  would have  to
include  the  capability  to  model  the other  agent's  modeling  the
original  agent.   This  leads  to  an  impossibility  result  due  to
self-reference,  which is very  similar to  G\"{o}del's incompleteness
theorem  and the halting  problem \cite{Brandenburger02:Power}.   On a
positive   note,  some  convergence   results  \cite{Kalai93:Rational}
strongly suggest  that approximate optimality  is achievable, although
their applicability to our work remains open.

As  we mentioned,  the  0-th  level types  are  POMDPs.  They  provide
probability distributions  over actions of  the agent modeled  at that
level  to  models  with   strategy  level  of  1.   Given  probability
distributions  over  other  agent's  actions the  level-1  models  can
themselves be solved as  POMDPs, and provide probability distributions
to  yet  higher  level  models.   Assume that  the  number  of  models
considered  at  each level  is  bound by  a  number,  $M$. Solving  an
$\mbox{\textit{I-POMDP}}_{i,l}$ in then equivalent to solving $O(M^l)$
POMDPs.      Hence,      the     complexity     of      solving     an
$\mbox{\textit{I-POMDP}}_{i,l}$   is  PSPACE-hard   for   finite  time
horizons,{\footnote{Usually PSPACE-complete since the number of states
in  I-POMDPs   is  likely   to  be  larger   than  the   time  horizon
\cite{Papadimitriou87:Complexity}.}}   and  undecidable  for  infinite
horizons, just like for POMDPs.

%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\subsection{Some Properties of I-POMDPs}
\label{subsec:prop}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In  this  section  we   establish  two  important  properties,  namely
convergence of value iteration  and piece-wise linearity and convexity
of the value function, for finitely nested I-POMDPs.  

%These properties
%are similar to  those in POMDPs, and carry over  to I-POMDPs under the
%assumption of finite  nesting of beliefs.  This assumption  is one way
%of assuring that the value function is well defined.

\subsubsection{Convergence of Value Iteration}

For an  agent $i$ and  its \textit{I-POMDP$_{i,l}$}, we can  show that
the sequence of value functions,  \{$U^n$\}, where $n$ is the horizon,
obtained  by  value   iteration  defined  in  Eq.~\ref{eqn:valuefunc},
converges to a unique fixed-point, $U^*$.

Let us define  a {\em backup} operator $H: B  \rightarrow B$ such that
$U^n  =  HU^{n-1}$,   and  $B$  is  the  set   of  all  bounded  value
functions.  In  order  to  prove  the  convergence  result,  we  first
establish some of the properties of $H$.

\begin{lem}[Isotonicity]
For any finitely nested  \textit{I-POMDP} value functions $V$ and $U$,
if $V \leq U$, then $HV \leq HU$.
\end{lem}

The  proof  of  this lemma  is  analogous  to  one due  to  Hauskrecht
~\citeyear{Hauskrecht97:Planning}, for POMDPs.  It is also sketched in
the  Appendix.  Another important  property  exhibited  by the  backup
operator is the property of contraction.

\begin{lem}[Contraction]
For any finitely nested  \textit{I-POMDP} value functions $V$, $U$ and
a discount factor $\gamma \in (0,1)$, $||HV-HU|| \leq \gamma||V-U||$.
\end{lem}

The proof of  this lemma is again similar to  the corresponding one in
POMDPs ~\cite{Hauskrecht97:Planning}. The proof  makes use of Lemma 1.
$||\cdot||$ is the supremum norm.

Under the  contraction property of $H$,  and noting that  the space of
value functions along  with the supremum norm forms  a complete normed
space  (Banach space), we  can apply  the Contraction  Mapping Theorem
~\cite{Stokey89:Recursive} to  show that value  iteration for I-POMDPs
converges to  a unique fixed  point (optimal solution).  The following
theorem captures this result.

\begin{thm}[Convergence]For any finitely nested \textit{I-POMDP}, the 
value  iteration algorithm  starting from  any  arbitrary well-defined
value function converges to a unique fixed-point.
\label{thm:convergence}
\end{thm}

The detailed proof of this theorem is included in the Appendix.

As in  the case of  POMDPs ~\cite{Russell03:Artificial}, the  error in
the iterative  estimates, $U^n$,  for finitely nested  I-POMDPs, i.e.,
$||U^n -U^*||$, is reduced by the  factor of at least $\gamma$ on each
iteration. Hence,  the number of  iterations, $N$, needed to  reach an
error of at most $\epsilon$ is:

\begin{equation}
N = \lceil \log(R_{max}/\epsilon(1-\gamma))/\log(1/\gamma)\rceil
\label{eq:convergence-rate}
\end{equation}

\noindent where $R_{max}$ is the upper bound of the reward function.
%One  way of meeting
%the assumption under which the theorem holds is to restrict the domain
%of  the I-POMDP  value  function  to agent  types  with finite  belief
%nestings.   Another  method  is  to  demonstrate the  existence  of  a
%fixed-point  as the  depth of  the  belief nestings  increase. We  are
%currently investigating the latter approach.

\subsubsection{Piecewise Linearity and Convexity}

Another  property that  carries over  from POMDPs  to  finitely nested
I-POMDPs is the piecewise linearity  and convexity (PWLC) of the value
function.   Establishing  this property  allows  us  to decompose  the
I-POMDP  value function into  a set  of {\em  alpha} vectors,  each of
which represents a  policy tree. The PWLC property  enables us to work
with sets  of alpha vectors  rather than perform value  iteration over
the continuum of agent's beliefs.  Theorem~\ref{thm:PWLC} below states
the PWLC property of the I-POMDP value function.

\begin{thm}[PWLC] For any finitely nested \textit{I-POMDP}, $U$ is 
piecewise linear and convex.
\label{thm:PWLC}
\end{thm}

The  complete  proof  of  Theorem~\ref{thm:PWLC} is  included  in  the
Appendix.  The  proof is  similar to one  due to Smallwood  and Sondik
\citeyear{Smallwood73:Optimal} for  POMDPs and proceeds  by induction.
The  basis case  is established  by  considering the  horizon 1  value
function.   Showing   the  PWLC   for  the  inductive   step  requires
substituting    the     belief    update    (Eq.~\ref{eqn:bu})    into
Eq.~\ref{eqn:valuefunc},  followed by  factoring out  the  belief from
both terms of the equation.

%----------------------------------------------------------------------
\section{Example: Multi-agent Tiger Game}
\label{sec:tiger}
%----------------------------------------------------------------------

 To illustrate  optimal sequential  behavior of agents  in multi-agent
settings we apply our I-POMDP framework to the multi-agent tiger game,
a traditional version of which we described before.

%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\subsection{Definition}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Let us denote the actions of opening doors and listening as OR, OL and
L, as before.  TL and  TR denote states corresponding to tiger located
behind the left and  right door, respectively.  The transition, reward
and observation  functions depend now  on the actions of  both agents.
Again, we  assume that  the tiger location  is chosen randomly  in the
next time  step if any of the  agents opened any doors  in the current
step.  We also assume that the  agent hears the tiger's growls, GR and
GL,  with  the  accuracy  of  85\%.   To  make  the  interaction  more
interesting we  added an observation  of door creaks, which  depend on
the action  executed by the other  agent.  Creak right,  CR, is likely
due to the other agent having opened the right door, and similarly for
creak left, CL.  Silence, S, is a good indication that the other agent
did not open  doors and listened instead. We  assume that the accuracy
of  creaks is  90\%.   We also  assume  that the  agent's payoffs  are
analogous    to    the   single    agent    versions   described    in
Section~\ref{sec:pomdp-tiger}  to make  these cases  comparable.  Note
that the result  of this assumption is that  the other agent's actions
do  not  impact the  original  agent's  payoffs  directly, but  rather
indirectly  by  resulting  in  states  that  matter  to  the  original
agent. Table~\ref{fig:tables} quantifies these factors.

\begin{table}[!ht]
\begin{minipage}{6.0in}
\begin{scriptsize}
\centerline{\begin{tabular}{|c|c|c|c|}
\hline
{\bf $\langle a_i, a_j \rangle$} & {\bf State} & {\bf TL} & {\bf TR}\\
\hline
$\langle OL,* \rangle$ & * & 0.5 & 0.5\\
\hline
$\langle OR,* \rangle$ & * & 0.5 & 0.5\\
\hline
$\langle *,OL \rangle$ & * & 0.5 & 0.5\\
\hline
$\langle *,OR \rangle$ & * & 0.5 & 0.5\\
\hline
$\langle L,L \rangle$ & $TL$ & 1.0 & 0\\
\hline
$\langle L,L \rangle$ & $TR$ & 0 & 1.0\\
\hline
\end{tabular}
\hspace{0.3in}
\begin{tabular}{|c|c|c|}
\hline
{\bf $\langle a_i, a_j \rangle$} & {\bf TL} & {\bf TR}\\
\hline
$\langle OR,OR \rangle$ & 10 & -100\\
\hline
$\langle OL,OL \rangle$ & -100 & 10\\
\hline
$\langle OR,OL \rangle$ & 10 & -100\\
\hline
$\langle OL,OR \rangle$ & -100 & 10\\
\hline
$\langle L,L \rangle$ & -1 & -1\\
\hline
$\langle L,OR \rangle$ & -1 & -1\\
\hline
$\langle OR,L \rangle$ & 10 & -100\\
\hline
$\langle L,OL \rangle$ & -1 & -1\\
\hline
$\langle OL,L \rangle$ & -100 & 10\\
\hline
\end{tabular}
\hspace{0.1in}
\begin{tabular}{|c|c|c|}
\hline
{\bf $\langle a_i,a_j \rangle$} & {\bf TL} & {\bf TR}\\
\hline
$\langle OR,OR \rangle$ & 10 & -100\\
\hline
$\langle OL,OL \rangle$ & -100 & 10\\
\hline
$\langle OR,OL \rangle$ & -100 & 10\\
\hline
$\langle OL,OR \rangle$ & 10 & -100\\
\hline
$\langle L,L \rangle$ & -1 & -1\\
\hline
$\langle L,OR \rangle$ & 10 & -100\\
\hline
$\langle OR,L \rangle$ & -1 & -1\\
\hline
$\langle L,OL \rangle$ & -100 & 10\\
\hline
$\langle OL,L \rangle$ & -1 & -1\\
\hline
\end{tabular}}
\end{scriptsize}
\hspace{0.45in} Transition function: $T_i = T_j$ \hspace{0.70in} Reward functions of agents $i$ and $j$
\end{minipage}
\begin{minipage}{6.0in}
\begin{scriptsize}
\vspace{0.3in}
\centerline{\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
{\bf $\langle a_i, a_j \rangle$} & {\bf State} & {\bf $\langle$ GL, CL $\rangle$} & {\bf $\langle$ GL, CR $\rangle$} & {\bf $\langle$ GL, S $\rangle$} & {\bf $\langle$ GR, CL $\rangle$} & {\bf $\langle$ GR, CR $\rangle$} & {\bf $\langle$ GR, S $\rangle$} \\
\hline
$\langle L,L \rangle$ & $TL$ & 0.85*0.05 & 0.85*0.05 & 0.85*0.9 & 0.15*0.05 & 0.15*0.05 & 0.15*0.9\\
\hline
$\langle L,L \rangle$ & $TR$ & 0.15*0.05 & 0.15*0.05 & 0.15*0.9 & 0.85*0.05 & 0.85*0.05 & 0.85*0.9\\
\hline
$\langle L,OL \rangle$ & $TL$ & 0.85*0.9 & 0.85*0.05 & 0.85*0.05 & 0.15*0.9 & 0.15*0.05 & 0.15*0.05\\
\hline
$\langle L,OL \rangle$ & $TR$ & 0.15*0.9 & 0.15*0.05 & 0.15*0.05 & 0.85*0.9 & 0.85*0.05 & 0.85*0.05\\
\hline
$\langle L,OR \rangle$ & $TL$ & 0.85*0.05 & 0.85*0.9 & 0.85*0.05 & 0.15*0.05 & 0.15*0.9 & 0.15*0.05\\
\hline
$\langle L,OR \rangle$ & $TR$ & 0.15*0.05 & 0.15*0.9 & 0.15*0.05 & 0.85*0.05 & 0.85*0.9 & 0.85*0.05\\
\hline
$\langle OL,* \rangle$ & $*$ & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6\\
\hline
$\langle OR,* \rangle$ & $*$ & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6\\
\hline
\end{tabular}}
\vspace{0.1in}
\centerline{\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
{\bf $\langle a_i, a_j \rangle$} & {\bf State} & {\bf $\langle$ GL, CL $\rangle$} & {\bf $\langle$ GL, CR $\rangle$} & {\bf $\langle$ GL, S $\rangle$} & {\bf $\langle$ GR, CL $\rangle$} & {\bf $\langle$ GR, CR $\rangle$} & {\bf $\langle$ GR, S $\rangle$} \\
\hline
$\langle L,L \rangle$ & $TL$ & 0.85*0.05 & 0.85*0.05 & 0.85*0.9 & 0.15*0.05 & 0.15*0.05 & 0.15*0.9\\
\hline
$\langle L,L \rangle$ & $TR$ & 0.15*0.05 & 0.15*0.05 & 0.15*0.9 & 0.85*0.05 & 0.85*0.05 & 0.85*0.9\\
\hline
$\langle OL,L \rangle$ & $TL$ & 0.85*0.9 & 0.85*0.05 & 0.85*0.05 & 0.15*0.9 & 0.15*0.05 & 0.15*0.05\\
\hline
$\langle OL,L \rangle$ & $TR$ & 0.15*0.9 & 0.15*0.05 & 0.15*0.05 & 0.85*0.9 & 0.85*0.05 & 0.85*0.05\\
\hline
$\langle OR,L \rangle$ & $TL$ & 0.85*0.05 & 0.85*0.9 & 0.85*0.05 & 0.15*0.05 & 0.15*0.9 & 0.15*0.05\\
\hline
$\langle OR,L \rangle$ & $TR$ & 0.15*0.05 & 0.15*0.9 & 0.15*0.05 & 0.85*0.05 & 0.85*0.9 & 0.85*0.05\\
\hline
$\langle *,OL \rangle$ & $*$ & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6\\
\hline
$\langle *,OR \rangle$ & $*$ & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6\\
\hline
\end{tabular}}
\end{scriptsize}
\centerline{Observation functions of agents $i$ and $j$.}
\caption{Transition, reward, and observation functions for the multi-agent Tiger game.}
\label{fig:tables}
\end{minipage}
\end{table}


When  an agent  makes its  choice in  the multi-agent  tiger  game, it
considers what it believes about the location of the tiger, as well as
whether the  other agent  will listen  or open a  door, which  in turn
depends  on the  other  agent's beliefs,  reward function,  optimality
criterion, etc.{\footnote{We assume an  intentional model of the other
agent here.}}  In  particular, if the other agent were  to open any of
the doors  the tiger location  in the next  time step would  be chosen
randomly.  Thus,  the information  obtained from hearing  the previous
growls  would have  to be  discarded.   We simplify  the situation  by
considering  $i$'s I-POMDP with  a single  level of  nesting, assuming
that all of the agent  $j$'s properties, except for beliefs, are known
to  $i$, and  that $j$'s  time horizon  is equal  to $i$'s.   In other
words, $i$'s uncertainty pertains only to $j$'s beliefs and not to its
frame.  Agent $i$'s  interactive state space is, $IS_{i,1}  = S \times
\Theta_{j,0}$, where  $S$ is the  physical state, $S$=\{TL,  TR\}, and
$\Theta_{j,0}$ is a set of  intentional models of agent $j$'s, each of
which differs only in $j$'s beliefs over the location of the tiger.


%'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
\subsection{Examples of the Belief Update}
%'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

In Section~\ref{sec:ipomdps}, we  presented the belief update equation
for  I-POMDPs (Eq.~\ref{eqn:bu}). Here  we consider
examples of  beliefs, $b_{i,1}$, of  agent $i$, which  are probability
distributions over  $S \times \Theta_{j,0}$.  Each 0-th level  type of
agent $j$, $\theta_{j,0} \in  \Theta_{j,0}$, contains a ``flat'' belief
as to the location of the  tiger, which can be represented by a single
probability assignment -- $b_{j,0} = p_j(TL)$.

\begin{figure}[!ht]
\centerline{\begin{minipage}{2.2in}
\includegraphics[width=2.2in]{butracet01.eps}
\includegraphics[width=2.2in]{butracet02.eps}
\centerline{\begin{tiny}$(i)$\end{tiny}}
\end{minipage}
%\begin{minipage}{1.8in}
%\includegraphics[width=1.6in]{beta1.eps}
%\includegraphics[width=1.6in]{beta2.eps}
%\centerline{\begin{tiny}$(ii)$\end{tiny}}
%\end{minipage}
\begin{minipage}{2.3in}
\includegraphics[width=2.4in]{beta3.eps}
\includegraphics[width=2.4in]{beta4.eps}
\centerline{\begin{tiny}$(ii)$\end{tiny}}
\end{minipage}}
\caption{Two examples of singly nested  belief states of agent $i$. In
each case $i$ has no  information about the tiger's location. In $(i)$
agent $i$ knows that $j$ does  not know the location of the tiger; the
single point (star) denotes a Dirac delta function which integrates to
the height of the point, here  0.5 . In $(ii)$ agent $i$ is uninformed
about $j$'s beliefs about tiger's location.}
\label{fig:prior-beliefs}
\end{figure} 

In  Fig.~\ref{fig:prior-beliefs}  we show  some  examples  of level  1
beliefs of agent $i$.  In each  case $i$ does not know the location of
the tiger so that the marginals  in the top and bottom sections of the
figure  sum  up to  0.5  for  probabilities of  TL  and  TR each.   In
Fig.~\ref{fig:prior-beliefs}$(i)$,  $i$  knows  that $j$  assigns  0.5
probability to tiger being behind  the left door.  This is represented
using a Dirac  delta function.  In Fig.~\ref{fig:prior-beliefs}$(ii)$,
agent $i$ is uninformed about $j$'s beliefs.  This is represented as a
uniform  probability density over  all values  of the  probability $j$
could assign to state TL.

To  make the  presentation of  the belief  update more  transparent we
decompose the formula in Eq.~\ref{eqn:bu} into two steps:

\begin{itemize}
\itemsep=0pt
\topsep=0pt\partopsep=0pt \parskip=0pt\parsep=0pt
\parindent=0pt
\item {\em Prediction:} When  agent $i$ performs an action $a_i^{t-1}$,
and given  that agent $j$  performs $a_j^{t-1}$, the  predicted belief
state is:
\begin{equation}\begin{array}{ll}
\widehat{b}_i^t(is^t) = Pr(is^t|a_i^{t-1},a_j^{t-1},b_i^{t-1}) &= 
\sum_{is^{t-1}|\widehat{\theta}_j^{t-1}=\widehat{\theta}_j^t}
b_i^{t-1}(is^{t-1})Pr(a_j^{t-1}|\theta_j^{t-1})\\&\times T(s^{t-1},a^{t-1},s^t)
\underset{o_j^t} {\sum}O_j(s^t,a^{t-1},o_j^t)\\&\times
\tau_{\theta_j^t}(b_j^{t-1},a_j^{t-1},o_j^t,b_j^t)
\end{array}
\label{eqn:IPOMDPbu1}
\end{equation}

\item  {\em  Correction:}  When  agent $i$  perceives  an  observation,
$o_i^t$,         the          predicted         belief         states,\\
$Pr(\cdot|a_i^{t-1},a_j^{t-1},b_i^{t-1})$, are combined according to:
\begin{equation}b_i^t(is^t) = Pr(is^t|o_i^t,a_i^{t-1},b_i^{t-1})= 
\beta\sum_{a_j^{t-1}} O_i(s^t,a^{t-1},o_i^t)Pr(is^t|a_i^{t-1},
a_j^{t-1},b_i^{t-1})
\label{eqn:IPOMDPbu2}
\end{equation}
where $\beta$ is the normalizing constant. 
\end{itemize}

%\begin{figure}[!ht]
%\centerline{\includegraphics[width=3.5in]{tiger.1.team.alpha.eps}}
%\caption{Value function of an agent,  $j$ in this case, whose strategy
%level is  0 and time horizon is  1. We assumed that  the other agent's
%actions are equally likely. Note  that listening is the best action if
%the agent does not have any information about the tiger's location, as
%in the single agent case in Fig.~\ref{fig:ValTigerSingleAgT1}.}
%\label{fig:vf-lev0}
%\end{figure}

\begin{figure}[!ht]
%\centerline{$b_i^{t-1}$        \hspace{1.0in}        $\widehat{b}_i^t$
%\hspace{1.0in}        $b_i^t$        \hspace{1.0in}       $b_i^{t+1}$}
\centerline{\includegraphics[width=6.0in]{belieftrace.eps}}
\centerline{\scriptsize{(a)  \hspace{1.3in} (b)  \hspace{1.3in} (c)
\hspace{1.4in} (d)}}
\caption{A trace of the belief update of agent $i$.  $(a)$ depicts the
 prior.   $(b)$ is  the  result of  prediction  given $i$'s  listening
 action,  L, and  a pair  denoting $j$'s  action and  observation. $i$
 knows that $j$ will listen and  could hear tiger's growl on the right
 or the  left, and that the  probabilities $j$ would assign  to TL are
 0.15 or 0.85, respectively.  $(c)$  is the result of correction after
 $i$   observes   tiger's  growl   on   the   left   and  no   creaks,
 $\langle$GL,S$\rangle$.   The probability  $i$ assigns  to TL  is now
 greater than TR.   $(d)$ depicts the results of  another update (both
 prediction and correction) after another listen action of $i$ and the
 same observation, $\langle$GL,S$\rangle$.}  Each discrete point above
 denotes, again, a Dirac delta function which integrates to the height
 of the point.
 
\label{fig:belieftrace}
\end{figure}

%\begin{figure}[!ht]
%\centerline{
%\begin{minipage}{1.2in}
%\centerline{$b_i^{t-1}$}
%\includegraphics[width=1.2in]{butracet01.eps}\\
%\includegraphics[width=1.2in]{butracet02.eps}\\
%\centerline{(i)}
%\end{minipage}
%\begin{minipage}{1.2in}
%\centerline{$\widehat{b}_i^t$}
%\includegraphics[width=1.2in]{butrace11p.eps}\\
%\includegraphics[width=1.2in]{butrace12p.eps}\\
%\centerline{(ii)}
%\end{minipage}
%\begin{minipage}{1.2in}
%\centerline{$b_i^t$}
%\includegraphics[width=1.2in]{butracet11.eps}\\
%\includegraphics[width=1.2in]{butracet12.eps}\\
%\centerline{(iii)}
%\end{minipage}
%\begin{minipage}{1.2in}
%\centerline{$b_i^{t+1}$}
%\includegraphics[width=1.2in]{butracet21.eps}\\
%\includegraphics[width=1.2in]{butracet22.eps}\\
%\centerline{(iv)}
%\end{minipage}}
%%\centerline{}
%\caption{A trace of the I-POMDP belief update using the multiagent tiger game. 
%%Column (i) shows the initial belief state of agent $i$. Column %(ii) displays the belief state after $i$ listens and perceives %growl-left and no creaks. Column (iii) shows the belief state %after $i$ again listens and perceives growl-left and no creaks.
%}
%\label{fig:belieftrace}
%\end{figure}
%To illustrate the belief update, let us  trace the update process using the multiagent tiger game. 
%We first note that modeling the tiger game as a single-agent horizon 1 POMDP, and solving it gives us a policy which prescribes opening the left door if the agent's belief of the tiger being on the left is less than 0.1, listening for beliefs between 0.1 and 0.9, and opening the right door if the agent's belief is greater than 0.9. 
%To see how the belief update  proceeds, first note that for agent $j$,
%modeled by $i$  as 0-level with time horizon of  1, the value function
%is as depicted in Fig.~\ref{fig:tiger1comp}.  %%Make sure this rfers to
%%the correct Figure...
%Thus, if $i$ knows that $j$
%does not  know the location  of the tiger,  $i$ can conclude  that $j$
%will execute its listen action.

%% since the belief update fig will change, the para below needs to be
%% made consistent with it...
In  Fig.~\ref{fig:belieftrace}, we display  the example  trace through
the  update  of  singly  nested   belief.   In  the  first  column  of
Fig.~\ref{fig:belieftrace}, labeled (a), is  an example of agent $i$'s
prior belief we  introduced before, according to which  $i$ knows that
$j$ is  uninformed of the location of  the tiger.{\footnote{The points
in Fig.~\ref{fig:belieftrace-flat} again  denote Dirac delta functions
which integrate  to the value equal  to the points'  height.}}  Let us
assume that $i$ listens and hears a growl from the left and no creaks.
The  second column  of Fig.~\ref{fig:belieftrace},  (b),  displays the
{\em  predicted}   belief  after   $i$  performs  the   listen  action
(Eq.~\ref{eqn:IPOMDPbu1}). As  part of the prediction  step, agent $i$
must solve $j$'s model to  obtain $j$'s optimal action when its belief
is  0.5  (term  $Pr(a_j^{t-1}|\theta_j)$ in  Eq.~\ref{eqn:IPOMDPbu1}).
Given  the  value   function  in  Fig.~\ref{fig:ValTigerCompT3},  this
evaluates to probability of 1  for listen action, and zero for opening
of any  of the doors.   $i$ also updates  $j$'s belief given  that $j$
listens  and hears the  tiger growling  from either  the left,  GL, or
right,  GR, (term $\tau_{\theta_j^t}(b_j^{t-1},a_j^{t-1},o_j^t,b_j^t)$
in  Eq.~\ref{eqn:IPOMDPbu1}). Agent  $j$'s  updated probabilities  for
tiger being  on the left are 0.85  and 0.15, for $j$'s  hearing GL and
GR,   respectively.   If   the  tiger   is   on  the   left  (top   of
Fig.~\ref{fig:belieftrace} (b))  $j$'s observation GL  is more likely,
and consequently $j$'s  assigning the probability of 0.85  to state TL
is more  likely ($i$  assigns a probability  of 0.425 to  this state.)
When the tiger is  on the right $j$ is more likely  to hear GR and $i$
assigns the lower probability, 0.075, to $j$'s assigning a probability
0.85  to  tiger  being  on  the  left.   The  third  column,  (c),  of
Fig.~\ref{fig:belieftrace} shows  the posterior belief  after the {\em
correction} step.  The belief in  column (b) is updated to account for
$i$'s   hearing    a   growl   from   the   left    and   no   creaks,
$\langle$GL,S$\rangle$.  The resulting marginalised probability of the
tiger being on the left is  higher (0.85) than that of the tiger being
on  the right.  If  we assume  that in  the next  time step  $i$ again
listens and hears the tiger growling  from the left and no creaks, the
belief     state    depicted     in    the     fourth     column    of
Fig.~\ref{fig:belieftrace} results.
%The optimal  action for $i$ is to open the right door.
%

\begin{figure}%[!ht]
%\centerline{$b_i^{t-1}$        \hspace{2.0in}        $\widehat{b}_i^t$
%\hspace{2.0in}        $b_i^t$}        
\centerline{\includegraphics[width=6.0in]{belieftrace11.eps}}
%\centerline{\scriptsize{(a)  \hspace{2.0in} (b)  \hspace{2.0in} (c)}}
\caption{A trace of the belief update of agent $i$.  $(a)$ depicts the
 prior  according to  which  $i$ is  uninformed  about $j$'s  beliefs.
 $(b)$  is the  result of  the prediction  step after  $i$'s listening
 action (L).   The top half of  $(b)$ shows $i$'s belief  after it has
 listened and given that $j$  also listened.  The two observations $j$
 can make, GL  and GR, each with probability  dependent on the tiger's
 location,  give rise  to flat  portions representing  what  $i$ knows
 about  $j$'s belief  in  each case.   The  increased probability  $i$
 assigns  to $j$'s  belief between  0.472 and  0.528 is  due  to $j$'s
 updates after it hears GL and after it hears GR resulting in the same
 values in this interval.  The bottom half of $(b)$ shows $i$'s belief
 after $i$  has listened and $j$ has opened the left  or right door
 (plots are identical for each action  and only one of them is shown).
 $i$ knows that  $j$ has no information about  the tiger's location in
 this  case.  $(c)$  is the  result of  correction after  $i$ observes
 tiger's growl on the  left and no creaks $\langle$GL,S$\rangle$.  The
 plots in $(c)$ are obtained by performing a weighted summation of the
 plots in  $(b)$.  The  probability $i$ assigns  to TL is  now greater
 than TR, and information about $j$'s beliefs allows $i$ to refine its
 prediction of $j$'s action in the next time step.}
\label{fig:belieftrace-flat}
\end{figure}

In Fig.~\ref{fig:belieftrace-flat} we  show the belief update starting
from the  prior in Fig.~\ref{fig:prior-beliefs}  $(ii)$, according to
which agent $i$  initially has no information about  what $j$ believes
about the tiger's location.

The  traces  of   belief  updates  in  Fig.~\ref{fig:belieftrace}  and
Fig.~\ref{fig:belieftrace-flat}  illustrate   the  changing  state  of
information  agent  $i$ has  about  the  other  agent's beliefs.   The
benefit  of representing  these updates  explicitly is  that,  at each
stage, $i$'s optimal behavior depends on its estimate of probabilities
of $j$'s actions.   The more informative these estimates  are the more
value agent $i$ can expect out of the interaction.  Below, we show the
increase in  the value function  for I-POMDPs compared to  POMDPs with
the noise factor.

%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\subsection{Examples of Value Functions}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

\begin{figure}
\centerline{\includegraphics[width=4.0in]{tiger.1.neutral.comp.eps}}
\caption{For  time horizon  of 1  the value  functions  obtained from
  solving  a singly  nested  I-POMDP  and a  POMDP  with noise  factor
  overlap.}
\label{fig:val-fun-ipomdp-pomdp.1}
\end{figure}



\begin{figure}[!ht]
\centerline{\includegraphics[width=5.7in]{tiger.2.neutral.ipomdp.pomdp.comp.eps}}
\caption{Comparison  of  value  functions  obtained from  solving  an
  I-POMDP  and a POMDP  with noise for time  horizon of  2.  I-POMDP
  value function dominates due to  agent $i$ adjusting the behavior of
  agent $j$ to the remaining steps to go in the interaction.}
\label{fig:val-fun-ipomdp-pomdp.2}
\end{figure}

This section  compares value functions  obtained from solving  a POMDP
with a  static noise  factor, accounting for  the presence  of another
agent,{\footnote{The  POMDP   with  noise  is  the   same  as  level-0
I-POMDP.}}  to  value functions of level-1 I-POMDP.   The advantage of
more refined  modeling and update in  I-POMDPs is due  to two factors.
First  is the  ability to  keep track  of the  other agent's  state of
beliefs  to better  predict its  future  actions.  The  second is  the
ability  to adjust the  other agent's  time horizon  as the  number of
steps to  go during  the interaction decreases.   Neither of  these is
possible within the classical POMDP formalism.

\begin{figure}[!ht]
\centerline{\includegraphics[width=4.7in]{tiger.3.neutral.ipomdp.pomdp.comp.no.labels.eps}}
\caption{Comparison  of  value  functions  obtained  from  solving  an
  I-POMDP and a POMDP with noise for time horizon of 3.  I-POMDP value
  function  dominates due  to  agent $i$'s  adjusting $j$'s  remaining
  steps to  go, and due to  $i$'s modeling $j$'s  belief update.  Both
  factors  allow  for  better  predictions  of  $j$'s  actions  during
  interaction.  The  descriptions of individual  policies were omitted
  for      clarity;     they      can     be      read      off     of
  Fig.~\ref{fig:ipomdp.policy.3}.}
\label{fig:val-fun-ipomdp-pomdp.3}
\end{figure}


We continue with the simple example of $\mbox{\textit{I-POMDP}}_{i,1}$
of  agent $i$.   In  Fig.~\ref{fig:val-fun-ipomdp-pomdp.1} we  display
$i$'s value  function for the time  horizon of 1,  assuming that $i$'s
initial belief  as to the  value $j$ assigns  to TL, $p_j(TL)$,  is as
depicted  in  Fig.~\ref{fig:prior-beliefs} $(ii)$,  i.e.   $i$ has  no
information about what $j$ believes about tiger's location. This value
function  is identical  to the  value function  obtained for  an agent
using  a traditional  POMDP framework  with noise,  as well  as single
agent POMDP which  we described in Section~\ref{sec:pomdp-tiger}.  The
value  functions overlap  since agents  do  not have  to update  their
beliefs and  the advantage  of more refined  modeling of agent  $j$ in
$i$'s I-POMDP  does not become  apparent. Put another way,  when agent
$i$ models $j$ using an intentional model, it concludes that agent $j$
will open each  door with probability 0.1 and  listen with probability
0.8.  This   coincides  with   the  noise   factor  we   described  in
Section~\ref{sec:pomdp-tiger}.

In   Fig.~\ref{fig:val-fun-ipomdp-pomdp.2}  we  display   $i$'s  value
functions  for  the  time  horizon   of  2.   The  value  function  of
$\mbox{\textit{I-POMDP}}_{i,1}$ is higher than the value function of a
POMDP  with  a  noise  factor.   The  reason is  not  related  to  the
advantages  of modeling  agent $j$'s  beliefs --  this  effect becomes
apparent at  the time  horizon of 3  and longer.  Rather,  the I-POMDP
solution dominates due to agent $i$ modeling $j$'s time horizon during
interaction:  $i$ knows that  at the  last time  step $j$  will behave
according to its optimal policy for  time horizon of 1, while with two
steps  to  go  $j$ will  optimize  according  to  its  2 steps  to  go
policy. As we  mentioned, this effect cannot be  modeled using a POMDP
with a static noise factor included in the transition function.

Fig.~\ref{fig:val-fun-ipomdp-pomdp.3}  shows a comparison  between the
I-POMDP  and the  noisy  POMDP  value functions  for  horizon 3.   The
advantage of more refined  agent modeling within the I-POMDP framework
has increased.{\footnote{Note that I-POMDP  solution is not as good as
the  solution  of  a  POMDP  for  an  agent  operating  alone  in  the
environment  shown in Fig.~\ref{fig:ValTigerCompT3}.}}   Both factors,
$i$'s  adjusting $j$'s  steps to  go and  $i$'s modeling  $j$'s belief
update  during  interaction are  responsible  for  the superiority  of
values achieved using the I-POMDP.   In particular, recall that at the
second  time step  $i$'s information  as  to $j$'s  beliefs about  the
tiger's  location is  as  depicted in  Fig.~\ref{fig:belieftrace-flat}
(c).  This  enables $i$ to make  a high quality  prediction that, with
two steps left to go, $j$ will  perform its actions OL, L, and OR with
probabilities 0.009076, 0.96591  and 0.02501, respectively (recall that
for POMDP  with noise these  probabilities remained unchanged  at 0.1,
0,8, and 0.1, respectively.)

\begin{figure}[!ht]
\centerline{\includegraphics[width=5.0in]{ipomdp.policy.3.eps}}
\caption{The policy  graph corresponding to the I-POMDP  value function in Fig.~\ref{fig:val-fun-ipomdp-pomdp.3}.}
\label{fig:ipomdp.policy.3}
\end{figure}

%Let us  note that the value  functions for I-POMDPs in  all cases have
%the PWLC property, and that values for longer time horizons refine the
%values for the single step game.  This illustrates the general results
%obtained  in Section~\ref{sec:prop},  of  PWLC of  value function  and
%convergence of value iteration for I-POMDPs.

Fig.~\ref{fig:ipomdp.policy.3} shows agent $i$'s policy graph for time
horizon  of  3. As  usual,  it  prescribes  the optimal  first  action
depending  on the  initial belief  as  to the  tiger's location.   The
subsequent   actions  depend  on   the  observations   received.   The
observations include  creaks that are indicative of  the other agent's
having  opened a door.   The creaks  contain valuable  information and
allow the agent to make more  refined choices, compared to ones in the
noisy POMDP in  Fig.~\ref{fig:pomdp.noise.policy.3}. Consider the case
when agent $i$ starts out with  fairly strong belief as to the tiger's
location, decides to listen (according  to the four off-center top row
``L'' nodes in Fig.~\ref{fig:ipomdp.policy.3}) and hears a door creak.
The agent is then in the position to open either the left or the right
door, even  if that is counter  to its initial belief.   The reason is
that the creak  is an indication that the  tiger's position has likely
been reset  by agent $j$ and  that $j$ will  then not open any  of the
doors during the following two time steps. Now, two growls coming from
the same door  lead to enough confidence to open  the other door. This
is because the agent $i$'s hearing of tiger's growls are indicative of
the tiger's position in the state following the agents' actions,

Note that  the value functions and  the policy above  depict a special
case of  agent $i$  having no information  as to what  probability $j$
assigns    to     tiger's    location    (Fig.~\ref{fig:prior-beliefs}
($ii$)). Accounting  for and visualizing all possible  beliefs $i$ can
have about  $j$'s beliefs  is difficult due  to the complexity  of the
space  of  interactive beliefs.   As  our  ongoing  work indicates,  a
drastic  reduction   in  complexity   is  possible  without   loss  of
information,  and  consequently   representation  of  solutions  in  a
manageable number  of dimensions is  indeed possible.  We  will report
these results separately.

%--------------------------------------------------------------------
\section{Conclusions}
\label{sec:conclusion}
%--------------------------------------------------------------------

We  proposed  a   framework  for  optimal  sequential  decision-making
suitable  for  controlling autonomous  agents  interacting with  other
agents  within  an  uncertain  environment.   We  used  the  normative
paradigm of  decision-theoretic planning under  uncertainty formalized
as partially observable Markov  decision processes (POMDPs) as a point
of departure.  We extended POMDPs  to cases of agents interacting with
other  agents by  allowing them  to have  beliefs not  only  about the
physical  environment, but also  about the  other agents.   This could
include  beliefs about  the others'  abilities,  sensing capabilities,
beliefs,  preferences,  and intended  actions.   Our framework  shares
numerous  properties with POMDPs,  has analogously  defined solutions,
and reduces to POMDPs when agents are alone in the environment.

In     contrast    to     some    recent     work     on    DEC-POMDPs
\cite{Bernstein02:Complexity,Nair03:Taming}, and  to work motivated by
game-theoretic                                               equilibria
\cite{Boutilier99:Sequential,Hu98:Theoretical,Koller01:Multi-Agent,Littman94:Markov},
our  approach  is  subjective  and amenable  to  agents  independently
computing their optimal solutions.

The line  of work presented here  opens an area of  future research on
integrating frameworks  for sequential planning with  elements of game
theory and Bayesian learning  in interactive settings.  In particular,
one of the  avenues of our future research  centers on proving further
formal  properties  of I-POMDPs,  and  establishing clearer  relations
between  solutions  to I-POMDPs  and  various  flavors of  equilibria.
Another concentrates on  developing efficient approximation techniques
for  solving  I-POMDPs.  As  for  POMDPs,  development of  approximate
approaches to I-POMDPs is crucial for moving beyond toy problems.  One
promising  approximation  technique  we  are working  on  is  particle
filtering.  We  are also  devising  methods  for representing  I-POMDP
solutions  without  assumptions  about  what's  believed  about  other
agents' beliefs.  As  we mentioned, in spite of  the complexity of the
interactive state space, there seem to be intuitive representations of
belief  partitions  corresponding to  optimal  policies, analogous  to
those for  POMDPs.  Other research issues include  the suitable choice
of  priors   over  models,{\footnote{We  are   looking  at  Kolmogorov
complexity~\cite{Li97:Introduction}  as  a   possible  way  to  assign
priors.}}  and  the ways to fulfill the  absolute continuity condition
needed for  convergence of  probabilities assigned to  the alternative
models during interactions ~\cite{Kalai93:Rational}.


%---------------------------------------------------------------------
\section*{Acknowledgments}
%---------------------------------------------------------------------
This research  is supported by the National  Science Foundation CAREER
award IRI-9702132, and NSF award IRI-0119270.

\appendix
\section{Proofs}

\begin{proof}[Proof of Propositions  1 and  2]

We start with Proposition 2, by applying the Bayes Theorem:

\begin{equation}\begin{array}{l}
b_i^t(is^t)= Pr(is^t|o_i^t, a_i^{t-1}, b_i^{t-1}) = 
 \frac{Pr(is^t,o_i^t|a_i^{t-1},b_i^{t-1})}{Pr(o_i^t|a_i^{t-1},b_i^{t-1})}\\\\
= \beta \sum_{is^{t-1}}b_i^{t-1}(is^{t-1})Pr(is^t,o_i^t|a_i^{t-1},is^{t-1})\\
= \beta \sum_{is^{t-1}}b_i^{t-1}(is^{t-1})\sum_{a_j^{t-1}}Pr(is^t,o_i^t|a_i^{t-1},a_j^{t-1},is^{t-1})
Pr(a_j^{t-1}|a_i^{t-1},is^{t-1})\\
= \beta \sum_{is^{t-1}}b_i^{t-1}(is^{t-1})\sum_{a_j^{t-1}}Pr(is^t,o_i^t|a_i^{t-1},a_j^{t-1},is^{t-1})
Pr(a_j^{t-1}|is^{t-1})\\
= \beta \sum_{is^{t-1}}b_i^{t-1}(is^{t-1})\sum_{a_j^{t-1}}Pr(a_j^{t-1}|m_j^{t-1})
Pr(o^i_t|is^t,a^{t-1},is^{t-1}) 
Pr(is^t|a^{t-1},is^{t-1})\\
= \beta \sum_{is^{t-1}}b_i^{t-1}(is^{t-1})\sum_{a_j^{t-1}}Pr(a_j^{t-1}|m_j^{t-1})
Pr(o^i_t|is^t, a^{t-1})
Pr(is^t|a^{t-1}, is^{t-1})\\
= \beta \sum_{is^{t-1}}b_i^{t-1}(is^{t-1})\sum_{a_j^{t-1}}Pr(a_j^{t-1}|m_j^{t-1})
O_i(s^t,a^{t-1},o_i^t)
Pr(is^t|a^{t-1},is^{t-1})\\
\end{array}\label{eqn:main}\end{equation}

%\begin{equation}\begin{array}{ll}
%Pr(is^t|a^{t-1}, is^{t-1}) &= \sum_{o_j^t}
%\overset{{\bf 1}}{Pr(is^t|a^{t-1},is^{t-1},o_j^t)}\overset{{\bf 2}}{Pr(o_j^t|a^{t-1},is^{t-1})}
%\end{array}\label{eqn:derv2}\end{equation}

To simplify  the  term  $Pr(is^t|a^{t-1},is^{t-1})$ let  us
substitute   the  interactive  state   $is^t$  with   its  components. 
When $m_j$ in the interactive states is intentional: $is^t=(s^t,\theta_j^t)=(s^t,b_j^t,\widehat{\theta}_j^t)$.
\begin{equation}\begin{array}{ll}
Pr(is^t|a^{t-1},is^{t-1}) &= Pr(s^t,b_j^t,\widehat{\theta}_j^t|a^{t-1},is^{t-1})\\
&= Pr(b_j^t|s^t,\widehat{\theta}_j^t,a^{t-1},is^{t-1})
Pr(s^t,\widehat{\theta}_j^t|a^{t-1},is^{t-1})\\
&= Pr(b_j^t|s^t,\widehat{\theta}_j^t,a^{t-1},is^{t-1})
Pr(\widehat{\theta}_j^t|s^t,a^{t-1},is^{t-1})Pr(s^t|a^{t-1},is^{t-1})\\
&= Pr(b_j^t|s^t,\widehat{\theta}_j^t,a^{t-1},is^{t-1})
I(\widehat{\theta}_j^{t-1},\widehat{\theta}_j^t)T_i(s^{t-1},a^{t-1},s^t)
\end{array}\label{eqn:trans}\end{equation}
When $m_j$ is subintentional: $is^t=(s^t,m_j^t)=(s^t,h_j^t,\widehat{m}_j^t)$.
$$\begin{array}{ll}
Pr(is^t|a^{t-1},is^{t-1}) &= Pr(s^t,h_j^t,\widehat{m}_j^t|a^{t-1},is^{t-1})\\
&= Pr(h_j^t|s^t,\widehat{m}_j^t,a^{t-1},is^{t-1})
Pr(s^t,\widehat{m}_j^t|a^{t-1},is^{t-1})\\
&= Pr(h_j^t|s^t,\widehat{m}_j^t,a^{t-1},is^{t-1})
Pr(\widehat{\theta}_j^t|s^t,a^{t-1},is^{t-1})Pr(s^t|a^{t-1},is^{t-1})\\
&= Pr(h_j^t|s^t,\widehat{m}_j^t,a^{t-1},is^{t-1})
I(\widehat{m}_j^{t-1},\widehat{m}_j^t)T_i(s^{t-1},a^{t-1},s^t) \hspace{0.7in} $(14')$
\end{array}$$

The joint action pair, $a^{t-1}$,  may change the physical state.  The
third term on  the right-hand side of Eqs.~\ref{eqn:trans} and $14'$ above captures  this transition. We
utilized  the MNM  assumption  to  replace the  second  terms of the equations with boolean
identity functions, $I(\widehat{\theta}_j^{t-1},\widehat{\theta}_j^t)$ and $I(\widehat{m}_j^{t-1},\widehat{m}_j^t)$ respectively,
which equal 1 if the two  frames are identical, and 0 otherwise. Let us turn our attention to the first terms. If $m_j$ in $is^t$ and $is^{t-1}$ is intentional:

\begin{equation}\begin{array}{ll}
Pr(b_j^t|s^t,\widehat{\theta}_j^t,a^{t-1},is^{t-1}) &= \sum_{o_j^t} Pr(b_j^t|s^t,\widehat{\theta}_j^t,a^{t-1},is^{t-1},o_j^t)
Pr(o_j^t|s^t,\widehat{\theta}_j^t,a^{t-1},is^{t-1})\\
&= \sum_{o_j^t} Pr(b_j^t|s^t,\widehat{\theta}_j^t,a^{t-1},is^{t-1},o_j^t)
Pr(o_j^t|s^t,\widehat{\theta}_j^t,a^{t-1})\\
&=\sum_{o_j^t} \tau_{\theta_j^t}(b_j^{t-1},a_j^{t-1}, o_j^t, b_j^t)
O_j(s_t,a^{t-1},o_j^t)
\end{array}\label{eqn:tau}
\end{equation}
Else if it is subintentional:
$$\begin{array}{ll}
Pr(h_j^t|s^t,\widehat{m}_j^t,a^{t-1},is^{t-1}) &= \sum_{o_j^t} Pr(h_j^t|s^t,\widehat{m}_j^t,a^{t-1},is^{t-1},o_j^t)
Pr(o_j^t|s^t,\widehat{m}_j^t,a^{t-1},is^{t-1})\\
&= \sum_{o_j^t} Pr(h_j^t|s^t,\widehat{m}_j^t,a^{t-1},is^{t-1},o_j^t)
Pr(o_j^t|s^t,\widehat{m}_j^t,a^{t-1})\\
&=\sum_{o_j^t} \delta_K(\mbox{APPEND}(h_j^{t-1},o_j^t), h_j^t)
O_j(s_t,a^{t-1},o_j^t) \hspace{0.75in} $(15')$
\end{array}$$
In Eq.~\ref{eqn:tau}, the first term on the right-hand  side is 1 if agent $j$'s  belief update, $SE_{\theta_j}(b_j^{t-1},a_j^{t-1},o_j^t)$
generates a belief  state equal to $b_j^t$. Similarly, in Eq. $15'$, the first term is 1 if appending the $o_j^t$ to $h_j^{t-1}$ results in $h_j^t$. $\delta_K$ is the Kronecker delta function.
In the second terms on the right-hand side of the equations,
the  MNO  assumption makes  it  possible to  replace
$Pr(o_j^t|s^t,\widehat{\theta}_j^t,a^{t-1})$ with
$O_j(s^t,a^{t-1},o_j^t)$, and $Pr(o_j^t|s^t,\widehat{m}_j^t,a^{t-1})$ with $O_j(s^t,a^{t-1},o_j^t)$ respectively.

Let us now substitute Eq.~\ref{eqn:tau} into Eq.~\ref{eqn:trans}. 
\begin{equation}\begin{array}{ll}
Pr(is^t|a^{t-1},is^{t-1}) &= \sum_{o_j^t} \tau_{\theta_j^t}(b_j^{t-1},a_j^{t-1}, o_j^t, b_j^t)
O_j(s^t,a^{t-1},o_j^t)I(\widehat{\theta}_j^{t-1},\widehat{\theta}_j^t)T_i(s^{t-1},a^{t-1},s^t)
\end{array}\label{eqn:transf}\end{equation}

Substituting Eq. $15'$ into Eq. $14'$ we get,
$$\begin{array}{ll}
Pr(is^t|a^{t-1},is^{t-1}) &= \sum_{o_j^t} \delta_K(\mbox{APPEND}(h_j^{t-1}, o_j^t), h_j^t)
O_j(s^t,a^{t-1},o_j^t)I(\widehat{m}_j^{t-1},\widehat{m}_j^t)\\
&\times T_i(s^{t-1},a^{t-1},s^t)\hspace{3.15in} $(16')$
\end{array}$$

Replacing Eq.~\ref{eqn:transf} into Eq.~\ref{eqn:main} we get:

\begin{equation}\begin{array}{ll}
b_i^t(is^t) &= \beta \sum_{is^{t-1}}b_i^{t-1}(is^{t-1})\sum_{a_j^{t-1}}Pr(a_j^{t-1}|\theta_j^{t-1})O_i(s^t,a^{t-1},o_i^t)
\sum_{o_j^t} \tau_{\theta_j^t}(b_j^{t-1},a_j^{t-1},o_j^t,b_j^t)\\
&\times O_j(s^t, a^{t-1},o_j^t)I(\widehat{\theta}_j^{t-1},\widehat{\theta}_j^t) T_i(s^{t-1},a^{t-1},s^t)
\label{eqn:proof-bu1}\end{array}\end{equation}

Similarly, replacing Eq.~$16'$ into Eq.~\ref{eqn:main} we get:

$$\begin{array}{ll}b_i^t(is^t) &= \beta \sum_{is^{t-1}}b_i^{t-1}(is^{t-1})\sum_{a_j^{t-1}}Pr(a_j^{t-1}|m_j^{t-1})O_i(s^t,a^{t-1},o_i^t)\\
&\times\sum_{o_j^t} \delta_K(\mbox{APPEND}(h_j^{t-1},o_j^t),h_j^t)
 O_j(s^t,a^{t-1},o_j^t)I(\widehat{m}_j^{t-1},\widehat{m}_j^t) T_i(s^{t-1},a^{t-1},s^t)\end{array}$$\hspace{5.75in}$(17')$

We arrive  at the final expressions for the belief update  by removing the
terms $I(\widehat{\theta}_j^{t-1},\widehat{\theta}_j^t)$ and $I(\widehat{m}_j^{t-1},\widehat{m}_j^t)$  and
changing the scope of the first summations.

When $m_j$ in the interactive states is intentional:

\begin{equation}\begin{array}{ll}
b_i^t(is^t) &= \beta \sum_{is^{t-1}:\widehat{m}_j^{t-1}=\widehat{\theta}_j^t}b_i^{t-1}(is^{t-1})\sum_{a_j^{t-1}}Pr(a_j^{t-1}|\theta_j^{t-1})O_i(s^t,a^{t-1},o_i^t)\\
&\times \sum_{o_j^t} \tau_{\theta_j^t}(b_j^{t-1},a_j^{t-1},o_j^t,b_j^t)
O_j(s^t, a^{t-1},o_j^t) T_i(s^{t-1},a^{t-1},s^t)
\end{array}\end{equation}

Else, if it is subintentional:
\begin{equation}\begin{array}{ll}
b_i^t(is^t) &= \beta \sum_{is^{t-1}:\widehat{m}_j^{t-1}=\widehat{m}_j^t}b_i^{t-1}(is^{t-1})\sum_{a_j^{t-1}}Pr(a_j^{t-1}|m_j^{t-1})O_i(s^t,a^{t-1},o_i^t)\\
&\times \sum_{o_j^t} \delta_K(\mbox{APPEND}(h_j^{t-1},o_j^t),h_j^t)
O_j(s^t, a^{t-1},o_j^t) T_i(s^{t-1},a^{t-1},s^t)
\end{array}\end{equation}

Since  proposition 2 expresses  the belief  $b_i^t(is^t)$ in  terms of
parameters  of the  previous time  step only,  Proposition 1  holds as
well.
\end{proof}

Before we  present the  proof of Theorem~\ref{thm:convergence}  we note
that the  Equation~\ref{eqn:valuefunc}, which defines  value iteration
in  I-POMDPs,  can  be  rewritten   in  the  following  form,  $U^n  =
HU^{n-1}$. Here, $H : B \rightarrow B$ is a {\em backup} operator, and
is defined as,
$$HU^{n-1}(\theta_i) = \underset{a_i \in A_i}{max} ~h(\theta_i,a_i,U^{n-1})$$ 
where $h : \Theta_i \times A_i \times B \rightarrow \Real$ is,
$$\begin{array}{ll}h(\theta_i,a_i,U)                                 &=
\underset{is}{\sum}b_i(is)ER_i(is, a_i)+  \gamma \sum_{o \in \Omega_i}
Pr(o_i|a_i,        b_i)        U(\langle SE_{\theta_i}(b_i,        a_i,
o_i),\hat{\theta}_i\rangle)\end{array}$$ and  where $B$ is  the set of
all bounded  value functions $U$.  Lemmas 1 and 2  establish important
properties of the  backup operator.  Proof of Lemma  1 is given below,
and proof of Lemma 2 follows thereafter.

\begin{proof}[Proof of Lemma 1]
Select arbitrary value functions $V$ and $U$ such that $V(\theta_{i,l}) \leq U(\theta_{i,l})~~ \forall \theta_{i,l} \in \Theta_{i,l}$. Let $\theta_{i,l}$ be an arbitrary type of agent $i$. 

$$\begin{array}{ll}HV(\theta_{i,l}) &= \underset{a_i \in A_i}{max}\bigg\{\sum_{is}b_i(is)ER_i(is,
a_i)+ \gamma \sum_{o \in \Omega_i} Pr(o_i|a_i, b_i)
V(\langle SE_{\theta_{i,l}}(b_i, a_i, o_i),\hat{\theta}_i\rangle)\bigg\}\\
&= \sum_{is}b_i(is)ER_i(is,a_i^*) + \gamma \sum_{o \in \Omega_i} Pr(o_i|a_i^*, b_i) V(\langle SE_{\theta_{i,l}}(b_i, a_i^*, o_i),\hat{\theta}_i\rangle)\\
&\leq \sum_{is}b_i(is)ER_i(is,a_i^*) + \gamma \sum_{o \in \Omega_i} Pr(o_i|a_i^*, b_i) U(\langle SE_{\theta_{i,l}}(b_i, a_i^*, o_i),\hat{\theta}_i\rangle)\\
&\leq \underset{a_i \in A_i}{max}\bigg\{\sum_{is}b_i(is)ER_i(is,a_i) + \gamma \sum_{o \in \Omega_i} Pr(o_i|a_i, b_i) U(\langle SE_{\theta_{i,l}}(b_i, a_i, o_i),\hat{\theta}_i\rangle)\bigg\}\\
&= HU(\theta_{i,l})
\end{array}$$

Since $\theta_{i,l}$  is arbitrary,  $HV \leq HU$. 
\end{proof}

\begin{proof}[Proof of Lemma 2]
Assume two  arbitrary well  defined value functions  $V$ and  $U$ such
that  $V \leq  U$. From  Lemma 1  it follows  that $HV  \leq  HU$. Let
$\theta_{i,l}$ be an arbitrary type of agent $i$. Also, let $a_i^*$ be
the action that optimizes $HU(\theta_{i,l})$.

$$\begin{array}{ll}
0 &\leq HU(\theta_{i,l}) - HV(\theta_{i,l})\\
&= \underset{a_i \in A_i}{max} \bigg\{sum_{is}b_i(is)ER_i(is,
a_i) + \gamma \sum_{o \in \Omega_i} Pr(o_i|a_i, b_i)
U (SE_{\theta_{i,l}}(b_i, a_i, o_i),\langle\hat{\theta}_i\rangle)\bigg\} ~- \\
&~~~~\underset{a_i \in A_i}{max}\bigg\{\sum_{is}b_i(is)ER_i(is,
a_i) + \gamma \sum_{o \in \Omega_i} Pr(o_i|a_i, b_i)
V(SE_{\theta_{i,l}}(b_i, a_i, o_i),\langle\hat{\theta}_i\rangle)\bigg\}\\
&\leq \sum_{is}b_i(is)ER_i(is,a_i^*) + \gamma \sum_{o \in \Omega_i} Pr(o_i|a_i^*, b_i)
U (SE_{\theta_{i,l}}(b_i, a_i^*, o_i),\langle\hat{\theta}_i\rangle) ~- \\
&~~~~\sum_{is}b_i(is)ER_i(is,
a_i^*) - \gamma \sum_{o \in \Omega_i} Pr(o_i|a_i^*, b_i)
V(SE_{\theta_{i,l}}(b_i, a_i^*, o_i),\langle\hat{\theta}_i\rangle)\\
&= \gamma \sum_{o \in \Omega_i} Pr(o_i|a_i^*, b_i)
U (SE_{\theta_{i,l}}(b_i, a_i^*, o_i),\langle\hat{\theta}_i\rangle) -
\\&  \gamma \sum_{o \in \Omega_i} Pr(o_i|a_i^*, b_i)
V(SE_{\theta_{i,l}}(b_i, a_i^*, o_i),\langle\hat{\theta}_i\rangle)\\
&=\gamma \sum_{o \in \Omega_i} Pr(o_i|a_i^*, b_i)\bigg[U (SE_{\theta_{i,l}}(b_i, a_i^*, o_i),\langle\hat{\theta}_i\rangle) - V(SE_{\theta_{i,l}}(b_i, a_i^*, o_i),\langle\hat{\theta}_i\rangle)\bigg\}\\
&\leq \gamma \sum_{o \in \Omega_i} Pr(o_i|a_i^*, b_i)|| U - V ||\\
&=\gamma || U - V ||\\
\end{array}$$

As the supremum  norm is symmetrical, a similar  result can be derived
for  $HV(\theta_{i,l}) -  HU(\theta_{i,l})$.  Since $\theta_{i,l}$  is
arbitrary, the Contraction property  follows, i.e. $||HV - HU||
\leq ||V - U||$.
\end{proof}

Lemmas   1   and  2   provide   the   stepping   stones  for   proving
Theorem~\ref{thm:convergence}.  Proof of Theorem~\ref{thm:convergence}
follows from a straightforward  application of the Contraction Mapping
Theorem.     We    state     the    Contraction     Mapping    Theorem
\cite{Stokey89:Recursive} below:

\begin{thm}[Contraction Mapping Theorem]If $(S,\rho)$ is a complete metric space and $T:S \rightarrow S$ is a contraction mapping with modulus $\gamma$, then
\begin{enumerate}
\item $T$ has exactly one fixed point $U^*$ in $S$, and
\item The sequence $\{U^n\}$ converges to $U^*$.
\end{enumerate}
\label{thm:cmt}
\end{thm}

Proof of Theorem~\ref{thm:convergence} follows.

\begin{proof}[Proof of Theorem~\ref{thm:convergence}] 
The normed space $(B,||\cdot||)$  is complete w.r.t the metric induced
by the supremum norm. Lemma  2 establishes the contraction property of
the   backup   operator,   $H$.   Using   Theorem~\ref{thm:cmt},   and
substituting $T$ with $H$,  convergence of value iteration in I-POMDPs
to a unique fixed point is established.
\end{proof}

We go on  to the piecewise linearity and  convexity (PWLC) property of
the value  function.  We  follow the outlines  of the analogous  proof for POMDPs in ~\cite{Hauskrecht97:Planning,Smallwood73:Optimal}.

Let  $\alpha :  IS \rightarrow  \Real$  be a  real-valued and  bounded
function.  Let the  space  of such  real-valued  bounded functions  be
$B(IS)$. We will now define an inner product.

\begin{defn}[Inner product]
Define the inner product,  $\langle \cdot,\cdot \rangle : B(IS) \times
\Delta(IS) \rightarrow \Real$, by
$$
\langle \alpha, b_i \rangle = \sum_{is} b_i(is)\alpha(is)
$$
\end{defn}

The next lemma establishes the bilinearity of the inner product defined above. 

\begin{lem}[Bilinearity]
For  any  $s,t  \in  \Real$,  $f,g  \in  B(IS)$,  and  $b,\lambda  \in
\Delta(IS)$ the following equalities hold:
$$\begin{array}{l}
	\langle sf+tg,b \rangle = s\langle f,b \rangle + t\langle g,b \rangle\\
	\langle f,sb+t\lambda \rangle = s\langle f,b \rangle + t\langle f,\lambda \rangle
\end{array}$$
\label{lem:bilinearity}
\end{lem}

We     are     now     ready      to     give     the     proof     of
Theorem~\ref{thm:PWLC}.        Theorem~\ref{thm:PWLC2}        restates
Theorem~\ref{thm:PWLC}   mathematically,   and   its   proof   follows
thereafter.

\begin{thm}[PWLC] 
The value  function, $U^n$, in  finitely nested I-POMDP  is piece-wise
linear and convex (PWLC). Mathematically,


$$U^n(\theta_{i,l})          =          \underset{\alpha^n}{max}\sum_{is}b_i(is)\alpha^n(is)~~~~~~ n=1,2,...$$
\label{thm:PWLC2}
\end{thm}\begin{proof}[Proof of Theorem~\ref{thm:PWLC2}]

{\bf Basis Step:} $n=1$

From Bellman's Dynamic Programming equation,

\begin{equation}U^1(\theta_i) = \underset{a_i}{max}\sum_{is}b_i(is)ER(is,a_i)
\label{eqn:horizon1}
\end{equation}

where  $ER_i(is,a_i)  =  \sum_{a_j} R(is,a_i,a_j)Pr(a_j|m_j)$.   Here,
$ER_i(\cdot)$  represents the  expectation of  $R$ w.r.t.  agent $j$'s
actions. Eq.~\ref{eqn:horizon1} represents  an inner product and using
Lemma~\ref{lem:bilinearity}, the inner product is linear in $b_i$.  By
selecting the  maximum of  a set of  linear vectors  (hyperplanes), we
obtain a PWLC horizon 1 value function.

{\bf  Inductive Hypothesis:}  Suppose that  $U^{n-1}(\theta_{i,l})$ is
PWLC. Formally we have,


\begin{equation}\begin{array}{ll}
U^{n-1}(\theta_{i,l}) &=  \underset{\alpha^{n-1}}{max}\sum_{is}b_i(is)\alpha^{n-1}(is)\\
&= \underset{\dot{\alpha}^{n-1},~\ddot{\alpha}^{n-1}}{max}\bigg\{\sum_{is:m_j\in IM_j}b_i(is)\dot{\alpha}^{n-1}(is) + \sum_{is:m_j\in SM_j}b_i(is)\ddot{\alpha}^{n-1}(is)\bigg\}

%= \underset{\alpha^{n-1} \in
%\Gamma^{n-1}}{max} \langle  \alpha^{n-1},b_i^t\rangle
\end{array}\end{equation}


{\bf Inductive Proof:} To show that $U^n(\theta_{i,l})$ is PWLC.

$$U^n(\theta_{i,l})                                                   =
\underset{a_i^{t-1}}{max}\Bigg\{\sum_{is^{t-1}}b_i^{t-1}(is^{t-1})ER_i(is^{t-1},a_i^{t-1})+\gamma\sum_{o_i^t}Pr(o_i^t|a_i^{t-1},b_i^{t-1})U^{n-1}(\theta_{i,l})\Bigg\}$$

From the inductive hypothesis:
$$\begin{array}{ll}U^n(\theta_{i,l}) =
\underset{a_i^{t-1}}{max}\Bigg\{&\sum_{is^{t-1}}b_i^{t-1}(is^{t-1})ER_i(is^{t-1},a_i^{t-1})\\                                             &+\gamma\sum_{o_i^t}Pr(o_i^t|a_i^{t-1},b_i^{t-1})\underset{\alpha^{n-1}
\in\Gamma^{n-1}}{max}\sum_{is^t}b_i^t(is^t)\alpha^{n-1}(is^t)\Bigg\}\end{array}$$

Let $l(b_i^{t-1},a_i^{t-1},o_i^t)$  be the  index of the  alpha vector
that       maximizes      the       value       at      $b_i^t       =
SE(b_i^{t-1},a_i^{t-1},o_i^t)$. Then,
$$\begin{array}{ll}U^n(\theta_{i,l})                                  =
\underset{a_i^{t-1}}{max}\Bigg\{&\sum_{is^{t-1}}b_i^{t-1}(is^{t-1})ER_i(is^{t-1},a_i^{t-1})\\
&+\gamma\sum_{o_i^t}Pr(o_i^t|a_i^{t-1},b_i^{t-1})\sum_{is^t}b_i^t(is^t)\alpha^{n-1}_{l(b_i^{t-1},a_i^{t-1},o_i^t)}\Bigg\}\end{array}$$

From the second equation in the inductive hypothesis:
$$\begin{array}{ll}U^n(\theta_{i,l})                                  =
\underset{a_i^{t-1}}{max}\Bigg\{&\sum_{is^{t-1}}b_i^{t-1}(is^{t-1})ER_i(is^{t-1},a_i^{t-1})+\gamma\sum_{o_i^t}Pr(o_i^t|a_i^{t-1},b_i^{t-1})\\
&\times\bigg\{\sum_{is^t:m_j^t \in IM_j}b_i^t(is^t)\dot{\alpha}^{n-1}_{l(b_i^{t-1},a_i^{t-1},o_i^t)}
+ \sum_{is^t:m_j^t \in SM_j}b_i^t(is^t)\ddot{\alpha}^{n-1}_{l(b_i^{t-1},a_i^{t-1},o_i^t)}
\bigg\}\Bigg\}\end{array}$$

Substituting $b_i^t$  with the appropriate belief updates from  Eqs.~\ref{eqn:proof-bu1} and~$17'$ we get:
$$\begin{array}{ll}  U^n(\theta_{i,l}) &=\underset{a_i^{t-1}}{max}\Bigg\{\sum_{is^{t-1}}b_i^{t-1}(is^{t-1})ER_i(is^{t-1},a_i^{t-1})+ \gamma\sum_{o_i^t}Pr(o_i^t|a_i^{t-1},b_i^{t-1})\\      
&\times\beta\Bigg[\sum_{is^t:m_j^t\in IM_j}\sum_{is^{t-1}}b_i^{t-1}(is^{t-1})\bigg\{\sum_{a_j^{t-1}}Pr(a_j^{t-1}|\theta_j^{t-1})\bigg[O_i(s^t,a^{t-1},o_i^t)\\ 
&  \times\sum_{o_j^t}O_j^t(s^t,a^{t-1},o_j^t)   
\bigg\{\tau_{\theta_j^t}(b_j^{t-1},a_j^{t-1},o_j^t,b_j^t)I(\widehat{\theta}_j^{t-1},\widehat{\theta}_j^t)T_i(s^{t-1},a^{t-1},s^t)\bigg\}\bigg]\bigg\}\\
&\times\dot{\alpha}^{n-1}_{l(b_i^{t-1},a_i^{t-1},o_i^t)}(is^t)\\
&+ \sum_{is^t:m_j^t \in SM_j}\sum_{is^{t-1}}b_i^{t-1}(is^{t-1})
\bigg\{\sum_{a_j^{t-1}}Pr(a_j^{t-1}|m_j^{t-1})\bigg[O_i(s^t,
a^{t-1},o_i^t)\\
&\times\sum_{o_j^t}O_j^t(s^t,a^{t-1},o_j^t)
\bigg\{\delta_K(\mbox{APPEND}(h_j^{t-1},o_j^t)-h_j^{t})I(\widehat{m}_j^{t-1},\widehat{m}_j^t)T_i(s^{t-1},a^{t-1},s^t)\bigg\}\bigg]\bigg\} \\
&\times\ddot{\alpha}^{n-1}_{l(b_i^{t-1},a_i^{t-1},o_i^t)}(is^t)\Bigg]\Bigg\}\\      
\end{array}$$ and further
%&=
$$\begin{array}{ll}U^n(\theta_{i,l})                                  &=
\underset{a_i^{t-1}}{max}\Bigg\{\sum_{is^{t-1}}b_i^{t-1}(is^{t-1})ER_i(is^{t-1},a_i^{t-1})+ \gamma\sum_{o_i^t}\Bigg[\sum_{is^t:m_j^t\in IM_j}\\      
&\times\sum_{is^{t-1}}b_i^{t-1}(is^{t-1})\bigg\{\sum_{a_j^{t-1}}Pr(a_j^{t-1}|\theta_j^{t-1})\bigg[O_i(s^t,a^{t-1},o_i^t)\\ 
&  \times\sum_{o_j^t}O_j^t(s^t,a^{t-1},o_j^t)   
\bigg\{\tau_{\theta_j^t}(b_j^{t-1},a_j^{t-1},o_j^t,b_j^t)I(\widehat{\theta}_j^{t-1},\widehat{\theta}_j^t)T_i(s^{t-1},a^{t-1},s^t)\bigg\}\bigg]\bigg\}\\
&\times\dot{\alpha}^{n-1}_{l(b_i^{t-1},a_i^{t-1},o_i^t)}(is^t)\\
&+ \sum_{is^t:m_j^t \in SM_j}\sum_{is^{t-1}}b_i^{t-1}(is^{t-1})
\bigg\{\sum_{a_j^{t-1}}Pr(a_j^{t-1}|m_j^{t-1})\bigg[O_i(s^t,
a^{t-1},o_i^t)\\
&\times\sum_{o_j^t}O_j^t(s^t,a^{t-1},o_j^t)
\bigg\{\delta_K(\mbox{APPEND}(h_j^{t-1},o_j^t)-h_j^{t})I(\widehat{m}_j^{t-1},\widehat{m}_j^t)T_i(s^{t-1},a^{t-1},s^t)\bigg\}\bigg]\bigg\} \\
&\times\ddot{\alpha}^{n-1}_{l(b_i^{t-1},a_i^{t-1},o_i^t)}(is^t)\Bigg]\Bigg\}\\
\end{array}$$

Rearranging the terms of the equation:
$$\begin{array}{ll}                                 U^n(\theta_{i,l})&=
\underset{a_i^{t-1}}{max}\Bigg\{\sum_{is^{t-1}:m_j^{t-1} \in IM_j}b_i^{t-1}(is^{t-1})\bigg\{ER_i(is^{t-1},a_i^{t-1})+
\gamma\sum_{o_i^t}\sum_{is^{t}:m_j^t \in IM_j}\\
&\times\bigg\{\sum_{a_j^{t-1}}Pr(a_j^{t-1}|\theta_j^{t-1})
 \bigg[O_i(s^t,a^{t-1},o_i^t)
\sum_{o_j^t}O_j^t(s^t,a^{t-1},o_j^t)\\
&\times\bigg\{\tau_{\theta_j^t}(b_j^{t-1},a_j^{t-1},o_j^t,b_j^t)I(\widehat{\theta}_j^{t-1},\widehat{\theta}_j^t)T_i(s^{t-1},a^{t-1},s^t)\bigg\}\bigg]\bigg\}
\dot{\alpha}^{n-1}_{l(b_i^{t-1},a_i^{t-1},o_i^t)}(is^t)\bigg\}\\
&+\sum_{is^{t-1}:m_j^{t-1} \in SM_j}b_i^{t-1}(is^{t-1})\bigg\{ER_i(is^{t-1},a_i^{t-1})+
\gamma\sum_{o_i^t}\sum_{is^{t}:m_j^t \in SM_j}\sum_{o_i^t}\\
&\times\bigg\{\sum_{a_j^{t-1}}Pr(a_j^{t-1}|m_j^{t-1})
 \bigg[O_i(s^t,a^{t-1},o_i^t)
\sum_{o_j^t}O_j^t(s^t,a^{t-1},o_j^t)\\
&\times\bigg\{\delta_K(\mbox{APPEND}(h_j^{t-1},o_j^t)-h_j^t)I(\widehat{m}_j^{t-1},\widehat{m}_j^t)T_i(s^{t-1},a^{t-1},s^t)\bigg\}\bigg]\bigg\}
\ddot{\alpha}^{n-1}_{l(b_i^{t-1},a_i^{t-1},o_i^t)}(is^t)\bigg\}\Bigg\}
\\    
&=\underset{a_i^{t-1}}{max}\bigg\{\sum_{is^{t-1}:m_j^{t-1}\in IM_j}b_i^{t-1}(is^{t-1})\dot{\alpha}^n_{a_i}(is^{t-1})\\
&+\sum_{is^{t-1}:m_j^{t-1}\in SM_j}b_i^{t-1}(is^{t-1})\ddot{\alpha}^n_{a_i}(is^{t-1})\bigg\}\\
\end{array}$$

Therefore,

\begin{equation}\begin{array}{ll}
U^n(\theta_{i,l})         &=        \underset{\dot{\alpha}^n, ~\ddot{\alpha}^n}  {max}\bigg\{\sum_{is^{t-1}:m_j^{t-1}\in IM_j}b_i^{t-1}(is^{t-1})\dot{\alpha}^n(is^{t-1})\\
&+\sum_{is^{t-1}:m_j^{t-1}\in SM_j}b_i^{t-1}(is^{t-1})\ddot{\alpha}^n(is^{t-1})\bigg\}\\
&=       
\underset{\alpha^n} {max}\sum_{is^{t-1}}b_i^{t-1}(is^{t-1})\alpha^n(is^{t-1})
=\underset{\alpha^n} {max}\langle b_i^{t-1},\alpha^n \rangle\\


%\underset{\dot{\alpha}^n_{a_i},~\ddot{\alpha}^n_{a_i}}{max}\bigg\{\langle \dot{\alpha}^n_{a_i},b_i^{t-1} \rangle + \langle \ddot{\alpha}^n_{a_i},b_i^{t-1} \rangle \bigg\}
\label{eqn:horizonn}
\end{array}
\end{equation}
where, if $m_j^{t-1}$ in $is^{t-1}$ is intentional then $\alpha^n = \dot{\alpha}^n$:
$$\begin{array}{ll}          \dot{\alpha}^n(is^{t-1})         &=
ER_i(is^{t-1},a_i^{t-1})                  +                 \gamma
\sum_{o_i^t}\sum_{is^t:m_j^t \in IM_j}\bigg\{\sum_{a_j^{t-1}}Pr(a_j^{t-1}|\theta_j^{t-1})\bigg[O_i(is^t,
a^{t-1},o_i^t)\\    &\times    \sum_{o_j^t}O_j^t(is_j^t,a^{t-1},o_j^t)
\bigg\{\tau_{\theta_j^t}(b_j^{t-1},a_j^{t-1},o_j^t,b_j^t)I(\widehat{\theta}_j^{t-1},\widehat{\theta}_j^t)T_i(s^{t-1},a^{t-1},s^t)\bigg\}\bigg]\bigg\}\\
&\times\alpha^{n-1}_{l(b_i^{t-1},a_i^{t-1},o_i^t)}(is^t)
\end{array}$$
and, if $m_j^{t-1}$ is subintentional then $\alpha^n = \ddot{\alpha}^n$:
$$\begin{array}{ll}          \ddot{\alpha}^n(is^{t-1})         &=
ER_i(is^{t-1},a_i^{t-1})                  +                 \gamma
\sum_{o_i^t}\sum_{is^t:m_j^t \in SM_j}\bigg\{\sum_{a_j^{t-1}}Pr(a_j^{t-1}|\theta_j^{t-1})\bigg[O_i(is^t,
a^{t-1},o_i^t)\\    &\times    \sum_{o_j^t}O_j^t(is_j^t,a^{t-1},o_j^t)
\bigg\{\delta_K(\mbox{APPEND}(h_j^{t-1},o_j^t)-h_j^t)I(\widehat{m}_j^{t-1},\widehat{m}_j^t)T_i(s^{t-1},a^{t-1},s^t)\bigg\}\bigg]\bigg\}\\
&\times\alpha^{n-1}_{l(b_i^{t-1},a_i^{t-1},o_i^t)}(is^t)
\end{array}$$


Eq.~\ref{eqn:horizonn}   is   an {\bf   inner   product}  and   using
Lemma~\ref{lem:bilinearity}, the value function is linear in $b_i^{t-1}$. Furthermore,
maximizing  over a  set  of linear  vectors  (hyperplanes) produces  a
piecewise linear and convex value function.
\end{proof}
%---------------------------------------------------------------------
\begin{small}
\bibliographystyle{theapa}
\bibliography{../refs}
%\bibliography{PRASH}
\end{small}


\end{document}
