What type of inference is planning?

Thank you for your time in reviewing this paper. We would like to address one of your comments:

One thing that would be of interest is how "reactivity" interacts with online re-planning.

We do a worked out example in Appendix F.2, in which we show how for some MDPs online replanning is not as good as using a reactive policy when planning. In essence, an agent not only benefits from the ability to replan, but also from knowing ahead of time that it will have the ability to replan.

I thank the authors for the response. The worked example is very helpful.

Thank you for your careful review this paper, and for your insightful comments and suggested improvements, which we will incorporate.

Please define what f(x, a) is

We tacitly take f(x, a) to correspond to the factor graph of Fig. 1 [left], but this is not explicitly mentioned in the text. We will define fully.

Define the bracket notation or convert everything to expectations for consistency

We will convert everything to expectation notation.

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)$?

All the other variational expressions have been provided somewhere in existing literature, so we didn't rederive them in this work. But we can indeed include them in an appendix if the reviewer feels that it would improve clarity.

Marginal inference: This is the standard VI problem, see e.g., (Jordan et al., 1999).

MMAP inference: This result is derived in (Liu and Ihler, 2013).

MAP inference: Taking the variational problem of marginal inference and setting the entropy to zero (sometimes by multiplying it with a temperature that goes to 0) results in an LP problem that corresponds exactly to maximum a posteriori inference (Weiss et al., 2012). Further relaxing the marginal polytope into a local polytope gives rise to most well-known methods for approximate MAP inference, such as dual decomposition. See e.g., (Sontag et al., 2011).

$R({\pmb x}, {\pmb a})$ should be explicitly defined some where as the cumulative reward

Oftentimes (and indeed in our experiments), rewards do not depend on the action and the above expression can be simplified to $R({\pmb x})$. This is already defined in line 48. We will define the more general case $R({\pmb x}, {\pmb a})$.

Some derivation of the computational complexity would be good (e.g. in the Appendix).

The computational complexity is mentioned in line 159, we will add a derivation to the appendix in the final version.

"none of which corresponds with the exact “planning inference” from this work, which is exact." --- exact with respect to what?

The quantity of interest of "planning inference" is the expected utility of an optimal planner. When running "planning inference" in a standard MDP, the result is exactly the best expected utility. This is exact with respect to, for instance, value iteration.

This means that, in a standard MDP, an agent that follows the best action as prescribed by "planning as inference" is an optimally-acting agent that will attain maximum reward, regardless of the MDP. However, given an agent that follows the optimal action according to any other type of inference (even if such inference is exact), can be fooled by a specially crafted MDP, and in general will not perform as well as the "planning inference" agent. We give a worked out example of this in appendix F.2, in which an MMAP agent is led astray by an MDP that is crafted to need high reactivity. Also, Figure 1[right] illustrates this point, where all inference types have a negative advantage, and $F^\text{planning}$ has exactly 0 advantage.

First, from inspection of the entropy terms it is trivial to see that.." --- to me this wasn't trivial for all the comparisons shown (...) In particular, for Marginal$^\text{U}$

Yes, an appendix with a proof of all the sequential bounding will be helpful, we will add it in the final version.

In particular, marginal inference can be combined with different normalizing constants. Regardless of the normalizing constant, its behavior is the same and the resulting planner will take the same actions and achieve the same reward. But in terms of bounding, different normalizing constants will have different effects.

Your comment made us realize that a more in-depth analysis of the possible normalizing constants and their effect on bounding should be included in the paper. We will do that in the final version.

For upper bounding, the marginal entropy term

$H^\text{Marginal}({\pmb q}) = H_{\pmb q}(x_1) + \sum_{t=1}^{T-1} H_{\pmb q}(x_{t+1}, a_t| x_t)$

clearly upper bounds the "planning inference entropy term"

$H^\text{Planning}({\pmb q}) = H_{\pmb q}(x_1) + \sum_{t=1}^{T-1} H_{\pmb q}(x_{t+1}|x_t, a_t)$

since $H_{\pmb q}(x_{t+1}, a_t| x_t) = H_{\pmb q}(x_{t+1}| a_t, x_t)+ H_{\pmb q}(a_t| x_t)$ and entropies are non-negative.

For lower-bounding, we can use a uniform weighting over trajectories and use the entropy term $H^{\text{Marginal1}^\text{U}}({\pmb q}) = H_{\pmb q}(x_1) + \sum_{t=1}^{T-1} H_{\pmb q}(x_{t+1}, a_t| x_t) - (T-1)\log N_aN_s^{N_e} - \log N_s$

It is clear that $H_{\pmb q}(x_1) \leq \log N_s$ and $H_{\pmb q}(x_{t+1}, a_t| x_t) \leq \log N_aN_s^{N_e}$, with equality being achieved when $\pmb q$ is a uniform distribution. Therefore, $H^{\text{Marginal1}^\text{U}}({\pmb q})$ is always non-positive, as required to lower bound $H^\text{MAP}({\pmb q})$.

If instead, we use a uniform weighting over actions, as suggested in our paper we have $H^{\text{Marginal2}^\text{U}}({\pmb q}) = H_{\pmb q}(x_1) + \sum_{t=1}^{T-1} H_{\pmb q}(x_{t+1}, a_t| x_t) - (T-1)\log N_a$

Since $H_{\pmb q}(a_t)\leq \log N_a$, it follows that $H^{\text{Marginal}^\text{U}}({\pmb q}) \leq H^\text{MMAP}({\pmb q})$

where

$H^\text{MMAP}({\pmb q}) = H_{\pmb q}(x_1) + \sum_{t=1}^{T-1} H_{\pmb q}(x_{t+1}, a_t| x_t)-H_{\pmb q}(a_t)$

If we further assume deterministic dynamics, then $H_{\pmb q}(x_1) = 0$ and $H_{\pmb q}(x_{t+1}, a_t| x_t)\leq \log N_a$, thus making $H^{\text{Marginal2}^\text{U}}({\pmb q})$ non-positive, as required to lower bound $H^\text{MAP}({\pmb q})$.

I think it should be clarified that the MMAP objective is a lower bound to the planning objective (...) with a sentence like (...)

Your phrasing is clearer, we will adapt it and adopt it.

The introduction and the first subsection of the backgrounds have zero references.

This work is related to a vast amount of literature from classical planning, reinforcement learning, variational inference, influence diagrams, etc. While it is impossible to cite all the related work, we have included a selection in our Section 5, "Related work", trying to at least touch all relevant subfields. We already have on our radar some additional citations that we want to include in the final version and are happy to hear suggestions for any glaring missing citations.

The reason why all citations from the introduction have been moved Section 5 is that we wanted to be able to connect each citation with a type of inference, and potentially discuss other details about it in relation with our VI framework, and this was only possible after developing the theory sections of this paper.

We will add MDP references to Section 2.1.

The paper is not self-contained. I understand the limit of space, but the background section doesn’t provide all the necessary background.

As mentioned before, this work connects multiple fields, so detailed background about all of them cannot be included. Some degree of familiarity with factor graphs, variational inference, loopy BP, and reinforcement learning does indeed help with the reading. We have included the minimal background required to be able to derive our results from either first principles or cited sources. While we are unlikely to be able to fit much more information in the background section, we would like to know if the reviewer has a particular result in mind that could be cited or included to make this work more self-contained.

The notation is not always properly introduced, for example:

(a) Explicitly write the equations for the different types of inference (...) I would expect a more formal definition

The explicit expression for each type of inference appears in the second column of Table 1. This is a precise definition of each type of inference on the factor graph of Figure 1[Left].

(b) 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.

Section 3 has three references (Marthe et al., 2023; Föllmer and Schied, 2011; Shen et al., 2014) that explain the role of $\lambda$ in planning. It controls how risk-seeking the agent is. Although this is not standard in MDPs or RL, it is not a concept that we introduce in this paper, but rather, a concept that has already been developed for planning in MDPs and that we leverage to include both the dynamics and the rewards within the same factor graph, since all the terms become multiplicative in this formulation. This is a generalization of the standard utility in MDPs, so we do not lose generality.

(c) Your definition of “planning inference”, that is central to the paper, is too fuzzy

Theorem 1 defines the "planning inference" objective, which is Eq. (2), whose terms are further defined in Eqs. (3) and (4). Approximations are introduced in Section 3.2 to make this objective tractable for factored MDPs.

You state that your definition of inference is exact. This I think is a bit confusing. VI is by nature an approximation.

To clarify: VI is exact when the variational distribution is arbitrarily flexible and is optimized completely. In other words, the evidence lower bound (ELBO) matches the exact evidence if (a) the variational distribution can fit the posterior arbitrarily well and (b) the optimization finds the maximum of the ELBO. VI is thought of as approximate because typically none of these two conditions are met. In the case of a standard tractable MDP, both conditions are met for "planning inference", and it produces the exact result. This makes sense, since other techniques (such as value iteration) also allow for exact planning. In the case of an intractable factored MDP, we need to introduce approximations, and the proposed VBP no longer corresponds to exact planning.

Thank you for your time reading this paper, we hope that you will find the following clarifications useful in its judgement.

Why do you focus on finite-horizon MDPs? Do your result easily translate to infinite-horizon MDPs?

When thinking of planning as inference in a factor graph, it is simpler to consider a finite factor graph that has been unrolled for a finite number of steps $T$. Classical references such as (Levine, 2018) do the same.

Practically speaking, when solving an intractable MDP (such as a factored MDP with an exponentially large state space at each time step), rewards beyond a certain horizon rarely affect the agent. As an example, competitors in the IPPC were given a finite MDP of horizon 40, but they often designed agents that considered and even shorter horizon. Even if an MDP is infinite-horizon, an approximate finite-horizon agent will probably have similar performance to an approximate infinite-horizon agent, since the approximations have a stronger effect than considering the horizon finite vs. infinite.

Theoretically speaking, it is possible to extend our work to deal with infinite horizon MDPs by using the regular structure of the graph. In an infinite MDP, the forward and backward messages at all timesteps should be identical (discounting edge effects), so this becomes a highly symmetric inference problem. Lifted BP was designed for efficient inferences in highly symmetric models. The recipe that we followed to extend standard loopy BP to planning should apply to extend lifted BP to planning.

In the introduction (line 27) you mention value iteration, but then any connection with classic MDP algorithms (and Bellman update) is missing

The connection is mentioned in Section 3.3, where the backward updates correspond exactly with Bellman updates. Note that the definition of $Q(x_t,a_t)$ (in line 163) happens to coincide exactly with the Q table in reinforcement learning. This, together with the backward updates corresponds to value iteration.

You focus on “best exponential utility”, why not the classic “maximum expected utility”

The best exponential utility is identical to the“maximum expected utility” in the limit $\lambda \rightarrow 0$. Therefore, this is a strict generalization for all $\lambda$. Section 3 has three references (Marthe et al., 2023; Föllmer and Schied, 2011; Shen et al., 2014) that explain the role of $\lambda$ in planning. Essentially, it is a parameter controlling how risk-seeking an agent is. Using a generic $\lambda$ allows us to formulate the utility in Eq. (1) in which the exponentiated reward and the dynamics interact multiplicatively. This is critical to express them as a factor graph, since in factor graphs all factors interact multiplicatively.

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?

Good catch, we had normalized the entropy in the x-axis for the [left] plot but not for the [right] one. We have corrected this. Nothing changes other than a different labeling in the x-axis, which now runs from 0 to 1.

how do you explain the fact that the different methods converge again when the stochasticity increases?

This is an expected result. When the dynamics are moderately stochastic, a single sequence of actions (as in MMAP) becomes more inadequate to solve the planning problem, and we need more reactivity to the environment to plan. Thus, as stochasticity grows, our proposed method becomes increasingly better than, e.g., MMAP. However, if the stochasticity grows too much, the agent starts to lose any ability to control the environment and this advantage is lost. Think of the extreme case: When dynamics are fully stochastic, the agent follows a random walk regardless of which action is taken. In that extreme regime, any planning method will have the same performance: that of a random walk.

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?

That would have been our expectation as well. However, the stochasticity of game of life and sysadmin are very similar (17% and 23%, respectively), so other differences can have a stronger effect. For instance, the structure of the MDP describing the game of life depends, on average, on more entities from the previous time slice, as compared with sysadmin. It might also require more reactivity for succesful control. These differences make the gap between VBP and SOGBOFA-LC wider than expected when judging purely from a stochasticity level perspective.

you say that you notice a significant advantage of your proposal wrt to SOGBOFA-LC. I’m not sure if I agree with it.

Yes, this requires more qualification. The advantage is significant in the statistical sense for most instances of game of life and sysadmin (note the lack of overlap of the uncertainty regions in most instances). For the other problems, which are mostly deterministic, it is hard to say whether VBP or MMAP is performing better across the board, as expected since they are very deterministic. ARollout on the other hand is a bit hit or miss, since it integrates over all actions rather than optimizing over them. It works well for game of life, but for the very deterministic elevators in which one can derive a clear plan of action, ARollout performs very poorly.

Thank you for your careful reading and positive impression, we will take your comments into account to improve the clarity of the final manuscript.

Are there any computational constraints on the VBP? Is it comparable in speed to the gradient descent techniques?

VBP computational and convergence behavior mirrors that of standard loopy belief propagation.

Per iteration, the computational cost is of the same order as gradient-based SOGBOFA techniques. However, unlike SOGBOFA, it is not finding a single sequence of actions, but what in effect is an approximate policy. This is more involved an often requires more iterations, particularly in very loopy graphs. In the IPPC problems, VBP was slower than SOGBOFA. VBP does not have a theoretical advantage over SOGBOFA when dynamics are very deterministic, and it is likely to be slower, so in those cases SOGBOFA might be a better alternative.

Are there convergence issues? The paper briefly discusses this but more detail is needed.

Just like when using loopy BP for inference, there are no convergence guarantees, and the presence of convergence actually correlates with good performance. There are many methods in the literature that address the non-convergence of loopy BP, turning it into a convergent algorithm (often using a double-loop algorithm, or using a concave approximation to the entropy terms to make the problem monomodal). All of these methods can be applied to VBP. Interestingly, although all of these approaches result in convergent algorithms, the performance doesn't significantly improve. This was our observation as well. Our convergent variant VI LP did not typically perform as well or as robustly as VBP, despite being convergent.

Can the other forms of inference (e.g., $F^\text{Marginal}$ , etc.) map exactly to different forms of planning? The experimental results seem to suggest this, e.g., $F^\text{Marginal}$ maps to ARollout, but it would be helpful to know this earlier in the paper.

Yes, different forms of inference map to different forms of planning, we discuss this in section 5 (Related work), but instead of using the $F$ notation, we describe it verbally, for instance pointing out that SOGBOFA corresponds to marginal MAP (which would be $F^\text{MMAP}$). We will further clarify this.

Use of the exponential utility and $\lambda$

The exponential utility is what allows us to write a compact factor graph that contains both rewards and dynamics. It contains the standard accumulated reward as a special case (when $\lambda \rightarrow 0$), so it is strictly more general. Note that in the standard formulation, rewards are additive, so we cannot include them in the factor graph directly. There is a path to deriving a variational formulation for the standard accumulated reward by using additional auxiliary variables and another step of lower bounding, but it would be an additional complication, and we believe that the introduction of $\lambda$ makes the model more flexible in practice (see below).

This is a pervasive problem when trying to connect planning with inference. See for instance (Levine, 2018). Their Eq. 8 tacitly uses an exponential utility with $\lambda = 1$. The motivation is the same as ours, being able to formulate the dynamics and rewards in the same factor graph. The introduction of $\lambda$ allows us to keep the simple factor graph formulation, while still being able to handle additive rewards. In practice, $\lambda$ would be a free tunable parameter that simply acknowledges the relevance of the scale of the reward when making rewards interact in a multiplicative way.

The IPPC setup corresponds to $\lambda \rightarrow 0$. However, in our internal experiments, we observed that for some problems, other values of $\lambda$ resulted in agents that were able to capture more rewards (even when measured in terms of the standard accumulated reward). The limitations of approximate inference sometimes make agents more conservative, and larger values of $\lambda$ encourage them to take more risks, which allows them to effectively capture more reward, regardless of how you measure it.

A more thorough discussion of the motivation and implications of the use of $\lambda$ parameter will be included.

Thank you for your careful reading and catching several typos. We have corrected the paper accordingly and include further explanations below.

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. If this is intended, please expand on this relationship.

We will explicitly mention the connection with value iteration and Bellman backups. Planning inference is exact in standard (non-factored) MDPs, and corresponds exactly to value iteration. The backward updates of Section 3.3 together with the definition of $Q(x_t, a_t)$ in line 163 can be recognized as the standard Bellman backups, although written with slightly different notation, since these are messages. In particular $Q(x_t, a_t)$ is exactly the Q-function.

Can you explain more what is the meaning and/or impact of the result that $F_\lambda^\text{planning}\leq F^{\text{marginal}}_{\lambda}$? e.g. Is the marginal inference an overapproximation?

$F^{\text{marginal}}_{\lambda}$ corresponds to running marginal inference on the unnormalized factor graph from Figure 1, the same on which we run planning inference. That factor graph is missing a prior term for the actions. This means that rather than averaging over all the possible sequences of actions, we are summing over all the possible sequences of actions. In the deterministic case it is obvious that this results in an overapproximation, since we are summing the "correct" total reward corresponding to the optimal sequence of actions plus the rewards obtained by all other sequences of actions. This intuition, although not as direct, carries over to the stochastic case, so yes, it is an overapproximation in the general case.

What are the terms in the denominator of $H_\text{MDP}$ and how is it computed for the IPPC domains?

A factored MDP such as the one in Figure 1[Right] describes, among other things, the dynamics of multiple entities that are locally independent. E.g., the distribution of $x^{(1)}$ is independent of the distribution of $x^{(2)}$ given the action and values of the entities in the previous time slice. We can separately compute the conditional entropies $H(p(x_{t+1}^{(i)}|x_t,a_t))$ for each entity $i$, conditional on each possible value $x_t, a_t$ of the previous time slice.

The normalized entropy is defined as

(note that there's a typo in the manuscript). The largest value of the conditional entropy $H(p(x_{t+1}^{(i)}|x_t,a_t))$ is achieved when dynamics are purely random and equals $\log N_s$, where $N_s$ is the number of states of entity (i), i.e., the cardinality $|x_{t+1}^{(i)}|$. Given that we are summing over all possible values of the previous time slice ($N_a$ is the number of possible actions and $N_s^{N_e}$ is the number of possible states of all $N_e$ entities in the previous time slice), and over all the entities $N_e$ in the current time slice, the maximum value of the numerator is $N_eN_aN_s^{N_e}\log N_s$, which is used as normalizing denominator. $H_\text{MDP}$ would equal 1 only when the dynamics of the factored MDP are purely random.

In the IPPC case, the problem setup gives us direct access to $p(x_{t+1}^{(i)}|x_t,a_t)$, where the conditioning only depends on a small number of entities from the previous timestep, so it is possible to compute $H(p(x_{t+1}^{(i)}|x_t,a_t))$ exactly for all entities and all $x_t, a_t$ and simply average those (which is equivalent to the summing and normalizing of the definition above for $H_\text{MDP}$).

About the definition of ${\pmb x}$ and $\pmb a$

These are defined in Section 2.1 (line 43 to be more precise).

$H_\text{Bethe}$ is not used in line 118

You are absolutely correct, we have fixed this. The corrected equation is

About the update equations in Sec 3.3 Thanks for pointing this out. Since these equations arise from deterministic distributions, we think the best option is to use a Kronecker delta $\delta_{a,b}$, where $\delta_{a,b} = 1$ if and only if $a = b$ and 0 otherwise. This results in

Forward updates:

Posterior:

About the normalized entropy and missing definitions

The terms $N_s, N_e$ are introduced in Section 2.1, we will add the definition of $N_a$ (which is the number of actions). The normalized entropy is probably the most naive way to measure the randomness of a factored MDP, and as far as we are aware has never been proposed before. It was very useful to characterize the behavior of the different types of inference.