Soft-UCT: An algorithm for probabilistic planning based on a generalized mean operator

We propose a variant of the Upper Confidence bounds applied to Trees (UCT) algorithm as an alternative for time-constrained domain-independent probabilistic planning. The original UCT builds progressively the decision tree that represents a MDP and propagates averaged rewards through the tree. As a result, high but singular rewards in a large lookahead search can be "hidden out" in the partial tree generated by UCT. Our adaptation, called Soft-UCT, uses a "soft" generalized mean operator, starting the execution updating the expected reward with a weighted mean and, as the algorithm progresses and the search tree gets more similar to a complete search, the operator changes progressively until getting replaced by the maximum operator. We show how Soft-UCT performs in domain-independent probabilistic planning, with better results than UCT especially in domains that require a longer lookahead to get higher rewards.