The Dirichlet measure has probability density function w.r.t. Here we first note the original result from Biggs and Guedj (2022b) that is adapted in Equation (3); since this is obtained by applying an upper bound to the inverse small-kl and an additional step, it is strictly looser than the result we give in Equation (3). Biggs and Guedj (2022b) also uses a dimension doubling trick to allow negative weights (as they consider only the binary case), which we remove here to replace the factor log(2d) by log d. B.1 Definition of the margin We here note that the definition of the margin given in Gao and Zhou (2013) and Biggs and Guedj (2022b) is slightly different from our own, leading to a scaling of the margin definition by a factor of one-half. B.2 Proof of Theorem 6 and Equation (3) For completeness we provide here short proofs of Equation (3) and Theorem 6.

We study the model-based undiscounted reinforcement learning for partially observable Markov decision processes (POMDPs). The oracle we consider is the optimal policy of the POMDP with a known environment in terms of the average reward over an infinite horizon. We propose a learning algorithm for this problem, building on spectral method-of-moments estimations for hidden Markov models, the belief error control in POMDPs and upper-confidence-bound methods for online learning. We establish a regret bound of $O(T^{2/3}\sqrt{\log T})$ for the proposed learning algorithm where $T$ is the learning horizon. This is, to the best of our knowledge, the first algorithm achieving sublinear regret with respect to our oracle for learning general POMDPs.