# Generalization and Exploration via Randomized Value Functions

arXiv: https://arxiv.org/abs/1402.0635 · HTML: https://mlsanity.com/paper/1402.0635/

## Key facts

- Cited by 112 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2014.

## Built on by (most cited first, 30 of 112)

- [Exploration in Deep Reinforcement Learning: A Survey](https://mlsanity.com/paper/2205.00824/) (2022)
- [Epistemic Neural Networks](https://mlsanity.com/paper/2107.08924/) (2021)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [A Survey of Exploration Methods in Reinforcement Learning](https://mlsanity.com/paper/2109.00157/) (2021)
- [Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domain](https://mlsanity.com/paper/2109.06668/) (2021)
- [Randomized Exploration for Reinforcement Learning with General Value Function Approximation](https://mlsanity.com/paper/2106.07841/) (2021)
- [Making RL with Preference-based Feedback Efficient via Randomization](https://mlsanity.com/paper/2310.14554/) (2023)
- [Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity](https://mlsanity.com/paper/2206.07659/) (2022)
- [Thompson sampling for improved exploration in GFlowNets](https://mlsanity.com/paper/2306.17693/) (2023)
- [A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning](https://mlsanity.com/paper/2208.10904/) (2022)
- [On the Importance of Exploration for Generalization in Reinforcement Learning](https://mlsanity.com/paper/2306.05483/) (2023)
- [Minimax Regret for Stochastic Shortest Path](https://mlsanity.com/paper/2103.13056/) (2021)
- [Provable Benefit of Multitask Representation Learning in Reinforcement Learning](https://mlsanity.com/paper/2206.05900/) (2022)
- [Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo](https://mlsanity.com/paper/2305.18246/) (2023)
- [Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting](https://mlsanity.com/paper/2105.08024/) (2021)
- [Reinforced Few-Shot Acquisition Function Learning for Bayesian Optimization](https://mlsanity.com/paper/2106.04335/) (2021)
- [A Single Goal is All You Need: Skills and Exploration Emerge from Contrastive RL without Rewards, Demonstrations, or Subgoals](https://mlsanity.com/paper/2408.05804/) (2024)
- [Beyond Fine-Tuning: Transferring Behavior in Reinforcement Learning](https://mlsanity.com/paper/2102.13515/) (2021)
- [Cross-Trajectory Representation Learning for Zero-Shot Generalization in RL](https://mlsanity.com/paper/2106.02193/) (2021)
- [Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learning](https://mlsanity.com/paper/2206.02072/) (2022)
- [Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning](https://mlsanity.com/paper/2202.10678/) (2022)
- [Langevin Soft Actor-Critic: Efficient Exploration through Uncertainty-Driven Critic Learning](https://mlsanity.com/paper/2501.17827/) (2025)
- [Toward Efficient Exploration by Large Language Model Agents](https://mlsanity.com/paper/2504.20997/) (2025)
- [Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets](https://mlsanity.com/paper/2203.03684/) (2022)
- [Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency](https://mlsanity.com/paper/2204.09787/) (2022)
- [A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Games](https://mlsanity.com/paper/2210.01907/) (2022)
- [Posterior Sampling for Deep Reinforcement Learning](https://mlsanity.com/paper/2305.00477/) (2023)
- [Near-Optimal Randomized Exploration for Tabular Markov Decision Processes](https://mlsanity.com/paper/2102.09703/) (2021)
- [The Value of Information When Deciding What to Learn](https://mlsanity.com/paper/2110.13973/) (2021)
- [An L2 Analysis of Reinforcement Learning in High Dimensions with Kernel and Neural Network Approximation](https://mlsanity.com/paper/2104.07794/) (2021)

## Abstract (arXiv)

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.