What type of inference is planning?

Summary

This paper studies 3 types of factor graph inference for planning and in particular their relationship to optimal planning. The well known $\exp(\lambda R(x, a, x'))$ factor is used. MAP inference computes the maximum energy configuration over states and actions which corresponds to zero posterior entropy. Marginal inference computes the joint over states and actions. Marginal MAP inference set the action entropy in marginal inference to zero. An interesting connection was made with the dual LP formulation of MDP. The method was further applied to factored state MDP. The relationship between MDP stochasticity and inference approximation to optimal planning was studied in the experiments.

Strengths

**Originality & significance**: The paper is original and the three types of inference have not been studied in prior "planning as inference" literature to my knowledge. The connection between the variational formulation and the dual LP formulation is also interesting. In the discussion on stochastic dynamics, the notion of "reactivity" is also interesting and formalizes intuition from prior work to some extent. **Quality & clarity**: The paper is well written and the notation and exposition are clear.

Weaknesses

There isn't any salient weaknesses of the paper as far as I can tell. My impression is the results are somewhat "expected" given this type of "planning as inference" has been widely studied in prior work, at least empirically. One thing that would be of interest is how "reactivity" interacts with online re-planning.

Questions

I don't have any outstanding questions for the authors.

Rating

6

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

This paper does not contain a limitations section.

Summary

This paper investigates the concept of "planning as inference", which frames planning problems (i.e. coming up with actions to reach a goal or attain reward) using the vocabulary and mathematics of probabilistic inference. The paper surveys existing formalizations of this broad concept, finding that none of them exactly correspond to the standard planning notion of computing a policy that maximizes expected cumulative reward. In response, the authors introduce a new variational objective, $F_\text{planning}(q)$ the optimization of which is a generalization of the objective of maximizing expected cumulative reward using some (potentially reactive) policy $\pi$ (instead of just finding a single action sequence $\mathbf{a}$ that performs this maximization, as in MMAP). They also show that this objective differs from existing inference objectives (MAP, MMAP, and Marginal inference) in terms of the entropy terms associated with their variational formulations. The authors then derive several practical methods for optimizing $F_\text{planning}(q)$ based on linear programming (VI LP) or loopy belief propagation (VBP) to compute the optimal $q$ (which corresponds to the action policy $\pi$). In both synthetic experiments and benchmark IPC problems, they show that these methods are competitive with other planning-as-inference algorithms based on other inference formulations, and confirm that optimizing $F_\text{planning}(q)$ leads to (desirably) different properties than MAP or MMAP inference, e.g. in terms of policy reactivity.

Strengths

This was a detailed, interesting, and well-substantiated paper that addresses an important conceptual question for the field of planning-as-inference: What inference objective corresponds to the standard decision-theoretic notion of maximizing expected cumulative reward? To my knowledge, this question hasn't been adequately addressed, and this paper does a very thorough job of providing an answer --- one that I believe will be valuable for future practitioners in the field. Overall, the paper was well-presented for researchers already with an understanding of planning-as-inference, and the theoretical results were mostly well-explained (see later comments for how the exposition could be improved for a broader audience, as well as several theoretical claims that need to be better justified / clarified). I especially appreciated the explanations as to how the optimization of $F_\text{planning}(q)$ differs from other inference objectives (vis a vis policy reactivity), and the derivation (mostly in the Appendix) of how a variant of their objective can capture determinization in planning (which makes clear the variational gap this introduces). Regard soundness, the proofs that I checked (in Appendices A, B, ad E) appear to be correct, and the experiments provide sufficient validation for both the new objective and the approximate methods they use to optimize it. Even though these approximate methods mostly match existing methods for planning-as-inference like SOGBOFA-LC, the experiments show that in at least some cases (e.g. higher entropy cases or cases requiring reactivity), optimizing the right objective (i.e. $F_\text{planning}(q)$) leads to higher cumulative reward.

Weaknesses

In my opinion, the main way this paper could be improved is in exposition, especially for a broader audience than people already familiar with planning-as-inference, factor graphs, and variational inference. The introduction right now is very short, and then paper goes straight into mathematical background. IMO, some of the discussion in the Related Work should be moved into the Introduction itself, and I think the Related Work probably is best placed after the Introduction. I also think both the Abstract and the Introduction could foreground the intuitive / standard notion of planning as "maximizing expected cumulative reward", and communicate that their variational formulation of planning-as-inference both reproduces this objective and generalizes it, whereas other inference objectives do not. This, to me, is one of the main upshots of the paper, and it should be communicated clearly from to get-go as a motivation. Right now, the idea that maximizing $F_\text{planning}(q)$ generalizes "maximize expected cumulative reward" only starts appearing in Table 1, and Section 3.1. As an additional organizational suggestion, after introducing the Background, I think it is probably better to cover the content in Section 4 first, by introducing $F_\text{planning}(q)$ as a variational objective, then comparing it to the other existing inference objectives. After you have established that $F_\text{planning}(q)$ is the "right" objective for planning, then you can go into the content of Section 3.2 as a separate section that is focused on practical methods for optimizing the planning objective. By organizing things in this way, you first clearly motivate the desirability of $F_\text{planning}(q)$ as an objective, which then motivates practical methods for optimizing $F_\text{planning}(q)$. Aside from exposition, I think a number of theoretical claims that the paper makes could be better explained and clarified. In particular, it was not obvious to me that the ranking of inference types in Section 4.1 could be read off from the entropy terms in Table 1 -- there should be an associated proof in either the main paper or Appendix. There are also a few notational choices that I think need to be clearly defined before use, and several sentence discussing the relationship of $F_\text{planning}(q)$ to other inference objectives that could be clarified. I will detail these more in the Questions section. I think the experiments could be made even stronger by comparing against e.g. Monte Carlo methods for planning-as-inference (e.g. Piche et al. (2018)) and model-based planning algorithms for MDPs (standard value iteration, RTDP, etc.), but this is not strictly necessary.

Questions

Line 62: "For a general factor graph f(x, a)" -- please define what f(x, a) is. Even among probabilistic inference practitioners, the factor graph representation of a inference problem may not be widely known (compared to e.g. computing or sampling from a posterior distribution). Line 62: I think the bra-ket notation for expectations should probably be defined somewhere, since it is less commonly used than the expectation operator. And perhaps the paper should consistently use one notation or the other. Table 1: Could you provide derivations or explanations of the variational identities for Marginal, MMAP, and MAP somewhere (e.g. the Appendix), just as you've done for $F_\text{planning}(q)$? Right now it's not obvious to me why the conditional entropies end up differing in the way shown in column 2, and it seems like there should be some fairly straightforward intuition as to why, e.g. MMAP requires subtracting out $H_q(a_t)$, and why Marginal has $H_q(x_{t+1}, a_t | x_t)$ instead of $H_q(x_{t+1} | a_t, x_t)$ as the conditional entropy term. Table 1 and Eq 1: $R(\mathbf{x}, \mathbf{a})$ should be explicitly defined some where as the cumulative reward. Line 159: Some derivation of the computational complexity would be good (e.g. in the Appendix). Lines 180-181: "none of which corresponds with the exact “planning inference” from this work, which is exact." --- exact with respect to what? Exactly captures the notion of maximizing expected cumulative reward? Exact in the sense that $F_\text{planning}$ is not a lower bound of itself? I think this should be clarified. Line 182: "First, from inspection of the entropy terms it is trivial to see that.." --- to me this wasn't trivial for all the comparisons shown, and there should be some explanation and derivation. In particular, it was not obvious to me why the entropy term for Marginal$^\text{U}$ should be lower the entropy term for MAP, which is zero. Lines 185-186: "Since the tightness of a lower bound is an indication of its quality, it follows that MMAP inference is no worse and potentially better than all other common types of inference." --- I think it is confusing for this sentence to follow right after Equation (8), because it suggests that the "best" objective is $F_\text{marginal}$, even though the whole point of the paper is that $F_\text{marginal}$ does not capture our standard notion of planning. I think it should be clarified that the MMAP objective is a lower bound to the planning objective in particular, which is the true objective the paper cares about. You could do this with a sentence like "Except for $F_\text{marginal}$, which is not a planning objective in the sense of maximizing expected (exponential) utility, $F_\text{MMAP}$ is the best lower bound to $F_\text{planning}$".

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

4

Limitations

While there is no explicit limitations section, the authors adequately discuss the approximate nature of their proposed optimization methods, and also discuss cases where their proposed objective is equivalent (and hence does not improve on) existing planning-as-inference formulations (namely, cases without deterministic dynamics). There is some discussion of this already, but I think it would be good for the paper to better recognize when Marginal$^\text{U}$ might be desirable as an objective, as this corresponds to a notion of "soft planning" that is similar to Boltzmann-rational models of action selection and max-entropy inverse RL (Ziebart et al, 2010). Sometimes, our goal is not to derive a reward-optimal policy, but to get a policy that is stochastic (because we desire diversity, or because we want to model human planning). The paper is largely theoretical in nature, and discussions of societal impact are not immediately relevant.

Summary

This work introduces a variational inference (VI) framework to characterise different types of inference for planning, specifically for finite-horizon MDPs represented as probabilistic graphical models. They also develop an inference algorithm (VBP) that takes inspiration from the loopy belief propagation and adapts it to planning. An experimental evaluation seems to confirm the theoretical analysis.

Strengths

The idea is very interesting and original. They also performed an extensive experimental analysis.

Weaknesses

The paper has two major flaws. First, the text is poorly written, and it definitely doesn’t meet the standards of a high profile conference as NeurIPS. In particular, 1) The introduction and the first subsection of the backgrounds have zero references. 2) The paper is not self-contained. I understand the limit of space, but the background section doesn’t provide all the necessary background. Moreover, the experiment on “Reactivity avoidance” is interesting, but most of the explanation is in the appendix, making it hard to grasp with the sole information in the paper. 3) The notation is not always properly introduced, for example: - At the beginning of 2.2 I would explicitly write the equations for the different types of inference. Considering how central they are to the paper, and the fact that the work if theoretical, I would expect a more formal definition. - The risk parameter \lambda is introduced in section 3 without any context on what that means in terms of planning. It is not in the standard formulation of MDPs, nor introduced in your background section. - The “discussion” is not really a discussion, maybe we can call it a conclusion, but anyway it looks rushed and not very “conclusive” See detailed comments below for more examples. Second, the soundness of the contribution is undermined by missing details and not very convincing results. In particular: 4) Your definition of “planning inference”, that is central to the paper, is too fuzzy. On line 96 you state that your definition of “planning inference” corresponds to the entropy in Eq.4, however later on line 181, you state that your definition of inference is exact. This I think is a bit confusing. VI is by nature an approximation. I presume I understand what you want to say, nevertheless I think it should be clarified. 5) The discussion on the different types of inference lacks rigour. The notation is not always clear, and most importantly, it is not clear what is the impact of this finding on the planning community. What does it mean in practice that “planning inference” is different from all the others in stochastic settings? 6) The experiments, despite being extensive, don’t show a significant impact coming from the new “planning inference” introduced by the authors. See my questions to the authors for more details.

Questions

1) Why do you focus on finite-horizon MDPs? Do your result easily translate to infinite-horizon MDPs? 2) In the introduction (line 27) you mention value iteration, but then any connection with classic MDP algorithms (and Bellman update) is missing. Moreover, you focus on “best exponential utility”, why not the classic “maximum expected utility”? Can you elaborate on this? I think there is a sort-of hint on this in section 3.3 but it is not exactly clear to me. 3) In Figure 2 (right) the x-axis should be in [0,1] if you are plotting the normalized entropy, why is it not the case? 4) Connected to the previous question, how do you explain the fact that the different methods converge again when the stochasticity increases? From 4.2 you seem to suggest that the more stochastic the environment, the more your solution should be preferable. Am I missing something? 5) In Figure 3, it looks like SOGBOFA-LC performs slightly worse on game of life than sysadmin. Doesn’t it go against the intuition that MMAP should degrade when the stochasticity increases? 6) On line 276 you say that you notice a *significant* advantage of your proposal wrt to SOGBOFA-LC. I’m not sure if I agree with it. Only for the game of life there is clear improvement, but in that case a Rollout is performing better. Can you elaborate on this? Minor comments: - In the abstract, the sentence “...show that all commonly used types of inference correspond to different weightings of the entropy terms” is a bit misleading since these are already known results, as you point out in section 2.2. I recommend re-writing in order to not set the wrong expectations to the reader. - Some notation is not properly introduced: line 62 (angular brackets, I assume it’s a shorthand for the expected value that might be standard in VI but not in planning communities), line 82 (the limit), line 158 (n_a, n_s), etc. - Line 44, “small subset of x_t” is an assumption. In principle, x_t^(i) can depend on all x_t-1 - Line 64, I think the “-” before the log shouldn’t be there - Better avoid contractions and other “informal abbreviations” e.g. “let’s” (line 50) or “wrt” (line 176) - Line 289, “further the understanding”, I think you want to remove that “the” - a few more words on the “planning as learning” on line 210, and how that is different from your analysis could be interesting. - There is a lot of math (that I appreciate) but some intuitive explanation could very much improve the presentation of the results.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

Okay.

Summary

This paper shows that planning in an MDP can be posed as a specific form of inference in a graphical model; in this context of inference, different forms of inference can be applied, with different results. Additionally, alternate forms of inference such as variational techniques can be used, which allow better plans to be inferred than existing baselines. This is not a perfect paper, but overall it is a good idea, well executed and I recommend it for acceptance.

Strengths

- The primary strength of this paper is the technical contribution, which is how the paper places the planning problem in the context of inference in graphical models. The relationship between planning and inference is not novel, but the generalisation of this relationship to different forms of inference is novel. - The paper (mostly) shows how the policy for a standard, flat MDP can be found by solving for the variational posterior over states, and also shows how a variant of belief propagation can be used to find this posterior. - The paper generalises this result to factored MDPs, and shows how belief propagation is even more useful. - The paper evaluates the VBP technique against gradient descent baselines and exact solution techniques on both 5000 synthetic MDPs and also 6 domains from the internation planning competition. The paper shows that VBP is very close to the exact solution and outperforms the other baselines on the synthetic domains. On the IPC domains, the VBP seems to match the performance of the best baseline across all IPC domains (different baselines have different performance across different domains -- VBP seems to match the best one on each domain).

Weaknesses

The paper has two primary weaknesses: - There is no discussions of the weaknesses of the inference-based technique. It is not clear if the VBP is computationally more costly than, for instance, the gradient-based SOGBOFA techniques. Timing information would have been very helpful. It is also the case that while VBP consistently matches the best performing baseline, it does not seem to outperform any of the baselines. It would have been helpful to know why VBP isn't able to match the exact planning technique -- where is the loss in performance coming from? - Some of the writing is less than clear. For instance, the exponential utility is introduced in table 1, and is justified on page 3 with a short reference to being "more suitable for a factor graph representation" but more explanation would have been helpful. Please note in the author response that the concern is not that the exponential utility is problematic, but the text needs to spend more time addressing and justifying this. Similarly, the introduction of the $\lambda$ risk setting is not the common case, and needs more justification. It's not clear that the $\lambda$ term adds much to the primary point of the paper, and seems to be set to 0 for most (if not all) of the experimental results. Furthermore, appendix F.3.7 indicates that $\lambda$ has no meaning if "if the reward can have arbitrary scaling". This is a crucial point that should be in the main body of the paper, and in fact the paper might be clearer without incorporating $\lambda$ at all since it does not add much to the explanation of planning as inference.

Questions

- Are there any computational constraints on the VBP? Is it comparable in speed to the gradient descent techniques? - Are there convergence issues? The paper briefly discusses this but more detail is needed. - Can the other forms of inference (e.g., $F^{marginal}$, etc.) map exactly to different forms of planning? The experimental results seem to suggest this, e.g., $F^{marginal}$ maps to ARollout, but it would be helpful to know this earlier in the paper.

Rating

8

Confidence

5

Soundness

4

Presentation

3

Contribution

4

Limitations

The authors did not include a discussion of limitations, and this is one of the weaknesses of the paper.

Summary

The paper proposes a framework to understand, as the title suggests, what type of inference is (probabilistic) planning. The authors make use of variational inference which encompasses marginal, MAP, and marginal MAP (MMAP) inference to theoretically compare the power of such types of inference in bounding the optimal expected reward for probabilistic planning. Furthermore, the authors propose an approximation of planning inference for factored MDPs as they search space is exponential in the input problem. Experiments are run to support the theoretical results and claims.

Strengths

1. The paper poses an interesting theoretical study from a statistical viewpoint on optimisation functions for planning. 2. The main story and results are well presented and easy to understand. 3. The experiments are diverse and well motivated, with results supporting the theoretical claims. 4. The paper provides a good coverage of related work.

Weaknesses

1. The main weakness of the paper is its clarity. The paper can be better self-contained if some of the other sections can be better motivated and/or explained by an additional sentence or two, rather than references to the appendix. Furthermore, some of the equations and technical details seem to be ambiguous and not well defined. See suggestions/comments below.

Questions

1. The introduction mentions that planning inference is the same as `value iteration', but nowhere else in the paper is value iteration nor Bellman backups explicitly mentioned. Is this a typo with variational inference (both have the same acronym), or is this intended? If this is intended, please expand on this relationship. The closest looking result is in Sec. 3.3. 2. Can you explain more what is the meaning and/or impact of the result that $F^{\text{planning}}_{\lambda} \leq F^{\text{marginal}}_{\lambda}$? e.g. Is the marginal inference an overapproximation? 3. What are the terms in the denominator of $H_{\text{MDP}}$ and how is it computed for the IPPC domains? Suggestions/comments - It would be helpful for the reader to provide definitions of some notation in the variational inference section. More specifically it would be helpful to define what is a factor graph and the function $\langle \cdot \rangle_{q}$ in the `energy term'. - It could be worth mentioning what is the type of $\mathbf{a}$ and $\mathbf{x}$ in Eqn. 1. I assume now that it is a list of $a$s and $x$s of size $T$ - line 114: never access to the full joint -> never access the full joint - The motivation and explaination for the Bethe approximation can be brought earlier rather than referring to the appendix. - The term $H_{\text{Bethe}}$ is not used in the equation under line 118. I only see $H_{\text{Bethe}}^{\text{planning}}$ and $H_{\text{Bethe}}^{\text{marginal}}$ - Sec 3.3. forward updates: the sum should not range over $a_t$ if it is defined as the argmax of $Q(x_t, a_t')$. Furthermore, either bring the equality out of the equations, or remove the $a_t=$s in the forward updates and posterior equations. - The meaning of $H_{\text{MDP}}$ as normalised entropies can be explained with an additional sentence rather than referring to the appendix. Furthermore, even when looking at the appendix, none of the $N_e, N_a, N_s$ terms seem to be defined anywhere in the paper. Also is this a new metric or something that exists? There does not seem to be a reference associated with it.

Rating

6

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors correctly fill in the checklist and justify their answers.

Thank you for the response.

Thank you for the response, and for the explanation of the sequential bounding in particular, which clarified my confusions. Do include these derivations in the Appendix. Regarding derivations of the variational expressions, I think it's up to the authors to include the full derivations in the Appendix, but I do think readers will probably find it helpful if some explanation or intuition is provided. For Marginal$^U$ inference, for example, I can see that the $H(q)$ term is really just some kind of KL-divergence between $q(x, a)$ and the (uniform) prior over trajectories or actions. For MAP, I can also see the intuition for why $H(q)$ is zero, because in MAP inference you are just interested in finding a point estimate, and so $q$ should have zero uncertainty (and hence zero entropy). For MMAP, it was helpful for me to realize the entropy term is just equal to $H_q(x_{1:t}, a_{1:t}) - H_q(a_{1:t}) = H_q(x_{1:t} | a_{1:t})$, which intuitively makes sense because in MMAP, you only want to marginalize over $x_{1:t}$ for a fixed value of $a_{1:t}$, and hence only care about the randomness in $x_{1:t}$ conditional on $a_{1:t}$. I think these sorts of intuitive explanations would be helpful to include somewhere. I'll be keeping my score of 7. I encourage the authors to restructure the exposition of their paper in some of the ways I suggested, so that the paper will be more accessible to others and have a greater impact.