According to Alg. 2, in each exploration, at least one leaf node will be expanded. Moreover, the overall size of the belief tree isO((|A|min(Pδmax,Nmax))D), where Nmax is the maximum sample size given by KLD-Sampling,Pδmax = supb,aPδ(Yb,a), and Yb,a is the set of reachable beliefs after executing actiona at belief b. The tree size is limited sinceNmax is finite. The weights are normalized, i.e., There exist bounded functionsα and α0 such that V (b) = R α(s)b(s)ds, and V (b0) = R α0(s)b0(s)ds. Wecan bound the first and third terms, respectively,byλinlight ofthe assumptions.

Thepartially observableMarkovdecision process (POMDP) provides ageneral framework for modeling an agent's decision process with state uncertainty, and online planning plays a pivotal role in solving it. A belief is a distribution of states representing state uncertainty. Methods forlarge-scale POMDP problems rely on the same idea of sampling both states and observations.

According to Alg. 2, in each exploration, at least one leaf node will be expanded. Thus, we have the conclusion that AdaOPS is guaranteed to terminate. First, we will demonstrate that the value of any belief can be formulated as an integral. This lemma is a concentration inequality of self-normalized importance sampling estimator. The ESS threshold µ for adaptive resampling is set to .