Randomized Exploration for Reinforcement Learning with General Value Function Approximation
This addresses exploration challenges in reinforcement learning for researchers and practitioners, offering a more computationally efficient alternative to UCB-based methods, though it appears incremental as it builds on existing RLSVI and optimism principles.
The paper tackles the problem of computationally intractable exploration in reinforcement learning by proposing a model-free algorithm that uses randomized perturbations and optimistic reward sampling instead of UCB bonuses, achieving a worst-case regret bound of $\widetilde{O}(\mathrm{poly}(d_EH)\sqrt{T})$ and reducing to $\widetilde{\mathcal{O}}(\sqrt{d^3H^3T})$ in linear settings.
We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm as well as the optimism principle. Unlike existing upper-confidence-bound (UCB) based approaches, which are often computationally intractable, our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. To attain optimistic value function estimation without resorting to a UCB-style bonus, we introduce an optimistic reward sampling procedure. When the value functions can be represented by a function class $\mathcal{F}$, our algorithm achieves a worst-case regret bound of $\widetilde{O}(\mathrm{poly}(d_EH)\sqrt{T})$ where $T$ is the time elapsed, $H$ is the planning horizon and $d_E$ is the $\textit{eluder dimension}$ of $\mathcal{F}$. In the linear setting, our algorithm reduces to LSVI-PHE, a variant of RLSVI, that enjoys an $\widetilde{\mathcal{O}}(\sqrt{d^3H^3T})$ regret. We complement the theory with an empirical evaluation across known difficult exploration tasks.