Exploration in Model-based Reinforcement Learning with Randomized Reward
This work addresses a foundational problem in reinforcement learning theory by bridging theory and practice for researchers, though it is incremental as it builds on existing MBRL frameworks.
The paper tackles the gap between theoretical worst-case regret analysis and empirical success in model-based reinforcement learning by investigating whether randomized model ensembles guarantee optimism, showing that reward randomization under the kernelized linear regulator model yields partial optimism and near-optimal worst-case regret in terms of interactions.
Model-based Reinforcement Learning (MBRL) has been widely adapted due to its sample efficiency. However, existing worst-case regret analysis typically requires optimistic planning, which is not realistic in general. In contrast, motivated by the theory, empirical study utilizes ensemble of models, which achieve state-of-the-art performance on various testing environments. Such deviation between theory and empirical study leads us to question whether randomized model ensemble guarantee optimism, and hence the optimal worst-case regret? This paper partially answers such question from the perspective of reward randomization, a scarcely explored direction of exploration with MBRL. We show that under the kernelized linear regulator (KNR) model, reward randomization guarantees a partial optimism, which further yields a near-optimal worst-case regret in terms of the number of interactions. We further extend our theory to generalized function approximation and identified conditions for reward randomization to attain provably efficient exploration. Correspondingly, we propose concrete examples of efficient reward randomization. To the best of our knowledge, our analysis establishes the first worst-case regret analysis on randomized MBRL with function approximation.