PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Exploration through Bayesian Deep Q-Networks

Kamyar Azizzadenesheli, Animashree Anandkumar

arXiv:1802.04412v4cs.AIcs.LGstat.ML

TL;DR

The paper studies efficient exploration in high-dimensional episodic RL when optimal Q-functions are linear in state-action features. It develops LINPSRL and LINUCB, then extends their Bayesian approximation to BDQN, which uses Bayesian last-layer regression and Thompson sampling. On Atari, BDQN reaches DDQN performance faster and reports substantially higher cumulative rewards, while the theoretical regret bounds have unfavorable dependence on episode length.

  • Problem

    High-dimensional RL requires exploration methods that use uncertainty, but posterior computation and planning can become intractable as problem dimension grows.

  • Method

    The paper proposes LINPSRL and LINUCB for linear-Q episodic MDPs, then extends them to BDQN by replacing DDQN's last-layer linear regression with Bayesian linear regression and Thompson sampling.

  • Results

    BDQN reaches DDQN performance in less than 5M±1M interactions for almost half of Atari games and improves cumulative reward by a median of 300% across all games.

  • Takeaways & Limitations

    Bayesian uncertainty over the Q-function supports efficient exploration in deep RL while requiring only a simple modification to DDQN.

  • Takeaways & Limitations

    The regret upper bounds have bad dependence on the horizon length H, and the authors plan to develop tighter bounds.

Abstract

from arXiv · show

We study reinforcement learning (RL) in high dimensional episodic Markov decision processes (MDP). We consider value-based RL when the optimal Q-value is a linear function of d-dimensional state-action feature representation. For instance, in deep-Q networks (DQN), the Q-value is a linear function of the feature representation layer (output layer). We propose two algorithms, one based on optimism, LINUCB, and another based on posterior sampling, LINPSRL. We guarantee frequentist and Bayesian regret upper bounds of O(d sqrt{T}) for these two algorithms, where T is the number of episodes. We extend these methods to deep RL and propose Bayesian deep Q-networks (BDQN), which uses an efficient Thompson sampling algorithm for high dimensional RL. We deploy the double DQN (DDQN) approach, and instead of learning the last layer of Q-network using linear regression, we use Bayesian linear regression, resulting in an approximated posterior over Q-function. This allows us to directly incorporate the uncertainty over the Q-function and deploy Thompson sampling on the learned posterior distribution resulting in efficient exploration/exploitation trade-off. We empirically study the behavior of BDQN on a wide range of Atari games. Since BDQN carries out more efficient exploration and exploitation, it is able to reach higher return substantially faster compared to DDQN.

1 Introduction

The paper addresses inefficient uncertainty-aware exploration in high-dimensional RL by extending linear-MDP methods into practical deep RL. Its BDQN algorithm uses Bayesian last-layer learning and Thompson sampling, achieving faster Atari performance than DDQN with modest computational changes.

  • Motivation: High-dimensional RL needs exploration methods that account for Q-value uncertainty, whereas ε-greedy and Boltzmann strategies do not fully exploit it.These strategies either randomize actions or use estimated returns without incorporating uncertainty in the estimates.
  • Motivation: Thompson sampling offers uncertainty-guided exploration, but posterior computation and planning can become intractable as problem dimension grows.Prior work addressed this bottleneck in tabular MDPs with linear Q-functions and Bayesian linear regression.
  • Theory: LINPSRL and LINUCB extend posterior-sampling and optimism methods to episodic MDPs whose optimal Q-function is linear in d-dimensional state-action features.LINPSRL samples a posterior model each episode, while LINUCB acts optimistically using an upper confidence bound.
  • Method: A Bayesian linear-regression approximation unifies the practical versions of LINPSRL and LINUCB into the same Gaussian distribution, enabling Thompson sampling for deep RL.The authors use this approximation because exact posterior maintenance can be impractical in high-dimensional settings.
  • Method: BDQN modifies DDQN mainly by replacing last-layer linear regression with Bayesian linear regression and sampling from the resulting Q-function posterior.This requires no backpropagation in the last layer and instead periodically inverts a 512 × 512 matrix, taking less than a second.
  • Empirical results: BDQN reached DDQN performance in less than 5M±1M interactions for almost half of Atari games, with median cumulative-reward improvement of 300%.Across all games, the maximum reported cumulative-reward improvement was 80K%, and area-under-performance improved by 300% ± 40%.

2 Linear Q-function

The paper studies episodic MDPs whose optimal Q-function is linear in state-action features, developing Bayesian and frequentist algorithms with regret guarantees. It also analyzes practical posterior and confidence-set approximations for high-dimensional reinforcement learning.

  • Linear Q-function: The optimal Q-function is assumed linear in a d-dimensional state-action feature representation.The representation uses φ(x_h,a_h)^⊤ω*_h, with the optimal policy selecting the action maximizing this function.
  • Algorithms: LINPSRL samples Q-function parameters from a posterior at each episode and acts optimally under the sampled model.LINUCB instead estimates the parameters within high-probability confidence sets.
  • Regret analysis: LINUCB and LINPSRL use confidence or posterior updates to reduce parameter uncertainty and per-step regret as samples accumulate.The analysis relates shrinking confidence sets to more accurate parameter estimation.
  • Assumptions: The framework assumes sub-Gaussian noise, bounded parameters and features, and expected rewards and returns in [0, 1].These conditions support the regression and regret analyses.
  • Regret guarantees: Theorem 1 and Theorem 2 provide Bayesian and frequentist regret upper bounds for LINPSRL and LINUCB, respectively.The bounds apply to episodic MDPs with horizon H, discount factor γ, and d-dimensional feature maps.
  • Limitations: The regret bounds are order-optimal in T and d but have a poor dependence on horizon length H.The authors identify tighter horizon-dependent bounds as future work.

3 Bayesian Deep Q-Networks

BDQN extends DDQN by replacing last-layer linear regression with Bayesian linear regression, producing an approximate Q-function posterior for Thompson-sampling exploration. The method retains the DDQN architecture while incorporating uncertainty into action selection.

  • Linear representation: DDQN represents each Q-value as a linear function of the neural network’s feature representation in its output layer.For action a, Q(x,a)=φ_θ(x)^⊤w_a, with separate target-network features and weights.
  • Bayesian last layer: BDQN follows DDQN except that Bayesian linear regression replaces last-layer linear regression.This produces an approximate posterior over the last-layer weights and consequently over the Q-function.
  • Posterior construction: For each action, BDQN constructs a dataset from replay experiences and approximates the posterior distribution of that action’s weights.The construction uses action-specific feature matrices and target values.
  • Posterior construction: The Bayesian linear regression posterior is characterized by a mean and covariance for each action’s weights.The paper identifies the prior and likelihood variances as σ and σ_ε, respectively.
  • Implementation: BDQN initializes the online and target networks, action weights, and posterior covariances before using replay-buffer training.The implementation retains DDQN-style target-network and replay-buffer components.
  • Thompson sampling: BDQN uses Thompson sampling on approximate posteriors to balance exploration and exploitation.Posterior sampling is performed every T_S while posterior updates occur every T_BT.

4 Experiments

The experiments evaluate BDQN against DDQN and other reported methods on Atari, emphasizing sample complexity, scores, and exploration behavior. BDQN reaches strong performance with fewer interactions, though comparisons across methods involve implementation and evaluation differences.

  • Experimental setup: BDQN and DDQN were evaluated on Atari games using sample complexity and score measures.The study followed the DDQN implementation and used publicly available code.
  • Evaluation caveats: Table 2 compares scores and sample complexities, but its methods use differing sources, evaluation procedures, and implementation details.The paper cautions that Table 2 is not intended as a direct comparison among all methods.
  • Results: BDQN’s dropout-based Thompson Sampling variant failed to capture statistical uncertainty and performed below a random policy.The authors attribute this to dropout models being nearly identical in the cited analysis.
  • Exploration behavior: BDQN assigns less exploration priority to actions already judged unworthy, improving sample complexity and preserving model capacity for important actions.The paper links this behavior to better policies and higher scores.
  • Results: In Atlantis, BDQN reached 3.24M after 20M steps versus DDQN+ at 64.67k, then reached 62M after removing the episode-length limit.The reported 3.24M result was constrained by the internal OpenAI Gym max_episode limit.

5 Related Work

Related work addresses exploration in high-dimensional RL through optimism, ensembles, variational methods, noisy networks, and linear value-function approaches. The paper distinguishes its Bayesian regression approach by linking explicit value-function uncertainty to improved Atari performance.

  • Linear RL: Linear RL extends linear-bandit ideas to episodic MDPs, with both optimism and Thompson sampling providing results for high-dimensional problems.The paper positions its LinReL development as an extension from linear bandits to MDPs.
  • Motivation: Deep RL successes in Atari, Go, robotics, and autonomous driving motivate exploration methods for high-dimensional environments.The cited literature presents these domains as promising applications of deep RL.
  • High-dimensional exploration: Prior work applies optimism, bootstrapped ensembles, variational approximations, and noisy networks to exploration in high-dimensional RL.These methods approximate posterior uncertainty or optimism in different ways.
  • Comparison with related methods: Compared with least-squares temporal difference learning, BDQN outperformed a common Atari game by 360% relative to the score reported in that work.The authors interpret the result as evidence that Bayesian regression and explicit Q-function uncertainty provide substantial benefit.

6 Conclusion

The paper develops LINPSRL and LINUCB for continuous MDPs and extends them to BDQN for high-dimensional deep RL. It reports improved training, convergence, regret, and game performance, while acknowledging that the regret dependence on episode length may be sub-optimal.

  • Contributions: The paper proposes LINPSRL and LINUCB as algorithms for continuous MDPs.LINPSRL uses posterior sampling, while LINUCB uses optimism-based confidence bounds.
  • Contributions: BDQN extends these methods to high-dimensional environments through Thompson sampling and a computationally efficient modification of DDQN.The modification replaces last-layer linear regression with Bayesian linear regression.
  • Findings: The paper reports improvements in training, convergence, regret, and performance across many games.These claims summarize the paper’s concluding empirical assessment.
  • Limitations and future work: The current regret upper bounds may be sub-optimal in their dependence on episode length H.The authors identify tighter bounds, lower bounds, performance guarantees, and extensions beyond linear models as future work.

A Empirical Study

The empirical study compares BDQN with DDQN across Atari games, emphasizing sample complexity, scores, and exploration behavior. BDQN generally reaches strong scores faster, with especially large gains reported for Atlantis.

  • A Empirical Study: BDQN significantly improves sample complexity over DDQN and reaches DDQN’s highest scores with fewer interactions.The study reports both faster convergence and higher scores, not only reduced interaction requirements.
  • A Empirical Study: BDQN was observed to learn better policies in shorter periods because of its exploration-exploitation strategy.Additional Atlantis runs were conducted to examine a recurring performance jump, while some experiments continued until a plateau.
  • A Empirical Study: 64.67k versus 3.24M: on Atlantis, DDQN+ reached 64.67k during evaluation while BDQN reached 3.24M after 20M interactions.After relaxing the episode-length limit, BDQN’s reported Atlantis score increased to 62M after 15M steps.
  • A Empirical Study: Table 3 compares BDQN with DDQN, DDQN+, human scores, and area-under-performance ratios using score and sample-complexity measures.Its columns include score ratios, AuPPr, samples needed to beat human scores, and samples needed to beat DDQN+.
  • A Empirical Study: 62M: BDQN reached this Atlantis score after removing the maximum episode-length limit.The long episode filled much of the replay buffer and caused later forgetting of earlier-game skill; several possible remedies were noted but not implemented.

A.2 Further discussion on Reproducibility

The reproducibility discussion cautions against direct scientific comparisons with external baselines when implementation and environment details differ. Some reported baseline scores were copied or could not be fairly reproduced.

  • A.2 Further discussion on Reproducibility: Scores for bootstrap DQN and NoisyNet were copied from their original papers without modification.The authors also included count-based-method scores despite the source not providing a score table.
  • A.2 Further discussion on Reproducibility: NoisyNet scores used a DQN objective because corresponding DDQN-objective scores were unavailable.The authors explicitly identify this as a limitation of the comparison.
  • A.2 Further discussion on Reproducibility: The authors state that Table 2 cannot scientifically establish superiority over baselines without detailed implementation and environment information.They note that DDQN scores can differ substantially across implementations and papers.

B Why Thompson Sampling and not ε-greedy or Boltzmann exploration

The paper contrasts Thompson sampling with ε-greedy and Boltzmann exploration because it uses uncertainty in addition to estimated action values. This is intended to make exploration more targeted in high-dimensional RL.

  • B Why Thompson Sampling and not ε-greedy or Boltzmann exploration: ε-greedy explores uniformly among non-greedy actions, while Boltzmann exploration samples using estimated Q-values without uncertainty estimates.The paper presents Thompson sampling as incorporating both quantities.
  • B Why Thompson Sampling and not ε-greedy or Boltzmann exploration: ε-greedy can waste exploration probability on actions already estimated to be sub-optimal when uncertainty information is available.The paper’s example assigns equal exploration probability to actions 5 and 6 despite their estimated sub-optimality.
  • B Why Thompson Sampling and not ε-greedy or Boltzmann exploration: Boltzmann exploration can assign similar probabilities to actions with different uncertainty levels, including an action needing more exploration.In the cited example, action 6 has much higher uncertainty than action 5.
  • B Why Thompson Sampling and not ε-greedy or Boltzmann exploration: Thompson sampling uses both estimated Q-values and their uncertainties to carry out more efficient exploration.The paper identifies the missing uncertainty estimate as the limitation of both ε-greedy and Boltzmann strategies.

C BDQN Implementation

BDQN adds Bayesian linear regression and Thompson sampling to a DDQN-style network, periodically sampling last-layer weights while training the feature network. The implementation emphasizes efficient updates, practical tuning, and uncertainty-aware decisions.

  • C BDQN Implementation: BDQN samples a new model periodically from an approximated posterior over last-layer weights to balance exploration and exploitation.The posterior is updated from randomly selected replay-buffer experiences at a separate interval.
  • C BDQN Implementation: The sampled Q-function selects actions through the maximum weighted feature representation, with sampling intervals chosen near the episode length for Atari.The feature network continues to use DDQN-like training.
  • C BDQN Implementation: BDQN updates its posterior from replay-buffer minibatches and uses posterior means for target weights while sampling action weights from the posterior.The network uses RMSProp and DDQN-style target-network updates.
  • C BDQN Implementation: BDQN adds a BLR layer above a convolutional network whose final fully connected representation has size 512.The input consists of four 84 × 84 observations processed through three convolutional layers.
  • C BDQN Implementation: BDQN’s BLR tuning used less than two days of GPU time, while the paper reports no exhaustive hyperparameter search.The authors describe the tuning procedure as simple, fast, and cheap.
  • C BDQN Implementation: DDQN with BDQN’s learning rate initially learned well but later degraded below the original DDQN configuration.The paper highlights DDQN’s sensitivity to learning-rate changes, whereas BDQN used the higher rate without tuning it.
  • C BDQN Implementation: Sampling too frequently can make feature-learning gradients noisier, while sampling too infrequently can make the feature representation unsuitable across sampled last-layer weights.For shorter-horizon problems, the authors suggest separate, more frequent sampling parameters.
  • C BDQN Implementation: The posterior distribution over discounted returns can support a safety criterion based on return variance.For equal-mean actions, higher estimated variance is treated as indicating a less safe action.

E.4 Bayesian Regret of Alg. 1

The section extends the PSRL analysis to Bayesian regret by averaging over models and derives a high-probability regret bound under event ΘT. The proof uses history-conditioned policy and model distributions, concentration terms, and a final failure-probability argument.

  • Bayesian regret: Bayesian regret analysis applies the preceding PSRL argument with an additional expectation over models.The section frames Bayesian regret under a prior over the parameters ω∗h.
  • Bayesian regret: At the beginning of each episode, PSRL draws a model parameter and follows the corresponding policy conditioned on the observed history.Ht denotes the episode history, while πh_t denotes the PSRL policy at time step h.
  • Regret bound: The bound combines logarithmic confidence terms, a dimensional term d log(1 + T L^2/λ), and a regularization-dependent contribution.The displayed expressions include 2 log(1/δ) and λ^1/2Lω terms.
  • Regret bound: With probability at least 1 − δ, event ΘT holds and the regret is bounded by the right-hand side of Eq. 11; otherwise, the failure probability is at most 1/T when δ = 1/T.On the failure event, the analysis uses a maximum regret of T.

E.5 Proof of Lemmas

The proof section establishes the supporting concentration and determinant lemmas used by the analysis. It combines self-normalized bounds, stopping-time arguments, matrix identities, and assumptions controlling the relevant expectations.

  • Matrix lemmas: The determinant lemmas are derived using the matrix determinant lemma and Sylvester’s determinant identity.The resulting determinant relation supports the main statement of Lemma 1.
  • Expectation bounds: Lemma 3 follows from bounding the relevant expectation by 1 under Assumption 1, including the first time step.The proof explicitly invokes the assumption to establish the inequality for the initial step.
  • Concentration lemmas: Lemma 4 extends a self-normalized bound to stopping times and filtrations, with probability at least 1 − Hδ for all h.The proof also uses a stopping time defined by the first failure of the concentration condition.
  • Concentration lemmas: The proof of Lemma 4 treats Ωh as a Gaussian random vector and uses covariance properties together with Markov’s inequality.The argument identifies positive semidefinite and positive definite matrix terms before applying the inequality.
  • Proof details: The proof accounts for bias introduced by ∥Φh and incorporates the optimal action of the pessimistic model in the high-probability argument.These terms appear in the intermediate proof steps for the lemma analysis.
Loading 1802.04412v4…