Interactive partially observable Markov decision processes (I-POMDPs) provide a principled framework for planning and acting in a partially observable, stochastic and multiagent environment, extending POMDPs to multi-agent settings by including models of other agents in the state space and forming a hierarchical belief structure. In order to predict other agents' actions using I-POMDP, we propose an approach that effectively uses Bayesian inference and sequential Monte Carlo (SMC) sampling to learn others' intentional models which ascribe them beliefs, preferences and rationality in action selection. For problems of various complexities, empirical results show that our algorithm accurately learns models of other agents and has superior performance in comparison with other methods. Our approach serves as a generalized reinforcement learning algorithm that learns over other agents' transition, observation and reward functions. It also effectively mitigates the belief space complexity due to the nested belief hierarchy.
Partially observable Markov decision processes (POMDPs)
Interactive POMDP (I-POMDP)
However, the interactive belief modification for
IPOMDPs results in a drastic increase of the belief space
complexity, adding to the curse of dimensionality: the
complexity of the belief representation is proportional to
belief dimensions due to exponential growth of agent
models with increase of nesting level. Since exact solutions
to POMDPs are proven to be PSPACE-complete for
finite horizon and undecidable for infinite time horizon
(Papadimitriou and Tsitsiklis 1987), the time complexity of the
more generalized I-POMDPs, which may contain multiple
POMDPs and I-POMDPs of other agents, is greater than
or equal to PSPACE-complete for finite horizon and
undecidable for infinite time horizon. Due to this severe space
complexity, currently no complete belief update has been
accomplished using the sophisticated intentional models over
entire interactive belief space. There are only partial
updates on other agents’ sole beliefs about the physical states
To address this issue, we propose a Bayesian approach
that utilizes customized sequential Monte Carlo sampling
algorithms
Our approach, for the first time, successfully learns others’ models over the entire intentional model space which contains their initial belief, transition, observation and reward functions, making it a generalized reinforcement learning method for multi-agent settings. Our algorithm accurately predicts others’ actions on various problem settings, therefore enables the modeling agent to make corresponding optimal action to maximize its own rewards. By approximating Bayesian inference using a customized sequential Monte Carlo sampling method, we significantly mitigate the belief space complexity of the I-POMDPs.
A Partially observable Markov decision process (POMDP)
P OM DPi = hS, Ai, ⌦ i, Ti, Oi, Rii (1) Where the meaning for each element in the 6-tuple is: • S is the set of states of the environment. • Ai is the set of agent i’s possible actions • ⌦ i is the set of agent i’s possible observations • Ri : S ⇥ Ai ! Ri is the reward function.
Given the definition above, an agent’s belief about the state can be represented as a probability distribution over S. The belief update can be simply done using the following formula, where ↵ is the normalizing constant: b (s0) = ↵O (o, s, a) X T (s0, a, s)b(s) (2) s2 S Given the agent’s belief, then the optimal action, a⇤ , is simply part of the set of optimal actions, OP T (bi), for the belief state defined as: 1https://github.com/solohan22/IPOMDP.git
OP T (bi) =arg max n X bi(s)R(s, ai) ai2 Ai +
X
The Markov Chain Monte Carlo (MCMC) method
In order to make MCMC work on sequential inference
task, especially sequential decision makings under Markov
assumptions, sequential versions of Monte Carlo methods
have been proposed and some of them are capable of
dealing with high dimensionality and/or complexity problems,
such as particle filters
An interactive POMDP of agent i, I-POMDP i, is defined as:
I-P OM DPi = hISi,l, A, ⌦ i, Ti, Oi, Rii (4) where ISi,l is the set of interactive states of the environment, defined as ISi,l = S ⇥ Mi,l 1, l 1, where S is the set of states and Mi,l 1 is the set of possible models of agent j, and l is the strategy level. A specific class of models are the (l 1)th level intentional models, ⇥ j,l 1, of agent j: ✓ j,l 1 = hbj,l 1, A, ⌦ j , Tj , Oj , Rj , OCj i, bj,l 1 is agent j’s belief nested to level (l 1), bj,l 1 2 ( ISj,l 1), and OCj is j’s optimality criterion. The intentional model ✓ j,l 1, sometimes is referred to as type, can be rewritten as ✓ j,l 1 = hbj,l 1, ✓ ˆj i, where ✓ ˆj includes all elements of the intentional model other than the belief and is called the agent j’s frame.
The ISi,l could be defined in an inductive manner (note that when ✓ ˆj is usually known, ✓ ˆj reduces to bj ): ISi,0 = S, ISi,1 = S ⇥ ✓ j,0, ......
✓ j,0 = {hbj,0, ✓ ˆj i : bj,0 2 ( S)} ✓ j,1 = {hbj,1, ✓ ˆj i : bj,1 2 ( ISj,1)} (5) ISi,l = S ⇥ ✓ j,l 1, ✓ j,l = {hbj,l, ✓ ˆj i : bj,l 2 ( ISj,l)}
And all other remaining components in an I-POMDP are similar to those in a POMDP: • ⌦ i is the set of agent i’s possible observations. • A = Ai ⇥
Unlike plain belief update in POMDP, the interactive belief update in I-POMDP takes two additional sophistications into account. Firstly, the probabilities of other’s actions given its models (the second summation) need to be computed since the state of physical environment now depends on both agents’ actions. Secondly, the agent needs to update its beliefs based on the anticipation of what observations the other agent might get and how it updates (the third summation).
Then the optimal action, a⇤ , for the case of infinite horizon criterion with discounting, is part of the set of optimal actions, OP T (✓ i), for the belief state defined as: OP T (✓ i) = arg max ai2 Ai n X bis(s)ERi(is, ai)
is2 IS
The Interactive Particle Filter (I-PF)
The intuition of our algorithm is to assign appropriate prior distributions over agent j’s all possible models ✓ j =< bj (s), Aj , ⌦ j , Tj , Oj , Rj , OCj > and sample from each dimension of them. At each time step, we update all samples using perceived observations, namely computing and assigning weights to each sample, and resample them according to the weights. At last, since it is a randomized Monte Carlo method, to prevent the learning algorithm from converging (6) (7) o to incorrect models, we add another resampling step to sample from the neighboring similar models given the current samples. Consequently, our algorithm is able to maintain a probability distribution of the most possible models of other agents and eventually learn the optimal actions of them.
The interactive belief update described in Algorithm 1 is similar to I-PF in terms of the recursive Monte Carlo sampling and nesting hierarchy, but it has three major differences. Firstly, the belief update is over the entire intentional model space of other agents, therefore the initial set of N samples ˜btk,l1 =< b(nk),,lt 11, A k, ⌦
k, T (nk), O(nk), R(nk), OCj >, where k here denotes the modeling agent and k denotes all other modeled agents. We only assume that the actions A k, observations ⌦ k and optimal criteria OCj are known, as in a multi-agent game the rules are usually known to all agents or could be obtained through intelligence. Secondly, it is intuitive to see that the observation function O(nk)(ot k|s(n),t, atk 1, at k1) in line 13 is now randomized as well, as each of them is a particular observation function of that agent. Lastly, we add another resampling step in line 18 in order to avoid divergence, by resampling each dimension of the model samples from a Gaussian distribution with the mean of current sample value. Intuitively, similar models are resampled from a relatively tight neighboring region of the current model samples to maintain the learning accuracy.
Algorithm 1 can be viewed as two major steps. The
importance sampling step (line 1 to line 16) samples from belief
priors ˜btk,l1 and propagates forward using related proposal
distributions and computes the weights of all samples. And
the selection or resapmling step (line 17 to line 18)
resamples according to weights and similar models. Specifically,
the algorithm starts from a set of initial priors is(kn),t 1, for
each of them, it samples other agents’ optimal action at k1
from its policy P (A k|✓ (n),t 1), which is solved using a
k
very efficient POMDP solver called Perseus2
Algorithm 2: Level-0 Belief Update bk,0 =Level0BeliefUpdate(btk,01,atk 1,otk, Tk(n),Ok(n)) t 1 P (at k1) = 1/at k1 2 for st 2 S: 3 for st 1: 4 for a(tk 1) 2 A k: 5 P (n)(st|st 1, atk 1) = 6
O(n)(otk|st, at 1, at k1)P (at k1)
k k btk,0 = sum(n) ⇥ P (n)(otk|st, atk 1) normalize and return btk,0
The 0-level belief update, described in Algorithm 2, is similar to POMDP belief update but treats other agents’ actions as noise and randomized the state transition function and observation function as input parameters. It assume other agents in the environment choose their actions according to a uniform distribution (line 1), therefore is essentially a no-information model. For each possible action a(tk 1), it computes the actual state transition (line 5) and actual observation function (line 8) by marginalizing over others’ actions, and returns the normalized belief btk,0. Notice that the 2http://www.st.ewi.tudelft.nl/˜mtjspaan/ pomdp/index_en.html transition function T (n)(st|st 1, atk 1, at k1) and observak tion function O(n)(otk|st, at 1, at k1) are now both samples k k from input arguments, depending on model parameters of the actual agent on the 0th level.
In figure 1, we illustrate the interactive belief update using the problem discussed in the following section . Suppose there are two agents i and j in the environment, the sample size is 8 and the nesting level is 2, the subscripts in figure 1 denotes the corresponding agents and each dot represents a particular belief sample. The propagate step corresponds to line 2 to 12 in Algorithm 1, the weight step corresponds to line 13 to 16, the resample step corresponds to line 17 and 18. The belief update for a particular level-0 model sample (✓ j = hbj (s) = 0.5, pT 1 = 0.67, pT 2 = 0.5, pO1 = 0.85, pO2 = 0.5, pR1 = 1, pR2 = 100, pR3 = 10i) is solved using Algorithm 2, and the optimal action is computed by calling the Perseus POMDP solver.
We present the results using the multi-agent tiger game
Let’s see a specific game example with known parameters: there are a tiger and a pile of gold behind two doors respectively, two players can both listen for a growl of the tiger and a creak caused by the other player, or open doors which resets the tiger’s location with equal probability. Their observation toward the tiger and the other player are both relatively high (0.85 and 0.9 respectively). No matter triggered by which player, the reward for listening action is -1, opening the tiger door is -100 and opening the gold door is 10.
For the sake of brevity, we restrict the experiments to a two-agent setting and nesting level of one, but the sampling algorithm is extensible to any number of agents and nesting levels in a straightforward manner. Recall that an interactive POMDP of agent i is defined as a six tuple I-P OM DPi = hISi,l, A, ⌦ i, Ti, Oi, Rii. Thus for the specific setting of multi-agent tiger problem: • ISi,1 = S ⇥ ✓ j,0, where S = {tiger on the left (TL), tiger on the right (TR)} and ✓ j,0 =< bj (s), Aj , ⌦ j , Tj , Oj , Rj , OCj >}. • A = Ai ⇥ Aj is a combination of both agents’ possible actions: listen (L), open left door (OL) and open right door(OR). • ⌦ i is all the combinations of each agent’s possible observations: growl from left (GL) or right (GR), combined with creak from left (CL), right (CR) or silence (S). • Ti = Tj : S ⇥ Ai ⇥ Aj ⇥ S ! [0, 1] is a joint state transition probability that involves both actions. • Oi : S ⇥ Ai ⇥ Aj ⇥ ⌦ i ! [0, 1] becomes a joint observation probability that involves both actions. Oj is symmetric of Oi with respect to the joint actions. • Ri : IS ⇥ Ai ⇥ Aj ! Ri: agent i gets corresponding rewards when he listens, opens the wrong door and opens the correct door respectively. They are independent of j’s actions.
For the experiments of multi-agent tiger game, we want to learn over all possible intentional models of the other agent j: ✓ j =< bj (s), Aj , ⌦ j , Tj , Oj , Rj , OCj >. We only make reasonable assumptions that Aj and ⌦ j are known, OCj is infinite horizon with discounting. Now what we really want to learn are as follow: • bj0: the initial belief of agent j about the physical state. • Tj : the transition function of agent j, which can be parametrized by two parameters pT 1 and pT 2, as shown in Table 1. • Oj : the observation function of agent j, which can be parametrized by two parameters pO1 and pO2, as shown in Table 2. • Tj : the reward function of agent j, which can be parametrized by three parameters pR1, pR2 and pR3, as shown in Table 3. pR1 ⇥ pR2 ⇥ pR3, where bj 2 [0, 1] ⇢ pT 2 2 [0, 1] ⇢ R, pO1 2 [0, 1] ⇢ pR1 2 [1 , +1 ] ⇢ R, pR2 2 [1 [1 , +1 ] ⇢ R.
We mainly reduce this huge space by two means: utilizing Monte Carlo sampling methods and giving them problemspecific priors so that they are not over informative but provide enough information for the algorithm to learn from.
For the actual experiments, we fix the number of samples to be 2000 and run it on a two agent tiger game simulation as described above. We run experiments for learning three difference models of agent j: 1. ✓ j1 =< 0.5, 0.67, 0.5, 0.85, 0.5, 1, 100, 10 > 2. ✓ j2 =< 0.5, 1.00, 0.5, 0.95, 0.5, 1, 10, 10 > 3. ✓ j3 =< 0.5, 0.66, 0.5, 0.85, 0.5, 10, 100, 10 >
These models are all very special cases and carefully chosen in order to verify the correctness and evaluate the performance of our algorithm. For instance, the first model is a sophisticated one when the other agent is actually modeling his opponent using a subintentional model, while the second is a classic single-agent POMDP and the third is a very simple one but contains a large model space. We want to investigate if our framework is able to correctly and efficiently learn these models through these experiments.
The aim of first experiment to try to learn relatively complicated models of agent j with ✓ j =< 0.5, 0.67, 0.5, 0.85, 0.5, 1, 100, 10 >, who assumes others’ actions are drawn from a uniform distribution. Equivalently, agent j’s actual policy, as shown in figure 2, is to look for three consecutive growls from same direction and then open the corresponding door. For this particular experiment, we simulated the observation history for agent i, for the sake of firstly verifying the correctness of our algorithm, excluding the impacts of uncertainties from hearing accuracy. The simulated observation history is as follows: {GL,S GL,S GL,S GL,CR GL,S GL,S GL,S GR,CR GL,S GL,S GL,S GR,CR GL,S GL,S GL,S GR,CR GR,S GR,S GR,S GR,CL GR,S GR,S GR,S GR,CL GR,S GR,S GR,S GR,CL GR,S GR,S GR,S GR,CL GR,S GR,S GR,S GR,CL GR,S GR,S GR,S GL,CL GL,S GL,S GL,S GR,CR GL,S GL,S GL,S GR,CR GR,S GR,S}
The priors we assign to each parameters are shown in figure 3, specifically, they are uniform U(0,1) for bj0, Beta(5,3) with mode 0.67 for pT 1, Beta(5,5) for pT 2, Beta(3.5,1.4) with mode 0.85 for pO1, Beta(5,5) for pO2, Gaussian N(1,2) for pR1, N(-100,4) for pR2, and N(10,2) for pR3.
After 50 time steps, the algorithm converge to a posterior distribution over agent j’s intentional models, the results are also given in figure 3. Since the parameter space of agent j’s models is 8-dimensional, here we only show the marginal distributions of each parameter space in histograms. We can easily see that the majority of samples are centered around the true parameter values.
We use principal component analysis (PCA)
We tested the performance of our algorithms in terms of prediction accuracy towards others’ actions. We compared the results with other modeling approaches, such as a frequency-based approach, in which agent j is assumed to choose his action according to a fixed but unknown distribution, and a no-information model which treats j’s actions purely as uniform noise. The results shown in figure 5 are averaged plots of 10 random runs, each of which has 50 time steps. It shows clearly that the intentional I-POMDP approach has significantly lower error rates as agent i perceives more observations. The subintenional model assume j’s action is draw from a uniform distribution, therefore has a fixed high error rate. The frequency based approach has certain learning ability but is far from enough sophisticated for modeling a fully rational agent.
In the second experiment, we run our algorithm on actual observations for 30 time steps until it converges, and try to learn models of a simpler classic POMDP with high listening accuracy of 0.95 and small penalty of -10, e.g. the agent j alternately opens door and listens as shown in Figure 6 left. The actual model of j is ✓ j = h 0.5, 1, 0.5, 0.95, 0.5, -1, -10, 10 i, the priors assigned to b0, pT 1, pT 2, j pO1, pO2, pR2, pR3 are U(0,1), Beta(2,0.5), Beta(10,10), Beta(19,1), Beta(10,10), N(-1,1), N(-10,2), N(10,2), and the actual observation history is {GR,S GL,CR GL,S GL,CL GL,S GL,CR GL,S GL,CL GL,S GR,S GR,CL GR,CL GL,S GR,S GR,S GL,CL GR,S GL,CR GR,S GR,CR GR,CR GR,CL GL,S GL,S GL,S GL,CR GL,S GL,CL GR,S GR,S}.
Similarly, we report the learned posterior distributions over model parameters in figure 7. We observe an interesting pattern that while some parameters, such as bj,0, pT 2 and pO2 are concentrated around the actual values, others like pT 1 and pO1 become more dispersed than initial priors. The intuition behind is that the penalty and reward are -10 and 10, so one listening of reward -1 is enough for making decision of opening doors. That is to say, as long as tiger likely remains behind the same door when agent listens (the meaning of pT 1) and has a reliable hearing accuracy (the meaning of pO1), there are many models which satisfy this particular observation sequence, hence our algorithm learns them all.
For conciseness, we show the average prediction error rates for both second and third experiments in figure 9. Both results are averaged among 10 random runs, each of which has 30 time steps. In the second experiment in figure 9(a), the intentional I-POMDP approach still has significantly lower error rates than others.
In the last experiment, we wants to learn a model of ✓ j =
Figure 7: Learned posterior distributions for model ✓ j = h 0.5, 1, 0.5, 0.95, 0.5, -1, -10, 10 i. h0.5, 0.66, 0.5, 0.85, 0.5, 10, -100, 10i, who always listens since the listening penalty is now equal to the reward, as shown in figure 6(b). For brevity, we only show the marginal distributions over model parameters in figure 8. The priors assigned to bj0, pT 1, pT 2, pO1, pO2, pR2, pR3 are U(0,1), Beta(5,3), Beta(10,10), Beta(3.5,1.4), Beta(10,10), N(10,1), N(-100,2), N(10,2), and the actual observation history i learns from is {GL,S GL,S GR,S GL,S GL,CL GR,S GR,S GL,CL GR,S GL,S GL,S GR,S GL,S GL,S GL,S GL,CL GR,S GL,S GL,S GL,S}. We can see that all three reward parameters are correctly learned, while samples of pT 1, pT 2, pO1 and pO2 are not very concentrated to their true values but close to their corresponding priors, since intuitively they become less important and can be in a relatively loose region due to the increased pR1=10. Lastly, the performance comparison is given in figure 9(b).
We have described a new approach to learn other agents’ models by approximating the interactive belief update using Bayesian inference and Monte Carlo sampling methods. Our framework correctly learns others’ models over the entire intentional model space and therefore is a generalized reinforcement learning algorithm for multi-agent settings. It also effectively mitigates the belief space complexity and has a significant better performance than other approaches in terms of predicting others’ actions.
In the future, in order to fully evaluate the practicability on larger problem space, more multi-agent problems of various sizes could be tested. Due to computation complexity, experiments on higher nesting levels are currently limited. Thus, more efforts could be made on utilizing nonparametric Bayesian methods which inherently deal with nested belief structures.