Abstract
We study reinforcement learning algorithms that utilize randomized value functions for exploration, a class of methods known for strong empirical performance but historically lagging theoretical guarantees. We introduce Single Seed Randomization (SSR), an algorithm that employs a single random seed per episode and Bernstein-type noise to achieve a worst-case regret bound of $\widetilde{O}(H\sqrt{SAT})$ for episodic time-inhomogeneous Markov Decision Processes (MDPs). This result polynomially improves upon existing bounds for randomized methods and, for the first time, matches the $\Omega(H\sqrt{SAT})$ lower bound up to logarithmic factors. Our analysis relies on a novel clipping operation that ensures constant probabilities of optimism and pessimism, alongside a new recursive formula for analyzing the absolute value of estimation errors.
Introduction
In Reinforcement Learning (RL), the agent faces a fundamental trade-off between exploitation (leveraging known high-reward paths) and exploration (investigating uncertain actions to improve future performance). Traditionally, two paradigms have dominated this space:
- Optimism in the Face of Uncertainty (OFU): Algorithms like UCB add a deterministic bonus to uncertain actions. These have long held the crown for theoretical optimality.
- Randomized Exploration: Methods like Thompson Sampling or Randomized Least-Squares Value Iteration (RLSVI) inject stochastic noise into value estimates. These are often preferred in practice due to their ease of implementation in complex systems like deep neural networks.
Despite their practical appeal, randomized methods have historically suffered from a "theoretical tax," with regret bounds significantly higher than the minimax optimal rates achieved by optimistic algorithms. This paper closes that gap, proving that randomized exploration can be just as efficient as its optimistic counterparts in the tabular setting.
Methodology: Single Seed Randomization (SSR)
The authors propose the Single Seed Randomization (SSR) algorithm, which introduces three critical technical innovations to stabilize and optimize exploration.
1. Single Seed Randomization
Previous randomized algorithms typically generated fresh noise at every time step. The authors identify a "cancellation effect" in this approach: noise injected at step $t$ might be negated by noise at step $t+1$, requiring excessively large noise magnitudes to ensure effective exploration. SSR instead samples a single random seed at the start of each episode. This seed generates correlated noise across the entire horizon, creating a consistent "plan" for the episode and preventing the dithering behavior that plagues independent noise methods.
2. Bernstein-type Noise
Most randomized methods rely on Hoeffding-type noise, which scales based only on the range of possible rewards. SSR utilizes Bernstein-type noise, which scales according to the actual variance of the transitions. This allows for much tighter confidence intervals and is the primary driver for achieving the $\sqrt{T}$ optimality.
3. Value-Based Clipping
To prevent stochastic noise from causing value estimates to diverge, SSR employs a specific clipping operation. Unlike traditional methods that focus solely on maintaining optimism, this clipping ensures that the probability of the agent being both optimistic and pessimistic is lower-bounded by a constant. This maintains a stable range for value estimates while preserving the stochasticity required for exploration.
Theoretical Contributions
The primary contribution of this work is the proof that SSR with Bernstein noise achieves a regret bound of $\widetilde{O}(H\sqrt{SAT} + H^4 S^2 A)$. In the regime where the number of interactions $T$ is large, the first term dominates, matching the $\Omega(H\sqrt{SAT})$ lower bound.
To achieve this, the authors developed a new analytical framework. While optimistic algorithms only require proving that the agent does not underestimate the value function, randomized algorithms can fluctuate above or below the true value. The authors introduced a new recursive formula to analyze the absolute value of estimation errors, providing a robust tool for future randomized regret analysis.
Empirical Evaluation: The Deep Sea Benchmark
The authors evaluated SSR on "Deep Sea," a classic hard-exploration environment. In this grid-like MDP, an agent must move "right" at every step to reach a treasure. Moving right incurs a small penalty, while moving left is free but yields no treasure. A random-walking agent is exponentially unlikely to find the treasure.
Key Results: * Superiority over RLSVI: SSR significantly outperformed the previous state-of-the-art randomized method, RLSVI. While RLSVI often failed to find the treasure (resulting in linear regret), SSR consistently reached the goal. * Parity with OFU: SSR performed on par with UCBVI, the leading optimistic algorithm, demonstrating that its theoretical optimality translates to empirical efficiency. * Ablation: The results confirmed that the performance gains were specifically due to the single-seed correlation rather than simple noise tuning.
Conclusion and Future Work
This work represents a milestone in RL theory by demonstrating that randomized exploration is not fundamentally inferior to optimistic exploration. By using correlated noise and variance-aware scaling, SSR achieves minimax optimality in tabular MDPs.
Future research directions include:
- Function Approximation: Extending the optimality proofs from tabular settings to deep RL and general function approximation.
- Horizon-Free Bounds: Investigating whether the dependence on the planning horizon $H$ can be further reduced in time-homogeneous models.
- Lower-Order Terms: Refining the $H^4 S^2 A$ term to improve the algorithm's efficiency in short-term learning scenarios.
Summary updated