Practical $\epsilon$-Exploring Thompson Sampling for Reinforcement Learning with Continuous Controls

PETS maintains multiple posterior samples and performs parallel exploration, which can increase the computational burden, especially when scaling to high-dimensional environments. The need to maintain and update multiple models or samples can lead to higher memory and CPU/GPU requirements, particularly when dealing with large state and action spaces. While PETS uses Thompson Sampling to balance exploration and exploitation, it might still struggle in environments with sparse rewards or deceptive reward structures. The method may over-explore in certain cases, leading to inefficient learning when exploitation would yield better results. Similarly, the $\epsilon$-Exploring Thompson Sampling ($\epsilon$-TS) might lead to suboptimal performance when $\epsilon$ is not well-calibrated.

1. My main complaint for this work is that it doesn’t situate the contribution of the paper relative to other highly related papers such as Ishfaq et al 2024a and Ishfaq et al 2024b. In line 70-74, it introduces the idea of using LMC for TS as if it’s the first work to do so. Proposition C.1, Definition C.2, Lemma C.5, Lemma C.6, Lemma C.7, Lemma C.8, Lemma C.9 all are essentially verbatim to different lemmas used in the proof of Ishfaq et al 2024a. With this respect the novelty of the algorithmic contribution and theoretical analysis are very limited in this paper.

2. Practical $\epsilon$ Exploring Thompson Sampling (PETS) directly borrows ideas/methods from two existing works $\epsilon$-TS [Jin et al 2023] and LMC-LSVI of Ishfaq et al 2024a. As such the novelty in terms of algorithmic design seems limited. Despite borrowing significant chunk of Ishfaq 2024a for algorithm design, the paper fails to properly acknowledge it in their method section, especially in Section 3.1.

3. Also, I think all the assumptions made in the theorem statements such as L-smoothness and Polyak Lojasiewicz inequality in Theorem 3.1 should be clearly defined in the main paper.

4. Missing related work: I think in Section 5, around Line 486, the authors should discuss other provably efficient randomized exploration methods such as Ishfaq et al 2021, Russo 2019, Xiong et al 2022 etc.

5. Missing code: Given the empirical aspect of the work, I think the authors should share the code even during the reviewing process. Could you please share the code base anonymously?

6. Mujoco experiments: for mujoco experiments in Fig3, it was run for 150k or 100k time steps whereas the standard is to run for 1million step. Could you explain why this is the case? With this low number of steps, the result interpretation can be unfair. Also, can you consider stronger baseline such as DSAC-T (Duan et al 2023)?

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" The 1st Reinforcement Learning Conference. 2024b

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

Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. 2019

Xiong et al. Near-optimal randomized exploration for tabular Markov decision processes 2022

Duan et al. DSAC-T: Distributional Soft Actor-Critic with Three Refinements, 2023

• My main concern is the technical novelty. The proof of Theorem 1 seems very similar to the analysis in Ishfaq et al., 2024. What is the main technical challenge or novelty in this work compared to Ishfaq et al., 2024, particularly in proving Theorem 1? A detailed discussion of these technical challenges in the main paper would be very helpful.

• Regarding the experiments, I have several comments:

  1. Generally, a strong exploration strategy is particularly beneficial in sparse reward settings. However, it appears that all the experiments in this paper were conducted in dense reward environments. Do you believe your algorithm would still demonstrate improved performance in sparse reward settings?

  2. The paper lacks an analysis of computational costs. The proposed method appears to be computationally intensive due to the large number of posterior samples and gradient ascent steps, especially in the Cheetah environment where $n=50$, likely resulting in considerable computational overhead. Including a comparison of computational costs with baseline algorithms would be helpful for understanding the contribution of your work.

  3. I wonder if the proposed method might be sensitive to the exploration probability $\epsilon$, given that it varies considerably across different environments. Is your algorithm robust to changes in $\epsilon$?

• Use of LMC and Parallel Markov Chains: This approach essentially amounts to maintaining an ensemble of models and uniformly sampling one at each decision point. This is conceptually similar to existing ensemble sampling methods used to approximate TS. [Line 7 of Algorithm 1]

• Computational Complexity: The paper lacks a thorough analysis of the per-episode computational complexity, especially concerning the number of episodes and the number of parallel Markov chains maintained. The overhead introduced by managing multiple chains and performing multiple optimizations per action selection could impact scalability in large-scale applications.

• Connection to Ensemble Methods: The methodology shows strong parallels to ensemble sampling approaches, such as those found in "Ensemble Langevin DQN" by Dwaracherla & Van Roy, where ensembles are used with Langevin dynamics for exploration. The paper does not acknowledge or discuss these similarities, missing an opportunity to position PETS within the broader context of ensemble-based RL methods.

• Statistical Significance and Computational Cost:

  • Statistical Analysis: The experiments are conducted over a limited number of seeds (5 to 8), which may not provide sufficient statistical power to confirm the results' significance.

  • Computational Overhead: The paper does not quantify the additional computational cost per episode introduced by maintaining multiple parallel Markov chains and performing optimization steps. This omission makes it difficult to assess the practical trade-offs between performance gains and computational efficiency.

• Baseline Comparisons: The experimental comparisons are primarily against base algorithms without PETS. The paper does not compare PETS against Ensemble Langevin DQN [https://arxiv.org/abs/2002.07282]

Related Work Comparison

The paper contributes to the application of TS in continuous action spaces but fails to adequately discuss relevant existing literature, particularly on ensemble methods:

• Ensemble Methods and Approximate TS, Randomized Value Functions:

  • "Ensemble Sampling" by Lu & Van Roy: This work develops ensemble sampling as an approximation to TS, maintaining an ensemble of models and sampling from them to drive exploration. PETS's use of multiple parallel Markov chains closely resembles this approach but lacks acknowledgment of this connection.

  • "Ensemble Langevin DQN" by Dwaracherla & Van Roy: This paper demonstrates that ensemble methods combined with Langevin dynamics can achieve deep exploration without additional complexity for epistemic uncertainty representation. PETS uses a similar strategy but does not reference this work.

  • "Deep Exploration via Bootstrapped DQN" by Osband et al.: Introduces an ensemble-based method (Bootstrapped DQN) for deep exploration in RL, which PETS could be compared against.

  • "Deep Exploration via Randomized Value Functions" by Osband et al.: Discusses using randomized value functions to encourage exploration, which is conceptually related to PETS's approach.

  • "Randomized Value Functions via Multiplicative Normalizing Flows" by Touati et al.: Proposes achieving randomized value functions in high-dimensional domains using variational Bayesian methods, offering an alternative to PETS's LMC sampling.

  • "Q-Star Meets Scalable Posterior Sampling" by Li et al.: Presents an efficient method for approximate posterior sampling in RL, achieving sublinear regret and superior performance in large-scale deep RL benchmarks, which could provide valuable insights or comparisons for PETS.

The omission of these works limits the paper's positioning within the existing body of research and undermines its claim of novelty.

5. Clarity and Presentation

The paper is structured logically, but several aspects could be improved:

• Methodological Clarity:

  • Details on Computational Complexity: A detailed analysis of the per-episode computational complexity is missing. Understanding how the number of episodes and the number of parallel Markov chains impact computational resources is crucial for practical applications.

  • Algorithmic Similarities: The paper does not clarify how its approach differs from or improves upon existing ensemble methods, which could confuse readers familiar with ensemble sampling.

• Algorithm Descriptions:

  • Algorithm 1: Line 7's operation of sampling from multiple models is similar to ensemble sampling, but this is not acknowledged, leading to potential misunderstandings about the novelty of the approach.

• Presentation of Theoretical Results:

  • Regret Analysis: The theoretical analysis may be dense and could benefit from additional explanations or simplifications to enhance accessibility.

6. Overall Impact

While PETS aims to advance exploration strategies in RL with continuous controls, its impact is limited by several factors:

• Novelty: The core methodology closely resembles ensemble sampling approaches already present in the literature. Without acknowledging or differentiating from these methods, the paper's originality is diminished.

• Practical Contribution: The lack of computational complexity analysis raises concerns about the method's scalability and practical applicability in large-scale RL tasks.

• Theoretical and Empirical Validation: Although the paper provides theoretical regret bounds and empirical improvements, these are less compelling without thorough comparisons to existing ensemble-based exploration methods.

Weaknesses:

• Lack of Novelty: The method closely mirrors ensemble sampling techniques without proper acknowledgment or differentiation, undermining claims of innovation.

• Omission of Related Work: Fails to discuss relevant literature on ensemble methods and randomized value functions, which is critical for situating the contribution within the field.

• Insufficient Computational Analysis: Does not provide an analysis of the computational complexity per episode, leaving practical efficiency and scalability unaddressed.

• Limited Experimental Rigor: Experiments lack statistical significance testing and do not compare PETS against other state-of-the-art exploration methods, weakening the empirical validation.

Suggestions for Improvement:

1. Acknowledge and Discuss Related Work: Incorporate discussions of ensemble sampling methods, such as Bootstrapped DQN, Ensemble Sampling, and Ensemble Langevin DQN. Highlight how PETS relates to, differs from, and potentially improves upon these approaches.

2. Clarify Novel Contributions: Clearly articulate what is novel about PETS in comparison to existing ensemble methods. If PETS offers specific advantages or innovations, these should be explicitly stated and justified.

3. Analyze Computational Complexity: Provide a detailed analysis of the per-episode computational cost, including how it scales with the number of episodes and parallel Markov chains. Discuss any trade-offs between computational overhead and performance gains.

4. Enhance Experimental Evaluation:

   • Statistical Significance: Increase the number of random seeds and perform appropriate statistical tests to strengthen the reliability of the results.

   • Comparative Baselines: Include comparisons with other ensemble-based exploration methods and state-of-the-art algorithms to contextualize the performance improvements.

5. Improve Clarity and Presentation:

   • Methodological Details: Expand on the implementation aspects, particularly regarding the optimization methods and how parallel chains are maintained.

   • Algorithm Descriptions: Update algorithm pseudocode to reflect similarities and differences with existing methods, and clearly explain any unique steps.

6. Theoretical Insights: Simplify the theoretical analysis where possible, and provide intuitive explanations to make the content accessible to a broader audience.

By addressing these issues, the paper could significantly strengthen its contribution to the field, offering clearer insights into how PETS advances exploration in reinforcement learning and distinguishing it from existing ensemble methods.