Generalization and Exploration via Randomized Value Functions

By Ian Osband, Benjamin Van Roy, Zheng Wen. 2014

339 citations recorded by the source corpus.

We propose randomized least-squares value iteration (RLSVI) -- a new reinforcement learning algorithm designed to explore and generalize efficiently via linearly parameterized value functions. We explain why versions of least-squares value iteration that use Boltzmann or epsilon-greedy exploration can be highly inefficient, and we present computational results that demonstrate dramatic efficiency gains enjoyed by RLSVI. Further, we establish an upper bound on the expected regret of RLSVI that demonstrates near-optimality in a tabula rasa learning context. More broadly, our results suggest that randomized value functions offer a promising approach to tackling a critical challenge in reinforcement learning: synthesizing efficient exploration and effective generalization.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

In Optimization & Training

Citations in the corpus

The Uncertainty Bellman Equation and Exploration (2017, background): “This assumption means that the agent cannot revisit a state within the same episode, and is a common assumption in the literature (Osband et al., 2014).”
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, methodology): “We replace Lemma 5 in [21] with a relaxation for V ∈ { 0 , h } S .”
Deep Exploration via Bootstrapped DQN (2016, methodology): “The analysis for the linear setting suggests that this nonlinear approach will work well so long as the distribution { Q 1 , .., Q K } remains stochastically optimistic [16], or at least as spread out as the “correct” posterior.”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, background): “Approximations to the optimal Bayesian policy exist, one of the most successful being Thompson sampling [53, 55] wherein the agent samples from the posterior over value functions and acts greedily with respect to that sample [38, 42, 27, 41].”
Episodic Exploration for Deep Deterministic Policies: An Application to StarCraft Micromanagement Tasks (2016, methodology): “Compared to algorithms for eﬃcient direct exploration in parameter space (see e.g., [18, 27, 37, 25]), the novelty of our algorithm is to mix exploration through parameter randomization and plain gradient descent.”
Count-Based Exploration with Neural Density Models (2017, background): “From a theoretical perspective, exploration is now well-understood (e.g. Strehl & Littman, 2008; Jaksch et al., 2010; Osband et al., 2016), and Bayesian methods have been successfully demonstrated in a number of settings (Deisenroth & Rasmussen, 2011; Guez et al., 2012).”
Noisy Networks for Exploration (2017, background): “Randomised value functions provide a provably efﬁcient means of exploration (Osband et al., 2014).”
#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning (2016, background): “Although these heuristics are suﬃcient in tasks with well-shaped rewards, the sample complexity can grow exponentially (with state space size) in tasks with sparse rewards (Osband et al., 2016b).”
Randomized Prior Functions for Deep Reinforcement Learning (2018, background): “Crucially, algorithms without deep exploration take (2N ) episodes to learn the optimal policy [52].”
Parameter Space Noise for Exploration (2017, background): “In the context of deep reinforcement learning, a large variety of techniques have been proposed to improve exploration [5, 3, 1, 7, 2, 36, 37].”
Stochastic Neural Networks for Hierarchical Reinforcement Learning (2016, background): “The challenge is further complicated by long horizons, where naive exploration strategies can lead to exponentially large sample complexity (Osband et al., 2014).”
Efficient Exploration Through Bayesian Deep Q-Networks (2018, methodology): “Since we assume the environment is an MDP, following the Bellman optimality we have for h H (cid:12)(cid:12)(cid:12) where the optimal policy π ∗ ( ) denotes a deterministic mapping from states to actions.”
Reverse Curriculum Generation for Reinforcement Learning (2017, background): “As discussed above, the sparsity of this reward function makes learning extremely difficult for RL algorithms [6, 31, 32], and approaches like reward shaping [7] are difficult and time-consuming to engineer for each task.”
A Tutorial on Thompson Sampling (2017, background): “Subsequent papers have further developed this theory [43, 44, 45] and have studied extensions of Thompson sampling to reinforcement-learning [35, 46, 47, 48].”
From Language to Programs: Bridging Reinforcement Learning and Maximum Marginal Likelihood (2017, background): “…such as (cid:15) -greedy, entropy regularization (Williams and Peng, 1991), Monte Carlo tree search (Coulom, 2006), randomized value functions (Osband et al., 2014, 2016), and meth-ods which prioritize learning environment dynamics (Duff, 2002) or under-explored states (Kearns and Singh,…”
Deep Exploration via Randomized Value Functions (2017, background): “A preliminary version of part of this work has also been reported in a short paper [34].”
Near-optimal Reinforcement Learning in Factored MDPs (2014, background): “Value-based approaches typically struggle to plan efficient exploration and so cannot obtain efficient learning guarantees, although there has been interesting progress in this field as well [25].”
Provably Efficient Exploration in Policy Optimization (2019, methodology): “Broadly speaking, our work is related to a vast body of work on value-based reinforcement learning in tabular (Jaksch et al., 2010; Osband et al., 2014; Osband & Van Roy, 2016; Azar et al., 2017; Dann et al., 2017; Strehl et al., 2006; Jin et al., 2018) and linear settings (Yang & Wang, 2019b;a; Jin”