PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Exploration via Randomized Value Functions

Ian Osband, Benjamin Van Roy, Daniel Russo, Zheng Wen

arXiv:1703.07608v5stat.MLcs.AIcs.LG

TL;DR

Reinforcement learning needs exploration that is statistically efficient in costly, constrained environments while also generalizing across large state spaces. The paper uses randomized value functions to guide deep exploration, develops several algorithms, and reports computational and theoretical evidence, including a tabular Bayesian-regret bound.

  • Problem

    Real-world reinforcement learning requires statistically efficient exploration, while practical methods must also generalize across large state spaces.

  • Method

    The paper samples statistically plausible randomized value functions and uses them to guide deep exploration within practical value-function learning methods.

  • Results

    The paper establishes a strong Bayesian-regret bound for a tabular algorithm and reports efficiency gains in toy problems plus compatibility with linear and neural-network value functions.

  • Takeaways & Limitations

    Randomized value functions provide a practical approach to combining deep exploration with value-function generalization.

  • Takeaways & Limitations

    The empirical investigation is intentionally concise and focused on simple, interpretable results rather than large-scale applications.

Abstract

from arXiv · show

We study the use of randomized value functions to guide deep exploration in reinforcement learning. This offers an elegant means for synthesizing statistically and computationally efficient exploration with common practical approaches to value function learning. We present several reinforcement learning algorithms that leverage randomized value functions and demonstrate their efficacy through computational studies. We also prove a regret bound that establishes statistical efficiency with a tabular representation.

1. Introduction

The paper targets statistically efficient exploration for real-world reinforcement learning, where data is costly and state spaces are large. It proposes randomized value functions to support deep exploration while retaining practical value-function learning and reports theoretical and computational evidence.

  • Motivation: Real-world reinforcement learning requires statistical efficiency because data collection is costly or constrained, making exploration a key driver of performance.Simulated systems can generate millions to trillions of episodes, unlike many physical settings.
  • Motivation: Tabular exploration results have limited practical import because large state spaces make parameter and data requirements scale prohibitively with the number of states.The paper frames efficient exploration in generalizing value-function representations as an important unresolved challenge.
  • Existing exploration: Greedy policies neglect poorly understood actions with unattractive point estimates, even when those actions could be optimal and yield cumulative future benefits.This motivates exploration beyond exploitation of current value estimates.
  • Existing exploration: Dithering ignores value uncertainty and can waste effort on known-inferior actions, producing learning times that grow exponentially with the number of states.Myopic exploration improves on dithering in some cases but can also require exponential learning times or fail to learn.
  • Deep exploration: Deep exploration considers how actions affect future learning opportunities, including sequences of costly actions whose information arrives only after multiple periods.Dithering and myopic approaches do not pursue information strategically across time.
  • Proposed approach: Randomized value functions select actions greedily under sampled plausible value functions, turning uncertainty into variation that incentivizes experimentation.The paper presents algorithms, a tabular Bayesian-regret bound, and computational studies spanning toy examples and cart-pole balancing.

2. Literature review

Prior work established deep exploration and efficient tabular algorithms, but practical reinforcement learning also requires generalization across large state spaces. This paper develops randomized value functions as a general approach for combining efficient exploration with parameterized value-function learning.

  • Exploration foundations: Bayes-optimal exploration provides a statistical gold standard but is computationally intractable for practically interesting problems.Its computational requirements grow exponentially in problem complexity.
  • Tabular exploration: Tabular research established multi-period deep exploration and polynomial sub-optimality guarantees, whereas ϵ-greedy and Boltzmann exploration can require exponential learning times.These tabular results do not directly resolve the challenges of enormous practical state spaces.
  • Generalization: Practical reinforcement learning must generalize across states because curse-of-dimensionality effects make purely tabular algorithms of limited practical importance.Model-learning approaches often rely on restricted model classes or face statistical and computational limitations.
  • Generalization: Value-function generalization offers a practical route to efficient exploration, but whether the relevant KWIK online-regression problem can be solved efficiently was unknown.This motivates methods that operate directly through parameterized value functions.
  • Randomized value functions: RLSVI leverages randomized value functions to explore efficiently while generalizing through parameterized value functions.It is related to LSVI and SARSA but distinguishes itself through exploration based on randomized value samples.
  • Paper contribution: The paper develops a general template and several instantiations, evaluates them in new simulations including neural-network approximation, and provides a full regret-bound treatment.The stated goal is to synthesize efficient exploration and effective generalization.
  • Related approaches: Density-model exploration can perform well when its generalization aligns with the task, but its uncertainty bonuses are uncoupled across states and may reduce statistical efficiency.Randomized value functions instead target plausible optimal value functions, following the motivation of Thompson sampling.

3. Reinforcement learning problem

The paper models episodic interaction with an unknown finite-state, finite-action Markov decision process and defines policies, values, regret, and Bayesian regret over episode histories. It assumes termination occurs almost surely under every policy.

  • Environment model: The environment is a Markov decision process M = (S,A,R,P,ρ) with finite state and action spaces, reward and transition models, and an initial-state distribution.The agent interacts with the unknown environment over a sequence of episodes.
  • Episodic interaction: Each episode begins from ρ, selects actions from the available action space, generates rewards and transitions from the MDP, and continues until termination.The observation sequence records states, actions, rewards, and the random termination time.
  • Policies and algorithms: A policy maps states to probability distributions over actions, and the algorithm produces each episode’s policy from the state-action spaces and previous observation history.The algorithm itself may be randomized, so repeated applications can yield different policies.
  • Assumption: The framework assumes that the MDP terminates almost surely in finite time under every policy.Equivalently, the policy-induced transition process satisfies the stated limiting condition.
  • Performance criteria: Regret compares optimal expected value with the algorithm’s expected value across episodes, while Bayesian regret averages over a prior distribution on MDPs.These measures quantify how quickly average regret should diminish for reasonable algorithms.

4. Deep exploration

Deep exploration accounts for how actions shape future learning opportunities, not merely immediate information gain. In the deep-sea example, randomized and optimistic approaches learn efficiently while exploitation, dithering, and myopic exploration can require exponentially many episodes.

  • Deep exploration: Deep exploration considers how an action positions the agent to acquire information over subsequent time periods.It may accept losses across multiple actions when informative observations arrive only later.
  • Deep-sea example: The deep-sea example uses an N × N grid with unknown action associations and an unknown treasure-or-bomb reward at the chest.Action associations are independently uncertain across states, while the chest contains treasure or a bomb with equal prior probability.
  • Deep-sea example: A uniformly random policy reaches the chest with probability (1/2)^N per episode, requiring 2^N expected episodes to observe its content.For N = 50, this exceeds a quintillion episodes.
  • Baseline methods: Pure exploitation avoids the costly path toward the chest because its expected reward is zero, making it unlikely to learn an optimal policy.The algorithm follows a best-guess MDP based on rewards and transitions conditioned on observed data.
  • Randomized exploration: Randomized value estimates extend Thompson sampling to complex reinforcement-learning problems where optimistic deep exploration may not be computationally tractable.In the example, randomized estimates explore similarly to optimism on average and can learn the optimal policy within 2N episodes.
  • Comparison: Θ(N) episodes suffice for the optimal known-action strategy, while pure exploitation and myopic exploration require Θ(2^N) episodes; optimistic and randomized methods require Θ(N).Dithering also fails to improve the deep-sea problem because it does not write off known-inferior actions.

5. Algorithms

The paper develops randomized value-function methods that make deep exploration computationally tractable while retaining value-function generalization. Its algorithms include RLSVI, Gaussian-noise and bootstrap variants, ensemble sampling, and incremental learning, supported by regret analysis and computational results.

  • Randomized value functions: Randomized least-squares value iteration (RLSVI) injects randomness into LSVI to provide a computationally tractable means to deep exploration.RLSVI is modeled after Thompson sampling but samples value functions without explicitly maintaining belief distributions.
  • Value-function learning: LSVI supports generalization and computational tractability by scaling with parameter dimension and historical observations rather than the number of states.Less flexible parameterizations can both generalize across states and avoid the intractable state-space scaling of value iteration.
  • Theoretical analysis: RLSVI with Gaussian data randomization and a random prior recovers a polynomial regret bound with linear value functions and tabular representation.The paper contrasts this result with LSVI combined with dithering, which cannot recover such a bound.
  • Randomized value functions: Greedy actions under randomly drawn statistically plausible value functions explore actions whose uncertain values produce high variance and positive bias.The resulting uncertainty can propagate across multiple time periods, incentivizing information-seeking actions that enable deep exploration.
  • Practical variants: The paper combines RLSVI with practical variants including ensemble sampling, incremental temporal-difference learning, and bootstrap randomization.Ensemble sampling maintains K perturbed value estimates in parallel, while bootstrap randomization can induce state-dependent and heteroskedastic variation.

6. Regret bound

The paper proves a polynomial Bayesian-regret bound for tabular RLSVI in finite-horizon time-inhomogeneous MDPs under an independent Dirichlet prior. The analysis links stochastic optimism and on-policy Bellman error to near-optimal decision-making with fewer samples than transition-model learning requires.

  • Scope: The result establishes statistical efficiency in a tabular setting while extending the randomized-value-function approach toward parameterized-value-function generalization.The paper identifies this combination as distinct from previous algorithms with comparable tabular regret guarantees.
  • Theorem 1: RLSVI receives a polynomial Bayesian-regret bound for tabular representations under an independent Dirichlet prior.The theorem assumes an infinite buffer, greedy actions, Gaussian-noise updates, β ≥ 3, and parameters v = 3H^2, θ̄ = H^1, and v/λ = β.
  • Regret scaling: For constant β, the regret bound scales as ˜O(H^2√(|X||A|L)) up to poly-logarithmic factors.Here |S| = |X|H and T = LH in the finite-horizon construction.
  • Interpretation: RLSVI needs a number of episodes linear in the number of states to reach near-optimal performance.The paper states that cumulative Bayesian regret below Lϵ is achievable when L scales with |X|/ϵ^2.
  • Proof strategy: The analysis treats RLSVI as a stochastic Bellman recursion whose Gaussian update noise produces stochastic optimism in the sampled state-action values.The proof bounds cumulative regret through on-policy Bellman error across episodes.

7. Computational studies

The computational studies evaluate randomized value functions across tabular, linear, misspecified, and neural representations. Results indicate efficient deep exploration, graceful scaling, robustness under moderate misspecification, and successful neural-network generalization, while experiments remain deliberately simple and interpretable.

  • 7.1.1 Tabular representation: RLSVI is competitive with UCRL2 and PSRL in tabular exploration, with PSRL lowest regret, followed by RLSVI and UCRL2.Figure 4 averages regret over five seeds with a bomb and five with treasure.
  • 7.1.1 Tabular representation: Learning times scale as ˜O(N5) for RLSVI and ˜O(N7) for UCRL2, while observed performance broadly matches these theoretical results.The associated plot also strengthens the hypothesis that the known PSRL bound ˜O(N5) is loose.
  • 7.1.2 Linearly parameterized value functions: Per-episode regret vanishes much faster than any dithering method, which would require at least 250 ≃1015 episodes to reach the chest.
  • 7.1.2 Linearly parameterized value functions: Learning time grows sub-exponentially with chain length N and approximately quadratically in N.The log-log slope is approximately two, whereas dithering has a lower bound of O(2N).
  • 7.1.2 Linearly parameterized value functions: Learning time grows linearly with features M up to a threshold near M = 2N, after which additional features add little incremental time.Beyond the threshold, additional features must be linearly dependent.
  • 7.1.3 Misspecified representations: RLSVI remains robust to some misspecification, with larger feature representations tolerating larger noise scales ψ.For M ≥2N, random basis functions span the true value function with high probability; M = 40,N = 20 performs similarly across ψ.
  • 7.1.4 Parameter tuning: Bootstrapping adapts the noise variance and its variation across states and actions, with learning-time scaling similar to randomized least-squares value iteration.
  • 7.2 Deep exploration with deep learning: Ensemble RLSVI combines deep exploration with neural-network generalization, while DQN dithering fails to gather informative data and linear or single-layer Q-functions fail on swing-up.RLSVI learns a successful swing-up policy with the same network architecture as DQN.

8. Closing remarks

Real-world reinforcement learning motivates statistical efficiency because data collection is costly or physically constrained. The paper presents randomized value functions as a way to combine efficient deep exploration with commonly used value-function learning.

  • Data collection in real systems is costly or constrained by physical context, motivating a focus on statistical efficiency.
  • Exploration is a key driver of statistical efficiency, with deep exploration potentially requiring exponentially fewer data than dithering.
  • Randomized value functions enable efficient deep exploration in conjunction with commonly used value-function learning methods.

A.1 Proof of Lemma 1

The proof establishes the planning-error-to-Bellman-error relationship for greedy policies induced by a sequence of value functions. It then obtains the result by iterating that relation.

  • For any value-function sequence ending with QH = 0, the policy selects at each state the action maximizing the corresponding Qt.
  • The proof rewrites the relevant relation using M,tQt+1 = FM,tQt+1 for every time t.
  • The lemma follows by iterating the rewritten relation.

A.2 Proof of Lemma 2

The proof shows that stochastic optimism is preserved when independent random variables are combined through convex increasing functions. It proceeds by induction on the number of variables.

  • If each Xi stochastically dominates Yi and the variables are independent, convex increasing transformations preserve the comparison.
  • The base case fixes a convex increasing univariate function and observes that its composition remains convex increasing.
  • The induction step defines UX and UY by conditioning on the first variable while applying the induction hypothesis to the remaining variables.The construction uses UY(z) ≡ E[u(f(z,Y2,...,Yn))].
  • Independence and the Fubini–Tonelli theorem justify the first and last equalities, while the final inequality follows from stochastic optimism.

A.3 Proof of Corollary 4

The corollary proof bounds the randomized value-function quantities using Gaussian maxima, value-function norms, and backward induction, then substitutes the stated parameter choices.

  • Gaussian maximum inequalities and Jensen’s inequality initiate the bound on independent standard-normal variables.The proof applies a standard Gaussian maximum inequality before using Jensen’s inequality.
  • The value-function norm is controlled by ∥VQ∥∞ ≤ 1 + ∥Q∥∞ for every state-action value function Q.
  • Backward induction repeats the bound across periods and episodes.
  • Substituting β ≥ 3, v = 3H^2, and θ̄ = H yields the stated result.

A.4 Proof of Lemma 7

The proof defines the set of valid period, state, and action triples and counts its cardinality.

  • The proof sets Y = {0,...,H − 1} × X × A as the valid period-state-action triple set.
  • Each element y ∈ Y is a triple y = (t,x,a) containing a period, state, and action.
  • The set has cardinality |Y| = H|X||A|.

A.5 Proof of Lemma 4

The proof establishes Lemma 4 by deriving sufficient conditions for stochastic optimism, comparing Dirichlet and Beta variables, and then comparing Beta and Gaussian variables. These comparisons produce a Gaussian upper bound for the Dirichlet inner product.

  • Sufficient conditions for stochastic optimism: Condition (4) is presented as a new, easier-to-verify sufficient condition for stochastic optimism.The paper contrasts it with earlier conditions, including a consequence known since Hanoch and Levy (1969).
  • Sufficient conditions for stochastic optimism: Lemma 8 lists sufficient conditions under which one integrable random variable stochastically optimistically dominates another.One condition constructs coupled variables with X̃ = Ỹ + W̃ and nonnegative conditional expected increment.
  • Distributional comparisons: The proof uses Gamma-variable ratios to relate Dirichlet and Beta distributions, then applies Lemmas 9 and 10 to compare them with a Gaussian.Lemma 9 compares P^T V with a matched Beta variable, while Lemma 10 gives a Gaussian-Beta optimism relation.
  • Final bound: The proof’s stochastic-optimism criterion is illustrated using distributions such as Beta(3,2) and N(3/5,1/3).Figure 18 compares these distributions and marks the boundaries of set C.
  • Distributional comparisons: For the normalized vector V′, the proof obtains P^T V′ ⪯SO X ⪯SO Z through successive stochastic-optimism comparisons.
Loading 1703.07608v5…