How Does an Approximate Model Help in Reinforcement Learning?

  • 2020-07-13 18:42:20
  • Fei Feng, Wotao Yin, Lin F. Yang
  • 0

Abstract

One of the key approaches to save samples in reinforcement learning (RL) isto use knowledge from an approximate model such as its simulator. However, howmuch does an approximate model help to learn a near-optimal policy of the trueunknown model? Despite numerous empirical studies of transfer reinforcementlearning, an answer to this question is still elusive. In this paper, we studythe sample complexity of RL while an approximate model of the environment isprovided. For an unknown Markov decision process (MDP), we show that theapproximate model can effectively reduce the complexity by eliminatingsub-optimal actions from the policy searching space. In particular, we providean algorithm that uses $\widetilde{O}(N/(1-\gamma)^3/\varepsilon^2)$ samples ina generative model to learn an $\varepsilon$-optimal policy, where $\gamma$ isthe discount factor and $N$ is the number of near-optimal actions in theapproximate model. This can be much smaller than the learning-from-scratchcomplexity $\widetilde{\Theta}(SA/(1-\gamma)^3/\varepsilon^2)$, where $S$ and$A$ are the sizes of state and action spaces respectively. We also provide alower bound showing that the above upper bound is nearly-tight if the value gapbetween near-optimal actions and sub-optimal actions in the approximate modelis sufficiently large. Our results provide a very precise characterization ofhow an approximate model helps reinforcement learning when no additionalassumption on the model is posed.

 

Quick Read (beta)

loading the full paper ...