Softstar: Heuristic-Guided Probabilistic Inference
Recent machine learning methods for sequential behavior prediction estimate the motives of behavior rather than the behavior itself. This higher-level abstraction improves generalization in different prediction settings, but computing predictions often becomes intractable in large decision spaces. We propose the Softstar algorithm, a softened heuristic-guided search technique for the maximum entropy inverse optimal control model of sequential behavior. This approach supports probabilistic search with bounded approximation error at a significantly reduced computational cost when compared to sampling based methods. We present the algorithm, analyze approximation guarantees, and compare performance with simulation-based inference on two distinct complex decision tasks.
I think this paper presents a valuable contribution to inverse optimal control and more generally to analysis of decision making and control as probabilistic inference. Incorporating ideas from heuristic search to estimate state marginals under the maxent model is an interesting and thought-provoking idea. The authors also evaluate their method on two interesting real-world datasets, including a football prediction dataset.I think that there is a lot to learn from this work, and I can see some follow-up working making good use of the ideas presented in this paper.That said, I think the paper is seriously hampered by confusing writing and excessive "specialization". For example, it took me several passes through the paper to understand that the authors were actually estimating the model parameters theta, which is mentioned briefly in the experiments section and at the end of Sec 2.2. Most of the paper is concerned with inference, which is indeed the most pressing problem in the maxent IOC framework, but the authors don't really explain this very well in the background section. The main technical sections of the paper are quite heavy on derivation and light on intuition and motivation, which also makes them tough to follow. Overall, I think the paper can be improved dramatically from a more thorough top-down organization that clearly lays out what the authors are trying to do, better explains the maxent model, and clarifies where the proposed component fits in in the context of a practical algorithm.