Online regret bounds for undiscounted continuous reinforcement learning

We derive sublinear regret bounds for undiscounted reinforcement learning in con-tinuous state space. The proposed algorithm combines state aggregation with the use of upper confidence bounds for implementing optimism in the face of uncer-tainty. Beside the existence of an optimal policy which satisfies the Poisson equa-tion, the only assumptions made are Hölder continuity of rewards and transition probabilities.