Symbolic Opportunistic Policy Iteration for Factored-Action MDPs
This paper addresses the scalability of symbolic planning under uncertainty with factored states and actions. Our first contribution is a symbolic implementation of Modified Policy Iteration (MPI) for factored actions that views policy evaluation as policy-constrained value iteration (VI). Unfortunately, a naïve approach to enforce policy constraints can lead to large memory requirements, sometimes making symbolic MPI worse than VI. We address this through our second and main contribution, symbolic Opportunistic Policy Iteration (OPI), which is a novel convergent algorithm lying between VI and MPI, that applies policy constraints if it does not increase the size of the value function representation, and otherwise performs VI backups. We also give a memory bounded version of this algorithm allowing a space-time tradeoff. Empirical results show significantly improved scalability over state-of-the-art symbolic planners.
This paper presents a novel policy iteration algorithm 
      for symbolic MDPs with factored-action (in addition to factored-state) 
      dynamics. The algorithm, MB-OPI, yields a way to trade 
      representational complexity between value and policy iteration for the 
      class of MDPs defined over algebraic decision diagrams, just as MPI 
      gives a way to smoothly trade computational complexity. In doing so, 
      the authors generalize several existing algorithms which consider 
      factored actions and memory constraints independently. The 
      main technical challenge is that ADD policy iteration requires 
      multiplying an explicit policy representation into the current value 
      function, which can significantly increase its size. The solution is 
      to control this increase in size by defining a procedure to 
      conservatively combine policy and value diagrams using a pruning 
      procedure, rather than naively multiplying them. Results are 
      presented in terms of solution time, and show a ~2-6x improvement over 
      existing approaches. This paper is technically sound and well 
      written. The authors make a theoretical contribution to the literature 
      on symbolic MDP planning by introducing the concept of pruning as an 
      alternative to ADD products, and proving that this satisfies the 
      guarantees of MPI. Also couched as generalization to existing work in 
      symbolic dynamic programming, and appears to be state of the art for 
      planning with factored actions Empirical results support the idea 
      that pruning offers an MPI approach to SDP planning that avoids 
      representational bloat, and offers a several factor speed up 
      The paper is also generally well written and easy to follow. 
      If possible, I would suggest adding more background on SDP solving 
      using ADDs for representing value and DBNs, the basic policy iteration 
      approach using ADD product, and the difference between multiplying pi 
      into V vs. pruning V with pi. It would also be nice to have 
      (a) discussion of practical problems with many parallel actions for 
      which factoring actions is critical, and (b) a toy test case with 
      large parallel actions that highlights the best-case improvement over 
      SPUDD and FAR. Some notes on clarity that might be helpful: 
      053, "enforcement of policy constraint": 'constraint' hasn't been 
      defined yet, and only makes sense if you remember to view policy iteration 
      as policy-constrained value iteration 060, Figure 1: ordering of 
      state and action nodes would be more readable if they were interleaved or 
      stacked (something consistent) 060, Figure 1: as state variables 
      these are propositions, not predicates, so might be better to use 
      underscores (e.g. reboot_c1) 095, "marginalization operators": 
      examples include marginalization but also max. should reword for 
      correctness 110, equation 1: this was confusing without referring 
      back to SPUDD paper. I suggest adding 2 things: (a) explanation of how 
      expectation for factored models turns into a product of DBNs, and that 
      sums can be pushed in, and (b) simple explanation that "primed" literally 
      adds a prime to each state variable, and is necessary to make the ADD 
      operations well defined (saying "swaps the state variables X in the 
      diagram V with next state variables X′" can be confused with more 
      complicated mapping issues) 152, policy ADD: Would be helpful to 
      have a sentence like "Intuitively, this representation makes it possible 
      to express 1-step policy backup as the ADD product of a policy with a 
      value function". 179, Figure 4: caption uses C to denote policy, 
      but figures use \pi. other places too 206, "size of a Bellman 
      backup": usually think of backups in terms of computational complexity, so 
      should clarify that "size" refers to the data structure that results from 
      applying eq1. also would be helpful to intuitively explain what this looks 
      like, as opposed to pi (both have action variables, so why is pi generally 
      bigger??) 206, (due to…): for clarity, would help to clarify that 
      pi is bigger because it represents joint-actions, whereas backup only 
      represents value and (product of) factored actions 212, "only 
      those paths in D that": add "in D" to make clear that policy is being 
      applied to value function. otherwise can be confused with original 
      definition of policy 247, eq3: two extra close parens 252, 
      "sandwiched": intuitive, but perhaps too informal (though who am I to say 
      such a thing?) 278, "parameterized by k, …": missing comma 
      327, Figure 6: colors for OPI 2 and 5 are reversed in b... I 
      think.