Online Reinforcement Learning in Periodic MDP

We study learning in periodic Markov decision process (MDP), a special type of nonstationary MDP where both the state transition probabilities and reward functions vary periodically, under the average reward maximization setting. We formulate the problem as a stationary MDP by augmenting the state space with the period index and propose a periodic upper confidence bound reinforcement learning-2 (PUCRL2) algorithm. We show that the regret of PUCRL2 varies linearly with the period <inline-formula><tex-math notation="LaTeX">$N$</tex-math></inline-formula> and as <inline-formula><tex-math notation="LaTeX">$\mathcal{O}(\sqrt{T \text{log} T})$</tex-math></inline-formula> with the horizon length <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula>. Utilizing the information about the sparsity of transition matrix of augmented MDP, we propose another algorithm [periodic upper confidence reinforcement learning with Bernstein bounds (PUCRLB) which enhances upon PUCRL2, both in terms of regret (<inline-formula><tex-math notation="LaTeX">$O(\sqrt{N})$</tex-math></inline-formula> dependency on period] and empirical performance. Finally, we propose two other algorithms U-PUCRL2 and U-PUCRLB for extended uncertainty in the environment in which the period is unknown but a set of candidate periods are known. Numerical results demonstrate the efficacy of all the algorithms.