Deep Exploration via Randomized Value Functions

Motivation and approach

• Efficient exploration remains challenging because practical reinforcement-learning problems have enormous state spaces requiring algorithms that generalize across states while learning effective decisions quickly.Most prior exploration work focuses on tabular representations whose parameter and data requirements scale with the number of states.Source: §1 · p. 1
• Dithering wastes exploratory effort by ignoring uncertainty, while myopic exploration overlooks future learning opportunities and can require exponential learning time or fail entirely.Deep exploration instead considers how actions affect subsequent information and may accept losses over multiple steps for later informative observations.Source: §1 · p. 2
• Randomized value functions enable deep exploration by selecting actions greedily under statistically plausible sampled value functions, encouraging experimentation with uncertain actions and future learning consequences.The approach approximates posterior sampling over value functions; uncertainty creates sampled-value variance and often positive bias that induces exploration.Source: §1 · p. 2

Contributions

• Randomized value functions are abstract and broadly applicable, allowing established reinforcement-learning ideas to be combined into custom exploration algorithms for specific contexts.The framework is intended to synthesize efficient exploration with practical value-function learning methods that generalize over states and actions.Source: §1 · pp. 1, 3
• The paper establishes a strong Bayesian-regret bound for a tabular algorithm that also works effectively with parameterized value-function methods capable of generalizing over states and actions.The authors describe this as the first such combination of a strong tabular regret guarantee with compatibility across practical generalizing value-function methods.Source: §1 · p. 3
• Computational studies show dramatic efficiency gains over dithering on toy problems and apply randomized value functions with linear and neural-network value functions to generalizing exploration tasks.The experiments include cart-pole balancing, which requires both deep exploration and generalization.Source: §1 · p. 3

Exploration challenge

• Bayes-optimal exploration is statistically efficient but computationally intractable, motivating randomized value functions as a practical alternative for deep exploration.The Bayes-optimal policy conditions actions on the posterior and can require computation exponential in problem parameters.Source: §2 · p. 3

Tabular exploration

• Tabular research established that multi-period deep exploration enables polynomial-time learning, whereas ϵ-greedy and Boltzmann exploration can require exponentially long learning times.The tabular algorithms bound sub-optimality polynomially in states and/or horizon, but their state-space requirements limit practical importance.Source: §2 · pp. 3–4

Generalization

• Practical reinforcement learning requires generalization across enormous state spaces, yet successful applications using naive exploration have often consumed hundreds of billions to trillions of simulated games.Model-learning and policy-learning methods face restrictive assumptions or computational/statistical difficulties at practical scale.Source: §2 · p. 4

Randomized value functions

• RLSVI explores by sampling statistically plausible parameterized value functions, extending randomized value-function learning beyond prior algorithms and aiming to avoid exponential learning times.The paper develops a general template, several instantiations, new simulations including neural-network approximation, and a full regret analysis.Source: §2 · pp. 4–5

Regret analysis

• The tabular RLSVI analysis gives an expected regret bound ˜O(HSAHL), versus an adapted universal lower bound Ω(HSAL), differing by a factor of H.The comparison is not apples-to-apples because the lower bound maximizes over MDPs, whereas the upper bound averages under a specified prior; Russo (2019) later established worst-case tabular bounds.Source: §2 · p. 5

Related exploration methods

• Randomized value functions approximate posterior sampling of the optimal value function, unlike pseudocount bonuses or distributional RL, which represent different notions of uncertainty.Pseudocount bonuses can misalign generalization with task objectives and couple uncertainty poorly across states, while distributional RL models stochastic realized outcomes rather than Bayesian uncertainty about the optimal value.Source: §2 · p. 6

MDP formulation

• The environment is a finite MDP M = (S,A,R,P,ρ), with stochastic rewards, sub-distribution transitions, and termination represented by missing transition probability.The initial-state distribution ρ determines where episodes begin, while transition and reward models govern subsequent observations.Source: §3 · p. 6

Episodic interaction

• Episodes begin from ρ, proceed through sampled actions, rewards, and transitions, and end at a random termination time τℓ.Policies map states to action distributions, and the induced transition matrix is substochastic.Source: §3 · pp. 6–7

Finite-horizon condition

• Assumption 1 requires every policy-induced MDP to terminate almost surely in finite time, ensuring well-defined episodes and value functions.The condition is expressed as limt→∞ P_π^t = 0 for every policy π.Source: §3 · p. 7

Algorithms and evaluation

• Before each episode, algorithm alg selects a policy from prior observation history, and regret compares its expected value with the optimal value.Bayesian regret instead averages performance over a prior distribution on MDPs, avoiding worst-case evaluation that can produce overly conservative behavior.Source: §3 · pp. 7–8

Deep-sea example

• In the deep-sea example, uniform random exploration reaches the chest with probability (1/2)^N per episode, making discovery require an expected 2^N episodes.The example has N^2 grid states, episodes lasting N periods, unknown action associations, and an unknown treasure-or-bomb reward.Source: §4 · pp. 8–9

Failure of conventional exploration

• Pure exploitation never visits the chest because its expected reward is zero and moving toward it incurs cost, so it is unlikely to learn an optimal policy.Dithering remains biased against the chest and relies on random perturbations, yielding expected learning time Θ(2N).Source: §4 · pp. 10–11

Deep exploration

• Deep exploration values actions that may create downstream learning opportunities, even when they provide no immediate reward or information.Myopic exploration fails because it avoids costly actions whose benefits arise only after several subsequent steps.Source: §4 · p. 11

Optimistic and randomized exploration

• Optimism drives consecutive rightward actions toward the chest and learns an optimal policy within N episodes, while randomized posterior value samples achieve this within 2^N episodes.Randomized samples are optimistic or pessimistic with equal probability before the chest is observed, producing optimistic-like exploration in half the episodes.Source: §4 · pp. 11–12

Overall comparison

• For Example 1, optimistic and randomized exploration learn an optimal policy in Θ(N) episodes, matching the minimal time, while pure exploitation and myopic exploration require Θ(2N).Dithering does not help in this problem; the minimal strategy moves right whenever it knows how to.Source: §4 · p. 12

5. Algorithms

• The algorithms contribute randomized value functions as a broadly applicable approach intended to enable computationally efficient deep exploration.The framework builds on value function learning and complements existing reinforcement-learning algorithmic ideas.Source: §5 · pp. 12–13

5.1 Value function learning

• Value function learning represents state-action values with parameterized families and agents that act, store observations, and learn from their buffers.Agents may select greedy actions, update a memory buffer, and learn value estimates from accumulated data.Source: §5.1 · p. 13

5.2 Least-squares value iteration

• LSVI approximates value iteration from observed data while avoiding state-space scaling, but finite data and restricted parameterizations can make its estimates differ from optimal values.Its computation scales polynomially with parameter dimension, historical observations, and action maximization time rather than linearly with the number of states.Source: §5.2 · pp. 14–16

5.3 Randomized least-squares value iteration

• RLSVI makes value-function sampling computationally tractable by randomizing LSVI computations, offering an effective approach to deep exploration without explicitly maintaining Bayesian beliefs.The method was first introduced in Wen (2014), with later work studying linear and nonlinear function approximation (Osband et al., 2016b,a; Osband, 2016).Source: §5.3 · p. 16

5.3.1 Randomization via Gaussian noise

• Gaussian RLSVI injects noise into data and priors so that, in linear regression, perturbed least-squares training matches conjugate Bayesian posterior sampling.The resulting learn grlsvi method is identical to LSVI except that optimization uses randomized versions of the underlying data and prior.Source: §5.3.1 · pp. 17–18

5.3.2 How does RLSVI drive deep exploration?

• RLSVI propagates uncertainty across transitions and horizons, producing optimistic samples that can incentivize pursuing information requiring multiple time periods.High-variance value samples arise where optimal-value uncertainty is large, thereby driving deep exploration rather than only immediate-reward dithering.Source: §5.3.2 · p. 20

5.3.3 Randomization via statistical bootstrap

• Statistical bootstrap randomizes by resampling datasets with replacement, providing a data-based alternative to Gaussian noise that may better capture the generating process.The classic bootstrap creates a sampled dataset of the same size as the original and can provide convergence guarantees in certain cases.Source: §5.3.3 · p. 20
• Bootstrap-randomized value functions avoid specifying a noise variance and can induce state-dependent, heteroskedastic randomization, while random prior regularization enables early exploration.Without random-prior regularization, bootstrap-based methods can lack meaningful early uncertainty and incur regret linear in the time horizon; the prior effect vanishes as diverse data accumulates.Source: §5.3.3 · p. 21

5.4 Practical variants of RLSVI

• Practical RLSVI variants target computational efficiency and robustness to mis-specification by combining interchangeable ideas from reinforcement learning into algorithms for complex problems.The section presents a non-exhaustive mix of methods rather than a complete survey of possible variants.Source: §5.4 · p. 21

5.4.1 Finite buffer experience replay

• Finite-buffer experience replay replaces the linearly growing infinite buffer with a FIFO queue, reducing memory and computation while emphasizing recent data when Q* cannot be represented by Qθ.Prior work also suggests that prioritizing data in finite buffers can improve storage decisions (Schaul et al., 2015).Source: §5.4.1 · pp. 21–22

5.4.2 Discounted TD and incremental learning

• Discounted TD learning replaces horizon-specific batch recomputation with incremental updates, and learn online lsvi updates its previous estimate by gradient descent over subsets of data.The discount factor γ induces an effective planning horizon of approximately 1/(1−γ), while the method is a temporal-difference approach related to TD-gammon and DQN.Source: §5.4.2 · p. 22

5.4.3 Randomization via ensemble sampling

• Ensemble sampling approximates RLSVI’s randomized estimate distribution with K parallel estimates, each trained on perturbed data and sampled uniformly at the start of an episode.Ensemble RLSVI maintains separate perturbed-data buffers and parameter estimates, but off-policy TD losses can become unstable or diverge, motivating alternatives designed for off-policy learning (Munos et al., 2016).Source: §5.4.3 · p. 23, Figure 3 · p. 23

6.1 Formulation of a time-inhomogenous MDP

• The regret guarantee is established for finite-horizon time-inhomogeneous MDPs whose outcome distributions are independently drawn from Dirichlet priors with binary rewards.States advance through time-indexed layers and terminate after period H; the Dirichlet prior assumption is not required for every intermediate result.Source: §6.1 · p. 25

6.2 Bayesian regret bound

• RLSVI achieves Bayesian regret ˜O(H2√∣X∣∣A∣L) when β is constant, requiring episodes scaling linearly with ∣X∣ to reach near-optimal performance.The result applies to infinite-buffer, greedy RLSVI with tabular representation under Assumption 3 and parameters v = 3H2, ¯θ = H1, and v/λ = β.Source: §6.2 · p. 26

6.3 Stochastic Bellman operators

• RLSVI’s stochastic Bellman operator differs from the empirical update through prior-mean regularization and, crucially, independent Gaussian noise added to each update.These randomized updates generate the value-function sequence used for greedy action selection.Source: §6.3 · pp. 27–28

6.4 Optimism and regret decompositions

• When the initial sampled value is optimistic, episode regret is bounded by on-policy Bellman error, yielding the decomposition used to analyze cumulative regret.The resulting corollary provides the core reduction: prove optimism in every episode, then bound cumulative on-policy Bellman error.Source: §6.4 · p. 29

6.5 Stochastic optimism

• RLSVI obtains stochastic optimism because Gaussian Bellman updates dominate Dirichlet transition averages, and this ordering is preserved through convex operations, convolution, maximization, and recursive Bellman application.The analysis defines stochastic optimism using expectations of all convex increasing functions and establishes monotonicity of the randomized Bellman operator.Source: §6.5 · pp. 30–32
• Lemmas 3 and 5 imply stochastic optimism for the state-action value functions Qℓ,0 generated by RLSVI.Corollary 2 specifies parameter conditions under which this result holds.Source: §6.5 · p. 32

6.6 Analysis of on-policy Bellman error: proof of Theorem 1

• The regret proof bounds RLSVI’s visited noise terms and sampled value-function norms using a Gaussian maximal-inequality argument.The analysis also uses conditional independence and Corollary 4 to control the accumulated terms.Source: §6.6 · pp. 33–35
• The combined calculations establish the regret bound for RLSVI and complete the proof of Theorem 1.The final step handles separate regimes of L and applies either the derived bound or a naive bound.Source: §6.6 · pp. 35–36

7. Computational studies

• The studies are didactic rather than large-scale benchmarks, emphasizing efficient deep exploration with generalization while noting computational costs and dependence on accurate linear bases in earlier methods.The neural-network experiments address these limitations with ensemble RLSVI and extend the investigation to nonlinear representations and continuous control.Source: §7 · p. 36, §7.2 · pp. 42–43

7.1 Deep-sea exploration

• Across deep-sea experiments, RLSVI verifies deep exploration where dithering requires exponentially many episodes, extending from tabular settings to representations that generalize across states and actions.The experiments focus on understanding how randomized value functions work rather than solving challenging problems.Source: §7.1 · p. 36, §7 · p. 36

7.1.1 Tabular representation

• In tabular deep-sea experiments, RLSVI is competitive with PSRL and UCRL2, ranking behind PSRL but ahead of UCRL2 in average regret.Observed learning-time scaling broadly matches the theoretical comparison, with approximately ˜O(N5) for RLSVI versus ˜O(N7) for UCRL2.Source: §7.1.1 · pp. 37–38, Figure 4 · p. 37, Figure 5 · p. 38

7.1.2 Linearly parameterized value functions

• For linearly parameterized deep-sea values, regret vanishes faster than dithering, learning time grows approximately quadratically with N, and added-feature costs become small beyond M = 2N.The representation uses row-local features so RLSVI can learn separate M-dimensional representations without inverting a full D-dimensional system.Source: §7.1.2 · pp. 38–39, Figure 7 · p. 39, Figure 8 · p. 40

7.1.3 Misspecified representations

• RLSVI remains robust to moderate representation misspecification, while larger feature sets tolerate greater noise and M ≥ 2N basis functions span the true value function with high probability.For M = 40 and N = 20, performance remains similarly good across misspecification levels.Source: §7.1.3 · p. 40, Figure 9 · p. 40

7.1.4 Parameter tuning

• Prior variance that is too small can prevent learning, while the best noise variance depends on environmental stochasticity and bootstrapping performs competitively without advance specification.In deterministic environments low v performs best; in stochastic environments v should match the environment’s noise scale, while overly small v can cause premature linear-regret convergence.Source: §7.1.4 · pp. 41–42, Figure 10 · p. 41, Figure 11 · p. 41

7.2.1 RLSVI via ensemble sampling

• With neural-network representations, ensemble RLSVI directs deep exploration using relatively small ensembles, exploits informative features, and reverts toward tabular learning when features provide no useful structure.For deep sea with N = 25, marginal benefits plateau around K = 20, while parallel computation is substantially cheaper than naive full resampling.Source: §7.2.1 · pp. 43–44, Figure 14 · p. 44, Figure 15 · p. 44

7.2.2 Cartpole swing up

• Ensemble RLSVI learns a successful cartpole swing-up policy, whereas epsilon-greedy DQN fails to gather informative data and linear or single-layer value functions also fail.The result demonstrates that both deep exploration and deep representation learning are important in this setting.Source: §7.2.2 · pp. 45–46, Figure 16 · p. 45, Figure 17 · p. 46

8. Closing remarks

• Statistical efficiency matters when data collection is costly or constrained by the physical context, motivating evaluation over a fixed number of episodes.Evaluating final policies after billions or trillions of simulated episodes can make performance depend heavily on computational resources and simulation time.Source: §8 · p. 46
• Deep exploration can require exponentially less data than dithering-based exploration, making exploration a key driver of statistical efficiency.The comparison is discussed in Section 4.Source: §8 · p. 46
• Randomized value functions enable efficient deep exploration in conjunction with commonly used reinforcement-learning value-function learning methods.The paper presents this concept as its central contribution to improving statistical efficiency.Source: §8 · p. 47

A.1 Proof of Lemma 1

• The lemma considers Q_0,Q_1,...,Q_H with Q_H=0 and the policy π_t(x)=arg max_a Q_t(x,a) in any MDP.The statement applies to every initial state x and defines the policy greedily at each time step.Source: §A.1 · p. 48
• The proof introduces the MDP- and time-indexed quantities used to analyze policy π at time t.Source: §A.1 · p. 48
• It uses the identity M,tQ_{t+1}=F_{M,t}Q_{t+1} for every t to rewrite equation (A.1).Source: §A.1 · p. 48
• The rewritten expression is converted into the defining relation for the quantities in the lemma.Source: §A.1 · p. 48
• Iterating this relation completes the proof.Source: §A.1 · p. 48

A.2 Proof of Lemma 2

• The lemma states that coordinatewise stochastic optimism is preserved under any convex increasing function for two collections of independent random variables.Source: §A.2 · p. 48
• The proof proceeds by induction on n, beginning with n = 1, where composition with a convex increasing function remains convex increasing.Source: §A.2 · p. 48
• For the inductive step, fixing one coordinate yields convex increasing functions whose expectations are ordered by the hypothesis applied to the remaining variables.The argument uses independence and the Fubini–Tonelli theorem for equalities, then applies the definition of stochastic optimism for the final inequality.Source: §A.2 · p. 49

A.3 Proof of Corollary 4

• The proof begins with a standard Gaussian maximum inequality for independent X0,...,Xn ∼N(0,1), bounding E[max_i X_i] by 2log(n + 1).Jensen’s inequality is then applied to this maximum-function bound.Source: §A.3 · p. 49
• For every state-action value function Q, the proof uses ∥VQ∥∞≤1 + ∥Q∥∞ to bound episode-period values.This step invokes equation 6.4.Source: §A.3 · p. 49
• Backward induction repeats the value bound across periods, after which equation (A.2) supplies the final step in the argument.The resulting inequalities are combined before parameter substitution.Source: §A.3 · p. 50
• The corollary follows by substituting β ≥3, v = 3H2, and ¯θ = H into the preceding bounds.These are the parameter values used when RLSVI is applied.Source: §A.3 · pp. 49–50

• The proof sets Y = {0,...,H −1} × X × A as the set of valid period, state, action triples.Source: §A.4 · p. 51
• Each element y ∈ Y is represented as a triple (t,x,a) consisting of a period, state, and action.Source: §A.4 · p. 51
• The set has cardinality ∣Y∣= H∣X∣∣A∣.Source: §A.4 · p. 51

Sufficient conditions for stochastic optimism

• Lemma 8’s new fourth condition gives stochastic optimism when E[X] ≥E[Y ] and {x ∈R ∶g(x) > f(x)} is convex.The section identifies this as easier to verify than the earlier condition (3.) and provides a detailed proof.Source: §A.5 · p. 52

Beta-Dirichlet optimism

• Lemma 9 addresses Beta-Dirichlet optimism for P ∼Dirichlet(α) and 0 = V1 ≤⋯≤Vn = 1, with X = Y + W and E[W ∣Y ] = 0.Source: §A.5 · pp. 53, 55

Gaussian-Beta optimism

• Lemma 10 shows that N(µ,σ) stochastically dominates Beta(α,β) when α + β ≥3, µ = α/(α + β), and σ2 = (α + β −2)−1.The proof verifies quasi-concavity of the Gaussian-to-Beta density ratio and applies Lemma 8’s fourth condition.Source: §A.5 · p. 55

Final proof

• The proof combines Lemmas 8–10 to establish Lemma 4’s stochastic-optimism bound for a Dirichlet inner product.Lemma 9 compares the Dirichlet inner product with a Beta variable, and Lemma 10 compares that Beta variable with a Gaussian variable.Source: §A.5 · p. 55