Settling the Sample Complexity of Online Reinforcement Learning

arXiv:2307.13586v2 Announce Type: replace
Abstract: A central issue lying at the heart of online reinforcement learning (RL) is data efficiency. While a number of recent works achieved asymptotically minimal regret in online RL, the optimality of these results is only guaranteed in a ``large-sample'' regime, imposing enormous burn-in cost in order for their algorithms to operate optimally. How to achieve minimax-optimal regret without incurring any burn-in cost has been an open problem in RL theory.
We settle this problem for …

abstract arxiv complexity cost cs.lg data efficiency issue online reinforcement learning reinforcement reinforcement learning results sample type