Scalable Exploration via Ensemble++

This paper proposes an improved ensemble exploration method called Ensemble++, which incorporates decoupled optimization and lifted index sampling for more efficient exploration and uncertainty estimation. The architecture outperforms existing methods and is scalable in terms of computational cost.

This paper presents Ensemble++, an ensemble sampling method that enhances the computational efficiency of Thompson sampling. Recently, Ensemble+ was developed to tackle this challenge; however, it faces an issue with ensemble coupling that adversely affects its performance. To address this problem, Xu et al. later introduced Langevin Monte Carlo Thompson Sampling, which, unfortunately, incurs high computational costs. The aim of this paper is to improve the approach to ensemble coupling while minimizing computational expenses. The proposed approach, Ensemble++, addresses this by implementing decoupled optimization and lifted index sampling, enhancing exploration and uncertainty estimation. Theoretically, the paper shows that it achieves the same regret bounds as exact Thompson sampling in linear contextual bandits, with a per-step computation complexity of $\tilde{O}(\log T)$. Empirical results in the performance of Ensemble++ are presented.

Scalable exploration is challenging in high-dimensional bandit settings. Ensembling is one (computationally expensive) way to try to approximate thompson sampling; ensembling can be made computationally cheaper by sharing one feature extractor between ensemble members, but can underestimate uncertainty due to the ensemble coupling issue, where ensemble members are too similar.

Authors propose Ensemble++, which uses stop gradients and a high-dimensional ensemble index. Empirically, authors find Ensemble++ outperforms existing methods in bandit settings. Authors analyze regret and computation for Ensemble++ in linear contextual bandit settings; Ensemble++ achieves the same regret bounds as exact TS, and has $\tilde O(\log T)$ per-step computation complexity.

============================ I appreciate the author's response to my questions and comments and have accordingly raised my score.

Scalable exploration in sequential decision-making is challenging, especially in high-dimensional environments. Ensemble sampling, an approximation of Thompson sampling, is widely used but can suffer from performance degradation due to ensemble coupling in shared-layer networks. The Ensemble++ architecture is proposed to overcome this limitation by introducing decoupled optimization and lifted index sampling. Empirical results show that Ensemble++ outperforms existing methods in regret minimization across various tasks.

Dear author,

From the writing, it seems that Ensemble++ is proposed for general sequential decision making problems (that includes reinforcement learning as well) and only for the theoretical regret guarantee, the authors consider the linear contextual bandit setting. Despite claiming to be a general method for sequential decision making problems, the authors missed many relevant papers that tackles exploration in RL. I would like to highlight some of them.

In Line 38, you mention perturbed history exploration and cite Kventon et al 2020 which considered linear bandit setting. In Ishfaq et al 2021, we proposed RLSVI-PHE which uses perturbed history exploration in RL and provides provable regret bound in MDP under general function approximation setting. This work should be cited along with Kventon et al 2020.

In Line 46 (and other places) you discuss Langevin Monte Carlo based Thompson sampling (Xu et al 2022) which only considered bandit setting. However, Ishfaq et al 2024a and Ishfaq et al 2024b, both of them proposes Langevin Monte Carlo based RL algorithms which are both provably efficient and practically efficient for deep RL with SOTA performance among randomized exploration based approaches. These 2 works should also be cited with Xu et al 2022.

I would appreciate if you could cite these works as they are highly relevant and SOTA randomized exploration methods with provable regret guarantees.

Ishfaq, Haque, et al. "Randomized exploration in reinforcement learning with general value function approximation." International Conference on Machine Learning. PMLR, 2021.

Ishfaq, Haque, et al. "Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo." The Twelfth International Conference on Learning Representations. (2024a)

Ishfaq, Haque, et al. "More Efficient Randomized Exploration for Reinforcement Learning via Approximate Sampling." Reinforcement Learning Conference (2024b).

This paper studies ensemble sampling, an approximation of Thompson sampling, which is widely used but prone to performance degradation due to ensemble coupling in shared-layer networks. To address this limitation, the authors propose the Ensemble++ architecture, introducing decoupled optimization and lifted index sampling. Empirical results suggest that the proposed method outperforms existing approaches in regret minimization. However, during the discussion phase, reviewers raised concerns about the consistency of the proposed method and its effectiveness in addressing the core issue of ensemble coupling. Additionally, the focus on regret analysis for linear contextual bandits felt disconnected from the primary challenge of gradient coupling in ensemble sampling. While theoretical insights from linear models can sometimes inform understanding of nonlinear methods, it remains unclear how the provided analysis specifically explains or resolves the challenges in neural network-based ensemble sampling methods. Given these concerns, reviewers were mostly unenthusiastic and leaned toward rejecting the paper. I encourage the authors to address these questions thoroughly and provide a more coherent and aligned presentation in their future version.

Reject

We are writing to formally withdraw our submission, "Scalable Exploration via Ensemble++" (Submission #11456). This paper has recently been accepted for publication at NeurIPS 2025.

We would like to sincerely thank the ICLR 2025 program chairs and the reviewers for their time and effort in reviewing our work.