  Solving Partially Observable Markov Decision Processes (POMDPs) is hard.
Learning optimal controllers for POMDPs when the model is unknown is harder.
Online learning of optimal controllers for unknown POMDPs, which requires
efficient learning using regret-minimizing algorithms that effectively tradeoff
exploration and exploitation, is even harder, and no solution exists currently.
In this paper, we consider infinite-horizon average-cost POMDPs with unknown
transition model, though a known observation model. We propose a natural
posterior sampling-based reinforcement learning algorithm (PSRL-POMDP) and show
that it achieves a regret bound of $O(\log T)$, where $T$ is the time horizon,
when the parameter set is finite. In the general case (continuous parameter
set), we show that the algorithm achieves $O (T^{2/3})$ regret under two
technical assumptions. To the best of our knowledge, this is the first online
RL algorithm for POMDPs and has sub-linear regret.
