A Theory Proofs and Complimentary Material

First, obviously, the maximum over a set containing a single random variable has the distribution of that single element. Hence, there is no overestimation bias in the single-element case; i.e., Next, we consider the two (deterministic) following possible cases. In the rest of the proof, we shall apply Cantelli's inequality to upper bound Theorem 3.5 now follows from Theorem A.1 after plugging the approximation The scores are obtained via BCTS with a Batch-BFS implementation, as reported in Section 5.1. TS of depths 2,3, and 4. Note that for depth 1, the correction is vacuous since it coincides with the Episodic training cumulative reward of DQN with TS based on 5 seeds. Lastly, we summarize the results for all tested games in Table 2. Ablation study: Propagated value (PV) from the tree nodes: Ablation study for scores of all tested games.