  We present the first PAC optimal algorithm for Bayes-Adaptive Markov Decision
Processes (BAMDPs) in continuous state and action spaces, to the best of our
knowledge. The BAMDP framework elegantly addresses model uncertainty by
incorporating Bayesian belief updates into long-term expected return. However,
computing an exact optimal Bayesian policy is intractable. Our key insight is
to compute a near-optimal value function by covering the continuous
state-belief-action space with a finite set of representative samples and
exploiting the Lipschitz continuity of the value function. We prove the
near-optimality of our algorithm and analyze a number of schemes that boost the
algorithm's efficiency. Finally, we empirically validate our approach on a
number of discrete and continuous BAMDPs and show that the learned policy has
consistently competitive performance against baseline approaches.
