PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalization and Exploration via Randomized Value Functions

Ian Osband, Benjamin Van Roy, Zheng Wen

arXiv:1402.0635v3stat.MLcs.AIcs.LGeess.SY

TL;DR

Reinforcement learning needs exploration that remains efficient in large state-action spaces while still generalizing through value functions. The paper proposes RLSVI, which samples plausible linearly parameterized value functions for exploration, and reports dramatic efficiency gains plus a near-optimal tabula rasa regret bound. Its broader conclusion is that randomized value functions are a promising way to combine efficient exploration with effective generalization.

  • Problem

    Efficiently exploring large state-action spaces while generalizing through value functions remains an important reinforcement-learning challenge.

  • Method

    RLSVI combines linearly parameterized value-function generalization with exploration by sampling statistically plausible value functions and acting greedily.

  • Results

    RLSVI shows dramatic computational efficiency gains and a tabula rasa expected-regret bound matching the corresponding worst-case lower bound up to logarithmic factors.

  • Takeaways & Limitations

    Randomized value functions are presented as a promising approach to synthesizing efficient exploration and effective generalization in reinforcement learning.

  • Takeaways & Limitations

    The recommendation-system simulations use an extremely simplified model, limiting the scope of that application evidence.

Abstract

from arXiv · show

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.

1. Introduction

RLSVI addresses inefficient exploration in large state-action spaces by combining linearly parameterized value-function generalization with randomized exploration. The paper presents computational efficiency gains and a regret bound for tabula rasa learning.

  • RLSVI targets efficient exploration and generalization in large state-action spaces using linearly parameterized value functions.
  • Prior value-function approaches can require learning times exponential in the number of model parameters and/or planning horizon.
  • RLSVI samples statistically plausible value functions, unlike Boltzmann or epsilon-greedy action dithering used by related methods.
  • The paper frames randomized value functions as a promising approach to synthesizing efficient exploration with effective generalization.
  • Computational results show dramatic efficiency gains, while the expected-regret bound matches the tabula rasa lower bound up to logarithmic factors.
  • The paper reports RLSVI as the first algorithm that is provably efficient in tabula rasa learning while also demonstrating efficiency with linearly parameterized value-function generalization.

2. Episodic reinforcement learning

The paper formulates episodic reinforcement learning with finite-horizon MDPs, policies, value functions, and cumulative regret. It also distinguishes coherent learning, where the agent’s belief is correct, from agnostic learning.

  • A finite-horizon MDP specifies finite states and actions, episode duration H, transitions P, rewards R, and an initial-state distribution pi.
  • Each episode begins by sampling an initial state, then proceeds through H periods of state transitions and rewards before a terminal reward.
  • A policy is a sequence of functions mapping states to actions at each period.
  • The optimal value function and optimal policy characterize the highest achievable value from each state.
  • Expected cumulative regret measures performance over L episodes, equivalently over elapsed time T=LH.
  • Coherent learning means the agent’s belief is correct, whereas agnostic learning refers to the alternative setting.

3. The problem with dithering for exploration

Action dithering can explore inefficiently because it does not consistently direct exploration toward informative state-action pairs. In a simple chain, LSVI with epsilon-greedy or Boltzmann exploration needs exponentially many episodes to learn the optimal policy.

  • LSVI combined with epsilon-greedy or Boltzmann exploration uses random action dithering to select actions.
  • Efficient exploration must target potentially informative state-action pairs consistently across multiple timesteps, whereas dithering can yield regret exponential in H and/or S.
  • In the chain example, dithering-based LSVI requires exponentially many episodes to learn an optimal policy even with few basis functions and coherent learning.
  • The chain has left and right actions, with right succeeding probabilistically and reward available only at the far-right state.
  • For any basis function, LSVI with epsilon-greedy or Boltzmann exploration incurs regret that grows exponentially in S.
  • 2^(S−1)−1 is a lower bound on the expected first visit episode and asymptotic regret in the chain example.

4. Randomized value functions

RLSVI explores by sampling randomized value functions and then acting greedily with respect to the sampled functions. Its implementation uses Bayesian linear regression and Gaussian posterior sampling within least-squares value iteration.

  • RLSVI replaces random action selection with random sampling of value functions for exploration.
  • The resulting sampled value functions are used to select greedy actions during each episode.
  • The algorithm samples a value function distribution viewed as an approximation to a posterior over plausible value functions, drawing inspiration from Thompson sampling.
  • RLSVI produces episode-specific value-function parameters through Bayesian linear regression.
  • At each period, it samples parameters from a Gaussian posterior over the regression parameters.
  • The algorithm repeats this process over episodes while observing states, actions, rewards, and successor states as data.

5. Provably efficient tabular learning

The section establishes that RLSVI can achieve provable efficiency in tabular learning through stochastic optimism and concentration of randomized value estimates. Under specified prior and parameter conditions, its regret scaling is competitive with optimistic algorithms and contrasts with inefficient dithering methods.

  • Setting: RLSVI is analyzed in a tabular setting with identity basis functions, addressing the absence of analytical regret bounds for linear value-function generalization in large MDPs.The analysis assumes Φ_h = I, so it does not establish the generalization result in the broader linear setting.
  • Assumptions: The tabular analysis assumes deterministic state, action, horizon, and policy spaces, with rewards and transitions drawn from Dirichlet prior distributions.Rewards use values on {−1, 0}; the passage notes that similar results can extend to general bounded distributions.
  • Regret guarantee: RLSVI’s regret scaling is surprising because it matches the order admitted by state-of-the-art optimistic algorithms and is provably efficient unlike epsilon-greedy dithering.The theorem requires identity features and parameter choices including λ exceeding the reward-prior mass and σ² at least H² + 1.
  • Regret analysis: The regret proof decomposes error into optimism and concentration terms, with the optimism term having nonpositive conditional expectation and the concentration term diminishing.The analysis represents transition noise using samples and martingale differences, then bounds the resulting estimation error.
  • Stochastic optimism: The proof establishes stochastic optimism: conditional on any history, RLSVI-generated Q-values are stochastically optimistic for the true Q-values.The argument proceeds by backward induction over timesteps and uses a relation between Gaussian and Dirichlet random variables.
  • Concentration: Gaussian perturbations decrease as observations accumulate, allowing concentration errors to vanish as the value estimates gather data.The concentration analysis also accounts for optimistic bias caused by shrinking estimates toward zero rather than the Dirichlet prior.

6. Experiments

The experiments evaluate RLSVI’s ability to combine exploration with linear value-function generalization across coherent and agnostic environments, Tetris, and recommendation systems. Across these settings, RLSVI learns efficiently, scales favorably, and can outperform dithering and myopic baselines.

  • Experimental scope: RLSVI’s tabular-basis analysis motivates randomized value functions as an approximation to PSRL, while the experiments target larger systems requiring generalization.The paper presents experiments to test applicability and scalability beyond tabular environments.
  • Experimental scope: The experiments cover coherent and agnostic chain environments, Tetris, and a recommendation-system model, comparing RLSVI with dithering and bandit approaches.The study examines exploration, scaling, model misspecification, gameplay, and sequential recommendation decisions.
  • Coherent learning: RLSVI consistently learns the optimal policy in roughly 500 episodes, whereas dithering requires at least 10^15 episodes in the motivating example.The comparison highlights the benefit of exploiting generalization and prior structure in the basis functions.
  • Coherent learning: For chain length N=100, the dithering lower bound exceeds 10^28 and H^2SA exceeds 10^6, while RLSVI outperforms these bounds and scales gracefully with N.Learning time is measured by the episodes needed to obtain 10 rewards, averaged over five random seeds.
  • Coherent learning: Learning time scales gracefully with the number of basis functions K, with diminishing marginal effects as the feature span approaches the full state-action space.The observed scalings are consistent with polynomial learning and remain robust across several orders of magnitude in σ and λ.
  • Agnostic learning: Under basis misspecification, RLSVI is ineffective for large noise but remains remarkably stable over some region 0 < ρ < ρ∗.The agnostic experiment varies ρ from 0 to 1 while measuring episodes until 10 rewards.
  • Tetris: In Tetris, RLSVI and LSVI reach higher final performance than LSPI’s best level of 3183, with reported values of approximately 3500 and 4500 respectively.Both methods also learn from scratch, and RLSVI improves exploration relative to tuned epsilon-greedy LSVI.
  • Recommendation engine: RLSVI explores more efficiently than Boltzmann exploration and eventually outperforms the optimal myopic policy in the recommendation-system model.The linear contextual bandit performs better initially, but RLSVI learns a richer multi-period policy as more data arrives.

7. Closing remarks

RLSVI combines a tabular regret guarantee with a broader proposal to use randomized value functions for exploration alongside nonlinear generalization. The authors view this approach as promising beyond the specific linear implementation.

  • 7. Closing remarks: RLSVI has a regret bound affirming efficiency in tabula rasa learning, while its broader promise concerns exploration in large-scale environments with generalization.The authors describe RLSVI as simple, practical, and effective in several environments where state-of-the-art approaches are ineffective.
  • 7. Closing remarks: Randomized value-function exploration is presented as a concept that may extend beyond RLSVI and linearly parameterized value functions.The paper suggests that insights from RLSVI may remain useful with highly nonlinear deep neural networks.
  • 7. Closing remarks: The optimal myopic policy knows the true model but does not plan over multiple timesteps.
  • 7. Closing remarks: Recent work has reproduced similar performance using linear value functions.

APPENDICES

The appendices specify LSVI and its action-selection variants. LSVI fits value functions by backward least-squares regression, while Boltzmann and epsilon-greedy versions add distinct randomization schemes.

  • APPENDICES: LSVI iterates backward through the planning horizon, fitting each value function to immediate rewards plus next-period value estimates by least squares.
  • APPENDICES: At the first episode, LSVI sets all value-function parameters to zero because its regression matrix and vector are empty.
  • APPENDICES: Algorithm 3 takes episodic feature and reward data plus λ as input and outputs value-function parameters for each time period.
  • APPENDICES: The least-squares subroutine performs linear regression for the value function during each backward iteration.
  • APPENDICES: Boltzmann and epsilon-greedy exploration combine LSVI with action randomization controlled by temperature η or exploration probability ϵ.
  • APPENDICES: The Boltzmann variant samples actions according to exponentiated estimated values, whereas epsilon-greedy chooses a uniformly random action with probability ϵ and otherwise acts greedily.

B. Efficient exploration with generalization

The paper presents a conjectured generalization guarantee for RLSVI and emphasizes that its complexity depends on basis functions rather than the sizes of the state and action spaces. Supporting experiments are described as consistent with this conjecture.

  • B. Efficient exploration with generalization: RLSVI’s computational results suggest efficiency far beyond LSVI combined with Boltzmann or epsilon-greedy exploration, but guarantees in generalized settings remain open.The authors formulate a conjecture to stimulate progress on these guarantees.
  • B. Efficient exploration with generalization: Conjecture 1 posits a unique linear representation of the optimal value function under bounded rewards and specified model, feature, σ, and λ conditions.
  • B. Efficient exploration with generalization: The conjectured bound depends on the number of basis functions rather than the number of states or actions.
  • B. Efficient exploration with generalization: The appendix reports empirical results consistent with the conjecture and describes graceful scaling with the number of basis functions.
  • B. Efficient exploration with generalization: The random basis functions are rescaled to match the scale of Q*, although the scaling choice is arbitrary because equivalent changes can be made to λ and σ.

C.2. Robustness to λ, σ

RLSVI remains stable across many λ and σ settings, but exploration and learning speed depend on σ. Experiments also indicate polynomial scaling with problem size and basis dimension, with diminishing marginal cost near the maximum problem dimension.

  • C.2. Robustness to λ, σ: For N = 50 and K = 10, cumulative-regret experiments over 10000 episodes found remarkably stable learning for most tested σ and λ combinations.
  • C.2. Robustness to λ, σ: Figure 10 fixes σ = 0.1 while varying λ.
  • C.2. Robustness to λ, σ: Large σ slows learning because the Bayesian posterior concentrates slowly, while excessively small σ can concentrate too quickly and impair exploration in stochastic domains.
  • C.3. Scaling with number of bases K: Figure 12 examines graceful scaling with the number of basis functions, and Figure 13 repeats this analysis across chains of different lengths.
  • C.3. Scaling with number of bases K: For low K, the episodes required until learning appears to increase linearly with K, while marginal increases decrease and nearly plateau once K ≥ SA.
  • C.3. Scaling with number of bases K: Simulation results suggest learning is polynomial in both chain length N and basis count K, supported by separate quadratic regression fits for each K.

D.1. Algorithm specification

RLSVI adapts least-squares value iteration by using Bayesian linear regression and randomized value-function estimates, with greedy action selection. In mini-Tetris, it learns faster and achieves a higher convergent policy than tuned LSVI with dithering.

  • Algorithm specification: The Tetris implementation uses an episodic RLSVI adaptation without known episode length, with LSVI formed analogously.This version was used in the Tetris experiments.
  • Algorithm specification: RLSVI uses Bayesian linear regression to estimate a value function and selects actions greedily from randomized estimates.The stationary version approximates a time-homogeneous value function; γ = 0.99 was helpful for stability in both RLSVI and LSVI.
  • Implementation: The implementation limits stored data to the most recent N = 10^5 transitions, while computation remains negligible relative to running the Tetris simulator.The stated memory requirement could fit 10^5 transitions for every possible action in less than 10 MB.
  • Implementation: RLSVI uses fixed σ = 1 and λ = 1 in the reported experiments, although an inverse-gamma variance prior produced slightly better performance with minor improvements.The authors suggest a wider variance prior may be more robust than selecting specific σ and λ values.
  • Mini-Tetris: In four-row mini-Tetris with only S and Z pieces, RLSVI greatly outperforms LSVI with a tuned ϵ schedule, learning faster and reaching a higher convergent policy.The environment is described as more difficult and as emphasizing the need for efficient exploration.

E.1. Experiment Setup

The experiments compare randomized value-function exploration with bandit and action-dithering baselines across recommendation-system and continual-learning settings. The supplied setup also introduces incremental and discounted infinite-horizon RLSVI extensions and supporting stochastic-optimism results.

  • Recommendation-system setup: Recommendation-system experiments use N = 10, J = H = 5, c = 2, and L = 1200.The setup specifies repeated Bernoulli-bandit, linear-contextual-bandit, LSVI-Boltzmann, and RLSVI runs.
  • Recommendation-system setup: The recommendation experiments average regret across 100 Bernoulli-bandit runs, 100 linear-contextual-bandit runs, and ten runs for each LSVI-Boltzmann and RLSVI configuration.LSVI-Boltzmann uses λ = 0.2, while RLSVI uses λ = 0.2 and σ² = 10^-3.
  • Baselines: The Bernoulli bandit samples product probabilities from beta posteriors, ranks them, and recommends the first J products.Its uniform prior initializes α_n = β_n = 1.
  • Baselines: The linear contextual bandit resembles RLSVI but omits backward value propagation, thereby targeting the myopic policy while remaining incrementally implementable.Its parameters are estimated through backward regression over periods.
  • Incremental learning: The batch RLSVI algorithm requires all past observations for each episode, so its per-episode computation grows with episode index.An incremental variant instead updates from summary statistics and recent observations, making per-episode computation episode-independent.
  • Continual learning: A continual RLSVI extension targets infinite-horizon time-invariant discounted MDPs and uses autocorrelated perturbations so consecutive perturbations change gradually.The gradual changes support multi-period plans toward poorly understood state-action pairs.
  • Stochastic optimism: The theoretical development establishes stochastic-optimism relationships linking Gaussian, Beta, and Dirichlet random variables through dominance and matched conditional means.The proof combines a Beta-versus-Dirichlet result with Gaussian-versus-Beta dominance.

G.3.1. SPECIAL CASE α > 1, β ≤1

This section proves Gaussian-versus-Beta dominance in the remaining parameter regions using calculus, convexity, and bounds on log-likelihood differences. The argument concludes with positive lower bounds that establish the required crossing behavior.

  • Completion: The cases with α ≤ 1, β > 1 follow by a similar argument, while the final dominance proof combines the Gaussian-versus-Beta result with the Beta-versus-Dirichlet lemma.The authors note that a more elegant general proof method may exist.
  • Convex-function case: For α, β > 1, the proof uses convexity of the log-likelihood difference and evaluates it at its stationary point.The case is organized around the region (α − 1)(β − 1) ≥ 1.
  • Special case: The remaining region requires bounding the Beta normalizing constant and comparing the Beta log-likelihood with the maximum normal log-likelihood.The argument uses auxiliary functions and convexity to control possible crossings.
  • Special case: The proof reduces the crossing analysis to checking positivity at selected points and uses monotonicity over the extremal boundary.It examines functions f_i and g_i after parameterizing the boundary by B = 1/9A.
  • Special case: The auxiliary lower bounds satisfy g_1(A) ≥ 0.01 and g_2(A) > 0.01, completing the double-crossing argument in this region.Both bounds are obtained by monotonicity and evaluation at A = 1/3.
Loading 1402.0635v3…