Stochastic Safe Action Model Learning

We appreciate the review. Here are some explanation of the details of our tensor decomposition based method.

The tensor decomposition will not return a non-distinct set of vectors V, because if there are two identical vectors, their weights will simply merge together in the decomposition, as we are seeking the minimum number of decomposed vectors.

$Rank(V)=r$ would indeed be a sufficient condition but it’s generally not true. We do not make such assumptions but instead raise the moment to a degree that is large enough to ensure such rank lower bound.

Could you please point out some of the cyclical arguments in Sec.4.1. so that we can further clarify?

Generic tensor is the set of all tensors with the exclusion of a measure zero set. It is a term that has been used by the literature for the convenience of mathematical proof. We also found this term ambiguous since binary valued tensors can possibly fall into this set of measure zero. Therefore, we seek to provide a sufficient guarantee for the uniqueness of tensor decomposition in Sec.2.2, and Sec. 2.3.

We appreciate the review. The following are the answers to the questions.

IPC probabilistic tracks is a set of benchmark datasets for planning, including parking, satellite, and transport planning. In these real world planning problems, the number of effects for each action is less than 5. The number of effects is the tensor rank in our formulation. Constantly small rank is a key requirement in our algorithm.

The second question is not very clear to us. What do you mean by “the level of stochasticity”?

The sample complexity does not depend on true effect probabilities values, but the confidence threshold and success rate. If the number of samples is large enough then the computed effect probabilities will be closer to the true probabilities.

We appreciate the interest in the symbolic learning aspect of our paper.

However, we would like to point out that our solution to this problem is not very intuitive. Firstly, even if the learning data consist of only positive trajectories, the success rate can still go wrong if the learned effect distribution of action model is off. Besides, the sampled policy that we used to produce the trajectories in the training set does not always end up reaching the goal state: the agent can simply reach the maximum number of steps and stop (please see the end of Sec. 2.1).

The theorem under Sec.2.2 and Lemma 1 are classical tensor decomposition results. Theorem 1,2 both require long proofs which are not the focus of this paper. As long as we obtain the learning guarantee of the action’s effect distribution, we can plug it into their proof without much change. The main focus in this paper is how to learn each action’s effects without the strong assumption of independence of the environment factors.

The superscript cross d means doing outer product with itself d times. $a_k, b_k, c_k$ are column vectors of the matrix.

Again, this paper presents a completely different learning approach than Juba & Stern 2022. We are solving a problem with a more general setting, where the probability of the change of each environmental factor given an action is not necessarily independent of those of other factors (please also see our answer to reviewer bFXN).

Thank you for the response. We would strongly recommend reading our answer to reviewer bFXN, as it clarifies the difference between our paper and Juba & Stern 2022, and more importantly, why their theoretical proof of safety and completeness is not our focus and we do not heavily rely on that. Regardless, we will simply repeat it as follows.

Please note that the learning algorithm we propose has very little to do with the learning method proposed by Juba & Stern (2022). Their learning algorithm is simply computing the empirical estimates of $Pr( \ell’|a, \ell)$ for all the environment factor $\ell’$ and $\ell$ to reconstruct the transition probabilities $Pr(s’ | a, s)$, which is a product of $Pr( \ell’|a, \ell)$ probabilities, since they assume that the environment factors \ell are independent. This is not the case in our problem because we lifted the restriction of the factors being independent. If we simply compute the empirical estimates of all the transition probabilities $Pr(s’ | a, s)$, it will be infeasible since the number of states is exponentially large. Our tensor decomposition based learning method allows us to infer the set of effects of each action by only estimating a polynomial number of moments with bounded degree.

The key that enables the use of Juba & Stern (2022)’s proof of safety and approximate completeness is the learning guarantee of each action’s set of effects in Alg.1 in this more general stochastic action model, which is the focus of this paper. Juba & Stern (2022) did not need such guarantee for their proof of safety or completeness, since their strong assumption of the independence of state factors allows them to simply learn the action’s effect on each factor independently.

Because we do not assume such independence. Our setting is more general. The assumption of small number of effects for each action is justified in all the realistic benchmark datasets for planning in IPC probabilistic tracks, including parking, satellite, and transport planning, where the number of effects for each action is less than 5.

Thank you for the response! As for running example, please see illustrations in section 3.2 equations (2) and (3), and a toy example that we included in Appendix C of the revision.

Thank you for pointing out the confusing part of this paper.

When you say “methodology of Juba & Stern (2022)”, do you mean the learning method or the method to prove safety and approximate completeness?

If you meant the learning method, please note that our assumptions of a more general stochasticity does not help us learn, and the learning algorithm we propose has very little to do with the learning method proposed by Juba & Stern (2022). Their learning algorithm is simply computing the empirical estimates of $Pr( \ell’|a, \ell)$ for all the environment factor $\ell’$ and $\ell$ to reconstruct the transition probabilities $Pr(s’ | a, s)$, which is a product of $Pr( \ell’|a, \ell)$ probabilities, since they assume that the environment factors \ell are independent. This is not the case in our problem because we lifted the restriction of the factors being independent. If we simply compute the empirical estimates of all the transition probabilities $Pr(s’ | a, s)$, it will be infeasible since the number of states is exponentially large. Our tensor decomposition based learning method allows us to infer the set of effects of each action by only estimating a polynomial number of moments with bounded degree.

If you meant the latter, then please note that the key that enables the use of Juba & Stern (2022)’s proof of safety and approximate completeness is the learning guarantee of each action’s set of effects in Alg.1 in this more general stochastic action model, which is the focus of this paper. Juba & Stern (2022) did not need such guarantee for their proof of safety or completeness, since their strong assumption of the independence of state factors allows them to simply learn the action’s effect on each factor independently.

Please note that PPDDL has an established action model that applies to the real world. Our model is strictly more general, which at least captures these real world situations and beyond.

We agree that experiments will make this work stronger. However, the focus of this work is to derive a provable learning guarantee for the complex environment we consider, where it was not clear even a polynomial-time learning algorithm exists for this setting.