Abstract
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.
Introduction
Reinforcement Learning (RL) agents face a fundamental "exploration-exploitation" dilemma: should they stick with what they know works (exploit) or try something new to find a better strategy (explore)?
Most popular deep RL algorithms, like DQN, rely on "blind" exploration strategies like $\epsilon$-greedy, which simply picks a random action every once in a while. These methods don't account for the agent's uncertainty—they treat an action they’ve tried a thousand times the same as one they’ve never seen. While more sophisticated methods like Thompson Sampling exist, they have historically been too computationally expensive to scale to high-dimensional environments like Atari games.
Methods
The authors bridge the gap between theoretical RL and practical deep learning through a two-step approach:
Theoretical Foundation
They first analyze RL in environments where the optimal Q-value is a linear function of state-action features. They propose two algorithms, LINUCB (frequentist) and LINPSRL (Bayesian), and prove that both achieve a regret bound of $\tilde{O}(d\sqrt{T})$, where $d$ is the feature dimension and $T$ is the number of episodes.
The BDQN Algorithm
To scale this to deep RL, they modify the Double DQN (DDQN) architecture. In a standard DDQN, the last layer is a simple linear regression. BDQN replaces this with Bayesian Linear Regression (BLR).
- Posterior Distribution: Instead of learning a single "best guess" for Q-values, BLR maintains a posterior distribution (mean and covariance) over the weights of the last layer. The deep layers of the DQN act as a feature extractor, and Bayesian methods are applied only to the final linear layer to maintain computational efficiency.
- Thompson Sampling: At each step, the agent draws a sample from this posterior. This sample represents a "plausible" version of the world. The agent then acts optimally according to that specific sample, naturally encouraging exploration in areas where the agent is uncertain.
Key Results
BDQN was evaluated on a wide range of Atari games within the Arcade Learning Environment (ALE). The results demonstrated a massive leap in sample efficiency and total performance compared to its predecessor, DDQN, and other exploration-focused methods like NoisyNet and Bootstrap DQN.
- Faster Learning: BDQN reached DDQN’s final performance levels in less than 5 million interactions for nearly half of the games tested.
- Higher Returns: Across the Atari suite, BDQN improved cumulative rewards by a median of 300%, with some games seeing improvements as high as 80,000%.
- Sample Complexity: BDQN reached human-level scores much faster than standard methods. For example, in BattleZone, BDQN reached human level in 25.1M steps, whereas standard DDQN often requires 200M+ steps to plateau.
Conclusion
By explicitly modeling uncertainty in the Q-function, BDQN allows agents to prioritize exploring actions they know the least about. This principled approach to exploration provides significant gains in sample efficiency without the massive computational overhead of fully Bayesian deep neural networks. Future work will investigate tighter theoretical bounds and extend the Bayesian approach to continuous control tasks in robotics.
Summary updated