🤖 machine learning

Information-Based Exploration via Random Features for Reinforcement Learning

This paper introduces Random Feature Information Gain (RFIG), a scalable and theoretically grounded exploration method for deep reinforcement learning that leverages random Fourier features to approximate information gain in non-countable spaces, offering competitive performance with superior interpretability compared to black-box neural network approaches.

Original authors: Waris Radji, Odalric-Ambrym Maillard

Published 2026-07-21

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Waris Radji, Odalric-Ambrym Maillard

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to navigate a giant, foggy maze. The robot's goal is to find the exit and collect as many shiny coins as possible along the way. This is the world of Reinforcement Learning, where an agent learns by trying things, making mistakes, and getting rewards. But here's the tricky part: the robot faces a constant tug-of-war called the exploration-exploitation tradeoff. "Exploitation" means sticking to the path it knows gives coins right now. "Exploration" means wandering into the foggy, unknown corners where there might be a treasure chest, or just a dead end. If the robot never explores, it stays stuck with a few coins. If it explores too much, it wastes time in the fog.

For years, scientists have tried to solve this by giving the robot a "curiosity bonus"—extra points for visiting places it doesn't know well. In simple, small mazes, this is easy: you just count how many times the robot has visited a spot. But in the real world, the "maze" is often a continuous, infinite space where the robot might never visit the exact same spot twice. Counting becomes impossible. To fix this, modern AI uses giant, complex neural networks (digital brains) to guess how "uncertain" a spot is. But these digital brains are like black boxes: they are hard to understand, very sensitive to tiny changes in settings, and sometimes fail mysteriously. This paper asks a simple question: Can we build a curiosity system that is just as good as these complex brains, but is transparent, mathematically sound, and doesn't require a PhD to tune?

The authors of this paper, Waris Radji and Odalric-Ambrym Maillard, say yes. They introduce a new method called Random Feature Information Gain (RFIG). Instead of using a giant, opaque neural network to guess uncertainty, they use a clever mathematical trick involving "random features" and "kernel methods." Think of it like this: imagine you want to know how crowded a park is, but you can't count every single person. Instead of building a massive surveillance system (the neural network), you throw a handful of colored darts randomly into the air. By seeing where the darts land and how they cluster, you can mathematically estimate the crowd density without ever needing to see the people clearly.

In the paper, the researchers show that this dart-throwing method (Random Features) can approximate the "Information Gain"—a fancy term for how much new knowledge you get from visiting a spot. They prove mathematically that this approximation is accurate and that the error stays small, even as the amount of data grows. They tested their method by plugging it into a standard robot learning algorithm (PPO) and letting it play various games, from balancing a pole to navigating complex mazes. The results were impressive: RFIG performed just as well as the top-tier neural network methods, and in some cases, even better. Crucially, unlike the neural networks, RFIG didn't need a delicate, trial-and-error tuning process to work; it was stable and reliable.

The paper argues that we don't always need to make our AI "smarter" by making it more complex and harder to understand. Sometimes, a simpler, mathematically transparent approach like RFIG can do the heavy lifting just as effectively. The authors suggest that this approach could be a game-changer for making AI exploration more reliable and easier to trust, offering a clear, closed-form solution that avoids the "brittleness" of deep learning. While they note that more work is needed to see how this scales to massive image-based tasks, their simulations show that for many control and navigation problems, this "random feature" approach is a powerful, theoretically grounded alternative to the black-box giants.

Technical Summary: Information-Based Exploration via Random Features for Reinforcement Learning

1. Problem Statement

Reinforcement Learning (RL) agents face the fundamental exploration-exploitation tradeoff, requiring a balance between leveraging known rewards and discovering new strategies. In small-scale, discrete environments, the "Optimism in the Face of Uncertainty" (OFU) principle effectively drives exploration using count-based bonuses (e.g., $1/\sqrt{n(s)}$ ). However, in continuous and high-dimensional state spaces, direct counting becomes meaningless as the probability of visiting the exact same state twice is zero.

Current deep RL solutions address this by using neural networks (NNs) to learn representations of uncertainty or pseudo-counts (e.g., Random Network Distillation, Bayesian NNs). While empirically successful, these approaches suffer from:

Limited Theoretical Interpretability: They rely on complex, black-box optimization dynamics.
Hyperparameter Sensitivity: Performance is fragile and heavily dependent on learning rates, architectures, and regularization, often failing to transfer across domains.
Computational Complexity: Some theoretically grounded alternatives, such as Gaussian Processes (GPs), suffer from cubic computational complexity ( $O(n^3)$ ) regarding the dataset size, rendering them unscalable for deep RL.

The paper asks: How can we design alternative exploration mechanisms for deep RL that offer theoretical interpretability and computational tractability while achieving competitive empirical performance?

2. Methodology: Random Feature Information Gain (RFIG)

The authors propose Random Feature Information Gain (RFIG), an exploration bonus derived from Bayesian kernel methods but made scalable for deep RL via Random Fourier Features (RFFs).

Theoretical Foundation

The method is grounded in the concept of Information Gain (IG). In a Bayesian setting, the information gained from querying a state $x^*$ is defined as the reduction in differential entropy of the posterior distribution of the unknown function $f$ . For a Gaussian Process (GP) with noise $\sigma^2$ , the IG is:
$IG(x^* | D_n) = \frac{1}{2} \log \left( 1 + \frac{\sigma_n^2(x^*)}{\sigma^2} \right)$
where $\sigma_n^2(x^*)$ is the posterior variance. This quantity naturally serves as an exploration bonus: high variance (uncertainty) yields high information gain.

Scalability via Random Features

Standard GP inference requires inverting an $n \times n$ kernel matrix, which is $O(n^3)$ . To overcome this, RFIG employs Random Fourier Features (RFFs) (Rahimi and Recht, 2007) to approximate shift-invariant kernels (e.g., RBF) with explicit finite-dimensional mappings $\phi(x) \in \mathbb{R}^D$ .

The kernel $k(x, x')$ is approximated as $\phi(x)^T \phi(x')$ .
The posterior variance is computed using the feature matrix $\Phi_n \in \mathbb{R}^{n \times D}$ , reducing complexity to $O(D^3)$ , where $D$ is the number of random features.
The resulting approximation for Information Gain is:
$\hat{IG}(x^* | D_n) = \frac{1}{2} \log \left( 1 + \phi(x^*)^T (\Phi_n^T \Phi_n + \lambda I_D)^{-1} \phi(x^*) \right)$

Algorithmic Integration

RFIG is integrated into standard deep RL algorithms (specifically PPO) as an intrinsic reward bonus added to the extrinsic reward: $r_{total} = r + \beta r^+$ . Key implementation details include:

State Normalization: Running statistics are used to normalize states to ensure kernel computations are not dominated by scale differences.
Subsampling: A subset of states is used to update the feature matrix $\Phi_t$ to prevent the information gain bonus from vanishing too quickly as $n$ grows and to accelerate matrix inversion convergence.
Matrix Inversion: The Newton-Schulz iteration is used for efficient, numerically stable matrix inversion, allowing for warm-starts and GPU parallelization.
Hyperparameters: The method requires minimal tuning: the number of features $D$ , regularization $\lambda$ , and a length-scale $\ell$ (initialized proportional to the square root of the effective input dimension).

3. Key Contributions

Novel Exploration Bonus: Introduction of RFIG, a closed-form exploration bonus derived from Bayesian kernel theory that approximates information gain in non-countable spaces.
Scalability: Demonstration that RFIG can be scaled to deep RL scenarios by combining Bayesian kernel methods with Random Fourier Features, reducing computational complexity from $O(n^3)$ to $O(D^3)$ .
Theoretical Guarantees: Provision of error bounds showing that the approximation error of RFIG scales with the kernel approximation quality and decreases with sample size, ensuring consistency.
Practical Implementation: A detailed recipe for integrating RFIG into deep RL, including state normalization, subsampling strategies, and efficient matrix inversion techniques, avoiding the backpropagation complexity of neural uncertainty estimators.

4. Experimental Results

The authors evaluated RFIG by integrating it with Proximal Policy Optimization (PPO) across four domains: classic control (Acrobot, MountainCar), sparse-reward continuous control (Brax locomotion), navigation (PointMaze), and MinAtar tasks.

Performance: RFIG achieved competitive performance against established deep exploration baselines, including Random Network Distillation (RND), VIME (Variational Information Maximizing Exploration), and #Explo.
Consistency: Unlike representation-dependent methods (VIME, #Explo) which showed environment-specific success or failure (often due to poor representation learning), RFIG demonstrated remarkable stability across diverse tasks without catastrophic failures.
Efficiency: The JAX implementation showed no significant execution time difference compared to neural network approaches, despite using full matrix inversion.
Comparison: RFIG matched or exceeded RND's performance while offering superior theoretical interpretability.

5. Significance and Claims

The paper claims that RFIG challenges the prevailing assumption that effective exploration in deep RL requires increasingly sophisticated neural architectures with black-box optimization dynamics.

Theoretical Rigor: By leveraging kernel methods, RFIG provides mathematical rigor and closed-form solutions often absent in popular deep RL exploration strategies.
Robustness: It offers a more robust alternative to neural-based methods by avoiding the hyperparameter brittleness and optimization instabilities inherent in training neural networks for uncertainty estimation.
General Applicability: The framework suggests that principled kernel methods can match the empirical performance of neural approaches without requiring representation learning or extensive hyperparameter tuning.

The authors position RFIG not as a replacement for all deep RL methods, but as a theoretically grounded, computationally tractable alternative that bridges the gap between classical exploration theory and modern deep learning scalability.