Learning in Online MDPs: Is there a Price for Handling the Communicating Case?
This resolves a theoretical gap in online reinforcement learning by clarifying the impact of feedback type on regret rates for communicating MDPs.
The paper tackles the problem of learning in online Markov Decision Processes (MDPs) with communicating structure, showing that with full information, an O(√T) regret rate can be achieved, which improves upon the previously known Ω(T^{2/3}) lower bound for bandit feedback.
It is a remarkable fact that the same $O(\sqrt{T})$ regret rate can be achieved in both the Experts Problem and the Adversarial Multi-Armed Bandit problem albeit with a worse dependence on number of actions in the latter case. In contrast, it has been shown that handling online MDPs with communicating structure and bandit information incurs $Ω(T^{2/3})$ regret even in the case of deterministic transitions. Is this the price we pay for handling communicating structure or is it because we also have bandit feedback? In this paper we show that with full information, online MDPs can still be learned at an $O(\sqrt{T})$ rate even in the presence of communicating structure. We first show this by proposing an efficient follow the perturbed leader (FPL) algorithm for the deterministic transition case. We then extend our scope to consider stochastic transitions where we first give an inefficient $O(\sqrt{T})$-regret algorithm (with a mild additional condition on the dynamics). Then we show how to achieve $O\left(\sqrt{\frac{T}α}\right)$ regret rate using an oracle-efficient algorithm but with the additional restriction that the starting state distribution has mass at least $α$ on each state.