  We motivate and analyse a new Tree Search algorithm, GPTS, based on recent
theoretical advances in the use of Gaussian Processes for Bandit problems. We
consider tree paths as arms and we assume the target/reward function is drawn
from a GP distribution. The posterior mean and variance, after observing data,
are used to define confidence intervals for the function values, and we
sequentially play arms with highest upper confidence bounds. We give an
efficient implementation of GPTS and we adapt previous regret bounds by
determining the decay rate of the eigenvalues of the kernel matrix on the whole
set of tree paths. We consider two kernels in the feature space of binary
vectors indexed by the nodes of the tree: linear and Gaussian. The regret grows
in square root of the number of iterations T, up to a logarithmic factor, with
a constant that improves with bigger Gaussian kernel widths. We focus on
practical values of T, smaller than the number of arms. Finally, we apply GPTS
to Open Loop Planning in discounted Markov Decision Processes by modelling the
reward as a discounted sum of independent Gaussian Processes. We report similar
regret bounds to those of the OLOP algorithm.
