A Provably Efficient Sample Collection Strategy for Reinforcement Learning

One of the challenges in online reinforcement learning (RL) is that the agent\nneeds to trade off the exploration of the environment and the exploitation of\nthe samples to optimize its behavior. Whether we optimize for regret, sample\ncomplexity, state-space coverage or model estimation, we need to strike a\ndifferent exploration-exploitation trade-off. In this paper, we propose to\ntackle the exploration-exploitation problem following a decoupled approach\ncomposed of: 1) An "objective-specific" algorithm that (adaptively) prescribes\nhow many samples to collect at which states, as if it has access to a\ngenerative model (i.e., a simulator of the environment); 2) An\n"objective-agnostic" sample collection exploration strategy responsible for\ngenerating the prescribed samples as fast as possible. Building on recent\nmethods for exploration in the stochastic shortest path problem, we first\nprovide an algorithm that, given as input the number of samples $b(s,a)$ needed\nin each state-action pair, requires $\\tilde{O}(B D + D^{3/2} S^2 A)$ time steps\nto collect the $B=\\sum_{s,a} b(s,a)$ desired samples, in any unknown\ncommunicating MDP with $S$ states, $A$ actions and diameter $D$. Then we show\nhow this general-purpose exploration algorithm can be paired with\n"objective-specific" strategies that prescribe the sample requirements to\ntackle a variety of settings -- e.g., model estimation, sparse reward\ndiscovery, goal-free cost-free exploration in communicating MDPs -- for which\nwe obtain improved or novel sample complexity guarantees.\n