Research map / Reinforcement learning / Policy gradient and actor-critic

Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgent

ICML 2024 · Reinforcement learning › Policy gradient and actor-critic · approach: Model-based RL with guarantees · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes HyperAgent, a DQN-style RL agent with a last-layer linear hypermodel and index sampling that incrementally approximates posteriors over Q* without conjugacy, with tabular regret guarantees and strong DeepSea and Atari results.

Problem

Exploration in RL requires posterior sampling over the optimal action-value function, but exact posterior sampling is tractable only in conjugate settings, and existing scalable deep RL agents use epsilon-greedy, which is data-inefficient, or ensembles that are costly per step.

Approach

A last-layer linear hypermodel with a random index input, trained with perturbed TD loss and incremental updates, gives approximate posterior samples of Q* whose noise variance tracks visitation counts, enabling Thompson-style deep exploration with bounded per-step computation (log K in tabular theory).

Key results

• On Atari with 2M training data, HyperAgent reaches IQM 1.22 (95% CI 1.15-1.30) versus 0.70 for DDQN(ours) and 0.13 for DDQN†.
• Solves DeepSea up to 120x120 with episodes scaling as Theta(N), and uses only 5% of ENNDQN's parameters at DeepSea N=20.
• Tabular theory: regret O~(H^2 sqrt(SAK)) with per-step computation O(S^2A + SAM), M = O(log(SAHK)).

Measured effects reported in the paper

Surprising findings

• Claims HyperAgent reaches human-level Atari performance with about 15% of the interaction data and 5% of the parameters of BBF, though these comparisons use the authors' own protocol and data extraction.

Limitations

• Regret theory is restricted to tabular, time-inhomogeneous MDPs; the neural-network setting lacks analysis.
• Last-layer linear hypermodel assumption is validated only when the hidden feature map is fixed (one-hot tabular case).

Experimental setup

Datasets: DeepSea Atari 2600 (Arcade Learning Environment)

Benchmarks: DeepSea Atari 2600 (26 games, IQM/median/mean) 8 hardest exploration Atari games

Metrics: IQM human-normalized score median mean interactions to solve DeepSea parameter count

Baselines: DDQN Ensemble+ Rainbow DER HyperDQN BBF EfficientZero ENNDQN LMC-LSVI (AdamLMCDQN) SANE

Builds on: DQN Double DQN Ensemble sampling RLSVI PSRL

Closest papers by meaning

• Hyper: Hyperparameter Robust Efficient Exploration in Reinforcement Learning (ICML 2025 · similarity 0.88)
• Random Latent Exploration for Deep Reinforcement Learning (ICML 2024 · similarity 0.86)
• Adaptive $Q$-Network: On-the-fly Target Selection for Deep Reinforcement Learning (ICLR 2025 · similarity 0.86)
• Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo (ICLR 2024 · similarity 0.86)
• HyperMARL: Adaptive Hypernetworks for Multi-Agent RL (NeurIPS 2025 · similarity 0.85)
• The Effective Horizon Explains Deep RL Performance in Stochastic Environments (ICLR 2024 · similarity 0.85)