Point Based Value Iteration with Optimal Belief Compression for Dec-POMDPs
We present four major results towards solving decentralized partially observable Markov decision problems (DecPOMDPs) culminating in an algorithm that outperforms all existing algorithms on all but one standard infinite-horizon benchmark problems. (1) We give an integer program that solves collaborative Bayesian games (CBGs). The program is notable because its linear relaxation is very often integral. (2) We show that a DecPOMDP with bounded belief can be converted to a POMDP (albeit with actions exponential in the number of beliefs). These actions correspond to strategies of a CBG. (3) We present a method to transform any DecPOMDP into a DecPOMDP with bounded beliefs (the number of beliefs is a free parameter) using optimal (not lossless) belief compression. (4) We show that the combination of these results opens the door for new classes of DecPOMDP algorithms based on previous POMDP algorithms. We choose one such algorithm, point-based valued iteration, and modify it to produce the first tractable value iteration method for DecPOMDPs that outperforms existing algorithms.
SUMMARY: This paper proposes a new method for 
      Dec-POMDP planning that is built out of several components. The first is a 
      new way of solving cooperative Bayesian games using an integer linear 
      program. The second is the transformation of the Dec-POMDP to a belief 
      POMDP in which a "centralized mediator" must select at each timestep the 
      best action for each agent-belief pair. The third is to automate the 
      discovery of optimal belief compression by dividing each timestep into two 
      parts, the first corresponding to the original Dec-POMDP and the second 
      giving each agent a chance to select how its beliefs in that timestep are 
      mapped to a bounded set and thus compressed. The fourth assembles these 
      components together into a point-based value iteration method that solves 
      the resulting belief POMDP using a varient of PERSEUS in which the CBG 
      solver is used to compute maximizations. ORIGINALITY: To 
      my knowledge, the integer linear programming formulation of the CBG is 
      novel, as is the optimal belief compression scheme. The latter in 
      particular is a very original and intriguing idea. The PBVI method is also 
      novel as far as I know, though it is only a minor variation on PERSEUS. 
      However, I have serious doubts about the originality of the belief POMDP 
      formulation presented in Section 4. In particular, it bears a striking 
      similarity to the continuous-state MDP approach recently proposed by 
      Dibangoye et al. [1]. Though those authors use an MDP formulation, this is 
      really just the belief MDP of a POMDP that, as far as I can tell, is 
      conceptually identical to the belief POMDP formulation used in this paper. 
      In Dibangoye et al., the actions correspond to assignments of decision 
      rules to each agent, such that the central planner has a Markov state 
      representation but each decision rule conditions only on individual 
      observations available to each agent. This is exactly the approach taken 
      here as well. Section 4 may also relate to recent work by Oliehoek [2], 
      though the exact nature of the relationship is less clear to me in that 
      case. The fact that this submission doesn't compare to or even cite these 
      highly related papers is a significant concern for me. CLARITY: 
      Overall this is a polished and well written work. I found some 
      aspects of the exposition unclear (see detailed comments below) but these 
      were not fatal. SIGNIFICANCE: Given the questions about 
      novelty of Section 4, the algorithmic contribution is moderate: somewhat 
      incremental but certainly nontrivial. In my opinion, the most interesting 
      and potentially significant aspect is the belief compression approach of 
      Section 5. However, I am also somewhat skeptical that this idea is 
      practical. Intuitively, it seems that there must be a trade-off: asking 
      the planner to determine how best to compress beliefs must increase 
      computational costs that might or might not outweigh the benefit of 
      compressing beliefs. Unfortunately, no analysis (or even mention) of this 
      trade-off appears in the paper. Furthermore, the empirical analysis does 
      not isolate the effect of this component of the algorithm. This is an 
      example of a more general problem limiting the paper's significance. 
      Because the experiments only assess the complete system, no insights are 
      gleaned into how each component contributes to performance. Does it work 
      because of or in spite of each component? Is the total performance gain 
      more than the sum of that of its parts? The paper would be greatly 
      improved if it addressed such questions. Detailed comments: 
      1: PERSUES -> PERSEUS 3: The explanation of the integer 
      linear program is unclear, which I believe is due to confusion between 
      state and joint observations. The variable x_a\theta is indexed by \theta 
      but then we are told there is one for each state. (2) contains no mention 
      of state but the text below it refers to feasible assignments of x_as. 
      Also, constraints 2 -> constraints (2). 4: I don't understand 
      why the assumption there is a bounded number of possible beliefs is 
      important. First of all, it seems to me that in any finite Dec-POMDP, 
      there is at any timestep only a finite number of reachable beliefs. The 
      fact that this number can increase over time would mean that the size of 
      the action space of the belief POMDP grows over time, but I don't see why 
      that's problematic for the formulation. I can understand bounding the 
      number of beliefs as a compression technique to yield efficient 
      approximations, but this bound is presented as a prerequisite for the 
      conversion to a belief POMDP which doesn't seem right to me. Also, the use 
      of the word "observation" is confusing in this section. How can there be a 
      one-to-one mapping between observations and beliefs? Do you mean 
      observation history? Similarly, we are told on line 173 that there are no 
      observations in the belief POMDP but then told in line 178 that actions in 
      this belief POMDP are mappings from observations to actions. Why is the 
      Lemma numbered 4.0.1? 5: Is t_i the same as |B|? 6: What 
      is a concave and locally linear value vector? Aren't these vectors 
      piecewise linear and convex? 7: To what horizon where these 
      problems tested? How many hours were used by the methods that obtained the 
      "Previous Best Utility"? If it's not the same as for your PBVI method, how 
      can the comparison be fair? Refs: Is [18] correct? It has the same 
      title and authors as [17]. [1] Optimally Solving Dec-POMDPs as 
      Continuous-State MDPs. Jilles S. Dibangoye, Christopher Amato, Olivier 
      Buffet and François Charpillet. In Proceedings of the Twenty-Third 
      International Joint Conference on Artificial Intelligence (IJCAI-13), 
      2013. [2] Frans A. Oliehoek. Sufficient Plan-Time Statistics for 
      Decentralized POMDPs. In Proceedings of the Twenty-Third International 
      Joint Conference on Artificial Intelligence, 2013.