Near-Optimal Randomized Exploration for Tabular Markov Decision Processes

Zhihan Xiong, Ruoqi Shen, Qiwen Cui, Maryam Fazel, Simon S. Du

Introduction

In Reinforcement Learning (RL), agents face a fundamental dilemma: exploring new states to discover potentially higher rewards versus exploiting known states to maximize immediate returns. Theoretically, algorithms based on "Optimism in the Face of Uncertainty" (OFU), such as Upper Confidence Bound (UCB) methods, are the gold standard. They achieve minimax optimal regret bounds. However, UCB algorithms are notoriously difficult to scale to complex, deep RL settings because explicitly computing confidence bounds for neural networks is often computationally intractable.

To circumvent this, practitioners often rely on randomized exploration—such as adding noise to the value function or using noisy networks. While these randomized methods are much easier to implement and perform exceptionally well empirically, their theoretical understanding has historically lagged far behind. Prior to this work, the best-known worst-case regret bound for randomized exploration in tabular Markov Decision Processes (MDPs) was $\tilde{O}(H^2 S\sqrt{AT})$, which falls significantly short of the known theoretical lower bound of $\Omega(H\sqrt{SAT})$.

This paper bridges the theoretical gap between optimistic algorithms and randomized exploration. By introducing a novel "Single Seed Randomization" (SSR) algorithm, the authors prove for the first time that randomized exploration can be just as sample-efficient as optimistic approaches in the worst case, achieving a near-optimal $\tilde{O}(H\sqrt{SAT})$ regret bound.

Methodology: Single Seed Randomization (SSR)

To achieve this theoretical breakthrough, the authors propose the SSR algorithm, which relies on three major algorithmic and analytical innovations:

1. Single Random Seed per Episode

Previous randomized algorithms typically sampled new noise at every single time step. The problem with per-step noise is that independent perturbations often cancel each other out over time, much like a random walk. To guarantee that the agent remains optimistic enough to explore, prior methods had to inject a massive amount of noise, which ultimately destabilized learning. SSR solves this by sampling a single standard Gaussian seed at the start of an episode and using it to perturb the value functions across all time steps. This ensures consistent optimism (or pessimism) throughout the trajectory, allowing the algorithm to explore efficiently with a much smaller perturbation magnitude.

2. Bernstein-Type Noise Magnitude

Just as Bernstein-based bonuses are required to achieve minimax optimal bounds in UCB algorithms, using variance to scale random perturbations is the secret to shaving off a factor of $\sqrt{H}$ in randomized exploration. Instead of scaling the random noise based purely on visit counts (Hoeffding-style), SSR scales the noise using the empirical variance of the value function. This allows the noise to be smaller while still guaranteeing optimism with constant probability.

3. Two-Sided Value Clipping

In UCB algorithms, the estimated value is almost always an upper bound on the true value, meaning the error is one-sided. In randomized exploration, however, the estimate fluctuates above and below the true value. To keep value estimates from exploding, the authors introduce a novel clipping operation. Unlike previous clipping methods that only maintained optimism, this new strategy maintains both optimism and pessimism. This is critical because analyzing randomized algorithms requires bounding the absolute estimation error. To support this, the authors developed a completely new recursive formula to bound the absolute value of the policy estimation error.

Key Theoretical Results

The primary focus of the paper is on mathematical regret bounds for episodic time-inhomogeneous MDPs (where $S$ is the state space size, $A$ is the action space size, $H$ is the planning horizon, and $T$ is the number of interactions).

  • Hoeffding-type Noise: When using standard Hoeffding-based noise, SSR achieves a regret bound of $\tilde{O}(H^{1.5}\sqrt{SAT} + H^4 S^2 A)$. This alone improves upon the previous state-of-the-art for randomized algorithms.
  • Bernstein-type Noise: By upgrading to the variance-aware Bernstein noise, SSR achieves a tighter regret bound of $\tilde{O}(H\sqrt{SAT} + H^4 S^2 A)$.
  • Minimax Optimality: When the number of interactions $T$ is sufficiently large ($T \ge \tilde{\Omega}(H^6 S^3 A)$), the lower-order terms vanish. The regret bound simplifies to $\tilde{O}(H\sqrt{SAT})$, perfectly matching the theoretical lower bound $\Omega(H\sqrt{SAT})$ up to logarithmic factors.

While the paper is heavily theoretical, the authors also validated their approach empirically in the Deep-Sea environment—a standard benchmark for deep exploration—demonstrating that SSR outperforms traditional Randomized Least Square Value Iteration (RLSVI).

Limitations and Future Directions

While this work represents a major theoretical milestone, several open challenges remain:

  1. Large $T$ Requirement: The optimal bound is only strictly achieved when $T$ is very large due to the sub-optimal lower-order term $\tilde{O}(H^4 S^2 A)$. Improving this term to relax the requirement on $T$ is a promising future direction.
  2. Time-Homogeneous MDPs: The paper focuses on time-inhomogeneous MDPs, where transition dynamics can change at each step of the episode. Achieving a "horizon-free" regret bound in time-homogeneous models remains an open problem.
  3. Tabular Focus: The rigorous proofs in this paper apply specifically to tabular MDPs (discrete states and actions). Extending these exact theoretical guarantees to function approximation (such as neural networks used in deep RL) remains a complex but highly impactful challenge for future research.

Summary updated

Abstract

We study algorithms using randomized value functions for exploration in reinforcement learning. This type of algorithms enjoys appealing empirical performance. We show that when we use 1) a single random seed in each episode, and 2) a Bernstein-type magnitude of noise, we obtain a worst-case $\widetilde{O}\left(H\sqrt{SAT}\right)$ regret bound for episodic time-inhomogeneous Markov Decision Process where $S$ is the size of state space, $A$ is the size of action space, $H$ is the planning horizon and $T$ is the number of interactions. This bound polynomially improves all existing bounds for algorithms based on randomized value functions, and for the first time, matches the $\Omega\left(H\sqrt{SAT}\right)$ lower bound up to logarithmic factors. Our result highlights that randomized exploration can be near-optimal, which was previously achieved only by optimistic algorithms. To achieve the desired result, we develop 1) a new clipping operation to ensure both the probability of being optimistic and the probability of being pessimistic are lower bounded by a constant, and 2) a new recursive formula for the absolute value of estimation errors to analyze the regret.
BibTeX
@inproceedings{xiong2022near,
  author = {Zhihan Xiong and Ruoqi Shen and Qiwen Cui and Maryam Fazel and Simon S. Du},
  title = {{Near-Optimal Randomized Exploration for Tabular Markov Decision Processes}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=-h-NVQ92bAT},
}
Figure